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 α 2 -approximation algorithm for the problem, where α 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.