On the structure of parallelism in a highly concurrent PDE solver

Abstract

A parallel multigrid algorithm for solving elliptic partial differential equations is developed and evaluated. A V-cycle multigrid method is altered to increase the degree of parallelism. A numerical analysis of the resulting concurrent-iteration multigrid algorithm is performed; its architectural implications are considered; highly parallel systems without shared memory are examined (including mesh-connected arrays, mesh-shuffle-connected systems, permutation networks, and direct VLSI embeddings); and the results of numerical experiments are presented in tables and graphs.