Data redistribution and concurrency

The role of data distribution in concurrent computations is twofold: achieving load balanced computations and minimizing the number of synchronization points and/or message exchanges. It is clear that the optimal data distribution is dependent on the particular algorithm. However, when faced with typical application programs several algorithms involving varying types of computation may have to be performed on the same data at different stages of the computation. In between these stages a redistribution of the data may be necessary. Memory is often a constraining factor in highly concurrent machines and there is usually great advantage if the data redistribution can be done in place. In this paper we propose a general in place concurrent data redistribution algorithm and we identify the data distributions that can be mapped into one another by the proposed technique.