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 cu rrently envisioned machines will provide an efficient platform for suc h algorithms. These algorithms substantially improve the performance o f iterative methods of solving partial differential equations. We cons ider the domain parallel version of the standard V-cycle multigrid alg orithm on model problems, discretized using finite difference techniqu es in two and three dimensions on block-structured grids of size 10(6) and 10(9), respectively. We develop a set of models of parallel compu tation which reflect the computing characteristics of the current gene ration of massively parallel multicomputers. These models are based on an interconnection network of 256 to 16,384 message passing, ''workst ation size'' processors executing in a SPMD mode. The models, based on the computing characteristics of an architectural class, provide metr ics which balance abstraction with machine specificity. With the mediu m grain parallelism of the current generation and the high fixed cost of an interprocessor communication, our analysis suggests that an effi cient implementation for practical problem sizes requires the machine to support the efficient transmission of long messages (up to 1000 wor ds); otherwise the high initiation cost of a communication must be sig nificantly reduced through an alternative optimization technique. The analysis also suggests that low diameter multistage networks provide l ittle or no advantage over a simple single stage communications networ k. Finally, the analysis suggests that fine grain parallelism and low fixed communication costs may provide more efficiency than medium grai n parallelism with low variable communications costs. (C) 1996 Academi c Press,Inc.