结构数组 (AoS) 与数组结构 (SoA) 随机读取向量化

Question

我的问题是关于书中的以下短语：

Unfortunately, the SoA form is not ideal in all circumstances. For random or incoherent circumstances, gathers are used to access the data and the SoA form can result in extra unneeded data being read into cache, thus reducing performance. In this case, use of the AoS form instead will result in a smaller working set and improved performance. Generally, though, if the computation is to be vectorized, the SoA form is preferred.

我猜测为什么 AoS 可能会导致更好的性能是当不同的，或者更好的是，同一结构中的所有字段都参与单一矢量化运行。

示例（只是一个概念，根本没有具体的或有效的代码）：

/*Note that the types of data I maintain the same intentionally, 
  to simplify discussion*/
struct Data {
     float mean; 
     float distribution[10]
}

并定义从某些数据源

随机得到的数组

Data aos[5];

现在，如果在矢量化循环中我做了类似的事情：

float* dataPtr =  &(aos[0].mean);

#pragma simd
for(int i=0; i< 60; i++)
{
   const float mean = (*dataPtr);
   /*do something with mean */

   dataPtr++;

   /*do something with distribution */
}

这将带来更好的性能，因为在 SoA 的情况下，我将在缓存行上推送更多我可能在此计算期间实际需要的信息。一些 CPU 预缓存？在 AoS 的情况下，反而会产生更好的性能。

我的假设是否正确，还是有其他问题？

Answer 1

是的，你似乎了解情况。

如果您从同一个结构中读取多个值，那么 CPU 将只需要为这些结构成员获取所需数量的缓存行 - 如果结构成员放置得当，可能只需要一个出去。所以缓存可能看起来像这样（其中 v 是你想要的值，空槽是其他值）

line 1: | v |   | v | v |   |   | v |   |

如果这些值每个都必须从单独的数组中读取，那么它将必须为每个值获取整个缓存行。所以缓存可能看起来像

line 1: |   |   | v |   |   |   |   |   |
line 2: |   |   |   |   | v |   |   |   |
line 3: |   | v |   |   |   |   |   |   |
line 4: |   |   | v |   |   |   |   |   |

如果您按顺序处理数组，那很好 - 您很快就会需要获取的额外值。

然而，如果你没有按顺序工作（用书的话说，你在 "random or incoherent circumstances"），那么每次获取超过你需要的东西都会浪费 space 在缓存中，与将所需的值放在一个结构中相比，您最终会使用更多的内存带宽。

Answer 2

您可以通过两种方式并行化您的程序：水平和垂直。我认为您正在混合使用这两种方法。

水平并行化将 SIMD 单元中的每个通道视为一个单独的 "thread"，处理不同的数据。垂直并行化使整个 SIMD 单元处理同一个数据对象，试图从其内部多维性中获益。

举一个具体的例子：假设您有 2 个数组 X 和 Y 要添加的 3D 向量。

水平方法：SIMD 单元的每个通道都可以：

for(idx = 0; idx<size; idx+=SIMD_size) {
    ... = X[idx+laneid].x + Y[idx+laneid].x;
    ... = X[idx+laneid].y + Y[idx+laneid].y;
    ... = X[idx+laneid].z + Y[idx+laneid].z;
}

垂直方法：SIMD 单元的每个通道采用相同向量的不同分量：

for(idx = 0; idx<size; idx+=1) { 
    ... = X[idx].coord(laneid) + Y[idx].coord(laneid);
}

垂直方法更容易实施。事实上，编译器已经在尝试自动矢量化。问题是随着 SIMD 单元宽度的增加，实现无法从中受益。如果您从 4 宽 SIMD 切换到 16 宽 SIMD，您仍然只能将 3 个数字与 3D 向量并行相加。

水平方法更难。您通常必须处理发散分支、函数调用等......并且 - 您希望将数据重新组织为数组结构 - 以便不同数据对象的相应字段在内存中彼此相邻。

现在，回到您的问题：SoA 仅如果您进行水平并行化才有意义。当每个通道访问不同对象的相同字段时，SoA 允许用更好对齐的单个内存提取来替换昂贵的收集指令。如果你尝试做垂直，就像你在问题中的例子一样 - 没有人会首先考虑做 SoA - 访问同一对象的多个字段会导致 "gather".

但是，对于随机访问，即使您进行水平并行化，SoA 也可能不是最佳选择。首先，拥有 SoA 不会给您带来任何好处，因为您仍然需要进行昂贵的收集。但是，由于同一对象的字段分布在内存中，因此每次加载都会命中不同的缓存通道。它不仅增加了内存带宽的使用，还可能导致缓存抖动。这就是为什么 SoA 在随机访问方面效率不高的原因。

更好的解决方案是采用混合方法：将数据打包在具有大小的 SIMD 数组的结构数组中。但那是另外一回事了...

结构数组 (AoS) 与数组结构 (SoA) 随机读取向量化

Array of Structures (AoS) vs Structure of Arrays (SoA) on random reads for vectorization

c++

parallel-processing

vectorization

cpu-cache