Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model
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 less than or equal to n greater than or equal to p we present a deterministic BSP* algorithm that is 1-optimal, if n/p greater than or equal to log(2)n. For m>n greater than or equal to p, we present a randomized BSP* algorithm that is 1-optimal with high probability, if m less than or equal to 2(p) and n/p greater than or equal to log(3)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. (C) 1998 Published by Elsevier Science B.V. All rights reserved.
parallel algorithms multisearch bulk synchronous computing data structures