Paper Info
Title
Nonmigratory Multiprocessor Scheduling for Response Time and Energy
Abstract
Energy usage has been an important concern in recent research on online job scheduling, where processors are allowed to vary the speed dynamically so as to save energy whenever possible. Notice that providing good quality of service such as response time (flow time) and conserving energy are conflicting objectives. An interesting problem for scheduling is how to optimize an economic tradeoff of flow time and energy. To this end, the past two years have witnessed significant progress in the single-processor setting, and online algorithms with performance close to optimal have been obtained. In this paper we extend the study of optimizing the tradeoff between flow time and energy to the multi-processor setting. We derive and analyze a simple non-migratory online algorithm that makes use of the classified-round-robin (CRR) strategy to dispatch jobs. Even in the worst case, its performance is within O(log P) times of the optimal migratory offline algorithm, where P is the ratio of the maximum job size to the minimum job size. Technically speaking, this online result stems from a non-trivial solution to an offline problem of eliminating migration, which is also interesting by itself.
Year
DOI
Venue
2008
10.1109/TPDS.2008.115
IEEE Trans. Parallel Distrib. Syst.
Keywords
Field
DocType
sequencing and scheduling,round-robin strategy,response time,scheduling,energy usage,online algorithm,quality of service,energy minimization,analysis of algorithms and problem complexity,dynamic speed scaling,competitive analysis,flow time,nonmigratory multiprocessor scheduling,minimum job size,online result,conserving energy,online computation,online multi-processor scheduling algorithms,simple non-migratory online algorithm,online job scheduling,maximum job size,single-processor setting,dynamic scheduling,scheduling algorithm,multiprocessor scheduling,energy efficiency,cost function,algorithm design and analysis,job scheduling
Online algorithm,Multiprocessor scheduling,Computer science,Efficient energy use,Scheduling (computing),Response time,Real-time computing,Job scheduler,Dynamic priority scheduling,Competitive analysis,Distributed computing
Journal
Volume
Issue
ISSN
19
11
1045-9219
Citations 
PageRank 
References 
5
0.41
32
Authors
4
Name
Order
Citations
PageRank
Tak-Wah Lam11860164.96
Lap-Kei Lee240621.59
Isaac K. K. To31326.41
Prudence W. H. Wong437438.69