Constraint Satisfaction in Incremental Placement with Application to Performance Optimization under Power Constraints. ICCD’07

We present new techniques for explicit constraint satisfac-tion in the incremental placement process. Our algorithm employs a Lagrangian Relaxation (LR) type approach in the analytical global placement stage to solve the constrained optimization problem. We establish theoretical results that prove the optimality of this stage. In the detailed place-ment stage, we develop a constraint-monitoring and satisfac-tion mechanism in a network (n/w) ow based detailed place-ment framework proposed recently, and empirically show its near-optimality. We establish the effectiveness of our general constraint-satisfaction methods by applying them to the prob-lem of timing-driven optimization under power constraints. We overlay our algorithms on a recently developed uncon-strained timing-driven incremental placement method Flow-Place. On a large number of benchmarks with up to 210K cells, our constraint satisfaction algorithms obtain an av-erage timing improvement of 12.4 % under a 3 % power in-crease limit (the actual average power increase incurred is only 2.1%), while the original unconstrained method gives an average power increase of 8.4 % for a timing improvement of 17.3%. Our techniques thus yield a tradeoff of 75 % power improvement to 28 % timing deterioration for the given con-straint. Our constraint-satisfying incremental placer is also quite fast, e.g., its run time for the 210K-cell circuit ibm18 is only 1541 secs.