Approximation algorithms for variable voltage processors : Min energy, max throughput and online heuristics

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

10 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)4074-4080
Journal / PublicationTheoretical Computer Science
Volume412
Issue number32
Online published22 Oct 2010
Publication statusPublished - 22 Jul 2011

Abstract

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 (nlog 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.

Research Area(s)

  • Approximation algorithms, Dynamic voltage scaling, Minimum energy, Online heuristics, Throughput