Obstacle-avoiding rectilinear Steiner tree construction

ABSTRACT

In today's VLSI designs, there can be many blockages in a routing region. The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has become an important problem in the physical design stage of VLSI circuits. This problem has attracted a lot of attentions in research and several approaches have been proposed to solve this problem effectively. In this paper, we will present a heuristic maze routing based approach to solve this OARSMT problem. It is commonly believed that maze routing based approaches can only handle small scale problems and there is a lack of an effective multi-terminal variant to handle multi-pin nets in practice. We will show in this paper that maze routing based approaches can also handle large scale OARSMT problems effectively. Our approach is based on the searching process as in maze routing and can handle multi-pin nets very well in both solution quality, running time and memory space usage. We have compared our results with those of the previous works and can show that we can out-perform the best previous results on this problem [15] by giving an OARSMT with 2.01% less wire length on average and can make a 27.04% improvement in wire length in comparison with a lower bound of the optimal solution on average, while the running times are all very short and comparable to those in [15]. Besides, due to the flexibility of maze routing, we can handle different kinds of obstacles with different convex or concave rectilinear shapes directly without a need to partition each blockage into a set of rectangular sub-blockages, which will increase the size of the problem.

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: 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]
• 3: J. Ganley and J. P. Cohoon, "Routing a Multi-terminal Critical Net: Steiner Tree Construction in the Presence of Obstacles", Proceedings International Symposium on Circuits and Systems, pp.113--116, 1994.
• 4: S. Q. Zheng and J. S. Lim and S. S. Iyengar, "Finding Obstacleavoiding Shortest Paths using Implicit Connection Graphs", IEEE Transaction on Computer-Aided Design, Vol.15, No.1, pp.103--110, 1996.
• 5: Y. Yang and Q. Zhu and T. Jing and X. Hong and Y. Wang, "Rectilinear Steiner Minimal Tree Among Obstacles", Proceedings IEEE ASICCON, pp.348--351, 2003.
• 6: H. Wu and Z. Feng and T. Jing and X. Hong and Y. Yang and G. Yu and 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.
• 7: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 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: 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]
• 10: H. Zhou, "Efficient Steiner Tree Construction Based on Spanning Graphs", IEEE Transactions on Computer-Aided Design, Vol.23, No.5, pp.704--710, 2004.
• 11: 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]
• 12: 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]
• 13: Pei-Ci Wu , Jhih-Rong Gao , Ting-Chi Wang, A Fast and Stable Algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction, Proceedings of the 2007 conference on Asia South Pacific design automation, p.262-267, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.357996]
• 14: Renato F. Hentschke , Jaganathan Narasimham , Marcelo O. Johann , Ricardo L. Reis, Maze routing steiner trees with effective critical sink optimization, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA [doi>10.1145/1231996.1232024]
• 15: 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]