Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2486159.2486179 | SPAA |
Keywords | Field | DocType |
new online algorithm sata,flow-time scheduling,non-migratory algorithm,deterministic algorithm,competitive ratio,multi-processor job scheduling,deterministic non-migratory algorithm,competitive tradeoff,flow time,arrival time,multiple processor,job size,competitive analysis | Online algorithm,Mathematical optimization,Upper and lower bounds,Workload,Computer science,Scheduling (computing),Parallel computing,Server,Job scheduler,Deterministic algorithm,Competitive analysis,Distributed computing | Conference |
Citations | PageRank | References |
2 | 0.38 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sze-Hang Chan | 1 | 43 | 3.80 |
| Tak-Wah Lam | 2 | 1860 | 164.96 |
| Lap-Kei Lee | 3 | 406 | 21.59 |
| Jianqiao Zhu | 4 | 4 | 1.09 |