An efficient timing-driven global routing algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient timing-driven global routing algorithm

Full text

Pdf (572 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 30th international Design Automation Conference table of contents

Dallas, Texas, United States

Pages: 596 - 600

Year of Publication: 1993

ISBN:0-89791-577-1

Authors

Jin Huang
Xian-Long Hong
Chung-Kuan Cheng
E. S. Kuh

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 31, Citation Count: 15

Additional Information:

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

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.

	Con90	J. Cong. Provable good performancedriven global routing. Pvoc. Inte. Conf. on Computer-Aided Design, pages 48-51, 1990.
	DAD+84	A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
	EM87	E.Horneber and W. Mathis. A closedform expression for signal delay in cmosdriven branched transmission lines. VLSI, pages 353-362, 1987.
	HNY87	P.S. Hauge, R. Nair, and E. J. Yoffa. Circuit placement for predictable performance. In IEEE International Conference on Computer-Aided Design,ICCAD- 87, pages 88-91, 1987.
	Hu82	T. C. Hu , M. T. Shing , Y. S. Kuo, Combinatorial Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
	HXC+92	X. Hong, T. Xiong, C.K. Cheng, E.S. Kuh, and Jin Huang. Performance-driven steiner tree algorithms for global routing. Research Report, EECS/ERL, UC Berkeley, 1992.
	IC91	Robert C. Carden, IV , Chung-Kuan Cheng, A global router using an efficient approximate multicommodity multiterminal flow algorithm, Proceedings of the 28th conference on ACM/IEEE design automation, p.316-321, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127687]
	JK89	M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
	JKMS87	M. A. B. Jackson, E. S. Kuh, and M. Marek-Sadowska. Timing-driven routing for building-block layout. In IEEE International Symposium on Circuits and Systems, pages 518-519, 1987.
	KAE91	K.Chaudhary, A.Srinivasan, and E.S.Kuh. Ritual: A performance driven placement algorithm for small cell ics. IC- CAD, pages 48-51, 1991.
	ML90	G. Meixner and U. Lauther. A new global router based on a flow model and linear assignment. ICCAD, 1990.
	MMDN88	M.Rose, M.Wiesel, D.Kirkpatrick, and N.Nettleton. Dense, performance directed, auto place and route. Proc. CICC, pages 11.1.1-11.1.4, 1988.
	MSL89	M. Marek-Sadowska and S. P. Lin. Timing-driven placement. IEEE international Conference on Computer-Aided Design ICCAD-89, pages 94-97, 1989.
	Mur83	K.G. Murty. Linear Programming. John Wiley and Sons, 1983.
	PW90	S. Prasitjutrakul and W.J.Kubits. A timing-driven global router for custom chip design. Proc. lute. Conf. on Computer-Aided Design, pages 48-51, 1990.
	Sak83	T. Sakurai. Approximation of wiring delay in mosfet lsi. IEEE J. of Solid-state Circuits, SC-18:418-426, 1983.
	SE90	Suphachai Sutanthavibul , Eugene Shragowitz, An adaptive timing-driven layout for high speed VLSI, Proceedings of the 27th ACM/IEEE conference on Design automation, p.90-95, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123233]
	TC84	T.M.Lin and C.A.Mead. Signal delay in general re networks. IEEE Trans. on CAD, CAD-3:331-349, 1984.
	WRBS90	Wilm E. Donath , Reini J. Norman , Bhuwan K. Agrawal , Stephen E. Bello , Sang Yong Han , Jerome M. Kurtzberg , Paul Lowy , Roger I. McMillan, Timing driven placement using complete path delays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.84-89, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123232]
	XJCE92	X.-L. Hong , J. Huang , C.-K. Cheng , E. S. Kuh, FARM: an efficient feed-through pin assignment algorithm, Proceedings of the 29th ACM/IEEE conference on Design automation, p.530-535, June 08-12, 1992, Anaheim, California, United States
	YME90	Y.Ogawa, M.Pedram, and E.S.Kuh. Timing-driven placement for general cell layout. Proc. Inle. Symp. on circuits and Systems, pages 872-876, 1990.
	YS89	Y. Fujihara , Y. Sekiyama , Y. Ishibashi , M. Yanaka, DYNAJUST: an efficient automatic routing technique optimizing delay conditions, Proceedings of the 26th ACM/IEEE conference on Design automation, p.791-794, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74531]

CITED BY 15

	Feodor F. Dragan , Andrew B. Kahng , Ion Mandoiu , Sudhakar Muddu , Alexander Zelikovsky, Provably good global buffering by multi-terminal multicommodity flow approximation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.120-125, January 2001, Yokohama, Japan
	Jason Cong , Patrick H. Madden, Performance driven global routing for standard cell design, Proceedings of the 1997 international symposium on Physical design, p.73-80, April 14-16, 1997, Napa Valley, California, United States
	Ikuo Harada , Hitoshi Kitazawa, A global router optimizing timing and area for high-speed bipolar LSI's, Proceedings of the 31st annual conference on Design automation, p.177-181, June 06-10, 1994, San Diego, California, United States
	Feodor F. Dragan , Andrew B. Kahng , Ion Măndoiu , Sudhakar Muddu , Alexander Zelikovsky, Provably good global buffering using an available buffer block plan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Christoph Albrecht, Provably good global routing by a new approximation algorithm for multicommodity flow, Proceedings of the 2000 international symposium on Physical design, p.19-25, May 2000, San Diego, California, United States
	Andrew B. Kahng, Research directions for coevolution of rules and routers, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Jiang Hu , Sachin S. Sapatnekar, A timing-constrained algorithm for simultaneous global routing of multiple nets, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Tong Jing , Xian Long Hong , Hai Yun Bao , Jing Yu Xu , Jun Gu, SSTT: efficient local search for GSI global routing, Journal of Computer Science and Technology, v.18 n.5, p.632-639, September 2003
	Jin-Tai Yan , Shun-Hua Lin, Timing-constrained congestion-driven global routing, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.683-686, January 27-30, 2004, Yokohama, Japan
	Hua Xiang , Xiaoping Tang , D. F. Wong, An algorithm for simultaneous pin assignment and routing, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	XianLong Hong , Tong Jing , JingYu Xu , HaiYun Bao , Jun Gu, CNB: a critical-network-based timing optimization method for standard cell global routing, Journal of Computer Science and Technology, v.18 n.6, p.732-738, November 2003
	Stelian Alupoaei , Srinivas Katkoori, Net Clustering Based Constructive and Iterative Improvement Approaches for Macro-Cell Placement, Journal of VLSI Signal Processing Systems, v.37 n.1, p.151-163, May 2004
	Jingyu Xu , Xianlong Hong , Tong Jing , Yici Cai , Jun Gu, A novel timing-driven global routing algorithm considering coupling effects for high performance circuit design, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Tong Jing , Xianlong Hong , Haiyun Bao , Yici Cai , Jingyu Xu , Chungkuan Cheng , Jun Gu, UTACO: a unified timing and congestion optimizing algorithm for standard cell global routing, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Seokjin Lee , Yongseok Cheon , Martin D. F. Wong, A Min-Cost Flow Based Detailed Router for FPGAs, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.388, November 09-13, 2003