Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to Cilk

We study the problem of executing parallel programs, in particular Cilk programs, on a collection of processors of different speeds. We consider a model in which each processor maintains an estimate of its own speed, where communication between processors has a cost, and where all scheduling must be online. This problem has been considered previously in the fields of asynchronous parallel computing and scheduling theory. Our model is a bridge between the assumptions in these fields. We provide a new more accurate analysis of an old scheduling algorithm called the maximum utilization scheduler . Based on this analysis, we generalize this scheduling policy and define the high utilization scheduler . We next focus on the Cilk platform and introduce a new algorithm for scheduling Cilk multithreaded parallel programs on heterogeneous processors. This scheduler is inspired by the high utilization scheduler and is modified to fit in a Cilk context. A crucial aspect of our algorithm is that it keeps the original spirit of the Cilk scheduler. In fact, when our new algorithm runs on homogeneous processors, it exactly mimics the dynamics of the original Cilk scheduler.

Authors and Affiliations

1. Department of Computer Science, State University of New York, bender@cs.sunysb.edu, Stony Brook, NY 11794-4400, USA, USA

   Michael A. Bender

2. Division of Engineering and Applied Sciences, Harvard University, rabin@deas.harvard.edu, Cambridge, MA 02138, USA, USA

   Michael O. Rabin

Reprints and permissions