Markus Kowarschik, Iris Christadler, and Ulrich Rüde
Computer Science
University Erlangen
Germany
Multigrid methods have been shown to be among the fastest solution methods for certain classes of elliptic partial differential equations. Unfortunately, when applied to reasonably large problems, conventional multigrid implementations typically suffer from a poor utilization of memory hierarchies. Therefore, they commonly run at a rather small fraction of the theoretically available peak performance of the underlying machine.
Our previous research has primarily focused on transformations of the data layout scheme and the data access pattern in order to improve the cache performance of multigrid codes. The application of these techniques does not modify the numerical results of the computations. Note that, in order to achieve efficient code execution in a parallel computing environment, cache performance optimizations must be applied in addition to the common parallelization efforts, such as load balancing, etc.
The approach we will present in this talk goes one step further than our previous efforts and targets the numerical behavior of the multigrid algorithm itself. We will introduce patch-adaptive relaxation strategies that can significantly increase the robustness of the multigrid solver. Our techniques are based on the theory of fully adaptive multigrid methods. By partitioning the grids of the hierarchy into suitably sized patches, we further achieve a better utilization of the cache. Our new algorithms thus combine enhanced robustness with cache-efficient execution, yielding higher execution speed.
We will provide numerical examples as well as performance results. The performance results will be based on the use of profiling tools and cache simulators.