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

The Complexity of Speed-Scaling

Barcelo, Neal (2015) The Complexity of Speed-Scaling. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Accepted Version

Download (1MB)


It seems to be a corollary to the laws of physics that, all else being equal, higher performance devices are necessarily less energy efficient than lower performance devices. Conceptually there is an energy efficiency spectrum of design points, with high performance and low energy efficiency on one end, and low performance and high energy efficiency on the other end. As in most technologies, there is not a universal sweet spot for computer chips that is best for all situations. For example, there are situations when there are critical tasks to be done, when performance is more important than energy efficiency, and there are situations when there are no critical tasks, when energy efficiency may be more important than performance. Speed-scalable processors aim to resolve this conflict by allowing the operating system to dynamically choose the performance to energy trade-off.
The resulting optimization problems involve scheduling jobs on such a processor and have conflicting dual objectives of quality of service and some energy related objective. This engenders many different optimization problems, depending on how one models the processor, the performance objective, and how one handles the dual objectives.

In this thesis we map out a reasonably full landscape of all possible formulations, determining which assumptions drive computational tractability. Beyond identifying the individual computational complexities, we use algorithmics as a lens to study the combinatorial structure of such trade-off schedules. In particular, we give several general reductions which, in some sense, reduce the number of problems that are distinct in a complexity theoretic sense. We show that some problems, for which there are efficient algorithms on a fixed speed processor, are NP-hard. Finally, we present several primal-dual based polynomial time algorithms.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Barcelo, Nealncb30@cs.pitt.eduNCB30
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairPruhs, Kirkkirk@cs.pitt.eduKRP2
Committee MemberLee, Adamadamlee@cs.pitt.eduADAMLEE
Committee MemberMosse, MOSSE
Committee MemberGupta,
Date: 10 September 2015
Date Type: Publication
Defense Date: 29 April 2015
Approval Date: 10 September 2015
Submission Date: 27 May 2015
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Number of Pages: 143
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: Energy,Scheduling,Complexity
Date Deposited: 10 Sep 2015 15:06
Last Modified: 19 Dec 2016 14:42


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item