The epsilon-approximation to discrete VT assignment for leakage power minimization

As VLSI technology reaches 45nm technology node, leakage power optimization has become a major design challenge. Threshold voltage (vt) assignment has been extensively studied, due to its effectiveness in leakage power reduction. In contrast to the efficiently solvable continuous vt assignment problem, the discrete vt assignment problem is known to be NP-hard. All of the existing techniques are heuristics without performance guarantee due to the NP-hardness nature of the problem. It is still not known whether there is any rigorous approximation algorithm for the discrete vt assignment problem. In this paper, the first ε-approximation algorithm is designed for the discrete vt assignment problem. The algorithm can ε-approximate the optimal vt assignment solution in (equation presented) time, where n is the size of the combinational circuit and m is the number of available threshold voltages per gate. It is based on an advanced potential function technique and an efficient dual decision core query technique. Our experiments on ISCAS\u2785 benchmark circuits demonstrate that the new algorithm always returns a solution with error bounded by ε even compared to the lower bound of the optimal solution. On average, it can approximate the optimal solution with 2.8% additional leakage power running in 51.3 seconds, while the integer linear programming technique is computationally prohibitive. Our algorithm also significantly outperforms the heuristic in [1] by 16.5% leakage power saving with similar runtime. This clearly demonstrates the practicality of the proposed ε-approximation algorithm for the vt assignment problem. Copyright 2009 ACM