Can I read A Provably Good Approximation Algorithm for Power Optimization Using Multiple Supply Voltages on EtoBox?

A Provably Good Approximation Algorithm for Power Optimization Using Multiple Supply Voltages by Hung-Yi Liu; Wan-Ping Lee; Yao-Wen Chang is a Computer Science article available to read on EtoBox.

What is A Provably Good Approximation Algorithm for Power Optimization Using Multiple Supply Voltages about?

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 NPhardness, 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.

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

Author

Hung-Yi Liu; Wan-Ping Lee; Yao-Wen Chang

Publisher

ACM Press

Published

2007

Language

EN

Field

Computer Science (Physical Sciences)