使用数组避免OpenMP中的虚假共享

Question

我已经开始学习如何使用OpenMP作为大学课程的一部分.作为实验练习,我们获得了一个需要并行化的系列程序.

我们首先了解了False Sharing的危险性,尤其是在为循环并行更新数组时.

但是,我发现很难将以下代码片段转换为可并行执行的任务,而不会导致错误共享:

int ii,kk;

double *uk = malloc(sizeof(double) * NX);
double *ukp1 = malloc(sizeof(double) * NX);
double *temp;

double dx = 1.0/(double)NX;
double dt = 0.5*dx*dx;

// Initialise both arrays with values
init(uk, ukp1);

for(kk=0; kk<NSTEPS; kk++) {
   for(ii=1; ii<NX-1; ii++) {
      ukp1[ii] = uk[ii] + (dt/(dx*dx))*(uk[ii+1]-2*uk[ii]+uk[ii-1]);
   }

   temp = ukp1;
   ukp1 = uk;
   uk = temp;
   printValues(uk,kk);
}

我的第一反应是尝试分享ukp1:

for(kk=0; kk<NSTEPS; kk++) {
   #pragma omp parallel for shared(ukp1)
   for(ii=1; ii<NX-1; ii++) {
      ukp1[ii] = uk[ii] + (dt/(dx*dx))*(uk[ii+1]-2*uk[ii]+uk[ii-1]);
    }

   temp = ukp1;
   ukp1 = uk;
   uk = temp;
   printValues(uk,kk);
}

但与串行版相比,这显然显示出明显的减速.显而易见的原因是在对ukp1的一些写操作期间发生了虚假共享.

我的印象是,我可能会使用还原子句,但我很快就发现这不能用于数组.

有什么我可以用来并行化这段代码来改善运行时间吗？是否有我可以使用的条款,我没有听说过？或者这是我需要重构代码以实现正确的并行化的任务？

所有形式的输入将不胜感激!

编辑:有人指出我的代码中有一个错误.我在本地的代码是正确的,我只是错误地编辑它(这改变了代码的结构),抱歉混乱!

编辑2:

@Sergey向我指出的一些信息我觉得很有用:

• 将uk或ukp1设置为private将基本上具有与将它们设置为共享相同的效果,因为它们都是指向同一内存位置的指针

• 使用静态调度应该在理论上有所帮助,但我仍然遇到同样的减速.此外,我觉得静态调度不是解决此问题的最便携方式.

Answer 1

因为我们首先讨论优化问题:

将常量定义为宏,允许编译器进行更好的优化.

#define dx (1.0/(double)NX)
#define dt (0.5*dx*dx)

在使用OpenMP时,变量的默认共享规则是shared,尽管最好将其设置为none并手动启用并行部分中所需的每个变量.这样您就可以确定避免冲突.

#pragma omp parallel for default(none) shared(ukp1, uk)

设置ukp1或uk任何共享状态也只会将指针传递到并行部分,因为您将它们声明为指针.所以它们中的内存仍然是共享的.

最后,为了避免flase共享,您需要确保尽可能少地在线程之间共享缓存行.只读高速缓存行(因此uk在您的情况下)是无关紧要的,它们可以存在于每个线程中,但写入高速缓存行ukp1应该是每个线程.今天缓存行通常是64字节长 - 因此一个缓存行将适合8 double秒.所以你想为每个线程分配至少8次迭代的块:

#pragma omp parallel for default(none) shared(ukp1, uk) schedule(static,8)

将每个块部署代码8次迭代,并应出现在内部循环中.

for(kk=0; kk<NSTEPS; kk++) {
   #pragma omp parallel for default(none) shared(ukp1, uk) schedule(static,8)
   for(ii=1; ii<NX-1; ii++) {
      ukp1[ii] = uk[ii] + (dt/(dx*dx))*(uk[ii+1]-2*uk[ii]+uk[ii-1]);
   }
   // Swap pointers for the next time step
   temp = ukp1;
   ukp1 = uk;
   uk   = temp;
}

实际上,根据您的数据大小,您可能希望分配更大的块大小.我倾向于使用0x1000- 在大多数系统上甚至可以适合整个页面(假设你是页面对齐的).

编辑:

为了实现这一点,您需要正确对齐内存.你是从索引开始的1,所以:

 double *uk = memalign(0x40 , sizeof(double) * (NX + 8));
 double *ukp1 = memalign(0x40 , sizeof(double) * (NX + 8));
 uk += 7;
 ukp1 += 7;

现在ukp1[1]是缓存行对齐.增加块大小可能会有所帮助,但除非您计划在NX > 100000第一时间进行并行化并没有多大意义.

您需要记住,在每次迭代中重新启动并行部分会产生大量开销.为了控制这一点,您需要在简单的OpenMP之外重新调整您的日程安排.

Answer 2

我相信@SergeyL。是对的，你的代码应该看起来更像这样：

// Parabolic 1D heat diffusion solved with an explicit method
for(kk=0; kk<NSTEPS; kk++) {
   for(ii=1; ii<NX-1; ii++) {
      ukp1[ii] = uk[ii] + (dt/(dx*dx))*(uk[ii+1]-2*uk[ii]+uk[ii-1]);
   }
   // Swap pointers for the next time step
   temp = ukp1;
   ukp1 = uk;
   uk   = temp;
}

也就是说，为了避免错误共享，您必须确保不同的线程不在同一缓存行上运行。这确实需要您选择合适的调度和块大小。我想到的最简单的解决方案是：

// Parabolic 1D heat diffusion solved with an explicit method
#pragma omp parallel private(kk)
{
for(kk=0; kk<NSTEPS; kk++) {
#pragma omp for schedule(static)
   for(ii=1; ii<NX-1; ii++) {
      ukp1[ii] = uk[ii] + (dt/(dx*dx))*(uk[ii+1]-2*uk[ii]+uk[ii-1]);
   }
#pragma omp single
   {
       // Swap pointers for the next time step
       temp = ukp1;
       ukp1 = uk;
       uk   = temp;
   }
} // outer for loop
} // pragma omp parallel