Startseite > Publikationen > Publikationen

Publikationen

Bäumker, Armin;Dittrich, Wolfgang;Meyer auf der Heide, Friedhelm:

Truly Efficient Parallel Algorithms: c-Optimal Multisearch for an Extension of the BSP Model.

ESA 1995 : S. 17-30, Jul. 1995

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 = Ω(p log² p). For m > n, we present a randomized BSP* algorithm that is (1 + δ)-optimal for arbitrary δ > O, m ≤ 2^(p) and n = Ω(p log² p). Both results hold for a wide range of BSP* parameters where the range becomes larger with growing input sizes m and n. We further report on implementation work in progress. Previous parallel algorithms for Multisearch were far away from being c-optimal in our model and do not consider blockwise communication.

Dateien

hni1810.pdf



Bibtex

@article{hniid=1862,
author = {B{\"a}umker, Armin and Dittrich, Wolfgang and Meyer auf der Heide, Friedhelm},
title = {Truly Efficient Parallel Algorithms: c-Optimal Multisearch for an Extension of the BSP Model},
journal = {ESA 1995},
pages = {17-30},
month = jul,
year = {1995},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/1862