Vector Chaining and What It Costs in the Register File

A vector operation on a length-64 vector does not take 64 cycles of arithmetic and then finish. Its functional unit is pipelined, accepting one element per cycle and producing one result per cycle after a fixed latency. The interesting question is what happens when the next operation needs those results. One answer serialises the two operations: the first writes all its elements to the vector register, and the second reads them back after a register file round trip. The other forwards each result element as it appears, so the second unit starts working while the first is still finishing.

The second answer is chaining, and it turns a sequence of vector operations into an assembly line. It is the mechanism that made the early vector machines fast, and it is a distinct concept from both superscalar issue and from the SIMD lane model in Fixed-Width SIMD Lanes Versus Scalable Vector Registers, because chaining is decided at run time by a scoreboard rather than by the encoding.

Latency without chaining

Model a vector unit with an adder whose pipeline accepts one element per cycle and produces its output five cycles after input, and a multiplier with the same throughput and a latency of seven. For d = a * b + c over 64 elements, executed as two separate vector instructions:

The multiply issues its 64 elements one per cycle, so the last element enters the multiplier at cycle 64. The first result appears after the multiplier’s latency of seven cycles, at cycle 8, and the last result appears at cycle 71. The add cannot begin until the multiply has written its final element, unless the two are chained, so it starts issuing at cycle 72, produces its first output at cycle 77, and finishes at 139. The whole sequence takes about 139 cycles.

With chaining, the multiplier’s output element for index i is forwarded directly to the adder’s input for index i, and the adder begins as soon as the multiplier’s first result is available. Element i’s add finishes at cycle i plus the two latencies, so the last add result appears at cycle 64 plus twelve, about 76 cycles rather than 139.

The saving is not the sum of latencies minus one; it is the elimination of the serialisation, one full vector’s worth of issue time per dependent operation. For a long chain of dependent vector operations, latency without chaining accumulates as the sum of the vector lengths, which is proportional to the number of operations. Latency with chaining accumulates as the sum of the pipeline latencies only, which does not depend on vector length at all.

The scoreboard’s role

Chaining is dynamic. The compiler emits plain vector instructions, each naming a vector register for its destination and for its sources, and a hardware scoreboard tracks the progress of each register: which elements have been written, which unit is writing them, and which operation is waiting on them.

When an instruction is issued, the scoreboard checks its sources. If a source register is still being written by an in-flight operation, the instruction is held, but held in a state that allows it to begin as soon as the first element arrives rather than when the last does. The scoreboard must therefore know, per source, how far the producer has progressed, so it can start the consumer with the element index the producer has just finished.

This requires each vector register to have an associated element counter visible to the scoreboard, and it requires the forwarding network to connect each functional unit’s output to the inputs of the other units without going through the register file. On a machine with six functional units, that is thirty forwarding paths, each vector-wide. The cost grows with the square of the unit count, the same quadratic that limits superscalar width, and it is the reason chaining is implemented for a limited set of unit pairs rather than all of them in some designs.

Chain slots as the real resource

Once chaining works, the number of functional units stops being the bound. A vector machine can keep every unit busy with a single dependent chain, because the chain propagates through the units one element per cycle. What it cannot do is keep two independent chains going simultaneously if the register file has only one write port per cycle, or if the forwarding network has only one path per unit.

Hence the notion of chain slots: the number of independent chains the register file and forwarding network can sustain. A machine might have two vector adders, a multiplier, a shift unit, and a memory unit, but only three chain slots, because the register file can accept three vector results per cycle and the bypass network can route three. The fourth and later chains stall behind the first three even though the arithmetic units are free.

This is a resource bound analogous to the reservation station size in a superscalar design, and it is computed the same way: the number of concurrent chains a loop can sustain is the number of chain slots, so throughput is bounded by the slot count rather than by the number of independent chains the loop offers. A loop with five independent chains on a three-slot machine completes three chains in the time one chain alone would take, so it runs at about three times the single-chain rate, not at the fivefold rate the chain count would suggest.

Register file structure for vector machines

A vector register file is large and highly ported. A machine with eight vector registers of 64 elements of 64 bits each has 4 KiB of vector state, and each register must be readable by at least the units that consume it and writable by the units that produce it. The port problem described for scalar registers in Register File Ports and Operand Delivery is worse here, because a vector register’s read is a stream rather than a single access.

Three structures are used. The first is a set of banks with an interleaved layout: element i of vector register v lives in bank i mod B, so reading a full vector proceeds one element per bank per cycle, and the throughput is B elements per cycle from a banked structure with B banks. The second is a set of dedicated buffers per unit, into which a vector is copied before use and out of which it is written, which decouples port count from element rate at the cost of copies. The third is to keep operands in registers and rely on chaining, so consumers rarely need to read the whole register from the file at once.

The banked layout has a well-known failure: a unit reading two vectors whose element indices map to the same bank at the same time conflicts. Because both reads stream in index order, both hit bank i mod B at the same time, so the conflict is systematic rather than random. The fix is to skew the banks by unit, so unit 0 reads bank i, unit 1 reads bank (i+1) mod B, and so on. A skewed banked file with B banks sustains B reads per cycle only if no two units are offset by a multiple of B, which is the classic skewing constraint.

A worked comparison

Consider a dot product of two length-n vectors, sum += a[i] * b[i], on a chained machine with one multiplier, one adder, and two chain slots.

Each iteration loads two vector elements from memory, multiplies them, and accumulates. The multiply and the accumulate form a dependent chain of length two, and successive iterations’ multiplies are independent, so the loop’s parallelism is the number of multiplies in flight. With two chain slots, the machine can have one multiply and one add active at a time. The load unit and the multiplier overlap, and the add follows the multiply with a latency gap.

If the loop is written as a single vector statement over n elements, the compiler emits one vector load pair, one vector multiply, and one vector add, and the chaining hardware overlaps them. The vector add is the recurrence, since it accumulates into the same register, so the add’s own latency bounds the vector iterations. Vectorising eliminates the loop-carried dependency at the element level but not at the vector level: the running sum still depends on the previous vector’s sum, unless the compiler keeps several partial sums, which is the same transformation described in Software Pipelining and Loop-Carried Dependences.

/* Four independent accumulators: the vector recurrence is now
   distance four, so the add latency is amortised over four chains. */
double dot4(const double *a, const double *b, int n)
{
    double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
    int i = 0;
    for (; i + 3 < n; i += 4) {
        s0 += a[i]     * b[i];
        s1 += a[i + 1] * b[i + 1];
        s2 += a[i + 2] * b[i + 2];
        s3 += a[i + 3] * b[i + 3];
    }
    for (; i < n; i++)
        s0 += a[i] * b[i];
    return (s0 + s1) + (s2 + s3);
}

What chaining does not fix

Chaining shortens the dependent path but does nothing for a chain that is longer than the machine’s forwarding network, and nothing for memory. A vector load from a cache line that is not present foregrounds the whole machine: the load unit stalls, the chained consumer stalls behind it, and the vector register’s element counter stops advancing. The mechanism that hides this is either multiple outstanding vector loads with more chain slots, or prefetching, or the hardware’s ability to continue other chains while one waits.

Chaining also interacts badly with register naming when the destination is the same as a source, as in an accumulating add where the destination register is also one of the sources. The hardware must not overwrite the source elements before the consumer has read them, which means either in-order element processing per register or a second physical copy. Implementations use the in-order rule, which is one reason vector operations on a given register proceed strictly in element order and cannot be internally reordered the way a superscalar machine reorders scalar instructions.

The result is a machine whose parallelism comes from the number of independent vector operations in a loop and from the number of chain slots, not from the width of any single operation. That is a different optimisation surface from the superscalar one, and mixing the two, as modern cores do with vector units behind a superscalar front end, means both structures must be filled simultaneously for the machine to approach its peak.