VMIPS and the art of counting convoys: chaining, lanes, lengths, masks and banks

Convoys and chimes: time counted in whole vectors

Lesson 30 built VMIPS: the scalar MIPS pipeline plus a vector unit — vector registers of 64 elements of 64 bits, deeply pipelined vector functional units, one vector load/store unit — so that DAXPY, \(Y = a \cdot X + Y\) on 64 elements, takes 6 instructions instead of about 578 (p. 402). Here you count its clock cycles. These are its five vector instructions as the papers write them; F0 already holds the scalar a.

L.V      V1, RX       # V1 ← X
MULVS.D  V2, V1, F0   # V2 ← a * X
L.V      V3, RY       # V3 ← Y
ADDVV.D  V4, V2, V3   # V4 ← a * X + Y
S.V      V4, RY       # Y  ← V4

A vector unit is a deep pipeline that accepts one new element per clock cycle. MULVS.D on 64 elements keeps the multiplier busy for 64 cycles, plus a few cycles while the first element travels down the pipeline — a start-up that the papers' counts leave out. Picture each unit as a car-wash tunnel: a vector instruction sends a train of 64 cars through it, one car per cycle. The whole question is which trains may roll at the same time.

Now the dependences. MULVS.D needs V1, which L.V is still filling. Without chaining, the multiply waits until the load has written the whole of V1 — the last of its 64 elements — so the two cannot share a convoy. With chaining, the first element of V1 goes from the load unit straight into the multiplier, the way forwarding passes a result to the next instruction in the five-stage pipeline. The multiply trails the load by a few cycles, element by element, inside the same chime: chaining is forwarding for vectors.

Without chaining every true dependence ends a convoy: the multiply comes after the first load, the add after the multiply, the store after the add — four convoys, 4 × 64 = 256 cycles. With chaining the multiply joins the first load and the add joins the second load: three convoys, 3 × 64 = 192 cycles. The store would chain on the add too, but the load/store unit is busy with L.V V3 in that convoy. The paper asks for the same result as a table, one row per convoy and one column per unit:

With chaining, only the structural rule — one instruction per unit — separates convoys; without it, every true dependence does too.

The quiz of every paper, in four moves

The three official papers (July 2024, June 2025, June 2026) each have a convoy quiz worth 1 point, plus 1 for the table or timeline that motivates it, on a machine described in the same words: a vector register file of "32 vectors of 16 elements" (or of 8) "per 64 bits/element", "One Load/Store Vector Unit with operation chaining and memory bandwidth 64 bits", one ADD/SUB and one MUL/DIV unit, both with chaining. The February 2025 and January 2026 papers transcribed in the notes have a quiz of the same kind. Four moves solve it.

1. Read the chime. VL is the number of elements per register, 16 or 8. A memory bandwidth of 64 bits moves one 64-bit element per cycle, and so does every arithmetic unit: a convoy lasts VL cycles.
2. Find the floor. Count the instructions of each unit. The busiest unit needs at least that many convoys. On every paper's machine it is the single load/store unit, so the number of vector loads and stores is a lower bound on m.
3. Pack. Put each instruction into the earliest convoy where its unit is still free and each source vector is either complete — written in an earlier convoy — or produced in the same convoy by an instruction it chains to. An instruction does not wait for unrelated instructions above it in the listing.
4. Multiply and draw. Cycles = m × VL. Then fill the paper's table (one row per convoy, one column per unit) or its timeline (one strip of VL cycles per convoy).

Move 3 is the counting of the notes' solutions and of every table in this lesson: an independent instruction may run ahead of unrelated ones above it. In the June 2025 quiz the first multiply joins the first load, although two more loads stand between them in the listing; move 2 then explains why that quiz cannot go below four convoys.

Know the other reading too. A vector unit that issues strictly in listing order cannot start that multiply before the third load, and packing that way gives the June 2025 code 6 convoys, 48 cycles; on the other papers' code both readings give the same count. No official key settles it, so write the assumption in one line under your table. Try the moves yourself before reading the solutions below.

Now the longest quiz, from the February 2025 paper (transcribed in the notes, p. 580): nine instructions on registers of 8 elements, same machine.

L.V      V1, RA
L.V      V3, RB
MULVS.D  V1, V1, F0
ADDVV.D  V2, V1, V1
MULVS.D  V2, V2, F0
ADDVV.D  V3, V2, V3
S.V      V1, RX
S.V      V2, RY
S.V      V3, RZ

Move 2 gives the answer before any table: two loads and three stores on one load/store unit need at least 5 convoys. Move 3 shows that five are enough, so the answer is 5 convoys; 5 × 8 = 40 clock cycles — Answer 4, as the notes say.

In the first convoy the load feeds the multiply, which feeds the add: a chain of three. In the second, MULVS.D V2 reads the V2 that the first convoy completed, and ADDVV.D V3 chains on two producers at once, the multiply and the load of V3. The notes' own table puts S.V V1 before the second load — also legal, since V1 is complete after the first convoy — with the same count. Without chaining every true dependence costs a convoy, and the chain L.V V1 → MULVS.D V1 → ADDVV.D V2 → MULVS.D V2 → ADDVV.D V3 → S.V V3 has six links: 6 convoys, 48 cycles.

Why 8 cycles per convoy? The notes never say. Each register holds 8 elements of 64 bits; the load/store unit moves 64 bits — one element — per cycle, and so does every arithmetic unit; the start-up of the pipelines is not counted. A convoy is therefore a chime of 8 cycles, and every option of the quiz is a multiple of 8: 16, 24, 32, 40, 48.

Lanes: several elements per cycle, the same instructions

So far a unit handled one element per cycle, and a chime lasted VL cycles. Hardware can do better without touching the program: it replicates each pipeline into L lanes. Take ADDVV.D V3, V1, V2 on 16 elements. With one lane, element 0 enters the adder in the first cycle and element 15 in the sixteenth. With four lanes, four adders take elements 0 to 3 in the first cycle and 4 to 7 in the second: the vector is through in 4 cycles.

The interleaving of Fig. 2 holds for every register: element i lives in lane i mod L, so an element-wise operation never needs data from another lane, and the lanes need no wires between them. Each lane is a slice of the register file plus one pipeline of each unit (p. 405; the notes' Figure 30, p. 392, draws elements 0, 4, … 60 in the first of four lanes). With L lanes a vector of n elements takes ⌈n / L⌉ cycles (p. 405), and the chime model becomes:

The notes' Example 3 is DAXPY with VL = 64: the multiply takes 64 cycles on one lane and 16 on four, the add likewise (p. 405). Chained, the three convoys take 3 × 16 = 48 cycles instead of 192.

The instruction set does not change: the same ADDVV.D runs on one lane or on eight, and the same binary gets faster — the notes say vector machines scale "transparently" with hardware width, unlike scalar unrolling (p. 406), which rewrites the code for every width. The cost is paid elsewhere: the register file needs read and write ports for every lane, and the load/store unit must deliver L words per cycle. Where those words come from is the subject of the last section.

Lanes divide the chime, not the number of convoys: T ≈ m × ⌈VL/L⌉.

Longer than a register: MVL, VLR and strip mining

A loop rarely has exactly 64 iterations. Take n = 100 on VMIPS, whose registers hold 64 elements. The first pass handles elements 0 to 63. If every vector instruction always processed a whole register, the second pass would touch elements 64 to 127: 28 elements past the end of the arrays, read and written by mistake (pp. 407–408). One register fixes it.

The second pass therefore sets VLR = 36 and processes elements 64 to 99; the other 28 entries of the register are simply not used. MVL is the hardware; VLR is the knob the software turns.

When n is larger than MVL the compiler applies strip mining: it cuts the loop into strips of at most MVL elements — ⌊n / MVL⌋ full strips and, when n mod MVL is not zero, one short strip with VLR = n mod MVL (eq. 84, p. 408). The notes' example: 1000 = 15 × 64 + 40.

Two papers ask it as a quiz: for (i=0; i<260; i++) Y[i] = X[i] + Y[i]; on VMIPS with "8 registers of 64 elements" (July 2024) or "16 Vector registers of 32 elements" (June 2026) — which transformation: trace scheduling, software pipelining, strip mining or a mask register? Strip mining: 260 = 4 × 64 + 4, or 260 = 8 × 32 + 4. Trace scheduling and software pipelining are compiler techniques that reorder scalar instructions for a VLIW (lesson 21 meets this very quiz from their side), and a mask register is for an if inside the loop, which this loop does not have. The number of registers is not the problem either: the loop needs two.

Hennessy and Patterson write the strip-mined loop with the short strip first; the notes put it last. Both are correct:

low = 0;
VL = n % MVL;                      /* odd-size strip first */
for (j = 0; j <= n / MVL; j++) {   /* one pass per strip   */
    for (i = low; i < low + VL; i++)
        Y[i] = a * X[i] + Y[i];    /* vector code, VLR = VL */
    low = low + VL;
    VL = MVL;                      /* later strips are full */
}

The inner loop becomes one sequence of vector instructions, executed once per strip with VLR set to VL. The price is the scalar strip loop around them, a few instructions per strip that the papers' counts ignore.

An if inside the loop: the vector mask register

Now a loop that is parallel but not uniform (p. 409):

for (i = 0; i < 64; i++)
    if (X[i] != 0)
        X[i] = X[i] - Y[i];

Every iteration is independent, yet a single SUBVV.D would subtract at every element, including those the if skips. A vector processor has one program counter for all 64 elements: there is nothing to branch around element by element. Instead it turns the condition into data.

In Hennessy and Patterson's VMIPS, written with the papers' load and store, the loop becomes (F0 holds 0.0):

L.V      V1, RX       # V1 ← X
L.V      V2, RY       # V2 ← Y
SNEVS.D  V1, F0       # VM(i) = 1 if V1(i) != F0
SUBVV.D  V1, V1, V2   # subtract under the mask
S.V      V1, RX       # X ← V1

The mask keeps the loop vectorizable, with no scalar fallback, and works with any vector instruction (p. 409). What it does not do is save time: SUBVV.D still streams all 64 elements through the subtracter, masked or not, so it takes the same 64 cycles. In Fig. 3, 6 of the 16 cycles do no useful work; the more elements are masked off, the lower the efficiency — still better than running the loop as scalar code (p. 410). Lesson 32 meets the same price under another name, branch divergence on a GPU.

A mask preserves vectorizability, not speed: a masked element still costs its cycle.

Memory banks: when the stride keeps hitting the same bank

A load/store unit that delivers one 64-bit word per cycle needs a memory that can keep up, and one memory bank cannot: after an access it stays busy for several cycles. Vector machines therefore spread consecutive words over many memory banks, round-robin (p. 411):

With 8 banks, words 0 to 7 sit in banks 0 to 7 and word 8 in bank 0 again. Walk a row of a C matrix — consecutive words, stride 1 — and every bank serves one element and is not asked again for eight cycles. Now walk a column of a matrix whose rows hold 128 words: consecutive elements are 128 words apart, and 128 mod 8 = 0, so every element lands in the same bank (p. 412). The notes' picture is a supermarket with eight checkouts and eight shoppers all queuing at checkout 0, while seven cashiers wait.

The number of different banks a strided access visits is (p. 412):

Stride 1 and every odd stride visit all 8 banks; stride 2 visits 4; stride 4, two; strides 8, 32 and 128 visit one. Whether that costs time depends on how long a bank stays busy. Hennessy and Patterson's example, not in the notes: 8 banks, a bank busy time of 6 cycles, a memory latency of 12, a 64-element load. With stride 1 each bank is reached again only after 8 elements, when its 6 busy cycles are over: 12 + 64 = 76 cycles. With stride 32 every access waits for the one bank: 12 + 1 + 6 × 63 = 391 cycles, five times slower. The steps below show where the gcd comes from, and when a repeated bank hurts:

1. Element k of an access with stride s, starting at word address \(a_0\), lies at \(a_0 + k s\); with N banks its bank is

   \[ b_k = (a_0 + k\,s) \bmod N . \]

2. Elements k and k + d fall in the same bank exactly when the extra distance d·s is a multiple of N:

   \[ d\,s \equiv 0 \pmod{N} . \]

3. Write \(g = \gcd(s, N)\), so \(s = g s'\) and \(N = g N'\) with s′ and N′ coprime. Dividing by g, d·s′ must be a multiple of N′; since s′ shares no factor with N′, d itself must be one, and the smallest such d is

   \[ d = N' = \frac{N}{\gcd(s, N)} . \]

4. So the banks repeat with period N / gcd(s, N): the first N / gcd(s, N) elements all fall in different banks, and the access visits exactly that many — formula (86).

5. At one access per cycle the same bank is hit again every N / gcd(s, N) cycles, but it is free only after its busy time t. The access stalls exactly when the bank comes back too soon:

   \[ \frac{N}{\gcd(s, N)} \lt t . \]

6. 8 banks and t = 6: stride 1 gives 8 ≥ 6, no stall (76 cycles); stride 4 gives 2 < 6, a wait every second element (200 cycles); stride 32 gives 1 < 6, a wait at every element (391 cycles).

The notes list three fixes (pp. 412–413). Change the traversal order, so that the inner loop walks along rows — the loop interchange of lesson 25, met there for caches. Pad each row with one unused word: the column stride becomes 129, gcd(129, 8) = 1, and the column spreads over all eight banks, as in Fig. 4. Or store the matrix column by column (Fortran, MATLAB) when columns are what the code walks. With a power-of-two number of banks every odd stride is harmless (given at least as many banks as busy cycles), while more banks of the same kind do not help a stride that is a multiple of their number: 16 banks and stride 128 still give one bank.

Sparse data have no stride at all. A gather loads a vector from the addresses given by an index vector and a scatter stores to them (p. 413) — LVI and SVI in Hennessy and Patterson's VMIPS. They keep sparse matrices vectorizable, at a cost: every element is a separate access, free to collide with the others.

Back to the quiz of the hook. The unit that decides is the load/store unit. The seven lines contain four memory instructions, and one load/store unit takes one of them per convoy: at least four convoys, so Answers 1 and 2 are impossible on sight. Four are enough — L.V V1 with ADDVS.D V2 and MULVS.D V2 chained behind it, L.V V3 with its add, then one store per convoy. Answer 4, 5 convoys and 80 cycles, is the count without chaining. Answer 3 is right: 4 × 16 = 64 clock cycles. And this section showed why that unit matters twice: its one word per cycle is itself a promise that only the banks can keep. A vector processor is as fast as its memory lets it be.