Scheduling cilk multithreaded parallel programs on processors of different speeds

We study the problem of executing parallel programs, in particular Cilk programs, on a collection of processors of dif-ferent speeds. We consider a model in which each processor maintains an estimate of its own speed, where communica-tion between processors has a cost, and where all scheduling must be online. This problem has been considered previ-ously in the elds of asynchronous parallel computing and scheduling theory. Our model is a bridge between the as-sumptions in these elds. 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 dene the high utilization sched-uler. We next focus on the Cilk platform and introduce a new algorithm for scheduling Cilk multithreaded parallel programs on heterogeneous processors. This scheduler is in-spired by the high utilization scheduler and is modied to t 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. 1