Efficient obstacle-avoiding rectilinear steiner tree construction

ABSTRACT

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, antenna jumpers for reliability enhancement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Nevertheless, considering obstacles significantly increases the problem complexity, and thus most previous works suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph (OASG), this paper presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction. Unlike previous heuristics, our algorithm guarantees to find an optimal OARSMT for any 2-pin net and many higher-pin nets. Extensive experiments show that our algorithm results in significantly shorter wirelengths than all state-of-the-art works.

REFERENCES

• 1: K. Clarkson , S. Kapoor , P. Vaidya, Rectilinear shortest paths through polygonal obstacles in O(n(logn)²) time, Proceedings of the third annual symposium on Computational geometry, p.251-257, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41985]
• 2: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 3: Zhe Feng , Yu Hu , Tong Jing , Xianlong Hong , Xiaodong Hu , Guiying Yan, An O(nlogn) algorithm for obstacle-avoiding routing tree construction in the λ-geometry plane, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123020]
• 4: J. Ganley and J. P. Cohoon, "Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles," Proc. ISCAS, vol. 1, pp. 113--116, 1994.
• 5: M. Garey and D. Johnson, "The rectilinear Steiner tree problem in NP-Complete," SIAM Journal of Applied Mathematics, pp. 826--834, 1977.
• 6: 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]
• 7: Y. Hu, Z. Feng, T. Jing, X. Hong, Y. Yang, G. Yu, X. Hu, and G. Yan, "FORst: a 3-step heuristic for obstacle-avoiding rectilinear Steiner minimal tree construction," Journal of Information and Computational Science, pp. 107--116, 2004.
• 8: 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]
• 9: C. Y. Lee, "An algorithm for connections and its application," IRE Trans. on Electronic Computer, pp. 346--365, 1961.
• 10: K. Mikami and K. Tabuchi, "A computer program for optimal routing of printed circuit connectors," Proc. IFIPS, pp. 1475--1478, 1968, H47.
• 11: Zion Shen , Chris C. N. Chu , Ying-Meng Li, Efficient Rectilinear Steiner Tree Construction with Rectilinear Blockages, Proceedings of the 2005 International Conference on Computer Design, p.38-44, October 02-05, 2005 [doi>10.1109/ICCD.2005.45]
• 12: Yiyu Shi , Tong Jing , Lei He , Zhe Feng , Xianlong Hong, CDCTree: novel obstacle-avoiding routing tree construction based on current driven circuit model, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118447]
• 13: Y. Yang, Q. Zhu, T. Jing, X. Hong, and Y. Wang, "Rectilinear Steiner minimal tree among obstacles," Proc. ASIC, pp. 348--351, 2003.
• 14: H. Zhou, "Efficient Steiner tree construction based on spanning graphs," IEEE Trans. Computer-Aided Design, Vol. 23, No. 5, pp. 704--710, May 2004.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
Steiner tree, physical design, routing, spanning tree