Item Details

Provably Good Routing Tree Construction With Multi-Port Terminals

Bateman, C; Helvig, C; Robins, Gabe; Zelikovsky, A
Format
Report
Author
Bateman, C
Helvig, C
Robins, Gabe
Zelikovsky, A
Abstract
Previous literature on VLSI routing and wiring estimation typically assumes a one - to - one correspondence between terminals and ports. In practice, however (say, in a gridded routing regime), each "terminal" consists of a large collection of electrically equivalent ports, a fact that is not accounted for in layout steps such as wiring estimation. The presence of multiple ports for a given terminal gives rise to the group Steiner minimal tree problem. In this paper, we address the general problem of minimum-cost routing tree construction in the presence of multi-port terminals. Our main result is the first known heuristic with a sub - li'ne:zr performance bound. In particular, for a net with In multi - port terminals, previous heuristics have a performance bound of (Is: - 1) ~ OPT, while our construction offers an improved performance bound of (1 + ln « x/h ~ OPT. Our Java implementation is available on the World Wide Web. Note: Abstract extracted from PDF file via OCR
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1997
Published Date
1997
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online