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
KeywordsAlgorithms
Power management techniques
Scheduling problem
Speed scaling
Voltage scaling
Issue Date2008
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2008, v. 4957 LNCS, p. 240-251 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 [8] 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 ( ) that runs each job at a constant speed between its release and its deadline. They showed that the competitive ratio of is at most (2α) α /2 if a processor running at speed s uses power s α . We show the competitive ratio of is at least ((2∈-∈δ) α) α /2, where δ is a function of α that approaches zero as α approaches infinity. This shows that the competitive analysis of by Yao, Demers, and Shenker is essentially tight, at least for large α. We also give an alternative proof that the competitive ratio of 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 in [8]. © 2008 Springer-Verlag Berlin Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/92656
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_HK
dc.contributor.authorBunde, DPen_HK
dc.contributor.authorChan, HLen_HK
dc.contributor.authorPruhs, Ken_HK
dc.date.accessioned2010-09-17T10:53:12Z-
dc.date.available2010-09-17T10:53:12Z-
dc.date.issued2008en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2008, v. 4957 LNCS, p. 240-251en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92656-
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 [8] 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 ( ) that runs each job at a constant speed between its release and its deadline. They showed that the competitive ratio of is at most (2α) α /2 if a processor running at speed s uses power s α . We show the competitive ratio of is at least ((2∈-∈δ) α) α /2, where δ is a function of α that approaches zero as α approaches infinity. This shows that the competitive analysis of by Yao, Demers, and Shenker is essentially tight, at least for large α. We also give an alternative proof that the competitive ratio of 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 in [8]. © 2008 Springer-Verlag Berlin Heidelberg.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectAlgorithmsen_HK
dc.subjectPower management techniquesen_HK
dc.subjectScheduling problemen_HK
dc.subjectSpeed scalingen_HK
dc.subjectVoltage scalingen_HK
dc.titleAverage rate speed scalingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=60&issue=4&spage=877&epage=889&date=2011&atitle=Average+rate+speed+scaling-
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-540-78773-0_21en_HK
dc.identifier.scopuseid_2-s2.0-43049151836en_HK
dc.identifier.hkuros194064-
dc.identifier.volume4957 LNCSen_HK
dc.identifier.issue4-
dc.identifier.spage240en_HK
dc.identifier.epage251en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridBansal, N=7102714084en_HK
dc.identifier.scopusauthoridBunde, DP=6602970167en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridPruhs, K=6603866438en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats