Predicting performance and selecting modes of parallelism: A case study using cyclic reduction on three parallel machines

Academic Article


  • Mapping cyclic reduction, a known approach for the parallel solution of tridiagonal and block tridiagonal systems of equations, onto the MasPar MP-1, nCUBE 2, and PASM parallel processing systems is discussed. Each of these represents a different mode of parallelism that can be used in the design of supercomputers. The MasPar MP-1 is a commercially available SIMD system with near-neighbor and multiplexed-multistage communications networks, the nCUBE 2 is a commercially available MIMD system with a partitionable hypercube communication network, and PASM is an experimental partitionable-SIMD/MIMD mixed-mode machine with a partitionable multistage cube network. Specific issues addressed here are SIMD/MIMD trade-offs, the effect on execution time of increasing the number of processors used, the impact of the interprocessor communications network on performance, the importance of predicting algorithm performance as a function of the mapping used, and the advantages of a partitionable system. Analytical results are validated by experimentation on all three machines. © 1993 Academic Press, Inc.
  • Authors

    Digital Object Identifier (doi)

    Author List

  • Saghi G; Siegel HJ; Gray JL
  • Start Page

  • 219
  • End Page

  • 233
  • Volume

  • 19
  • Issue

  • 3