|
|
|
Graduate Course
"Energy Efficient Algorithms"
Summer term 2008
Prof. Dr. Susanne Albers
Sonja Lauer, Tim Nonner
Organization
Lectures
- Monday 11:00 - 13:00 c.t., room 00-010/14, building 101
- Thursday 11:00 - 13:00 c.t., room 00-010/14, building 101
every other week, alternating with exercises
Exercises
- Thursday 11:00 - 13:00 c.t., room 00-010/14, building 101
every other week, alternating with Thursday lecture
Successful participation in the course gives 6 credit points.
Please register via LSF-HIS.
|
News
- April 16, 2008:
Based on the audience, the course will be held in English or German.
- April 14, 2008:
The first lecture is on Monday, April 21.
- July 11, 2008:
No lecture on Monday, July 14.
|
Course description
In many computational environments energy is a scarce and/or expensive resource. In portable
devices such as laptops or mobile phones, the amount of available energy is severely limited. The same holds
true for sensor networks. Furthermore electricity costs impose a substantial strain on the budget of data
and computing centers where servers and, in particular, CPUs account for
50-60 % of the energy consumption.
In this course we will study algorithmic techniques to save energy. There has recently been considerable
research interest in the design and analysis of such strategies. The course will cover scientific results
developed in the algorithms community over the past five years and concentrates, in particular, on the
following topics.
- Power-down strategies
- Energy-efficient network design
- Data aggregation in networks
- Dynamic speed scaling
- Energy-efficient broadcast
|
Assignments
Every other week, a new exercise sheet will be published here. The solutions are to be handed in during the lecture. You will get the corrected papers back in the exercises.
| |
Exerice Sheets |
Release |
Hand in by |
| |
Assignment 1 |
April 28, 2008 |
May 19, 2008 |
| |
Assignment 2 |
May 19, 2008 |
June 2, 2008 |
| |
Assignment 3 |
June 2, 2008 |
June 16, 2008 |
| |
idleperiods |
|
|
| |
Assignment 4 |
June 2, 2008 |
June 16, 2008 |
| |
Assignment 5 |
June 30, 2008 |
July 14, 2008 |
| |
network.txt |
|
|
|
Literature
This is a completely new course on a research topic of current interest, and no textbooks are
available. Therefore, the lectures are based on research papers. Selected reading:
-
J. Augustine, S. Irani and C. Swamy. Optimal power-down strategies. Proc. 45th
Annual IEEE Symposium on Foundations of Computer Science, 530-539, 2004.
- N. Bansal, T. Kimbrel and K. Pruhs. Dynamic speed scaling to manage energy and
temperature. Proc. 45th Annual IEEE Symposium on Foundations of Computer Science,
520-529, 2004.
- P. Baptiste. Scheduling unit tasks to minimize the number of idle periods: A polynomial
time algorithm for offline dynamic power management. Proc. 17th Annual ACM-SIAM
Symposium on Discrete Algorithms, 364-367, 2006.
- N. Bansal and K. Pruhs. Speed scaling to manage temperature.
Proc. 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS),
Springer LNCS 3404, 460--471, 2005.
- S. Irani, R. Gupta and S. Shukla. Competititve analysis of dynamic power management strategies
for systems with multiple power savings states. Proc. IEEE Conference on Design, Automation and Test in Europe, 2002.
- S. Irani, S. Shukla and R. Gupta. Algorithms for power savings.
Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 37-46, 2003.
- K. Pruhs, P. Uthaisombut and G. Woeginger. Getting the best response for your erg.
Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT), Springer LNCS 3111, 15-25, 2004.
- F. Yao, A. Demers and S. Shenker. A scheduling model for reduced
CPU energy. Proc. 36th Annual Symposium on Foundations of Computer Science, 374-382, 1995.
|
|
