An optimization algorithm for simultaneous routing and buffer insertion with delay-power constraints in VLSI layout design

Buffer insertion is a very effective technique to reduce propagation delay in deep sub-micron VLSI interconnects. As design dimension shrinks, more buffers are needed to improve timing performance. However, the buffer itself consumes power and it has been shown that power dissipation overhead due to buffer insertions is significantly high. Many methodologies to optimize propagation delay with power constraint have been proposed but none of them can be integrated into buffer insertion algorithm using dynamic programming. This paper presents a new technique to optimize the interconnect delay and power consumption of buffers in buffer insertion algorithm using dynamic programming. The proposed technique allows dynamic power consumption of buffers to be computed incrementally. In order to increase the efficiency of the algorithm, we incorporate a technique called look-ahead into the algorithm. Experimental results show that the proposed technique is accurate, fast, and scalable with problem size.