c++ - 多线程代码中缓存友好的数组迭代模式

Question

我有一段代码迭代结构数组，对其中的每个元素进行更改:

const size_t nThreads = 4;

struct foo {
  int a = 0;
  float b = 10;
};

void process(foo * array, size_t i, size_t end) {
  for (; i < end; i++) array[i].a += array[i].b;
}

int main() {
  foo fooArray[512];
  process(fooArray, 0, 512);
  return 0;
}

现在，我计划利用没有其他代码访问 fooArray 并且每个元素彼此独立的优势，以拆分 process() 在不同部分工作fooArray，每个部分都在自己的线程中。

我知道通常每个核心都有自己独立的(只有 L1？)缓存，当它们有重叠的缓存区域时，写入一个核心缓存必须与指向它的其他缓存同步，导致数据停顿。我还知道，通常通过 FSB 访问 RAM 是同步的，如果不同内核频繁发生高速缓存未命中，这也会导致停顿。

那么问题是: 考虑到所有这些，考虑到我想最大限度地减少缓存未命中和数据停顿，访问 fooArray 的最佳模式是什么:按条纹还是按切片？

按切片:

void process(foo * array, size_t i, size_t end) {
  for (; i < end; i++) array[i].a += array[i].b;
}

for (int i = 0; i < nThreads; i++) {
  std::thread t = std::thread([fooArray, i]() {
    process(fooArray, i * 512/nThreads, (i+1) * 512/nThreads -1);
  }
  t.join();
}

在这种情况下，每个线程将遍历数组的一部分(线程 t1 将遍历 0 到 127，t2 从 128 到 255，t3 从 256 到 383，t4 从 384 到 511)。我相信这会通过内核之间的缓存同步来最大程度地减少数据停顿，因为每个切片可能由不同的内核缓存处理，但如果所有内核都尝试同时获取缓存行，则可能会由于 FSB 同步访问而增加停顿。

按条纹:(注意 i+=nThreads)

 void process(foo * array, size_t i, size_t end) {
  for (; i < end; i+=nThreads) array[i].a += array[i].b;
}

for (int i = 0; i < nThreads; i++) {
  std::thread t = std::thread([fooArray, i]() {
    process(fooArray, i, 512);
  }
  t.join();
}

在这种情况下，t1 将遍历元素 0、4、8、12、...、508，t1 遍历 1、5、9、13、...、509，t3 遍历 2、6、10， 14, ..., 510 和 t4 超过 3, 7, 11, 15, ..., 511。我相信这会最大限度地减少 FSB 访问，因为每次缓存未命中只会触发一次对 RAM 的访问，但由于缓存同步会导致数据停顿增加。

Answer 1

您可以引用以下 SO 链接，其中包含有关此概念的重要信息以及专家就此主题提供的各种信息的链接:https://stackoverflow.com/a/23172120/2724703

在处理与性能相关的问题时，我们应该始终自己测量执行时间并了解可能影响的各种参数。对于所有三种情况，第一件事应该是测量时间。

话虽如此，我认为您的“按切片”方法会比其他方法更好，原因如下:

所以要在我们的程序中实现对缓存友好的逻辑，我们应该尽量做到线性内存访问。这真的会受到缓存机制的喜爱，因为内存拥有 L1 缓存的可能性会大大提高。在这种情况下，线程对数组段的线性访问会比另一个好得多。现在，如果我们的数据集很大并且不适合放入 L1 缓存，这个概念就适用了。在这两种情况下，整个数据都可以很容易地放入 L1 缓存中。

因此，如果我们的工作/逻辑很大，那么这种技术会更合适，在这种情况下，这种复杂性可能不会带来任何好处(有时执行时间可能会增加)。了解这些概念是可以的，但实际上，只有当我们通过测量发现这会导致瓶颈时，我们才应该尝试优化我们的代码。

我认为由于内核之间的缓存同步而导致的数据停顿应该不会有任何问题。这种开销应该同样适用于这两种情况。