Item Details

Print View

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
2012-10-29
Published
University of Virginia, Department of Computer Science, 1997
Published Date
1997
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online