Message Scheduling for Irregular Data Redistribution in Parallelizing Compilers

Hui WANG  Minyi GUO  Daming WEI  

IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.2   pp.418-424
Publication Date: 2006/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Parallel/Distributed Computing and Networking)
Category: Parallel/Distributed Programming Models, Paradigms and Tools
parallel computing,  parallel compiler,  GEN_BLOCK,  data redistribution,  list algorithm,  

Full Text: PDF(269.3KB)
>>Buy this Article

In parallelizing compilers on distributed memory systems, distributions of irregular sized array blocks are provided for load balancing and irregular problems. The irregular data redistribution is different from the regular block-cyclic redistribution. This paper is devoted to scheduling message for irregular data redistribution that attempt to obtain suboptimal solutions while satisfying the minimal communication costs condition and the minimal step condition. Based on the list scheduling, an efficient algorithm is developed and its experimental results are compared with previous algorithms. The improved list algorithm provides more chance for conflict messages in its relocation phase, since it allocates conflict messages through methods used in a divide-and-conquer algorithm and a relocation algorithm proposed previously. The method of selecting the smallest relocation cost guarantees that the improved list algorithm is more efficient than the other two in average.