File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Non-migratory Online Deadline Scheduling on Multiprocessors

TitleNon-migratory Online Deadline Scheduling on Multiprocessors
Authors
Issue Date2004
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2004, v. 15, p. 963-972 How to Cite?
AbstractIn this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m processors. We show that I can also be completed by a non-migratory online schedule using m speed-5.828 processors (i.e., processors of 5.828 times faster). This result supplements the previous results that I can also be completed by a non-migratory offline schedule using 6m unit-speed processors or a migratory online schedule using m speed-2 processors. Our result is based on a simple conservative scheduling algorithm called PARK which commits a processor to a job only when the processor has zero commitment before its deadline. A careful analysis of PARK further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). PARK also finds application in overloaded systems; it gives the first online non-migratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm.
Persistent Identifierhttp://hdl.handle.net/10722/151853
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorTo, KKen_US
dc.date.accessioned2012-06-26T06:30:07Z-
dc.date.available2012-06-26T06:30:07Z-
dc.date.issued2004en_US
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2004, v. 15, p. 963-972en_US
dc.identifier.urihttp://hdl.handle.net/10722/151853-
dc.description.abstractIn this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m processors. We show that I can also be completed by a non-migratory online schedule using m speed-5.828 processors (i.e., processors of 5.828 times faster). This result supplements the previous results that I can also be completed by a non-migratory offline schedule using 6m unit-speed processors or a migratory online schedule using m speed-2 processors. Our result is based on a simple conservative scheduling algorithm called PARK which commits a processor to a job only when the processor has zero commitment before its deadline. A careful analysis of PARK further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). PARK also finds application in overloaded systems; it gives the first online non-migratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm.en_US
dc.languageengen_US
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.titleNon-migratory Online Deadline Scheduling on Multiprocessorsen_US
dc.typeConference_Paperen_US
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityChan, HL=rp01310en_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-1842591306en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-1842591306&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume15en_US
dc.identifier.spage963en_US
dc.identifier.epage972en_US
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridTo, KK=36785812300en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats