Dual-V(dd) buffer insertion for power reduction
This paper presents the first in-depth study on dual-V(dd) buffer insertion for power minimization under delay constraint. Compared with delay-optimal single V(dd) buffer insertion, the dual-V(dd) buffer insertion reduces power by 16%. Such power reduction increases when the delay specification is relaxed. Whereas the van Ginneken algorithm can be extended to handle the new problem formulation optimally, its time complexity increases from quadratic time (O(vertical bar B vertical bar n(2))) to pseudopolynomial time (O(vertical bar B vertical bar n(3)c(max)(2)log(nc(max))), where vertical bar B vertical bar is the size of buffer library, n is the number of buffer stations, and c(max) is proportional to the number of all possible subtrees of the net. To improve the time complexity, we propose an approximation technique by sampling subsolutions (i.e., options) and apply predictive min-delay and prebuffer slack pruning rules from a related work. Experiments show that sampling is most effective to reduce run time, whereas the two pruning rules further improve efficiency and accuracy loss due to sampling. We show that our proposed algorithm has linear time complexity with respect to the tree size. It runs over 1000 times faster at a cost of less than 2% delay and power increase over the extended van Ginneken algorithm.
dual-v(dd) buffer insertion delay low power