An experimental study of methods for parallel preconditioned Krylov methods

ABSTRACT

High performance multiprocessor architectures differ both in the number of processors, and in the delay costs for synchronization and communication. In order to obtain good performance on a given architecture for a given problem, adequate parallelization, good balance of load and an appropriate choice of granularity are essential. We discuss the implementation of parallel version of PCGPAK for both shared memory architectures and hypercubes. Our parallel implementation is sufficiently efficient to allow us to complete the solution of our test problems on 16 processors of the Encore Multimax/320 in an amount of time that is a small multiple of that required by a single head of a Cray X/MP, despite the fact that the peak performance of the Multimax processors is not even close to the supercomputer range. We illustrate the effectiveness of our approach on a number of model problems from reservoir engineering and mathematics.

REFERENCES

• 1: A. Greenbaum, Solving Sparse Triangular Linear Systems Using Fortran with Pamlllel Eztensions on the NYU Ultmcomputer Prototype, Report 99, NYU Ultracomputer Note, April 1986.
• 2: Rati Chandra, Conjugate gradient methods for partial differential equations., 1978
• 3: D. M. Nicol and J. H. Saltz, Principles for Problem Aggregation and Assignment in Medium Scale Multiprocessors, Technical Report 87-39, ICASE, September 1987.
• 4: Todd Dupont, Richard P. Kendall and H. H. Rachford Jr., An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM Journal on NumericM Analysis, 5(1968), pp. 559-573.
• 5: Howard C. Elman, Iterative methods for large, sparse, nonsymmetric systems of linear equations, 1982
• 6: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• 7: J. $altz, Automated Problem Scheduling and Reduction of Synchronization Delay Effects, Report 87-22, }CASE report, July 1987.
• 8: J. A. Meijerink and H. A. van der Vorst, Guidelines for the usage of incomplete decompositions in solving sets of linear equations as occur in practical problems, Journal of Computational Physics, 44 (1981), pp. 134-155.
• 9: Scientific Computing Associates, PC'GPAK: Benchmarks for the FPS and CRA~/XMP, Technical Report 111, Scientific Computing Associates, New Haven Connecticut, 1987.
• 10: --------, PCGPAK: User's Guide, Technical Report 106, Scientific Computing Associates, New Haven Connecticut, 1984.
• 11: Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]
• 12: 3oel Saltz, Ravi Mirchandaney, Roger M. Smith, David M. Nico{ and Kay Crowley, The Automated Crystal Runtime System: A Framework, Technical Report 588, Yale University Department of Computer Science, January 1988.
• 13: Y. Saad, M. Schultz, Parallel Implementations of Preconditioned Conjugate Gradient Methods, Department of Computer Science YALEU/DCS/TR-425, Yale University, October 1985.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Measurement, Performance