Semi-iterative methods on distributed memory multiprocessor architectures

ABSTRACT

In the parallel ELLPACK (//ELLPACK) project we are developing a library of parallel interative methods for distributed memory multiprocessor systems and software tools for partitioning and allocation of the underlying computations. In this paper we discuss the implementation issues within the //ELLPACK environment and present preliminary performance results of some of the modules on three hypercube based architectures: NCUBE, iPSC/1 and iPSC/2. These results indicate that the iterative methods are capable of delivering close to optimal scaled speed-ups while the combination of concurrent/vector processing can lead to sizable improvements of the overall performance. These experiments have shown that distributed memory systems are capable of solving significantly large problems effectively.

REFERENCES

• Ayka 88: C. Aykanat , F. Özgüner , F. Ercal , P. Sadayappan, Iterative Algorithms for Solution of Large Sparse Systems of Linear Equations on Hypercubes, IEEE Transactions on Computers, v.37 n.12, p.1554-1568, December 1988 [doi>10.1109/12.9733]
• Chris 89: N.P. Chrisochoides, E.N. Houstis, C.E. Houstis, S.M. Kortesis and J.R. Rice, Automatic Load Balanced Partitioning Strategies for PDE Computations, Purdue University CAPO Technical Report CER- 89-7, February 1989.
• Couc 87: A. L. Couch, Seecube User's Manual, Tufts University, Department of Computer Science Report, April 1987.
• Duni 88: T. H. Dunigan, Performance of a Second Generation Hypercube, Tech. Report. ORNL/TM-10881, Oak Ridge National Laboratory, Mathematical Science Section, (1988).
• Farh 87: C. Farhat and E. Wilson, Concurrent Iteratire Solutions of Large Finite Element Systems, Communic. in Applied Numerical Methods 8, (1987), 319-326.
• Gust 88: J. L. Gustafson, G. R. Montry and R. E. Benner, Development of Parallel Methods for a 1024-Processor Hypercube, SiAM J. Sci. Stat. Comp. 9, (1988), 609-638.
• Hous 88a: E. N. Houstis , J. R. Rice , C. C. Christara , E. A. Vavalis, Performance of scientific software, Mathematical aspects of scientific software, Springer-Verlag New York, Inc., New York, NY, 1988
• Hous 88b: E. N. Houstis , J. R. Rice , E. A. Vavalis, A Schwarz splitting variant of cubic spline collocation methods for elliptic PDEs, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1746-1754, January 1989, Pasadena, California, United States [doi>10.1145/63047.63133]
• Hous 89a: E.N. Houstis, T.S. Papatheodorou and J.R. Rice, Parallel ELLPACK: An Expert System for the Parallel Processing of Partial Differential Equations, Math. Comp. Sim ul., 31, (1989), to appear.
• Hous 89b: E.N. Houstis, P.N. Papachiou, J.R. Rice and M.K. Samartzis, Domain Decomposer: A Software Tool for Partitioning PDE Computations Based on Geometry Decomposition Strategies, Purdue University Technical Report, in preparation.
• Kinc 82: David R. Kincaid , John R. Respess , David M. Young , Rober R. Grimes, Algorithm 586: ITPACK 2C: A FORTRAN Package for Solving Large Sparse Linear Systems by Adaptive Accelerated Iterative Methods, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.302-322, Sept. 1982 [doi>10.1145/356004.356009]
• Rice 85: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• Rodr 84: G. Rodrigue and J. Simon, Jacobi splittings and the method of overlapping domains for solving elliptic PDEs, in: Advances in Computer Methods for Partial Differential Equations, Vol. V, ( R. Vichnevetsky, R. S. Stepleman, editor), (1984), 383-386.
• Tang 87: W.P. Tang, Schwarz splitting, a model of parallel computations, Ph.D. Thesis, Stanford University, (1987).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Experimentation, Management, Measurement, Performance, Standardization, Theory