Analysis of the Multigrid FMV Cycle on Large-Scale Parallel Machines

Abstract

On serial computers it is well known that the multigrid FMV cycle is preferable to the V cycle both asymptotically and in practical use over a wide range of applications. However, on massively parallel machines, the parallel efficiency of the FMV (full multigrid V cycle) scheme is noticeably lower than that of the V cycle due to a large percentage of time spent on coarse grids. Thus the question arises: are the additional coarse grid computations within the FMV cycle warranted on massively parallel machines? To answer this, a number of issues are addressed regarding parallel FMV cycles: what efficiencies can be achieved; how do these compare with V cycle efficiencies; are FMV cycles still preferable to V cycles in a massively parallel environment? A model is used to analyze the efficiency of both FMV and V cycles as a function of relaxation efficiency. Using this model, the standard FMV grid-switching criterion is modified to incorporate the efficiency of the coarse grid processing. Numerical results obtained from a multigrid implementation on a 1024-processor nCUBE 2 are used in conjunction with the model to quantify the performance and efficiency of the FMV cycle. Finally, comments are made regarding limitations of parallel processors based on FMV efficiencies.

Keywords

Related Publications