TY - JOUR
T1 - Approximation algorithms for variable voltage processors
T2 - Min energy, max throughput and online heuristics
AU - Li, Minming
PY - 2011/7/22
Y1 - 2011/7/22
N2 - Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power sα when running at speed s, the online heuristic AVR has a competitive ratio (2α)α/2. In this paper we first study the online heuristics for the discrete model where the processor can only run at d given speeds. We propose a method to transform online heuristic AVR to an online heuristic for the discrete model and prove a competitive ratio 2α-1(α-1)α-1(δα-1)α/(δ-1)(δα-δ)α-1+1, where δ is the maximum ratio between adjacent non-zero speed levels. We also prove that the analysis holds for a class of heuristics that satisfy certain natural properties. We further study the throughput maximization problem when there is an upper bound for the maximum speed. We propose a greedy algorithm with running time O (n2 log n) and prove that the output schedule is a 3-approximation of the throughput and a (α-1)α-1(3α-1)α/2αα(3α-1-1)α-1-approximation of the energy consumption.
AB - Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power sα when running at speed s, the online heuristic AVR has a competitive ratio (2α)α/2. In this paper we first study the online heuristics for the discrete model where the processor can only run at d given speeds. We propose a method to transform online heuristic AVR to an online heuristic for the discrete model and prove a competitive ratio 2α-1(α-1)α-1(δα-1)α/(δ-1)(δα-δ)α-1+1, where δ is the maximum ratio between adjacent non-zero speed levels. We also prove that the analysis holds for a class of heuristics that satisfy certain natural properties. We further study the throughput maximization problem when there is an upper bound for the maximum speed. We propose a greedy algorithm with running time O (n2 log n) and prove that the output schedule is a 3-approximation of the throughput and a (α-1)α-1(3α-1)α/2αα(3α-1-1)α-1-approximation of the energy consumption.
KW - Approximation algorithms
KW - Dynamic voltage scaling
KW - Minimum energy
KW - Online heuristics
KW - Throughput
UR - http://www.scopus.com/inward/record.url?scp=79959328068&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-79959328068&origin=recordpage
U2 - 10.1016/j.tcs.2010.10.011
DO - 10.1016/j.tcs.2010.10.011
M3 - 21_Publication in refereed journal
VL - 412
SP - 4074
EP - 4080
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 32
ER -