Fast load balancing on a PRAM

Abstract

Consider the following setting: 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 tasks is achieved. Ignoring rescheduling overhead the tasks can be completed in O(1) time. Thus the batch execution problem captures some basic cooperation obstacles of the PRAM model. The paper presents a load balancing algorithm for solving the batch execution problem. The algorithm runs in O(lg lg n) time and achieves, with overwhelming probability, an almost flat distribution, i.e., O(1) tasks for each processor. The model of computation used is the CRCW-PRAM. Nevertheless, the only requirement from the implementation is that the concurrent-write operation is permitted; no assumption is made about its result.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>