Computer Science Department
School of Computer Science, Carnegie Mellon University


Evaluation of Task Assignment Policies for Supercomputing Servers:
The Case for Load Unbalancing and Fairness

Bianca Schroeder, Mor Harchol-Balter

March 2000

Keywords: Task assignment, supercomputing, clusters, load sharing, load balancing, job scheduling, supercomputing workloads, heavy-tailed behavior, high variance, distributed servers, fairness, contrary behavior.

While the MPP is still the most common architecture in supercomputer centers today, a simpler and cheaper machine configuration is growing increasingly common. This alternative setup may be described simply as a collection of multiprocessors or a distributed server system. This collection of multiprocessors is fed by a single common stream of jobs, where each job is dispatched to exactly one of the multiprocessor machines for processing.

The biggest question which arises in such distributed server systems is what is a good policy for assigning jobs to host machines. Many task assignment policies have been proposed, but not systematically evaluated under supercomputing workloads. In this paper we start by comparing existing task assignment policies using a trace-driven simulation under supercomputing workloads. We use analysis to validate our results and to provide intuition. We find that while the performance of supercomputing servers varies widely with the task assignment policy, none of the above policies perform as well as we would like.

We observe that all task assignment policies proposed thus far aim to balance load among the hosts. We propose a policy which purposely unbalances load among the hosts, yet, counter-to-intuition, is also fair in that it achieves the same expected slowdown for all jobs -- thus no jobs are biased against. We evaluate this policy again using both trace-driven simulation and analysis. We find that the performance of the load unbalancing policy is significantly better than the best of those policies which balance load.

18 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by