An-OARSMan: obstacle-avoiding routing tree construction with good length performance

ABSTRACT

Routing is one of the important steps in VLSI/ULSI physical design. The rectilinear Steiner minimum tree (RSMT) construction is an essential part of routing. Since macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase, obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. This paper focuses on the OARSMT problem and presents an algorithm, named An-OARSMan, based on ant colony optimization. A greedy obstacle penalty distance (OP-distance) local heuristic is used in the algorithm and performed on the track graph. The algorithm has been implemented and tested on different kinds of obstacles. Experimental results show that An-OARSMan can handle complex obstacle cases including both convex and concave polygon obstacles with good length performance. It can always achieve the optimal solution in the cases with no more than 7 terminals.

REFERENCES

• 1: C. Y. Lee, "An alogrithm for path connections and its applications". IRE Trans on Electronic Computers, 1961, 10: pp. 346--365.
• 2: S. Q. Zheng, J. S. Lim, and S. S. Iyengar, "Finding obstacle-avoiding shortest paths using implicit connection graphs". IEEE Trans on CAD, 1996, 15(1): pp. 103--110.
• 3: 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]
• 4: 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.
• 5: 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
• 6: 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.
• 7: M. Dorigo, V. Maniezzo, and A. Colorni, "The Ant System: Optimization by a colony of cooperating agents", IEEE Trans on Systems, Man, and Cybernetics--Part B, 1996, 26(1): pp. 1--13.
• 8: Sanjoy Das , Shekhar V. Gosavi , William H. Hsu , Shilpa A. Vaze, An Ant Colony Approach For The Steiner Tree Problem, Proceedings of the Genetic and Evolutionary Computation Conference, p.135, July 09-13, 2002
• 9: S. B. Akers, "A Modification of Lee's Path Connection Algorithm", IEEE Trans on Electronic Computer, 1967, 16(4): pp. 97--98.
• 10: 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
• 11: Hadlock, "A Shortest Path Algorithm for Grid Graphs", Networks, 1977(7): pp. 323--334.
• 12: F. Rubin, "The Lee Connection Algorithm", IEEE Trans on Computer, 1974(23): pp. 907--914.
• 13: 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.
• 14: 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]
• 15: K. Mikami and K. Tabuchi, "A Computer Program for Optimal Routing of Printed Circuit Connectors", in Proc of IFIPS, 1968, H47: pp. 1475--1478.
• 16: Yu Hu, Zhe Feng, Tong Jing, Xianlong Hong, Yang Yang, Ge Yu, Xiaodong Hu, and Guiying Yan, "A 3-Step Heuristic for Obstacle-Avoiding Rectilinear Steiner Minimum Tree Construction", in Proc. of ISC&I'04, Zhuhai, China, pp. 1017--1021.