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 [math]\displaystyle{ y }[/math] holding [math]\displaystyle{ N }[/math] non-empty elements can be represented by two densely-populated vectors of length [math]\displaystyle{ N }[/math]; [math]\displaystyle{ x }[/math] containing the non-empty elements of [math]\displaystyle{ y }[/math], and [math]\displaystyle{ idx }[/math] giving the index in [math]\displaystyle{ y }[/math] where [math]\displaystyle{ x }[/math]'s element is located. The gather of [math]\displaystyle{ y }[/math] into [math]\displaystyle{ x }[/math], denoted [math]\displaystyle{ x \leftarrow y|_x }[/math], assigns [math]\displaystyle{ x(i)=y(idx(i)) }[/math] with [math]\displaystyle{ idx }[/math] having already been calculated. 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 [math]\displaystyle{ y|_x \leftarrow x }[/math] is the reverse operation. It copies the values of [math]\displaystyle{ x }[/math] into the corresponding locations in the sparsely populated vector [math]\displaystyle{ y }[/math], i.e. [math]\displaystyle{ y(idx(i))=x(i) }[/math].

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

See also

• SIMD
• Vectorization
• Compute kernel
• Memory access pattern