PRAM Variants and the Cost of Ignoring Memory

The DAG model says nothing about where data lives. Every node costs one step whether it reads a register or a location that another processor wrote a nanosecond ago. That abstraction is deliberate, and it produced the bulk of parallel algorithm theory: models that ignore memory are tractable, and their predictions about which problems have polylogarithmic depth hold across machines. But when the question is how long a specific kernel takes on a specific machine, the missing term is the dominant one, and the correction requires a different model rather than a better constant.

Three PRAM variants

The Parallel Random Access Machine gives P processors, a shared memory of unbounded size, and unit-cost access to any location. Processors run in lockstep steps; in each step each processor may read one location, compute, and write one location. Variants differ only in what happens when several processors touch the same location in the same step:

• EREW, exclusive read exclusive write: concurrent access to a location is a programming error. The most restrictive model, and the easiest to implement on real hardware, since no arbitration is needed.
• CREW, concurrent read exclusive write: many processors may read one location simultaneously; writes must be exclusive. Broadcast of a shared value is free in this model.
• CRCW, concurrent read concurrent write: writes to the same location are permitted, with a sub-variant deciding the winner — arbitrary (any one write succeeds), priority (the highest-priority processor wins), or common (all writing processors must write the same value, otherwise the result is undefined).

The three form a chain of increasing permissiveness, so an algorithm written for a stricter model runs unchanged on a looser one and a result proved for EREW is a result for all three. The interesting results are the simulations in the other direction. A concurrent-write step can be simulated on an EREW machine at a polylogarithmic factor, using a sorting network or a prefix computation to arbitrate which write wins; the common variant, where all writing processors must store the same value, needs only a test for agreement, and the priority variant needs a prefix minimum over the priorities. Arbitrary-winner CRCW is the awkward case, since the result is permitted to be any one of the written values, and the algorithms that rely on it need a deterministic simulation that costs another logarithmic factor. In practice the choice between variants rarely changes the asymptotic complexity of an algorithm; it changes the exponent’s constant and the clarity of the pseudocode, which is why theory papers pick whichever variant makes the algorithm cleanest.

Work, depth, and the bridge to the DAG

The PRAM’s time for an algorithm is the number of lockstep steps, and its work is P times that. Those correspond to depth and work in the DAG model, with one caveat: a PRAM algorithm’s step count assumes all P processors are busy every step, so a PRAM algorithm with T steps and P processors has work P·T only if it never idles. Most PRAM algorithms are written for a fixed P and pad with no-ops, which inflates the work figure by the idle fraction.

The standard way to relate the two is Brent’s simulation: any PRAM algorithm with T steps on P processors can be run on P′ < P processors in O(T·P/P′) steps by serialising the operations of each step. So the PRAM’s T is the depth and its P·T is the work, and a PRAM algorithm with T = O(log n) and P·T = O(n) is exactly a work-efficient, polylog-depth algorithm. The reverse direction — turning a DAG into a PRAM algorithm — requires the DAG to be levelled, which fails for computations whose tasks have unequal durations.

This correspondence is why the DAG model in the work-span article is the more useful of the two for engineering: it makes no assumption about lockstep, and the span is a lower bound on any schedule. The PRAM remains useful for proving that a problem is in a low-depth class, which is a statement about the problem rather than about an implementation.

Where the PRAM’s accounting goes wrong

The model charges one step for a shared-memory read. On a real machine, a read that hits L1 costs a few cycles, a read that hits L3 costs tens, and a read that goes to another socket costs hundreds. A PRAM algorithm with T = 10 steps and P = 1000 processors does 10⁴ operations and predicts a time of 10 steps; the same algorithm on hardware may take longer than the sequential version, because most of its 10⁴ operations are misses that the sequential version’s cache-resident loop avoids.

Two distinct effects are hidden in that gap:

Latency. A dependent chain of memory accesses costs the sum of the latencies. A PRAM algorithm that reads a value, then reads an array indexed by that value, then reads again, has depth 3 in the model and depth 3·latency in cycles. The model’s depth is a lower bound only if every access is a register.

Bandwidth. The total bytes moved per step is bounded by the memory system, not by P. If a step touches n bytes and the machine can deliver n/10 per unit time, the step costs 10 units regardless of how many processors are involved. Bandwidth-bound steps look free in the model and are the bottleneck in reality. That is the same phenomenon as the c(P) overhead in the scaling article, expressed as a model defect rather than as a law.

The ideal-cache correction

The cache-oblivious model replaces “shared memory, unit cost” with a two-level hierarchy: a cache of size M and lines of size B, with memory transfers counted in lines. The algorithm is written without knowing M or B, and its transfer count is analysed as a function of them. An algorithm is cache-oblivious-optimal if its transfer count matches the best possible for any M and B, without tuning.

The canonical example is matrix multiplication. The naive triple loop performs Θ(n³) operations; its transfer count depends on the loop order, from Θ(n³/B) when the innermost loop walks a contiguous dimension to Θ(n³) when it walks a strided one, because each strided access touches a fresh cache line. A blocked version with blocks of size √M performs Θ(n³/(B√M)) transfers, which is optimal for the two-level model under the tall-cache assumption M ≥ B², but requires knowing M. Recursive divide-and-conquer multiplication — split each matrix into four quadrants, recurse on eight subproblems, combine — achieves the same transfer count for every cache level simultaneously, without any parameter. That is the property the model was built to explain, and it is why recursive layouts and recursive algorithms appear in high-performance kernels that must run on machines whose cache sizes were not known at compile time.

The transfer-count analysis has a matching lower bound: any algorithm that reads n³ inputs and produces n² outputs must move at least Ω(n³/(B√M)) lines, by an argument about the number of distinct input-output pairs a cache of M words can serve. The bound is the communication lower bound restricted to a single level of the hierarchy, and the same counting argument gives the distributed version.

What survives from the abstract model

Despite the accounting gap, PRAM results remain the right first filter, for three reasons.

The depth bound is hardware-independent. A problem with polylogarithmic depth can be made fast on any machine with enough parallelism; a problem with linear depth cannot. The model’s depth figure is a lower bound on real time in the same way that the DAG’s span is, and it is derived from the algorithm rather than from a machine.

The work bound tells whether a parallel algorithm is worth using at all. An algorithm with n log n work where n is achievable sequentially needs a speedup of log n just to break even. The PRAM makes this comparison natural because both figures are in the same currency.

The simulations are constructive. Algorithms designed for CRCW translate to EREW with a constant or polylog factor, so a result proved in the strongest model is a result about a realisable algorithm. The translation usually takes the form of a prefix computation, which is why scan appears in the simulation of almost every concurrent-write primitive.

The practical discipline is to use the PRAM or DAG model to establish depth and work, then to check the two things the model omits: whether the algorithm’s memory access pattern is local at every level of the hierarchy, and whether the total bytes moved fits the bandwidth available in the time the arithmetic takes. An algorithm that passes both is fast on real hardware. One that fails either is a theory result with a known gap, and no amount of scheduler tuning closes it.

A concrete mismatch

Multiplying two n×n matrices illustrates the size of the gap. The straightforward parallel algorithm assigns one output element to each of n² processors; each sums n products, so depth n and work n³. On a PRAM with n² processors, the time is n steps. On a real machine, each of the n² processors reads a row and a column: the row reads are shared and can be broadcast, but the column reads are strided, touching a new cache line per element. The transfer count is Θ(n³) lines against the optimal Θ(n³/(B√M)), a factor of B√M worse with B and M counted in the same units. A 64-byte line holds eight doubles, and an L2 holding a few hundred thousand doubles has √M in the hundreds, so the factor runs into the thousands.

The fix is not more processors. It is to change the algorithm so that each processor works on a block of outputs and the block’s inputs are loaded once into a cache-resident working set, which leaves the arithmetic unchanged and cuts the transfers by the factor above. That is the whole content of the cache-oblivious and blocked formulations, and it is why an algorithm with optimal PRAM work can be orders of magnitude slower than a blocked algorithm with identical abstract work.

The lesson generalises: the abstract model ranks algorithms by operation count, and on machines where a floating-point operation costs a cycle and a DRAM access costs hundreds, the ranking by operation count is often the wrong ranking. The next correction, for machines where the data does not fit in one memory at all, is to count messages rather than bytes, which is where the bulk-synchronous model starts.