Gather/scatter (vector addressing)

Gather and scatter are vector addressing operations used in parallel computing and vector processors. They are fundamental operations for accessing and manipulating data in a non-contiguous or irregular manner within memory. Unlike traditional vector load/store operations that access elements with a fixed stride, gather and scatter allow for indirect memory access based on an index vector.

Gather:

The gather operation reads elements from memory at addresses specified by an index vector and assembles them into a contiguous vector. The operation effectively gathers data scattered throughout memory into a more accessible, packed form.

More formally, a gather operation can be described as:

destination_vector[i] = memory[index_vector[i]]

For each index i, the element at the memory location specified by index_vector[i] is read and stored into the i-th position of the destination_vector.

Scatter:

The scatter operation performs the inverse of the gather operation. It takes a vector of data and writes its elements to memory locations specified by an index vector. In essence, it scatters the elements of the input vector into potentially disjoint memory locations.

A scatter operation can be described as:

memory[index_vector[i]] = source_vector[i]

For each index i, the element at the i-th position of the source_vector is written to the memory location specified by index_vector[i].

Key Characteristics:

• Irregular Memory Access: Gather and scatter operations enable the processing of data stored in non-contiguous memory locations, which is crucial for applications dealing with sparse data structures, graphs, and irregular grids.
• Index Vector: The index vector plays a central role, determining the source addresses for gather and the destination addresses for scatter. The index vector can contain absolute memory addresses or offsets relative to a base address.
• Parallelism: Both gather and scatter operations are inherently parallelizable, as each element access is independent of the others (assuming no write conflicts in the scatter operation). This allows them to be efficiently implemented on vector processors and GPUs.
• Handling Conflicts: Scatter operations can potentially lead to write conflicts if the index vector contains duplicate values. In such cases, different hardware and software implementations employ various strategies to resolve these conflicts, such as atomic updates, prioritizing one write over another, or generating errors.
• Performance Considerations: The performance of gather and scatter operations can be influenced by factors such as memory access patterns, cache coherence, and the specific hardware architecture. Efficient implementations often involve techniques like coalescing memory accesses and minimizing cache line thrashing.

Applications:

Gather and scatter operations find applications in a wide range of fields, including:

• Sparse Linear Algebra: Accessing non-zero elements in sparse matrices.
• Graph Processing: Implementing graph algorithms that involve traversing edges and updating node properties.
• Image Processing: Performing image transformations that require irregular pixel access.
• Scientific Computing: Solving partial differential equations on unstructured grids.
• Database Management: Indexing and retrieval of data based on complex criteria.