TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 20.06.2013

isti-logo

Page Content

to Navigation

Optimal Energy Trade-off Schedules

Professor Kirk Pruhs (University of Pittsburgh)

I will start by giving a brief overview of the state of the art on research on energy as a computational resource, highlighting the physical reasons why energy as a computational resource is so different than the traditional computational resources of time and space. In particular, there doesn't appear that there will be energy equivalent of our beloved time and space complexity classes.

Then as an example of what the research on energy as a computational resource looks like, we consider scheduling tasks that arrive over time on a speed scalable processor. At each time a schedule specifies a job to be run and the speed at which the processor is run. Processors are generally less energy efficient at higher speeds. We seek to understand the structure of schedules that optimally trade-off the energy used by the processor with a common scheduling quality of service measure,
fractional weighted delay. We assume that there is some user defined parameter beta specifying the user's desired additive trade-off between energy efficiency and quality of service. We prove that the optimal energy trade-off schedule is essentially unique, and has a simple structure. Thus it is easy to check the optimality of a schedule. We further prove that the optimal energy trade-off schedule changes continuously as a function of the parameter beta. Thus it is possible to compute the optimal energy trade-off schedule using a natural homotopic optimization algorithm. We further show that multiplicative trade-off schedules have fewer desirable properties.  I will try to highlight several intriguing open problems exposed by this research.

(joint work with Neal Barcelo, Daniel Cole, Dimitrios Letsios, Michael Nugent)

Date
Speaker
Location
Language
20.06.2013 16:15
Kirk Pruhs
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe