Low power discrete voltage assignment under clock skew scheduling

Multiple Supply Voltage (MSV) assignment has emerged as an appealing technique in low power IC design, due to its flexibility in balancing power and performance. However, clock skew scheduling, which has great impact on criticality of combinational paths in sequential circuit, has not been explored in the merit of MSV assignment. In this paper, we propose a discrete voltage assignment algorithm for sequential circuit under clock scheduling. The sequential MSV assignment problem is first formulated as a convex cost dual network flow problem, which can be optimally solved in polynomial time assuming delay of each gate can be chosen in continuous domain. Then a mincut-based heuristic is designed to convert the unfeasible continuous solution into feasible discrete solution while largely preserving the global optimality. Besides, we revisit the hardness of the general discrete voltage assignment problem and point out some misunderstandings on the approximability of this problem in previous related work. Benchmark test for our algorithm shows 9.2% reduction in power consumption on average, in compared with combinational MSV assignment. Referring to the continuous solution obtained from network flow as the lower bound, the gap between our solution and the lower bound is only 1.77%.