CDCTree: novel obstacle-avoiding routing tree construction based on current driven circuit model

ABSTRACT

Routing tree construction is a fundamental problem in modern VLSI design. In this paper we propose CDC-Tree, an Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) heuristic algorithm to construct an OARSMT. CDC-Tree is based on the current driven circuit (CDC) model mapped from an escape graph. The circuit structure comes from the topology of the escape graph, with each edge replaced by a resistor indicating the wirelength of that edge. By performing DC analysis on the circuit and selecting the edges according to the current distribution to construct an OARSMT, the wirelength of the resulting tree is short. The algorithm has been implemented and tested on cases of different scales and with different shapes of obstacles. Experiments show that CDCTree can achieve shorter wirelength than the existing best algorithm, An-OARSMan, when the terminal number of a net is less than 50.

REFERENCES

• 1: M. R. Garey and D. S. Johnson, "The rectilinear Steiner tree problem is NP-complete", SIAM Journal on Applied Mathematics, 1977(32): pp. 826--834.
• 2: C. Y. Lee, "An algorithm for path connections and its applications", IRE Trans. on Electronic Computers, 1961, 10: pp. 345--346.
• 3: S. B. Akers, "A Modifi cation of Lee's Path Connection Algorithm", IEEE Trans. on Electronic Computer, 1967, 16 (4): pp. 97--98.
• 4: J. Soukup, Fast maze router, Proceedings of the 15th conference on Design automation, p.100-102, June 19-21, 1978, Las Vegas, Nevada, United States
• 5: Hadlock, "A Shortest Path Algorithm for Grid Graphs", Networks, 1977(7): pp. 323--334.
• 6: F. Rubin, "The Lee Connection Algorithm", IEEE Trans. on Computer, 1974(23): pp. 907--914.
• 7: David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
• 8: K. Mikami and K. Tabuchi, "A Computer Program for Optimal Routing of Printed Circuit Connectors", in Proc. of IFIPS, 1968, H47: pp. 1475--1478.
• 9: J. L. Ganley and J. P. Cohoon, "Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles", in Proc. of IEEE ISCAS, London, UK, 1994: pp. 113--116.
• 10: Martin Zachariasen , Pawel Winter, Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.282-295, January 15-16, 1999
• 11: Y. Yang, Q. Zhu, T. Jing, X. L. Hong, and Y. Wang, "Rectilinear Steiner Minimal Tree among Obstacles", in Proc. of IEEE ASICON, Beijing, China, 2003: pp. 348--351.
• 12: Yu Hu, Zhe Feng, Tong Jing, Xianlong Hong, Yang Yang, Ge Yu, Xiaodong Hu, Guiying Yan, "FORst: A 3-Step Heuristic for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction", Journal of Information and Computational Science, 2004, 1(3): 107--116.
• 13: Yu Hu , Tong Jing , Xianlong Hong , Zhe Feng , Xiaodong Hu , Guiying Yan, An-OARSMan: obstacle-avoiding routing tree construction with good length performance, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120732]
• 14: Ying-Fung Wu , Peter Widmayer , Martine D. F. Schlag , C. K. Wong, Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles, IEEE Transactions on Computers, v.36 n.3, p.321-331, March 1987 [doi>10.1109/TC.1987.1676904]
• 15: Yiyu Shi, Bike Xie and Yanjie Mao, "Circuit Model in Mathematical Modeling", Journal of Mathematical Engineering, 2004, 21(7): pp. 43--48.
• 16: Ho C, Ruehli, Brennan P. "The Modified Nodal Approach to Network Analysis", IEEE Trans. Circuits and Systems, 1975, 39(22): pp. 504--509.
• 17: D. S. Kershaw, "The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations", Journal of Computational Physics, 26 I (Jan.) (1978), 43--65.
• 18: J. Wang, D. Xie and Y. Yao, "The Modified Solutoin for Large Sparse Symmetric Linear Systems in Electromagnetic Field Analysis", Transactions of China Electrotechnical Society, 2001 16(2): pp. 26--29.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Performance