Information Technology Reference
In-Depth Information
In this work we propose to study the impact on real-world scenarios of both
execution time and energy consumption uncertainties when considering system
performance and energy eciency objectives. We evaluate a set of online and
oine variants of scheduling algorithms proposed in [16] which simultaneously
consider both objectives. To the best of our knowledge, this is the first work to
evaluate energy consumption uncertainty in a computing scheduling problem.
4 Robustness of Energy Aware Scheduling Heuristics
In this work we consider three well-known scheduling approaches which can be
classified as
o
ine
,
online greedy
,and
online batch
[12]. The oine approach
assumes all tasks are known beforehand, hence the scheduling algorithm needs
only to be executed once and is able to consider all the tasks simultaneously for
the scheduling decisions. This approach is definitely the best in an uncertainty
free problem, since the scheduling algorithm is provided with absolutely all the
available information for making scheduling decision. Unfortunately, because the
scheduling algorithm is executed only once, it is unable to dynamically adjust
the scheduling to cope with uncertainty values.
On the other hand, in the online approach tasks are not known by the schedul-
ing algorithm until they arrive. This requires the scheduling algorithm to be
executed multiple times for completely scheduling a task workload. We tackle
the online scheduling problems using two different techniques, one is a greedy
technique and the other is a batch oriented technique. In the online greedy ap-
proach, tasks are scheduled one at a time as soon as they arrive and are never
rescheduled. This approach is very simple and straightforward, and is able to re-
act to some degree to uncertainty in the data. On the downside, the information
available to the scheduler for making the scheduling decisions is minimal.
The online batch approach tackles some of the previously presented problems.
In this approach the scheduling algorithm is re-executed after a predefined time
step, all the tasks that arrive in a given time-step are delayed, are grouped
as a batch, and are scheduled together by the scheduling algorithm. This way
the online problem is treated as a succession of smaller oine problems. We
consider two further improvements to this approach. The first being that in
every scheduling batch not only the tasks that arrive in that time step are
considered by the scheduler, but also all the tasks from previous batches already
scheduled but which have not started their execution (i.e. are still queued). The
second improvement is that the scheduling algorithm is not executed in every
time step, it is executed only if in the current time step some meaningful event
has occurred (i.e. at least one task has finished or at least a new task has arrived).
In this work we evaluate five different scheduling algorithms following the pre-
vious approaches. For the oine and online batch approaches we considered three
multiobjective two-phase list-scheduling algorithms proposed in [16]: MaxMin,
MaxMIN, and SuffMIN. Because a two-phase approach is not applicable to the
online greedy approach, two simple single-objective algorithms were proposed:
Min and MIN. The algorithms work as follows:
