WIRELESS AND PORTABLE DEVICES DEPEND ON???

Many wireless and portable devices depend on the limited power supplied by the battery. Dynamic voltage scaling (DVS) is an effective method to increase battery life by reducing the power consumption of a processor. Specifically, DVS reduces the energy consumption of a CMOS processor by dynamically controlling its supply voltage. The power consumed per CPU cycle can be expressed as P = kCV 2 f, where k is a constant, C the total capacitance of wires and transistor gates, V the supply voltage, and f the clock frequency. DVS technology has already been incorporated into many processors produced by companies including Transmeta, AMD, and Intel. Changing a processor’s supply voltage also changes its speed, since the relationship between clock frequency and supply voltage is f ∝ (V − Vt) 2 /V , where Vt is the threshold voltage. As a result, DVS may hurt the performance of some systems in a significant way, in particular, real-time systems where some deadlines are hard. In past work, many algorithms have been proposed to apply DVS to general purpose and soft real-time systems only, Applying DVS to hard real-time systems is more diffi- cult. When a DVS algorithm reduces CPU speed to save energy, it must guarantee that all jobs still meet their deadlines. In the past few years, a large number of algorithms are proposed, e.g., [23, 8, 9, 10, 21, 1, 11, 5, 6, 18, 19, 25, 12, 20, 24]. Although these algorithms have demonstrated the benefits of applying DVS to hard real-time systems, they generally only apply to some specific real-time scheduler. There has not been any algorithm designed to work with different real-time schedulers. The objective of this paper is to propose an integrated approach for applying DVS to hard real-time systems. Using this approach, we derive unified algorithms that work with different real-time schedulers. We illustrate the generality of the approach by applying it to RM and EDF schedulers; we shall derive the optimal off-line DVS algorithms for these real-time scheduling policies. Specifically, we shall propose the definition of two functions: the available cycle function (ACF) and the required cycle function (RCF). The values of these two functions are derived from the parameters of the task set and the scheduling policy used to dispatch the tasks of the system. These functions help us to capture the workload of a real-time system by characterizing an envelope: they constrain the range of a speed function so that if the CPU executes at the speed defined by the function, then there is no idle cycle and no job misses its deadline. Using ACF and RCF, we formulate the energy minimization problem as a constrained nonlinear optimization problem. We prove that for strictly convex power functions, which are the case for all known power models, we can simplify the formulation of the problem. We propose an algorithm to solve the problem and to derive the optimal speed function that minimizes energy consumption. The algorithm is shown to work with both EDF and RM. Since the static algorithm is based on the worst-case budget, we also propose a novel, online, dynamic algorithm to reclaim slack cycles which are generated by early completion of jobs; by a job, we mean an instance of a recurring task (periodic or otherwise) in a schedule. The dynamic algorithm lowers CPU speed whenever slack cycles are available; the new speed will not cause any missed deadline or extra idle cycles. The time complexity of the algorithm is O(1). Furthermore, the algorithm may trade runtime cost for energy savings. It can be improved, with added complexity so that an optimal CPU speed solution is always found at any time. Again, the dynamic algorithm works with both EDF and RM.