A Data Partitioning Algorithm for Distributed Memory Compilation

This paper proposes a compiler strategy for mapping FORTRAN programs onto distributed memory computers. Once the available parallelism has been identified, it has to be scheduled so as to minimise overhead. The minimisation of different costs will suggest different data and computation partitions. This is further complicated, as the effectiveness of the partition will depend on later compiler optimisations. For this reason, partitioning is at the crux point of compilation and has led several researchers to propose that it be left to the user. It is our contention that it is possible to automatically determine a good data partition and furthermore to make use of the analysis in later optimisation stages. This paper describes an automatic data partition algorithm which is based on four different analysis techniques. By determining the relative merit of each form of analysis, a data partitioning decision is made. By integrating this algorithm into an overall compilation strategy, effectiv..