A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State

Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott

Introduction

Energy efficiency is a cornerstone of modern green computing. To minimize energy consumption, processors typically employ two primary mechanisms: Dynamic Speed Scaling, where the processor's speed is adjusted (often reducing power consumption cubically with speed), and Sleep States, where the processor is turned off during idle periods. However, transitioning from a sleep state back to an active state incurs a fixed energy cost $C$.

This creates a "race to idle" dilemma: is it better to run a task slowly to minimize instantaneous power, or to run it faster to enter a sleep state sooner? While the standard speed-scaling problem (without sleep states) was solved by the YDS algorithm in the 1990s, the addition of a sleep state makes the problem NP-hard. This paper presents the first Fully Polynomial-Time Approximation Scheme (FPTAS) for this problem, settling a long-standing open question.

Problem Formulation

The "speed scaling with sleep state" problem involves scheduling a set of tasks, each with a release time, deadline, and work requirement, on a single processor. The goal is to minimize total energy, which is the sum of power integrated over time plus the wake-up costs. The power function $P(s)$ is assumed to be convex and non-negative. A critical concept is the critical speed ($s_{crit}$), the speed at which the energy per unit of work is minimized when accounting for leakage power.

The FPTAS Algorithm

The authors bridge the gap between NP-hardness and approximation by developing an FPTAS that finds a schedule within a factor of $(1 + \epsilon)$ of the optimal energy consumption in time polynomial to the number of tasks $n$ and $1/\epsilon$. The algorithm relies on three main pillars:

1. Preemptive to Non-Preemptive Transformation

The original problem allows tasks to be preempted. The authors transform this into a non-preemptive variant by subdividing each task into a polynomial number of infinitesimal "pieces."

2. Time Discretization

Because time is continuous, the search space for optimal start and end times is infinite. The authors define a discrete set of "time points" $W$ based on a geometric series and an error parameter $\delta$. They prove that a near-optimal schedule exists where every task piece begins and ends only at these specific points.

Discretization of time intervals into a finite set of candidate points for scheduling.

3. Dynamic Programming and Lexicographical Ordering

To manage the complexity of scheduling these pieces, the authors introduce a strict lexicographical ordering. This ensures that the dynamic programming (DP) approach can efficiently explore the schedule space without losing the flexibility of the original preemptive model. The DP table $E_k(\tau_1, \tau_2)$ calculates the minimum energy required to process a subset of job pieces within a specific time interval $[\tau_1, \tau_2]$.

Key Results

The primary contribution of this work is the proof of the existence of an FPTAS. By choosing $O(poly(n, 1/\epsilon))$ time points, the total energy consumption increases by at most a factor of $(1 + \epsilon)$. This result effectively "closes" the theoretical complexity of the problem, as an FPTAS is the strongest approximation result possible for an NP-hard problem (assuming $P \neq NP$). Additionally, the authors demonstrate that their discretized schedule maintains a speed bound, running at most $(1 + \delta)^3$ times the optimal speed.

Conclusion and Future Work

While this FPTAS provides a definitive theoretical solution for single-processor environments, several avenues for future research remain. The current algorithm is optimized for theoretical bounds rather than real-world execution speed, as FPTAS designs often involve high-degree polynomials. Furthermore, extending these results to multiprocessor environments presents a significantly more complex challenge. Finally, while the convex power function $P(s)$ is standard in literature, future work could explore more complex hardware-specific power models.

Summary updated

Abstract

We study classical deadline-based preemptive scheduling of tasks in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each task is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed scaling alone, the addition of a sleep state makes it sometimes beneficial to accelerate the processing of tasks in order to transition the processor to the sleep state for longer amounts of time and incur further energy savings. The goal is to output a feasible schedule that minimizes the energy consumption. Since the introduction of the problem by Irani et al. [16], its exact computational complexity has been repeatedly posed as an open question (see e.g. [2,8,15]). The currently best known upper and lower bounds are a 4/3-approximation algorithm and NP-hardness due to [2] and [2,17], respectively. We close the aforementioned gap between the upper and lower bound on the computational complexity of speed scaling with sleep state by presenting a fully polynomial-time approximation scheme for the problem. The scheme is based on a transformation to a non-preemptive variant of the problem, and a discretization that exploits a carefully defined lexicographical ordering among schedules.
BibTeX
@inproceedings{antoniadis2015fully,
  author = {Antonios Antoniadis and Chien-Chung Huang and Sebastian Ott},
  title = {{A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State}},
  booktitle = {SODA},
  year = {2015},
  doi = {10.1137/1.9781611973730.74},
}
Figure