ALCOMFT-TR-02-46

Olaf Bonorden, Friedhelm Meyer auf der Heide and Rolf Wanka
Composition of Efficient NestedBSP Algorithms: Minimum Spanning Tree Computation as an InstructiveExample
Paderborn. Work package 2. May 2002.

Abstract: 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 in the Paderborn University BSP library and present as an instructive example the theoretical and experimental results of implementations of sophisticated minimum spanning tree algorithms.

Postscript file: ALCOMFT-TR-02-46.ps.gz (68 kb).