Multigrid algorithms on massively parallel computers
Lesley R. Matheson · Princeton University eBooks · 1994
This thesis examines the potential performance of multigrid algorithms, a set of techniques to accelerate the convergence of the iterative methods, on massively parallel computers by critically analyzing a set of parallel multigrid algorithms on three classes of parallel models of computation. The set of algorithms includes standard multigrid algorithms and several more sophisticated algorithms designed specifically for massively parallel execution. The three sets of models include the abstract random access models and two practical models of parallel computation, based on the architectural characteristics of the existing and the proposed generation of massively parallel computers. The analysis produces several algorithmic and architectural conclusions and, in addition, offers insights on efficient implementation. It suggests that standard multigrid methods outperform algorithms designed specifically for massively parallel execution, regardless of architectural characteristics. The analysis suggests that the high fixed cost of a network communication in the current generation substantially degrades performance and that in order for these machines to be efficient platforms for practical multigrid applications the average cost per byte of a communication must be lowered. The analysis suggests that optimized implementation strategies differ for each architectural class: fine grain machines with high variable communications costs motivate optimized domain-to-processor mappings, while medium grain machines with high fixed communications costs motivate optimized domain partitions. These results strongly motivate this type of analysis. Using practical models which strike a novel balance between abstraction and machine specificity provides more accurate information than the use of abstract models and broader information than implementation. The analysis shows that parallel models of computation which are based on the common characteristics of an architectural class can deliver substantive information which can be used in the design of both efficient algorithms and effective computers. Finally, this thesis considers the massively parallel solution of unstructured multigrid problems. Unstructured meshes facilitate the solution of problems around the complex geometries of many practical multigrid applications. The final chapter focuses the issues involved in trying to adapt multigrid techniques to triangular and tetrahedral meshes for computation on massively parallel computers.