Race to Idle: Algorithms for SPeed Scaling with a Sleep State



Susanne Albers, Humboldt-Universitat zu Berlin

Monday, November 26, 2012
4:00pm 5130 Upson Hall



We study algorithmic techniques for energy savings in computer systems. We consider power-down mechanisms that transition an idle system into
low power stand-by or sleep states. Moreover, we address dynamic speed scaling, a relatively recent approach to save energy in modern, variable-speed microprocessors.

In the first part of the talk we survey important results in the area of energy-efficient algorithms. In the second part we investigate a setting where a variable-speed processor is equipped with an additional sleep state. This model integrates speed scaling and power-down mechanisms. We consider classical deadline-based scheduling and settle the complexity
of the offline problem. As the main contribution we present an algorithmic framework that allows us to develop a number of significantly improved constant-factor approximation algorithms.

The talk is based on work with Antonios Antoniadis, which was presented at SODA'12.