Evaluation of Data Distribution Patterns in Distributed-Memory Machines

Determining an appropriate data distribution among different memories is critical to the performance of data-parallel programs on distributedmemory machines. By analyzing the computational load of data arrays and the communication complexity of various data movement operations in a program, this paper suggests a first-order cost model for determining a small set of appropriate data distribution patterns among many possible choices. A new data distribution specification, namely CYBLOCK, is proposed to enhance the expressiveness of data distribution specifications being proposed in High Performance Fortran. Cost analysis of two case studies: a linear system solver and a Purdue-set benchmark loop, are used to illustrate the proposed evaluation method. The model correctly predicts the relative performance of the case studies when implemented with various regular data distributions on an nCUBE2 multicomputer. 1 Introduction Distributed-memory machines, such as the Intel Paragon, TMC CM-5,..