Congestion driven quadratic placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Congestion driven quadratic placement

Full text

Pdf (216 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 35th annual Design Automation Conference table of contents

San Francisco, California, United States

Pages: 275 - 278

Year of Publication: 1998

ISBN:0-89791-964-5

Authors

Phiroze N. Parakh	University Of Michigan, 1301 Beal Ave, EECS - ACAL, Ann Arbor, MI
Richard B. Brown	University Of Michigan, 1301 Beal Ave, EECS - ACAL, Ann Arbor, MI
Karem A. Sakallah	University Of Michigan, 1301 Beal Ave, EECS - ACAL, Ann Arbor, MI

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 16, Citation Count: 36

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

ABSTRACT

This paper introduces and demonstrates an extension to quadratic placement that accounts for wiring congestion. The algorithm uses an A* router and line-probe heuristics on region-based routing graphs to compute routing cost. The interplay between routing analysis and quadratic placement using a growth matrix permits global treatment of congestion. Further reduction in congestion is obtained by the relaxation of pin constraints. Experiments show improvements in wireability.

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	Kenneth D. Boese , Andrew B. Kahng , Gabriel Robins, High-performance routing trees with identified critical sinks, Proceedings of the 30th international conference on Design automation, p.182-187, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164662]
	3	David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
	4	E.S. David et. al, "Meshach: Matrix Computations in C". Proceedings of the Center forMathematics and its Applications. Australian National University, vol. 32, 1994.
	5	G.H. Golub et. al, "Matrix computations", The Johns Hopkins University Press, 2nd ed.
	6	Georg Sigl , Konrad Doll , Frank M. Johannes, Analytical placement: A linear or a quadratic objective function?, Proceedings of the 28th conference on ACM/IEEE design automation, p.427-432, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127707]
	7	J.M. Kleinhans et. al, "GORDIAN: VLSI placement by quadratic programming and slicing optimization". 1991 IEEE TCADICS, vol. 10, no.3, pp. 356-5.
	8	P.R. Suaris et. al, "A quadrisection-based combined place and route scheme for standard cells".1989 IEEETCADICS, vol.8, no.3, pp. 234-244.
	9	Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, Proud: a fast sea-of-gates placement algorithm, Proceedings of the 25th ACM/IEEE conference on Design automation, p.318-323, June 12-15, 1988, Atlantic City, New Jersey, United States
	10	S.-Mayrhofer et. al,"Congestlon-driven placement using a new multi-partitioning heuristic".IEEE ICCAD 90, pp. -332-5.
	11	S. Prasitjutrakul et. al,"A timinlg-driven global router for custom chip design". 19901EEEICCAD, pp. 48-51.
	12	S. Yousef, "Iterative methods for sparse linear systems". PWS Publishing Company.
	13	W. Dongsheng et. al, "Performance-driven interconnect global routing .Proc. 6th GreatLakesSymp'~nVLSl' pp. 132-6.
	14	Y. Saab, "A fast clustering-based min-cut placement algorithm with simulated-annealing performance". 199~LSI Design, vol.5, no.l, pp. 37-48.

CITED BY 36

	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
	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
	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
	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
	Ke Zhong , Shantanu Dutt, Algorithms for simultaneous satisfaction of multiple constraints and objective optimization in a placement flow with application to congestion control, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	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
	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
	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
	Phiroze N. Parakh , Richard B. Brown, Crosstalk constrained global route embedding, Proceedings of the 1999 international symposium on Physical design, p.201-206, April 12-14, 1999, Monterey, California, United States
	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
	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
	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
	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
	Stefan Thomas Obenaus , Ted H. Szymanski, Gravity: Fast placement for 3-D VLSI, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.3, p.298-315, July 2003
	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
	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
	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
	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
	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
	Davide Pandini , Lawrence T. Pileggi , Andrzej J. Strojwas, Bounding the efforts on congestion optimization for physical synthesis, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA
	Davide Pandini , Lawrence T. Pileggi , Andrzej J. Strojwas, Understanding and addressing the impact of wiring congestion during technology mapping, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, 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
	Amir H. Farrahi, Estimation and removal or routing congestion (discussion session), Proceedings of the 2000 international workshop on System-level interconnect prediction, p.149, April 08-09, 2000, San Diego, California, United States
	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
	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
	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
	J. Cong , M. Romesis , J. R. Shinnerl, Robust mixed-size placement under tight white-space constraints, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.165-172, November 06-10, 2005, San Jose, CA
	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
	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
	Fei He , Xiaoyu Song , Ming Gu , Lerong Cheng , Guowu Yang , Zhiwei Tang , Jiaguang Sun, A combinatorial congestion estimation approach with generalized detours, Computers & Mathematics with Applications, v.51 n.6-7, p.1113-1126, March, 2006