Scheduling Heterogeneous Processors Isn’t As Easy As You Think

Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley and 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 -speed -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 speedscalable 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.  


Guest: Kirk Pruhs
Host: Zvi Lotker

Leave a Reply

Your email address will not be published.

165,457 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>