Analysis of multigrid algorithms on massively parallel computers: Architectural implications

We study the potential performance of multigrid algorithms running on massively parallel computers with the intent of discovering whether currently envisioned machines will provide an efficient platform for such algorithms. These algorithms substantially improve the performance of iterative methods of solving partial differential equations. We consider the domain parallel version of the standard V-cycle multigrid algorithm on model problems, discretized using finite difference techniques in two and three dimensions on block-structured grids of size 10⁶ and 10⁹, respectively. We develop a set of models of parallel computation which reflect the computing characteristics of the current generation of massively parallel multicomputers. These models are based on an interconnection network of 256 to 16,384 message passing, "workstation size" processors executing in a SPMD mode. The models, based on the computing characteristics of an architectural class, provide metrics which balance abstraction with machine specificity. With the medium grain parallelism of the current generation and the high fixed cost of an interprocessor communication, our analysis suggests that an efficient implementation for practical problem sizes requires the machine to support the efficient transmission of long messages (up to 1000 words); otherwise the high initiation cost of a communication must be significantly reduced through an alternative optimization technique. The analysis also suggests that low diameter multistage networks provide little or no advantage over a simple single stage communications network. Finally, the analysis suggests that fine grain parallelism and low fixed communication costs may provide more efficiency than medium grain parallelism with low variable communications costs.