File Download
Supplementary
-
Citations:
- Appears in Collections:
Conference Paper: Nonclairvoyant sleep management and flow-time scheduling on multiple processors
Title | Nonclairvoyant sleep management and flow-time scheduling on multiple processors |
---|---|
Authors | |
Keywords | Online scheduling Competitive analysis Sleep management Flow time Job migration |
Issue Date | 2013 |
Publisher | Association for Computing Machinery (ACM). |
Citation | The 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '13), Montreal, QC., 23-25 July 2013. In Conference Proceedings, 2013, p. 261-270 How to Cite? |
Abstract | In large data centers, managing the availability of servers is often non-trivial, especially when the workload is unpredictable. Using too many servers would waste energy, while using too few would affect the performance. A recent theoretical study, which assumes the clairvoyant model where job size is known at arrival time, has successfully integrated sleep-and-wakeup management into multi-processor job scheduling and obtained a competitive tradeoff between flow time and energy [6]. This paper extends the study to the nonclairvoyant model where the size of a job is not known until the job is finished. We give a new online algorithm SATA which is, for any ε > 0, (1 + ε)-speed O( 1⁄ε2 )-competitive for the objective of minimizing the sum of flow time and energy.
SATA also gives a new nonclairvoyant result for the classic setting where all processors are always on and the concern is flow time only. In this case, the previous work of Chekuri et al. [7] and Chadha et al. [8] has revealed that random dispatching can give a non-migratory algorithm that is (1 + ε)-speed O( 1⁄ε3 )-competitive, and any deterministic non-migratory algorithm is Ω(m⁄s)-competitive using s-speed processors [7], where m is the number of processors. SATA, which is a deterministic algorithm migrating each job at most four times on average, has a competitive ratio of O(1⁄ε2). The number of migrations used by SATA is optimal up to a constant factor as we can extend the above lower bound result. |
Persistent Identifier | http://hdl.handle.net/10722/189626 |
ISBN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, SH | en_US |
dc.contributor.author | Lam, TW | en_US |
dc.contributor.author | Lee, LK | en_US |
dc.contributor.author | Zhu, J | en_US |
dc.date.accessioned | 2013-09-17T14:50:23Z | - |
dc.date.available | 2013-09-17T14:50:23Z | - |
dc.date.issued | 2013 | en_US |
dc.identifier.citation | The 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '13), Montreal, QC., 23-25 July 2013. In Conference Proceedings, 2013, p. 261-270 | en_US |
dc.identifier.isbn | 978-1-4503-1572-2 | - |
dc.identifier.uri | http://hdl.handle.net/10722/189626 | - |
dc.description.abstract | In large data centers, managing the availability of servers is often non-trivial, especially when the workload is unpredictable. Using too many servers would waste energy, while using too few would affect the performance. A recent theoretical study, which assumes the clairvoyant model where job size is known at arrival time, has successfully integrated sleep-and-wakeup management into multi-processor job scheduling and obtained a competitive tradeoff between flow time and energy [6]. This paper extends the study to the nonclairvoyant model where the size of a job is not known until the job is finished. We give a new online algorithm SATA which is, for any ε > 0, (1 + ε)-speed O( 1⁄ε2 )-competitive for the objective of minimizing the sum of flow time and energy. SATA also gives a new nonclairvoyant result for the classic setting where all processors are always on and the concern is flow time only. In this case, the previous work of Chekuri et al. [7] and Chadha et al. [8] has revealed that random dispatching can give a non-migratory algorithm that is (1 + ε)-speed O( 1⁄ε3 )-competitive, and any deterministic non-migratory algorithm is Ω(m⁄s)-competitive using s-speed processors [7], where m is the number of processors. SATA, which is a deterministic algorithm migrating each job at most four times on average, has a competitive ratio of O(1⁄ε2). The number of migrations used by SATA is optimal up to a constant factor as we can extend the above lower bound result. | - |
dc.language | eng | en_US |
dc.publisher | Association for Computing Machinery (ACM). | - |
dc.relation.ispartof | Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures | en_US |
dc.subject | Online scheduling | - |
dc.subject | Competitive analysis | - |
dc.subject | Sleep management | - |
dc.subject | Flow time | - |
dc.subject | Job migration | - |
dc.title | Nonclairvoyant sleep management and flow-time scheduling on multiple processors | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Chan, SH: shchan@cs.hku.hk | en_US |
dc.identifier.email | Lam, TW: hresltk@hkucc.hku.hk | en_US |
dc.identifier.email | Lee, LK: lklee@cs.hku.hk | - |
dc.identifier.email | Zhu, J: jianqiao@cs.wisc.edu | - |
dc.identifier.authority | Lam, TW=rp00135 | en_US |
dc.identifier.authority | Lee, LK=rp00140 | en_US |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1145/2486159.2486179 | - |
dc.identifier.hkuros | 222163 | en_US |
dc.identifier.spage | 261 | en_US |
dc.identifier.epage | 270 | en_US |
dc.publisher.place | United States | - |
dc.customcontrol.immutable | sml 131122 | - |