Trading Computation for Communication: A Low Communication Algorithm for the Parallel Solution of PDEs Using Range Decomposition, Nested Iteration, and Adaptive Mesh Refinement
David Appelhans
Applied Mathematics, University of Colorado Boulder
Date and time:
Tuesday, November 18, 2014 - 11:00am
Location:
Grandview Conference Room, 1320 Grandview Ave
Abstract:
In this defense I propose a new algorithm for solving PDEs on massively
parallel computers. The Range Decomposition (RD) algorithm uses nested
iteration and adaptive mesh refinement locally before performing a global
communication step. Only several such steps are observed to be necessary
before reaching a solution within a small multiple of discretization error.
The target application is peta- and exascale machines where traditional
parallel numerical PDE communication patterns stifle scalability. The RD
algorithm uses a partition of unity to equally distribute the error, and
thus, the work. The computational advantages of this approach are that
the decomposed problems can be solved using nested iteration and any
multigrid cycle type, in parallel, without any communication until the
partitioned solutions are summed. This offers potential advantages in the
paradigm of expensive communication but very cheap computation. This
talk introduces the method and explains the details of the communication step.
Two performance models are developed and numerical results for
the Laplace problem with Dirichlet boundary conditions demonstrate the
enhanced performance.