PhD Proposal

Speed Scaling for Energy Aware Processor Scheduling: Algorithms and Analysis

Daniel Cole

Tuesday July 3, 2012
12:00 pm - Sennott Square 6106 - Eli Lilly Room

Abstract

We propose theoretical algorithmic research of processor scheduling in an energy aware environment when the mechanism for energy control is speed scaling. We have two main goals in mind. The first is the development of algorithms, via a mathematical approach, that allow more energy efficient utilization of resources. The second goal is to further our ability to reason abstractly about energy in computing devices by developing and understanding algorithmic models of energy management. In order to achieve these goals, we investigate three classic process scheduling problems in the setting of a speed scalable processor.

Integer stretch is one of the most obvious classical scheduling objectives that has yet to be considered in the speed scaling setting. For the objective of integer stretch plus energy, under arbitrary power functions, we propose an online scheduling algorithm, that, for any input, produces a schedule with integer stretch plus energy that is at most 9.5 times the integer stretch plus energy of any schedule that finishes all jobs.

Second, we consider an optimization problem where the objective is to find a schedule S that minimizes some quality of service objective Q plus ß times the energy used by the processor. This schedule, S, is the optimal energy trade-off schedule in the sense that: no schedule can have better quality of service given the current investment of energy used by S, and an additional investment of one unit of energy is insufficient to improve the quality of service by more than ß. When Q is fractional weighted flow, jobs have arbitrary weights and sizes, and the power function is essentially arbitrary, we show that the optimal energy trade-off schedule is unique and has a simple structure, thus making it easy to check the optimality of a schedule. We further show that the optimal energy trade-off schedule changes continuously as a function of the parameter ß. This allows the optimal energy trade-off schedule to be computed using a natural homotopic optimization algorithm.

Lastly, we consider the speed scaling problem where the quality of service objective is deadline feasibility and the power objective is temperature. In the case of batched jobs, we give a simple algorithm to compute the optimal schedule. For general instances, we give a new online algorithm, and obtain an upper bound on the competitive ratio of this algorithm that is an order of magnitude better than the best previously known bound upper bound on the competitive ratio for this problem.

Dissertation Adviser

Dr. Kirk Pruhs, Department of Computer Science

Committee Members

Dr. Bruce Childers, Department of Computer Science
Dr. Rami Melhem, Department of Computer Science
Dr. Anupam Gupta, Department of Computer Science, Carnegie Mellon University