Startseite > Publikationen > Publikationen


Dietzfelbinger, Martin;Meyer auf der Heide, Friedhelm:

Simple, Efficient Shared Memory Simulations.

SPAA 1993 : S. 110-119, Jul. 1993


We present three shared memory simulations on distributed memory machines (DMMs), which use universal hashing to dietribute the shared memory cells over the memory modules of the DMM. We measure their quality in terms of delay, time-processor efficiency, memory contention (how many requests have to be satisfied by one memory module per simulated step) and simplicity. Further we take into consideration different rules for resolving access conflicts at the modules of the DMM, in particular the c-collision rule motivated by the idea of communicating between processors and modules using an optical crossbar. All simulations are very simple and deterministic (except for the random choice of the hash functions). In particular, we present the first "deterministic" time-processor optimal simulations with delay O(log n), both on Arbitrary DMMs and 2-collision DMMs. (These models are defined in the paper. ) The central idea for the latter simulation also yields a simple "deterministic" simulation of an n-processor PRAM on an n-processor 3-collision DMM with delay bounded by O(log log n) with high probability. For the time analysis of the simulations we utilize a new combinatorial lemma, which may be of independent interest. The lemma concerns events defined by properties of the color classes in random colorings of finite sets. Such events are not independent; the lemma shows that in an important special case such events are "negatively correlated", and thus, for the pupose of upper bounds on certain probabilities, may be treated as if independent.




author = {Dietzfelbinger, Martin and Meyer auf der Heide, Friedhelm},
title = {Simple, Efficient Shared Memory Simulations},
journal = {SPAA 1993},
pages = {110-119},
month = jul,
year = {1993},

BibTeX in die Zwischenablage kopieren