Paper Info
Title
Energy efficient deadline scheduling in two processor systems
Abstract
The past few years have witnessed different scheduling algorithms for a processor that can manage its energy usage by scaling dynamically its speed. In this paper we attempt to extend such work to the two-processor setting. Specifically, we focus on deadline scheduling and study online algorithms for two processors with an objective of maximizing the throughput, while using the smallest possible energy. The motivation comes from the fact that dual-core processors are getting common nowadays. Our first result is a new analysis of the energy usage of the speed function OA [15,4,8] with respect to the optimal two-processor schedule. This immediately implies a trivial two-processor algorithm that is 16-competitive for throughput and O(1)-competitive for energy. A more interesting result is a new online strategy for selecting jobs for the two processors. Together with OA, it improves the competitive ratio for throughput from 16 to 3, while increasing that for energy by a factor of 2. Note that even if the energy usage is not a concern, no algorithm can be better than 2-competitive with respect to throughput.
Year
DOI
Venue
2007
10.1007/978-3-540-77120-3_42
ISAAC
Keywords
Field
DocType
deadline scheduling,optimal two-processor schedule,smallest possible energy,competitive ratio,trivial two-processor algorithm,energy usage,energy efficient deadline scheduling,different scheduling algorithm,two-processor setting,processor system,new analysis,interesting result,energy efficient,online algorithm
Online algorithm,Efficient energy use,Computer science,Scheduling (computing),Throughput,Scaling,Competitive analysis,Distributed computing
Conference
Volume
ISSN
ISBN
4835
0302-9743
3-540-77118-2
Citations 
PageRank 
References 
16
0.84
14
Authors
4
Name
Order
Citations
PageRank
Tak-Wah Lam11860164.96
Lap-Kei Lee240621.59
Isaac K. K. To31326.41
Prudence W. H. Wong437438.69