File Download
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Trade-offs between speed and processor in hard-deadline scheduling
Title | Trade-offs between speed and processor in hard-deadline scheduling |
---|---|
Authors | |
Keywords | Mathematics computers |
Issue Date | 1999 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | The 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), Baltimore, MD, 17-19 January 1999. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 623-632 How to Cite? |
Abstract | This 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 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 | 2007-10-30T06:30:09Z | - |
dc.date.available | 2007-10-30T06:30:09Z | - |
dc.date.issued | 1999 | en_HK |
dc.identifier.citation | The 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), Baltimore, MD, 17-19 January 1999. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 623-632 | en_HK |
dc.identifier.issn | 1071-9040 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/45606 | - |
dc.description.abstract | This 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.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 Tenth Annual ACM-SIAM Symposium on Discrete Algorithms | en_HK |
dc.rights | © 1999 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms in 1999, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Mathematics computers | en_HK |
dc.title | Trade-offs between speed and processor in hard-deadline scheduling | en_HK |
dc.type | Conference_Paper | 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_2-s2.0-0032776989 | 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 |
dc.identifier.issnl | 1071-9040 | - |