Startseite > Publikationen > Publikationen

Publikationen

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

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

Theoretical Computer Science 203 (2): S. 175-203, Jun. 1998

Abstract

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=1810,
author = {B{\"a}umker, Armin and Dittrich, Wolfgang and Meyer auf der Heide, Friedhelm},
title = {Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSB model.},
journal = {Theoretical Computer Science},
volume = {203 (2)},
pages = {175-203},
month = jun,
year = {1998},
}

BibTeX in die Zwischenablage kopieren

Permalink

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