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 real-world 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 low-level 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 Skil-Compiler generates pure C-Code.

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 MPI-library 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, 2000-07, pp. 15-30.
Abstract, Paper
T. Richert:
Dynamic Load Balancing for Parallel Adaptive Multigrid Solvers with Algorithmic Skeletons
in Euro-Par 2000 - Parallel Processing, LNCS 1900,
pp. 325-328, Springer-Verlag, London.
Abstract, BibTeX-Entry
T. Richert:
Using Skeletons to Implement a Parallel Multigrid Method with Overlapping Adaptive Grids
in Proceedings of the International Conference PDPTA2000,
Vol. 3, pp. 1345-1351, CSREA Press, Las Vegas, Nevada, USA.
Abstract, Paper, BibTeX-Entry
T. Richert:
Management of Distributed Dynamic Data with Algorithmic Skeletons
in Parallel Computing - Proceedings of the International Conference ParCo99 ,
pp. 375-382, Imperial College Press, London.
Abstract, Paper, BibTeX-Entry
G. H. Botorog:
Deriving Skeletons for Multigrid Algorithms
in Proceedings of PDCN '97, IASTED/Acta Press, 1997, pp. 180-183.
Abstract, Paper

Webmaster

Last modified: Thu Jun 7 11:20:26 CEST 2001

Webmaster

Disclaimer

Last modified: 2001-06-07 09:21 UTC