Gather-scatter (vector addressing)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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[edit]

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[edit]

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[edit]

References[edit]