Exploiting storage redundancy to speed up randomized shared memory simulations. (English) Zbl 1379.68133
Mayr, Ernst W. (ed.) et al., STACS 95. 12th annual symposium on theoretical aspects of computer science, Munich, Germany, March 2–4, 1995. Proceedings. Berlin: Springer-Verlag (ISBN 3-540-59042-0). Lecture Notes in Computer Science 900, 267-278 (1995).
Summary: 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(\frac{\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^\ast n)\).
We further prove a lower bound for executing the above process, showing that our implementations are optimal.
For the entire collection see [Zbl 0813.68028].
– 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(\frac{\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^\ast n)\).
We further prove a lower bound for executing the above process, showing that our implementations are optimal.
For the entire collection see [Zbl 0813.68028].
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68M07 | Mathematical problems of computer architecture |
