File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Non-clairvoyant speed scaling for weighted flow time

TitleNon-clairvoyant speed scaling for weighted flow time
Authors
KeywordsAt-speed
Competitive algorithms
Energy efficient
Flow-time
Job scheduling
Issue Date2010
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 18th Annual European Symposium on Algorithms (ESA 2010), Liverpool, UK., 6-8 September 2010. In Lecture Notes In Computer Science, 2010, v. 6346 pt. 1, p. 23-35 How to Cite?
AbstractWe study online job scheduling on a processor that can vary its speed dynamically to manage its power. We attempt to extend the recent success in analyzing total unweighted flow time plus energy to total weighted flow time plus energy. We first consider the non-clairvoyant setting where the size of a job is only known when the job finishes. We show an online algorithm WLAPS that is 8α2-competitive for weighted flow time plus energy under the traditional power model, which assumes the power P(s) to run the processor at speed s to be sα for some α > 1. More interestingly, for any arbitrary power function P(s), WLAPS remains competitive when given a more energy-efficient processor; precisely, WLAPS is 16(1 + 1/ε) 2-competitive when using a processor that, given the power P(s), can run at speed (1 + ε)s for some ε > 0. Without such speedup, no non-clairvoyant algorithm can be O(1)-competitive for an arbitrary power function [8]. For the clairvoyant setting (where the size of a job is known at release time), previous results on minimizing weighted flow time plus energy rely on scaling the speed continuously over time [5-7]. The analysis of WLAPS has inspired us to devise a clairvoyant algorithm LLB which can transform any continuous speed scaling algorithm to one that scales the speed at discrete times only. Under an arbitrary power function, LLB can give an 4(1 + 1/ε)-competitive algorithm using a processor with (1 + ε)-speedup. © 2010 Springer-Verlag.
DescriptionLNCS v. 6346 has title: Algorithms - ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010: Proceedings
Persistent Identifierhttp://hdl.handle.net/10722/129559
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChan, SHen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.date.accessioned2010-12-23T08:39:16Z-
dc.date.available2010-12-23T08:39:16Z-
dc.date.issued2010en_HK
dc.identifier.citationThe 18th Annual European Symposium on Algorithms (ESA 2010), Liverpool, UK., 6-8 September 2010. In Lecture Notes In Computer Science, 2010, v. 6346 pt. 1, p. 23-35en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129559-
dc.descriptionLNCS v. 6346 has title: Algorithms - ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010: Proceedings-
dc.description.abstractWe study online job scheduling on a processor that can vary its speed dynamically to manage its power. We attempt to extend the recent success in analyzing total unweighted flow time plus energy to total weighted flow time plus energy. We first consider the non-clairvoyant setting where the size of a job is only known when the job finishes. We show an online algorithm WLAPS that is 8α2-competitive for weighted flow time plus energy under the traditional power model, which assumes the power P(s) to run the processor at speed s to be sα for some α > 1. More interestingly, for any arbitrary power function P(s), WLAPS remains competitive when given a more energy-efficient processor; precisely, WLAPS is 16(1 + 1/ε) 2-competitive when using a processor that, given the power P(s), can run at speed (1 + ε)s for some ε > 0. Without such speedup, no non-clairvoyant algorithm can be O(1)-competitive for an arbitrary power function [8]. For the clairvoyant setting (where the size of a job is known at release time), previous results on minimizing weighted flow time plus energy rely on scaling the speed continuously over time [5-7]. The analysis of WLAPS has inspired us to devise a clairvoyant algorithm LLB which can transform any continuous speed scaling algorithm to one that scales the speed at discrete times only. Under an arbitrary power function, LLB can give an 4(1 + 1/ε)-competitive algorithm using a processor with (1 + ε)-speedup. © 2010 Springer-Verlag.en_HK
dc.languageengen_US
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.comen_US
dc.subjectAt-speed-
dc.subjectCompetitive algorithms-
dc.subjectEnergy efficient-
dc.subjectFlow-time-
dc.subjectJob scheduling-
dc.titleNon-clairvoyant speed scaling for weighted flow timeen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0302-9743&volume=6346 &issue=pt. 1&spage=23&epage=35&date=2010&atitle=Non-clairvoyant+speed+scaling+for+weighted+flow+time-
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-15775-2_3en_HK
dc.identifier.scopuseid_2-s2.0-78249245096en_HK
dc.identifier.hkuros177022en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-78249245096&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6346 LNCSen_HK
dc.identifier.issuePART 1en_HK
dc.identifier.spage23en_HK
dc.identifier.epage35en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 18th Annual European Symposium on Algorithms (ESA 2010), Liverpool, UK., 6-8 September 2010. In Lecture Notes In Computer Science, 2010, v. 6346 pt. 1, p. 23-35-
dc.identifier.scopusauthoridChan, SH=36652336600en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats