The Power to Schedule a Parallel Program
Kunal Agrawal, Seth Lewis Gilbert · 2018
In this paper, we consider the problem of scheduling parallel programs on a multicore or multiprocessor machine so as to minimize the energy consumed. By adjusting the number of active processors and/or the speed of those processors, we can vary the amount of power used by the computation. We consider two versions of the problem: minimizing the running time given a power constraint, and minimizing the energy used given a time constraint. We consider the problem in the non-clairvoyant setting where the scheduler does not know anything about the program in advance, but has the flexibility to adjust the number of active processors and their speed as the program executes. We present a work-stealing algorithm that relies on a backoff-backon strategy to solve both of these problems, even while only adjusting the number of active processors and their speed a limited number of times. We show that our solution is competitive with the best static clairvoyant solution - here the scheduler knows the structure of the program in advance, but must choose the number of active processors and their speed in advance and can not change it while the program executes. Thus we conclude that with only a small number of adjustments, we can compensate for the lack of information about the future of the computation.