An effective congestion driven placement framework

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An effective congestion driven placement framework

Full text

Pdf (810 KB)

Source

International Symposium on Physical Design archive
Proceedings of the 2002 international symposium on Physical design table of contents

San Diego, CA, USA

SESSION: Placement table of contents

Pages: 6 - 11

Year of Publication: 2002

ISBN:1-58113-460-6

Authors

Ulrich Brenner	University of Bonn, Germany
André Rohe	University of Bonn, Germany

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 31, Citation Count: 27

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/505388.505391 What is a DOI?

ABSTRACT

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 parts of the placement algorithm or apply a post-placement optimization, but we use our congestion estimator for a dynamic avoidance of routability problems in one single run of the placement algorithm. Computational experiments on chips with up to 1,300,000 cells are presented: The framework reduces the usage of the most critical routing edges by 9.0% on average, the running time increase for the placement is about 8.7%. However, due to the smaller congestion, the running time of routing tools can be decreased drastically, so the total time for placement and (global) routing is decreased by 47% on average.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C. Albrecht. Global routing by new approximation algorithms for multicommodity flow. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20:622--632, 2001.
	2	Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
	3	Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
	4	Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
	5	Wenting Hou , Hong Yu , Xianlong Hong , Yici Cai , Weimin Wu , Jun Gu , William H. Kao, A new congestion-driven placement algorithm based on cell inflation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.605-608, January 2001, Yokohama, Japan [doi>10.1145/370155.370560]
	6	Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
	7	Patrick Hung , Michael J. Flynn, Stochastic Congestion Model for VLSI Systems, Stanford University, Stanford, CA, 1997
	8	Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
	9	S. Mayrhofer and U. Lauther. Congestion-driven placement using a new multi-partitioning heuristic. In ICCAD-90, pages 332--335. IEEE Computer Society Press, 1990.
	10	Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277121]
	11	Sadiq M. Sait , Habib Youssef, VISI Physical Design Automation: Theory and Practice, McGraw-Hill, Inc., New York, NY, 1994
	12	Majid Sarrafzadeh , M. Sarrafzadeh , C. K. Wong, An Introduction to VLSI Physical Design, McGraw-Hill Higher Education, 1996
	13	C. Sechen. VLSI Placement and Global Routing Using Simulated Annealing. Kluwer, 1988.
	14	Naveed A. Sherwani, Algorithms for VLSI Physcial Design Automation, Kluwer Academic Publishers, Norwell, MA, 1998
	15	Jens Vygen, Algorithms for large-scale flat placement, Proceedings of the 34th annual conference on Design automation, p.746-751, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266360]
	16	Maogang Wang , Majid Sarrafzadeh, On the behavior of congestion minimization during placement, Proceedings of the 1999 international symposium on Physical design, p.145-150, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300044]
	17	Maogang Wang , Majid Sarrafzadeh, Modeling and minimization of routing congestion, Proceedings of the 2000 conference on Asia South Pacific design automation, p.185-190, January 2000, Yokohama, Japan [doi>10.1145/368434.368601]
	18	Maogang Wang , Xiaojian Yang , Kenneth Eguro , Majid Sarrafzadeh, Multi-center congestion estimation and minimization during placement, Proceedings of the 2000 international symposium on Physical design, p.147-152, May 2000, San Diego, California, United States [doi>10.1145/332357.332391]
	19	W Harold Carter, Computer-aided design of integrated circuits, Computer, v.19 n.4, p.19-36, April 1986 [doi>10.1109/MC.1986.1663203]
	20	M. Wang, X. Yang, and M. Sarrafzadeh. Dragon2000: Standard-cell placement tool for large industry designs, 2000.
	21	D. F. Wong , H. W. Leong , C. L. Liu, Simulated annealing for VLSI design, Kluwer Academic Publishers, Norwell, MA, 1988
	22	Xiaojian Yang , Ryan Kastner , Majid Sarrafzadeh, Congestion estimation during top-down placement, Proceedings of the 2001 international symposium on Physical design, p.164-169, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369761]
	23	Xiaojian Yang , Ryan Kastner , Majid Sarrafzadeh, Congestion estimation during top-down placement, Proceedings of the 2001 international symposium on Physical design, p.164-169, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369761]

CITED BY 27

	Jarrod A. Roy , James F. Lu , Igor L. Markov, Seeing the forest and the trees: Steiner wirelength optimization in placemen, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Bo Hu , Malgorzata Marek-Sadowska, Congestion minimization during placement without estimation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.739-745, November 10-14, 2002, San Jose, California
	Mehdi Saeedi , Morteza Saheb Zamani , Ali Jahanian, Prediction and reduction of routing congestion, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Saurabh N. Adya , Mehmet C. Yildiz , Igor L. Markov , Paul G. Villarrubia , Phiroze N. Parakh , Patrick H. Madden, Benchmarking for large-scale placement and beyond, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Raia T. Hadsell , Patrick H. Madden, Improved global routing through congestion estimation, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Andrew B. Kahng , Xu Xu, Accurate pseudo-constructive wirelength and congestion estimation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	David E. Lackey , Paul S. Zuchowski , Juergen Koehl, Designing mega-ASICs in nanogate technologies, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Jason Cong , Joseph R. Shinnerl , Min Xie , Tim Kong , Xin Yuan, Large-scale circuit placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.389-430, April 2005
	Navaratnasothie Selvakkumaran , Phiroze N. Parakh , George Karypis, Perimeter-degree: a priori metric for directly measuring and homogenizing interconnection complexity in multilevel placement, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	Gi-Joon Nam , Charles J. Alpert , Paul Villarrubia , Bruce Winter , Mehmet Yildiz, The ISPD2005 placement contest and benchmark suite, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Christoph Bartoschek , Stephan Held , Dieter Rautenbach , Jens Vygen, Efficient generation of short and fast repeater tree topologies, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Juergen Koehl , David E. Lackey , George Doerre, IBM's 50 Million gate ASICs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Minsik Cho , Hongjoong Shin , David Z. Pan, Fast substrate noise-aware floorplanning with preference directed graph for mixed-signal SOCs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Qinghua Liu , Malgorzata Marek-Sadowska, A congestion-driven placement framework with local congestion prediction, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Jinan Lou , Wei Chen, Cross talk driven placement, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On whitespace and stability in physical synthesis, Integration, the VLSI Journal, v.39 n.4, p.340-362, July 2006
	Mehdi Saeedi , Morteza Saheb Zamani , Ali Jahanian, Evaluation, prediction and reduction of routing congestion, Microelectronics Journal, v.38 n.8-9, p.942-958, August, 2007
	Marvin Tom , David Leong , Guy Lemieux, Un/DoPack: re-clustering of large system-on-chip designs with interconnect variation for low-cost FPGAs, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Peter Spindler , Frank M. Johannes, Fast and accurate routing demand estimation for efficient routability-driven placement, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
	S. N. Adya , S. Chaturvedi , J. A. Roy , D. A. Papa , I. L. Markov, Unification of partitioning, placement and floorplanning, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.550-557, November 07-11, 2004
	D. Jariwala , J. Lillis, On interactions between routing and detailed placement, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.387-393, November 07-11, 2004
	Chen Li , Min Xie , Cheng-Kok Koh , J. Cong , P. H. Madden, Routability-driven placement and white space allocation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.394-401, November 07-11, 2004
	Haoxing Ren , D. Z. Pan , P. G. Villarubia, True crosstalk aware incremental placement with noise map, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.402-409, November 07-11, 2004
	Tony F. Chan , Jason Cong , Tim Kong , Joseph R. Shinnerl , Kenton Sze, An Enhanced Multilevel Algorithm for Circuit Placement, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.299, November 09-13, 2003
	Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On Whitespace and Stability in Mixed-Size Placement and Physical Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.311, November 09-13, 2003
	Jason Cong , Tim Kong , Joseph R. Shinnerl , Min Xie , Xin Yuan, Large-Scale Circuit Placement: Gap and Promise, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.883, November 09-13, 2003
	Kalliopi Tsota , Cheng-Kok Koh , Venkataramanan Balakrishnan, Guiding global placement with wire density, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California