License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10261.3
URN: urn:nbn:de:0030-drops-27971
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2797/
Go to the corresponding Portal

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

An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints

pdf-format:
10261.PruhsKirk.Paper.2797.pdf (0.5 MB)

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:DagSemProc.10261.3,
  author =	{Abousamra, Ahmed and Bunde, David P. and Pruhs, Kirk},
  title =	{{An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints}},
  booktitle =	{Algorithm Engineering},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10261},
  editor =	{Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2797},
  URN =		{urn:nbn:de:0030-drops-27971},
  doi =		{10.4230/DagSemProc.10261.3},
  annote =	{Keywords: Scheduling, Speed Scaling, Experimental Algorithms, Power Management}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI