SIMD Series – GATHER/SCATTER OperationsAs we know, SIMD registers can communicate with the scalar domain (or more accurately, memory) using LOAD/STORE operations. The downside of these operations is that they only allow moving contiguous data elements in memory. However, in our code, we often need to access non-contiguous memory. This tutorial will explain the GATHER/SCATTER operations and how they relate to LOAD/STORE operations.In some cases, you may want to fill registers using data from non-contiguous memory locations. Several use cases include:1) Accessing every other element in an array (Stride Access)2) Accessing elements of an array with newly computed offsets (Indexed Access)3) Accessing elements in a different order (Random Access)This article discusses the first two cases. The last case requires a more thorough discussion in the context of permutations, so we will cover that in the next tutorial.So what is the SCATTER operation? It is the inverse operation of GATHER, which “scatters” the contents of a register into memory. Thus, it is similar to the STORE operation, but allows for non-contiguous memory access.
1. Stride Access
When accessing memory fields at equal distances, the memory access pattern is called stride access. This distance is called the stride (not to be confused with the SIMD stride). A simple illustration of stride access:
As you can see, STRIDE-1 access is a special case of the GATHER operator: LOAD operation. So why do we have separate LOAD and GATHER operations (as well as STORE and SCATTER), instead of simplifying things and just using GATHER? There are two explanations: first is a historical issue: early processors only implemented LOAD instructions to move data between memory and scalar registers. Since you can access any element using a single scalar index in the scalar domain, there was no need for a more flexible operation. Second, there is a performance aspect: in addition to passing the base memory address, the GATHER instruction also needs to compute the relevant information for the specified offset. Regardless of how the instruction is implemented within the processor, this adds extra degrees of freedom, which may mean longer execution time, but definitely means additional circuitry.Performance TipUse LOAD/STORE operations whenever possible, and avoid GATHER/SCATTER as much as possible. In most cases, this means you must modify your data structures/algorithms. But only use GATHER/SCATTER when you are sure you cannot redesign the structure.When performing stride access, you need to know what the base address is (passed as a pointer to the start of the data) and the stride value (passed as a scalar integer). The stride is always passed as the number of elements rather than as a memory offset, so programming can be simplified.The following code demonstrates how to perform stride memory access:
float a[LARGE_DATA_SIZE];uint32_t STRIDE = 8;...for(int i = 0; i < PROBLEM_SIZE; i+=8) { SIMDVec<float, 8> vec; // Note that we have to scale the loop index. int offset = i*STRIDE; // 'load' the data to vec. vec.gather(&a[offset], STRIDE); // do something useful vec += 3.14; // store the result at original locations vec.scatter(&a[offset], STRIDE);}When using stride access, we must pass the address of the first element. This is done by calculating the offset variable in each iteration. Then, the GATHER operation uses this local base address and scalar stride to compute the offset for the respective elements.Once the necessary calculations are finished, the updated results are stored back at their original locations.
2. Indexed Access
Indexed access is more general than stride access. The main difference is that you must pass a SIMDVec of unsigned integer indices, rather than passing a scalar stride parameter.Indexed access can be understood using the following diagram:
The advantage of this pattern is that each element can be retrieved using a dedicated index. The downside is that such indexing can completely disrupt hardware-based memory prefetching, negatively impacting performance. Also note that all elements may be far apart, meaning more cache lines must be moved to the lowest cache level. An example of using indexed access:
float a[LARGE_DATA_SIZE];int indices[PROBLEM_SIZE];uint32_t STRIDE = 4;...for(int i = 0; i < PROBLEM_SIZE; i+=8) { SIMDVec<float, 8> vec; // Here we are using precomputed indices, // but they can be computed on-the-fly if necessary. SIMDVec<uint32_t, 8> indices_vec(&indices[i]); // 'load' the data to vec. vec.gather(&a[0], indices_vec); // do something useful vec += 3.14; // store the result at original locations vec.scatter(&a[0], indices_vec);}The basic difference is that we will be using a vector of unsigned integers with 32b indices, rather than passing a scalar stride.Note: Currently, this library is using unsigned integer vectors with the same precision as all gathered vector’s scalar elements. This will cause trouble when dealing with mixed precision and small types (like uint8_t) that do not have enough bits to represent the full range of indices. The library will be updated to always use uint32_t index vectors.
3. Ensuring Conditional Access
One of the issues you may encounter when writing code is trying to handle conditional statements. Consider the following scalar code:
float a[PROBLEM_SIZE], b[PROBLEM_SIZE];float c[LARGE_DATASET_SIZE];...for(int i = 0; i < PROBLEM_SIZE; i++) { // Here we are checking if for some reason one of the // values in (a[i],b[i]) pair is not determined properly. if (std::isfin(a[i] - b[i])) { // Calculate the index only if both 'a' and 'b' are well defined int index = int(a[i] - b[i]); // 'gather' single element at a time float temp = c[index]; // Do something with the value temp += 3.14; // Update the values of 'c' c[index] = temp; }}You should already know: see UME::SIMD Tutorial 8: Conditional execution using masks. The vector code using masks will perform all operations within the if branch. Rewriting the above code:
float a[PROBLEM_SIZE], b[PROBLEM_SIZE];float c[LARGE_DATASET_SIZE];...// For simplification we are assuming that: ((PROBLEM_SIZE % 8) == 0)for(int i = 0; i < PROBLEM_SIZE; i+= 8) { // Here we are checking if for some reason (e.g. a design decision) one // of the values in (a[i],b[i]) pair is not determined properly. SIMDVec<float, 8> a_vec(&a[i]), b_vec(&b[i]); SIMDVecMask<8> condition = (a_vec - b_vec).isfin(); // if (std::isfin(a[i] - b[i])) { SIMDVec<uint32_t, 8> indices = a_vec - b_vec; SIMDVec<float, 8> temp; temp.gather(&c[0], indices); // This is WRONG!!! temp.adda(condition, 3.14); // only change selected elements temp.scatter(&c[0], indices); // Again WRONG!!!}Why are the GATHER and SCATTER operations in this code wrong? They try to access memory even if the indices are incorrect. But GATHER and SCATTER do not care about that. They must trust that we can provide them with the correct indices, at least for performance reasons. If the indices are incorrect, they will attempt to access memory that may be outside the bounds of the c dataset. This could lead to memory faults, so we must use conditional masks to protect memory reads and writes:
float a[PROBLEM_SIZE], b[PROBLEM_SIZE];float c[LARGE_DATASET_SIZE];...// For simplification we are assuming that: ((PROBLEM_SIZE % 8) == 0)for(int i = 0; i < PROBLEM_SIZE; i+= 8) { // Here we are checking if for some reason (e.g. by design?) one of the // values in (a[i],b[i]) pair is not determined properly. SIMDVec<float, 8> a_vec(&a[i]), b_vec(&b[i]); SIMDVecMask<8> condition = (a_vec - b_vec).isfin(); // if (std::isfin(a[i] - b[i])) { SIMDVec<uint32_t, 8> indices = a_vec - b_vec; SIMDVec<float, 8> temp; temp.gather(condition, &c[0], indices); // Now the read is CORRECT!!! temp += 3.14; // we don't have to mask this operation temp.scatter(condition, &c[0], indices); // Again no problems here.}Therefore, in the corrected version, we must simply pass an additional mask parameter to the memory access operations, rather than to the arithmetic operations. The library will take care of ensuring safe reads so that they only access allowed memory addresses.
4. Summary
This tutorial introduced the concept of GATHER/SCATTER operations and explained why they are a useful addition to our SIMD programming model. We explored stride and indexed memory access patterns and explained how this concept generalizes the LOAD/STORE operations.While very useful, the “GATHER/SCATTER” operations are a double-edged sword that can make our lives easier but can also ruin our performance.
5. Original Article
https://gain-performance.com/2017/06/15/umesimd-tutorial-9-gatherscatter-operations/