TY - GEN

T1 - Scheduling heterogeneous processors isn't as easy as you think

AU - Gupta, Anupam

AU - Im, Sungjin

AU - Krishnaswamy, Ravishankar

AU - Moseley, Benjamin

AU - Pruhs, Kirk

PY - 2012

Y1 - 2012

N2 - 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 multi-processors, even in the related machines setting, for the objective of total (unweighted) flow time.

AB - 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 multi-processors, even in the related machines setting, for the objective of total (unweighted) flow time.

UR - http://www.scopus.com/inward/record.url?scp=84860153714&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860153714&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.98

DO - 10.1137/1.9781611973099.98

M3 - Conference contribution

AN - SCOPUS:84860153714

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1242

EP - 1253

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -