New algorithms and optimization techniques are needed to balance the accelerating trend towards bandwidth-starved multicore chips. It is well known that the performance of stencil codes can be improved by temporal blocking, lessening the pressure on the memory interface. We introduce a new pipelined approach that makes explicit use of shared caches in multicore environments and minimizes synchronization and boundary overhead. For clusters of shared-memory nodes we demonstrate how temporal blocking can be employed successfully in a hybrid shared/distributed-memory environment. 1 Temporal blocking of stencil codes The Jacobi algorithm is a simple method for solving boundary value problems. It serves here as a prototype for more advanced stencil-based methods like the lattice-Boltzmann algorithm (LBM). In three dimensions, one stencil (cell) update is described by Successive sweeps over the computational domain are performed to reach convergence, writing to grids A and B in turn. Counting the usually required read for ownership (RFO) on a write miss, the kernel has a naive code balance of B c = 8/6 W/F (double precision words per flop). However, the actual number of words transferred over the slowest data path (the memory bus) can be reduced to three per stencil update with a suitable spatial blocking scheme. Furthermore, the RFO can be circumvented on current x86-based processor architectures by employing non-temporal store instructions, which bypass the cache hierarchy. These and other well-known standard optimizations like data alignment and SIMD vectorization have been applied for our baseline version of the algorithm and are described in the literature [1, 2] . We use OpenMP-parallel C/C++ code whenever possible, and revert to compiler intrinsics only if necessary, e.g., if the compiler refuses SIMD vectorization because a loop runs backward (as is the case with the compressed grid version of pipelined temporal blocking, which will be described in Sect. 1.3). The memory-bound performance of the baseline code on a given architecture can be easily estimated by assuming that memory bandwidth is the sole limiting factor, and that all other contributions can be hidden behind it. This assumption is valid for current multicore processors if all cores sharing a memory interface are used in a parallel calculation, but may be false for single-threaded code [8] . If the achievable STREAM COPY bandwidth (using non-temporal stores) is M s , a "perfect" baseline Jacobi code (B c = 0.33 W/F) should show a performance of 1
In more general work on stencil implementations, REF explore the explicit use of shared caches in multi-core systems for implementing a pipelined temporal blocking approach for stencil computation.
Multicore-aware parallel temporal blocking of stencil codes for shared and distributed memory
ArXiv
ArXiv
Computer Science