Premium
VLSI Placement Using Quadratic Programming and Network Partitioning Techniques
Author(s) -
Kennings A.,
Vannelli A.
Publication year - 1997
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.1997.tb00091.x
Subject(s) - heuristics , very large scale integration , simulated annealing , computer science , heuristic , benchmark (surveying) , quadratic programming , cluster analysis , quadratic equation , mathematical optimization , standard cell , placement , algorithm , set (abstract data type) , parallel computing , integrated circuit , mathematics , physical design , geometry , geodesy , machine learning , embedded system , geography , operating system , programming language
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.