A provably good approximation optimization using multiple algorithm for power 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(2)-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(2)) 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.