Gather-scatter (vector addressing)

This article is about the vector addressing type. For the I/O method, see Vectored I/O.

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

References

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