Recipe of
Efficient PRAM simulations
- Choose a simple hash function.
- Hash PRAM's shared memory to local memory modules
- Setup a virtual "coated" DAG (logical diameter
D; routing capacity Omega
(PD))
- Allocate Omega(D) threads (virtual
PRAM processors) to each real processor.
- Route memory requests greedily.
- Keep consecutive PRAM steps separate with a syncronization
wave.

- What coated DEG? Mesh? Mesh of trees? Fat tree? Butterfly?
- How to implement the DAG?
- Where to get the threads?
A: Plenty of work-optimal NC-algorithms exists.
Last updated, Feb-5-1996.