Name
Title | ||
|---|---|---|
SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors |
Abstract | ||
|---|---|---|
We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online non-clairvoyant setting. In this problem, a set of jobs J arrive over time to be scheduled on a set of M machines. Each job j has processing length pj, weight wj, and is processed at a rate of ℓij when scheduled on machine i. The online scheduler knows the values of wj and ℓij upon arrival of the job, but is not aware of the quantity pj. We present the first online algorithm that is scalable ((1 + ϵ)-speed O(1/2)-competitive for any constant ϵ > 0) for the total weighted flow-time objective. No non-trivial results were known for this setting, except for the most basic case of identical machines. Our result resolves a major open problem in online scheduling theory. Moreover, we also show that no job needs more than a logarithmic number of migrations. We further extend our result and give a scalable algorithm for the objective of minimizing total weighted flow-time plus energy cost for the case of unrelated machines. In this problem, each machine can be sped up by a factor of f4-1 i (P) when consuming power P, wherefi is an arbitrary strictly convex power function. In particular, we get an O(γ2)-competitive algorithm when all power functions are of form sγ. These are the first non-trivial non-clairvoyant results in any setting with heterogeneous machines. The key algorithmic idea is to let jobs migrate selfishly until they converge to an equilibrium. Towards this end, we define a game where each job's utility which is closely tied to the instantaneous increase in the objective the job is responsible for, and each machine declares a policy that assigns priorities to jobs based on when they migrate to it, and the execution speeds. This has a spirit similar to coordination mechanisms that attempt to achieve near optimum welfare in the presen- e of selfish agents (jobs). To the best our knowledge, this is the first work that demonstrates the usefulness of ideas from coordination mechanisms and Nash equilibria for designing and analyzing online algorithms. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/FOCS.2014.63 | Foundations of Computer Science |
Keywords | DocType | Volume |
computational complexity,game theory,power aware computing,processor scheduling,Nash equilibria,O(γ2)-competitive algorithm,arbitrary strictly convex consuming power,execution speeds,heterogeneous processors,logarithmic number,migrations,nonclairvoyantly scheduling,online scheduling theory,optimum welfare,scalable algorithm,selfishmigrate,total weighted flow-time plus energy cost,unrelated machines,Flow-time,Online Scheduling,energy,non-clairvoyance | Journal | abs/1404.1943 |
ISSN | Citations | PageRank |
0272-5428 | 13 | 0.67 |
References | Authors | |
14 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sungjin Im | 1 | 353 | 33.73 |
| Janardhan Kulkarni | 2 | 28 | 3.34 |
| Kamesh Munagala | 3 | 1989 | 129.87 |
| Kirk Pruhs | 4 | 13 | 2.03 |