An Algorithmic Study on Energy-Minimizing Coherent Speed Scaling

In this thesis, we consider a model of multi-core job scheduling aimed at minimizing the energy consumption of the processors. In this model, schedules with coherent speed scaling are assumed, which means that the speed of the processors can be adjusted as often as needed under the constraint that the speed of all processors must be identical at any time. The energy consumed per unit of time is a convex function of the processing speed. A feasible schedule requires that each job be executed between its arrival time and deadline on a processor to which the job is pre-assigned, possibly with preemption but without migration. This model originates from the scenario of “voltage-islands” in a many-core system where there are multiprocessors, and the processors are clustered into islands such that the processors in an island are powered using a common voltage line, thereby restricting the processing speeds of the processors in the island. We study this model with coherent speed scaling and compute the speeds of the processors in each island such that the energy consumed is to be minimized.