
Truly Efficient Parallel Algorithms:
1Optimal 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
Abstract
In this paper we design and analyse parallel algorithms with the goal to get exact bounds on
their speedups 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 1optimality. Intuitively,
a 1optimal parallel algorithm for p processors achieves speedup 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 1optimal, if np >= log2 n. For m > n >= p, we present a
randomized BSP* algorithm that is 1optimal 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 1optimal 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,fmadhg@unipaderborn.de, Fax: +495251603514. Supported in part by DFG Sonderforschungsbereich 376 Massive Parallelit?at: Algorithmen, Entwurfsmethoden, Anwendungen", by DFG Leibniz Grant Me872/61, and by the Esprit Basic Research Action Nr 7141 (ALCOM II)