An efficient surface-based low-power buffer insertion algorithm

Abstract

Buffer insertion is an important technique used to achieve timing closure in high performance VLSI designs. As the number of buffers in ASIC designs has increased with process scaling, the power con-sumption of buffers has become a critical concern. In this paper, we present an efficient algorithm that performs van Ginneken style buffer insertion on RC trees and minimizes the total power con-sumption under a given delay constraint. Our algorithm is based on a formulation that uses a buffer library consisting of continuous buffer sizes. We construct solution candidates in the form of surfaces in the 3-D delay, capacitance and power (DCP) space and show the mecha-nisms to propagate and merge them in the interconnect tree. Instead of a single minimal power solution, the algorithm produces an entire DCP surface from which a suitable solution point can be selected. We also present a post-processing step where buffers with continu-ous (non-standard) sizes are snapped to discrete size values corre-sponding to the buffers in a given library. The proposed algorithm has a worst-case runtime complexity that is polynomial (quadratic) in the number of possible buffer locations. We implemented and tested our proposed algorithm on a number of large benchmark nets and observed that our method produces a speedup in runtime of 5-6X in comparison with previous power aware buffer insertion methods.