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 (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 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]];

Scatter

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 also

References

  1. ↑ BLAS Technical Forum standard, Chapter 3: Sparse BLAS.
This article is issued from Wikipedia - version of the 8/26/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.