Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones
- 1 October 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 16 (5) , 808-835
- https://doi.org/10.1137/0216053
Abstract
We describe a deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number n of processors as the simulated PRAM, and if the size of the PRAM's shared memory is polynomial in n, each PRAM step is simulated by O(log n) MPC steps or by O((log n)2) steps of the bounded degree network. This improves upon a previous result by Upfal and Wigderson. We also prove an ((log n)2/log log n) lower bound on the number of steps needed to simulate one PRAM step on a bounded degree network under the assumption that the communication in the network is point-to-point.Keywords
This publication has 8 references indexed in Scilit:
- Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memoriesActa Informatica, 1984
- Dynamic parallel memoriesInformation and Control, 1983
- On the power of probabilistic choice in synchronous parallel computationsPublished by Springer Nature ,1982
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- Explicit constructions of linear size superconcentratorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Two theorems on random polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- A Survey of Parallel Machine Organization and ProgrammingACM Computing Surveys, 1977