Article

Free access

Effective partition-driven placement with simultaneous level processing and global net views

Authors:

Shantanu DuttAuthors Info & Claims

ICCAD '00: Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design

Pages 254 - 259

Published: 05 November 2000 Publication History

Abstract

In this paper we take a fresh look at the partition-driven placement (PDP) paradigm for standard-cell placement for wire-length minimization. The goal is to develop several new algorithms for incorporation into a PDP framework that can rectify the well-known drawbacks of traditional PDP (increasingly localized view of nets with increasing levels of the partitioning tree, min-cut objective, inaccuracy and cost of terminal propagation (TP), irreversibility of move decisions), while preserving its considerable advantages (time efficiency, flexibility in accurately incorporating many optimization metrics, and flexibility in satisfying most constraints). We have developed several novel techniques within a PDP-based framework that yield the best wire-length results so far on all but two of the MCNC benchmark suite. Our major innovations are: (1) simultaneous level partitioning (SLP) in which we partition the entire circuit globally in every level of the partitioning tree, across the current cutline(s); (2) cell gain computation based on a global or distributed view of entire nets (thus obviating TP) and on the bounding-box (BB) minimization of nets (as opposed to mincut in prior PDP); (3) move irreversibility tackled in a post-processing phase via vertical and horizontal swaps. Empirical results indicate that our PDP algorithm SPADE (for Simultaneous level PArtitioning with Distributed [i.e., global] nEt views) provides almost 20% better wirelength results than an internal version of "regular" PDP with min-cut based gains, 10.8% better than the previous best PDP method QUAD, 10.6% better than TimberWolf (TW) 7.0, 15.8% better than the state-of-the-art force-directed technique from U. Munich (termed FD-98 here), and 15.3% better than the multilevel placement technique Snap-On. Besides TW7.0, we are also the only ones to report results on the approximately 100K-cell circuit golem3 (12.2% better than TW7.0). Our run times are quite reasonable.

References

[1]

M. Breuer, "A Class of Min-cut Placement Algorithm," Proc. 14th DAC, pp. 284-290, 1977.

Digital Library

[2]

A. Dunlop and B. Kernighan, "A Procedure for Placement of Standard Cell VLSI Circuits," IEEE Trans. CAD, Vol. CAD-4, No. 1, pp. 92-98, Jan. 1985.

[3]

P. Suaris and G. Kedem, "An Algorithm for Quadrisection and Its Application to Standard Cell Placement," IEEE Trans. CAS, Vol. 35, No. 3, pp. 294-303, Mar. 1988.

[4]

D. J-H. Huang and A. B. Kahng, "Partitioning-based Standard-cell Global Placement with An Exact Objective," Proc. ISPD, pp. 18-25, 1997.

Digital Library

[5]

A. E. Caldwell, A. B. Kahng, S. Mantik, I. L. Markov and A. Zelikovsky, "On Wirelength Estimations for Row-Based Placement," IEEE Trans. on CAD, pp. 1265-1278, Vol. 18, No. 9, Sept. 1999.

Digital Library

[6]

C. M. Fiduccia and R. M. Mattheyses, "A Linear-time Heuristic for Improving Network Partitions," Proc. 19th DAC, pp. 175-181, 1982.

Digital Library

[7]

S. Dutt and W. Deng, "A Probability-based Approach to VLSI Circuit Partitioning," Proc. 33rd DAC, pp. 100-105, 1996.

Digital Library

[8]

S. Dutt and W. Deng, "VLSI Circuit Partitioning by Cluster-removal Using Iterative Improvement Techniques," Proc. ICCAD, pp. 194-200, 1996.

Digital Library

[9]

C. J. Alpert and A. B. Kahng, "Recent Directions in Netlist Partitioning: A Survey," Integration, The VLSI Journal, 19(1-2), pp. 1-81, 1995.

Digital Library

[10]

G. Karypis, R. Aggarwal, V. Kumar and S. Shekhar, "Multilevel Hypergraph Partitioning: Application to VLSI Domain," Proc. 34th DAC, pp. 526-529, 1997.

Digital Library

[11]

C. J. Alpert, D. J. Huang and A. B. Kahng, "Multilevel Circuit Partitioning," Proc. 34th DAC, pp. 530-533, 1997.

Digital Library

[12]

C. Sechen, VLSI Placement and Global Routing Using Simulated Annealing, Kluwer, B. V., Deventer, The Netherlands, 1988.

[13]

W-J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits," IEEE Trans. CAD, Mar. 1995.

Digital Library

[14]

J.M. Kleinhans, G. Sigl, F.M. Johannes and K.J. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Trans. CAD, vol. 10, no. 3, pp. 356-365, 1991.

Digital Library

[15]

G. Sigl, K. Doll and F.M. Johannes, "Analytical placement: A Linear or Quadratic Objective Function?", Proc. 28th DAC, pp. 427-432, 1991.

Digital Library

[16]

H. Eisenmann and F. M. Johannes, "Generic Global Placement and Floorplanning," Proc. 35th DAC, pp. 269-274, 1998.

Digital Library

[17]

G. Persky, "PRO: an Automatic String Placement Program for Polycell Layout", Proc. 13th DAC, pp. 417-423, 1976.

Digital Library

[18]

X. Yang, M. Wang, K. Eguro and M. Sarrafzadeh, "A Snap-On Placement Tool", Proc. ISPD-2000, pp. 153-158.

Digital Library

Cited By

Fobel CGréwal GMorton A(2009)Hardware accelerated FPGA placementMicroelectronics Journal10.1016/j.mejo.2008.09.00840:11(1667-1671)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1016/j.mejo.2008.09.008
Kahng AReda SMalik SFix LKahng A(2004)Placement feedbackProceedings of the 41st annual Design Automation Conference10.1145/996566.996670(357-362)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996670
Chen GSapatnekar SPedram MAlpert C(2003)Partition-driven standard cell thermal placementProceedings of the 2003 international symposium on Physical design10.1145/640000.640018(75-80)Online publication date: 6-Apr-2003
https://dl.acm.org/doi/10.1145/640000.640018
Show More Cited By

Recommendations

Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs
DAC '08: Proceedings of the 45th annual Design Automation Conference

Routability is a challenging cost metric for modern large-scale mixed-size placement. Most existing routability-driven placement algorithms apply whitespace allocation to relieve the routing congestion. Nevertheless, we observe that whitespace ...
Routability-Driven Blockage-Aware Macro Placement
DAC '14: Proceedings of the 51st Annual Design Automation Conference

We present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro ...
An effective congestion driven placement framework
ISPD '02: Proceedings of the 2002 international symposium on Physical design

We present a fast but reliable way to detect routing criticalities in VLSI chips. In addition, we show how this congestion estimation can be incorporated into a partitioning based placement algorithm. Different to previous approaches, we do not rerun ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '00: Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design

November 2000

558 pages

ISBN:0780364481

Conference Chair:
Ellen M. Sentovich
Cadence Berkley Labs., Berkley, California

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE Circuits & Systems Society
The IEEE Computer Society DATC

Publisher

IEEE Press

Publication History

Published: 05 November 2000

Check for updates

Qualifiers

Article

Conference

ICCAD '00

Sponsor:

SIGDA

ICCAD '00: International Conference on Computer Aided Design

November 5 - 9, 2000

California, San Jose

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
184
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fobel CGréwal GMorton A(2009)Hardware accelerated FPGA placementMicroelectronics Journal10.1016/j.mejo.2008.09.00840:11(1667-1671)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1016/j.mejo.2008.09.008
Kahng AReda SMalik SFix LKahng A(2004)Placement feedbackProceedings of the 41st annual Design Automation Conference10.1145/996566.996670(357-362)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996670
Chen GSapatnekar SPedram MAlpert C(2003)Partition-driven standard cell thermal placementProceedings of the 2003 international symposium on Physical design10.1145/640000.640018(75-80)Online publication date: 6-Apr-2003
https://dl.acm.org/doi/10.1145/640000.640018
Zhong KDutt SAckland B(2002)Algorithms for simultaneous satisfaction of multiple constraints and objective optimization in a placement flow with application to congestion controlProceedings of the 39th annual Design Automation Conference10.1145/513918.514129(854-859)Online publication date: 10-Jun-2002
https://dl.acm.org/doi/10.1145/513918.514129
Madden PSapatnekar SWiesel M(2001)Reporting of standard cell placement resultsProceedings of the 2001 international symposium on Physical design10.1145/369691.369727(30-35)Online publication date: 1-Apr-2001
https://dl.acm.org/doi/10.1145/369691.369727
Yildiz MMadden PRoy KKang SKoh C(2001)Global objectives for standard cell placementProceedings of the 11th Great Lakes symposium on VLSI10.1145/368122.368801(68-72)Online publication date: 1-Mar-2001
https://dl.acm.org/doi/10.1145/368122.368801

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents