License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-27971
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2797/

Abousamra, Ahmed ; Bunde, David P. ; Pruhs, Kirk

An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints

pdf-format:
Dokument 1.pdf (516 KB)


Abstract

We consider the first, and most well studied, speed scaling problem in the algorithmic literature: where the scheduling quality of service measure is a deadline feasibility constraint, and where the power objective is to minimize the total energy used. Four online algorithms for this problem have been proposed in the algorithmic literature. Based on the best upper bound that can be proved on the competitive ratio, the ranking of the online algorithms from best to worst is: $qOA$, $OA$, $AVR$, $BKP$. As a test case on the effectiveness of competitive analysis to predict the best online algorithm, we report on an experimental ``horse race'' between these algorithms using instances based on web server traces. Our main conclusion is that the ranking of our algorithms based on their performance in our experiments is identical to the order predicted by competitive analysis. This ranking holds over a large range of possible power functions, and even if the power objective is temperature.

BibTeX - Entry

@InProceedings{abousamra_et_al:DSP:2010:2797,
  author =	{Ahmed Abousamra and David P. Bunde and Kirk Pruhs},
  title =	{An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints},
  booktitle =	{Algorithm Engineering},
  year =	{2010},
  editor =	{Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders},
  number =	{10261},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2797},
  annote =	{Keywords: Scheduling, Speed Scaling, Experimental Algorithms, Power Management}
}

Keywords: Scheduling, Speed Scaling, Experimental Algorithms, Power Management
Seminar: 10261 - Algorithm Engineering
Issue date: 2010
Date of publication: 23.11.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI