File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Nonmigratory multiprocessor scheduling for response time and energy

TitleNonmigratory multiprocessor scheduling for response time and energy
Authors
KeywordsAnalysis of algorithms and problem complexity
Energy-aware systems
Online computation
Sequencing and scheduling
Issue Date2008
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tpds
Citation
Ieee Transactions On Parallel And Distributed Systems, 2008, v. 19 n. 11, p. 1527-1539 How to Cite?
AbstractEnergy usage has been an important concern in recent research on online job scheduling, where processors are allowed to vary the speed dynamically so as to save energy whenever possible. Notice that providing good quality of service such as response time (flow time) and conserving energy are conflicting objectives. An interesting problem for scheduling is how to optimize an economic tradeoff of flow time and energy. To this end, the past two years have witnessed significant progress in the single-processor setting, and online algorithms with performance close to optimal have been obtained. In this paper we extend the study of optimizing the tradeoff between flow time and energy to the multi-processor setting. We derive and analyze a simple non-migratory online algorithm that makes use of the classified-round-robin (CRR) strategy to dispatch jobs. Even in the worst case, its performance is within O(log P) times of the optimal migratory offline algorithm, where P is the ratio of the maximum job size to the minimum job size. Technically speaking, this online result stems from a non-trivial solution to an offline problem of eliminating migration, which is also interesting by itself. © 2008 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/60632
ISSN
2023 Impact Factor: 5.6
2023 SCImago Journal Rankings: 2.340
ISI Accession Number ID
Funding AgencyGrant Number
Hong Kong GRF
EPSRCEP/E028276/1
Funding Information:

This research was partially supported by Hong Kong GRF Grant and by the EPSRC Grant EP/E028276/1.

References

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTo, IKKen_HK
dc.contributor.authorWong, PWHen_HK
dc.date.accessioned2010-05-31T04:15:20Z-
dc.date.available2010-05-31T04:15:20Z-
dc.date.issued2008en_HK
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 2008, v. 19 n. 11, p. 1527-1539en_HK
dc.identifier.issn1045-9219en_HK
dc.identifier.urihttp://hdl.handle.net/10722/60632-
dc.description.abstractEnergy usage has been an important concern in recent research on online job scheduling, where processors are allowed to vary the speed dynamically so as to save energy whenever possible. Notice that providing good quality of service such as response time (flow time) and conserving energy are conflicting objectives. An interesting problem for scheduling is how to optimize an economic tradeoff of flow time and energy. To this end, the past two years have witnessed significant progress in the single-processor setting, and online algorithms with performance close to optimal have been obtained. In this paper we extend the study of optimizing the tradeoff between flow time and energy to the multi-processor setting. We derive and analyze a simple non-migratory online algorithm that makes use of the classified-round-robin (CRR) strategy to dispatch jobs. Even in the worst case, its performance is within O(log P) times of the optimal migratory offline algorithm, where P is the ratio of the maximum job size to the minimum job size. Technically speaking, this online result stems from a non-trivial solution to an offline problem of eliminating migration, which is also interesting by itself. © 2008 IEEE.en_HK
dc.languageengen_HK
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tpdsen_HK
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systemsen_HK
dc.rights©2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.en_HK
dc.subjectAnalysis of algorithms and problem complexityen_HK
dc.subjectEnergy-aware systemsen_HK
dc.subjectOnline computationen_HK
dc.subjectSequencing and schedulingen_HK
dc.titleNonmigratory multiprocessor scheduling for response time and energyen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1045-9219&volume=19&issue=11&spage=1527&epage=1539&date=2008&atitle=Nonmigratory+multiprocessor+scheduling+for+response+time+and+energyen_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_fulltext-
dc.identifier.doi10.1109/TPDS.2008.115en_HK
dc.identifier.scopuseid_2-s2.0-54249150461en_HK
dc.identifier.hkuros154829en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-54249150461&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume19en_HK
dc.identifier.issue11en_HK
dc.identifier.spage1527en_HK
dc.identifier.epage1539en_HK
dc.identifier.isiWOS:000259457200008-
dc.publisher.placeUnited Statesen_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.issnl1045-9219-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats