Data parallel load balancing strategies

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. We propose load distribution data-parallel algorithms for a class of irregular data-parallel algorithms called stack algorithms. Our algorithms allow the use of regular and/or irregular communication patterns to exchange the works between processors. The results of theoretical analysis of these algorithms are presented. They allow different load balancing algorithms to be compared and the identification of criteria to choose between them. (C) 1998 Elsevier Science B.V. All rights reserved.