Automatic Data Distribution for Nearest Neighbor Networks

An algorithm for mapping an arbitrary, multidimensional array onto an arbitrarily shaped multidimensional nearest neighbor network of a distributed memory machine is presented. The individual dimensions of the array are labeled with high-level usage descriptors that can either be provided by the programmer or can be derived by sophisticated static compiler analysis. The presented algorithm achieves an appropriate exploitation of nearest neighbor communication and allows for efficient address calculations. We describe the integration of this technique into an optimizing compiler for Modula-2* and derive extensions that render efficient translation of nested parallelism possible and provide some support for thread scheduling. 1 Introduction An important problem facing numerous projects on distributed memory machines is that of distributing array data over the available processors. There is widespread agreement about the two goals of data distribution: (1) Data locality. All data elemen..