An integer linear programming based routing algorithm for flip-chip design

ABSTRACT

The flip-chip package provides a high chip-density solution to the demand for more I/O pads of VLSI designs. In this paper, we present the first routing algorithm in the literature for the pre-assignment flip-chip routing problem with a pre-defined netlist among pads and wire-width and signal-skew considerations. Our algorithm is based on integer linear programming (ILP) and guarantees to find an optimal solution for the addressed problem. It adopts a two-stage technique of global routing followed by detailed routing. In global routing, it first uses two reduction techniques to prune redundant solutions and create a global-routing path for each net. Without loss of the solution optimality, our reduction techniques can further prune the ILP variables (constraints) by 85.5% (98.0%) on average over a recent reduction technique. The detailed routing applies X-based grid-less routing to complete the routing. Experimental results based on five real industry designs show that our router can achieve 100% routability and the optimal global-routing wirelength and satisfy all signal-skew constraints, under reasonable CPU times, while recent related work results in much inferior solution quality.

REFERENCES

• 1: Charles Chiang , Qing Su , Ching-Shoei Chiang, Wirelength reduction by using diagonal wire, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764836]
• 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: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: http://lpsolve.sourceforge.net/5.5/.
• 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: Yoichi Tomioka , Atsushi Takahashi, Monotonic parallel and orthogonal routing for single-layer ball grid array packages, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118449]
• 7: UMC, "0.13μm flip-chip layout guideline," p. 6, 2004.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
detailed routing, global routing, physical design