Highly scalable algorithms for rectilinear and octilinear Steiner trees

ABSTRACT

The rectilinear Steiner minimum tree (RSMT) problem, which asks for a minimum-length interconnection of a given set of terminals in the rectilinear plane, is one of the fundamental problems in electronic design automation. Recently there has been renewed interest in this problem due to the need for highly scalable algorithms able to handle nets with tens of thousands of terminals. In this paper we give a practical O (n log² n) heuristic for computing near-optimal rectilinear Steiner trees based on a batched version of the greedy triple contraction algorithm of Zelikovsky [21]. Experiments conducted on both random and industry testcases show that our heuristic matches or exceeds the quality of best known RSMT heuristics, e.g., on random instances with more than 100 terminals our heuristic improves over the rectilinear minimum spanning tree by an average of 11%. Moreover, our heuristic has very well scaling runtime, e.g., it can route a 34k-terminals net extracted from a real design in less than 25 seconds compared to over 86 minutes needed by the O(n²) edge-based heuristic of Borah, Owens, and Irwin [3]. Since our heuristic is graph-based, it can be easily modified to handle practical considerations such as routing obstacles, preferred directions, via costs, and octilinear routing - indeed, experimental results show only a small factor increase in runtime when switching from rectilinear to octilinear routing.

REFERENCES

• 1: C. Alpert. Personal communication.
• 2: Piotr Berman , Ulrich Fößmeier , Marek Karpinski , Michael Kaufmann , Alexander Zelikovsky, Approaching the 5/4-Approximation for Rectilinear Steiner Trees, Proceedings of the Second Annual European Symposium on Algorithms, p.60-71, September 26-28, 1994
• 3: Manjit Borah , Robert Michael Owens , Mary Jane Irwin, A fast and simple Steiner routing heuristic, Discrete Applied Mathematics, v.90 n.1-3, p.51-67, Jan. 15, 1999 [doi>10.1016/S0166-218X(98)00085-7]
• 4: Giuseppe Cattaneo , Pompeo Faruolo , Umberto Ferraro Petrillo , Giuseppe F. Italiano, Maintaining Dynamic Minimum Spanning Trees: An Experimental Study, Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments, p.111-125, January 04-05, 2002
• 5: U. Fößmeier, M. Kaufmann and A. Zelikovsky. Faster approximation algorithms for the rectilinear Steiner tree problem, Discrete & Computational Geometry 18 (1997), pp. 93--109.
• 6: E. N. Gilbert, H. O. Pollak. Steiner minimal trees, SIAM J. Appl. Math. 32 (1977) pp. 826--834.
• 7: L. J. Guibas and J. Stolfi. On computing all north-east nearest neighbors in the L1 metric Information Processing Letters 17 (1983), pp. 219--223.
• 8: M. Hanan. On Steiner's problem with rectilinear distance, SIAM Journal on Applied Mathematics 14 (1966), 255--265.
• 9: F. K. Hwang and D. S. Richards and P. Winter. The Steiner tree problem. North-Holland, Annals of Discrete Mathematics 53, 1992.
• 10: A. B. Kahng and G. Robins. A new class of iterative Steiner tree heuristics with good performance, IEEE Trans. on CAD 11 (1992), pp. 1462--1465.
• 11: Cheng-Kok Koh , Patrick H. Madden, Manhattan or non-Manhattan?: a study of alternative VLSI routing architectures, Proceedings of the 10th Great Lakes symposium on VLSI, p.47-52, March 02-04, 2000, Chicago, Illinois, United States [doi>10.1145/330855.330961]
• 12: I. I. Măndoiu, V. V. Vazirani, and J. L. Ganley. A new heuristic for rectilinear Steiner trees. IEEE Transactions on Computer-Aided Design 19 (2000) pp. 1129--1139.
• 13: Benny K. Nielsen , Pawel Winter , Martin Zachariasen, An Exact Algorithm for the Uniformly-Oriented Steiner Tree Problem, Proceedings of the 10th Annual European Symposium on Algorithms, p.760-771, September 17-21, 2002
• 14: A. Rohe. Sequential and parallel algorithms for local routing, Ph.D. Thesis, Bonn University, Bonn, Germany, December 2001.
• 15: L. Scheffer. Rectilinear MST code, available as part of the RMST-Pack at http://www.gigascale.org/bookshelf/slots/RSMT/RMST/.
• 16: Steven L. Teig, The X architecture: not your father's diagonal wiring, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505355]
• 17: D. M. Warme, P. Winter, and M. Zacharisen. GeoSteiner 3.1 package, available from http://www.diku.dk/geosteiner/
• 18: http://www.xinitiative.org
• 19: Mehmet Can Yildiz , Patrick H. Madden, Preferred direction Steiner trees, Proceedings of the 11th Great Lakes symposium on VLSI, p.56-61, March 2001, West Lafayette, Indiana, United States [doi>10.1145/368122.368797]
• 20: M. Zachariasen. Personal communication, August 2002.
• 21: A. Zelikovsky. An 11/6-approximation for the network Steiner tree problem, Algorithmica 9 (1993), pp. 463--470.
• 22: Hai Zhou , Narendra Shenoy , William Nicholls, Efficient minimum spanning tree construction without Delaunay triangulation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.192-197, January 2001, Yokohama, Japan [doi>10.1145/370155.370320]