Toward a Steiner engine: enhanced serial and parallel implementations of the iterated 1-Steiner MRST algorithm

Author

Barrera, Tim ; Griffith, Jeff ; McKee, Sally A. ; Robins, Gabriel ; Zhang, Tongtong

Author_Institution

Dept. of Comput. Sci., Virginia Univ., Chartlottesville, VA, USA

fYear

1993

fDate

5-6 Mar 1993

Firstpage

90

Lastpage

94

Abstract

The minimum rectilinear Steiner tree (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 A.B. Kahng and G. Robins (1992). The authors develop a straightforward, efficient implementation of I1S, achieving speedup factors of over 200 compared to previous implementations. They also propose a parallel implementation of I1S that achieves high parallel speedup on K processors. Extensive empirical testing confirms the viability of the approach, which allows the benchmarking of I1S on nets containing several hundred pins

Keywords

circuit layout CAD; computational complexity; iterative methods; network routing; network topology; parallel algorithms; trees (mathematics); NP-hard; Steiner engine; VLSI layout; global routeing; iterated 1-Steiner MRST algorithm; minimum rectilinear Steiner tree; parallel implementations; Benchmark testing; Computer science; Cost function; Engines; Phase estimation; Pins; Routing; Signal design; Very large scale integration; Wiring;

fLanguage

English

Publisher

ieee

Conference_Titel

VLSI, 1993. 'Design Automation of High Performance VLSI Systems', Proceedings., Third Great Lakes Symposium on

Conference_Location

Kalamazoo, MI

Print_ISBN

0-8186-3430-8

Type

conf

DOI

10.1109/GLSV.1993.224473

Filename

224473