A survey of offline algorithms for energy minimization under deadline constraints
---
paper_title: Energy-efficient algorithms

paper_content:

Algorithmic solutions can help reduce energy consumption in computing environs.
---
paper_title: Reducing Peak Power Consumption inMulti-Core Systems without ViolatingReal-Time Constraints

paper_content:

The potential of multi-core chips for high performance and reliability at low cost has made them ideal computing platforms for embedded real-time systems. As a result, power management of a multi-core chip has become an important issue in the design of embedded real-time systems. Most existing approaches have been designed to regulate the behavior of average power consumption, such as minimizing the total energy consumption or the chip temperature. However, little attention has been paid to the worst-case behavior of instantaneous power consumption on a chip, called chip-level peak power consumption, an important design parameter that determines the cost and/or size of chip design/packaging and the underlying power supply. We address this problem by reducing the chip-level peak power consumption at design time without violating any real-time constraints. We achieve this by carefully scheduling real-time tasks, without relying on any additional hardware implementation for power management, such as dynamic voltage and frequency scaling. Specifically, we propose a new scheduling algorithm FPΘ that restricts the concurrent execution of tasks assigned on different cores, and perform its schedulability analysis. Using this analysis, we develop a method that finds a set of concurrent executable tasks, such that the design-time chip-level peak power consumption is minimized and all timing requirements are met. We demonstrate via simulation that the proposed method not only keeps the design-time chip-level peak power consumption as low as the theoretical lower bound for trivial cases, but also reduces the peak power consumption for non-trivial cases by up to 12.9 percent compared to the case of no restriction on concurrent task execution.
---
paper_title: Survey of Energy-Cognizant Scheduling Techniques

paper_content:

Execution time is no longer the only metric by which computational systems are judged. In fact, explicitly sacrificing raw performance in exchange for energy savings is becoming a common trend in environments ranging from large server farms attempting to minimize cooling costs to mobile devices trying to prolong battery life. Hardware designers, well aware of these trends, include capabilities like DVFS (to throttle core frequency) into almost all modern systems. However, hardware capabilities on their own are insufficient and must be paired with other logic to decide if, when, and by how much to apply energy-minimizing techniques while still meeting performance goals. One obvious choice is to place this logic into the OS scheduler. This choice is particularly attractive due to the relative simplicity, low cost, and low risk associated with modifying only the scheduler part of the OS. Herein we survey the vast field of research on energy-cognizant schedulers. We discuss scheduling techniques to perform energy-efficient computation. We further explore how the energy-cognizant scheduler's role has been extended beyond simple energy minimization to also include related issues like the avoidance of negative thermal effects as well as addressing asymmetric multicore architectures.
---
paper_title: Peak power reduction and workload balancing by space-time multiplexing based demand-supply matching for 3D thousand-core microprocessor

paper_content:

Space-time multiplexing is utilized for demand-supply matching between many-core microprocessors and power converters. Adaptive clustering is developed to classify cores by similar power level in space and similar power behavior in time. In each power management cycle, minimum number of power converters are allocated for space-time multiplexed matching, which is physically enabled by 3D through-silicon-vias. Moreover, demand-response based task adjustment is applied to reduce peak power and to balance workload. The proposed power management system is verified by system models with physical design parameters and benched power traces, which show 38.10% peak power reduction and 2.60x balanced workload.
---
paper_title: Power-aware scheduling for makespan and flow

paper_content:

We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work.For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by Pruhs et al. to give an arbitrarilygood approximation for scheduling equal-work jobs on a multiprocessor.
---
paper_title: Accurate Modeling of the Delay and Energy Overhead of Dynamic Voltage and Frequency Scaling in Modern Microprocessors

paper_content:

Dynamic voltage and frequency scaling (DVFS) has been studied for well over a decade. Nevertheless, existing DVFS transition overhead models suffer from significant inaccuracies; for example, by incorrectly accounting for the effect of DC–DC converters, frequency synthesizers, voltage, and frequency change policies on energy losses incurred during mode transitions. Incorrect and/or inaccurate DVFS transition overhead models prevent one from determining the precise break-even time and thus forfeit some of the energy saving that is ideally achievable. This paper introduces accurate DVFS transition overhead models for both energy consumption and delay. In particular, we redefine the DVFS transition overhead including the underclocking-related losses in a DVFS-enabled microprocessor, additional inductor IR losses, and power losses due to discontinuous-mode DC–DC conversion. We report the transition overheads for a desktop, a mobile and a low-power representative processor. We also present DVFS transition overhead macromodel for use by high-level DVFS schedulers.
---
paper_title: A time series-based approach for power management in mobile processors and disks

paper_content:

In this paper, we present a time series-based approach for managing power in mobile processors and disks that see multimedia workloads. Since multimedia applications impose soft real-time constraints, a key goal of our approach is to reduce energy consumption of multimedia applications without degrading performance. We present simple statistical techniques based on time series to dynamically compute the processor and I/O demands of multimedia applications and present techniques to dynamically vary the voltage settings and rotational speeds of mobile processors and disks, respectively. We implement our approaches in the Linux kernel running on a Sony Transmeta laptop and in a trace-driven simulator. Our experiments show that, compared to the traditional system-wide CPU voltage scaling approaches, our technique can achieve up to a 38.6% energy saving while delivering good performance to applications. Simulation results for our disk power management technique show a 20.3% reduction in energy consumption without any significant performance loss when compared to a traditional disk power management scheme.
---
paper_title: Using dynamic voltage scaling for energy-efficient flash-based storage devices

paper_content:

NAND flash memory is commonly known as a power-efficient storage medium. Because of the increasing complexity of flash-based storage devices, however, it is more difficult to achieve good power-efficiency without considering an energy-efficient storage device design. In this paper, we investigate the potential benefit of dynamic voltage/frequency scaling (DVFS) on the energy-efficiency of flash-based storage devices. We first develop a performance/power model for a flash device by using an FPGA-based flash device platform. We then propose a simple DVFS heuristic algorithm that exploits workload fluctuations of a flash device to achieve a significant reduction in energy consumption without performance degradation. Experimental results show that a flash device with DVFS can reduce energy consumption by up to 20%-30%.
---
paper_title: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

paper_content:

The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
---
paper_title: Energy-efficient algorithms

paper_content:

Algorithmic solutions can help reduce energy consumption in computing environs.
---
paper_title: Energy-Efficient Scheduling for Real-Time Systems on Dynamic Voltage Scaling (DVS) Platforms

paper_content:

Energy-efficient designs have played import roles for hardware and software implementations for a decade. With the advanced technology of VLSI circuit designs, energy-efficiency can be achieved by adopting the dynamic voltage scaling (DVS) technique. In this paper, we survey the studies for energy-efficient scheduling in real-time systems on DVS platforms to cover both theoretical and practical issues.
---
paper_title: Algorithmic problems in power management

paper_content:

We survey recent research that has appeared in the theoretical computer science literature on algorithmic problems related to power management. We will try to highlight some open problem that we feel are interesting. This survey places more concentration on lines of research of the authors: managing power using the techniques of speed scaling and power-down which are also currently the dominant techniques in practice.
---
paper_title: Survey of Energy-Cognizant Scheduling Techniques

paper_content:

Execution time is no longer the only metric by which computational systems are judged. In fact, explicitly sacrificing raw performance in exchange for energy savings is becoming a common trend in environments ranging from large server farms attempting to minimize cooling costs to mobile devices trying to prolong battery life. Hardware designers, well aware of these trends, include capabilities like DVFS (to throttle core frequency) into almost all modern systems. However, hardware capabilities on their own are insufficient and must be paired with other logic to decide if, when, and by how much to apply energy-minimizing techniques while still meeting performance goals. One obvious choice is to place this logic into the OS scheduler. This choice is particularly attractive due to the relative simplicity, low cost, and low risk associated with modifying only the scheduler part of the OS. Herein we survey the vast field of research on energy-cognizant schedulers. We discuss scheduling techniques to perform energy-efficient computation. We further explore how the energy-cognizant scheduler's role has been extended beyond simple energy minimization to also include related issues like the avoidance of negative thermal effects as well as addressing asymmetric multicore architectures.
---
paper_title: Understanding the Thermal Implications of Multi-Core Architectures

paper_content:

Multicore architectures are becoming the main design paradigm for current and future processors. The main reason is that multicore designs provide an effective way of overcoming instruction-level parallelism (ILP) limitations by exploiting thread-level parallelism (TLP). In addition, it is a power and complexity-effective way of taking advantage of the huge number of transistors that can be integrated on a chip. On the other hand, today's higher than ever power densities have made temperature one of the main limitations of microprocessor evolution. Thermal management in multicore architectures is a fairly new area. Some works have addressed dynamic thermal management in bi/quad-core architectures. This work provides insight and explores different alternatives for thermal management in multicore architectures with 16 cores. Schemes employing both energy reduction and activity migration are explored and improvements for thread migration schemes are proposed.
---
paper_title: Accurate Modeling of the Delay and Energy Overhead of Dynamic Voltage and Frequency Scaling in Modern Microprocessors

paper_content:

Dynamic voltage and frequency scaling (DVFS) has been studied for well over a decade. Nevertheless, existing DVFS transition overhead models suffer from significant inaccuracies; for example, by incorrectly accounting for the effect of DC–DC converters, frequency synthesizers, voltage, and frequency change policies on energy losses incurred during mode transitions. Incorrect and/or inaccurate DVFS transition overhead models prevent one from determining the precise break-even time and thus forfeit some of the energy saving that is ideally achievable. This paper introduces accurate DVFS transition overhead models for both energy consumption and delay. In particular, we redefine the DVFS transition overhead including the underclocking-related losses in a DVFS-enabled microprocessor, additional inductor IR losses, and power losses due to discontinuous-mode DC–DC conversion. We report the transition overheads for a desktop, a mobile and a low-power representative processor. We also present DVFS transition overhead macromodel for use by high-level DVFS schedulers.
---
paper_title: An optimal speed control scheme supported by media servers for low-power multimedia applications

paper_content:

In this paper, we present a new concept of dynamic voltage scaling (DVS) for low-power multimedia decoding in battery-powered mobile devices. Most existing DVS techniques are suboptimal in achieving energy efficiency while providing the guaranteed playback quality of service, which is mainly due to the inherent limitations of client-only approaches. To address this problem, in this paper, we investigate the possibility of media server supported DVS techniques with smoothing mechanisms. Towards this new direction, we propose a generic offline bitstream analysis framework and an optimal speed control algorithm which achieves the maximal energy savings among all feasible speed profiles for the given buffers. The proposed scheme enables us to compute the buffer sizes of feasibility condition, which are the theoretical lower bound of buffer size requirement for a given media clip. More importantly, our scheme facilitates practical applications from four aspects. First, it does not require feedback information on clients’ configuration. This renders our scheme particularly suitable for broadcast or multicast applications. Second, the speed profile based on buffer sizes of feasibility condition can provide satisfactory energy efficiency. Third, the required buffer sizes are so small that they can be met by most mobile devices. Fourth, additional side information (i.e., speed profile) of the proposed scheme is negligible compared to the size of media content. These properties solve the diversity issue and feasibility issue of media server supported DVS schemes. Experimental results show that, in comparison with the representative existing techniques, our scheme improves the performance of DVS significantly.
---
paper_title: Scheduling for reduced CPU energy

paper_content:

The energy usage of computer systems is becoming more important, especially for battery operated systems. Displays, disks, and cpus, in that order, use the most energy. Reducing the energy used by displays and disks has been studied elsewhere; this paper considers a new method for reducing the energy used by the cpu. We introduce a new metric for cpu energy performance, millions-of-instructions-per-joule (MIPJ). We examine a class of methods to reduce MIPJ that are characterized by dynamic control of system clock speed by the operating system scheduler. Reducing clock speed alone does not reduce MIPJ, since to do the same work the system must run longer. However, a number of methods are available for reducing energy with reduced clock-speed, such as reducing the voltage [Chandrakasan et al 1992][Horowitz 1993] or using reversible [Younis and Knight 1993] or adiabatic logic [Athas et al 1994]. What are the right scheduling algorithms for taking advantage of reduced clock-speed, especially in the presence of applications demanding ever more instructions-per-second? We consider several methods for varying the clock speed dynamically under control of the operating system, and examine the performance of these methods against workstation traces. The primary result is that by adjusting the clock speed at a fine grain, substantial CPU energy can be saved with a limited impact on performance.
---
paper_title: Optimal voltage allocation techniques for dynamically variable voltage processors

paper_content:

This paper presents important, new results of a study on the problem of task scheduling and voltage allocation in dynamically variable voltage processors, the purpose of which was minimization of processor energy consumption. The contributions are twofold: (1) For given multiple discrete supply voltages and tasks with arbitrary arrival-time/deadline constraints, we propose a voltage allocation technique that produces a feasible task schedule with optimal processor energy consumption. (2) We then extend the problem to include the case in which tasks have nonuniform loads (i.e.; switched) capacitances and solve it optimally. The proposed technique, called Alloc-vt, in (1) is based on the prior results in [Yao, Demers and Shenker. 1995. In Proceedings of IEEE Symposium on Foundations of Computer Science. 374--382] (which is optimal for dynamically continuously variable voltages, but not for discrete ones) and [Ishihara and Yasuura. 1998. In Proceedings of International Symposium on Low Power Electronics and Design. 197--202] (which is optimal for a single task, but not for multiple tasks), whereas the proposed technique, called Alloc-vtcap, in (2) is based on an efficient linear programming (LP) formulation. Both techniques solve the allocation problems optimally in polynomial time.
---
paper_title: A scheduling model for reduced CPU energy

paper_content:

The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.
---
paper_title: Voltage scheduling problem for dynamically variable voltage processors

paper_content:

This paper presents a model of dynamically variable voltage processors and basic theorems for power-delay optimization. A static voltage scheduling problem is also proposed and formulated as an integer linear programming (ILP) problem. In the problem, we assume that a core processor can vary its supply voltage dynamically, but can use only a single voltage level at a time. For a given application program and a dynamically variable voltage processor, a voltage scheduling which minimizes energy consumption under an execution time constraint can be found.
---
paper_title: TL-plane-based multi-core energy-efficient real-time scheduling algorithm for sporadic tasks

paper_content:

As the energy consumption of multi-core systems becomes increasingly prominent, it's a challenge to design an energy-efficient real-time scheduling algorithm in multi-core systems for reducing the system energy consumption while guaranteeing the feasibility of real-time tasks. In this paper, we focus on multi-core processors, with the global Dynamic Voltage Frequency Scaling (DVFS) and Dynamic Power Management (DPM) technologies. In this setting, we propose an energy-efficient real-time scheduling algorithm, the Time Local remaining execution plane based Dynamic Voltage Frequency Scaling (TL-DVFS). TL-DVFS utilizes the concept of Time Local remaining execution (TL) plane to dynamically scale the voltage and frequency of a processor at the initial time of each TL plane as well as at the release time of a sporadic task in each TL plane. Consequently, TL-DVFS can obtain a reasonable tradeoff between the real-time constraint and the energy-saving while realizing the optimal feasibility of sporadic tasks. Mathematical analysis and extensive simulations demonstrate that TL-DVFS always saves more energy than existing algorithms, especially in the case of high workloads, and guarantees the optimal feasibility of sporadic tasks at the same time.
---
paper_title: Energy-Aware Partitioned Fixed-Priority Scheduling for Chip Multi-processors

paper_content:

Energy management is becoming an increasingly important problem in application domains ranging from embedded devices to data centers. In many such systems, multi-core processors are projected as a promising technology to achieve improved performance with a lower power envelope. Managing the application power consumption under timing constraints poses significant challenges in these emerging platforms. In this paper, we study the energy-efficient scheduling of periodic real time tasks with implicit deadlines on chip multi-core processors (CMPs). We specifically consider processors with a single voltage and clock frequency domain, such as the state-of-the-art embedded multi-core NVIDIA Tegra 2processor and enterprise-class processors such as Intel'sItanium 2, i5, i7 and IBM's Power 6 and Power 7series. The major contributions of this work are (i)we prove that Worst-Fit-Decreasing (WFD) task partitioning when Rate-Monotonic Scheduling (RMS) is used has an approximation ratio of 1.71 for the problem of minimizing the schedulable operating frequency with partitioned fixed-priority scheduling, (ii) we illustrate the major shortcoming of WFD with RMS resulting from not considering task periods during allocation, and(iii) we propose a Single-clock domain multi-processor Frequency Assignment Algorithm (SFAA) that determines a globally energy-efficient frequency while including task period relationships. Our evaluation results show that SFAA provides significant energy gains when compared to WFD. In fact SFAA is shown to save up to 55% more power compared to WFD for an octa-core processor.
---
paper_title: On the Interplay of Voltage/Frequency Scaling and Device Power Management for Frame-Based Real-Time Embedded Applications

paper_content:

Voltage/Frequency Scaling (VFS) and Device Power Management (DPM) are two popular techniques commonly employed to save energy in real-time embedded systems. VFS policies aim at reducing the CPU energy, while DPM-based solutions involve putting the system components (e.g., memory or I/O devices) to low-power/sleep states at runtime, when sufficiently long idle intervals can be predicted. Despite numerous research papers that tackled the energy minimization problem using VFS or DPM separately, the interactions of these two popular techniques are not yet well understood. In this paper, we undertake an exact analysis of the problem for a real-time embedded application running on a VFS-enabled CPU and using multiple devices. Specifically, by adopting a generalized system-level energy model, we characterize the variations in different components of the system energy as a function of the CPU processing frequency. Then, we propose a provably optimal and efficient algorithm to determine the optimal CPU frequency as well as device state transition decisions to minimize the system-level energy. We also extend our solution to deal with workload variability. The experimental evaluations confirm that substantial energy savings can be obtained through our solution that combines VFS and DPM optimally under the given task and energy models.
---
paper_title: A New Energy-Aware Dynamic Task Set Partitioning Algorithm for Soft and Hard Embedded Real-Time Systems

paper_content:

Power consumption is a major design concern in current embedded systems. To deal with consumption, many systems apply dynamic voltage scaling (DVS) techniques which dynamically change the system speed depending on the workload characteristics. DVS costs in a multicore system can be reduced by sharing the same DVS regulator among the cores. In this context, to handle energy efficiently, the workload must be properly balanced among the cores. This paper proposes a new heuristic algorithm to balance the workload in an embedded system with a coarse-grain multithreaded multicore processor. This heuristic is aimed at improving the overlapping time between the memory and the processor while keeping balanced core utilizations. To this end, the heuristic dynamically drives the frequency/voltage level to guarantee deadline fulfillment of the hard real-time tasks as well as to achieve a good trade-off between deadline losses and energy savings of the soft real-time tasks. The proposed technique has been evaluated on a model of a contemporary high-end ARM embedded microprocessor executing a set of standard embedded benchmarks. Energy savings depend on the range of frequency/voltage levels that the DVS regulator implements. Experimental results show that with the proposed heuristic, when working with hard real-time tasks, the energy consumption is about 33% the energy dissipated by a system without DVS regulator and balancing heuristic. Moreover, when soft real-time tasks are also considered, the normalized consumption presents values ranging in between 8 and 70% depending on the scheduler aggressiveness.
---
paper_title: Optimal DPM and DVFS for frame-based real-time systems

paper_content:

Dynamic Power Management (DPM) and Dynamic Voltage and Frequency Scaling (DVFS) are popular techniques for reducing energy consumption. Algorithms for optimal DVFS exist, but optimal DPM and the optimal combination of DVFS and DPM are not yet solved. In this article we use well-established models of DPM and DVFS for frame-based systems. We show that it is not sufficient—as some authors argue—to consider only individual invocations of a task. We define a schedule that also takes interactions between invocations into account and prove—in a theoretical fashion—that this schedule is optimal.
---
paper_title: Optimal Power-Down Strategies

paper_content:

We consider the problem of selecting threshold times to transition a device to low-power sleep states during an idle period. The two-state case, in which there is a single active and a single sleep state, is a continuous version of the ski-rental problem. We consider a generalized version in which there is more than one sleep state, each with its own power-consumption rate and transition costs. We give an algorithm that, given a system, produces a deterministic strategy whose competitive ratio is arbitrarily close to optimal. We also give an algorithm to produce the optimal online strategy given a system and a probability distribution that generates the length of the idle period. We also give a simple algorithm that achieves a competitive ratio of $3 + 2\sqrt{2} \approx 5.828$ for any system.
---
paper_title: Algorithms for power savings

paper_content:

This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s) which indicates the power consumption level given a particular speed. We assume that P(s) is convex, nondecreasing, and nonnegative for s ≥ 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.
---
paper_title: From Preemptive to Non-preemptive Speed-Scaling Scheduling

paper_content:

We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s α units of energy per time unit, where α > 1. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption is minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case.
---
paper_title: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

paper_content:

The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
---
paper_title: Algorithms for power savings

paper_content:

This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s) which indicates the power consumption level given a particular speed. We assume that P(s) is convex, nondecreasing, and nonnegative for s ≥ 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.
---
paper_title: An optimal speed control scheme supported by media servers for low-power multimedia applications

paper_content:

In this paper, we present a new concept of dynamic voltage scaling (DVS) for low-power multimedia decoding in battery-powered mobile devices. Most existing DVS techniques are suboptimal in achieving energy efficiency while providing the guaranteed playback quality of service, which is mainly due to the inherent limitations of client-only approaches. To address this problem, in this paper, we investigate the possibility of media server supported DVS techniques with smoothing mechanisms. Towards this new direction, we propose a generic offline bitstream analysis framework and an optimal speed control algorithm which achieves the maximal energy savings among all feasible speed profiles for the given buffers. The proposed scheme enables us to compute the buffer sizes of feasibility condition, which are the theoretical lower bound of buffer size requirement for a given media clip. More importantly, our scheme facilitates practical applications from four aspects. First, it does not require feedback information on clients’ configuration. This renders our scheme particularly suitable for broadcast or multicast applications. Second, the speed profile based on buffer sizes of feasibility condition can provide satisfactory energy efficiency. Third, the required buffer sizes are so small that they can be met by most mobile devices. Fourth, additional side information (i.e., speed profile) of the proposed scheme is negligible compared to the size of media content. These properties solve the diversity issue and feasibility issue of media server supported DVS schemes. Experimental results show that, in comparison with the representative existing techniques, our scheme improves the performance of DVS significantly.
---
paper_title: A scheduling model for reduced CPU energy

paper_content:

The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.
---
paper_title: Speed Scaling with an Arbitrary Power Function

paper_content:

This article initiates a theoretical investigation into online scheduling problems with speed scaling where the allowable speeds may be discrete, and the power function may be arbitrary, and develops algorithmic analysis techniques for this setting. We show that a natural algorithm, which uses Shortest Remaining Processing Time for scheduling and sets the power to be one more than the number of unfinished jobs, is 3-competitive for the objective of total flow time plus energy. We also show that another natural algorithm, which uses Highest Density First for scheduling and sets the power to be the fractional weight of the unfinished jobs, is a 2-competitive algorithm for the objective of fractional weighted flow time plus energy.
---
paper_title: When Discreteness Meets Continuity: Energy-Optimal DVS Scheduling Revisited ∗

paper_content:

The energy-optimal DVS scheduling problem seeks to create a frequency-voltage schedule for the CPU that can achieve energy minimization with tolerable performance loss. Prior solutions to the problem assume that the CPU canrunacrossacontinuousrangeoffrequenciesandvoltages, but today’s DVS-enabled microprocessors can only support a discrete set. As a result, the energy-optimal results in the continuous case may no longer be valid in the discrete case. This paper bridges the two cases by showingthattheoptimalitycanberetainedthroughemulation. The resultisalso applicable tosystemsthat consider leakage and/or system energy usage.
---
paper_title: Leakage aware dynamic voltage scaling for real-time embedded systems

paper_content:

A five-fold increase in leakage current is predicted with each technology generation. While Dynamic Voltage Scaling (DVS) is known to reduce dynamic power consumption, it also causes increased leakage energy drain by lengthening the interval over which a computation is carried out. Therefore, for minimization of the total energy, one needs to determine an operating point, called the critical speed. We compute processor slowdown factors based on the critical speed for energy minimization. Procrastination scheduling attempts to maximize the duration of idle intervals by keeping the processor in a sleep/shutdown state even if there are pending tasks, within the constraints imposed by performance requirements. Our simulation experiments show that the critical speed slowdown results in up to 5% energy gains over a leakage oblivious dynamic voltage scaling. Procrastination scheduling scheme extends the sleep intervals to up to 5 times, resulting in up to an additional 18% energy gains, while meeting all timing requirements.
---
paper_title: A scheduling model for reduced CPU energy

paper_content:

The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.
---
paper_title: Algorithms for power savings

paper_content:

This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s) which indicates the power consumption level given a particular speed. We assume that P(s) is convex, nondecreasing, and nonnegative for s ≥ 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.
---
paper_title: Bounding energy consumption in large-scale MPI programs

paper_content:

Power is now a first-order design constraint in large-scale parallel computing. Used carefully, dynamic voltage scaling can execute parts of a program at a slower CPU speed to achieve energy savings with a relatively small (possibly zero) time delay. However, the problem of when to change frequencies in order to optimize energy savings is NP-complete, which has led to many heuristic energy-saving algorithms. To determine how closely these algorithms approach optimal savings, we developed a system that determines a bound on the energy savings for an application. Our system uses a linear programming solver that takes as inputs the application communication trace and the cluster power characteristics and then outputs a schedule that realizes this bound. We apply our system to three scientific programs, two of which exhibit load imbalance---particle simulation and UMT2K. Results from our bounding technique show particle simulation is more amenable to energy savings than UMT2K.
---
paper_title: Optimal voltage allocation techniques for dynamically variable voltage processors

paper_content:

This paper presents important, new results of a study on the problem of task scheduling and voltage allocation in dynamically variable voltage processors, the purpose of which was minimization of processor energy consumption. The contributions are twofold: (1) For given multiple discrete supply voltages and tasks with arbitrary arrival-time/deadline constraints, we propose a voltage allocation technique that produces a feasible task schedule with optimal processor energy consumption. (2) We then extend the problem to include the case in which tasks have nonuniform loads (i.e.; switched) capacitances and solve it optimally. The proposed technique, called Alloc-vt, in (1) is based on the prior results in [Yao, Demers and Shenker. 1995. In Proceedings of IEEE Symposium on Foundations of Computer Science. 374--382] (which is optimal for dynamically continuously variable voltages, but not for discrete ones) and [Ishihara and Yasuura. 1998. In Proceedings of International Symposium on Low Power Electronics and Design. 197--202] (which is optimal for a single task, but not for multiple tasks), whereas the proposed technique, called Alloc-vtcap, in (2) is based on an efficient linear programming (LP) formulation. Both techniques solve the allocation problems optimally in polynomial time.
---
paper_title: An optimal speed control scheme supported by media servers for low-power multimedia applications

paper_content:

In this paper, we present a new concept of dynamic voltage scaling (DVS) for low-power multimedia decoding in battery-powered mobile devices. Most existing DVS techniques are suboptimal in achieving energy efficiency while providing the guaranteed playback quality of service, which is mainly due to the inherent limitations of client-only approaches. To address this problem, in this paper, we investigate the possibility of media server supported DVS techniques with smoothing mechanisms. Towards this new direction, we propose a generic offline bitstream analysis framework and an optimal speed control algorithm which achieves the maximal energy savings among all feasible speed profiles for the given buffers. The proposed scheme enables us to compute the buffer sizes of feasibility condition, which are the theoretical lower bound of buffer size requirement for a given media clip. More importantly, our scheme facilitates practical applications from four aspects. First, it does not require feedback information on clients’ configuration. This renders our scheme particularly suitable for broadcast or multicast applications. Second, the speed profile based on buffer sizes of feasibility condition can provide satisfactory energy efficiency. Third, the required buffer sizes are so small that they can be met by most mobile devices. Fourth, additional side information (i.e., speed profile) of the proposed scheme is negligible compared to the size of media content. These properties solve the diversity issue and feasibility issue of media server supported DVS schemes. Experimental results show that, in comparison with the representative existing techniques, our scheme improves the performance of DVS significantly.
---
paper_title: Optimal voltage allocation techniques for dynamically variable voltage processors

paper_content:

This paper presents important, new results of a study on the problem of task scheduling and voltage allocation in dynamically variable voltage processors, the purpose of which was minimization of processor energy consumption. The contributions are twofold: (1) For given multiple discrete supply voltages and tasks with arbitrary arrival-time/deadline constraints, we propose a voltage allocation technique that produces a feasible task schedule with optimal processor energy consumption. (2) We then extend the problem to include the case in which tasks have nonuniform loads (i.e.; switched) capacitances and solve it optimally. The proposed technique, called Alloc-vt, in (1) is based on the prior results in [Yao, Demers and Shenker. 1995. In Proceedings of IEEE Symposium on Foundations of Computer Science. 374--382] (which is optimal for dynamically continuously variable voltages, but not for discrete ones) and [Ishihara and Yasuura. 1998. In Proceedings of International Symposium on Low Power Electronics and Design. 197--202] (which is optimal for a single task, but not for multiple tasks), whereas the proposed technique, called Alloc-vtcap, in (2) is based on an efficient linear programming (LP) formulation. Both techniques solve the allocation problems optimally in polynomial time.
---
paper_title: A scheduling model for reduced CPU energy

paper_content:

The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.
---
paper_title: When Discreteness Meets Continuity: Energy-Optimal DVS Scheduling Revisited ∗

paper_content:

The energy-optimal DVS scheduling problem seeks to create a frequency-voltage schedule for the CPU that can achieve energy minimization with tolerable performance loss. Prior solutions to the problem assume that the CPU canrunacrossacontinuousrangeoffrequenciesandvoltages, but today’s DVS-enabled microprocessors can only support a discrete set. As a result, the energy-optimal results in the continuous case may no longer be valid in the discrete case. This paper bridges the two cases by showingthattheoptimalitycanberetainedthroughemulation. The resultisalso applicable tosystemsthat consider leakage and/or system energy usage.
---
paper_title: On the Interplay between Global DVFS and Scheduling Tasks with Precedence Constraints

paper_content:

Many multicore processors are capable of decreasing the voltage and clock frequency to save energy at the cost of an increased delay. While a large part of the theory oriented literature focuses on local dynamic voltage and frequency scaling (local DVFS), where every core’s voltage and clock frequency can be set separately, this article presents an in-depth theoretical study of the more commonly available global DVFS that makes such changes for the entire chip. This article shows how to choose the optimal clock frequencies that minimize the energy for global DVFS, and it discusses the relationship between scheduling and optimal global DVFS. Formulas are given to find this optimum under time constraints, including proofs thereof. The problem of simultaneously choosing clock frequencies and a schedule that together minimize the energy consumption is discussed, and based on this a scheduling criterion is derived that implicitly assigns frequencies and minimizes energy consumption. Furthermore, this article studies the effectivity of a large class of scheduling algorithms with regard to the derived criterion, and a bound on the maximal relative deviation is given. Simulations show that with our techniques an energy reduction of 30% can be achieved with respect to state-of-the-art research.
---
paper_title: Optimal voltage allocation techniques for dynamically variable voltage processors

paper_content:

This paper presents important, new results of a study on the problem of task scheduling and voltage allocation in dynamically variable voltage processors, the purpose of which was minimization of processor energy consumption. The contributions are twofold: (1) For given multiple discrete supply voltages and tasks with arbitrary arrival-time/deadline constraints, we propose a voltage allocation technique that produces a feasible task schedule with optimal processor energy consumption. (2) We then extend the problem to include the case in which tasks have nonuniform loads (i.e.; switched) capacitances and solve it optimally. The proposed technique, called Alloc-vt, in (1) is based on the prior results in [Yao, Demers and Shenker. 1995. In Proceedings of IEEE Symposium on Foundations of Computer Science. 374--382] (which is optimal for dynamically continuously variable voltages, but not for discrete ones) and [Ishihara and Yasuura. 1998. In Proceedings of International Symposium on Low Power Electronics and Design. 197--202] (which is optimal for a single task, but not for multiple tasks), whereas the proposed technique, called Alloc-vtcap, in (2) is based on an efficient linear programming (LP) formulation. Both techniques solve the allocation problems optimally in polynomial time.
---
paper_title: New Results for Non-Preemptive Speed Scaling

paper_content:

We consider the speed scaling problem introduced in the seminal paper of Yao et al. [23]. In this problem, a number of jobs, each with its own processing volume, release time, and deadline, needs to be executed on a speed-scalable processor. The power consumption of this processor is P(s) = s α , where s is the processing speed, and α > 1 is a constant. The total energy consumption is power integrated over time, and the objective is to process all jobs while minimizing the energy consumption.
---
paper_title: Green Scheduling, Flows and Matchings

paper_content:

Recently, optimal combinatorial algorithms have been presented for the energy minimization multi-processor speed scaling problem with migration [Albers et al., SPAA 2011], [Angel et al., Euro-Par 2012]. These algorithms are based on repeated maximum-flow computations allowing the partition of the set of jobs into subsets in which all the jobs are executed at the same speed. The optimality of these algorithms is based on a series of technical lemmas showing that this partition and the corresponding speeds lead to the minimization of the energy consumption. In this paper, we show that both the algorithms and their analysis can be greatly simplified. In order to do this, we formulate the problem as a convex cost flow problem in an appropriate flow network. Furthermore, we show that our approach is useful to solve other problems in the dynamic speed scaling setting. As an example, we consider the preemptive open-shop speed scaling problem and we propose a polynomial-time algorithm for finding an optimal solution based on the computation of convex cost flows. We also propose a polynomial-time algorithm for minimizing a linear combination of the sum of the completion times of the jobs and the total energy consumption, for the multi-processor speed scaling problem without preemptions. Instead of using convex cost flows, our algorithm is based on the computation of a minimum weighted maximum matching in an appropriate bipartite graph.
---
paper_title: Speed scaling on parallel processors with migration

paper_content:

We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works) on parallel speed scalable processors so as to minimize the total energy consumption. We consider that both preemptions and migrations of jobs are allowed. For this problem, there exists an optimal polynomial-time algorithm which uses as a black box an algorithm for linear programming. Here, we formulate the problem as a convex program and we propose a combinatorial polynomial-time algorithm which is based on finding maximum flows. Our algorithm runs in \(O({ nf}(n)\log U)\) time, where n is the number of jobs, U is the range of all possible values of processors’ speeds divided by the desired accuracy and f(n) is the time needed for computing a maximum flow in a layered graph with O(n) vertices.
---
paper_title: On multi-processor speed scaling with migration: extended abstract

paper_content:

We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. Previous work has focused mostly on the setting where a single variable-speed processor is available. In this paper we study multi-processor environments with m parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. In contrast to a previously known strategy, our algorithm does not resort to linear programming. We develop a fully combinatorial algorithm that relies on repeated maximum flow computations. The approach might be useful to solve other problems in dynamic speed scaling. For the online problem, we extend two algorithms Optimal Available and Average Rate proposed by Yao et al. [16] for the single processor setting. We prove that Optimal Available is αα-competitive, as in the single processor case. Here α>1 is the exponent of the power consumption function. While it is straightforward to extend Optimal Available to parallel processing environments, the competitive analysis becomes considerably more involved. For Average Rate we show a competitiveness of (3\α)α/2 + 2α.
---
paper_title: Green Scheduling, Flows and Matchings

paper_content:

Recently, optimal combinatorial algorithms have been presented for the energy minimization multi-processor speed scaling problem with migration [Albers et al., SPAA 2011], [Angel et al., Euro-Par 2012]. These algorithms are based on repeated maximum-flow computations allowing the partition of the set of jobs into subsets in which all the jobs are executed at the same speed. The optimality of these algorithms is based on a series of technical lemmas showing that this partition and the corresponding speeds lead to the minimization of the energy consumption. In this paper, we show that both the algorithms and their analysis can be greatly simplified. In order to do this, we formulate the problem as a convex cost flow problem in an appropriate flow network. Furthermore, we show that our approach is useful to solve other problems in the dynamic speed scaling setting. As an example, we consider the preemptive open-shop speed scaling problem and we propose a polynomial-time algorithm for finding an optimal solution based on the computation of convex cost flows. We also propose a polynomial-time algorithm for minimizing a linear combination of the sum of the completion times of the jobs and the total energy consumption, for the multi-processor speed scaling problem without preemptions. Instead of using convex cost flows, our algorithm is based on the computation of a minimum weighted maximum matching in an appropriate bipartite graph.
---
paper_title: Approximation schemes for scheduling

paper_content:

We consider the classic scheduling/load balancing problems where there are m identical machines and n jobs, and each job should be assigned to some machine. Traditionally, the assignment of jobs to machines is measured by the makespan (maximum load) i.e., the L{sub {infinity}} norm of the assignment. An {epsilon}-approximation scheme was given by Hochbaum and Shmoys for minimizing the L{sub {infinity}} norm. In several applications, such as in storage allocation, a more appropriate measure is the sum of the squares of the loads (which is equivalent to the L{sub 2} norm). This problem was considered in who showed how to approximate the optimum value by a factor of about 1.04. In fact, a more general measure, which is the L, norm (for any p {ge} 1) t can also be approximated to some constant which may be as large as 3/2. We improve e these results by providing an c-approximation scheme for the general L{sub p} norm (and in particular for the L{sub 2} norm). We also consider the case of restricted assignment of unit jobs where we show how to find in polynomial time, a solution a which is optimal for all norms.
---
paper_title: Multiprocessor energy-efficient scheduling with task migration considerations

paper_content:

This paper targets energy-efficient scheduling of tasks over multiple processors, where tasks share a common deadline. Distinct from many research results on heuristics-based energy-efficient scheduling, we propose approximation algorithms with different approximation bounds for processors with/without constraints on the maximum processor speed, where no task migration is allowed. When there is no constraint on processor speeds, we propose an approximation algorithm for two-processor scheduling to provide trade-offs among the specified error, the running time, the approximation ratio, and the memory space complexity. An approximation algorithm with a 1.13-approximation ratio for M-processor systems is also derived (M > 2). When there is an upper bound on processor speeds, an artificial-bound approach is taken to minimize the energy consumption with a 1.13-approximation ratio. An optimal scheduling algorithm is then proposed in the minimization of the energy consumption when task migration is allowed.
---
paper_title: Energy Efficient Scheduling and Routing via Randomized Rounding

paper_content:

We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
---
paper_title: Energy-efficient algorithms for non-preemptive speed-scaling

paper_content:

We improve complexity bounds for energy-efficient non-preemptive scheduling problems for both the single processor and multi-processor cases. As energy conservation has become a major concern, traditional scheduling problems have been revisited in the past few years to take into account the energy consumption [1]. We consider the speed scaling setting introduced by Yao et al. [20] where a set of jobs, each with a release date, deadline and work volume, are to be scheduled on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the \(\alpha \)th power of their speed integrated over time. The objective is then to find a feasible non-preemptive schedule which minimizes the total energy used.
---
paper_title: Energy Optimal Scheduling on Multiprocessors with Migration

paper_content:

We show that the problem of finding an energy minimal schedule for execution of a collection of jobs on a multiprocessor with job migration allowed has polynomial complexity. Each job is specified by a release time, a deadline, and an amount of work to be performed. All of the processors have the same, convex power-speed trade-off of the form P = phi(s), where P is power, s is speed, and phi is convex. Unlike previous work on multiprocessor scheduling, we place no restriction on the release times, deadlines, or amount of work to be done. We show that the scheduling problem is convex, and give an algorithm based on linear programming. We show that the optimal schedule is the same for any convex power-speed trade-off function.
---
paper_title: A Fully Polynomial-Time Approximation Scheme for Speed Scaling with Sleep State

paper_content:

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. [17], its exact computational complexity has been repeatedly posed as an open question (see e.g. [2,9,16]). The currently best known upper and lower bounds are a 4/3-approximation algorithm and NP-hardness due to [2] and [2, 18], 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.
---
paper_title: Speed-scaling with no Preemptions

paper_content:

We revisit the non-preemptive speed-scaling problem, in which a set of jobs have to be executed on a single or a set of parallel speed-scalable processor(s) between their release dates and deadlines so that the energy consumption to be minimized. We adopt the speed-scaling mechanism first introduced in [Yao et al., FOCS 1995] according to which the power dissipated is a convex function of the processor's speed. Intuitively, the higher is the speed of a processor, the higher is the energy consumption. For the single-processor case, we improve the best known approximation algorithm by providing a $(1+\epsilon)^{\alpha}\tilde{B}_{\alpha}$-approximation algorithm, where $\tilde{B}_{\alpha}$ is a generalization of the Bell number. For the multiprocessor case, we present an approximation algorithm of ratio $\tilde{B}_{\alpha}((1+\epsilon)(1+\frac{w_{\max}}{w_{\min}}))^{\alpha}$ improving the best known result by a factor of $(\frac{5}{2})^{\alpha-1}(\frac{w_{\max}}{w_{\min}})^{\alpha}$. Notice that our result holds for the fully heterogeneous environment while the previous known result holds only in the more restricted case of parallel processors with identical power functions.
---
paper_title: Race to idle: New algorithms for speed scaling with a sleep state

paper_content:

We study an energy conservation problem where a variable-speed processor is equipped with a sleep state. Executing jobs at high speeds and then setting the processor asleep is an approach that can lead to further energy savings compared to standard dynamic speed scaling. We consider classical deadline-based scheduling, i.e. each job is specified by a release time, a deadline and a processing volume. For general convex power functions, Irani et al. [12] devised an offline 2-approximation algorithm. Roughly speaking, the algorithm schedules jobs at a critical speed Scrit that yields the smallest energy consumption while jobs are processed. For power functions P(s) = sα + γ, where s is the processor speed, Han et al. [11] gave an (αα + 2)-competitive online algorithm. ::: ::: We investigate the offline setting of speed scaling with a sleep state. First we prove NP-hardness of the optimization problem. Additionally, we develop lower bounds, for general convex power functions: No algorithm that constructs Scrit-schedules, which execute jobs at speeds of at least scrit, can achieve an approximation factor smaller than 2. Furthermore, no algorithm that minimizes the energy expended for processing jobs can attain an approximation ratio smaller than 2. ::: ::: We then present an algorithmic framework for designing good approximation algorithms. For general convex power functions, we derive an approximation factor of 4/3. For power functions P(s) = βsα + γ, we obtain an approximation of 137/117 < 1.171. We finally show that our framework yields the best approximation guarantees for the class of Scrit-schedules. For general convex power functions, we give another 2-approximation algorithm. For functions P(s) = βsα + γ, we present tight upper and lower bounds on the best possible approximation factor. The ratio is exactly eW−1(−e−1−1/e)/(eW−1(−e−1−1/e) + 1) < 1.211, where W--1 is the lower branch of the Lambert W function.
---
paper_title: From Preemptive to Non-preemptive Speed-Scaling Scheduling

paper_content:

We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s α units of energy per time unit, where α > 1. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption is minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case.
---
paper_title: Optimal voltage allocation techniques for dynamically variable voltage processors

paper_content:

This paper presents important, new results of a study on the problem of task scheduling and voltage allocation in dynamically variable voltage processors, the purpose of which was minimization of processor energy consumption. The contributions are twofold: (1) For given multiple discrete supply voltages and tasks with arbitrary arrival-time/deadline constraints, we propose a voltage allocation technique that produces a feasible task schedule with optimal processor energy consumption. (2) We then extend the problem to include the case in which tasks have nonuniform loads (i.e.; switched) capacitances and solve it optimally. The proposed technique, called Alloc-vt, in (1) is based on the prior results in [Yao, Demers and Shenker. 1995. In Proceedings of IEEE Symposium on Foundations of Computer Science. 374--382] (which is optimal for dynamically continuously variable voltages, but not for discrete ones) and [Ishihara and Yasuura. 1998. In Proceedings of International Symposium on Low Power Electronics and Design. 197--202] (which is optimal for a single task, but not for multiple tasks), whereas the proposed technique, called Alloc-vtcap, in (2) is based on an efficient linear programming (LP) formulation. Both techniques solve the allocation problems optimally in polynomial time.
---
paper_title: A scheduling model for reduced CPU energy

paper_content:

The energy usage of computer systems is becoming an important consideration, especially for battery-operated systems. Various methods for reducing energy consumption have been investigated, both at the circuit level and at the operating systems level. In this paper, we propose a simple model of job scheduling aimed at capturing some key aspects of energy minimization. In this model, each job is to be executed between its arrival time and deadline by a single processor with variable speed, under the assumption that energy usage per unit time, P, is a convex function, of the processor speed s. We give an off-line algorithm that computes, for any set of jobs, a minimum-energy schedule. We then consider some on-line algorithms and their competitive performance for the power function P(s)=s/sup p/ where p/spl ges/2. It is shown that one natural heuristic, called the Average Rate heuristic, uses at most a constant times the minimum energy required. The analysis involves bounding the largest eigenvalue in matrices of a special type.
---
paper_title: An $O(n^2)$ Algorithm for Computing Optimal Continuous Voltage Schedules

paper_content:

Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. In the continuous model, the processor can run at any speed, while in the discrete model, the processor can only run at finite number of speeds given as input. The current best algorithm for computing the optimal schedules for the continuous model runs at \(O(n^2\log n)\) time for scheduling n jobs. In this paper, we improve the running time to \(O(n^2)\) by speeding up the calculation of s-schedules using a more refined data structure. For the discrete model, we improve the computation of the optimal schedule from the current best \(O(dn\log n)\) to \(O(n\log \max \{d,n\})\) where d is the number of allowed speeds.
---
paper_title: New Results for Non-Preemptive Speed Scaling

paper_content:

We consider the speed scaling problem introduced in the seminal paper of Yao et al. [23]. In this problem, a number of jobs, each with its own processing volume, release time, and deadline, needs to be executed on a speed-scalable processor. The power consumption of this processor is P(s) = s α , where s is the processing speed, and α > 1 is a constant. The total energy consumption is power integrated over time, and the objective is to process all jobs while minimizing the energy consumption.
---
paper_title: ⋄ Convex Optimization,

paper_content:

Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics.
---
paper_title: When Discreteness Meets Continuity: Energy-Optimal DVS Scheduling Revisited ∗

paper_content:

The energy-optimal DVS scheduling problem seeks to create a frequency-voltage schedule for the CPU that can achieve energy minimization with tolerable performance loss. Prior solutions to the problem assume that the CPU canrunacrossacontinuousrangeoffrequenciesandvoltages, but today’s DVS-enabled microprocessors can only support a discrete set. As a result, the energy-optimal results in the continuous case may no longer be valid in the discrete case. This paper bridges the two cases by showingthattheoptimalitycanberetainedthroughemulation. The resultisalso applicable tosystemsthat consider leakage and/or system energy usage.
---
paper_title: Speed scaling on parallel processors with migration

paper_content:

We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works) on parallel speed scalable processors so as to minimize the total energy consumption. We consider that both preemptions and migrations of jobs are allowed. For this problem, there exists an optimal polynomial-time algorithm which uses as a black box an algorithm for linear programming. Here, we formulate the problem as a convex program and we propose a combinatorial polynomial-time algorithm which is based on finding maximum flows. Our algorithm runs in \(O({ nf}(n)\log U)\) time, where n is the number of jobs, U is the range of all possible values of processors’ speeds divided by the desired accuracy and f(n) is the time needed for computing a maximum flow in a layered graph with O(n) vertices.
---
paper_title: Algorithms for power savings

paper_content:

This article examines two different mechanisms for saving power in battery-operated embedded systems. The first strategy is that the system can be placed in a sleep state if it is idle. However, a fixed amount of energy is required to bring the system back into an active state in which it can resume work. The second way in which power savings can be achieved is by varying the speed at which jobs are run. We utilize a power consumption curve P(s) which indicates the power consumption level given a particular speed. We assume that P(s) is convex, nondecreasing, and nonnegative for s ≥ 0. The problem is to schedule arriving jobs in a way that minimizes total energy use and so that each job is completed after its release time and before its deadline. We assume that all jobs can be preempted and resumed at no cost. Although each problem has been considered separately, this is the first theoretical analysis of systems that can use both mechanisms. We give an offline algorithm that is within a factor of 2 of the optimal algorithm. We also give an online algorithm with a constant competitive ratio.
---
paper_title: On energy-optimal voltage scheduling for fixed-priority hard real-time systems

paper_content:

We address the problem of energy-optimal voltage scheduling for fixed-priority hard real-time systems, on which we present a complete treatment both theoretically and practically. Although most practical real-time systems are based on fixed-priority scheduling, there have been few research results known on the energy-optimal fixed-priority scheduling problem. First, we prove that the problem is NP-hard. Then, we present a fully polynomial time approximation scheme (FPTAS) for the problem. For any e > 0, the proposed approximation scheme computes a voltage schedule whose energy consumption is at most (1 + e) times that of the optimal voltage schedule. Furthermore, the running time of the proposed approximation scheme is bounded by a polynomial function of the number of input jobs and 1/e. Given the NP-hardness of the problem, the proposed approximation scheme is practically the best solution because it can compute a near-optimal voltage schedule (i.e., provably arbitrarily close to the optimal schedule) in polynomial time. Experimental results show that the approximation scheme finds more efficient (almost optimal) voltage schedules faster than the best existing heuristic.
---
paper_title: On multi-processor speed scaling with migration: extended abstract

paper_content:

We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. Previous work has focused mostly on the setting where a single variable-speed processor is available. In this paper we study multi-processor environments with m parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. In contrast to a previously known strategy, our algorithm does not resort to linear programming. We develop a fully combinatorial algorithm that relies on repeated maximum flow computations. The approach might be useful to solve other problems in dynamic speed scaling. For the online problem, we extend two algorithms Optimal Available and Average Rate proposed by Yao et al. [16] for the single processor setting. We prove that Optimal Available is αα-competitive, as in the single processor case. Here α>1 is the exponent of the power consumption function. While it is straightforward to extend Optimal Available to parallel processing environments, the competitive analysis becomes considerably more involved. For Average Rate we show a competitiveness of (3\α)α/2 + 2α.
---
paper_title: Speed scaling to manage energy and temperature

paper_content:

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. We study policies for setting the speed of the processor for both of the goals of minimizing the energy used and the maximum temperature attained. The theoretical study of speed scaling policies to manage energy was initiated in a seminal paper by Yao et al. [1995], and we adopt their setting. We assume that the power required to run at speed s is P(s) e sα for some constant α > 1. We assume a collection of tasks, each with a release time, a deadline, and an arbitrary amount of work that must be done between the release time and the deadline. Yao et al. [1995] gave an offline greedy algorithm YDS to compute the minimum energy schedule. They further proposed two online algorithms Average Rate (AVR) and Optimal Available (OA), and showed that AVR is 2α − 1 αα-competitive with respect to energy. We provide a tight αα bound on the competitive ratio of OA with respect to energy. We initiate the study of speed scaling to manage temperature. We assume that the environment has a fixed ambient temperature and that the device cools according to Newton's law of cooling. We observe that the maximum temperature can be approximated within a factor of two by the maximum energy used over any interval of length 1/b, where b is the cooling parameter of the device. We define a speed scaling policy to be cooling-oblivious if it is simultaneously constant-competitive with respect to temperature for all cooling parameters. We then observe that cooling-oblivious algorithms are also constant-competitive with respect to energy, maximum speed and maximum power. We show that YDS is a cooling-oblivious algorithm. In contrast, we show that the online algorithms OA and AVR are not cooling-oblivious. We then propose a new online algorithm that we call BKP. We show that BKP is cooling-oblivious. We further show that BKP is e-competitive with respect to the maximum speed, and that no deterministic online algorithm can have a better competitive ratio. BKP also has a lower competitive ratio for energy than OA for α ≥5. Finally, we show that the optimal temperature schedule can be computed offline in polynomial-time using the Ellipsoid algorithm.
---
paper_title: Polynomial-time algorithms for minimum energy scheduling

paper_content:

The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining satisfactory level of performance. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the paper, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses one unit of energy per one unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O(n^5)-time algorithm. In addition we provide an O(n^4)-time algorithm for computing the minimum energy schedule when all jobs have unit length.
---
paper_title: An optimal speed control scheme supported by media servers for low-power multimedia applications

paper_content:

In this paper, we present a new concept of dynamic voltage scaling (DVS) for low-power multimedia decoding in battery-powered mobile devices. Most existing DVS techniques are suboptimal in achieving energy efficiency while providing the guaranteed playback quality of service, which is mainly due to the inherent limitations of client-only approaches. To address this problem, in this paper, we investigate the possibility of media server supported DVS techniques with smoothing mechanisms. Towards this new direction, we propose a generic offline bitstream analysis framework and an optimal speed control algorithm which achieves the maximal energy savings among all feasible speed profiles for the given buffers. The proposed scheme enables us to compute the buffer sizes of feasibility condition, which are the theoretical lower bound of buffer size requirement for a given media clip. More importantly, our scheme facilitates practical applications from four aspects. First, it does not require feedback information on clients’ configuration. This renders our scheme particularly suitable for broadcast or multicast applications. Second, the speed profile based on buffer sizes of feasibility condition can provide satisfactory energy efficiency. Third, the required buffer sizes are so small that they can be met by most mobile devices. Fourth, additional side information (i.e., speed profile) of the proposed scheme is negligible compared to the size of media content. These properties solve the diversity issue and feasibility issue of media server supported DVS schemes. Experimental results show that, in comparison with the representative existing techniques, our scheme improves the performance of DVS significantly.
---
paper_title: Low complexity scheduling algorithm minimizing the energy for tasks with agreeable deadlines

paper_content:

Power management aims in reducing the energy consumed by computer systems while maintaining a good level of performance. One of the mechanisms used to save energy is the shut-down mechanism which puts the system into a sleep state when it is idle. No energy is consumed in this state, but a fixed amount of energy is required for a transition from the sleep state to the active state which is equal to L times the energy required for the execution of a unit-time task. In this paper, we focus on the off-line version of this problem where a set of unit-time tasks with release dates and deadlines have to be scheduled in order to minimize the overall consumed energy during the idle periods of the schedule. Here we focus on the case where the tasks have agreeable deadlines. For the single processor case, an O(n3) algorithm has been proposed in [7] for unit-time tasks and arbitrary L. We improve this result by introducing a new O(n2) polynomial-time algorithm for tasks with arbitrary processing times and arbitrary L. For the multiprocessor case we also improve the complexity from O(n3m2) [7] to O(n2m) in the case of unit-time tasks and unit L.
---
paper_title: From Preemptive to Non-preemptive Speed-Scaling Scheduling

paper_content:

We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s α units of energy per time unit, where α > 1. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption is minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case.
---
paper_title: Min-Energy Scheduling for Aligned Jobs in Accelerate Model

paper_content:

Dynamic voltage scaling technique provides the capability for processors to adjust the speed and control the energy consumption. We study the pessimistic accelerate model where the acceleration rate of the processor speed is at most K and jobs cannot be executed during the speed transition period. The objective is to find a min-energy (optimal) schedule that finishes every job within its deadline. The job set we study in this paper is aligned jobs where earlier released jobs have earlier deadlines. We start by investigating a special case where all jobs have common arrival time and design an O(n 2) algorithm to compute the optimal schedule based on some nice properties of the optimal schedule. Then, we study the general aligned jobs and obtain an O(n 2) algorithm to compute the optimal schedule by using the algorithm for the common arrival time case as a building block. Because our algorithm relies on the computation of the optimal schedule in the ideal model (K = ?), in order to achieve O(n 2) complexity, we improve the complexity of computing the optimal schedule in the ideal model for aligned jobs from the currently best known O(n 2logn) to O(n 2).
---
paper_title: Low complexity scheduling algorithms minimizing the energy for tasks with agreeable deadlines

paper_content:

Power management aims in reducing the energy consumed by computer systems while maintaining a good level of performance. One of the mechanisms used to save energy is the shut-down mechanism which puts the system into a sleep state when it is idle. No energy is consumed in this state, but a fixed amount of energy is required for a transition from the sleep state to the active state which is equal to L times the energy required for the execution of a unit-time task. In this paper, we focus on the off-line version of this problem where a set of unit-time tasks with release dates and deadlines have to be scheduled in order to minimize the overall consumed energy during the idle periods of the schedule. Here we focus on the case where the tasks have agreeable deadlines. For the single processor case, an O(n^3) algorithm has been proposed in Gururaj et al. (2010) for unit-time tasks and arbitrary L. We improve this result by introducing a new O(n^2) polynomial-time algorithm for tasks with arbitrary processing times and arbitrary L. For the multiprocessor case we also improve the complexity from O(n^3m^2) Gururaj et al. (2010) to O(n^2m) in the case of unit-time tasks and unit L.
---
paper_title: New Results for Non-Preemptive Speed Scaling

paper_content:

We consider the speed scaling problem introduced in the seminal paper of Yao et al. [23]. In this problem, a number of jobs, each with its own processing volume, release time, and deadline, needs to be executed on a speed-scalable processor. The power consumption of this processor is P(s) = s α , where s is the processing speed, and α > 1 is a constant. The total energy consumption is power integrated over time, and the objective is to process all jobs while minimizing the energy consumption.
---
paper_title: Green Scheduling, Flows and Matchings

paper_content:

Recently, optimal combinatorial algorithms have been presented for the energy minimization multi-processor speed scaling problem with migration [Albers et al., SPAA 2011], [Angel et al., Euro-Par 2012]. These algorithms are based on repeated maximum-flow computations allowing the partition of the set of jobs into subsets in which all the jobs are executed at the same speed. The optimality of these algorithms is based on a series of technical lemmas showing that this partition and the corresponding speeds lead to the minimization of the energy consumption. In this paper, we show that both the algorithms and their analysis can be greatly simplified. In order to do this, we formulate the problem as a convex cost flow problem in an appropriate flow network. Furthermore, we show that our approach is useful to solve other problems in the dynamic speed scaling setting. As an example, we consider the preemptive open-shop speed scaling problem and we propose a polynomial-time algorithm for finding an optimal solution based on the computation of convex cost flows. We also propose a polynomial-time algorithm for minimizing a linear combination of the sum of the completion times of the jobs and the total energy consumption, for the multi-processor speed scaling problem without preemptions. Instead of using convex cost flows, our algorithm is based on the computation of a minimum weighted maximum matching in an appropriate bipartite graph.
---
paper_title: Multiprocessor energy-efficient scheduling with task migration considerations

paper_content:

This paper targets energy-efficient scheduling of tasks over multiple processors, where tasks share a common deadline. Distinct from many research results on heuristics-based energy-efficient scheduling, we propose approximation algorithms with different approximation bounds for processors with/without constraints on the maximum processor speed, where no task migration is allowed. When there is no constraint on processor speeds, we propose an approximation algorithm for two-processor scheduling to provide trade-offs among the specified error, the running time, the approximation ratio, and the memory space complexity. An approximation algorithm with a 1.13-approximation ratio for M-processor systems is also derived (M > 2). When there is an upper bound on processor speeds, an artificial-bound approach is taken to minimize the energy consumption with a 1.13-approximation ratio. An optimal scheduling algorithm is then proposed in the minimization of the energy consumption when task migration is allowed.
---
paper_title: Energy Efficient Scheduling and Routing via Randomized Rounding

paper_content:

We propose a unifying framework based on configuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-non-migratory and the preemptive-migratory variants, our approach allows us to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-non-migratory variant, we are able to improve the best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to be routed on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
---
paper_title: Energy Optimal Scheduling on Multiprocessors with Migration

paper_content:

We show that the problem of finding an energy minimal schedule for execution of a collection of jobs on a multiprocessor with job migration allowed has polynomial complexity. Each job is specified by a release time, a deadline, and an amount of work to be performed. All of the processors have the same, convex power-speed trade-off of the form P = phi(s), where P is power, s is speed, and phi is convex. Unlike previous work on multiprocessor scheduling, we place no restriction on the release times, deadlines, or amount of work to be done. We show that the scheduling problem is convex, and give an algorithm based on linear programming. We show that the optimal schedule is the same for any convex power-speed trade-off function.
---
paper_title: Analytic Clock Frequency Selection for Global DVFS

paper_content:

Computers can reduce their power consumption by decreasing their speed using Dynamic Voltage and Frequency Scaling (DVFS). A form of DVFS for multicore processors is global DVFS, where the voltage and clock frequency is shared among all processor cores. Because global DVFS is efficient and cheap to implement, it is used in modern multicore processors like the IBM Power 7, ARM Cortex A9 and NVIDIA Tegra 2. This theory oriented paper discusses energy optimal DVFS algorithms for such processors. There are no known provably optimal algorithms that minimize the energy consumption of nontrivial real-time applications on a global DVFS system. Such algorithms only exist for single core systems, or for simpler application models. While many DVFS algorithms focus on tasks, this theoretical study is conceptually different and focuses on the amount of parallelism. We provide a transformation from a multicore problem to a single core problem, by using the amount of parallelism of an application. Then existing single core algorithms can be used to find the optimal solution. Furthermore, we extend an existing single core algorithm such that it takes static power into account.
---
paper_title: From Preemptive to Non-preemptive Speed-Scaling Scheduling

paper_content:

We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s then the energy consumption is s α units of energy per time unit, where α > 1. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption is minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a single-processor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case.
---
paper_title: Speed scaling on parallel processors with migration

paper_content:

We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works) on parallel speed scalable processors so as to minimize the total energy consumption. We consider that both preemptions and migrations of jobs are allowed. For this problem, there exists an optimal polynomial-time algorithm which uses as a black box an algorithm for linear programming. Here, we formulate the problem as a convex program and we propose a combinatorial polynomial-time algorithm which is based on finding maximum flows. Our algorithm runs in \(O({ nf}(n)\log U)\) time, where n is the number of jobs, U is the range of all possible values of processors’ speeds divided by the desired accuracy and f(n) is the time needed for computing a maximum flow in a layered graph with O(n) vertices.
---
paper_title: On multi-processor speed scaling with migration: extended abstract

paper_content:

We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. Previous work has focused mostly on the setting where a single variable-speed processor is available. In this paper we study multi-processor environments with m parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. In contrast to a previously known strategy, our algorithm does not resort to linear programming. We develop a fully combinatorial algorithm that relies on repeated maximum flow computations. The approach might be useful to solve other problems in dynamic speed scaling. For the online problem, we extend two algorithms Optimal Available and Average Rate proposed by Yao et al. [16] for the single processor setting. We prove that Optimal Available is αα-competitive, as in the single processor case. Here α>1 is the exponent of the power consumption function. While it is straightforward to extend Optimal Available to parallel processing environments, the competitive analysis becomes considerably more involved. For Average Rate we show a competitiveness of (3\α)α/2 + 2α.
---
paper_title: On the Interplay between Global DVFS and Scheduling Tasks with Precedence Constraints

paper_content:

Many multicore processors are capable of decreasing the voltage and clock frequency to save energy at the cost of an increased delay. While a large part of the theory oriented literature focuses on local dynamic voltage and frequency scaling (local DVFS), where every core’s voltage and clock frequency can be set separately, this article presents an in-depth theoretical study of the more commonly available global DVFS that makes such changes for the entire chip. This article shows how to choose the optimal clock frequencies that minimize the energy for global DVFS, and it discusses the relationship between scheduling and optimal global DVFS. Formulas are given to find this optimum under time constraints, including proofs thereof. The problem of simultaneously choosing clock frequencies and a schedule that together minimize the energy consumption is discussed, and based on this a scheduling criterion is derived that implicitly assigns frequencies and minimizes energy consumption. Furthermore, this article studies the effectivity of a large class of scheduling algorithms with regard to the derived criterion, and a bound on the maximal relative deviation is given. Simulations show that with our techniques an energy reduction of 30% can be achieved with respect to state-of-the-art research.
---
paper_title: Scheduling Precedence Constrained Tasks with Reduced Processor Energy on Multiprocessor Computers

paper_content:

Energy-efficient scheduling of sequential tasks with precedence constraints on multiprocessor computers with dynamically variable voltage and speed is investigated as combinatorial optimization problems. In particular, the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint are considered. Our scheduling problems contain three nontrivial subproblems, namely, precedence constraining, task scheduling, and power supplying. Each subproblem should be solved efficiently so that heuristic algorithms with overall good performance can be developed. Such decomposition of our optimization problems into three subproblems makes design and analysis of heuristic algorithms tractable. Three types of heuristic power allocation and scheduling algorithms are proposed for precedence constrained sequential tasks with energy and time constraints, namely, prepower-determination algorithms, postpower-determination algorithms, and hybrid algorithms. The performance of our algorithms are analyzed and compared with optimal schedules analytically. Such analysis has not been conducted in the literature for any algorithm. Therefore, our investigation in this paper makes initial contribution to analytical performance study of heuristic power allocation and scheduling algorithms for precedence constrained sequential tasks. Our extensive simulation data demonstrate that for wide task graphs, the performance ratios of all our heuristic algorithms approach one as the number of tasks increases.
---
paper_title: Energy-Efficient Scheduling for Real-Time Systems on Dynamic Voltage Scaling (DVS) Platforms

paper_content:

Energy-efficient designs have played import roles for hardware and software implementations for a decade. With the advanced technology of VLSI circuit designs, energy-efficiency can be achieved by adopting the dynamic voltage scaling (DVS) technique. In this paper, we survey the studies for energy-efficient scheduling in real-time systems on DVS platforms to cover both theoretical and practical issues.
---
paper_title: Analytic Clock Frequency Selection for Global DVFS

paper_content:

Computers can reduce their power consumption by decreasing their speed using Dynamic Voltage and Frequency Scaling (DVFS). A form of DVFS for multicore processors is global DVFS, where the voltage and clock frequency is shared among all processor cores. Because global DVFS is efficient and cheap to implement, it is used in modern multicore processors like the IBM Power 7, ARM Cortex A9 and NVIDIA Tegra 2. This theory oriented paper discusses energy optimal DVFS algorithms for such processors. There are no known provably optimal algorithms that minimize the energy consumption of nontrivial real-time applications on a global DVFS system. Such algorithms only exist for single core systems, or for simpler application models. While many DVFS algorithms focus on tasks, this theoretical study is conceptually different and focuses on the amount of parallelism. We provide a transformation from a multicore problem to a single core problem, by using the amount of parallelism of an application. Then existing single core algorithms can be used to find the optimal solution. Furthermore, we extend an existing single core algorithm such that it takes static power into account.
---

Title: A Survey of Offline Algorithms for Energy Minimization under Deadline Constraints
Section 1: Introduction
Description 1: Introduce the importance of energy consumption in computing systems, provide context on power management techniques, and give an overview of the paper’s contributions and structure.

Section 2: Related surveys
Description 2: Discuss existing surveys on energy-aware scheduling and highlight how this survey differs by focusing on offline algorithms for real-time systems.

Section 3: Modeling and notation
Description 3: Provide a unified notation and modeling assumptions for speed scaling and sleep mode problems to be used throughout the survey.

Section 4: Fundamental results
Description 4: Introduce key theoretical concepts and results that are foundational to various power management algorithms.

Section 5: Uniprocessor problems
Description 5: Survey algorithms for minimizing energy consumption in single-processor systems with deadline constraints.

Section 6: Multiprocessor problems
Description 6: Discuss algorithms focused on multiprocessor systems, covering general tasks, tasks with agreeable deadlines, and tasks with precedence constraints.

Section 7: Open problems
Description 7: Highlight unresolved issues and challenges in the field of algorithmic power management, particularly for multiprocessor systems and tasks with precedence constraints.

Section 8: Discussion
Description 8: Summarize the main contributions of the survey and discuss the gap between theory and practice in algorithmic power management.