Efficient address sequence generation for two-level mappings in High Performance Fortran

Data-parallel languages like High Performance Fortran allow users to specify mappings of arrays by first aligning elements to an abstract Cartesian grid called templates and then distributing the templates across processors. Code generation then includes the generation of the sequence of local addresses accessed on a processor. Address sequence generation for non-unit alignment strides, referred to as the two-level mapping problem, is difficult. We present efficient solutions to the problem of address generation for two-level mapping for general CYCLIC(k) distribution. Our approach involves the construction of pattern tables which incurs negligible runtime overhead compared to other existing solutions for this problem. We use two applications of the integer lattice-based method developed by Thirumalai and Ramanujam (1996) to generate the pattern of accesses using a variety of techniques. Extensive experiments demonstrate that the techniques presented in this paper significantly outperform current solutions to the two-level mapping problem