
MOVES: Software Modeling and Verification
(Informatik 2)

Home Page of the Pamusk Project
The Pamusk Project

What means Pamusk?

Pamusk stands for Parallel
Adaptive Multigrid Algorithms
with Skeletons. Algorithmic Skeletons are
algorithmic abstractions common to a series of applications which can be
implemented in parallel. In the Pamusk Project we use a data parallel
approach to implement skeletons for adaptive multigrid algorithms on a
parallel computer with distributed memory.

Intention

The itention of this project is to work out wheather skeletons are suited for
the implementation of data parallel realworld applications or not. We want
to show that it is much easier to develope such code with the skeleton based
declarative approch instead of using a lowlevel imperative language like C or
Fortran. The basic idea is to "hide" all communication inside the skeletons.
After designing and implementing the skeletons they can be integrated into
an application program in a sequential manner. For example, now you may
think in terms like "I want to move a part of a grid from one processor
to another" instead of "How I have to implement the
communication algorithm for moving a object from one processor to another?".
Another important criterion regarding to numerical algorithms is
runtime efficency. Unfortunately, runtime systems of common functional
languages like Haskell are (still) not fast enough
to execute time expensive multigrid algorithms with adaptive refinement.
A better approach is the use of an imperative language that is extended by the
neccessary functional features. We use Skil that
is a extension of C. The SkilCompiler generates pure CCode.

Adaptive Multigrid

Multigrid algorithms are the best known iterative solvers for partial
differential equations (pde).
At first step we have to perform a
discretization of the pde over a coarse grid inside the given domain.
With given boundary conditions we can compute an initial solution on
the coarse grid nodes using an exact solver for the equation system
that results from discretization. For discretization we use
Finite Elements because of the flexibility and the good mathematical
background of this approach. Here we use triangles as elements because
we can perform a flexible discretization even in the case of curved
boundaries. The finite elements method works also with other shaped elements
in 2D or 3D.
Now we have to refine the coarse grid and initialize the nodes of the
fine grid with the known values from the coarse grid. After that we start
a certain number of multigrid cycles. in each cycle we compute a solution
on the finest grid by a certain step of iterations. These iterations are
called relaxations. After that the computed values have to be
restrict to the next coarser level. If we reach the coarsest level,
we compute a new exact solution, otherwise we perform a relaxation phase.
Now the multigrid algorithm walks through the grid hierarchy up to the
finest grid level. The inverse operation to restriction is called
prolongation. After a prongation step we perform relaxations
on the current level.
We repeat this two phases (refinement and multigrid cycles) until the
solution is precise enough. For this decision we have to estimate the
algebraic error of the iterated solution against the exact solution
by a solver for linear equation systems.

Problems

The implementation of adaptive multigrid algorithms on a parallel computer
requires some additionally features:
 Identification
For a good multigrid computation performance we need overlapping of grid parts.
Hence, after creating (a new part of) a grid, for example when grid refinement
was performed, grid vertices or elements have to be identified if they
represent the same object on different processors. We need special
skeletons to do this work for abritary grid objects.
 Dynamic Load Balancing
After adaptive refinement some processors may hold more computation nodes than
others. Therefore, we have to move parts of a grid from one
processor to another. First the dynamic load balancing algorithm
detect the portion of grid vertices and elements that have to be moved.
At next the physical movment has to be executed by calling a skeleton.
Last but not least we have to take care about consistence of distributed
vertices and elements.
 Computation Consistency
During multigrid iteration we have to keep consistency of all distributed data
on all processors. We need skeletons working on virtual interfaces which
connect all instances of a distributed object.
 Error Computation
For checking how exact the iterated solution are we have to compute the
global maximum algebraic error value over the hole grid.
This implies the use of a fold skeleton which folds all error
values at the computation nodes together. The fold function has to be
a associative and commutative binary function, for instance the maximum
function or the summation. Clearly, we have to implement communication
inside the fold skeleton for yielding a global result.
 Multigrid Components
The components of a multigrid cycle, namely relaxation, restriction, and
interpolation, are locally restricted operations on one or two levels
of a multigrid. Hence we need a skeleton with the functionallity of a local
map. For updating values of distributed nodes we need the
communication via the virtual interfaces, too.

Enviornment

 Language
We implement the skeletons and the application algorithms in
Skil. Skil is a extension of C by
functional concepts: type polymorphism, higher order functions, and partial
application. Furthermore, Skil allows to declare parallel data structures.
More information about Skil you will find on the
Skil Home Page.
 Computer
Currently we use a PC cluster with 16 processor nodes connected
by Fast Ethernet. Later we will use a Cray T3E for runtime measurements.
 Message Passing
For the neccessary communication inside the skeletons we include
the free MPIlibrary
mpich 1.2.0.

Support

The Pamusk project is supported by the
Graduiertenkolleg "Informatik und Technik" at the RWTH Aachen.

Publications


T. Richert:
Skil: Programming with Algorithmic Skeletons  A Practical
Point of View
in
Draft Proceedings of the 12th International Workshop on
Implementation of Functional Languages,
Aachen, Germany, Aachener
Informatik Bericht, 200007, pp. 1530.
Abstract,
Paper

T. Richert:
Dynamic Load Balancing for Parallel Adaptive Multigrid Solvers
with Algorithmic Skeletons
in EuroPar 2000  Parallel Processing, LNCS 1900,
pp. 325328, SpringerVerlag, London.
Abstract,
BibTeXEntry

T. Richert:
Using Skeletons to Implement a Parallel Multigrid Method with
Overlapping Adaptive Grids
in Proceedings of the International Conference PDPTA2000,
Vol. 3, pp. 13451351, CSREA Press, Las Vegas, Nevada, USA.
Abstract,
Paper,
BibTeXEntry

T. Richert:
Management of Distributed Dynamic Data with Algorithmic Skeletons
in
Parallel Computing  Proceedings of the International Conference ParCo99
,
pp. 375382, Imperial College Press, London.
Abstract,
Paper,
BibTeXEntry

G. H. Botorog:
Deriving Skeletons for Multigrid Algorithms
in Proceedings of PDCN '97, IASTED/Acta Press, 1997, pp.
180183.
Abstract,
Paper
Webmaster 
Last modified: Thu Jun 7 11:20:26 CEST 2001

