SIMD系列-GATHER/SCATTER操作

yzsDBA

发布于 2023-08-09 15:25:02

4640

发布于 2023-08-09 15:25:02

文章被收录于专栏：PostgreSQL研究与原理解析PostgreSQL研究与原理解析

SIMD系列-GATHER/SCATTER操作

众所周知，SIMD寄存器可以使用LOAD/STORE操作与标量域（或者更准确的说是内存）进行通信。这些操作的缺点是：只允许移动内存中连续的数据元素。然而，我们代码中，经常需要访问非连续的内存。本教程中将解释GATHER/SCATTER操作以及他们如何类推到LOAD/STORE操作。

某些情况下，您可能希望使用来自非连续内存位置的数据填充寄存器。几个使用例子：

1）访问数组中的每隔一个元素（跨步访问）

2）以新计算的偏移量访问数组的元素（索引访问）

3）以不同顺序访问元素（随机访问）

本文讨论前两种情况。最后一类需要在permutations背景下进行更彻底的讨论，因此我们将在下一个教程中讨论。

那么什么是SCATTER操作呢？它是GATHER操作的逆操作，将寄存器的内容“分散”到内存中。因此类似于STORE操作，但能够进行非连续内存访问。

1、Stried access跨步访问

当访问的内存字段距离相等时，内存访问模式称为跨步。这个距离称为步幅（不要与SIMD步幅混淆）。跨步访问的简单图示：

正如你所见，STRIDE-1访问是GATHER操作符的特殊情况：LOAD操作。那为什么我们有单独的LOAD和GATHER操作（以及STORE和SCATTER），而不仅仅简化事情并仅使用GATHER？有2种解释，首先是一个历史问题：早期处理器仅实现LOAD指令在内存和标量寄存器之间移动数据。由于在标量域中，您可以使用单个标量索引访问任何元素，因此不需要更灵活的操作。其次，是性能方面：除了传递基内存地址外，GATHER指令还需要如何计算指定偏移的相关信息。无论指令在处理器内如何实现，这都是额外的自由度，可能意味着更长的执行时间，但肯定意味着额外的电路。

性能提示尽可能使用LOAD/STORE操作，并尽可能避免GATHR/SCATTER。在大多数情况下，意味着必须修改您的数据结构/算法。但当您确定无法重新设计结构时，才使用GATHE/SCATTER。

执行跨步访问时，需要知道什么是基地址（作为指向数据开头的指针传递）和跨步值（作为标量整数传递）。步幅始终作为元素数量而不是内存偏移量传递，以便可以简化编程。

以下代码展示了如何执行跨步内存访问：

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);
}

当使用跨步访问时，我们必须传递第一个元素地址。这是通过在每次迭代中计算偏移变量来完成的。然后，GATHER操作使用该本地基地址和标量步幅来计算相应元素的偏移量。

一旦必要的计算结束，更新的结果将存储回原始位置。

2、Indexed access索引访问

Indexed access比跨步访问更通用。主要区别在于，您必须传递无符号整数索引的SIMDVec，而不是传递标量步幅参数。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);
}

基本区别在于，我们将使用32b索引的无符号整数向量，而不是传递标量步长。

注意：目前该库正在使用与所有gathered向量的标量元素具有相同精度的无符号整数向量。当处理混合精度以及小类型（例如uint8_t）没有足够的位来表示完整范围的索引时，这回导致麻烦。该库将更新为始终使用uint32_t索引向量。

3、确保有条件访问

编写代码时可能会发现的问题之一是：尝试处理条件语句。考虑以下标量代码：

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;
 }
}

您应该已经知道：请参阅 UME::SIMD Tutorial 8: Conditional execution using masks。使用掩码的向量代码将执行if分支内的所有操作。将上面代码重写：

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!!!
}

为什么这段代码中的GATHER和SCATTER操作是错误的？即使索引不正确，它们都试图访问内存。但 GATHER 和 SCATTER 都不关心这一点。他们必须相信我们能为他们提供正确的索引，至少出于性能原因。如果索引不正确，它们将尝试访问可能位于“c”数据集边界之外的内存。这可能会导致内存故障，因此我们必须使用条件掩码来保护内存读取和写入：

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.
}

因此，在更正后的版本中，我们必须简单地将附加掩码参数传递给内存访问操作，而不是算术运算。该库将负责保护读取的安全，以便它们仅访问允许的内存地址。