Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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

• 1: CS2: min-cost flow solver. http://www.igsystems.com/cs2/index.html.
• 2: Wun-Tat Chan , Francis Y. L. Chin , Hing-Fung Ting, A Faster Algorithm for Finding Disjoint Paths in Grids, Proceedings of the 10th International Symposium on Algorithms and Computation, p.393-402, December 16-18, 1999
• 3: Wayne Wei-Ming Dai , Raymond Kong , Masao Sato, Routability of a rubber-band sketch, Proceedings of the 28th ACM/IEEE Design Automation Conference, p.45-48, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127623]
• 4: Jia-Wei Fang , Yao-Wen Chang, Area-I/O flip-chip routing for chip-package co-design, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
• 5: Jia-Wei Fang , Chin-Hsiung Hsu , Yao-Wen Chang, An integer linear programming based routing algorithm for flip-chip design, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278633]
• 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: Yukiko Kubo , Atsushi Takahashi, A global routing method for 2-layer ball grid array packages, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055146]
• 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 , F M Maley, Algorithms for routing and testing routability of planar VLSI layouts, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.69-78, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22153]
• 10: Lijuan Luo , Martin D. F. Wong, Ordered escape routing based on Boolean satisfiability, Proceedings of the 2008 Asia and South Pacific Design Automation Conference, January 21-24, 2008, Seoul, Korea
• 11: David Staepelaere , Jeffrey Jue , Tal Dayan , Wayne Wei-Ming Dai, SURF: Rubber-Band Routing System for Multichip Modules, IEEE Design & Test, v.10 n.4, p.18-26, October 1993 [doi>10.1109/54.245960]
• 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: Yoichi Tomioka , Atsushi Takahashi, Monotonic parallel and orthogonal routing for single-layer ball grid array packages, Proceedings of the 2006 Asia and South Pacific Design Automation Conference, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118449]
• 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: Renshen Wang , Rui Shi , Chung-Kuan Cheng, Layer minimization of escape routing in area array packaging, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233668]
• 16: Man-Fai Yu , Wayne Wei-Ming Dai, Pin assignment and routing on a single-layer Pin Grid Array, Proceedings of the 1995 Asia and South Pacific Design Automation Conference, p.32-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224899]
• 17: Man-Fai Yu , Wayne Wei-Ming Dai, Single-layer fanout routing and routability analysis for Ball Grid Arrays, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.581-586, November 05-09, 1995, San Jose, California, United States
• 18: Man-Fai Yu , Joel Darnauer , Wayne Wei-Ming Dai, Interchangeable pin routing with application to package layout, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.668-673, November 10-14, 1996, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Theory

Keywords:
PCB routing, diagonal capacity, escape routing, missing pin, network flow, package routing