Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Tradeoffs between speed and processor in harddeadline scheduling
Title  Tradeoffs between speed and processor in harddeadline scheduling 

Authors  
Keywords  Mathematics computers 
Issue Date  1999 
Publisher  Society for Industrial and Applied Mathematics. 
Citation  Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 1999, p. 623632 How to Cite? 
Abstract  This paper revisits the problem of online scheduling of sequential jobs with hard deadlines in a preemptive, multiprocessor setting. An online 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 offline sense. It is known that the earliestdeadlinefirst strategy (EDF) is optimal in a oneprocessor setting, and there is no optimal online algorithm in an mprocessor setting where m≥2. Recent work however reveals that if the online 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 tradeoff between increasing the speed and using more processors in deriving optimal online scheduling algorithms. Several upper bound and lower bound results are presented. For example, the speed requirement of EDF can be reduced to 21+p/m+p when it is given p≥0 extra processors. The main result is a new online 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 speedprocessor tradeoff 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/m2). 
Persistent Identifier  http://hdl.handle.net/10722/45606 
ISSN 
DC Field  Value  Language 

dc.contributor.author  Lam, Tak Wah  en_HK 
dc.contributor.author  To, Kar Keung  en_HK 
dc.date.accessioned  20071030T06:30:09Z   
dc.date.available  20071030T06:30:09Z   
dc.date.issued  1999  en_HK 
dc.identifier.citation  Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 1999, p. 623632  en_HK 
dc.identifier.issn  10719040  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/45606   
dc.description.abstract  This paper revisits the problem of online scheduling of sequential jobs with hard deadlines in a preemptive, multiprocessor setting. An online 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 offline sense. It is known that the earliestdeadlinefirst strategy (EDF) is optimal in a oneprocessor setting, and there is no optimal online algorithm in an mprocessor setting where m≥2. Recent work however reveals that if the online 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 tradeoff between increasing the speed and using more processors in deriving optimal online scheduling algorithms. Several upper bound and lower bound results are presented. For example, the speed requirement of EDF can be reduced to 21+p/m+p when it is given p≥0 extra processors. The main result is a new online 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 speedprocessor tradeoff 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/m2).  en_HK 
dc.format.extent  1075547 bytes   
dc.format.extent  4181 bytes   
dc.format.mimetype  application/pdf   
dc.format.mimetype  text/plain   
dc.language  eng  en_HK 
dc.publisher  Society for Industrial and Applied Mathematics.  en_HK 
dc.relation.ispartof  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms  en_HK 
dc.rights  Creative Commons: Attribution 3.0 Hong Kong License   
dc.subject  Mathematics computers  en_HK 
dc.title  Tradeoffs between speed and processor in harddeadline scheduling  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=10719040&volume=&spage=623&epage=631&date=1999&atitle=Tradeoffs+between+speed+and+processor+in+harddeadline+scheduling  en_HK 
dc.identifier.email  Lam, Tak Wah:twlam@cs.hku.hk  en_HK 
dc.identifier.authority  Lam, Tak Wah=rp00135  en_HK 
dc.description.nature  published_or_final_version  en_HK 
dc.identifier.scopus  eid_2s2.00032776989  en_HK 
dc.identifier.hkuros  40755   
dc.identifier.spage  623  en_HK 
dc.identifier.epage  632  en_HK 
dc.identifier.scopusauthorid  Lam, Tak Wah=7202523165  en_HK 
dc.identifier.scopusauthorid  To, Kar Keung=36785812300  en_HK 