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

Abstract

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 (I18) method recently proposed by Kahng and Robins [13]. HS achieves significantly improved averagecase 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 HS, achieving speedup factors of over 200 compared to previous implementations. We also propose a parallel implementation of HS that achieves near-linear speedup on K processors. Extensive empirical testing confirms the viability of our approaches, which allow for the first time the benchmarking of IIS on nets containing several hundred pins. Note: Abstract extracted from PDF file via OCR