NON-TREE ROUTING

An implicit premise of existing routing methods is that the routing to pology must correspond to a tree (i.e., it does not contain cycles). I n this paper we investigate the consequences of abandoning this basic axiom, and instead we allow routing topologies that correspond to arbi trary graphs (i.e., where cycles are allowed). We show that non-tree r outing can significantly improve signal propagation delay, reduce sign al skew, and afford increased reliability with respect to open faults that may be caused by manufacturing defects and electro-migration. Sim ulations on uniformly distributed nets indicate that depending on net size and technology parameters, our non-tree routing construction redu ces maximum sourse-sink SPICE delay by an average of up to 62%, and re duces signal skew by an average of up to 63%, as compared with Steiner routing. Moreover, up to 77% of the total wirelength in non-trees can tolerate an open fault without disconnecting the circuit.