An optimized buffer insertion algorithm with delay-power constraints for VLSIlayouts

Abstract

We propose a grid-graph algorithm for interconnect routing and buffer insertion in nanometer VLSI layoutdesigns. The algorithm is designed to handle multiconstraint optimizations, namely timing performance and powerdissipation. The proposed algorithm is called HRTB-LA, which stands for hybrid routing tree and buffer insertion withlook-ahead. In recent VLSI designs, interconnect delay has become a dominant factor compared to gate delay. Thewell-known technique to minimize the interconnect delay is by inserting buffers along the interconnect wires. However,the buffer itself consumes power and it has been shown that power dissipation overhead due to buffer insertions issigni cantly high. Many methodologies to optimize timing performance with power constraint have been proposed,and no algorithm is based on dynamic programing technique using a grid graph. In addition, most of the algorithmsfor buffer insertion use a postrouting buffer insertion approach. In the presence of buffer obstacles, these postroutingalgorithms may produce poor solutions. On the other hand, the simultaneous routing and buffer insertion algorithmoffers a better solution, but it was proven to be NP complete. Hence, our main contribution is an efficient algorithmusing a hybrid approach for multiconstraint optimization for multisink nets. The algorithm uses dynamic programmingto compute incrementally the interconnect delay and power dissipation of the inserted buffers while an effective runtimeis achieved with the aid of novel look-ahead and graph pruning schemes. Experimental results prove that HRTB-LA isable to handle multiconstraint optimizations and produces a solution up to 30% better compared to a postrouting bufferinsertion algorithm in comparable runtime.