A Provably Good Approximation Algorithm for Power Optimization Using Multiple Supply Voltages

Multiple supply voltages (MSV´s) provide an effective technique for power optimization. This paper addresses a voltage partitioning problem arising in MSV design during high-level synthesis. We point out a theoretical mistake in a recent publication and prove that the partitioning problem is NP-hard. Despite its NP-hardness, we propose an efficient alpha²-approximation algorithm for the problem, where a is the constant ratio of the maximum to the minimum voltages. Compared with the previous work that runs in O(dn²) time, the time complexity of our algorithm is only O(dkn), where d, k, and n are respectively the numbers of voltages employed in the final designs (i.e., voltage domains), available supply voltages in the technology library, and functional units. Note that both d and k can be considered as small constants for practical applications. Experimental results show that our algorithm can achieve 36-255X run-time speedups than the recent work, with the same power reduction.