An efficient and optimal algorithm for simultaneous buffer and wire sizing

In this paper, we consider the problem of interconnect delay minimization b y simultaneous buffer and wire sizing under the Elmore delay model. T-Ve fi rst present a polynomial time algorithm SBWS to minimize the delay of an in terconnect wire. Previously, no polynomial time algorithm for the problem h as been reported in the literature. SEWS is an iterative algorithm with gua ranteed convergence to the optimal solution. It runs in quadratic time and uses constant memory for computation. Experimental results show that SEWS i s extremely efficient in practice. For example, for an interconnect of 10 0 00 segments and buffers, the CPU time is only 0.255 s, We then extend our r esult to handle interconnect trees. We present an algorithm SBWS-T which al ways gives the optimal solution. Experimental results show that SBWS-T is f aster than the greedy wire sizing algorithm [2] in practice.