Gather/scatter (vector addressing)

Gather/scatter is a type of memory addressing that at once collects (gathers) from, or stores (scatters) data to, multiple, arbitrary indices. Examples of its use include sparse linear algebra operations, sorting algorithms, fast Fourier transforms, and some computational graph theory problems. 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 and scatter operations. 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. Assuming no pointer aliasing between x[], y[],idx[], a C implementation is for (i = 0; i < N; ++i) x[i] = y[idx[i]]; 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]; x86-64 CPUs which support the AVX2 instruction set can gather 32-bit and 64-bit elements with memory offsets from a base address. A second register determines whether the particular element is loaded, and faults occurring from invalid memory accesses by masked-out elements are suppressed. The AVX-512 instruction set also contains (potentially masked) scatter operations. The ARM instruction set's Scalable Vector Extension includes gather and scatter operations on 8-, 16-, 32- and 64-bit elements. InfiniBand has hardware support for gather/scatter. Without instruction-level gather/scatter, efficient implementations may need to be tuned for optimal performance, for example with prefetching; libraries such as OpenMPI may provide such primitives.