Compiling Affine Nested Loops: How to Optimize the Residual Communications After the Alignment Phase?

Minimizing communication overhead when mapping affine loop nests onto distributed memory parallel computers (DMPCs) is a key problem with regard to performance, and many authors have dealt with it. All communications are not equivalent. Local communications (translations), simple communications (horizontal or vertical ones), or structured communications (broadcasts, gathers, scatters, or reductions) are performed much faster than general affine communications onto DMPCs. In this paper, we recall the mapping heuristic given by Dion and Robert which consists in minimizing the number of nonlocal communications and we focus on the next step: as it is generally impossible to obtain a communication local mapping, we show how to optimize residual general communications using structured communications or decompositions into small sequences of simple communications