Strided, Indexed, and Gather Memory Access

A contiguous vector load of sixteen 32-bit elements reads 64 bytes, which is exactly one cache line on the common architectures. The address generator computes one address, the cache delivers one line, and the unit has its operand. Nothing about this resembles sixteen scalar loads, and it is the reason vector code can reach memory bandwidth that scalar code approaches only with deep unrolling and explicit prefetching.

The other access patterns do not have this property. A stride of four elements reads 16 bytes out of every 64, so the same sixteen elements touch four lines and use a quarter of each. An indexed access reads element i from an address that depends on data, so the hardware cannot compute a base plus stride and has to generate each address separately. Those patterns are common in real code, and the memory system’s response to them determines whether the vector unit is fed or starved.

Strides and the fraction of each line consumed

A strided access with stride s elements and element size e bytes reads one element per s*e bytes of address space. The number of cache lines touched by a vector of L elements is ceil(L * s * e / line_size) distributed across the access; each line delivers line_size / (s * e) useful elements, which is the fraction of the line actually consumed.

For a stride of two 32-bit elements and a 64-byte line, the fraction is eight elements per line out of sixteen, half the bandwidth wasted. For a stride of eight, the fraction is two out of sixteen, seven-eighths wasted. The hardware does not fetch less than a line on a miss, so the wasted bytes are fetched, occupy cache capacity, and consume bus bandwidth regardless.

Two mitigations exist. Software can restructure so that the strided access happens once and the transposition is done in registers or through a middle step, which is the classic blocked-transpose technique. Hardware can provide stride hints in the prefetcher so that the next line of the stride pattern is fetched early, which does not reduce waste but hides the latency. Neither reduces the bytes moved, and on a bandwidth-bound kernel a stride of two costs close to twice the traffic of a contiguous access of the same element count.

Strided accesses have one favourable case: when the stride is such that a whole number of elements fit in a line and the access starts line-aligned, the hardware can load the line once and extract the elements with a shuffle. A stride of four 32-bit elements on a 64-byte line is exactly this case, and compilers that can prove the alignment will emit a load plus shuffle rather than a strided load instruction.

Two-step access and the indexed form

Many ISAs separate the stride from the access. A vector load with a unit stride reads memory; a separate instruction sets an element stride register, or the access takes a stride operand, or the vector is loaded contiguously into a register set and a second instruction reads it with a stride. The last form, often called a two-step or register-level strided access, is attractive because the memory system sees only contiguous loads; the strided pattern is realised by a crossbar between register banks. The cost is that the number of register banks must equal the stride for the access to be conflict-free, which limits the supported strides to the powers of two the banks implement.

The indexed form is what remains when the offsets are arbitrary. An index vector holds one address or one offset per element, and a gather instruction reads each element from its own address.

   # Each element's address comes from a register element.
   vsetvli  t0, a0, e32, m4
   vluxei32.v v0, (a1), v4    # v0[i] = mem[a1 + v4[i]]  (zero-extended offsets)
   vse32.v   v0, (a2)

Nothing about this is line-oriented. Each element is an independent address, and each one may miss. The hardware’s job is to check them against the cache, coalesce the ones that fall in the same line, and queue the remaining misses. On a machine that can coalesce, sixteen indices falling in one line produce one miss. On a machine that cannot, they produce sixteen.

Gather as a sequence of cache transactions

A gather instruction decompresses into up to L independent memory accesses. The load/store unit processes them over several cycles, and the rate is limited by the number of address generation paths and the number of outstanding misses the unit can track.

The miss status holding registers are the binding limit. A machine with, say, thirty-two outstanding miss entries can have only thirty-two gather elements in flight, so a gather that misses on every element proceeds in ceil(L/32) batches. For a gather of 128 elements that is four batches, and at a few hundred cycles per memory latency the instruction takes over a thousand cycles for work that a handful of contiguous loads would have covered. This is the single most important fact about gather: it converts a vector instruction into a scalar-like burst of misses, and its performance depends almost entirely on locality, not on the vector width.

The write side has the same structure. A scatter writes each element to its own address, and the memory system must merge partial-line writes. A line that receives one element from one gather and another from a later one requires either a read-for-ownership of the line or a write-combining buffer that holds partial lines until they are complete. The former doubles the traffic per element written; the latter depends on the writes being close enough in time and address to combine.

Compression helps the scatter side. When a mask marks a subset of lanes, a compress operation packs the active elements into a contiguous prefix, so a sparse scatter becomes a shorter dense store, or a shorter scatter, and the line-level write combining has fewer partial lines to reconcile. The mask machinery that makes this possible is described in Mask Registers, Tail Handling, and the Cost of the Last Iteration; the gather side has no equivalent, because the addresses come from data and cannot be compacted without another gather to read them.

The bandwidth account

A vector unit with W lanes and a clock of f cycles per second, executing one vector arithmetic operation per cycle, consumes 2We bytes of operands and produces W*e bytes of results per cycle, where e is the element size. For W of sixteen and e of four bytes, that is 128 bytes read and 64 bytes written per cycle.

A cache can deliver one line of 64 bytes per cycle, so the arithmetic would need three cache accesses per cycle to keep up. No general-purpose register file and cache combination sustains that from DRAM; even an L1 hit delivers at most a line per cycle, and the ports to the vector register file have their own limit as described in Register File Ports and Operand Delivery.

The consequence is a ratio that designers state explicitly: the arithmetic intensity required to keep the vector unit busy. If the loop reads two operands and writes one per element, it moves three elements per element of arithmetic, and the unit is bandwidth-limited on any access that misses to DRAM. Loops that reuse data in registers or in a cache-resident tile move fewer bytes per operation and can be arithmetic-limited. This is the same reasoning that motivates tiling and blocking in numeric libraries, and it is why vector width beyond a point does not help a streaming kernel: the memory system, not the lanes, is the limit.

Prefetching recovers some of the gap by overlapping misses with computation, but prefetchers work on address patterns. A strided stream is easy to prefetch once the stride is detected. An indexed gather is not, because the addresses depend on data that may not have been computed yet, and the prefetcher sees an apparently random sequence. For gathers, the only reliable technique is to arrange the data so the access becomes contiguous or strided before the loop runs, which is a change to the data layout and often to the algorithm.

When to accept the gather

The gather is worth using when the alternative is a scalar loop with the same access pattern. It still merges the addresses into one instruction, it still allows the arithmetic to be vectorised, and the memory system sees the same number of accesses either way. The instruction is a compact encoding of a loop the compiler would otherwise have to emit, and the saving is front-end bandwidth rather than memory traffic.

It is not worth using to convert a contiguous access into an apparently irregular one, which happens when a data structure’s layout was chosen for other reasons. The response is to change the layout: split an array of structures into parallel arrays, keep the hot fields adjacent, and make the access unit-stride for at least one of the operands. Vector units reward regularity, and the compiler’s ability to see that regularity is the subject of Loop Dependences and What Blocks Vectorisation.