Efficient methods for multi-dimensional array redistribution

In many scientific applications, array redistribution is usually required t o enhance data locality and reduce remote memory access on distributed memo ry multicomputers. Since the redistribution is performed at run-time, there is a performance tradeoff between the efficiency of the new data decomposi tion for a subsequent phase of an algorithm and the cost of redistributing data among processors. In this paper, we present efficient methods for mult i-dimensional array redistribution. Based on the previous work, the basic-c ycle calculation technique, we present a basic-block calculation (BBC) and a complete-dimension calculation (CDC) techniques. We also developed a theo retical model to analyze the computation costs of these two techniques. The theoretical model shows that the BBC method has smaller indexing costs and performs well for the redistribution with small array size. The CDC method has smaller packing/unpacking costs and performs well when array size is l arge. When implemented these two techniques on an IBM SP2 parallel machine along with the PITFALLS method and the Prylli's method, the experimental re sults show that the BBC method has the smallest execution time of these fou r algorithms when the array size is small. The CDC method has the smallest execution time of these four algorithms when the array size is large.