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.
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