Item Details

Print View

Non-Tree Routing

McCoy, Bernard; Robins, Gabriel
McCoy, Bernard
Robins, Gabriel
An implicit premise of existing routing methods is that the routing topology must correspond to a tree (i.e., it does not contain cycles). In this paper we abandon this basic axiom and investigate the consequences of allowing routing topologies that correspond to arbitrary graphs (i.e., where cycles are allowed). We show that adding extra wires to an existing routing tree can often significantly improve signal propagation delay by exploiting a tradeoff between wire capacitance and resistance, and we propose several new routing algorithms based on this phenomenon. Using SPICE to determine the efficacy of our methods, we obtain dramatic results: for example, the addition of a single new wire to an existing minimum spanning tree (MST) routing reduces the average signal propagation delay by up to 24%, while the average interconnection cost increases by only 11%, depending on net size. The delay performance of our methods is competitive with the best existing routing tree constructions, while the average wirelength of our constructions is significantly better. Our basic formulation extends to several important routing regimes, including the Steiner case, critical-sink routing, and wire sizing. Note: Abstract extracted from PDF file via OCR
Date Received
University of Virginia, Department of Computer Science, 1993
Published Date
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less


Access Online