3

我一直在尝试提高我的 OpenMP 解决方案的性能，该解决方案通常必须处理数组上的嵌套循环。尽管我已经设法将其从串行实现的 59 秒降低到 37（在老化的双核 Intel T6600 上），但我担心缓存同步会引起 CPU 的大量关注（当 CPU 应该解决我的问题时！ ）。我一直在努力设置探查器，所以我还没有验证这一说法，但我的问题无论如何都是成立的。根据这个关于负载平衡的讲座：

CPU 没有工作，而是忙于争夺程序中唯一使用的高速缓存行。您可以使用一种非常奇怪的技术来解决此问题：将 CPU 数据移到内存中比一个缓存行更远的地方。例如，这里我们将每个线程访问的整数相隔 20 个单位。

然后继续提供相关的源代码（因此应该在四核上运行%4）

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

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

我的问题是： 设置一个相当大的块值是否会将数据移动到缓存行的下方？IE。上面的代码不等于

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

1 回答 1

8

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

在处理静态调度的循环时，我们会尝试最大化块大小，以减少每个线程运行的循环数量。例如，如果有 4 个线程，n为 64 并且块大小设置为 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

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

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

请注意，静态调度循环的默认块大小是#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++;

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

于 2013-08-21T08:23:31.447 回答