Scalability analysis of multidimensional wavefront algorithms on large-scale SMP clusters
- 1 January 1999
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We develop a model for the parallel performance of algorithms that consist of concurrent, two-dimensional wavefronts implemented in a message passing environment. The model combines the separate contributions of computation and communication wavefronts. We validate the model on three supercomputer systems, with up to 500 processors, using data from an ASCI deterministic particle transport application, although the model is general to any wavefront algorithm implemented on a 2-D processor domain. We also use the model to make estimates of performance and scalability of wavefront algorithms on 100-TFLOPS computer systems expected to be in existence within the next decade. Our model shows that on a 1-billion-cell problem, single-node computation speed (nor inter-processor communication performance, as is widely believed) is the bottleneck. Finally, we present preliminary considerations that reveal the additional complexity associated with modeling wavefront algorithms on reduced-connectivity network topologies, such as clusters of SMPs.Keywords
This publication has 4 references indexed in Scilit:
- AnSnAlgorithm for the Massively Parallel CM-200 ComputerNuclear Science and Engineering, 1998
- Parallel Solution of Triangular Systems on Distributed-Memory MultiprocessorsSIAM Journal on Scientific and Statistical Computing, 1988
- Diffusion Synthetic Acceleration Methods for the Diamond-Differenced Discrete-Ordinates EquationsNuclear Science and Engineering, 1977
- The parallel execution of DO loopsCommunications of the ACM, 1974