A Practical Approach to Dynamic Load Balancing

This paper presents a cohesive, practical load balancing framework that improves upon existing strategies. These techniques are portable to a broad range of prevalent architectures, including massively parallel machines such as the Cray T3D/E and Intel Paragon, shared memory systems such as the SGI PowerChallenge, and networks of workstations. As part of the work, an adaptive heat diffusion scheme is presented as well as a task selection mechanism that can preserve or improve communication locality. Unlike many previous efforts in this arena, the techniques have been applied to two large-scale industrial applications on a variety of multicomputers. In the process, this work exposes a serious deficiency in current load balancing strategies, motivating further work in this area. Keywords: Dynamic load balancing, diffusion, massively parallel computing, irregular problems 1 Introduction A number of trends in computational science and engineering have increased the need for effective dyn..