Title: Shared memory simulations with triple-logarithmic delay
Abstract: We consider the problem of simulating a PRAM on a distributed memory machine (DMM). Our main result is a randomized algorithm that simulates each step of an n-processor CRCW PRAM on an n-processor DMM with $$\mathcal{O}$$ log log log n log* n) delay, with high probability. This is an exponential improvement on all previously known simulations. It can be extended to a simulation of an (n log log log n log* n)-processor EREW PRAM on an n-processor DMM with optimal delay $$\mathcal{O}$$ (log log log n log* n), with high probability. Finally a lower bound of Ω(log log log n/log log log log n) expected time is proved for a large class of randomized simulations that includes all known simulations.
Publication Year: 1995
Publication Date: 1995-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 30
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot