DROPS

Document

An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints

Authors: Ahmed Abousamra, David P. Bunde, and Kirk Pruhs

Published in: Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)

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.

Cite as

Ahmed Abousamra, David P. Bunde, and Kirk Pruhs. An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.10261.3},
  URN =		{urn:nbn:de:0030-drops-27971},
  doi =		{10.4230/DagSemProc.10261.3},
  annote =	{Keywords: Scheduling, Speed Scaling, Experimental Algorithms, Power Management}
}

Search Results

Documents authored by Bunde, David P.

An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message