File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Optimizing throughput and energy in online deadline scheduling

TitleOptimizing throughput and energy in online deadline scheduling
Authors
KeywordsCompetitive analysis
Deadline scheduling
Online algorithms
Power saving
Speed scaling
Issue Date2009
PublisherAssociation for Computing Machinery, Inc
Citation
ACM Transactions On Algorithms, 2009, v. 6 n. 1, article no. 10 How to Cite?
AbstractThis article extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy usage (the rate is believed to be a cubic function of the speed). As the speed is upper bounded, the processor may be overloaded with jobs and no scheduling algorithms can guarantee to meet the deadlines of all jobs.Anoptimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. In designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. If we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [Koren and Shasha 1995]. On the other hand, existing work on energy-efficient scheduling focuses on a setting where the processor speed is unbounded and the concern is on minimizing the energy to complete all jobs; O(1)-competitive online algorithms with respect to energy usage have been known [Yao et al. 1995; Bansal et al. 2007a; Li et al. 2006]. This article presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is O(1)-competitive on both throughput and energy usage. If the maximum speed of the online scheduler is relaxed slightly to (1 + ε)T for some ε > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining O(1)-competitiveness on energy usage. © 2009 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/92649
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 1.555
ISI Accession Number ID
Funding AgencyGrant Number
HKU7176104
EPSRCEP/E028276/1
Funding Information:

The work of T.-W. Lam is partly supported by HKU Grant 7176104. The work of P. W. H. Wong is partly supported by EPSRC Grant EP/E028276/1.

References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorChan, JWTen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorMak, KSen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-09-17T10:53:00Z-
dc.date.available2010-09-17T10:53:00Z-
dc.date.issued2009en_HK
dc.identifier.citationACM Transactions On Algorithms, 2009, v. 6 n. 1, article no. 10en_HK
dc.identifier.issn1549-6325en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92649-
dc.description.abstractThis article extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy usage (the rate is believed to be a cubic function of the speed). As the speed is upper bounded, the processor may be overloaded with jobs and no scheduling algorithms can guarantee to meet the deadlines of all jobs.Anoptimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. In designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. If we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [Koren and Shasha 1995]. On the other hand, existing work on energy-efficient scheduling focuses on a setting where the processor speed is unbounded and the concern is on minimizing the energy to complete all jobs; O(1)-competitive online algorithms with respect to energy usage have been known [Yao et al. 1995; Bansal et al. 2007a; Li et al. 2006]. This article presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is O(1)-competitive on both throughput and energy usage. If the maximum speed of the online scheduler is relaxed slightly to (1 + ε)T for some ε > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining O(1)-competitiveness on energy usage. © 2009 ACM.en_HK
dc.languageengen_HK
dc.publisherAssociation for Computing Machinery, Incen_HK
dc.relation.ispartofACM Transactions on Algorithmsen_HK
dc.subjectCompetitive analysisen_HK
dc.subjectDeadline schedulingen_HK
dc.subjectOnline algorithmsen_HK
dc.subjectPower savingen_HK
dc.subjectSpeed scalingen_HK
dc.titleOptimizing throughput and energy in online deadline schedulingen_HK
dc.typeArticleen_HK
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/1644015.1644025en_HK
dc.identifier.scopuseid_2-s2.0-74049129322en_HK
dc.identifier.hkuros177251-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-74049129322&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6en_HK
dc.identifier.issue1en_HK
dc.identifier.spagearticle no. 10-
dc.identifier.epagearticle no. 10-
dc.identifier.eissn1549-6333-
dc.identifier.isiWOS:000273223500010-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridChan, JWT=16021445200en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridMak, KS=54970721600en_HK
dc.identifier.scopusauthoridWong, PWH=9734871500en_HK
dc.identifier.issnl1549-6325-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats