A BASIC-CYCLE CALCULATION TECHNIQUE FOR EFFICIENT DYNAMIC DATA REDISTRIBUTION

Array redistribution is usually required to enhance algorithm performa nce in many parallel programs on distributed memory multicomputers. Si nce it is performed at run-time, there is a performance trade-off betw een the efficiency of the new data decomposition for a subsequent phas e of an algorithm and the cost of redistributing data among processors . In this paper, we present a basic-cycle calculation technique to eff iciently perform BLOCK-CYCLIC(s) to BLOCK-CYCLIC(t) redistribution. Th e main idea of the basic-cycle calculation technique is, first, to dev elop closed forms for computing source/destination processors of some specific array elements in a basic-cycle, which is defined as lcm(s, t )/gcd(s, t). These closed forms are then used to efficiently determine the communication sets of a basic-cycle. From the source/destination processor/data sets of a basic-cycle, we can efficiently perform a BLO CK-CYCLIC(s) to BLOCK-CYCLIC(t) redistribution. To evaluate the perfor mance of the basic-cycle calculation technique, we have implemented th is technique on an IBM SP2 parallel machine, along with the PITFALLS m ethod and the multiphase method. The cost models for these three metho ds are also presented. The experimental results show that the basic-cy cle calculation technique outperforms the PITFALLS method and the mult iphase method for most test samples.