Optimal Dynamic Voltage Scaling in Energy-Limited Nonpreemptive Systems with Real-Time Constraints

Dynamic voltage scaling is used in energy-limited systems as a means of conserving energy and prolonging their life. We consider a setting in which the tasks performed by such a system are nonpreemptive and aperiodic. Our objective is to control the processing rate over different tasks so as to minimize energy subject to hard real-time processing constraints. Under any given task scheduling policy, we prove that the optimal solution to the offline version of the problem can be efficiently obtained by exploiting the structure of optimal sample paths, leading to a new dynamic voltage scaling algorithm termed the critical task decomposition algorithm (CTDA). The efficiency of the algorithm rests on the existence of a set of critical tasks that decompose the optimal sample path into decoupled segments within which optimal processing times are easily determined. The algorithm is readily extended to an online version of the problem as well. Its worst-case complexity of both offline and online problems is O(N²)