使用OpenMP块来破坏缓存

Question

我一直在努力提高我的OpenMP解决方案的性能,这通常需要处理数组上的嵌套循环.虽然我已经设法从串行实现的59秒(在老化的双核Intel T6600上)将其降低到37,但我担心缓存同步会引起很多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]++;
}

Answer 1

您提供的两个代码片段都不相同,因为第一个代码片段将继续重复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]) == 415个元素的填充.结果布局将是:

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

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