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

A cooperation
between

and
.

Funded by
.

rb2.F Program Description

File Name:

Description:

When implementing the standard red-black Gauss-Seidel algorithm, the usual practice is to do one complete sweep of the grid from bottom to top updating all the red nodes and then one complete sweep updating all of the black nodes. The first point to note is that as a red node in row i is updated the black node in row i-1 directly underneath it may also be updated. If a 5-point stencil is placed over one of the black nodes (see figure) then we can see that all of the red points it touches are up to date (as long as the red node above it is up to date). Consequently, we update a red node in a row i and the black node in row i-1 directly underneath it in pairs in all rows i (except the first row of the grid) before moving to the next red node in row i.

Comment:

Instead of doing a red sweep and then a black sweep, we just do one sweep of the grid updating the red and black nodes as we move through. The consequence is that the grid must be transfered from main memory to cache only once per update sweep instead of twice, as long as at least four lines of the grid fit in the cache. Three lines must fit in the cache to provide the data for the update of the black points and one additional line for the update of the red points in the line above the three lines.

An additinal effect which can improve the data locality is that the compiler might keep the value of the two updated nodes in a register, so that the update of the black node saves 2 load operations. Since 14 memory operations are required for the two update operations (6 loads and 1 store for each update) about 15% of all memory operations can be saved.

Results: