Provably good algorithm for low power consumption with dual supply voltages

The dual-voltage approach has emerged as an effective and practical technique for power reduction. In this paper, we explore power optimization with dual supply voltages under given timing constraints. By analyzing the relations among the timing slack, delay and power consumption in a given circuit, we relate the voltage-scaling power optimization to the maximal weighted independent set (MWIS) problem, which is polynomial-time solvable on a transitive graph. Then we develop a provably good lower-bound algorithm based on MWIS to generate the lower bound of the power consumption. Also, we propose a fast approach to predict the optimum supply voltages. The maximum power reduction is obtained by using a modified lower-bound algorithm with optimum voltages. Experimental results show that the resulting lower bound is tight for most circuits and that the estimated optimum supply voltage is exactly, or very close to, the best choice of actual voltages.