A Scheduling Model for Reduced CPU Energy

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.

Authors

• F. Frances Yao
• Alan J. Demers
• Scott Shenker

Keywords

• Processor scheduling
• Energy consumption
• Portable computers
• Central Processing Unit
• Computer displays
• Circuits
• Operating systems
• Scheduling algorithm
• Energy conservation
• Personal digital assistants
• Heuristic
• Arrival Time
• Power Function
• Clock Rate
• Online Algorithm
• Single Processor
• Remainder Of This Paper
• Power Consumption
• Constant Speed
• Linear Order
• Optimal Schedule
• Constant Ratio
• Problem Instances
• Canonical Form
• Execution Speed
• Joint Density
• Feasible Schedule
• Portable Computer
• Critical Interval
• Competitive Ratio