A simple load balancing scheme for task allocation in parallel machines

A collection of local workpiles (task queues) and a sim-ple load balancing scheme is well suited for schedul-ing tasks in shared memory parallel machines. Task scheduling on such machines has usually been done through a single, globally accessible, workpile. The scheme introduced in this paper achieves a balancing comparable to that of a global workpile, while minimiz-ing the overheads. In many parallel computer archi-tectures, each processor has some memory that it can access more efficiently, and so it is desirable that tasks do not mirgrate frequently. The load balancing is simple and distributed: When-ever a processor accesses its local workpile, it performs a balancing operation with probability inversely propor-tional to the size of its workpile. The balancing op-eration consists of examining the workpile of a random processor and exchanging tasks so as to equalize the size of the two workpiles. The probabilistic analysis of the performance of the load balancing scheme proves that each tasks in the system receives its fair share of com-putation time. Specifically, the expected size of each local task queue is within a small constant factor of the average, i.e. total number of tasks in the system divided by the number of processors.