We report on the results of an automatic configuration approach
for implementing complex parallel BSP algorithms.
For this approach, a parallel algorithm is described by a sequence of
instructions and of subproblems that have to be solved by
other parallel algorithms called as subroutines, together with a
mathematical description of its own running time.
There also may be free algorithmic parameters as, e.g., the degree
of trees in used data structures that have an impact on the running time.
As the running time of an algorithm depends on several machine
parameters, on some fixed and on
the choice of the free algorithmic parameters and
on the choice of the parallel subroutines for which the same statement
applies in turn, the actual composition of the parallel program for an actual
parallel machine from all
these ingredients is a difficult task.
We have implemented such a configuration
system using the Paderborn University BSP library
and present as an instructive example the theoretical and experimental
results of implementations of sophisticated minimum spanning tree algorithms.
[PDF, Postscript, BibTex]