A framework for efficient data redistribution on distributed memory multicomputers

Array redistribution is required often in programs on distributed memory pa rallel computers. It is essential to use efficient algorithms for redistrib ution; otherwise the performance of the programs will degrade considerably. The redistribution overheads consist of two parts: index computation and i nter-processor communication. In this paper, by using a notation for the lo cal data description called an LDD, we propose a framework to optimize the array redistribution algorithm both in index computation and inter-processo r communication. That is, our work makes an effort to optimize not only the computation cost but also communication cost for array redistribution algo rithms. We present an efficient index computation method and generate a sch edule that minimizes the number of communication steps and eliminates node contention in each communication step. Some experiments show the efficiency and flexibility of our techniques.