NON-TREE ROUTING

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 investigate the consequences of abandoning this basic axiom, and instead we allow routing topologies that correspond to arbitrary graphs (i.e., where cycles are allowed). We show that non-tree routing can significantly improve signal propagation delay, reduce signal skew, and afford increased reliability with respect to open faults that may be caused by manufacturing defects and electro-migration. Simulations on uniformly distributed nets indicate that depending on net size and technology parameters, our non-tree routing construction reduces maximum sourse-sink SPICE delay by an average of up to 62%, and reduces 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.