WG2011/M17Kronawitter

Many problems in computational science and engineering involve elliptic partial differential equations. Multigrid is presently considered the most efficient method for their solution. However, the concrete multigrid algorithm and its implementation depend highly on the underlying problem and hardware.

Project ExaStencils aims at a compiler and underlying code generation framework capable of generating automatically highly parallel and efficient geometric multigrid solvers from an abstract description, while selecting the most performant options for the target platform.

The optimizations required must be able to deal with both compute-bound and bandwidth-bound codes. For the former, a redundancy elimination applied to the body of the loop nest is helpful. Different techniques are implemented in current production compilers. To improve performance further, ExaStencils adds a stencils-specific, compiler-external redundancy elimination, including a loop-carried variant.

An optimization of bandwidth-bound codes benefits from an increase of data locality, for which the polyhedron model for loop transformation is perfect. However, in the domain of stencil codes, existing techniques fail to yield optimal or often even just bearable results. As an alternative, we propose a new, optimized, multi-dimensional polyhedral search space exploration. Along with a set of filters specifically for the domain of stencil codes, the exploration effort can be dramatically reduced without significantly impairing its performance.