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

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Improved bounds for speed scaling in devices obeying the cuberoot rule
Title  Improved bounds for speed scaling in devices obeying the cuberoot rule 

Authors  
Keywords  Computer Operating Systems Control Theory Energy Conservation Energy Management Geometry Linguistics Optimization Quality Of Service Translation (Languages) Wireless Telecommunication Systems 
Issue Date  2009 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 36th International Colloquium on Automata, Languages and Programming (ICALP), Rhodes, Greece, 512 July 2009. In Lecture Notes In Computer Science, 2009, v. 5555, pt. 1, p. 144155 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. In the most investigated speed scaling problem in the literature, the QoS constraint is deadline feasibility, and the objective is to minimize the energy used. The standard assumption is that the power consumption is the speed to some constant power α. We give the first nontrivial lower bound, namely e α1/α, on the competitive ratio for this problem. This comes close to the best upper bound which is about 2e α+1. We analyze a natural class of algorithms called qOA, where at any time, the processor works at q 1 times the minimum speed required to ensure feasibility assuming no new jobs arrive. For CMOS based processors, and many other types of devices, α=3, that is, they satisfy the cuberoot rule. When α=3, we show that qOA is 6.7competitive, improving upon the previous best guarantee of 27 achieved by the algorithm Optimal Available (OA). So when the cuberoot rule holds, our results reduce the range for the optimal competitive ratio from [1.2, 27] to [2.4, 6.7]. We also analyze qOA for general α and give almost matching upper and lower bounds. © 2009 Springer Berlin Heidelberg. 
Description  This vol. is the proceedings of ICALP 2009 
Persistent Identifier  http://hdl.handle.net/10722/92635 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Bansal, N  en_HK 
dc.contributor.author  Chan, HL  en_HK 
dc.contributor.author  Pruhs, K  en_HK 
dc.contributor.author  Katz, D  en_HK 
dc.date.accessioned  20100917T10:52:35Z   
dc.date.available  20100917T10:52:35Z   
dc.date.issued  2009  en_HK 
dc.identifier.citation  The 36th International Colloquium on Automata, Languages and Programming (ICALP), Rhodes, Greece, 512 July 2009. In Lecture Notes In Computer Science, 2009, v. 5555, pt. 1, p. 144155   
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/92635   
dc.description  This vol. is the proceedings of ICALP 2009   
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. In the most investigated speed scaling problem in the literature, the QoS constraint is deadline feasibility, and the objective is to minimize the energy used. The standard assumption is that the power consumption is the speed to some constant power α. We give the first nontrivial lower bound, namely e α1/α, on the competitive ratio for this problem. This comes close to the best upper bound which is about 2e α+1. We analyze a natural class of algorithms called qOA, where at any time, the processor works at q 1 times the minimum speed required to ensure feasibility assuming no new jobs arrive. For CMOS based processors, and many other types of devices, α=3, that is, they satisfy the cuberoot rule. When α=3, we show that qOA is 6.7competitive, improving upon the previous best guarantee of 27 achieved by the algorithm Optimal Available (OA). So when the cuberoot rule holds, our results reduce the range for the optimal competitive ratio from [1.2, 27] to [2.4, 6.7]. We also analyze qOA for general α and give almost matching upper and lower bounds. © 2009 Springer 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   
dc.subject  Computer Operating Systems  en_HK 
dc.subject  Control Theory  en_HK 
dc.subject  Energy Conservation  en_HK 
dc.subject  Energy Management  en_HK 
dc.subject  Geometry  en_HK 
dc.subject  Linguistics  en_HK 
dc.subject  Optimization  en_HK 
dc.subject  Quality Of Service  en_HK 
dc.subject  Translation (Languages)  en_HK 
dc.subject  Wireless Telecommunication Systems  en_HK 
dc.title  Improved bounds for speed scaling in devices obeying the cuberoot rule  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Bansal, N: nikhil@us.ibm.com  en_HK 
dc.identifier.email  Chan, HL:hlchan@cs.hku.hk   
dc.identifier.email  Pruhs, K: kirk@cs.pitt.edu   
dc.identifier.email  Katz, D: dkatzrog@us.ibm.com   
dc.identifier.authority  Chan, HL=rp01310  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/9783642029271_14  en_HK 
dc.identifier.scopus  eid_2s2.070449120552  en_HK 
dc.identifier.hkuros  177255   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.070449120552&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  5555 LNCS  en_HK 
dc.identifier.issue  pt. 1  en_HK 
dc.identifier.spage  144  en_HK 
dc.identifier.epage  155  en_HK 
dc.identifier.eissn  16113349   
dc.publisher.place  Germany  en_HK 
dc.description.other  The 36th International Colloquium on Automata, Languages and Programming (ICALP), Rhodes, Greece, 512 July 2009. In Lecture Notes In Computer Science, 2009, v. 5555, pt. 1, p. 144155   
dc.identifier.scopusauthorid  Bansal, N=7102714084  en_HK 
dc.identifier.scopusauthorid  Chan, HL=7403402384  en_HK 
dc.identifier.scopusauthorid  Pruhs, K=6603866438  en_HK 
dc.identifier.scopusauthorid  Katz, D=14028318800  en_HK 