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

Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott

This paper, titled "A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State," tackles a fundamental problem in green computing: how to schedule tasks to minimize energy consumption when your processor can both change its speed and go to sleep.

TL;DR

The authors present the first Fully Polynomial-Time Approximation Scheme (FPTAS) for the "speed scaling with sleep state" problem. This result settles a long-standing open question by proving that we can find a schedule within a factor of $(1 + \epsilon)$ of the optimal energy consumption in time polynomial to the number of tasks and $1/\epsilon$.

What Problem Does This Paper Address?

In modern computing, energy efficiency is a balancing act. Processors use two main tricks to save power:

  1. Dynamic Speed Scaling: Slowing down the processor to reduce power (usually proportional to the cube of the speed).
  2. Sleep States: Turning the processor off entirely when idle. However, waking up costs a fixed amount of energy ($C$).

This creates a "race to idle" dilemma. Sometimes it is more energy-efficient to run a task faster than necessary (consuming more instantaneous power) so the processor can enter a sleep state sooner and stay there longer.

While the standard speed-scaling problem (without sleep) was solved in the 90s by the famous YDS algorithm, adding a sleep state makes the problem significantly harder. Before this paper, the gap between the known NP-hardness and the best approximation algorithm (a 4/3-approximation) remained a major open question in the scheduling community.

Methods

The authors bridge this gap using a sophisticated discretization approach combined with Dynamic Programming (DP). Their method involves several key steps:

  • Preemptive to Non-Preemptive Transformation: They transform the original problem (where tasks can be interrupted) into a non-preemptive variant. They do this by breaking each task into a polynomial number of tiny "pieces."
  • Time Discretization: Since time is continuous, there are infinite possible schedules. The authors define a specific set of "time points" ($W$) based on a geometric series and an error parameter $\delta$. They prove that there exists a "near-optimal" schedule where every task piece starts and ends only at these specific points.
  • Lexicographical Ordering: To handle the complexities of preemption, they define a strict ordering for how pieces should be processed. This ensures that the DP doesn't "lose" the flexibility that preemption originally provided.
  • Dynamic Programming: They design a DP table $E_k(\tau_1, \tau_2)$ that calculates the minimum energy required to process a subset of job pieces within a specific time interval $[\tau_1, \tau_2]$.

Datasets

Not discussed in the paper. As a theoretical computer science paper, the work focuses on mathematical proofs and algorithmic complexity analysis rather than empirical testing on specific datasets.

Key Insights and Ideas

  • The Critical Speed ($s_{crit}$): The authors utilize the concept of "critical speed"—the most efficient speed for processing. If you run slower than this, the "leakage" power of being active outweighs the savings of a lower speed.
  • Discretization without much Loss: The "aha moment" is the proof that by choosing $O(poly(n, 1/\epsilon))$ time points, you only increase the total energy consumption by a factor of $(1 + \epsilon)$. This turns an infinite search space into a finite, manageable one.
  • Well-Ordered Schedules: By forcing the DP to produce "well-ordered" schedules, the authors ensure that the resulting non-preemptive schedule for job pieces behaves like an optimal preemptive schedule for the original jobs.

Key Results

  • Existence of an FPTAS: The paper proves that for any $\epsilon > 0$, a schedule with energy consumption at most $(1 + \epsilon) \cdot OPT$ can be found in polynomial time.
  • Complexity Settlement: This result effectively "closes" the problem's complexity. Since the problem is NP-hard, an FPTAS is the best theoretical result one can hope for (short of $P=NP$).
  • Speed Bound: The authors show that their discretized schedule runs at a speed at most $(1 + \delta)^3$ times the optimal speed, which is then used to bound the total energy increase.

Limitations and Future Work

  • Single Processor Constraint: The current FPTAS is designed for a single-processor environment. While the authors mention that related work has touched on multiprocessor settings, a general FPTAS for multiple processors with sleep states remains a more complex challenge.
  • Computational Constants: While the algorithm is "polynomial," FPTAS designs often involve high-degree polynomials. The paper focuses on the existence of the polynomial bound rather than optimizing the algorithm for real-world, sub-second execution on large task sets.
  • Power Function Assumptions: The proof relies on the power function $P(s)$ being convex and non-negative, which fits most theoretical models but may need adjustment for specific hardware quirks.

Summary updated

Abstract

We study classical deadline-based preemptive scheduling of jobs in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each job 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 jobs 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. (ACM Trans Algorithms 3(4), 2007), its exact computational complexity has been repeatedly posed as an open question (see e.g. Albers and Antoniadis in ACM Trans Algorithms 10(2):9, 2014; Baptiste et al. in ACM Trans Algorithms 8(3):26, 2012; Irani and Pruhs in SIGACT News 36(2):63–76, 2005). The currently best known upper and lower bounds are a 4 / 3-approximation algorithm and NP-hardness due to Albers and Antoniadis (2014) and Kumar and Shannigrahi (CoRR, 2013. arXiv:1304.7373 ), 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},
}

Loading related content...

Figure