File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor

TitleSpeed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor
Authors
KeywordsPower Management
Scheduling
Speed Scaling
Issue Date2011
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00224/
Citation
Theory Of Computing Systems, 2011, v. 49 n. 4, p. 817-833 How to Cite?
AbstractWe consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the processes to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. We assume that a processor running at speed s uses power sα for some constant α > 1. For processes that may have side effects or that are not checkpointable, we show an Ω(m(α-1)/α2) bound on the competitive ratio of any randomized algorithm. For checkpointable processes without side effects, we give an O(log m)-competitive algorithm. Thus for processes that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable processes without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log1/αm) on the competitive ratio of any randomized algorithm for checkpointable processes without side effects. © 2011 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/152468
ISSN
2015 Impact Factor: 0.719
2015 SCImago Journal Rankings: 0.677
ISI Accession Number ID
Funding AgencyGrant Number
NSERC Canada
IBM
NSFCNS-0325353
CCF-0514058
IIS-0534531
CCF-0830558
Funding Information:

J. Edmonds was supported in part by NSERC Canada.

References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_US
dc.contributor.authorEdmonds, Jen_US
dc.contributor.authorPruhs, Ken_US
dc.date.accessioned2012-06-26T06:39:27Z-
dc.date.available2012-06-26T06:39:27Z-
dc.date.issued2011en_US
dc.identifier.citationTheory Of Computing Systems, 2011, v. 49 n. 4, p. 817-833en_US
dc.identifier.issn1432-4350en_US
dc.identifier.urihttp://hdl.handle.net/10722/152468-
dc.description.abstractWe consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the processes to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. We assume that a processor running at speed s uses power sα for some constant α > 1. For processes that may have side effects or that are not checkpointable, we show an Ω(m(α-1)/α2) bound on the competitive ratio of any randomized algorithm. For checkpointable processes without side effects, we give an O(log m)-competitive algorithm. Thus for processes that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable processes without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log1/αm) on the competitive ratio of any randomized algorithm for checkpointable processes without side effects. © 2011 Springer Science+Business Media, LLC.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00224/en_US
dc.relation.ispartofTheory of Computing Systemsen_US
dc.subjectPower Managementen_US
dc.subjectSchedulingen_US
dc.subjectSpeed Scalingen_US
dc.titleSpeed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessoren_US
dc.typeArticleen_US
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_US
dc.identifier.authorityChan, HL=rp01310en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s00224-011-9349-0en_US
dc.identifier.scopuseid_2-s2.0-80053460130en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80053460130&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume49en_US
dc.identifier.issue4en_US
dc.identifier.spage817en_US
dc.identifier.epage833en_US
dc.identifier.isiWOS:000295519200008-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.scopusauthoridEdmonds, J=7102594589en_US
dc.identifier.scopusauthoridPruhs, K=6603866438en_US
dc.identifier.citeulike9510455-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats