Parallelizing algorithms for MIMD architectures with shared memory

The solution of a system of linear equations Ax = b is an important application in scientific computation. It arises for the numerical solution of self adjoint problems using finite difference or finite element methods for discretization. For realistic problems the coefficient matrix A is sparse most of the times, i.e. a large number of its elements are zero. The three commonly used classes of algorithms to solve the linear system of equations are direct methods, semi-iterative methods and iterative methods which differ in their numerical properties and their computer implementations. The multiprocessor L/U Decomposition for sparse systems was implemented by Gita Alaghband [Git85] as an example for a parallelized direct method. In this paper we will present examples for efficient parallelizations of iterative and semi-iterative algorithms and their implementations on various MIMD shared memory architectures. The iterative methods generate a sequence of approximate solutions which converge to the exact solution. To improve the rate of convergence the Multigrid approach [Hac80] is used as an accelerator. Semi-iterative methods operate in an iterative manner with the property of finite termination in exact arithmetic. The Conjugate Gradient methods shown in this paper are among the most popular representatives of this class of algorithms. They are usually not as robust as direct methods but there are computational advantages over methods that require the factorization of the coefficient matrix A.

First we present FORCE [Jor87] as an example for a portable parallel language, then, in section three, the implementation of the algorithms on three MIMD shared memory architectures is described and finally runtime measurements and speedup calculations are carried out in section four.