System-Level Energy Management for Real-Time Systems

Abstract

Energy management has recently become one of the key dimensions in the design of real-time embedded systems. While early studies focused separately on individual energy management techniques targeting different system components, there is growing interest in system-level energy management frameworks that exploit multiple techniques simultaneously. A primary objective of this dissertation is the integration of two well-known energy management techniques Dynamic Voltage Scaling (DVS) and Dynamic Power Management (DPM). With DVS, the supply voltage and clock frequency of the processor can be scaled down at run-time, to save CPU energy at the expense of increased task response times. On the other hand, DPM targets reducing the energy consumption of idle off-chip system devices such as disk and memory modules, by transitioning them to their low-power sleep states. While effective system-level energy management mandates the use of both DVS and DPM, their integration poses several challenges. For instance, minimizing device energy requires running the processor at high clock frequencies to maximize the length of device idle intervals in order to apply DPM, but minimizing CPU energy involves lowering CPU clock frequencies. This dissertation first illustrates how the DVS and DPM techniques can be integrated optimally for a real-time application potentially using multiple devices during execution. An exact characterization of the system-level energy as a function of the CPU frequency is provided. Using this characterization, an efficient static algorithm is designed to determine the CPU frequency and device transitioning decisions that minimize system-wide energy without violating the timing constraints. Second, the integration of DVS and DPM for real-time applications that consist of multiple periodic tasks is considered. The problem of optimally using DPM for periodic realtime tasks, even in the absence of DVS, is formally shown to be NP-Hard in the strong sense. Then, a novel DPM framework called device forbidden regions is proposed and feasibility tests for both fixed- and dynamic-priority periodic real-time systems are developed. Using this framework as a building block, unified energy management frameworks that efficiently combine DVS and DPM at the system level are proposed. Third, the problem of managing system-wide energy for periodic real-time tasks running on emerging chip-multiprocessor systems with global voltage and frequency constraint is addressed. Contributions made in this area include selecting the number of cores to execute the workload and managing the global frequency at run-time across all cores to reduce dynamic energy while meeting the task deadlines. A final contribution of this dissertation is the competitive analysis of online real-time scheduling problems under a given hard energy constraint. Specifically, worst-case performance bounds that apply to any online algorithm are derived, when compared to an optimal algorithm that has the knowledge of the input sequence in advance. Focusing on uniform value-density preemptive execution settings, optimal online and semi on-line algorithms achieving the best competitive factors are proposed. A number of additional fundamental results are provided for non-uniform value density, non-preemptive, and DVS-enabled execution settings.