Efficient Address Generation for Block-Cyclic Distributions

Data-parallel languages, such as High Performance Fortran, are designed to make programming of distributed-memory machines easier, and resulting programs more portable and efficient. Advanced features of these languages require new methods in both compilers and run-time systems. We present efficient techniques for generating local memory addresses, in the exact order as specified by the original program, for computations involving references to arrays with cyclic(k) distribution, the most general regular data distribution provided in data-parallel languages. Our method exploits the repetitive pattern of memory accesses to handle arbitrary affine subscripts, while minimizing the space and time overhead. Extensive experimental results indicate the efficiency of our approach in practice. 1 Introduction Distributed-memory machines are widely regarded as the most promising means for high performance computing. However, the message-passing programming model, typically associated with these ..