Abstract
We consider the problem of online dynamic power management that provides hard realtime guarantees for multiprocessor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a nonmigrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energyefficient solutions for realtime multiprocessor systems.
First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59.
Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a tradeoff between the energyefficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(hk) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)competitive algorithm.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2014:4460,
author = {JianJia Chen and MongJen Kao and D.T. Lee and Ignaz Rutter and Dorothea Wagner},
title = {{Online Dynamic Power Management with Hard RealTime Guarantees}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {226238},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4460},
URN = {urn:nbn:de:0030drops44607},
doi = {10.4230/LIPIcs.STACS.2014.226},
annote = {Keywords: EnergyEfficient Scheduling, Online Dynamic Power Management}
}
Keywords: 

EnergyEfficient Scheduling, Online Dynamic Power Management 
Collection: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) 
Issue Date: 

2014 
Date of publication: 

05.03.2014 