File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783540787730_21
 Scopus: eid_2s2.043049151836
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: Average rate speed scaling
Title  Average rate speed scaling 

Authors  
Keywords  Algorithms Power management techniques Scheduling problem Speed scaling Voltage scaling 
Issue Date  2008 
Publisher  Springer 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. 240251 How to Cite? 
Abstract  Speed scaling is a power management technique that involves dynamically changing the speed of a processor. This gives rise to dualobjective 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 SpringerVerlag Berlin Heidelberg. 
Persistent Identifier  http://hdl.handle.net/10722/92656 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
DC Field  Value  Language 

dc.contributor.author  Bansal, N  en_HK 
dc.contributor.author  Bunde, DP  en_HK 
dc.contributor.author  Chan, HL  en_HK 
dc.contributor.author  Pruhs, K  en_HK 
dc.date.accessioned  20100917T10:53:12Z   
dc.date.available  20100917T10:53:12Z   
dc.date.issued  2008  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2008, v. 4957 LNCS, p. 240251  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/92656   
dc.description.abstract  Speed scaling is a power management technique that involves dynamically changing the speed of a processor. This gives rise to dualobjective 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 SpringerVerlag Berlin Heidelberg.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.rights  The original publication is available at www.springerlink.com   
dc.subject  Algorithms  en_HK 
dc.subject  Power management techniques  en_HK 
dc.subject  Scheduling problem  en_HK 
dc.subject  Speed scaling  en_HK 
dc.subject  Voltage scaling  en_HK 
dc.title  Average rate speed scaling  en_HK 
dc.type  Article  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=01784617&volume=60&issue=4&spage=877&epage=889&date=2011&atitle=Average+rate+speed+scaling   
dc.identifier.email  Chan, HL:hlchan@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, HL=rp01310  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/9783540787730_21  en_HK 
dc.identifier.scopus  eid_2s2.043049151836  en_HK 
dc.identifier.hkuros  194064   
dc.identifier.volume  4957 LNCS  en_HK 
dc.identifier.issue  4   
dc.identifier.spage  240  en_HK 
dc.identifier.epage  251  en_HK 
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Bansal, N=7102714084  en_HK 
dc.identifier.scopusauthorid  Bunde, DP=6602970167  en_HK 
dc.identifier.scopusauthorid  Chan, HL=7403402384  en_HK 
dc.identifier.scopusauthorid  Pruhs, K=6603866438  en_HK 