Efficient algorithms for block-cyclic array redistribution between processor sets

Run-time array redistribution is necessary to enhance the performance of pa rallel programs on distributed memory supercomputers. In this paper, we pre sent an efficient algorithm for array redistribution from cyclic(x) on P pr ocessors to cyclic(Kx) on Q processors. The algorithm reduces the overall t ime for communication by considering the data transfer, communication sched ule, and index computation costs. The proposed algorithm is based on a gene ralized circulant matrix formalism. Our algorithm generates a schedule that minimizes the number of communication steps and eliminates node contention in each communication step. The network bandwidth is fully utilized by ens uring that equal-sized messages are transferred in each communication step. Furthermore, the time to compute the schedule and the index sets is signif icantly smaller. It takes O(maz(P, Q)) time and is less than 1 percent of t he data transfer time. In comparison, the schedule computation time using t he state-of-the-art scheme (which is based on the bipartite matching scheme ) is 10 to 50 percent of the data transfer time for similar problem sizes. Therefore, our proposed algorithm is suitable for run-time array redistribu tion. To evaluate the performance of our scheme, we have implemented the al gorithm using C and MPI on an IBM SP2. Results show that our algorithm perf orms better than the previous algorithms with respect to the total redistri bution time, which includes the time for data transfer. schedule, and index computation.