Surprising Results on Task Assignment in Server Farms under
High Variability Workloads
Mor Harchol-Balter
Computer Science Dept.
Carnegie Mellon
Tuesday, February 02, 2010
4:30 - 5:30 PM
Terman Engineering Center, Room 453
Abstract:
It is well-known that when job size variability is high, one needs to
prevent short jobs from getting stuck behind long jobs. In a server
farm setting, one way to achieve this goal is to allocate short jobs
their own server (or set of servers). This is the theory behind the
popular Size Interval Task Assignment policy (SITA) for server farms,
which assigns each server a unique size range, so that short jobs are
given isolation from long ones. The SITA policy is prevalent
throughout compute server farms and manufacturing systems, whenever
job size variability is high. The higher the job size variability, the
more important it is to provide short jobs some isolation from long
ones, via a SITA policy, or some variation thereof.
This talk questions the above common wisdom. To understand what's
going on, we study the performance of task assignment policies, in the
limit, as the variability of job sizes (service demands) approaches
infinity. Results in this limiting regime reveal that the SITA policy
can be far inferior to much simpler greedy policies, like
Least-Work-Left (LWL), for many common job size distributions,
including a range of Pareto distributions. Regimes are also defined
where SITA's performance is good, and here simple closed-form bounds
are proved on its performance. Towards the end of the talk we will
also consider the performance of SITA variants/hybrids.
Parts of this work appeared in ACM SIGMETRICS 2009.
JOINT WORK WITH:
Alan Scheller-Wolf and Andrew Young
BIO:
Mor Harchol-Balter is Associate Department Head of the Computer
Science Department at Carnegie Mellon University. She received her
doctorate from the Computer Science department at the University of
California at Berkeley under the direction of Manuel Blum. She is a
recipient of the McCandless Chair, the NSF CAREER award, the NSF
Postdoctoral Fellowship in the Mathematical Sciences, multiple best
paper awards, and several teaching awards, including the Herbert
A. Simon Award for Teaching Excellence. She is heavily involved in the
ACM SIGMETRICS research community, and recently served as Technical
Program Chair for SIGMETRICS. Mor's work focuses on designing new
resource allocation policies (load balancing policies, power
management policies, and scheduling policies) for server farms and
distributed systems in general. Her work spans both queueing analysis
and systems implementation, and emphasizes integrating measured
workload distributions into the problem solution.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html