Provably good global routing by a new approximation algorithm for multicommodity flow

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Provably good global routing by a new approximation algorithm for multicommodity flow

Full text

Pdf (182 KB)

Source

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

San Diego, California, United States

Pages: 19 - 25

Year of Publication: 2000

ISBN:1-58113-191-7

Author

Christoph Albrecht

Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, 53113 Bonn, Germany

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 51, Citation Count: 14

Additional Information:

references cited by 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/332357.332368 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.

	1	K. Aoshima and E. S. Kuh. Multi-Channel Optimization in Gate-Array LSI Layout. In Proceedings ISCAS, pages 1005-1008, 1983.
	2	Randall J. Brouwer , Prithviraj Banerjee, PHIGURE: a parallel hierarchical global router, Proceedings of the 27th ACM/IEEE conference on Design automation, p.650-653, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123429]
	3	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]
	4	Jason Cong , Bryan Preas, A new algorithm for standard cell global routing, Integration, the VLSI Journal, v.14 n.1, p.49-65, Nov. 1992 [doi>10.1016/0167-9260(92)90010-V]
	5	W.-M. Dai and E. S. Kuh. Simultaneous Floor Planning and Global Routing for Hierarchical Building- Block Layout. IEEE Transactions on Computer-Aided Design, 6(5):828-837, 1997.
	6	Lisa Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.24, October 17-18, 1999
	7	Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
	8	A. Hetzel. Verdrahtungsprobleme im VLSI-Design: Spezielle Teilprobleme und ein sequentielles LSsungsverfahren. Ph.D. Thesis (in German), University of Bonn, 1995.
	9	A. Hetzel, A sequential detailed router for huge grid graphs, Proceedings of the conference on Design, automation and test in Europe, p.332-339, February 23-26, 1998, Le Palais des Congrés de Paris, France
	10	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 [doi>10.1145/157485.165063]
	11	B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer-Verlag, Berlin, 2000.
	12	G. Meixner and U. Lauther. A New Global Router Based on A Flow Model and Linear Assignment. In Proceedings of the International Conference on Computer Aided Design, pages 44-47, 1990.
	13	Takumi Okamoto , Masaki Ishikawa , Tomoyuki Fujita, A new feed-through assignment algorithm based on a flow model, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.775-778, November 07-11, 1993, Santa Clara, California, United States
	14	Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
	15	P. Raghavan and C. D. Thompson. Multiterminal global routing: A deterministic approximation. Algorithmica, 6:73-82, 1991.
	16	A. Rohe and M. Zachariasen. Rectilinear Group Steiner Trees and Application in VLSI-Design. Technical Report, University of Bonn. 2000.
	17	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]

CITED BY 16

	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
	Jason Cong , Jie Fang , Yan Zhang, Multilevel approach to full-chip gridless routing, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	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
	Juergen Koehl , David E. Lackey , George Doerre, IBM's 50 Million gate ASICs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Jason Cong , Min Xie , Yan Zhang, An enhanced multilevel routing system, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.51-58, November 10-14, 2002, San Jose, California
	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
	Yiyu Shi , Paul Mesa , Hao Yu , Lei He, Circuit simulation based obstacle-aware Steiner routing, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, 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
	Deming Chen , Jason Cong , Peichen Pan, FPGA Design Automation: A Survey, Foundations and Trends® in Electronic Design Automation, v.1 n.3, p.139-169, January 2006
	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
	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
	Muhammet Mustafa Ozdal, Escape routing for dense pin clusters in integrated circuits, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Yiyu Shi , Paul Mesa , Hao Yu , Lei He, Circuit-simulated obstacle-aware Steiner routing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.3, p.1-18, August 2007
	Muhammet Mustafa Ozdal , Martin D. F. Wong, Archer: a history-driven global routing algorithm, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Muhammet Mustafa Ozdal, Detailed-routing algorithms for dense pin clusters in integrated circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, v.28 n.3, p.340-349, March 2009
	Muhammet Mustafa Ozdal , Martin D. F. Wong, Archer: a history-based global routing algorithm, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, v.28 n.4, p.528-540, April 2009

Collaborative Colleagues:

Christoph Albrecht: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player