Track assignment: a desirable intermediate step between global routing and detailed routing

ABSTRACT

Routing is one of the most complex stages in the back-end design process. Simple routing algorithms based on two stages of global routing and detailed routing do not offer appropriate opportunities to address problems arising from signal delay, cross-talk and process constraints. An intermediate stage of track assignment between global and detailed routing proves to be an ideal place to address these problems. With this stage it is possible to use global routing information to efficiently address these problems and to aid the detailed router in achieving the wiring completions. In this paper we formulate routing as a three stage process; global routing, track assignment and detailed routing. We describe the intermediate track assignment problem and suggest an efficient heuristic for its solution. We introduce cost metrics to model basic effects arising from connectivity. We discuss extensions to include signal integrity and process constraints. We propose a heuristic based on weighted bipartite matching as a core routine. To improve its performance additional heuristics based on lookahead and segment splitting are also suggested. Experimental results are given to highlight the efficacy of track assignment stage in routing process.

REFERENCES

• 1: H. B. Bakoglu, Circuits, interconnections, and packaging for VLSI, Addison-Wesley, Reading, MA, USA, 1990.
• 2: Naveed A. Sherwani, Algorithms for VLSI Physcial Design Automation, Kluwer Academic Publishers, Norwell, MA, 1998
• 3: A. Hetzel, A sequential detailed router for huge grid graphs, Proceedings of the conference on Design, automation and test in Europe, p.332-339, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 4: H.-P. Tseng, L. Scheffer, and C. Sechen, "Timing and crosstalk-driven area routing," IEEE Trans. CAD of Integrated Circuits and Systems, vol. 20, no. 4, pp. 528--544, Apr. 2001.
• 5: Chin-Chih Chang , Jason Cong, Pseudo pin assignment with crosstalk noise control, Proceedings of the 2000 international symposium on Physical design, p.41-47, May 2000, San Diego, California, United States [doi>10.1145/332357.332372]
• 6: Y. S. Kuo , T. C. Chern , Wei-kuan Shih, Fast algorithm for optimal layer assignment, Proceedings of the 25th ACM/IEEE conference on Design automation, p.554-559, June 12-15, 1988, Atlantic City, New Jersey, United States
• 7: C.-J. R. Shi, "Solving constrained via minimization by compact linear programming," Proceedings of the Asia and South Pacific Design Automation Conference, pp. 635--640, 1997.
• 8: C.-C. Chang and J. Cong, "An efficient approach to multilayer layer assignment with an application to via minimization," IEEE Trans. CAD of Integrated Circuits and Systems, vol. 18, no. 5, pp. 608--620, May 1999.
• 9: M. Sriram , S. M. Kang, Detailed layer assignment for MCM routing, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.386-389, November 1992, Santa Clara, California, United States
• 10: J. M. Ho, M. Sarrafzadeh, G. Vijayan, and C. K. Wong, "Layer assignment for multichip modules," IEEE Trans. CAD, vol. 9, no. 12, pp. 1272--1277, December 1990.
• 11: M. J. Ciesielski, "Layer assignment for VLSI interconnect delay minimization," IEEE Trans. CAD, vol. 8, no. 6, pp. 701--707, June 1989.
• 12: P. Saxena and C. L. Liu, "Optimization of the maximum delay of global interconnects during layer assignment," IEEE Trans. CAD of Integrated Circuits and Systems, vol. 20, no. 4, pp. 503--515, April 2001.
• 13: J. D. Cho, S. Raje, M. Sarrafzadeh, M. Sriram, and S. M. Kang, "Crosstalk-minimum layer assignment," Custom Integrated Circuits Conference, pp. 29.7.1--29.7.4, 1993.
• 14: Jason Cong , Jie Fang , Kei-Yong Khoo, DUNE: a multi-layer gridless routing system with wire planning, Proceedings of the 2000 international symposium on Physical design, p.12-18, May 2000, San Diego, California, United States [doi>10.1145/332357.332367]
• 15: Rony Kay , Rob A. Rutenbar, Wire packing: a strong formulation of crosstalk-aware chip-level track/layer assignment with an efficient integer programming solution, Proceedings of the 2000 international symposium on Physical design, p.61-68, May 2000, San Diego, California, United States [doi>10.1145/332357.332375]
• 16: P. Groeneveld and L. P. P. P. van Ginneken, "Method of designing a constraint-driven integrated circuit layout," U.S. Patent number 6,230,304, May 2001.
• 17: U. Gupta, D. T. Lee, and J. Leung, "An optimal solution for the channel assignment problem," IEEE Transactions on Computers, pp. 807--810, November 1979.
• 18: M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitrou, "The complexity of coloring circular arcs and chords," SIAM Journal on Algebraic Discrete Methods, vol. 1, no. 20, pp. 216--227, june 1980.
• 19: T. Yoshimura and E. S. Kuh, "Efficient algorithms for channel routing," IEEE Trans. CAD of Integrated Circuits and Systems, vol. CAD-1, no. 1, pp. 25--35, January 1982.
• 20: F. Harary, Graph Theory, Addison-Wesley, Reading, MA, USA, 1972.
• 21: R. Jonker , A. Volgenant, A shortest augmenting path algorithm for dense and sparse linear assignment problems, Computing, v.38 n.4, p.325-340, March 1987 [doi>10.1007/BF02278710]
• 22: 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
• 23: M. Sarrafzadeh and D. T. Lee, "Restricted track assignment with application," International Journal of Computational Geometry and Applications, vol. 4, no. 1, pp. 53--68, 1994.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Placement and routing

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Experimentation, Performance, Theory