使用数组避免OpenMP中的错误共享问题

Question

使用数组避免OpenMP中的错误共享问题

12

我已经开始学习如何使用OpenMP作为大学课程的一部分。作为实验练习，我们被要求并行化一个串行程序。

我们首先意识到了False Sharing的危险性，尤其是在并行循环中更新数组时。

然而，我发现很难将以下代码片段转换为可并行化的任务，而不会引起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期间发生了False sharing。

我曾经认为也许我可以使用reduction子句，但很快我就发现它不能用于数组。

有什么我可以使用来并行化这段代码以改善运行时间吗？有没有我没听说过的子句可以使用？或者这是需要重新构造代码以允许适当的并行化的任务？

所有形式的输入都将非常感激！

编辑：有人指出我的代码中有一个错误。我本地的代码是正确的，我只是错误地编辑了它（这改变了代码的结构），对此混淆感到抱歉！

编辑2：

@Sergey指出给我一些信息，我觉得很有用：

将 uk 或 ukp1 设置为私有，基本上与将它们设置为共享相同，因为它们都指向同一个内存位置。
理论上使用静态调度应该有所帮助，但我仍然遇到了同样的减速问题。此外，我觉得静态调度不是解决这个问题最可移植的方法。

- Michael Aquilina

你的外层循环索引 kk 在循环内部没有被使用，这是有意为之吗？ - Sergey L.

是的，我相信kk的目的只是作为外部循环的索引。外部循环仅用于多次重复操作（在我的情况下为1000次，但可以更改）。由于外部循环依赖于先前的值，我认为我们无法并行化它。 - Michael Aquilina

2

你只是在循环内修改 ukp1，但从未从中读取，因此每个 kk 的迭代都会完全相同。 - Sergey L.

这是否意味着这不可能是虚假共享的情况？写入操作不会导致缓存行被更新吗？ - Michael Aquilina

ukp1仅用作临时存储。它获取上一次迭代中的值（存储在uk中），并使用其邻居（ii + 1和ii - 1）计算差分。完成所有计算并填充ukp1后，将其与uk交换以再次在下一次迭代中使用。因此，虽然它在循环内部未被使用，但它确实有一个目的。这段代码不是我自己编写的，而是由我们的导师编写的。我们的任务只是将其并行化。 - Michael Aquilina

显示剩余4条评论

2个回答

4

我认为@SergeyL.是正确的，你的代码应该更像这样：

我相信@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

- Massimiliano

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey L. · Accepted Answer

既然我们谈论优化问题，那么首先要做的就是定义常量为宏，这可以让编译器更好地进行优化。

#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字节长 - 因此一个缓存行可以容纳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。