Efficient decomposition and performance of parallel PDE, FFT, Monte Carlo simulations, simplex, and sparse solvers

The authors describe the decomposition of six algorithms: two partial differential equations (PDE) solvers (successive over-relaxation (SOR) and alternating direction implicit (ADI)), fast Fourier transform (FFT), Monte Carlo simulations, simplex linear programming, and sparse solvers. They present the performance results of these algorithms on two shared-memory VAX/VMS multiprocessor prototypes: VAX 6300 series with up to eight processors and M31 with up to 22 processors. It is demonstrated that by efficient decomposition it is possible to achieve high performance for all algorithms on both prototypes. The efficient decomposition techniques applied to optimize the performance of parallel algorithms are described. The performance implications of different cache designs for two multiprocessors are discussed