Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Power-aware scheduling for makespan and flow

SpeakerDavid Bunde

The proliferation of mobile computing devices has made power management an important problem. One tool these devices have is the ability to conserve energy by operating more slowly. For example, many modern processors can reduce their clock speed, enabling them to operate at a lower voltage. Similarly, wireless devices can transmit more slowly, enabling them to use a coding scheme with lower rate and reduce their transmission power. Scheduling where the system can save energy by slowing down gives a tradeoff between energy consumption and schedule quality.

In this talk, I will summarize known results and describe offline algorithms for the bicriteria problems of minimizing energy and either makespan or total flow. The main result is a linear-time algorithm for uniprocessor makespan that computes all non-dominated solutions. An extension of that algorithm does the same for multiprocessors running equal-work jobs. The technique also gives an arbitrarily-good approximation for minimizing the total flow of equal-work jobs on a multiprocessor. Finally, I show that it is NP-hard to minimize makespan on a multiprocessor with arbitrary jobs and impossible to exactly minimize total flow on a uniprocessor with equal-work jobs.