Startseite > Publikationen > Publikationen

Publikationen

Meyer auf der Heide, Friedhelm;Scheideler, Christian;Stemann, Volker:

Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations.

STACS 1995 : S. 267-278, Jul. 1995

Abstract

This paper presents and analyses efficient implementations of a so-called direct process on distributed memory machines (DMMs) that yields
- a simulation of an n-processor PRAM on an n-processor optical crossbar DMM with delay O(log log n),
- a simulation of an n-processor PRAM on an n-processor arbitrary DMM with delay O( (log log n) / (log log log n) ),
- an implementation of a static dictionary on an n-processor arbitrary DMM with parallel access time of O(log* n).
We further prove a lower bound for executing the above process, showing that our implementations are optimal.

Dateien

hni1868.pdf



Bibtex

@article{hniid=1868,
author = {Meyer auf der Heide, Friedhelm and Scheideler, Christian and Stemann, Volker},
title = {Exploiting Storage Redundancy to Speed Up Randomized Shared Memory Simulations},
journal = {STACS 1995},
pages = {267-278},
month = jul,
year = {1995},
}

BibTeX in die Zwischenablage kopieren

Permalink

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