Composition of Efficient Nested BSP Algorithms: Minimum Spanning Tree Computation as an Instructive Example
Olaf Bonorden, Friedhelm Meyer auf der Heide, Rolf Wanka Dept. of Mathematics and Computer Science
and Heinz Nixdorf Institute
University Paderborn
33095 Paderborn, Germany
e-mail: {bono, fmadh, wanka}@upb.de
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.
Paper in compressed Postscript format (gzip used):
A4 Paper in pdf format
A4
In: Proceedings of the Int. Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA); Vol. IV, pp. 2202-2208; 2002.