File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Trade-offs between speed and processor in hard-deadline scheduling

TitleTrade-offs between speed and processor in hard-deadline scheduling
Authors
KeywordsMathematics computers
Issue Date1999
PublisherSociety for Industrial and Applied Mathematics.
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 1999, p. 623-632 How to Cite?
AbstractThis paper revisits the problem of on-line scheduling of sequential jobs with hard deadlines in a preemptive, multiprocessor setting. An on-line scheduling algorithm is said to be optimal if it can schedule any set of jobs to meet their deadlines whenever it is feasible in the off-line sense. It is known that the earliest-deadline-first strategy (EDF) is optimal in a one-processor setting, and there is no optimal on-line algorithm in an m-processor setting where m≥2. Recent work however reveals that if the on-line algorithm is given faster processors, EDF is actually optimal for all m (e.g., when m = 2, it suffices to use processors 1.5 times as fast). This paper initiates the study of the trade-off between increasing the speed and using more processors in deriving optimal on-line scheduling algorithms. Several upper bound and lower bound results are presented. For example, the speed requirement of EDF can be reduced to 2-1+p/m+p when it is given p≥0 extra processors. The main result is a new on-line algorithm which demands less speedy processors so as to attain optimality (e.g., when m = 2, the speed requirement is 1 1/3) and admits a better speed-processor trade-off than EDF (e.g., when m = 2 and p = 1, the speed requirement is 1.2). In general, no optimal algorithm exists when the speed factor is less than 1/(2√2+p/m-2).
Persistent Identifierhttp://hdl.handle.net/10722/45606
ISSN

 

DC FieldValueLanguage
dc.contributor.authorLam, Tak Wahen_HK
dc.contributor.authorTo, Kar Keungen_HK
dc.date.accessioned2007-10-30T06:30:09Z-
dc.date.available2007-10-30T06:30:09Z-
dc.date.issued1999en_HK
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 1999, p. 623-632en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45606-
dc.description.abstractThis paper revisits the problem of on-line scheduling of sequential jobs with hard deadlines in a preemptive, multiprocessor setting. An on-line scheduling algorithm is said to be optimal if it can schedule any set of jobs to meet their deadlines whenever it is feasible in the off-line sense. It is known that the earliest-deadline-first strategy (EDF) is optimal in a one-processor setting, and there is no optimal on-line algorithm in an m-processor setting where m≥2. Recent work however reveals that if the on-line algorithm is given faster processors, EDF is actually optimal for all m (e.g., when m = 2, it suffices to use processors 1.5 times as fast). This paper initiates the study of the trade-off between increasing the speed and using more processors in deriving optimal on-line scheduling algorithms. Several upper bound and lower bound results are presented. For example, the speed requirement of EDF can be reduced to 2-1+p/m+p when it is given p≥0 extra processors. The main result is a new on-line algorithm which demands less speedy processors so as to attain optimality (e.g., when m = 2, the speed requirement is 1 1/3) and admits a better speed-processor trade-off than EDF (e.g., when m = 2 and p = 1, the speed requirement is 1.2). In general, no optimal algorithm exists when the speed factor is less than 1/(2√2+p/m-2).en_HK
dc.format.extent1075547 bytes-
dc.format.extent4181 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectMathematics computersen_HK
dc.titleTrade-offs between speed and processor in hard-deadline schedulingen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1071-9040&volume=&spage=623&epage=631&date=1999&atitle=Trade-offs+between+speed+and+processor+in+hard-deadline+schedulingen_HK
dc.identifier.emailLam, Tak Wah:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, Tak Wah=rp00135en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-0032776989en_HK
dc.identifier.hkuros40755-
dc.identifier.spage623en_HK
dc.identifier.epage632en_HK
dc.identifier.scopusauthoridLam, Tak Wah=7202523165en_HK
dc.identifier.scopusauthoridTo, Kar Keung=36785812300en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats