A global router using an efficient approximate multicommodity multiterminal flow algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A global router using an efficient approximate multicommodity multiterminal flow algorithm

Full text

Pdf (643 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 28th ACM/IEEE Design Automation Conference table of contents

San Francisco, California, United States

Pages: 316 - 321

Year of Publication: 1991

ISBN:0-89791-395-7

Authors

Robert C. Carden, IV	Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA
Chung-Kuan Cheng	Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/127601.127687 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.

	BP83	M. Burstein and R. Pelavin. Hierarchical wire routing. IEEE Transactions on Computer. Aided Design, CAD-2:223-234, October 1983.
	CSW89a	C. Chiang, M. Sarrafzadeh, and C.K. Wong. A powerful global router: Based on steiner minmax trees. In Proceeding o.f IEEE International Conference on Computer-Aided Design, pages 2- 5, 1989.
	CSW89b	C. Chiang, M. Sarrafzadeh, and C.K. Wong. A powerful global router: Based on steiner min-max trees. Manuscript, 1989.
	HS85	T.C. Hu and M.T. Shing. A decomposition algorithm for circuit routing. In T.C. Hu and E.S. Kuh, editors, VLSI Circuit Layout: Theory and Design, pages 144-152. IEEE Press, New York, NY, 1985.
	Hu69	T.C. Ha. Integer Programming and Network Flows. Addison-Wesley, Reading, MA, 1969.
	Hu82	T. C. Hu , M. T. Shing , Y. S. Kuo, Combinatorial Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
	HVW89	J.M. Ho, G. Vijayan, and C.K. Wong. Constructing the optimal rectifinear steiner tree derivable from a minimum spanning tree. In Proceeding o} IEEE International Conference on Computer-Aided Design, pages 6-9, 1989.
	Kar84	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	KLR+87	R.M. Karp, F.T. Leighton, R.L. Rivest, C.D. Thompson, U.V. Vazirani, and V.V. Varizani. Global wire routing in two-dimensional arrays. Algorithmica, 2:113-129, 1987.
	Lom85	M.V. Lomonosov. Combinatorial approaches to multiflow problems. Discrete Applied Mathematics, 11(1):1-94, 1985.
	LS91	Kai-Win Lee , Carl Sechen, A global router for sea-of-gates circuits, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	ML90	G. Meixner and U. Lauther. A new global router based on a flow model and linear assignment. In Proceeding of IEEE international Conference on Computer-Aided Design, pages 44-47, 1990.
	MSK86	M. Marek-Sadowska and E.S. Kuh. Global routing. In T. Ohtsuki, editor, Layout Design and Verification. North Holland, 1986.
	PT89	T.M. Parng and R.S. Tsay. A new approach to sea-of-gates global routing. In Proceeding of IEEE International Conference on Computer- Aided Design, pages 52-55, 1989.
	Rag90	P. Raghavan. Lecture notes on randomized algorithms. Research Report RC 15340 (#68237) 1/9/90, IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY 10598, 1990.
	SK87	E. Shragowitz , S. Keel, A global router based on a multicommodity flow model, Integration, the VLSI Journal, v.5 n.1, p.3-16, March 1987 [doi>10.1016/S0167-9260(87)80003-2]
	SM88	F. Shahrokhi and D.W. Matula. The maximum concurrent flow problem. Manuscript, New Mexico Tech, January 1988.
	TT83	B.S. Ting and B.N. Tien. Routing techniques for gate array. IEEE Transactions on Computer-Aided Design, CAD-2:301-312, October 1983.
	Van89	A. Vannelli. An interior point method for solving the global routing problem. In Proceeding o/ IEEE Custom Integrated Circuits Conference, pages 3.4.1-3.4.4, 1989.

CITED BY 18

	William R. Pulleyblank, Two Steiner tree packing problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.383-387, May 29-June 01, 1995, Las Vegas, Nevada, United States
	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
	Takahiro Deguchi , Tetsushi Koide , Shin'ichi Wakabayashi, Timing-driven hierarchical global routing with wire-sizing and buffer-insertion for VLSI with multi-routing-layer, Proceedings of the 2000 conference on Asia South Pacific design automation, p.99-104, January 2000, Yokohama, Japan
	Jin Huang , Xian-Long Hong , Chung-Kuan Cheng , E. S. Kuh, An efficient timing-driven global routing algorithm, Proceedings of the 30th international conference on Design automation, p.596-600, June 14-18, 1993, Dallas, Texas, United States
	William Swartz , Carl Sechen, A new generalized row-based global router, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.491-498, November 07-11, 1993, Santa Clara, California, United States
	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
	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
	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
	Xianlong Hong , Tianxiong Xue , Ernest S. Kuh , Chung-Kuan Cheng , Jin Huang, Performance-driven Steiner tree algorithm for global routing, Proceedings of the 30th international conference on Design automation, p.177-181, June 14-18, 1993, Dallas, Texas, United States
	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
	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
	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
	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
	Feng Zhou , Esther Y. Cheng , Bo Yao , Chung-Kuan Cheng , Ronald Graham, A hierarchical three-way interconnect architecture for hexagonal processors, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA
	Devang Jariwala , John Lillis, Trunk decomposition based global routing optimization, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	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
	Christoph Albrecht , Andrew B. Kahng , Ion Mandoiu , Alexander Zelikovsky, Floorplan Evaluation with Timing-Driven Global Wireplanning, Pin Assignment and Buffer/Wire Sizing, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.580, January 07-11, 2002
	Yi Zhu , Yuanfang Hu , Michael B. Taylor , Chung-Kuan Cheng, Energy and switch area optimizations for FPGA global routing architectures, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.1, p.1-25, January 2009