high performance computing on graphics processing units: hgpu.org

Geometric Multigrid (GMG) is an efficient method to solve partial differential equations. It consists of four operations (smooth, residual, restrict and prolongate), which are applied iteratively. All four operations are stencil computations and hence benefit from being executed on many-core architectures like GPUs. Programs executed on a GPU are usually written using low-level programming approaches like OpenCL or CUDA. In order to achieve high performance, expert knowledge is required to manage the hardware details such as the memory and thread hierarchy, exposed to the programmer by these low-level approaches. However, the optimizations that achieve high performance may be different for individual architectures and programs, so tuning for one device often leads to poor performance on other devices. Using the Lift framework is a promising approach for achieving performance portability. Computations are expressed using a small set of reusable parallel primitives. Optimizations are encoded in rewrite rules to be applied automatically in a rewriting process. This thesis demonstrates how the four GMG operations can be expressed as a combination of simple 1-dimensional Lift primitives. In addition to that, well-known optimizations for GMG methods are analyzed. Finally, we express some of them in the functional language of Lift and investigate why the other optimizations are currently not expressible.