File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Nonmigratory online deadline scheduling on multiprocessors

TitleNonmigratory online deadline scheduling on multiprocessors
Authors
KeywordsCompetitive analysis
Job migration
Multiprocessor scheduling
Online algorithms
Resource augmentation
Issue Date2005
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP
Citation
Siam Journal On Computing, 2005, v. 34 n. 3, p. 669-682 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 nonmigratory online schedule using m speed-5.828 processors (i.e., processors 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 [B. Kalyanasundaram and K. R. Pruhs, J. Algorithms, 38 (2001), pp. 2-24] or a migratory online schedule using m speed-2 processors [C. A. Phillips et al., Algorithmica. 32 (2002), pp. 163-200]. 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 nonmigratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm. © 2005 Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/43620
ISSN
2015 Impact Factor: 0.841
2015 SCImago Journal Rankings: 1.808
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HOLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorKarKeung, TOen_HK
dc.date.accessioned2007-03-23T04:50:37Z-
dc.date.available2007-03-23T04:50:37Z-
dc.date.issued2005en_HK
dc.identifier.citationSiam Journal On Computing, 2005, v. 34 n. 3, p. 669-682en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43620-
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 nonmigratory online schedule using m speed-5.828 processors (i.e., processors 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 [B. Kalyanasundaram and K. R. Pruhs, J. Algorithms, 38 (2001), pp. 2-24] or a migratory online schedule using m speed-2 processors [C. A. Phillips et al., Algorithmica. 32 (2002), pp. 163-200]. 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 nonmigratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm. © 2005 Society for Industrial and Applied Mathematics.en_HK
dc.format.extent187614 bytes-
dc.format.extent26112 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMPen_HK
dc.relation.ispartofSIAM Journal on Computingen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectCompetitive analysisen_HK
dc.subjectJob migrationen_HK
dc.subjectMultiprocessor schedulingen_HK
dc.subjectOnline algorithmsen_HK
dc.subjectResource augmentationen_HK
dc.titleNonmigratory online deadline scheduling on multiprocessorsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0097-5397&volume=34&issue=3&spage=669&epage=682&date=2005&atitle=Nonmigratory+Online+Deadline+Scheduling+on+Multiprocessorsen_HK
dc.identifier.emailChan, HOL:hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityChan, HOL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1137/S0097539703435765en_HK
dc.identifier.scopuseid_2-s2.0-20544472683en_HK
dc.identifier.hkuros100152-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-20544472683&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume34en_HK
dc.identifier.issue3en_HK
dc.identifier.spage669en_HK
dc.identifier.epage682en_HK
dc.identifier.isiWOS:000228917600007-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, HOL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridKarKeung, TO=8644294300en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats