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

A cooperation
between

and
.

Funded by
.

rb4.F Program Description

File Name:

Description:

The algorithms rb2.F and rb3.F both try to reuse the data of the red update sweep in the black sweep soon enough so that the data is still in the cache. They do this by melting the operations for the red and black update sweeps together. However, if several successive red-black Gauss-Seidel relaxations are performed the data in the cache is not reused between different relaxation sweeps if the grid is to big to fit in the cache. The present algorithm addresses this issue.

Assume that we melt two red-black Gauss-Seidel sweeps together. We start in a situation where we have updated the first rows in pairs (see figure above; circles indicate number of performed relaxations). In this situation we are able to update the red points in row 1 the second time. We now continue to update the red nodes in row 4. Once all of the red nodes in row 4 have been updated all of the black nodes in row 3 can be updated. Then all red nodes in row 2 are updated the second time and as a consequence also the black nodes in row 1 are updated the second time.

We now are in a wavefront like situation where we have updated some of the lines once and some twice. Then we update the (red) nodes in line 5 and cascade down three rows updating alternately black and red nodes. In this way, we move the wavefront throught the grid until we reach the last row of the grid (step 9). The height of the wavefront is the number of simultaneously performed update sweeps. The width of the wavefornt is twice the number of update sweeps. In the shown case of two simultaniously performed update sweeps this means that the wavefront is 4 rows wide. At the top of the grid (step 10 to 15) the wavefront shrinks down to one single row. So that at the end of the relaxation sweep only the black nodes in the last row remains for update.

The technique can be generalized so that the nodes can be updated m times in one sweep throught the grid obtaining the same results we would get if m sweps of the standard red-black Gauss-Seidel algorithm were applied.

Comment:

Instead of doing m successive sweeps through the grid updating each node once we do just one sweep throught the grid updating each node m times. Hence, the grid is transfered from main memory to the cache once instead of m times. However, this is only correct if m*2+2 rows of the grid fit in the cache.

Results: