A survey of PRAM simulation techniques
TJ Harris - ACM Computing Surveys (CSUR), 1994 - dl.acm.org
The Parallel Random Access Machine (PRAM) is an abstract model of parallel computation
which allows researchers to focus on the essential characteristics of a parallel architecture …
which allows researchers to focus on the essential characteristics of a parallel architecture …
Deterministic Simulations of PRAMs on Bounded Degree Networks
KT Herley, G Bilardi - SIAM Journal on Computing, 1994 - SIAM
The problem of simulating a PRAM with n processors and memory size m\geqslantn on an n-
node bounded degree network is considered. A deterministic algorithm is presented that …
node bounded degree network is considered. A deterministic algorithm is presented that …
Efficient deterministic and probabilistic simulations of PRAMs on linear arrays with reconfigurable pipelined bus systems
In this paper, we present deterministic and probabilistic methods for simulating PRAM
computations on linear arrays with reconfigurable pipelined bus systems (LARPBS). The …
computations on linear arrays with reconfigurable pipelined bus systems (LARPBS). The …
Work-optimal simulation of PRAM models on meshes
V Leppänen, M Penttonen - Nordic Journal of Computing, 1995 - dl.acm.org
Memory access is the bottleneck in the simulation of shared memory on a distributed
memory model. We show that EREW, CREW, and CRCW PRAM models can be simulated …
memory model. We show that EREW, CREW, and CRCW PRAM models can be simulated …
Constructive deterministic PRAM simulation on a mesh-connected computer
A Pietracaprina, G Pucci, JF Sibeyn - Proceedings of the sixth annual …, 1994 - dl.acm.org
We present a constructive deterministic simulation of a PRAM with n processors and m= n α
shared variables, 1< α≤ 2, on an n-node mesh-connected computer where each node hosts …
shared variables, 1< α≤ 2, on an n-node mesh-connected computer where each node hosts …
[PDF][PDF] Deterministic P-RAM simulation with constant redundancy
SW Hornick, FP Preparata - Proceedings of the first annual ACM …, 1989 - dl.acm.org
In this paper, we show that distributing the memory of a parallel computer and, thereby,
decreasing its granularity allows a reduction in the redundancy required to achieve polylog …
decreasing its granularity allows a reduction in the redundancy required to achieve polylog …
[PDF][PDF] A practical constructive scheme for deterministic shared-memory access
A Pietracaprina, FP Preparata - Proceedings of the fifth annual ACM …, 1993 - dl.acm.org
We present an explicit memory organization scheme for distributing hl data items among N
memory modules where M 6@(N15-o (lt'Og~ l). Each datum is replicated into a constant …
memory modules where M 6@(N15-o (lt'Og~ l). Each datum is replicated into a constant …
An O (√ n)-worst-case-time solution to the granularity problem
A Pietracaprina, FP Preparata - STACS 93: 10th Annual Symposium on …, 1993 - Springer
In this paper we deal with the granularity problem, that is, the problem of implementing a
shared memory in a distributed system where n processors are connected to n memory …
shared memory in a distributed system where n processors are connected to n memory …
Improved memory utilization in deterministic PRAM simulation
Y Aumann, A Schuster - Journal of Parallel and Distributed Computing, 1991 - Elsevier
A scheme for deterministic simulation of the PRAM on the Module Parallel Computer or on
Bounded Degree Networks is described. The scheme requires only a constant memory …
Bounded Degree Networks is described. The scheme requires only a constant memory …
[PDF][PDF] Space-efficient representations of shared data for parallel computers
K Herley - Proceedings of the second annual ACM symposium on …, 1990 - dl.acm.org
The problem of representing a set. tr k (2~ 1,.... II,,} of read-write variables on an n-node
distribut, ed memory pa. rallel computer is considered. It is shown that, Cr can be …
distribut, ed memory pa. rallel computer is considered. It is shown that, Cr can be …