Programming irregular and dynamic data-parallel algorithms must consider the effect of data distribution. The implementation of a load balancing algorithm is quite a difficult task for the programmer. However, a load balancing strategy may be developed independently of the application. The integration of such a strategy into the data-parallel algorithm may be relevant to a library or a data-parallel compiler run-time.
In the frame of the DPLB project, we proposed many load distribution data-parallel algorithms for a class of irregular data-parallel algorithms called stack algorithms. These algorithms allow the use of regular and/or irregular communication patterns to exchange the works between processors.
Theoretical analysis of these algorithms have been realized. These analysis have led to comparison between the algorithms (in term of cost and quality) which have identified criteria to chose an algorithm in a given situation.
The theorical results have been empirically verified by experiments on a MasPar parallel computer. We have implemented several problems representative of the stack algorithms. These experiments have confirmed our proposals on the choice of a load-balancing strategy for a given architecture or a given problem.
Data-Parallel Load Balancing Strategies, Parallel Computing, 24(11):1665-1684, october 1998.
Distribution Dynamique de
Données sur Machines SIMD, Thèse de doctorat (PhD Thesis), Cyril
Fonlupt, December 1994, (in French).