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 3^dim, 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.