Estimating routing congestion using probabilistic analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Estimating routing congestion using probabilistic analysis

Full text

Pdf (326 KB)

Source

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

Sonoma, California, United States

Pages: 112 - 117

Year of Publication: 2001

ISBN:1-58113-347-2

Authors

Jinan Lou	Synopsys Inc., 700 E. Middlefield Road, Mountain View, CA
Shankar Krishnamoorthy	Synopsys Inc., 700 E. Middlefield Road, Mountain View, CA
Henry S. Sheng	Synopsys Inc., 700 E. Middlefield Road, Mountain View, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 33, Citation Count: 40

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

ABSTRACT

Design routability is a major concern in the ASIC design flow, particularly with todays increasingly aggressive process technology nodes. Increased die areas, cell densities, routing layers, and net count all contribute to complex interconnect requirements, which can significantly deteriorate performance, and sometimes lead to unroutable solutions. Congestion analysis and optimization must be performed early in the design cycle to improve routability. This paper presents a congestion estimation algorithm for a placed netlist. We propose a net-based stochastic model for computing expected horizontal and vertical track usage, which considers routing blockages. The main advantages of this algorithm are accuracy and fast runtime. We show that the congestion estimated by this algorithm correlates well with post-route congestion, and show experimental results of subsequent congestion optimization based this algorithm.

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	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
	2	J. M. Kleinhans, S. Sigl, F. M. Johannes and K. J. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization," IEEE Transactions on Computer Aided Design, Vol. 10, No. 3, pages 356-365, 1991
	3	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	4	S. Mayrhofer and U. Lauther, "Congestion-Driven Placement Using a New Multi-partitioning Heuristic," Proceedings of International Conference on Computer Aided Design, pages 332-335, 1990
	5	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]
	6	Carl Sechen , Alberto Sangiovanni-Vincentelli, TimberWolf3.2: a new standard cell placement and global routing package, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.432-439, July 1986, Las Vegas, Nevada, United States
	7	Naveed A. Sherwani, Algorithms for VLSI Physcial Design Automation, Kluwer Academic Publishers, Norwell, MA, 1998
	8	R. S. Tsay, S. C. Chang and J. Thorvaldson, "Early Wireability Checking and 2-D Congestion-Driven Circuit Placement," Proceedings of Fifth Annual IEEE International ASIC Conference and Exhibit, pages 50-53, 1992
	9	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]
	10	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]

CITED BY 40

	Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Routability driven white space allocation for fixed-die standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Chiu Wing Sham , Evangeline F. Y. Young, Routability driven floorplanner with buffer block planning, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Parivallal Kannan , Shankar Balachandran , Dinesh Bhatia, On metrics for comparing routability estimation methods for FPGAs, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, 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
	Ulrich Brenner , André Rohe, An effective congestion driven placement framework, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, 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
	Xiaojian Yang , Ryan Kastner , Majid Sarrafzadeh, Congestion reduction during placement based on integer programming, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	X. Yang , M. Wang , R. Kastner , S. Ghiasi , M. Sarrafzadeh, Congestion reduction during placement with provably good approximation bound, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.316-333, July 2003
	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
	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
	Qinghua Liu , Malgorzata Marek-Sadowska, Pre-layout wire length and congestion estimation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Parivallal Kannan , Shankar Balachandran , Dinesh Bhatia, On metrics for comparing interconnect estimation methods for FPGAs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.4, p.381-385, April 2004
	Arvind Kumar , Sandip Tiwari, Defect tolerance for nanocomputer architecture, Proceedings of the 2004 international workshop on System level interconnect prediction, February 14-15, 2004, Paris, France
	Zion Cien Shen , Chris C. N. Chu, Accurate and efficient flow based congestion estimation in floorplanning, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.671-676, January 27-30, 2004, Yokohama, Japan
	CeRA: A Router for Symmetrical FPGAs Based on Exact Routing Density Evaluation, IEEE Transactions on Computers, v.53 n.7, p.829-842, July 2004
	Jurjen Westra , Chris Bartels , Patrick Groeneveld, Probabilistic congestion prediction, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, 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
	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
	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
	Chiu-wing Sham , Evangeline F. Y. Young , Hai Zhou, Interconnect-driven floorplanning by searching alternative packings, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Jinjun Xiong , Lei He, Probabilistic congestion model considering shielding for crosstalk reduction, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Keith W. C. Wong , Evangeline F. Y. Young, Fast buffer planning and congestion optimization in interconnect-driven floorplanning, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, 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
	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
	Yajun Ran , Malgorzata Marek-Sadowska, Via-configurable routing architectures and fast design mappability estimation for regular fabrics, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.9, p.998-1009, September 2006
	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
	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
	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
	Steve T. W. Lai , Evangeline F. Y. Young , Chris C. N. Chu, A New and Efficient Congestion Evaluation Model in Floorplanning: Wire Density Control with Twin Binary Trees, Proceedings of the conference on Design, Automation and Test in Europe, p.10856, March 03-07, 2003
	Shankar Balachandran , Parivallal Kannan , Dinesh Bhatia, On Routing Demand and Congestion Estimation for FPGAs, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.639, January 07-11, 2002
	Yi-Lin Hsieh , Tsai-Ming Hsieh, A New Effective Congestion Model in Floorplan Design, Proceedings of the conference on Design, automation and test in Europe, p.21204, February 16-20, 2004
	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
	Chiu-Wing Sham , Evangeline F. Y. Young , Hai Zhou, Optimizing wirelength and routability by searching alternative packings in floorplanning, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.1, p.1-13, January 2008
	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
	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
	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
	Steve T. W. Lai , Evangeline F. Y. Young , Chris C. N. Chu, Handling routability in floorplan design with twin binary trees, Integration, the VLSI Journal, v.42 n.4, p.449-456, September, 2009
	Robert Fischbach , Jens Lienig , Tilo Meister, From 3D circuit technologies and data structures to interconnect prediction, Proceedings of the 11th international workshop on System level interconnect prediction, July 26-27, 2009, San Francisco, CA, USA