Concepts for parallel numerical solution of PDEs
Guntram Berti
Institute of Mathematics
BTU Cottbus
Universit"atsplatz 3-4
03044 Cottbus, Germany
berti@math.tu-cottbus.de
The parallelization of numerical code still is a demanding programming task.
Often, it is performed on a per-application basis
by implicitely building the requirements of the specific algorithms
into the corresponding data structures.
However, many of the algorithms used in this field
exhibit strong structural similarities.
A uniform treatment
exploiting these similarities
is developed in this paper.
In the field of numerical PDE solution,
geometric partitioning or domain decomposition in a wider sense
is the parallelization paradigm of choice.
We present the concept of
distributed overlapping grids (DOGs),
both structured and unstructured,
to offer high-level support for this strategy.
Appropriate data structures,
such as overlap ranges ensuring data locality,
encapsulate the technical details stemming from data distribution.
The important parameters of distributed execution
can be controlled by the application programmer with the aid of
powerful high-level primitives.
In particular, they offer a simple way
to determine the order in which to perform calculations
and to synchronize data structures,
both with respect to the overlap regions.
The concrete shape of the necessary overlap essentially depends on the
local access pattern (stencil) of the involved algorithms.
We present an easy way of describing these stencils also for
the unstructured grid case, thus effectively decoupling overlap generation
from algorithmic details.
It follows that the approach is applicable to many grid-based applications
involving locally operating algorithms of a certain data-parallel type.
The concept of distributed overlapping grids not only applies to
physical distribution on MIMD-type architectures.
A similar distribution pattern is typical of
composite or multiblock grids,
hybrid grids (structured/unstructured coupling),
and grids for problems with periodic boundaries.
Hybrid grids, in particular, form the basic building blocks for
the coupling of different types of numerical algorithms
in different regions of the computational domain,
thus allowing to combine computational efficiency
with geometric flexibility.
A central trait of our approach is a unifying, abstract view on
grids and geometric data structures, that can be described by
a generic interface.
An implementation of DOGs based on this interface
is parameterized by the concrete type of the grid data structures.
Thus, a single implementation acts as a generic wrapper
for sequential grid representations that provide this abstract interface,
augmenting them by distributed functionality.
The generic implementation comprehends data structures for managing
overlap subranges and algorithms to determine the shape of these ranges.
Generic progamming methodology also enables an implementation
that is largely independent of space dimension.
Currently, there exist implementations in C++ for the 2D case,
covering the distributed-memory
and the composite-grid context,
both possibly with periodic boundaries.
These implementations are built on top
of a general distributed grid layer,
thus sharing a large amount of code.
The versatility of the approach is demonstrated by various applications
from numerical simulation of conservation laws,
like inviscid two-component gas flow.