Mor Harchol-Balter, Carnegie Mellon University
Department of Computer Science
Carnegie Mellon University
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
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.
- Workflow Status: Published
- Created By: Mike Alberghini
- Created: 12/20/2012
- Modified By: Fletcher Moore
- Modified: 10/07/2016