A GENERAL MATRIX ITERATIVE MODEL FOR DYNAMIC LOAD BALANCING

Many applications require some form of load balancing in order to obta in good performance on parallel computing systems. A number of load ba lancing algorithms have been proposed, and implemented on real systems . However, application developers are in need of a performance tool th at compares and evaluates various balancing algorithms, and helps sele ct the best algorithm for a given application and computing platform. Tn this paper, we propose a matrix iterative model that can represent a wide range of dynamic load balancing algorithms. The model captures the change in task distribution over the processors due to both the ap plication imbalance and load balancing algorithm. We also define perfo rmance measures that capture the costs of executing the parallel appli cation and load balancing algorithm on a given computing platform. The model and the performance measures are used to compare and evaluate v arious load balancing algorithms. in this paper, the model is paramete rized to represent three load balancing algorithms - the random, diffu sion and redistribution algorithms. Model predictions and experimental measurements are compared for the parallel N-body simulation applicat ion. This application is representative of a wide class of scientific applications where time-varying workload distributions are present. Th e model predictions are within 20% of measured values. The performance of the three algorithms are compared, and optimal algorithm parameter s are derived showing how the model can be used to both select an algo rithm and set its parameters.