File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Deadline scheduling and power management for speed bounded processors

TitleDeadline scheduling and power management for speed bounded processors
Authors
KeywordsCompetitive analysis
Deadline scheduling
Energy saving
Online algorithms
Sleep management
Speed scaling
Issue Date2010
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2010, v. 411 n. 40-42, p. 3587-3600 How to Cite?
AbstractIn this paper we consider online deadline scheduling on a processor that can manage its energy usage by scaling the speed dynamically or entering a sleep state. A new online scheduling algorithm called SOA is presented. Assuming speed can be scaled arbitrarily high (the infinite speed model), SOA can complete all jobs with reduced energy usage, improving the competitive ratio for energy from 22α-2αα+2α-1+2 (Irani et al. (2007) [17]) to αα+2, where α is the constant involved in the speed-to-power function, commonly believed to be 2 or 3. More importantly, SOA is the first algorithm that works well even if the processor has a fixed maximum speed and the system is overloaded. In this case, SOA is 4-competitive for throughput and (αα+α24α+2)-competitive for energy. Note that the throughput ratio cannot be better than 4 even if energy is not a concern. © 2010 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/152442
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
Funding AgencyGrant Number
Fundamental Research Funds for the Central Universities
EPSRCEP/E028276/1
Funding Information:

X. Han is partially supported by the Fundamental Research Funds for the Central Universities.

References

 

DC FieldValueLanguage
dc.contributor.authorHan, Xen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTo, IKKen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2012-06-26T06:39:06Z-
dc.date.available2012-06-26T06:39:06Z-
dc.date.issued2010en_HK
dc.identifier.citationTheoretical Computer Science, 2010, v. 411 n. 40-42, p. 3587-3600en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/152442-
dc.description.abstractIn this paper we consider online deadline scheduling on a processor that can manage its energy usage by scaling the speed dynamically or entering a sleep state. A new online scheduling algorithm called SOA is presented. Assuming speed can be scaled arbitrarily high (the infinite speed model), SOA can complete all jobs with reduced energy usage, improving the competitive ratio for energy from 22α-2αα+2α-1+2 (Irani et al. (2007) [17]) to αα+2, where α is the constant involved in the speed-to-power function, commonly believed to be 2 or 3. More importantly, SOA is the first algorithm that works well even if the processor has a fixed maximum speed and the system is overloaded. In this case, SOA is 4-competitive for throughput and (αα+α24α+2)-competitive for energy. Note that the throughput ratio cannot be better than 4 even if energy is not a concern. © 2010 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.subjectCompetitive analysisen_HK
dc.subjectDeadline schedulingen_HK
dc.subjectEnergy savingen_HK
dc.subjectOnline algorithmsen_HK
dc.subjectSleep managementen_HK
dc.subjectSpeed scalingen_HK
dc.titleDeadline scheduling and power management for speed bounded processorsen_HK
dc.typeArticleen_HK
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_fulltexten_US
dc.identifier.doi10.1016/j.tcs.2010.05.035en_HK
dc.identifier.scopuseid_2-s2.0-77956095113en_HK
dc.identifier.hkuros183171-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77956095113&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume411en_HK
dc.identifier.issue40-42en_HK
dc.identifier.spage3587en_HK
dc.identifier.epage3600en_HK
dc.identifier.isiWOS:000281942400005-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridHan, X=34872071800en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridTo, IKK=23398547200en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.identifier.citeulike7274395-
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats