Provably Good Routing Tree Construction with Multi-Port Terminals

Report
Authors:Bateman, C, Department of Computer ScienceUniversity of Virginia Helvig, C, Department of Computer ScienceUniversity of Virginia Robins, Gabe, Department of Computer ScienceUniversity of Virginia Zelikovsky, A, Department of Computer ScienceUniversity of Virginia
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

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

Bateman, C, C Helvig, Gabe Robins, and A Zelikovsky. "Provably Good Routing Tree Construction with Multi-Port Terminals." University of Virginia Dept. of Computer Science Tech Report (1997).

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