Parallelizing algorithms for MIMD architectures with shared memory

ABSTRACT

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.

REFERENCES

• Bal84: Balance 8000 System Technical Summary, Sequent Computer Systems, Beaverton, OR 1984
• Bre88: Brehm J.: Pamllelisierung und Implementierung yon Conjugate Gradient Verfahren for unterschiedliche Multiprozessorarchitekturen, Vortrag anl'figlich des Informatik Colloqiums zur Parallelverarbeitung 1988 in Lessach
• Cha87: Chaxbel Farhat: Computational Engineering Software, AERO 593-3 Lecture Notes, Fall Semester 1987/88, University of Colorado, Boulder 1987
• Duf86: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• Git85: Gita Alaghband: Multiprocessor Sparse L/U Decomposition with Controlled Fill-in, ICASE Report No 85-48, Hampton 1985
• Gol76: Gene H. Golub et. al.: A Generalized Conjugate Gradient Method for the Numerical Solution of Elliptic Partial Differential Equations, in Sparse Matrix Computation, Academic Press, New York 1976
• Gol83: Gene H. Golub et. al.: Matrix Computations, North Oxford Academic, Oxford 1983
• Jor87: Harry F. Jordan: The Force, ECE Technical Report, Computer Systems Design Group, University of Colorado, Boulder 1987
• Hac82: W. Hackbusch et. al.: Multigrid Methods, Proceedings of the Conference held at Cologne, Nov 23-27, 1981, Springer Verlag, Berlin 1982
• Mul86: Multimax Technical Summary, Encore Computer Corporation, Marlboro, MA, 1986

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Design, Measurement, Performance, Theory