The PRAM (introduced at STOC 1978 by Fortune & Wyllie and, independently, by Goldschlager) is the RAM model with the processor count turned up: p processors share one global memory and march in synchronous lockstep. In every time-step, each processor may read a shared cell or two, compute locally, and write one shared cell — and within a step, all reads complete before any write lands. (Formulations differ on one vs O(1) reads per step; we draw a two-read addition as a single step.) The radical simplification is uniformity: reading the cell next door and reading a cell “across the machine” both cost exactly one step. Memory has no geography.
That simplification is what made the model productive. Freed from machine details, PRAM theory mapped the structure of parallelism itself: work W (total operations), time/depth T (steps on unlimited processors), and Brent’s scheduling theorem — Tp ≤ W/p + T — which says any greedy schedule comes within a factor of about two of the best possible, once you know W and T. Prefix sums, list ranking, Euler tours, parallel connectivity: the classic parallel toolbox was built and analyzed here.
Watch the model’s favorite opening move: summing n numbers with a binary tree of additions — n/2 processors, log n steps. Note the meter that stays dark.
The PRAM family splits on one question: may two processors touch the same cell in the same step? EREW (exclusive read, exclusive write) says never. CREW allows shared reading but a single writer. CRCW allows both, and then needs a rule for write collisions: Common (all writers must agree on the value), Arbitrary (one unspecified writer wins), or Priority (the lowest-numbered processor wins).
The variants genuinely differ in power — computing the OR of n bits takes O(1) on a Common-CRCW machine (every 1-holder writes “1” to the same cell) but Ω(log n) on CREW, a lower bound of Cook, Dwork & Reischuk — yet not by much: any step of a Priority-CRCW PRAM can be simulated on an EREW PRAM with O(log p) slowdown by sorting the access requests. (A fourth write rule, Combining, merges colliding writes with an operator like + or max.) Logarithmic factors aside, the family stands or falls together.
Step through five collision scenarios below, and flip the variant selector to see which machines accept each one and what value lands in memory.
The PRAM’s founding results each exploit one of its idealizations to the hilt. The three below are chosen for exactly that reason: the scan leans on free lockstep synchrony, pointer jumping leans on distance-free memory, and CRCW max leans on unbounded concurrent writes. Step through each — and keep one eye on what the moves would cost on real silicon.
One processor per element. In round k = 1, 2, …, every element adds the value 2k−1 positions to its left (strides 1, 2, 4, …) — and because a PRAM round completes all reads before any write, the n simultaneous read-modify-writes can’t trample each other. After ⌈log₂ n⌉ rounds every inclusive prefix is done, at the price of Θ(n log n) work instead of the sequential n−1 — depth bought with work. Note the reads’ reach: the final round’s stride is n/2 cells. Uniform memory makes that free; a distance model would charge those long arcs the most. (The work-efficient fix, Blelloch’s up/down-sweep tree, is what the spatial-computer tutorial runs over Z-order quadrants for Θ(n) energy.)
A linked list lies scattered across memory — cell order and list order are unrelated, which is the honest picture of real linked structures. Sequentially, computing each node’s distance to the tail means chasing pointers n times. The PRAM collapses it to ⌈log₂ n⌉ rounds: in each, every node adds its successor’s counter to its own and re-points itself at its successor’s successor, halving every chain simultaneously. Watch what the model hands out: n arbitrary dereferences per round, each to wherever the pointer happens to aim, all unit cost. This is the PRAM habit distance models punish hardest — the spatial computer’s Ω(n3/2) permutation bound is, in effect, the invoice for scattering a list across a chip.
The Common-CRCW machine finds the max of n values in two rounds, for any n, using one processor per ordered pair: every processor whose left element loses its comparison writes a 1 into that element’s “loser” flag (many writers, same value, same cell — legal under Common); the unique survivor then writes itself out. It is the conflict lab’s same-value-write scenario weaponized into an algorithm, and the purest demo of what CRCW hands out free: n² hardware and unbounded write fan-in. An EREW machine provably cannot do this — max takes Ω(log n) there — and no physical machine comes close.
Dally’s argument is physical, and he brings receipts: a 32-bit add costs about 20 fJ, while fetching its two operand words from main memory costs 1.3 nJ — “64,000× less” for the arithmetic, in his words. Even on-chip, moving those two words a single millimeter costs 1.9 pJ (a hundred adds), and corner-to-corner across a 400 mm² chip, 77 pJ. “Because communication completely dominates the cost of computation, our model of computation must consider communication, and to do so, it must have a model of location.” His proposal, PECM (the parallel explicit communication model), keeps PRAM’s unit-cost arithmetic but assigns every processor and memory a location and prices each access by a distance function — Manhattan distance for on-chip traffic.
The simplified-dally-model distills this to a single processor. Memory cells are laid out in the upper half-plane around a core at the origin, linearly indexed along diagonal shells; cell i sits at Manhattan distance ⌈√i⌉. The pricing is brutal and clean: a read costs its distance; writes and arithmetic are free. A function call prices out as: the caller places every input byte, the program (a three-address IR) executes, and the outputs are read from caller-specified cells at standard read cost.
Geometry does all the work here. Only ~d² cells fit within distance d, so touching n values costs Θ(n3/2) no matter what — the √ that PRAM hides. And once reads have prices, placement becomes an optimization variable: below is the repo’s worked example a·b + c·d + e, priced live. Flip the placement and watch the same five instructions change price — under PRAM the two placements are indistinguishable.
The spatial computer (Gianinazzi, Ben-Nun, Besta, Ashkboos, Baumann, Luczynski, Hoefler; arXiv 2205.04934) applies the same physics to a parallel machine: an unbounded 2-D grid of processors with constant local memory, where sending a message costs its Manhattan distance in energy, and depth counts the longest chain of dependent messages. It is the PRAM’s opposite number: where PRAM makes communication invisible, the spatial computer makes it the only thing you pay for.
The two are formally connected. The spatial paper shows any EREW PRAM algorithm with p processors, m memory cells and T steps runs on the grid in O(p(√p + √m)·T) energy — lay the simulated shared memory out as a √m×√m subgrid and route each virtual access as a real message. PRAM algorithms aren’t wrong; they’re optimistically priced: each “unit” PRAM access really costs up to about √p + √m in distance. Algorithms redesigned for locality (Z-order scans, quadrant-recursive broadcasts, Cannon’s matmul) beat the simulation by polynomial factors — that story, with four more simulators, is in the companion tutorial.
The same task — sum 16 numbers — priced by each model. Flip between the tabs: the numbers are identical, the machines are not. PRAM finishes in 4 uniform steps and reports no communication at all. The Dally core must physically fetch every operand from its shell — 65 distance units, no parallelism. The spatial computer spreads the data over 16 tiny cores and gathers with a quadrant tree: 24 energy, 2 message rounds.
| PRAM (EREW) | Simplified Dally | Spatial computer | |
|---|---|---|---|
| Hardware assumed | 8 processors, uniform shared memory | 1 core, memory in half-plane shells | 16 grid processors, O(1) memory each |
| Parallel time | 4 steps | 15 sequential adds | 2 message rounds |
| Communication priced | 0 (not modeled) | 65 distance units | 24 energy units |
| Asymptotics | T = Θ(log n) | cost = Θ(n3/2) | E = Θ(n), D = Θ(log n) |
| What the number teaches | dependency structure of the algorithm | data movement dominates even sequentially | layout + communication co-design |
| PRAM | Simplified Dally model | Spatial computer | |
|---|---|---|---|
| Origin | Fortune & Wyllie, STOC 1978 | Dally, CACM 2022 (this repo’s single-core distillation) | Gianinazzi et al., arXiv 2205.04934 |
| Machine picture | p synchronous processors + one shared memory | 1 core at origin; memory cells on half-plane shells, cell i at distance ⌈√i⌉ | unbounded 2-D grid of processors, O(1) memory each, any-to-any messages |
| Cost of a memory access | 1 step, any cell | read = Manhattan distance; write = 0 | message = Manhattan distance (energy) |
| What’s free | all communication | writes, arithmetic | local compute; parallelism itself |
| Objective(s) | time T, work W | total read cost of a call | energy E, depth D, wire-depth Dw |
| Does data layout matter? | no — access is uniform | entirely — placement is the game | entirely — Z-order, quadrants, skews |
| Signature results | log-depth scan, list ranking, Brent’s theorem | function-call pricing; touching n values costs Θ(n3/2) | Θ(n) scan & selection, Θ(n3/2) sorting, Θ(n³) Cannon; permutation lower bound |
| Blind spot | communication, energy, locality | parallelism (one core by design) | local memory hierarchy is abstracted (until the S-fat variant) |
| Bridge to the others | — | PRAM access ↦ priced read; the √ reappears | simulates EREW PRAM in O(p(√p+√m)·T) energy |
The three are best read as layers, not rivals. PRAM answers “what parallel structure does this problem have?” — its uniform memory is a feature, isolating dependency depth from machine noise, and its algorithms (scan, tree contraction) survive intact as skeletons. Dally’s model answers “what will this cost on silicon?” for a single stream of instructions — even sequential code inherits a Θ(n3/2) floor just for touching its data, and placement becomes a first-class knob. The spatial computer asks both questions at once and adds the answer PRAM cannot give: port the Θ(log n)-depth PRAM scan through the simulation theorem and it costs O(n√n·log n) energy (about n√n for a work-optimal port) — re-lay the data along a Z-order curve and the same job costs Θ(n). The CACM point/counterpoint frames the trade honestly: Dally wants the model to expose location because the joules live there; Vishkin’s counterpoint replies that the real crisis is the parallel programming wall — programmer-facing models must stay as simple as PRAM, with PECM-style locality pushed into compilers, specialized routines, and accelerators. Both are right about their own layer: the PRAM tells you what to compute in parallel; the distance-aware models tell you where the joules go.