Abstract
In many scientific applications, array redistribution is usually required to enhance data locality and reduce remote memory access in many parallel programs on distributed memory multicomputers. We present a new processor mapping technique (PMT) to minimize the communication cost for BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) array redistribution and vice versa. The main idea of the PMT is first to develop mapping functions for computing a new rank of each destination processor. Based on the mapping functions, a new sequence of destination processors can be derived to minimize the amount of data exchange in a redistribution. The proposed mapping technique can handle redistribution with different source and destination processor sets and to be extensible to multidimensional arrays. We present a theoretical model to analyze the performance improvement of the PMT. To evaluate the performance of the proposed technique, we have implemented the PMT on an IBM SP2 parallel machine. The experimental results show that the PMT can provide performance improvement over a wide range of redistribution problems