RITUAL - A PERFORMANCE-DRIVEN PLACEMENT ALGORITHM

In this paper we describe an algorithm for obtaining a placement of large scale cell-based IC's subject to performance constraints. The problem is formulated as a constrained programming problem and is solved in two phases: continuous and discrete. Constraints are placed on total path delays including cell and interconnect delays and the behavior of all the paths is captured. Mathematical techniques and heuristics based on Lagrangian relaxation are used to find an approximate solution to the constrained problem. The algorithm yields good results as we show on a set of real examples. On the average, we are able to make between 8% and 30% improvement in the interconnect delay of these examples with little or no impact on chip area after routing. These improvements are obtained by modifying the placement alone. The acronym RITUAL represents the key idea of our technique: Residual Iterative Technique for Updating All Lagrange multipliers.