Provably Good Routing Tree Construction with Multi-Port Terminals

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

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).