File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Sleep with guilt and work faster to minimize flow plus energy

TitleSleep with guilt and work faster to minimize flow plus energy
Authors
KeywordsBounded-speed
Maximum speed
Multiple levels
New model
Non-clairvoyant algorithms
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 2009), Rhodes, Greece, 5-12 July 2009. In Lecture Notes in Computer Science, 2009, v. 5555, p. 665-676 How to Cite?
AbstractIn this paper we extend the study of flow-energy scheduling to a model that allows both sleep management and speed scaling. Our main result is a sleep management algorithm called IdleLonger, which works online for a processor with one or multiple levels of sleep states. The design of IdleLonger is interesting; among others, it may force the processor to idle or even sleep even though new jobs have already arrived. IdleLonger works in both clairvoyant and non-clairvoyant settings. We show how to adapt two existing speed scaling algorithms AJC [15] (clairvoyant) and LAPS [9] (non-clairvoyant) to the new model. The adapted algorithms, when coupled with IdleLonger, are shown to be O(1)-competitive clairvoyant and non-clairvoyant algorithms for minimizing flow plus energy on a processor that allows sleep management and speed scaling. The above results are based on the traditional model with no limit on processor speed. If the processor has a maximum speed, the problem becomes more difficult as the processor, once overslept, cannot rely on unlimited extra speed to catch up the delay. Nevertheless, we are able to enhance IdleLonger and AJC so that they remain O(1)-competitive for flow plus energy under the bounded speed model. Non-clairvoyant scheduling in the bounded speed model is left as an open problem. © 2009 Springer Berlin Heidelberg.
DescriptionLNCS v. 5555 is Proceedings of the 36th International Colloquium, ICALP 2009
Session A3 - Scheduling
Persistent Identifierhttp://hdl.handle.net/10722/93390
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorTo, IKKen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-09-25T14:59:38Z-
dc.date.available2010-09-25T14:59:38Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Rhodes, Greece, 5-12 July 2009. In Lecture Notes in Computer Science, 2009, v. 5555, p. 665-676en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93390-
dc.descriptionLNCS v. 5555 is Proceedings of the 36th International Colloquium, ICALP 2009-
dc.descriptionSession A3 - Scheduling-
dc.description.abstractIn this paper we extend the study of flow-energy scheduling to a model that allows both sleep management and speed scaling. Our main result is a sleep management algorithm called IdleLonger, which works online for a processor with one or multiple levels of sleep states. The design of IdleLonger is interesting; among others, it may force the processor to idle or even sleep even though new jobs have already arrived. IdleLonger works in both clairvoyant and non-clairvoyant settings. We show how to adapt two existing speed scaling algorithms AJC [15] (clairvoyant) and LAPS [9] (non-clairvoyant) to the new model. The adapted algorithms, when coupled with IdleLonger, are shown to be O(1)-competitive clairvoyant and non-clairvoyant algorithms for minimizing flow plus energy on a processor that allows sleep management and speed scaling. The above results are based on the traditional model with no limit on processor speed. If the processor has a maximum speed, the problem becomes more difficult as the processor, once overslept, cannot rely on unlimited extra speed to catch up the delay. Nevertheless, we are able to enhance IdleLonger and AJC so that they remain O(1)-competitive for flow plus energy under the bounded speed model. Non-clairvoyant scheduling in the bounded speed model is left as an open problem. © 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 (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.subjectBounded-speed-
dc.subjectMaximum speed-
dc.subjectMultiple levels-
dc.subjectNew model-
dc.subjectNon-clairvoyant algorithms-
dc.titleSleep with guilt and work faster to minimize flow plus energyen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-02927-1_55en_HK
dc.identifier.scopuseid_2-s2.0-70449095258en_HK
dc.identifier.hkuros162181en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-70449095258&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5555 LNCSen_HK
dc.identifier.issuePART 1en_HK
dc.identifier.spage665en_HK
dc.identifier.epage676en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Rhodes, Greece, 5-12 July 2009. In Lecture Notes in Computer Science, 2009, v. 5555, p. 665-676-
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridTo, IKK=23398547200en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats