File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Improved bounds for speed scaling in devices obeying the cube-root rule

TitleImproved bounds for speed scaling in devices obeying the cube-root rule
Authors
KeywordsComputer Operating Systems
Control Theory
Energy Conservation
Energy Management
Geometry
Linguistics
Optimization
Quality Of Service
Translation (Languages)
Wireless Telecommunication Systems
Issue Date2009
PublisherSpringer 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, 5-12 July 2009. In Lecture Notes In Computer Science, 2009, v. 5555, pt. 1, p. 144-155 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. 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 non-trivial 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 cube-root rule. When α=3, we show that qOA is 6.7-competitive, improving upon the previous best guarantee of 27 achieved by the algorithm Optimal Available (OA). So when the cube-root 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.
DescriptionThis vol. is the proceedings of ICALP 2009
Persistent Identifierhttp://hdl.handle.net/10722/92635
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_HK
dc.contributor.authorChan, HLen_HK
dc.contributor.authorPruhs, Ken_HK
dc.contributor.authorKatz, Den_HK
dc.date.accessioned2010-09-17T10:52:35Z-
dc.date.available2010-09-17T10:52:35Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 36th International Colloquium on Automata, Languages and Programming (ICALP), Rhodes, Greece, 5-12 July 2009. In Lecture Notes In Computer Science, 2009, v. 5555, pt. 1, p. 144-155-
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92635-
dc.descriptionThis vol. is the proceedings of ICALP 2009-
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. 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 non-trivial 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 cube-root rule. When α=3, we show that qOA is 6.7-competitive, improving upon the previous best guarantee of 27 achieved by the algorithm Optimal Available (OA). So when the cube-root 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.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-
dc.subjectComputer Operating Systemsen_HK
dc.subjectControl Theoryen_HK
dc.subjectEnergy Conservationen_HK
dc.subjectEnergy Managementen_HK
dc.subjectGeometryen_HK
dc.subjectLinguisticsen_HK
dc.subjectOptimizationen_HK
dc.subjectQuality Of Serviceen_HK
dc.subjectTranslation (Languages)en_HK
dc.subjectWireless Telecommunication Systemsen_HK
dc.titleImproved bounds for speed scaling in devices obeying the cube-root ruleen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailBansal, N: nikhil@us.ibm.comen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hk-
dc.identifier.emailPruhs, K: kirk@cs.pitt.edu-
dc.identifier.emailKatz, D: dkatzrog@us.ibm.com-
dc.identifier.authorityChan, HL=rp01310en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-02927-1_14en_HK
dc.identifier.scopuseid_2-s2.0-70449120552en_HK
dc.identifier.hkuros177255-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70449120552&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5555 LNCSen_HK
dc.identifier.issuept. 1en_HK
dc.identifier.spage144en_HK
dc.identifier.epage155en_HK
dc.identifier.eissn1611-3349-
dc.publisher.placeGermanyen_HK
dc.description.otherThe 36th International Colloquium on Automata, Languages and Programming (ICALP), Rhodes, Greece, 5-12 July 2009. In Lecture Notes In Computer Science, 2009, v. 5555, pt. 1, p. 144-155-
dc.identifier.scopusauthoridBansal, N=7102714084en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridPruhs, K=6603866438en_HK
dc.identifier.scopusauthoridKatz, D=14028318800en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats