Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Speed Scaling for Energy Aware Processor Scheduling: Algorithms and Analysis

Cole, Daniel (2013) Speed Scaling for Energy Aware Processor Scheduling: Algorithms and Analysis. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Primary Text

Download (986kB) | Preview


We present theoretical algorithmic research of processor scheduling in an energy aware environment using the mechanism of speed scaling. We have two main goals in mind. The first is the development of algorithms 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, we give an online scheduling algorithm that, for any input, produces a schedule with integer stretch plus energy that is competitive with the integer stretch plus energy of any schedule that finishes all jobs.

Second, we consider the problem of finding the schedule, S, that minimizes some quality of service objective Q plus B 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 B. When Q is fractional weighted flow, 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 can be computed with 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 show that it has a competitive ratio that is an order of magnitude better than the best previously known for this problem.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Cole, Danieldcc20@pitt.eduDCC20
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairPruhs, Kirkkirk@cs.pitt.eduKRP2
Committee MemberMelhem, Ramimelhem@cs.pitt.eduMELHEM
Committee MemberChilders, Brucechilders@cs.pitt.eduCHILDERS
Committee MemberGupta,
Date: 30 June 2013
Date Type: Publication
Defense Date: 2 April 2013
Approval Date: 30 June 2013
Submission Date: 18 April 2013
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Number of Pages: 91
Institution: University of Pittsburgh
Schools and Programs: Dietrich School of Arts and Sciences > Computer Science
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: algorithms, scheduling, energy
Date Deposited: 30 Jun 2013 18:39
Last Modified: 15 Nov 2016 14:11


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item