File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Average rate speed scaling

TitleAverage rate speed scaling
Authors
KeywordsOnline Algorithms
Power Management
Scheduling
Speed Scaling
Voltage Scaling
Issue Date2011
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica (New York), 2011, v. 60 n. 4, p. 877-889 How to Cite?
AbstractSpeed scaling is a power management technique that involves dynamically changing the speed of a processor. This gives rise to dual-objective scheduling problems, where the operating system both wants to conserve energy and optimize some Quality of Service (QoS) measure of the resulting schedule. Yao, Demers, and Shenker (Proc. IEEE Symp. Foundations of Computer Science, pp. 374-382, 1995) considered the problem where the QoS constraint is deadline feasibility and the objective is to minimize the energy used. They proposed an online speed scaling algorithm Average Rate (AVR) that runs each job at a constant speed between its release and its deadline. They showed that the competitive ratio of AVR is at most (2α) α /2 if a processor running at speed s uses power s α . We show the competitive ratio of AVR is at least ((2-δ)α) α /2, where δ is a function of α that approaches zero as α approaches infinity. This shows that the competitive analysis of AVR by Yao, Demers, and Shenker is essentially tight, at least for large α. We also give an alternative proof that the competitive ratio of AVR is at most (2α) α /2 using a potential function argument. We believe that this analysis is significantly simpler and more elementary than the original analysis of AVR in Yao et al. (Proc. IEEE Symp. Foundations of Computer Science, pp. 374-382, 1995). © 2009 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/152459
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.905
ISI Accession Number ID
Funding AgencyGrant Number
Howard Hughes Medical Institute52005130
NSFCNS-0325353
CCF-0514058
IIS-0534531
CCF-0830558
IBM Faculty
Funding Information:

D.P. Bunde was supported in part by Howard Hughes Medical Institute grant 52005130.

References

 

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_US
dc.contributor.authorBunde, DPen_US
dc.contributor.authorChan, HLen_US
dc.contributor.authorPruhs, Ken_US
dc.date.accessioned2012-06-26T06:39:19Z-
dc.date.available2012-06-26T06:39:19Z-
dc.date.issued2011en_US
dc.identifier.citationAlgorithmica (New York), 2011, v. 60 n. 4, p. 877-889en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152459-
dc.description.abstractSpeed scaling is a power management technique that involves dynamically changing the speed of a processor. This gives rise to dual-objective scheduling problems, where the operating system both wants to conserve energy and optimize some Quality of Service (QoS) measure of the resulting schedule. Yao, Demers, and Shenker (Proc. IEEE Symp. Foundations of Computer Science, pp. 374-382, 1995) considered the problem where the QoS constraint is deadline feasibility and the objective is to minimize the energy used. They proposed an online speed scaling algorithm Average Rate (AVR) that runs each job at a constant speed between its release and its deadline. They showed that the competitive ratio of AVR is at most (2α) α /2 if a processor running at speed s uses power s α . We show the competitive ratio of AVR is at least ((2-δ)α) α /2, where δ is a function of α that approaches zero as α approaches infinity. This shows that the competitive analysis of AVR by Yao, Demers, and Shenker is essentially tight, at least for large α. We also give an alternative proof that the competitive ratio of AVR is at most (2α) α /2 using a potential function argument. We believe that this analysis is significantly simpler and more elementary than the original analysis of AVR in Yao et al. (Proc. IEEE Symp. Foundations of Computer Science, pp. 374-382, 1995). © 2009 Springer Science+Business Media, LLC.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmica (New York)en_US
dc.subjectOnline Algorithmsen_US
dc.subjectPower Managementen_US
dc.subjectSchedulingen_US
dc.subjectSpeed Scalingen_US
dc.subjectVoltage Scalingen_US
dc.titleAverage rate speed scalingen_US
dc.typeArticleen_US
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_US
dc.identifier.authorityChan, HL=rp01310en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s00453-009-9379-zen_US
dc.identifier.scopuseid_2-s2.0-79959250379en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79959250379&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume60en_US
dc.identifier.issue4en_US
dc.identifier.spage877en_US
dc.identifier.epage889en_US
dc.identifier.isiWOS:000290267000009-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridBansal, N=7102714084en_US
dc.identifier.scopusauthoridBunde, DP=6602970167en_US
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.scopusauthoridPruhs, K=6603866438en_US
dc.identifier.citeulike6414401-
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats