Topological routing to maximize routability for package substrate

ABSTRACT

Compared with on-chip routers, the existing commercial tools for off-chip routing have a much lower routability and often result in a large number of unrouted nets for manual routing. In this paper, we develop an effective, yet efficient, substrate routing algorithm, applying dynamic pushing to alleviate the net ordering problem and reordering and rerouting for further wire length and congestion reduction. Compared with an industrial design tool that leaves 936 nets unrouted for nine industrial designs with a total of 6100 nets, our algorithm reduces the unrouted nets to 212, a 4.5-times net number reduction and practically more design time reduction.

REFERENCES

• 1: F. Bossen. Anisotropic mesh generation with particles. In M. S. thesis, Univ. of CMU, 1996.
• 2: S. S. Chen, J. J. Chen, S. J. Chen, and C. C. Tsai. An automatic router for the pin grid array package. In Proc. Asia South Pacific Design Automation Conf., pages 275--281, 1999.
• 3: L. P. Chew. Constraint Delaunay triangulations. Algorithmica, 4(1):97--108, 1980.
• 4: 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 conference on Design automation, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278633]
• 5: 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]
• 6: 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]
• 7: C. C. Tsai, C. M. Wang, and S. J. Chen. NEWS: a net-even-wiring system for the routing on a multilayer PGA package. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 17(2):182--189, 1998.
• 8: Man-Fai Yu , Wayne Wei-Ming Dai, Pin assignment and routing on a single-layer Pin Grid Array, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.32-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224899]
• 9: 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

General Terms:
Algorithms, Experimentation

Keywords:
IC package, substrate routing, system in package