Scheduling heterogeneous processors isn't as easy as you think.

Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Kirk Pruhs

Abstract

We consider preemptive online scheduling algorithms to minimize the total weighted/unweighted flow time plus energy for speed-scalable heterogeneous multiprocessors. We show that the well-known priority scheduling algorithms Highest Density First, Weighted Shortest Elapsed Time First, and Weighted Late Arrival Processor Sharing, are not O(1)-speed O(1)-competitive for the objective of weighted flow even in the special case of fixed variable speed processors (aka the related machines setting). This illustrates that scheduling heterogeneous multiprocessors is a different, and algorithmically more challenging problem, than scheduling homogeneous multiprocessors. We then show that a variation of the non-clairvoyant algorithm Late Arrival Processor Sharing coupled with a non-obvious speed scaling algorithm is scalable for the objective of unweighted flow plus energy on speed-scalable multiprocessors. This is the first provably scalable non-clairvoyant algorithm on heterogeneous multiprocessors, even in the related machines setting, for the objective of total (unweighted) flow time.
BibTeX
@inproceedings{gupta2012scheduling,
  author = {Anupam Gupta and Sungjin Im and Ravishankar Krishnaswamy and Benjamin Moseley and Kirk Pruhs},
  title = {{Scheduling heterogeneous processors isn't as easy as you think.}},
  booktitle = {SODA},
  year = {2012},
  doi = {10.1137/1.9781611973099.98},
}

Loading related content...

Figure