Optimal Wiresizing for Interconnects with Multiple Sources

Jason Cong and Lei He
cong, helei@cs.ucla.edu

The optimal wiresizing problem for nets with multiple sources is studied under the RC tree model and the Elmore delay model. We decompose the routing tree for a multi-source net into the source subtree (SST) and a set of loading subtrees (LSTs), and show that the optimal wiresizing solution satisfies a number of interesting properties, including: the LST separability, the LST monotone property, the SST local monotone property and the general dominance property. Furthermore, we study the optimal wiresizing problem using a variable segment-division rather than an a priori fixed segment-division in all previous works and reveal the bundled refinement property. These properties lead to efficient algorithms to compute the optimal solutions. We have tested our algorithm on a large number of multi-source nets, including several nets extracted from the layout for a high performance Intel microprocessor. Accurate SPICE simulation shows that our methods reduce the interconnect delay by up to 36.3% for submicron CMOS technology and 32.1% for MCM technology, respectively, when compared to the minimal wire width solution. In addition, the algorithm based on the variable segment-division yields a speedup of over 100x time and does not lose any accuracy, when compared with the methods based on the a priori fixed segment-division. To the best of our knowledge, it is the first work which presents an in-depth study of both the optimal wiresizing problem for multi-source interconnect tree and the optimal wiresizing problem using a variable segment-division.