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.

DefinitionsEdit

GatherEdit

A sparsely populated vector   holding   non-empty elements can be represented by two densely-populated vectors of length  ;   containing the non-empty elements of  , and   giving the index in   where  's element is located. The gather of   into  , denoted  , assigns   with   having already been calculated.[1] A C implementation is

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

ScatterEdit

The sparse scatter, denoted   is the reverse operation. It copies the values of   into the corresponding locations in the sparsely populated vector  , i.e.  .

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

See alsoEdit

ReferencesEdit