Probabilistic congestion prediction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Probabilistic congestion prediction

Full text

Pdf (258 KB)

Source

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

Phoenix, Arizona, USA

SESSION: Statistical analysis for placement table of contents

Pages: 204 - 209

Year of Publication: 2004

ISBN:1-58113-817-2

Authors

Jurjen Westra	Eindhoven University of Technology, Eindhoven, The Netherlands
Chris Bartels	Eindhoven University of Technology, Eindhoven, The Netherlands
Patrick Groeneveld	Eindhoven University of Technology, Eindhoven, The Netherlands

Sponsors

ACM: Association for Computing Machinery
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 42, Citation Count: 30

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/981066.981110 What is a DOI?

ABSTRACT

Congestion is a fundamental problem in VLSI design flows. Typically, it is handled by feeding back density information to the placers and routers. Fast and accurate congestion estimation is key in order to obtain a design flow with less iterations and higher predictability.Fast congestion prediction is based on an accurate approximation of the actual routing engine. In this paper we show experimentally that the number of two-pin nets with more than two bends in the actual router is negligible. It is also established that the ratio between the number of L-shapes and Z-shapes is more or less a constant.A fast and accurate algorithm for congestion prediction is developed. The above observations are translated into probabilities, that are used to "smear" out a net over its possible realizations. Extensive experimental evidence is provided using industrial designs.

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	Hung-Ming Chen , Hai Zhou , F. Y. YOung , D. F. Wong , Hannah H. Yang , Naveed Sherwani, Integrated floorplanning and interconnect planning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.354-357, November 07-11, 1999, San Jose, California, United States
	2	Jason Cong , Patrick H. Madden, Performance driven multi-layer general area routing for PCB/MCM designs, Proceedings of the 35th annual conference on Design automation, p.356-361, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277144]
	3	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 [doi>10.1145/775832.775842]
	4	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]
	5	Yuchun Ma , Xianlong Hong , Sheqin Dong , Song Chen , Yici Cai , C. K. Cheng , Jun Gu, Dynamic global buffer planning optimization based on detail block locating and congestion analysis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776036]
	6	Magma Design Automation, "Blast Chip 4.0 User Guide".
	7	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]
	8	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]
	9	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 30

	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
	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
	Chen Li , Cheng-Kok Koh , Patrick H. Madden, Floorplan management: incremental placement for gate sizing and buffer insertion, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Chiu-wing Sham , Evangeline F. Y. Young, Congestion prediction in floorplanning, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	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
	Rupesh S. Shelar , Prashant Saxena , Xinning Wang , Sachin S. Sapatnekar, An efficient technology mapping algorithm targeting routing congestion under delay constraints, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Jurjen Westra , Patrick Groeneveld, Is probabilistic congestion estimation worthwhile?, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, USA
	Chiu-wing Sham , Evangeline F. Y. Young, Congestion prediction in early stages, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, 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
	Tianpei Zhang , Sachin S. Sapatnekar, Buffering global interconnects in structured ASIC design, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Tianpei Zhang , Yong Zhan , Sachin S. Sapatnekar, Temperature-aware routing in 3D ICs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Minsik Cho , David Z. Pan, BoxRouter: a new global router based on box expansion and progressive ILP, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	Tianpei Zhang , Sachin S. Sapatnekar, Buffering global interconnects in structured ASIC design, Integration, the VLSI Journal, v.41 n.2, p.171-182, February, 2008
	Yaoguang Wei , Sheqin Dong , Xianlong Hong , Yuchun Ma, An accurate and efficient probabilistic congestion estimation model in x architecture, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
	Taraneh Taghavi , Foad Dabiri , Ani Nahapetian , Majid Sarrafzadeh, Tutorial on congestion prediction, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
	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
	Min Pan , Chris Chu, FastRoute: a step to integrate global routing into placement, 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
	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
	Jarrod A. Roy , Igor L. Markov, High-performance routing at the nanometer scale, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Tung-Chieh Chen , Ashutosh Chakraborty , David Z. Pan, An integrated nonlinear placement framework with congestion and porosity aware buffer planning, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Michael D. Moffitt , Jarrod A. Roy , Igor L. Markov, The coming of age of (academic) global routing, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Jin Hu , Jarrod A. Roy , Igor L. Markov, Sidewinder: a scalable ILP-based router, Proceedings of the 2008 international workshop on System level interconnect prediction, April 05-08, 2008, Newcastle, United Kingdom
	Tung-Chieh Chen , Minsik Cho , David Z. Pan , Yao-Wen Chang, Metal-density driven placement for cmp variation and routability, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Minsik Cho , Katrina Lu , Kun Yuan , David Z. Pan, BoxRouter 2.0: architecture and implementation of a hybrid and robust global router, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Michael D. Moffitt, MaizeRouter: engineering an effective global router, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Yanming Jia , Yici Cai , Xianlong Hong, Full-chip routing system for reducing Cu CMP & ECP variation, Proceedings of the 21st annual symposium on Integrated circuits and system design, September 01-04, 2008, Gramado, Brazil
	Chiu-Wing Sham , Evangeline F. Y. Young , Jingwei Lu, Congestion prediction in early stages of physical design, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.1, p.1-18, January 2009
	Minsik Cho , Katrina Lu , Kun Yuan , David Z. Pan, BoxRouter 2.0: A hybrid and robust global router with layer assignment for routability, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.2, p.1-21, March 2009
	Logan Rakai , Laleh Behjat , Shawki Areibi , Tamas Terlaky, A multilevel congestion-based global router, VLSI Design, 2009, p.1-1, January 2009