|
Abstract : |
Abstract Programming irregular and dynamic data-parallel algorithms requires to take data distribution into account. The implementation of a load balancing algorithm is a quite difficult task for the programmer. However, a load balancing strategy may be developed independently of the application. The integration of such a strategy in 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 a comparison of the different load balancing algorithms and the identification of criterion for the choice of a load balancing algorithm., |
