Simultaneous Technology Mapping and Placement for Delay Minimization
Abstract
Abstract—Technology mapping and placement have a significant impact on delays in standard cell-based very large
scale integrated circuits. Traditionally, these steps are applied
separately to optimize the delays, possibly since efficient algorithms that allow the simultaneous exploration of the mapping
and placement solution spaces are unknown. In this paper, we
present an exact polynomial time algorithm for delay-optimal
placement of a tree and extend the same to simultaneous
technology mapping and placement for the optimal delay in
the tree. We extend the algorithm by employing Lagrangian
relaxation technique, which assesses the timing criticality of paths
beyond a tree, to optimize the delays in directed acyclic graphs.
Experimental results on benchmark circuits in a 70 nm technology show that our algorithms improve timing significantly with
remarkably less runtimes compared to a competitive approach
of iterative conventional timing-driven mapping and multilevel placement.
Index Terms—algorithms, directed acyclic graph, physical
synthesis, placement, technology mapping, tree.