Title :
A Provably Good Approximation Algorithm for Power Optimization Using Multiple Supply Voltages
Author :
Liu, Hung-Yi ; Lee, Wan-Ping ; Chang, Yao-Wen
Author_Institution :
Nat. Taiwan Univ., Taipei
Abstract :
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 alpha2-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(dn2) 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.
Keywords :
approximation theory; computational complexity; computer power supplies; power aware computing; NP-hard; approximation algorithm; high-level synthesis; multiple supply voltages; power optimization; time complexity; voltage partitioning; Algorithm design and analysis; Approximation algorithms; Design optimization; High level synthesis; Libraries; Partitioning algorithms; Performance analysis; Power engineering and energy; Runtime; Voltage; Algorithms; Design; Multiple Supply Voltages; Power Optimization;
Conference_Titel :
Design Automation Conference, 2007. DAC '07. 44th ACM/IEEE
Conference_Location :
San Diego, CA
Print_ISBN :
978-1-59593-627-1