Renaming and Dispersing: Techniques for Fast Load Balancing

✍ Scribed by J. Gil

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 775 KB
• Volume: 23
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1994.1128

✦ Synopsis

Consider the following situation: (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 the quickest execution of all tasks is achieved. This problem captures some basic cooperation obstacles of the PRAM model since, without rescheduling overhead, all the tasks can be completed in (O(1)) time. The solution presented in this paper is an (O(\lg \lg n)) time load balancing algorithm which achieves, with overwhelming probability, an almost flat distribution, i.e., (O(1)) tasks for each processor. We introduce two novel techniques which are of an independent interest: renaming-a randomized scheme for an approximate compaction, and dispersing-a gather-scatter paradigm for distribution smoothing. The model of computation used in the CRCW PRAM. The concurrent-write submodel is Rовust; i.e., if two or more processors write into the same cell at the same time then no prediction can be made about the cell contents. (\mathbb{e} 1994) Academic Press. Inc.