high performance computing on graphics processing units: hgpu.org

Fast, robust and efficient multigrid solvers are a key numerical tool in the solution of partial differential equations discretised with finite elements. The vast majority of practical simulation scenarios requires that the underlying grid is unstructured, and that high-order discretisations are used. On the other hand, hardware is quickly evolving towards parallelism and heterogeneity, even within a single workstation. Commodity CPUs have multiple cores, and GPUs are the most prominent example of current fine-grained parallel architectures. We are convinced that geometric multigrid methods are superior to algebraic multigrid methods, emph{if} their components are designed with respect to the underlying finite element discretisation. Such an approach, which we call emph{finite element geometric multigrid (FE-GMG)}, allows the design and development of numerically optimal solvers. While many multigrid components can be parallelised in a straight forward manner, two components pose severe challenges: Robust and strong smoothers are inherently recursive and sequential, and grid transfer operations (prolongation and restriction) have to be re-formulated for the chosen finite element space and mesh hierarchy. Our approach follows the emph{hardware-oriented numerics} paradigm and we aim at simultaneously maximising numerical and computational efficiency. In this paper, we tackle the second problem and evaluate an implementation technique for geometric multigrid solvers that is based completely on sequences of sparse matrix-vector multiplications. With no loss in performance and only moderately increased memory requirements, this approach allows us to design a multigrid solver that is oblivious of the spatial dimension of the computational domain, the underlying unstructured discretisation grid, and the chosen finite element space. We are thus the first to assemble competitive geometric multigrid solvers for finite element discretisations on unstructured grids that execute very efficiently on both CPUs and GPUs. Our numerical evaluation yields that the emph{FE-GMG} completely assembled by sequences of sparse matrix-vector kernels is able to exploit the parallelism provided by multicore CPUs and GPUs: We gain a speedup of two to three when doubling the amount of memory controllers of the CPU and yet another factor of four to 14 (eight in average) when switching from a multi-core CPU to the GPU. Additionally we show that the numbering of the degrees of freedom can have a huge impact on the performance, up to a factor of 25 on both architectures.