A correct network flow model for escape routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A correct network flow model for escape routing

Full text

Pdf (194 KB)

Source

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

San Francisco, California

SESSION: Routing: from chip to package table of contents

Pages 332-335

Year of Publication: 2009

ISBN:978-1-60558-497-3

Authors

Tan Yan	University of Illinois at Urbana-Champaign
Martin D. F. Wong	University of Illinois at Urbana-Champaign

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references index terms

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

ABSTRACT

Escape routing for packages and PCBs has been studied extensively in the past. Network flow is pervasively used to model this problem. However, none of the previous works correctly models the diagonal capacity, which is essential for 45° routing in most packages and PCBs. As a result, existing algorithms may either produce routing solutions that violate the diagonal capacity or fail to output a legal routing even though there exists one. In this paper, we propose a new network flow model that guarantees the correctness when diagonal capacity is taken into consideration. This model leads to the first optimal algorithm for escape routing. We also extend our model to handle missing pins.

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	CS2: min-cost flow solver. http://www.igsystems.com/cs2/index.html.
	2	W.-T. Chan, F. Y. L. Chin, and H.-F. Ting. A faster algorithm for finding disjoint paths in grids. In Proc. Int. Symp. on Algorithms and Computation, pages 393--402, 1999.
	3	W. W.-M. Dai, R. Kong, and M. Sato. Routability of a rubber-band sketch. In Proc. Design Automation Conf., pages 45--48, 1991.
	4	J.-W. Fang and Y.-W. Chang. Area-I/O flip-chip routing for chip-package co-design. In Proc. Int. Conf. on Computer-Aided Design, pages 518--522, 2008.
	5	J.-W. Fang, C.-H. Hsu, and Y.-W. Chang. An integer linear programming based routing algorithm for flip-chip design. In Proc. Design Automation Conf., pages 606--611, 2007.
	6	J.-W. Fang, I.-J. Lin, Y.-W. Chang, and J.-H. Wang. A network-flow-based RDL routing algorithmz for flip-chip design. IEEE Trans. Computer-Aided Design, 26(8), Aug. 2007.
	7	Y. Kubo and A. Takahashi. A global routing method for 2-layer ball grid array packages. In Proc. Int. Symp. on Physical Design, pages 36--43, 2005.
	8	Y. Kubo and A. Takahashi. Global routing by iterative improvements for two-layer ball grid array packages. IEEE Trans. Computer-Aided Design, 25(4), Apr. 2006.
	9	C. E. Leiserson and F. M. Maley. Algorithms for routing and testing routability of planar VLSI layouts. In Proc. Ann. Symp. on Theory of Computing, pages 69--78, 1985.
	10	L. Luo and M. D. F. Wong. Ordered escape routing based on boolean satisfiability. In Proc. Asia and South Pacific Design Automation Conf., pages 244--249, 2008.
	11	D. Staepelaere, J. Jue, T. Dayan, and W. W.-M. Dai. SURF: Rubber-band routing system for multichip modules. IEEE Des. Test. Comput., 10(4):18--26, Dec. 1993.
	12	D. J. Staepelaere. Geometric transformations for a rubber-band sketch. Master's thesis, University of California at Santa Cruz, Santa Cruz, CA, USA, Sept. 1992.
	13	Y. Tomioka and A. Takahashi. Monotonic parallel and orthogonal routing for single-layer ball grid array packages. In Proc. Asia and South Pacific Design Automation Conf., pages 642--647, 2006.
	14	D. Wang, P. Zhang, C.-K. Cheng, and A. Sen. A performance-driven I/O pin routing algorithm. In Proc. Asia and South Pacific Design Automation Conf., pages 129--132, 1999.
	15	R. Wang, R. Shi, and C.-K. Cheng. Layer minimization of escape routing in area array packaging. In Proc. Int. Conf. on Computer-Aided Design, pages 815--819, 2006.
	16	M.-F. Yu and W. W.-M. Dai. Pin assignment and routing on a single-layer pin grid array. In Proc. Asia and South Pacific Design Automation Conf., pages 203--208, 1995.
	17	M.-F. Yu and W. W.-M. Dai. Single-layer fanout routing and routability analysis for ball grid arrays. In Proc. Int. Conf. on Computer-Aided Design, pages 581--586, 1995.
	18	M.-F. Yu, J. Darnauer, and W. W.-M. Dai. Interchangeable pin routing with application to package layout. In Proc. Int. Conf. on Computer-Aided Design, pages 668--673, 1996.