DATA-PARALLEL LOAD BALANCING STRATEGIES

Programming irregular and dynamic data-parallel algorithms must consid er the effect of data distribution. The implementation of a load balan cing algorithm is quite a difficult task for the programmer. However, a load balancing strategy may be developed independently of the applic ation. The integration of such a strategy into the data-parallel algor ithm 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 algor ithms 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 res erved.