Fast Load Balancing on a PRAM

We consider the following problem: n processors of a PRAM are given n independent tasks. Each task can be executed in constant time by a single processor. The distribution of tasks among the processors is unknown; each processor has information only about its set of tasks. The batch execution problem is to reschedule the tasks so that quickest execution of all the tasks will be achieved. Ignoring the overhead required for determining the redistribution pattern and the redistribution time itself, the tasks' execution can be done in O (1) time. Thus the batch execution problem captures a basic cooperation obstacles of the PRAM model. This paper solves the batch execution problem by using a novel object dispersal idea for crafting a load balancing algorithm ( as well as several extensions): the load balancing algorithm moves tasks between the processors and outputs in an almost even distribution, i.e., when the algorithm completes its run, each processor has O (1) tasks. The total run time is O (log log n) with overwhelming probability. The algorithm and the techniques presented are expected to serve as useful building blocks in the design of other efficient parallel algorithms. Particularly, the load balancing algorithm can be employed as a general tool for achieving optimal speedup, and for eliminating scheduling difficulties from parallel algorithms.