page 1  (27 pages)
2to next section

Truly Efficient Parallel Algorithms:

1-Optimal Multisearch for an Extension of the BSP Model*

Armin B?aumker, Wolfgang Dittrich

and Friedhelm Meyer auf der Heide

Department of Mathematics and Computer Science

and Heinz Nixdorf Institute, University of Paderborn
33095 Paderborn, Germany

In this paper we design and analyse parallel algorithms with the goal to get exact bounds on their speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP*, that rewards blockwise communication, and use Valiant's notion of 1-optimality. Intuitively, a 1-optimal parallel algorithm for p processors achieves speed-up close to p. We consider the Multisearch Problem: Assume a strip in 2D to be partitioned into m segments. Given n query points in the strip, the task is to locate, for each query, its segment. For m <= n >= p we present a deterministic BSP* algorithm that is 1-optimal, if np >= log2 n. For m > n >= p, we present a randomized BSP* algorithm that is 1-optimal with high probability, if m <= 2p and np >= log3 n. Both results hold for a wide range of BSP* parameters where the range becomes larger with growing input size n. We further report on implementation work. Previous parallel algorithms for Multisearch were far away from being 1-optimal in our model and did not consider blockwise communication.

1 Introduction

The theory of efficient parallel algorithms is very successful in developing new original algorithmic ideas and analytic techniques to design and analyse efficient parallel algorithms. For this purpose the PRAM has proven to be a very convenient computation model, because it abstracts from communication problems. On the other hand, the asymptotic results achieved, only give limited information about the behaviour of the algorithms on real parallel machines. This is mainly due to the following reasons.

ffl The PRAM cost model (communication is as expensive as computation) is far away from reality, because communication is by far more expensive than internal computation on real parallel machines [5].

*email: fabk,dittrich,, Fax: +49-5251-603514. Supported in part by DFG- Sonderforschungsbereich 376 Massive Parallelit?at: Algorithmen, Entwurfsmethoden, Anwendungen", by DFG Leibniz Grant Me872/6-1, and by the Esprit Basic Research Action Nr 7141 (ALCOM II)