c - 使用 OpenMP block 来破坏缓存

Question

我一直在尝试提高 OpenMP 解决方案的性能，该解决方案通常需要处理数组上的嵌套循环。虽然我已经设法将串行实现的时间从 59 秒降低到 37 秒(在老化的双核 Intel T6600 上)，但我担心缓存同步会引起 CPU 的大量关注(当 CPU 应该解决我的问题时! )。我一直在努力设置分析器，所以我还没有验证这一说法，但无论如何我的问题仍然存在。根据this lecture关于负载均衡:

Instead of doing work, the CPUs are busy fighting over the only used cache line in the program. You can fix this with a very strange technique: move the CPUs data apart in memory further than one cache line. For example, here we move the integers accessed by each thread 20 units apart.

然后继续提供相关源代码(应该在四核上运行，因此是 %4)

#pragma omp parallel for schedule(static,1)
    for (unsigned int i=0;i<n;i++) {
    arr[(i%4)*20]++;
}

也就是说，我对“ block ”是什么有一种直觉，但上面的实现似乎完全忽略了它，让我相信我的直觉是错误的。

我的问题是这样的:设置相当大的 block 值是否会将数据进一步移到缓存行中？ IE。上面的代码不等于

#pragma omp parallel for schedule(static, 20)
    for (unsigned int i=0;i<n;i++) {
    arr[i]++;
}

Answer 1

您给出的两个代码片段并不等效，因为第一个代码片段会不断重复大于 4 的 n 的相同元素。处理此类数组的正确方法是确保 sizeof(arr[0]) * n/#cores 是缓存行大小的倍数。现代 x86 CPU 的缓存行大小为 64 字节。如果 arr 是整数或单精度 float 组，则 sizeof(arr[0]) == 4 并且单个缓存行可容纳 16 个元素。对于双倍大小的数据类型，单个缓存行可容纳 8 个元素。最佳循环调度 block 大小在前一种情况下是 16 的倍数，在后一种情况下是 8 的倍数。

在处理静态调度的循环时，人们会尝试最大化 block 大小，以减少每个线程运行的循环数量。例如，如果有 4 个线程，n 为 64， block 大小设置为 8，则将使用以下调度:

thread    iterations (from-to)
------    --------------------
  0          0- 7, 32-39
  1          8-15, 40-47
  2         16-23, 48-53
  3         24-31, 54-63

这远非最佳，因为每个线程都必须运行循环两次。更好的解决方案是将 block 大小设置为 16(8 的倍数):

thread    iterations (from-to)
------    --------------------
  0             0-15
  1            16-31
  2            32-47
  3            48-63

请注意，静态调度循环的默认 block 大小为#iterations/#threads。

有时，必须并行处理无法分布在非重叠缓存行之间的数据。例如，arr[] 可能只是一个由 4 个元素组成的数组，全部适合单个缓存行。在这种情况下，应该在数组元素之间插入填充，以确保不同线程正在处理的数据位于不同的缓存行中。例如:

int arr[4];

#pragma omp parallel for
for (int i = 0; i < 4; i++)
   arr[i]++;

int arr[4] 结果如下内存布局:

|<-------- a single cache line ---------->|
| arr[0] | arr[1] | arr[2] | arr[3] | ... |

如果核心 0 更新 arr[0] 并且核心 1 更新 arr[1]，则缓存行将不断在两个核心之间反弹 - 错误共享和错误表现。因此，必须在 arr[0] 和 arr[1] 之间插入大小为 CLS - sizeof(arr[0]) 字节的填充，或者CLS/sizeof(arr[0]) - 1 数组元素，其中 CLS 是缓存行的大小(以字节为单位)。使用 CLS == 64 和 sizeof(arr[0]) == 4 这会产生 15 个填充元素。最终的布局将是:

|<----- one cache line ------>|<--- another cache line ---->|<-- yet another ...
| arr[0] | 15 unused elements | arr[1] | 15 unused elements | arr[2] | ...

截取的代码应修改为:

// cache line size in number of int elements
#define CLS    (64/sizeof(int))

int arr[4*CLS];

#pragma omp parallel for
for (int i = 0; i < 4; i++)
   arr[i*CLS]++;

另一个可以简化代码的选项是将每个数据元素包装在一个结构中，并将填充放入结构中:

// cache line size in number of bytes
#define CLS    (64)

typedef struct _item
{
   int data;
   int padding[CLS/sizeof(int)-1];
} item;

item arr[4];

#pragma omp parallel for
for (int i = 0; i < 4; i++)
   arr[i].data++;

无论您使用哪种方法，请记住，由于各种体系结构具有不同的缓存行大小，此类代码将变得不可移植。