Practical Dynamic Load Balancing for Irregular Problems

. In this paper, we present a cohesive, practical load balancing framework that addresses many shortcomings of existing strategies. These techniques are portable to a broad range of prevalent architectures, including massively parallel machines such as the Cray T3D and Intel Paragon, shared memory systems such as the SGI Power Challenge, and networks of workstations. This scheme improves on earlier work in this area and can be analyzed using well-understood techniques. The algorithm operates using nearest-neighbor communication and inherently maintains existing locality in the application. A simple software interface allows the programmer to use load balancing with very little effort. Unlike many previous efforts in this arena, the techniques have been applied to large-scale industrial applications, one of which is described herein. 1 Introduction A number of trends in computational science and engineering have increased the need for effective dynamic load balancing techniques. In par..