Parallel Bridging Models and Their Impact on Algorithm Design
Friedhelm Meyer auf der Heide, Rolf Wanka Dept. of Mathematics and Computer Science
and Heinz Nixdorf Institute
University Paderborn
33095 Paderborn, Germany
e-mail: {fmadh, wanka}@upb.de
Abstract
The aim of this paper is to demonstrate the impact of features of parallel computation models on the design of efficient parallel algorithms. For this purpose, we start with considering Valiant's BSP model and design an optimal multisearch algorithm. For a realistic extension of this model which takes the critical blocksize into account, namely the BSP* model due to Bäumker, Dittrich, and Meyer auf der Heide, this algorithm is far from optimal. We show how the critical blocksize can be taken into account by presenting a modified multisearch algorithm which is optimal in the BSP* model. Similarly, we consider the D-BSP model due to de la Torre and Kruskal which extends BSP by introducing a way to measure locality of communication. Its influence on algorithm design is demonstrated by considering the broadcast problem. Finally, we explain how our Paderborn University BSP (PUB) Library incorporates such BSP extensions.
Paper in compressed Postscript format (gzip used):
A4 format
© Copyright 2001 Springer-Verlag. In: Proceedings of the Int. Conf. on Computational Science (ICCS) 2001, Part II, pp. 628-637.