Scan directed load balancing for highly-parallel mesh-connected computers

Abstract : Scan Directed Load Balancing is a new, locality-preserving, dynamic load balancing algorithm for grid based computations on mesh connected parallel computers. Scans are used to efficiently determine what areas of the machine are heavily loaded and what areas are lightly loaded, and to organize the movement of data. Data is shifted along the mesh in a regular fashion to balance the load. The Locality Property of the algorithm guarantees that all the neighbors of a data point on the grid are stored either on the same processor, or on a processor that is directly connected to it. Scan Directed Load Balancing is applicable to both SIMD and MIMD mesh-connected parallel computers, and has been implemented on the MasPar MP-1. We present some theoretical bounds achieved by the algorithm as well as the algorithm's performance on a particular image processing problem, edge-directed diffusion. Our experiments show that the algorithm is effective in improving the load distribution for real problems, while the efficiency of the original grid-based computation is preserved by the locality property.