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.

Definition

Denoting by $idx$ the list of indices of sparse vector $x$, the sparse gather of dense $y$ into $x$ denoted $x \leftarrow y|_x$, assigns $x(i)=y(idx(i))$.^[1]

The sparse scatter, denoted $y|_x \leftarrow x$ is the reverse operation. It copies the nonzero values of sparse $x$ into the corresponding locations in the dense vector $y$, i.e. $y(idx(i))=x(i)$.

Examples

Gather

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

Scatter

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

See also

• SIMD
• Vectorization
• Compute kernel

References

1. BLAS Technical Forum standard, Chapter 3: Sparse BLAS.