Data Local Iterative Methods For The Efficient Solution of Partial Differential Equations

A cooperation
between

and
.

Funded by
.

Impact of data locality optimizations on red-black Gauss Seidel performance

Overview:

The smoother is one of the most computationally expensive parts of a multigrid algorithm. Therefore, improving the performance of this relatively small module can cause a significant improvement of the performance of the whole multigrid method.

We started our data locality studies with a straightforward implementation of red-black Gauss-Seidel in Fortran. We consider Poisson's equation delta u=f in two dimensions, assuming boundary conditions of Dirichlet type. We chose a uniform grid and discretise the Laplacian operator using the standard 5-point stencil with constant coefficients.

We performed several transformations on the source code and the best performances of all transformations compared to the standard red-black Gauss-Seidel algorithm for different grid sizes on a DEC PWS 500au are shown in the figure below.

Benchmark Results:

MFlops/sec rates for Red-Black Gauss-Seidel

The figure clearly shows that the performance can be improved for every grid size; even for the small ones. However, the greatest improvements can be achieved when the grid does not fit completely in one of the caches of the memory hierachy and the data must be fetched from main memory. In this case the improvement in the MFlops/sec rates can be more than a factor of 4. The table below shows the MFlops/sec rates of different code transformations for several grid sizes.

Working Set Sizes:

All optimized programs try to reuse the data as soon as possible to reduce the size of the working set. The working set is the data which is needed for the current computation plus the data which was loaded for an earlier computation and is needed again later. In general the working set changes during the computation of the program since new data may be needed for computation and old data can be discarded because it will not be reused again in the program.

In the optimal case the whole working set fits in L1 cache during the whole computation. However, in general the working set is to big to completely fit in any of the caches. The figure below shows an overview what amount of data fits in the caches of the DEC PWS 500au. In the case of standard red-black Gauss-Seidel, the working set of the program is equivalent to the whole grid plus the right-hand side of the equation.