Optimizations for stencil algorithms on multi-core systems

General Remarks

This project develops optimization techniques for stencil-based algorithms like the Jacobi and Gauss-Seidel smoothers and the lattice-Boltzmann method (LBM). While much work has been done in the past in this field, the current trend towards multi-core chips with complex cache topologies requires a re-evaluation of existing approaches and the development of new ideas that put the specific features of those processors to use.

Potentials of temporal blocking for stencil-based computations on multi-core systems

Master's thesis at the Georg Simon Ohm University of Applied Sciences Nuremberg.

Author: Markus Wittmann (now RRZE)

Supervisor: Georg Hager (HPC Services).

Abstract:The "DRAM Gap", i.e. the discrepancy between theoretical peak performance and memory bandwidth of a processor chip, has been worsening over the last two decades. This trend is currently even accelerating due to the advent of multi- and many-core processors. Therefore, new algorithms and optimization techniques must be developed in order to diminish the applications' hunger for memory bandwidth. Stencil codes, which are frequently used at the core of fluid flow simulations (like lattice-Boltzmann solvers) and PDE solvers including multi-grid methods, can break new performance grounds by improving temporal locality. This thesis is concerned with several different variants of temporal blocking, with a special emphasis on leveraging shared caches in multi-core environments. The developed optimization methods are thoroughly benchmarked and analyzed on three different processor architectures. Finally it is shown how temporal blocking, whose applicability is traditionally limited to shared-memory systems, can be employed on distributed-memory parallel computers.

Downloads: Poster (on display at SC09, Portland, OR), Thesis.

Publications

G. Wellein, G. Hager, T. Zeiser, M. Wittmann and H. Fehske: Efficient temporal blocking for stencil computations by multicore-aware wavefront parallelization. Proc. COMPSAC 2009. Best Paper Award! DOI:10.1109/COMPSAC.2009.82

M. Wittmann, G. Hager and G. Wellein: Multicore-aware parallel temporal blocking of stencil codes for shared and distributed memory. Accepted for Workshop on Large-Scale Parallel Processing (LSPP) 2010, April 23rd, Atlanta, GA. arXiv:0912.4506

Contact

Project manager:

• Prof. Dr. Gerhard Wellein
  Erlangen Regional Computing Center
  HPC Services
  Martensstr. 1
  91058 Erlangen
  +49 (0)9131 85 28136
  gerhard.wellein@rrze.fau.de