Memory-Coalescing Optimization. This section presents a transformation that fixes potential un- coalesced accesses of a map construct, such as map fun inp, where the elements of inp are arrays of similar dimensionality. ≡ One can observe that since map hides the iteration space, any array indexing inside fun would likely be invariant to the loop that implements map. For example, in the left side of Figure 8, DOALL i corresponds to the original map, and the DO j loop implements fun, which processes an inner array of dimension M, indexed by σ(j). Executing the i loop on GPU leads to the access pattern depicted in the left-bottom part of Figure 8, in which B cores in a SIMD-group access in one instruction elements that are 4*M bytes apart from each other, where we assumed for simplicity σ id. We fix this behavior by reshaping uniformly such arrays via transformation T([x,y]) = [x/B,y,x%B], in which x and y cor- respond to the row and column index in the original matrix (since Fortran uses column order, we would write ARR(y,x)). Since B is a power of two the new index is computed using fast arithmetic. In essence, we have trimmed the outermost dimension and added an innermost (row) dimension of size B, the size of the SIMD group, such that one SIMD instruction exhibits coalesced access. The top-right part of Figure 8 shows the transformed code, where we made explicit the SIMD grouping via the DOALL k loop, while the outer DOALL i loop expresses the parallelism among SIMD groups. The bottom-right part of Figure 8 demonstrates that after transformation B consecutive cores access contiguous locations. We observe that this transformation is effective for arrays of any dimensions, as long as the internal indexing is map-loop invariant. For example, assuming that the Brownian-bridge code of Figure 4 is written in map-reduce style, i.e., array expansion is applied to wf and zd, this transformation results in coalesced accesses for arrays wf and zd, despite the indirect indexing exhibited on the dates
