Efficient algorithms for multi-dimensional block-cyclic redistribution of arrays

We present a uniform framework for a classical problem, redistribution of a multi-dimensional array. Using a generalized circulant matrix formalism, we derive efficient direct, indirect and hybrid contention-free communication schedules. Our indirect schedule reduces the number of communication steps significantly compared with the previous approaches. Our approach exploits the regularity of the block-cyclic redistribution to minimize the index computation overheads. For the case of 2-d redistribution, when the block size increases by factors of K₁ and K₂ along each dimension and the process topology remains fixed, our indirect schedule performs the redistribution in O(log(K₁K₂)) communication steps. For the case of fixed block size and the processor topology is transposed, our indirect schedule results in O(log(L/G)) communication steps. Implementations of our algorithms on the IBM SP-2 show superior performance over previous approaches