Force-Directed Methods for Generic Placement
Authors:
- K.P. VorwerkKVK.P. Vorwerk
- 21 August 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 25 (10) , 2076-2087
Abstract
This paper describes the implementation of a wire length-driven force-directed placer named FDP for generic placement. Specifically, it describes efficient force computation for cell spreading, numerical instabilities during force-directed placement, a means to avoid instabilities, and metrics for proper assessment of cell distribution throughout the placement region. It demonstrates that one of the greatest impediments to achieving high-quality placements using a force-directed placer lies in the large amount of cell overlap present in initial placements. This overlap makes the determination of cell ordering difficult and can lead to the inadvertent separation of highly connected cells. It is shown that median improvement and multilevel clustering improve cell ordering and aid in wire length minimization. Numerical results are presented for both standard cell and mixed-size placement problems. For standard cell problems, the tool generates placements that are, on average, 3% better than Capo9.0, but 5% worse than FengShui2.6. For mixed-size problems, FDP generated placements that are, on average, 2%-5% better than Capo9.0 and -5%--2% better than Fengshui2.6, depending on the presence (or absence) of pin offsets. Run times for FDP are higher than both Capo9.0 and FengShu2.6, although reasonableKeywords
This publication has 24 references indexed in Scilit:
- FastPlace: efficient analytical placement using cell shifting, iterative local refinement,and a hybrid net modelIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005
- Engineering details of a stable force-directed placer2005
- Efficient thermal placement of standard cells in 3D ICs using a force directed approach2004
- Recursive bisection based mixed block placement2004
- Force directed mongrel with physical net constraints2003
- Attractor-repeller approach for global placement2003
- FAR2002
- Runtime and quality tradeoffs in FPGA placement and routing2001
- Generic global placement and floorplanning1998
- A hierarchical O(N log N) force-calculation algorithmNature, 1986