Simultaneous Technology Mapping and Placement for Delay Minimization
Venue
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, vol. 30 (2011), pp. 416-426
Publication Year
2011
Authors
Yifang Liu, Rupesh S. Shelar, Jiang Hu
BibTeX
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.
