Gather/scatter (vector addressing)

A sparsely populated vector ${\displaystyle y}$  holding ${\displaystyle N}$  non-empty elements can be represented by two densely populated vectors of length ${\displaystyle N}$ ; ${\displaystyle x}$  containing the non-empty elements of ${\displaystyle y}$ , and ${\displaystyle idx}$  giving the index in ${\displaystyle y}$  where ${\displaystyle x}$ 's element is located. The gather of ${\displaystyle y}$  into ${\displaystyle x}$ , denoted ${\displaystyle x\leftarrow y|_{x}}$ , assigns ${\displaystyle x(i)=y(idx(i))}$  with ${\displaystyle idx}$  having already been calculated.^[4] Assuming no pointer aliasing between x[], y[],idx[], a C implementation is

for (i = 0; i < N; ++i)
    x[i] = y[idx[i]];

The sparse scatter, denoted ${\displaystyle y|_{x}\leftarrow x}$  is the reverse operation. It copies the values of ${\displaystyle x}$  into the corresponding locations in the sparsely populated vector ${\displaystyle y}$ , i.e. ${\displaystyle y(idx(i))=x(i)}$ .

for (i = 0; i < N; ++i)
    y[idx[i]] = x[i];

Scatter/gather units were also a part of most vector computers, notably the Cray-1. In this case, the purpose was to efficiently store values in the limited resource of the vector registers. For instance, the Cray-1 had eight 64-word vector registers, so data that contained values that had no effect on the outcome, like zeros in an addition, were using up valuable space that would be better used. By gathering non-zero values into the registers, and scattering the results back out, the registers could be used much more efficiently, leading to higher performance. Such machines generally implemented two access models, scatter/gather and "stride", the latter designed to quickly load contiguous data.^[5] This basic layout was widely copied in later supercomputer designs, especially on the variety of models from Japan.

As microprocessor design improved during the 1990s, commodity CPUs began to add vector processing units. At first these tended to be simple, sometimes overlaying the CPU's general purpose registers, but over time these evolved into increasingly powerful systems that met and then surpassed the units in high-end supercomputers. By this time, scatter/gather instructions had been added to many of these designs.

x86-64 CPUs which support the AVX2 instruction set can gather 32-bit and 64-bit elements with memory offsets from a base address. A second register determines whether the particular element is loaded, and faults occurring from invalid memory accesses by masked-out elements are suppressed.^{[6]: 503–4} The AVX-512 instruction set also contains (potentially masked) scatter operations.^{[6]: 539 [7]} The ARM instruction set's Scalable Vector Extension includes gather and scatter operations on 8-, 16-, 32- and 64-bit elements.^[8][9] InfiniBand has hardware support for gather/scatter.^[10]

Without instruction-level gather/scatter, efficient implementations may need to be tuned for optimal performance, for example with prefetching; libraries such as OpenMPI may provide such primitives.^[2][8]

• SIMD
• Vectorization
• Compute kernel
• Memory access pattern