Octilinear redistributive routing in bump arrays

ABSTRACT

This paper proposes a scheme for automatic re-distribution layer (RDL) routing, which is used in chip-package connections. Traditional RDL routing designs are mostly performed manually because the wire geometries are more flexible and therefore more difficult to handle on RDL than on chip. For example, octilinear routing is manufacturable in RDL and is widely adopted due to its higher efficiency than Manhattan routing. In this paper we devise a polynomial time octilinear RDL routing algorithm based on a grid network embedded in the bump array. The grid network is constructed to fully utilize the routing space as well as avoid any spacing violation. Detailed routing solution can be obtained following the min-cost max-flow in the network. Experimental results show the effectiveness of our router.

REFERENCES

• 1: 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
• 2: Jia-Wei Fang , I-Jye Lin , Ping-Hung Yuh , Yao-Wen Chang , Jyh-Herng Wang, A routing algorithm for flip-chip design, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.753-758, November 06-10, 2005, San Jose, CA
• 3: 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]
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: T.-C. Hu, M.-T. Shing, The ±- routing, VLSI Circuit Layout: Theory and Design, pp.139--143, IEEE Press, 1985.
• 6: 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]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
8-geometry, interchangeability, network flow, routing grid