Message Scheduling for Irregular Data Redistribution in Parallelizing Compilers(Parallel/Distributed Programming Models, Paradigms and Tools, Paradigms and Tools, <Special Section> Parallel/Distributed Computing and Networking)

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
2006-02-01