11

我已经开始学习如何在大学课程中使用 OpenMP。作为实验室练习，我们得到了一个需要并行化的串行程序。

我们首先意识到False Sharing的危险，尤其是当涉及到并行更新数组时 for 循环。

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

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 本质上与将它们设置为 shared 具有相同的效果，因为它们都是指向同一内存位置的指针

  • 理论上使用静态调度应该会有所帮助，但我仍然遇到同样的减速。另外，我觉得静态调度不是解决这个问题的最便携的方法。

4

2 回答 2

13

由于我们首先谈论优化：

将常量定义为宏，允许编译器更好地优化。

#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任何共享状态只会将指针传递到您的并行部分，因为您将它们声明为指针。所以它们中的内存仍然是共享的。

最后，为了避免共享闪存，您要确保在线程之间共享尽可能少的缓存行。只读缓存线（因此uk在您的情况下）是无关紧要的，它们可以存在于每个线程中，但写入缓存ukp1线应该是每个线程。今天的缓存线通常是 64 字节长 - 因此一个缓存线将适合 8double秒。所以你想为每个线程分配至少 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- 在大多数系统上它甚至会适合整个页面（假设您是页面对齐的）。

编辑：

为了让它真正产生效果，你需要让你的记忆正确对齐。您从 index 开始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。

于 2013-10-09T17:56:44.247 回答
4

我相信@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
于 2013-10-09T17:54:58.263 回答