Campus Event Calendar
Event Entry
What and Who
Sleep with Guilt and Work Faster to Minimize Flow plus Energy
Lap-Kei Lee
The University of Hong Kong
AG1 Mittagsseminar (own work)
Lap-Kei Lee received his PhD degree in Computer Science from
the University of Hong Kong in 2009. His research interests
are design and analysis of algorithms, especially on online
scheduling and data streams. He will join MPI this fall.
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 24 June 2009
13:00
30 Minutes
E1 4
024
Saarbrücken
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. Providing
good quality of service such as 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 few years have witnessed significant progress
on minimizing total flow time plus energy, which is referred to as
flow-energy scheduling.
Besides speed scaling, energy saving can also be achieved by allowing
a processor to enter a low-power sleep state, yet waking up requires
extra energy. We extend the study of flow-energy scheduling to a model
that allows both sleep management and speed scaling. Our main result
is a sleep management algorithm called IdleLonger, which works online
for a processor with one or multiple levels of sleep states. IdleLonger
works in both clairvoyant and non-clairvoyant settings. We show how to
adapt two existing speed scaling algorithms AJC (for the clairvoyant
setting) and LAPS (for the non-clairvoyant setting) to the new model.
The adapted algorithms, when coupled with IdleLonger, are shown to be
O(1)-competitive clairvoyant and non-clairvoyant algorithms for
minimizing flow plus energy on a processor that allows sleep management and speed scaling.
The above results are based on the traditional model with no limit
on processor speed. If the processor has a maximum speed, the problem
becomes more difficult as the processor, once overslept, cannot rely
on unlimited extra speed to catch up the delay. Nevertheless, we are
able to enhance IdleLonger and AJC so that they remain O(1)-competitive
for flow plus energy under the bounded speed model. As a remark,
non-clairvoyant scheduling in the bounded speed model remains open.
online job scheduling, where processors are allowed to vary the
speed dynamically so as to save energy whenever possible. Providing
good quality of service such as 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 few years have witnessed significant progress
on minimizing total flow time plus energy, which is referred to as
flow-energy scheduling.
Besides speed scaling, energy saving can also be achieved by allowing
a processor to enter a low-power sleep state, yet waking up requires
extra energy. We extend the study of flow-energy scheduling to a model
that allows both sleep management and speed scaling. Our main result
is a sleep management algorithm called IdleLonger, which works online
for a processor with one or multiple levels of sleep states. IdleLonger
works in both clairvoyant and non-clairvoyant settings. We show how to
adapt two existing speed scaling algorithms AJC (for the clairvoyant
setting) and LAPS (for the non-clairvoyant setting) to the new model.
The adapted algorithms, when coupled with IdleLonger, are shown to be
O(1)-competitive clairvoyant and non-clairvoyant algorithms for
minimizing flow plus energy on a processor that allows sleep management and speed scaling.
The above results are based on the traditional model with no limit
on processor speed. If the processor has a maximum speed, the problem
becomes more difficult as the processor, once overslept, cannot rely
on unlimited extra speed to catch up the delay. Nevertheless, we are
able to enhance IdleLonger and AJC so that they remain O(1)-competitive
for flow plus energy under the bounded speed model. As a remark,
non-clairvoyant scheduling in the bounded speed model remains open.
Contact
Ho-Leung Chan
--email hidden
passcode not visible
logged in users only
Ho-Leung Chan, 06/03/2009 23:03 -- Created document.