Barcelo, Neal
(2015)
The Complexity of Speed-Scaling.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
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.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| 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 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/25280 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[img]](https://d-scholarship.pitt.edu/style/images/fileicons/application_pdf.png)
![[feed]](/images/feed-icon-32x32.png){kind=icon}