Truly Efficient Parallel Algorithms: c-Optimal Multisearch for an Extension of the BSP Model (Extended Abstract)
Armin Bäumker, Wolfgang Dittrich, Friedhelm Meyer auf der Heide · 1995
) Armin Baumker, 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 speed-ups on real machines. For this purpose we define an extension of Valiant's BSP model, BSP*, that rewards blockwise communication, and uses Valiant's notion of c-optimality. Intuitively a c-optimal parallel algorithm for p processors achieves speed-up close to p=c. 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 we present a deterministic BSP* algorithm that is 1-optimal, if n =\\Omega (p log 2 p). For m ? n, we present a randomized BSP* algorithm that is (1 + ffi)-optimal for arbitrary ffi ? 0, m 2 p and n =\\Omega (p log 2 p). Both r...