Minimizing Communications with Q-transformations in Uniform and Affine Stencils

In stencil based parallel applications, communications represent the main overhead, especially when targeting a fine grain parallelization in order to reduce the completion time. Techniques that minimize the number and the impact of communications are clearly relevant. In literature the best optimization reduces the number of communications per step from 3dim, featured by a naive implementation, to 2*dim, where dim is the number of the domain dimensions. To break down the previous bound, in the paper we introduce and formally prove Q-transformations, for stencils featuring data dependencies that can be expressed as geometric affine translations. Q-transformations, based on data dependencies orientations though space translations, lowers the number of communications per step to dim