Gather-scatter (vector addressing)

Gather-scatter is a type of memory addressing that often arises when addressing vectors in sparse linear algebra operations. It is the vector-equivalent of register indirect addressing, with gather involving indexed reads and scatter indexed writes. Vector processors (and some SIMD units in CPUs) have hardware support for gather-scatter operations, providing instructions such as Load Vector Indexed for gather and Store Vector Indexed for scatter.

Definitions[]

Gather[]

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.^[1] Assuming no pointer aliasing between x[], y[],idx[], a C implementation is

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

Scatter[]

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];

See also[]

• SIMD
• Vectorization
• Compute kernel
• Memory access pattern

References[]