Wire sizing for non-tree topology

Most existing methods for interconnect wire sizing are designed for RC trees. With the increasing popularity of the non-tree topology in clock networks and multiple link networks, wire sizing for non-tree networks becomes an important problem. In this paper, we propose the first systematic method to size the wires of general non-tree RC networks. Our method consists of three steps: 1) decompose a non-tree RC network into a tree RC network such that the Elmore delay at every sink remains unchanged; 2) size wires of the tree; and 3) merge the wires back to the original non-tree network. All three steps can be implemented in low-order polynomial time. Using this method, previous wire-sizing techniques for tree topology for various objectives, such as minimizing the maximum delay, minimizing the total area or power, and reducing skew variability under process variations, can be applied to non-tree topologies. For certain types of networks, such as the tree+link network, our method gives the optimal solution, provided the tree wire sizing is optimal. Compared with the previous best wire-sizing method for non-tree circuits we can achieve 2% to 17% Elmore delay reduction with 14% to 30% total wire area reduction. Compared with unsized minimum width networks, our delay is 25% less and the skew is 34% less, under SPICE simulation. For the tree+link network, we can achieve significant delay reduction and zero skew in nominal case, while get up to 66% skew variation reduction.