Why Cray threw away the cache: Flynn, SIMD and the vector idea

Past the walls of ILP: data-level parallelism

Lesson 8 ended at the limits of ILP, which the notes group as three walls (p. 387): control (a misprediction costs more the deeper the pipeline), memory (misses and pointer chasing starve the out-of-order window) and complexity/energy (renaming, reservation stations and reorder buffers grow faster than the IPC they buy: "a lot of energy is spent to squeeze out a few more IPCs"). The way past is another kind of parallelism: threads (TLP, lesson 29), independent requests (RLP), or data — this lesson and the next two.

Take the plainest loop there is, Z[i] = X[i] + Y[i] for i = 0 … 63. Iteration 17 never needs the result of iteration 16, so in principle all 64 additions could happen at the same moment. Change one index and the picture flips: in X[i] = X[i] + X[i-1], statement S1 of the July 2024 quiz on loop-carried dependences, every addition waits for the one before.

Why bother, when an out-of-order core would also find those 64 independent additions? Because of what finding them costs. A superscalar core fetches, decodes, renames, schedules and commits every single instruction, and that machinery, not the adder, is where most of its energy goes. A SIMD or vector machine "only needs to fetch one instruction per data operation" (p. 387): one instruction says "add these 64 pairs". Hence the claim this lesson has to justify: on such loops an in-order vector processor can match or beat a complex out-of-order core, at lower energy.

DLP is the same operation on many independent elements; a SIMD or vector machine pays for one instruction and gets many element operations, so the front-end cost per element almost vanishes.

Flynn counts streams, not width

Two machines each start four operations in the same clock cycle. The first is a 4-wide superscalar: it reads four instructions from one program counter — a load, a multiply, an add, an index update — and sends each to its own unit. The second is a SIMD array: it reads one instruction, ADD R1, R2, R3, and broadcasts it to four processing elements, each adding its own pair of registers. Both are parallel. Only one of them is SIMD.

In 1966 Michael Flynn classified computers by how many instruction streams and how many data streams they handle at once (p. 388):

The rule that settles the confusing cases is the notes' own: "Flynn's classification is about streams, not width" (p. 388). A superscalar may issue four, six or eight instructions per cycle, but all come from one PC, each a different instruction on its own operands: parallelism across instructions, ILP, still SISD. A SIMD machine fetches one instruction and applies it to many elements, as ADDVV.D V3, V1, V2 computes V3[i] = V1[i] + V2[i] for every i: parallelism across data, DLP. Multithreaded and multicore processors run one stream per thread: MIMD, TLP. Vector processors are the textbook SIMD machine.

The SIMD machine: one PC, many processing elements

A SIMD machine has a single control unit with one program counter: each instruction is fetched once and broadcast to all the processing elements (PEs), which execute it in lockstep, each on its own local data (p. 390). The notes' picture is a classroom: one teacher says "add 5 to your number", and 32 students do it at once, each in their own notebook. A PE is much simpler than a core — a few registers, an ALU or FPU, sometimes a slice of local memory — and has no PC, no branch predictor and no cache: it relies on the controller.

One PC buys three things (p. 391): energy, with one fetch and decode per operation instead of one per PE; compact code, written once for all PEs; and simplicity, because PEs stepping in lockstep never need to synchronise. The price is lockstep: all PEs execute the same instruction, or some are masked off (lesson 31). A MIMD multicore makes the opposite trade: every core has its own PC and can run anything, and synchronisation — locks, barriers — becomes the programmer's problem.

Real machines mix the two (p. 391): a scalar unit runs ordinary SISD code and the SIMD instructions go to the PE array — MIPS plus the vector unit of VMIPS, scalar x86 plus AVX-512. GPUs, with their thousands of threads, are "essentially SIMD under the hood": a warp of threads executes one instruction at a time in lockstep. The notes' Figure 30 (p. 392) draws a vector processor next to a GPU's SIMD processor, which Hennessy and Patterson call a multithreaded SIMD processor; lesson 32 takes the pair apart.

Count instruction streams and data streams, never instructions per cycle: superscalar = SISD (ILP), vector unit and GPU warp = SIMD (DLP), multicore = MIMD (TLP).

Space or time: arrays of PEs and pipelined vector units

"Not all SIMD is created equal" (p. 394). The first way to build it is the SIMD array — Illiac IV, the Connection Machine: the programmer sees an array of PEs with local memories, and each broadcast instruction runs on all of them at once. Such arrays are awkward to program (you think in PEs, local memories and communication) and handle branches badly: they are "of historical interest". The second way is the vector processor of Cray and VMIPS: the programmer sees vector registers, writes one instruction for a whole array, and the hardware streams the elements through deeply pipelined functional units — "classical SIMD, just presented in a more programmer-friendly way" (p. 392).

The difference shows in time. Suppose the add takes 6 cycles. In the array each PE executes the ADD "exactly like a tiny CPU would" and stays "frozen" until it finishes, so "latency is exposed": every operation pays all of it (p. 395). In the vector unit the add is a pipeline: in cycle 1 the first pair of elements enters the adder, in cycle 2 the second pair enters while the first is still inside, and so on. After the 6-cycle start-up one result leaves every cycle: 64 elements take 6 + 64 = 70 cycles, on a "conveyor belt" where "latency is only paid once".

Count both machines with the rule of the Tomasulo tables: a result is written \(L\) cycles after its operation starts (\(L\) the latency of the adder, \(n\) the number of elements).

1. Pipelined unit. Element \(k\) enters the adder in cycle \(k\) and is written \(L\) cycles later (WRITE RESULT = START EXEC + latency):

   \[ t_{\text{write}}(k) = k + L \]

2. The last element, \(k = n\), is written in cycle \(n + L\):

   \[ T_{\text{vector}} = L + n \]

   With \(L = 6\) and \(n = 64\): 70 cycles, the notes' count.

3. Array of \(N\) unpipelined PEs. \(N\) elements start together and keep their PEs frozen for \(L\) cycles; the next \(N\) start \(L\) cycles later. Round \(r\) starts and writes in

   \[ t_{\text{start}}(r) = (r-1)L + 1 \] \[ t_{\text{write}}(r) = rL + 1 \]

4. \(n\) elements need \(\lceil n/N \rceil\) rounds, so the last results are written in cycle

   \[ T_{\text{array}} = L \left\lceil \frac{n}{N} \right\rceil + 1 \]

   With \(L = 6\), \(n = 64\) and \(N = 8\): 6 · 8 + 1 = 49 cycles. With \(N = 1\), a single unpipelined adder: 385. The final 1 is the write cycle that the pipeline's \(L + n\) already contains.

5. Divide the results by the hardware: the pipelined adder alone delivers 64/70 = 0.91 results per cycle, each of the 8 array adders 64/(8 · 49) = 0.16, about one every \(L\) cycles:

   \[ \frac{n}{L+n} \quad \text{vs} \quad \frac{1}{L} \]

   The pipeline wins on hardware, not on latency: one \(L\)-stage pipelined unit does the work of about \(L\) unpipelined ones, once the vector is long enough to keep it full.

Why can a vector unit be pipelined so deeply? Because of element independence: the element entering the adder never needs the result of an element still inside it, since V3[17] = V1[17] + V2[17] does not read V3[16]. No hazard check is needed between consecutive elements, so the unit can be cut into many short stages and clocked fast (p. 397).

The widget adds a third machine: a scalar loop doing the same additions, the body of the papers' strip-mining quiz, Y[i] = X[i] + Y[i]:

LOOP: LD    F2, 0(R1)      ; X[i]
      LD    F4, 0(R2)      ; Y[i]
      FADD  F4, F4, F2     ; X[i] + Y[i]
      SD    F4, 0(R2)      ; Y[i] ← F4
      ADDUI R1, R1, 8
      ADDUI R2, R2, 8
      BNE   R1, R3, LOOP   ; R3 = end of X

Counted optimistically — one cycle for each of the six other instructions, \(L\) cycles for the FADD because the SD waits for its result, no other stall — every element costs \(L + 6\) cycles. The scalar loop also loads and stores each element, which a single ADDVV.D does not: the fair whole-loop comparison is lesson 31's. Watch how often each machine pays the latency.

An array of \(N\) PEs pays the latency once per round of \(N\) elements; a pipelined vector unit pays it once per vector and then streams one result per cycle: one \(L\)-stage pipelined adder does the work of about \(L\) unpipelined ones — on long vectors.

Cray's choices: where the transistors went

When people say "vector processor" they usually mean this Cray-style design, and VMIPS is a simplified version of it (p. 396). Its philosophy, in the notes' words: "don't waste transistors on speculation or caches; spend them on wide datapaths and memory bandwidth" (p. 398). The target is scientific code with long arrays — matrix operations, PDE solvers, simulations — and with no giant instruction window and no speculative logic the result is "much higher throughput per watt than OoO ILP" (p. 398). Five choices follow, each with a reason and a price:

Three supporting pieces complete the machine (p. 397), all put to work in lesson 31: vector mask registers, which switch off elements so that loops with an if stay vectorisable; multiple lanes, parallel copies of the units (4 lanes, 4 elements per cycle); and a scalar unit for control flow and scalar data.

A Cray-style machine bets on regularity: one instruction for many elements, vector registers, deep pipelines, interleaved banks — and no data cache, because a stream has nothing to reuse.

VMIPS, and DAXPY in six instructions

VMIPS is not a commercial computer but Hennessy and Patterson's teaching model: the MIPS you know plus "a Cray-style vector coprocessor", simple enough to count cycles by hand, faithful enough that the counts mean something, and a bridge to the SIMD units of today's processors (p. 399). The February 2025 paper prints its block diagram (notes p. 578), redrawn here.

Its three pillars, plus the scalar side (pp. 399–401):

• Vector register file. Eight registers, each holding 64 elements of 64 bits: 4 KB in all. Its 16 read and 8 write ports, connected to the units by a crossbar, let several units and the load/store unit use it in the same cycle. It is a compiler-controlled buffer between memory and the units: the compiler decides what is loaded and when, so it is not a cache.
• Vector functional units. Five of them — FP add/subtract, FP multiply, FP divide, integer, logical — all fully pipelined, each accepting a new element every cycle. One unit's output can feed another element by element, without waiting for the whole vector: chaining, the vector form of forwarding (lesson 31).
• Vector load/store unit. Moves a whole vector between memory and a register: the memory latency is paid once, then one word per cycle. Memory is interleaved — word 0 in bank 0, word 1 in bank 1 — so a sequential load never waits for a busy bank. Besides unit stride it can load every k-th word (strided access, for matrix columns) and gather or scatter elements through an index vector (sparse data).
• Scalar side. The MIPS core runs the code that does not vectorise, computes addresses and supplies scalar operands such as a.

The instructions, in the papers' spelling (Hennessy and Patterson write LV and SV for L.V and S.V):

The exam's machines are variations on VMIPS: "32 vectors of 16 elements" in July 2024 and June 2026, of 8 elements in June 2025. Always read the vector length from the question.

DAXPY, instruction by instruction

DAXPY, "Double-precision A·X Plus Y", is the loop of the opening puzzle (p. 402):

A BLAS kernel and the inner loop of the Linpack benchmark that ranks supercomputers, it does one multiply and one add per element, with no dependence between elements, so it isolates the effect of vectorisation. The scalar MIPS loop for 64 elements, in the papers' mnemonics:

        LD    F0, 0(R3)     ; F0 ← a
        ADDUI R4, R1, 512   ; R4 = end of X
LOOP:   LD    F2, 0(R1)     ; X[i]
        FMUL  F2, F2, F0    ; a * X[i]
        LD    F4, 0(R2)     ; Y[i]
        FADD  F4, F4, F2    ; a * X[i] + Y[i]
        SD    F4, 0(R2)     ; Y[i] ← F4
        ADDUI R1, R1, 8     ; next X
        ADDUI R2, R2, 8     ; next Y
        SUB   R5, R4, R1    ; elements left?
        BNE   R5, R0, LOOP  ; R0 is always 0

And on VMIPS, the same work:

        LD      F0, 0(R3)   ; F0 ← a
        L.V     V1, R1      ; V1 ← X[0..63]
        MULVS.D V2, V1, F0  ; V2 ← a * X
        L.V     V3, R2      ; V3 ← Y[0..63]
        ADDVV.D V4, V2, V3  ; V4 ← a * X + Y
        S.V     V4, R2      ; Y ← V4

1. Set-up, executed once: LD F0 (the scalar a) and ADDUI R4 (the end of X), 2 instructions.

2. Loop body, executed once per element: 9 instructions. Five do the work — two loads, the multiply, the add, the store — and four only run the loop: two pointer updates, the bound test and the branch.

3. For 64 elements:

   \[ 2 + 9 \times 64 = 578 \]

   dynamic instructions, the notes' "≈ 578".

4. VMIPS: the scalar LD F0 plus one vector instruction per operation of the body; no loop, so no pointers, no bound, no branch:

   \[ 578 - 6 = 572 \]

5. Where the 572 went: the 320 element instructions (5 × 64) became 5 vector instructions, 315 fewer; the 3 × 64 = 192 pointer updates and bound tests vanished, and so did the 64 branches and the bound set-up:

   \[ 315 + 192 + 64 + 1 = 572 \]

Fetch and decode are not all: the scalar pipeline also resolves the four dependences that carry the data through the body — LD to FMUL, FMUL to FADD, LD to FADD, FADD to SD — once per element, 256 times; VMIPS resolves each of them once. The widget counts both.

How long the six instructions take is the subject of lesson 31.

The opening puzzle, solved

Back to 1976. A cache pays off when data are reused or when the hardware has to guess what comes next, and a vector loop offers neither: a vector load states exactly which 64 words it wants, and DAXPY uses each once. A stream needs bandwidth and a way to pay latency once, and that is where the Cray-1's transistors went: sixteen banks, each busy for 4 clock periods, delivering one word per clock period (Russell, 1978); pipelined units that pay their latency once per 64 elements; and 4 KB of vector registers, the buffer a cache would have been, filled by the compiler, so nothing misses. The 578 against 6 is the same decision seen from the instruction side.

VMIPS is MIPS plus 8 vector registers of 64 × 64-bit elements (16 read, 8 write ports), five pipelined units and one pipelined load/store unit over interleaved banks; on it, DAXPY's 578 scalar instructions become 6.