Applications Of Block Relaxation
Authors: Buzbee B.L. , Boley D. , Parter S.V. 
Published: December 2007

Successful realization of the potential performance of a vector processor often necessitates performance of a vector processor often necessitates assembly language programming. In this paper we show how successive line overrelaxation can be implemented in Fortran on the CRAY-1 such that during its execution, it may perform as many as 30 million floating point operations per second. We also consider the solution of elliptic finite difference approximations in three dimensions with the assumption that the total number of mesh points is on the order of 106. Under this assumption, mesh data must be stored on disk and the overall computational process becomes I/O bound. This leads us to consider application of block relaxation techniques that minimize the number of times that the data must be accessed from disk.

Introduction

Successful realization of the potential performance of a vector processor can be difficult. In performance of a vector processor can be difficult. In general, algorithms that execute with high arithmetic efficiency on vector processors must "fit the architecture" of them and be carefully programmed in assembly language. For example, successive point overrelaxation of the classical five-point difference approximation can be implemented on the CRAY-1 such that the computer may perform as many as 90 million floating point operations during its execution. To achieve this performance level, a redblack ordering of points must be used and the algorithm programmed in assembly language with meticulous attention to architectural details. However, assembly language programming is human intensive, difficult to maintain, and nonportable, causing both managers and scientists to disfavor its usage. In this paper, we show how to implement successive line paper, we show how to implement successive line overrelaxation (SLOR) in Fortran on the CRAY-1 such that the computer may perform as many as 30 million floating point operations (megaflops) during its execution. This appears to be a reasonable compromise between high performance and ease of implementation. We also consider the solution of elliptic finite difference approximations in three-space dimensions with the assumption that the total number of mesh points is approximately 106. Under this assumption points is approximately 106. Under this assumption the mesh data will have to be stored on disk and the overall computation will become I/O bound. The latter leads us to consider algorithms that minimize the number of iterations performed, that is, the number of times the disk must be accessed. Two forms of block relaxation can achieve this goal while maintaining some ease of implementation.

VECTORIZATION OF SLOR

Consider the solution of

(1)

in two-space dimensions on the unit square with a(x,y) greater than 0 and Dirichlet boundary condition u(x,y) = g(x,y). We use the five-point approximation

(2)

with h = delta x = delta y = 1/(N + 1), N a positive integer, and. We assume that the reader is familiar with SLOR (see Ref. 2, Section 6.4). Because of our assumptions, each iteration of SLOR requires solution of a diagonally dominant tridiagonal system along each mesh line in one of the coordinate directions. The solution of a tridiagonal system involves recursion, and recursion does not easily lend itself to vectorization. However, if we adopt an odd/even ordering of lines all the tridiagonal systems associated with odd(even) lines are mutually independent and can be solved simultaneously. By solving these systems simultaneously, we can achieve vectorization, that is, recursions become recursions on vectors of length equal to the number of systems being solved.