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

Report
Authors:Barrera, Tim, Department of Computer ScienceUniversity of Virginia Griffith, Jeff, Department of Computer ScienceUniversity of Virginia McKee, Sally, Department of Computer ScienceUniversity of Virginia Robins, Gabriel, Department of Computer ScienceUniversity of Virginia Zhang, Tongtong, Department of Computer ScienceUniversity of Virginia
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

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Barrera, Tim, Jeff Griffith, Sally McKee, Gabriel Robins, and Tongtong Zhang. "Toward a Steiner Engine: Enhanced Serial and Parallel Implementations of the Iterated 1-Steiner MRST Heuristic." University of Virginia Dept. of Computer Science Tech Report (1992).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1992