Toward a Steiner Engine: Enhanced Serial and Parallel Implementations of the Iterated 1-Steiner MRST Algorithm

The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estimation, as well as in many other areas. The MRST problem is known to be NP-hard, and the best performing MRST heuristic to date is the Iterated 1-Steiner (I1S) method recently proposed by Kahng and Robins [13]. I1S achieves significantly improved average-case performance while avoiding the worst-case examples from which other approaches suffer, yet the algorithm has heretofore lacked a practical implementation. In this paper we develop a straightforward, efficient implementation of I1S, achieving speedup factors of over 200 compared to previous implementations. We also propose a parallel implementation of I1S that achieves high parallel speedup on K processors. Extensive empirical testing confirms the viability of our approach, which allows for the first time the benchmarking of I1S on nets containing several hundred pins. 1 Introduction The minimum rectilinear Steiner tree (MRST) problem is ..