VLSI Placement Using Quadratic Programming and Network Partitioning Techniques

VLSI cell placement involves positioning cells within a target placement geometry while minimizing the interconnecting wire length and placement area. In this paper, the placement problem is solved using a combination of quadratic programming, circuit partitioning, clustering and greedy cell interchange heuristics. The solution of a sequence of quadratic programs and circuit partitioning problems provides the general positions of cells in high quality palcement. Computational efficiency is achieved by using an interior point method for solving the sequence of quadratic programs. A very efficient clustering heuristic is used to keep important groups of cells together as the cells are spread throughout the placement area. Numerical results on a set of benchmark circuits illustrate that this new approach produces standard cell placements that are up 17% better in wire length. 14% better in row length and up to 25 times faster than a well known Simulated Annealing placement heuristic.