PARADIGM: A compiler for automatic data distribution on multicomputers

Abstract

One of the most challenging steps in developing a parallel program for a distributed memory machine is determining how data should be distributed across processors. Most of the compilers being developed to make it easier to program such machines still provide no assistance to the programmer in this difficult and machine-dependent task. We have developed PARADIGM, a compiler that makes data partitioning decisions for Fortran 77 procedures. A significant feature of the design of PARADIGM is the decomposition of the data partitioning problem into a number of sub-problems, each dealing with a different distribution parameter for all the arrays. This paper presents the algorithms that, in conjunction with the computational and the communication cost estimators developed by us, determine those distribution parameters. We also present results obtained on Fortran procedures taken from the Linpack and Eispack libraries, and the Perfect Benchmarks. We believe these are the first results demonstrating the success of automatic data partitioning on a significant class of Fortran procedures.