Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model

AbstractIn 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⩾log2n. For m>n⩾p, we present a randomized BSP∗ algorithm that is l-optimal with high probability, if m⩽2p and n/p⩾log3n. 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