Item Details

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

Barrera, Tim; Griffith, Jeff; McKee, Sally; Robins, Gabriel; Zhang, Tongtong
Format
Report
Author
Barrera, Tim
Griffith, Jeff
McKee, Sally
Robins, Gabriel
Zhang, Tongtong
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
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1992
Published Date
1992
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online