Optimal routing algorithms for rectilinear pin clusters in high-density multichip modules

ABSTRACT

As the circuit densities and transistor counts are increasing, the package routing problem is becoming more and more challenging. In this article, we study an important routing problem encountered in typical high-end MCM designs: routing within dense pin clusters. Pin clusters are often formed by pins that belong to the same functional unit or the same data bus, and can become bottlenecks in terms of overall routability. Typically, these clusters have irregular shapes, which can be approximated with rectilinear convex boundaries. Since such boundaries have often irregular shapes, a traditional escape routing algorithm may give unroutable solutions. In this article, we study how the positions of escape terminals on a convex boundary affect the overall routability. For this purpose, we propose a set of necessary and sufficient conditions to model routability outside a rectilinear convex boundary. Given an escape routing solution, we propose an optimal algorithm to select the maximal subset of nets that are routable outside the boundary. After that, we focus on an integrated approach to consider routability constraints (outside the boundary) during the actual escape routing algorithm. Here, we propose an optimal algorithm to find the best escape routing solution that satisfies all routability constraints. Our experiments demonstrate that we can reduce the number of layers by 17% on the average, by using this integrated methodology.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 2: Capwell, G. 1998. High density design with MicroStar BGAs. Application Report SPRA471A, Texas Instruments.
• 3: Wun-Tat Chan , Francis Y. L. Chin , Hing-Fung Ting, Escaping a grid by edge-disjoint paths, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.726-734, January 09-11, 2000, San Francisco, California, United States
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 6: John Hershberger , Subhash Suri, Efficient breakout routing in printed circuit boards, Proceedings of the thirteenth annual symposium on Computational geometry, p.460-462, June 04-06, 1997, Nice, France [doi>10.1145/262839.263082]
• 7: Katopis, G. A., Becker, W. D., Mazzawy, T. R., Smith, H. H., Vakirtzis, C. K., Kuppinger, S. A., Singh, B., Lin, P. C., Bartells, J., Kihlmire, G. V., Venkatachalam, P. N., Stoller, H. I., and Frankel, J. L. 1999. MCM technology and design for the S/390 G5 system. IBM J. Res. Development 43.
• 8: Nair, R. 1987. A simple yet effective technique for global wiring. IEEE Trans. on Computer-Aided Des. 6.
• 9: Ozdal, M. M. and Wong, M. D. F. 2006. Algorithms for simultaneous escape routing and layer assignment of dense PCBs. IEEE Trans. CAD Integ. Circu. Syst. 25, 1510--1522.
• 10: Ozdal, M. M., Wong, M. D. F., and Honsinger, P. S. 2008. Simultaneous escape routing algorithms for via minimization of high-speed boards. IEEE Trans. CAD Integ. Circ. Syst. 27, 84--95.
• 11: Rui Shi , Chung-Kuan Cheng, Efficient escape routing for hexagonal array of high density I/Os, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147162]
• 12: Titus, A., Jaiswal, B., Dishongh, T., and Cartwright, A. N. 2004. Innovative circuit board level routing designs for BGA packages. IEEE Trans. Advan. Pack. 27.
• 13: Wiens, D. 2000. Printed circuit board routing at the threshold. The Board Authority, 44--47.
• 14: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
Escape routing, multi-chip modules, network flow