Abstract

In embedded systems and data-center systems (systems, for short), it
is widely accepted that energy consumption has become the bottleneck
of system's performance improvement and it is one of the most
significant factors to optimize. Unfortunately, an effective
energy-aware strategy usually has an adverse impact on a job's flow
time or stretch --- two important user-perspective system performance
metrics. In some cases, the more energy is saved by an energy-aware
policy, the more flow time and the larger stretch occur to jobs. In
this paper, we investigate the impact on job processing delay
introduced by power-down energy-saving mechanisms. Specifically, we
study bicriteria algorithms that minimize maximum flow time or largest
stretch under a fixed energy budget and minimize total energy
consumption under an upper bound of flow time or stretch. We develop
optimal offline algorithms to quantitatively balance the
system-perspective performance metric (energy consumption) and the
user-perspective performance metric (flow time and stretch). We also
develop two simple min-energy online algorithms against weakened
adversaries. We prove that (1.) with appropriate extra flow time, an
online algorithm can beat a non-idling offline algorithm, which
achieves the minimum flow time, in terms of the total energy required;
(2.) an optimal deterministic online algorithm, in terms of
competitive ratio with respect to energy consumption, has a bounded
times of optimal stretch.

Speaker Bio

Zhi Zhang is a PhD candidate at George Mason University. Her research
focuses on algorithm design and analysis, mainly on applied scheduling
algorithms and green algorithms. Zhi received her BS and MS in
Computer Science from Wuhan University, China in 2006 and 2008,
respectively.