PRAM Model, in depth: EREW, CREW and CRCW, work and span, Brent's bound, pointer jumping and what survives on GPUs

The machine and its two costs

A PRAM has an unbounded array of shared memory cells, each holding an integer, and p processors with identical programs and their own ids 0 to p-1. Each synchronous step has three phases: every active processor reads, then computes, then writes. All reads in a step see memory as it was at the start of the step, which is why a PRAM step is well defined even when one processor reads a cell another processor is writing.

Two cost measures matter. The time (or span) is the number of synchronous steps. The work is the total number of processor-steps actually used. A parallel algorithm is work-efficient when its work is within a constant factor of the best sequential algorithm; summing n numbers with n - 1 additions is work-efficient, summing them with n log n additions is not.

EREW, CREW and CRCW

The variants differ only in what happens when two processors touch the same cell in the same step. That single rule changes what can be done in constant time.

The variants form a hierarchy: an EREW algorithm runs unchanged on CREW, a CREW algorithm on any CRCW, and common on arbitrary on priority. Going the other way costs time. The OR of n bits shows the gap. On common CRCW it takes one step: every processor holding a 1 writes 1 to a result cell that was 0. On CREW it needs Omega(log n) steps no matter how many processors you use, a lower bound proved by Cook, Dwork and Reischuk in 1986. A balanced binary tree of ORs meets that bound on EREW, so OR costs Theta(log n) on both exclusive-write models.

Work, span and Brent's bound

Writing a PRAM algorithm for exactly p processors is tedious. The work-time framework lets you write it for as many processors as each step wants, count the total work W and the number of steps D, and then schedule it on p real processors. Brent's bound (Brent, 1974) says this costs at most

T_p  <=  W / p  +  D

because a step that does w_i operations takes ceil(w_i / p) rounds on p processors, and the sum of ceil(w_i / p) over the D steps is at most W / p + D. Read it as two regimes. While p is below W / D, the W / p term dominates and adding processors gives near-linear speedup. Past that point the span D is the floor and extra processors idle. The ratio W / D is the algorithm's parallelism, and it tells you how many processors are worth buying.

The bound also explains why work-efficiency matters more than span in practice. A summation with W = n log n and the same span runs log n times slower on any realistic p, because the W / p term is the one you actually pay.

A simulator that enforces the rules

A simulator that enforces the conflict rules is the fastest way to build intuition, and it catches real mistakes: an algorithm you believed was EREW often reads one cell from many processors. The core is one method. Each processor's program receives a read function that records which processors touched which cell, reads come from a snapshot taken at the start of the step, and writes are applied only after every processor has run.

from collections import defaultdict

class PRAM:
    def __init__(self, memory, mode="EREW"):
        self.mem, self.mode = list(memory), mode
        self.steps = self.work = 0

    def step(self, active, program):
        # program(pid, read) returns a list of (address, value) writes
        reads, writes = defaultdict(set), defaultdict(list)
        snapshot = self.mem[:]
        for pid in active:
            def read(addr, pid=pid):
                reads[addr].add(pid)
                return snapshot[addr]
            for addr, val in program(pid, read):
                writes[addr].append((pid, val))
        if self.mode == "EREW":
            for addr, who in reads.items():
                if len(who) > 1:
                    raise RuntimeError(f"concurrent read of {addr} by {sorted(who)}")
        for addr, ws in writes.items():
            if len(ws) > 1:
                if self.mode in ("EREW", "CREW"):
                    raise RuntimeError(f"concurrent write to {addr}")
                if self.mode == "CRCW-common" and len({v for _, v in ws}) > 1:
                    raise RuntimeError(f"common-CRCW writers disagree at {addr}")
                if self.mode == "CRCW-priority":
                    ws = [min(ws)]            # lowest processor id wins
            self.mem[addr] = ws[-1][1]         # arbitrary: any single value is legal
        self.steps += 1
        self.work += len(active)

The work counter adds the number of active processors each step, which is the honest measure: a processor that is allocated but idle in a step is not charged.

Worked examples: OR, maximum and sum

Three small programs on this simulator show how the conflict rule changes the cost.

OR of 8 bits on common CRCW. Memory holds the bits in cells 0 to 7 and a result cell 8 set to 0. One step: processor i reads cell i and, if it is 1, writes 1 to cell 8. For the input 0,0,1,0,1,0,0,0 two processors write the same value to the same cell, which common CRCW allows. Result 1, 1 step, 8 work.

Maximum of 6 values in one step on common CRCW. Use n squared processors, one per pair (i, j). Processor (i, j) writes 0 to a flag for i if x_j beats x_i, where ties break toward the smaller index so exactly one flag survives. For 7,3,9,9,1,4 the simulator returns 9 in 1 step and 36 work. Constant time is real, but the work is quadratic, so this only makes sense inside a larger algorithm on small groups. Combining it with a tree gives the doubly logarithmic maximum of Shiloach and Vishkin, O(log log n) steps with n processors.

Sum of 16 values on EREW. In round r, processor i, for i a multiple of 2^(r+1), adds cell i + 2^r into cell i. No cell is read or written twice in a round, so the simulator accepts it in EREW mode. Result 136 in 4 steps and 15 work: exactly the n - 1 additions a sequential loop performs, spread over log2 16 rounds. This is the up-sweep half of the scan explained in the parallel prefix sum article.

Pointer jumping and list ranking

The signature PRAM technique is pointer jumping. Given a linked list as an array of successor pointers, compute each node's distance to the tail (its list rank). Sequentially you walk the list in n steps. In parallel, each node keeps a pointer and a partial rank, and in every round replaces its rank with its rank plus its successor's rank and its pointer with its successor's pointer. Each round doubles the distance every pointer spans, so ceil(log2 n) rounds finish. This is Wyllie's algorithm.

def list_rank(nxt):
    # cells [0, n) hold next pointers (the tail points to itself), [n, 2n) hold ranks
    n = len(nxt)
    m = PRAM(nxt + [0 if nxt[i] == i else 1 for i in range(n)], "CREW")
    for _ in range(max(1, (n - 1).bit_length())):    # ceil(log2 n) rounds
        def jump(i, rd):
            j = rd(i)
            return [(n + i, rd(n + i) + rd(n + j)), (i, rd(j))]
        m.step(range(n), jump)
    return m.mem[n:], m.steps, m.work

On the list 0, 3, 1, 4, 2, 5, 6, 7 the simulator returns ranks 7, 5, 3, 6, 4, 2, 1, 0 for nodes 0 to 7 in 3 steps and 24 work. On shuffled lists checked against the true positions, n = 1,024 took 10 steps and 10,240 work and n = 65,536 took 16 steps and 1,048,576 work. Work divided by n is exactly log2 n, so Wyllie's algorithm is not work-efficient: it does n log n operations where a sequential walk does n.

Run the same program in EREW mode and it fails in the first round: node 0 reads node 3's pointer while node 3 reads its own. That conflict could be removed by splitting the step in two, but a second one cannot be removed cheaply: once pointers reach the tail, every finished node reads the tail cell in the same step. That is why the algorithm is stated for CREW. Work-efficient list ranking exists: deterministic coin tossing (Cole and Vishkin) and randomised independent-set contraction remove a constant fraction of nodes per round, giving O(n) work and O(log n) time with more complicated code. The same doubling idea finds roots in forests.

Simulating one variant on another

Stronger variants can be simulated on weaker ones at a cost. A step of a p-processor priority CRCW PRAM can be simulated on a p-processor EREW PRAM in O(log p) steps: sort the write requests by address and processor id, keep the first request per address, and resolve concurrent reads the same way by sorting and broadcasting down segments. So any CRCW algorithm with time T runs on EREW in O(T log p) time. A log factor is the price of exclusive access, and the OR lower bound shows that some of that factor is unavoidable.

So design with the weakest variant you can, and use CRCW operations only where they buy a log factor in a hot spot.

From PRAM to BSP, LogP and GPUs

A PRAM hides three costs real machines charge for: synchronisation, communication and memory hierarchy. BSP (Valiant, 1990) puts them back by charging each superstep for its communication volume and a barrier latency; LogP (Culler and others, 1993) charges per-message latency, overhead and gap. Both reward algorithms that do much local work between synchronisations.

GPUs are the closest mass-market machine to a PRAM, and the mapping is useful if you know where it breaks. A warp executes one instruction for 32 threads at once, which resembles a PRAM step. Shared memory within a block is fast, and a barrier such as __syncthreads() separates steps. For concurrent writes, the CUDA programming guide states that when several threads of a warp perform a non-atomic write to the same address, which thread performs the final write is undefined: arbitrary-CRCW behaviour within a warp. Atomic adds behave like a combining CRCW variant. The analogy breaks on cost: blocks do not synchronise inside a kernel without cooperative launches, global memory latency is hundreds of cycles, and uncoalesced accesses multiply cost. The GPU matrix multiply article shows how much of real performance comes from the memory hierarchy the PRAM ignores.

So use the PRAM to find the parallel structure, check work-efficiency and span, and then redesign the data movement for the machine. Sorting is a good example: a sorting network has a fixed, oblivious comparison pattern that maps well onto lockstep hardware even though its work is O(n log^2 n), more than an optimal comparison sort.

Failure modes

• Ignoring work. An O(log n) time algorithm with n^2 work loses to a sequential loop for every n you can fit in memory. Report W and D together, never D alone.
• Assuming constant-time concurrent writes. Code designed for CRCW that runs on hardware where conflicting writes serialise can be slower than the sequential version. Hot result cells, global counters and flags written by every thread are the usual culprits; aggregate within a warp or block first.
• Relying on lockstep. PRAM steps are synchronous by definition. Threads on a GPU or CPU are not, so an algorithm that reads a neighbour's value from the previous step needs a barrier or double buffering. Missing it gives races that pass small tests.
• Forgetting the snapshot semantics. An in-place loop that emulates a parallel step reads values already overwritten in that step; read from a snapshot.

Trade-offs

What to do next

1. Copy the simulator and run the sum, OR and pointer jumping programs; then change one access pattern and watch the conflict check fire.
2. For an algorithm you care about, write down W and D, compute W / D, and compare it with the number of hardware threads you have.
3. Check work-efficiency against the best sequential algorithm; if the work has an extra log factor, look for a contraction or blocking version.
4. List every concurrent write in your design and decide how the hardware resolves it: plain store, atomic or a reduction tree.
5. Read the scan article next; scan is the building block that turns most PRAM algorithms into real kernels.