Multilevel fixed-point-addition-based VLSI placement

TitleMultilevel fixed-point-addition-based VLSI placement
Publication TypeJournal Article
Year of Publication2005
AuthorsHu, B, Marek-Sadowska, M
JournalComputer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Pagination1188 - 1203
Date Publishedaug.
Keywordsforce directed placement, integrated circuit layout, multilevel fixed point addition, pseudocells, quadratic programming, VLSI, VLSI placement
AbstractA placement problem can be formulated as a quadratic program with nonlinear constraints. Those constraints make the problem hard. Omitting the constraints and solving the unconstrained problem results in a placement with substantial cell overlaps. To remove the overlaps, we introduce fixed points into the nonconstrained quadratic-programming formulation. Acting as pseudocells at fixed locations, they can be used to pull cells away from the dense regions to reduce overlapping. We present an in-depth study of the placement technique based on fixed-point addition and prove that fixed points are generalizations of constant additional forces used previously to eliminate cell overlaps. Experimental results on public-domain benchmarks show that the fixed-point-addition-based placer produces better results than the placer based on constant additional forces. We present an efficient multilevel placer based upon the fixed-point technique and demonstrate that it produces competitive results compared to the existing state-of-the-art placers.