Article

Engineering details of a stable force-directed placer

Authors:

A. VannelliAuthors Info & Claims

ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design

Pages 573 - 580

https://doi.org/10.1109/ICCAD.2004.1382642

Published: 07 November 2004 Publication History

Abstract

Analytic placement methods that simultaneously minimize wire length and spread cells are receiving renewed attention from both academia and industry. We describe the implementation details of a force-directed placer, FDP. Specifically, we provide: (1) a description of efficient force computation for spreading cells; (2) an illustration of numerical instability in these methods and a means by which these instabilities are avoided; (3) spread metrics for measuring cell distribution throughout the placement region; and (4) a complementary technique which aids in directly minimizing HPWL. We present results comparing our analytic placer to other academic tools for both standard cell and mixed-size designs. Compared to Kraftwerk and Capo 8.7, our tool produces results with an average improvement of 9% and 3%, respectively.

References

[1]

{1} W. Swartz and C. Sechen, "Timing driven placement for large standard cell circuits," in Proc. of DAC, pp. 211-215, 1995.

Digital Library

[2]

{2} V. Betz and J. Rose, "VPR: A new packing, placement and routing tool for FPGA research," in Field-Programmable Logic and Applications (W. Luk, P. Y. Cheung, and M. Glesner, eds.), pp. 213-222, Springer-Verlag, Berlin, 1997.

Digital Library

[3]

{3} A.E. Dunlop and B. W. Kernighan, "A placement procedure for standard-cell VLSI circuits," Trans. on CAD, vol. 4, pp. 92-98, January 1985.

Digital Library

[4]

{4} A.E. Caldwell, A. B. Kahng, and I. Markov, "Can recursive bisection alone produce routable placements?," in Proc. of DAC, pp. 477-482, ACM Press, 2000.

Digital Library

[5]

{5} A. Khatkhate, C. Li, A. R. Agnihotri, M. C. Yildiz, S. Ono, C.-K. Koh, and P. H. Madden, "Recursive bisection based mixed block placement," in Proc. of ISPD, April 2004.

Digital Library

[6]

{6} J. Vygen, "Algorithms for large-scale flat placement," in Proc. of DAC, pp. 746-751, ACM Press, 1997.

Digital Library

[7]

{7} J. Kleinhans, G. Sigl, F. Johannes, and K. Antreich, "GORDIAN: VLSI placement by quadratic programming and slicing optimization," Trans. on CAD, vol. 10, pp. 356-365, March 1991.

Digital Library

[8]

{8} H. Etawil, S. Areibi, and A. Vannelli, "Attractor-repeller approach for global placement," in Proc. of ICCAD, pp. 20-24, 1999.

Digital Library

[9]

{9} G. Sigl, K. Doll, and F. Johannes, "Analytical placement: A linear or a quadratic objective function?" in Proc. of DAC, pp. 427-432, June 1991.

Digital Library

[10]

{10} H. Eisenmann and E M. Johannes, 'Generic global placement and floorplanning," in Proc. of DAC, pp. 269-274, ACM Press, 1998.

Digital Library

[11]

{11} B. Hu and M. Marek-Sadowska, "FAR: Fixed-points addition & relaxation based placement,' in Proc. of ISPD, pp. 161-166, ACM Press, 2002.

Digital Library

[12]

{12} F. Mo, A. Tabbara, and R. K. Brayton, "A timing-driven macro-cell placement algorithm," in Proc. of ICCAD, pp. 322-327, 2001.

Digital Library

[13]

{13} C. Mulpuri and S. Hauck, "Runtime and quality tradeoffs in FPGA placement and routing," in Proc. of FPGA, pp. 29-36, ACM Press, 2001.

Digital Library

[14]

{14} B. Goplen and S. S. Sapatnekar, "Efficient thermal placement of standard cells in 3D ICs using a force directed approach," in Proc. of ICCAD, pp. 86-89, IEEE Press, 2003.

Digital Library

[15]

{15} "The Boost C++ library," http://www.boost.org, Current July 2004.

[16]

{16} U. T. Mello and I. Khabibrakhmanov, "On the reusability and numeric efficiency of C++ packages in scientific computing," in Proc. of the ClusterWorld Conference and Expo, June 2003.

[17]

{17} J. George, Computer Implementation of the Finite-Element Method. Ph.D. thesis, Stanford University, 1971.

Digital Library

[18]

{18} N. Viswanathan and C. C.-N. Chu, "Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model," in Proc. of ISPD, April 2004.

Digital Library

[19]

{19} J. Barnes and P. Hut, "A hierarchical O(n logn) force calculation algorithm," Nature, vol. 324, 1986.

[20]

{20} M.H. Overmars and C.-K. Yap, "New upper bounds in Klee's measure problem," SIAM Journal on Computing, vol. 20, no. 6, pp. 1034-1045, 1991.

Digital Library

[21]

{21} J. Bentley, "Algorithms for Klee's rectangle problems." Unpublished Manuscript, 1977.

[22]

{22} S.-W. Hur, T. Cao, K. Rajagopal, Y. Parasuram, A. Chowdhary, V. Tiourin, and B. Halpin, "Force directed Mongrel with physical net constraints," in Proc. of DAC, pp. 214-219, ACM Press, 2003.

Digital Library

[23]

{23} A. Kennings and I. Markov, "Analytical minimization of half-perimeter wirelength," in Proc. of ASPDAC, pp. 179-184, ACM/IEEE, January 2000.

Digital Library

[24]

{24} G. Karypis, Multilevel Optimization and VLSICAD, ch. 3. Boston: Kluwer Academic Publishers, 2002.

[25]

{25} S.N. Adya and I. L. Markov, "Fixed-outline floorplanning: Enabling hierarchical design," Trans. on VLSI, vol. 11, pp. 1120-1135, December 2003.

Digital Library

[26]

{26} S. Adya and I. Markov, "Combinatorial techniques for mixed-size placement" Trans. on DAES, 2004. To appear.

Digital Library

[27]

{27} S. Adya and I. Markov, "Consistent placement of macro-blocks using floorplanning and standard-cell placement," in Proc. of ISPD, ACM Press, 2002.

Digital Library

[28]

{28} A. Saurabh and I. Markov, "ISPD02 mixed-size placement benchmarks." http://vlsicad.eees.umich.edu/BK/ISPD02bench, Current July 2004.

[29]

{29} X.Y.M. Wang and M. Sarrafzadeh, "Dragon2000: Standard-cell placement tool for large industry circuits," in Proc. of ICCAD, November 2000.

Digital Library

[30]

{30} C.-C. Chang, J. Cong, and X. Yuan, "Multi-level placement for large-scale IC designs," in Proc. of ASPDAC, pp. 325-330, 2003.

Digital Library

Cited By

Gharibian FShannon LJamieson PChung K(2013)Analyzing System-Level Information’s Correlation to FPGA PlacementACM Transactions on Reconfigurable Technology and Systems10.1145/25019856:3(1-21)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2501985
Lee DMarkov IChang YHu J(2011)Obstacle-aware clock-tree shaping during placementProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960425(123-130)Online publication date: 27-Mar-2011
https://dl.acm.org/doi/10.1145/1960397.1960425
Vorwerk KKennings AGreene J(2009)Improving simulated annealing-based FPGA placement with directed movesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.200916728:2(179-192)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1109/TCAD.2008.2009167
Show More Cited By

Recommendations

A force-directed macro-cell placer
ICCAD '00: Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design

In this paper we present a novel force-directed placement algorithm, which is used to solve macro-cell placement problems. A new wire model replaces the traditional clique model and makes possible early awareness of routing congestion. Issues such as ...
Force directed mongrel with physical net constraints
DAC '03: Proceedings of the 40th annual Design Automation Conference

This paper describes a new force directed global placement algorithm that exploits and extends techniques from two leading placers, Force-directed [12] [26] and Mongrel [22]. It combines the strengths of force directed global placement with Mongrel's ...
Implementation and extensibility of an analytic placer

Automated cell placement is a critical problem in very large scale integration (VLSI) physical design. New analytical placement methods that simultaneously spread cells and optimize wirelength have recently received much attention from both academia and ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design

November 2004

913 pages

ISBN:0780387023

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 07 November 2004

Check for updates

Qualifiers

Article

Conference

ICCAD04

Sponsor:

SIGDA

ICCAD04: The International Conference on Computer-Aided Design 2004

November 7 - 11, 2004

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Upcoming Conference

ICCAD '24

Sponsor:
sigda

IEEE/ACM International Conference on Computer-Aided Design

October 27 - 31, 2024

New York , NY , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
213
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gharibian FShannon LJamieson PChung K(2013)Analyzing System-Level Information’s Correlation to FPGA PlacementACM Transactions on Reconfigurable Technology and Systems10.1145/25019856:3(1-21)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2501985
Lee DMarkov IChang YHu J(2011)Obstacle-aware clock-tree shaping during placementProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960425(123-130)Online publication date: 27-Mar-2011
https://dl.acm.org/doi/10.1145/1960397.1960425
Vorwerk KKennings AGreene J(2009)Improving simulated annealing-based FPGA placement with directed movesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2008.200916728:2(179-192)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1109/TCAD.2008.2009167
Wang YZhou QCai YHu JHong XBian JKyung CChoi KHa S(2008)Low power clock buffer planning methodology in F-D placement for large scale circuit designProceedings of the 2008 Asia and South Pacific Design Automation Conference10.5555/1356802.1356894(370-375)Online publication date: 21-Jan-2008
https://dl.acm.org/doi/10.5555/1356802.1356894
Luo TPan DKyung CChoi KHa S(2008)DPlace2.0Proceedings of the 2008 Asia and South Pacific Design Automation Conference10.5555/1356802.1356890(346-351)Online publication date: 21-Jan-2008
https://dl.acm.org/doi/10.5555/1356802.1356890
Zhou PMa YLi ZDick RShang LZhou HHong XZhou QGielen G(2007)3D-STAFProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326196(590-597)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326196
Li JBehjat LHuang JMadden PPan D(2007)An effective clustering algorithm for mixed-size placementProceedings of the 2007 international symposium on Physical design10.1145/1231996.1232020(111-118)Online publication date: 18-Mar-2007
https://dl.acm.org/doi/10.1145/1231996.1232020
Vorwerk KKennings AChen DBehjat LZhou HMacii EYan ZMassoud Y(2007)Floorplan repair using dynamic whitespace managementProceedings of the 17th ACM Great Lakes symposium on VLSI10.1145/1228784.1228915(552-557)Online publication date: 11-Mar-2007
https://dl.acm.org/doi/10.1145/1228784.1228915
Li JBehjat LScheffer L(2006)Net clusterProceedings of the 2006 international symposium on Physical design10.1145/1123008.1123051(200-205)Online publication date: 9-Apr-2006
https://dl.acm.org/doi/10.1145/1123008.1123051
Xiong JWong YSarto EHe LHirose F(2006)Constraint driven I/O planning and placement for chip-package co-designProceedings of the 2006 Asia and South Pacific Design Automation Conference10.1145/1118299.1118356(207-212)Online publication date: 24-Jan-2006
https://dl.acm.org/doi/10.1145/1118299.1118356
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents