Optimal Wiresizing for Interconnects with Multiple Sources

In this paper, we study the optimal wiresizing problem for nets with multiple sources under the RC tree model and the Elmore delay model. We decompose the routing tree for a multisource 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 dominance property. Furthermore, we study the optimal wiresizing problem using a variable segment-division rather than an a priori fixed segment-division as 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 nets extracted from the multilayer layout for a high-performance Intel microprocessor. Accurate SPICE simulation shows that our methods reduce the average delay by up to 23.5% and the maximum delay by up to 37.8%, respectively, for the submicron CMOS technology when compared to the minimal wire width solution. In addition, the algorithm based on the variable segment-division yields a speedup of over 1003 time and does not lose any accuracy, when compared with the algorithm based on the a priori fixed segment-divisio