Compiler Techniques for Determining Data Distribution and Generating Communication Sets on Distributed-Memory Machines

This paper is concerned with designing efficient algorithms for determining data distribution and generating communication sets on distributed memory multicomputers. First, we propose a dynamic programming algorithm to automatically determine data distribution at compiling time. The proposed algorithm also can determine whether data redistribution is necessary between two consecutive DO-loop program fragments. Second, we propose closed forms to represent communication sets among processing elements for executing doall statements, when data arrays are distributed in a restricted block-cyclic fashion. Our methods can be included in current compilers and used when programmers fail to provide any data distribution directives. Experimental studies on a nCUBE-2 multicomputer are also presented.