An O(nlogn) edge-based algorithm for obstacle-avoiding rectilinear steiner tree construction

ABSTRACT

Obstacle-avoiding Steiner tree construction is a fundamental problem in VLSI physical design. In this paper, we provide a new approach for rectilinear Steiner tree construction in the presence of obstacles. We propose a novel algorithm, which generates sparse obstacle-avoiding spanning graphs efficiently. We design a fast algorithm for the minimum terminal spanning tree construction, which is the bottleneck step of several existing approaches in terms of running time. We adopt an edge-based heuristic, which enables us to perform both local and global refinement, leading to Steiner trees with small lengths. The time complexity of our algorithm is O(nlogn). Hence, our technique is the most efficient one to the best of our knowledge. Experimental results on various benchmarks show that our algorithm achieves 25.8 times speedup on average, while the average length of the resulting obstacle-avoiding rectilinear Steiner trees is only 1.58% larger than the best existing solution

REFERENCES

• 1: Borah, M., R. M. Owens, and M. J. Irwin, An Edge-Based Heuristic for Steiner Routing. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1994. 13(12): p. 1563--1568.
• 2: Hannan, M., On Steiner's Problem with Rectilinear Distance. SIAM Journal on Applied Mathematics, 1966. 14: p. 255--265.
• 3: Zhou, H., Efficient Steiner Tree Construction Based on Spanning Graph. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2004. 23(5): p. 704--710.
• 4: Garey, M. and D. Johnson, The Rectilinear Steiner Tree Problem is NP-Complete. SIAM Journal on Applied Mathematics, 1977. 32: p. 826--834.
• 5: Ganley, J. L. and J. P. Cohoon. Routing a Multi-Terminal Critical Net: Steiner Tree Construction in the Presence of Obstacles. in Int. Symp. on Circuits and Systems. 1994.
• 6: Yang, Y., et al. Rectilinear Steiner Minimal Tree among Obstacles. in Int. Conf. on ASIC. 2003.
• 7: 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]
• 8: 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]
• 9: Chung-Wei Lin , Szu-Yu Chen , Chi-Feng Li , Yao-Wen Chang , Chia-Lin Yang, Efficient obstacle-avoiding rectilinear steiner tree construction, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA [doi>10.1145/1231996.1232023]
• 10: Min Pan , Chris Chu, FastRoute: a step to integrate global routing into placement, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233596]
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
minimum terminal spanning tree, physical design, routing, spanning graph, steiner tree