Non-Tree Routing

Authors:McCoy, Bernard, Department of Computer ScienceUniversity of Virginia Robins, Gabriel, Department of Computer ScienceUniversity of Virginia

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

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

McCoy, Bernard, and Gabriel Robins. "Non-Tree Routing." University of Virginia Dept. of Computer Science Tech Report (1993).

University of Virginia, Department of Computer Science
Published Date: