如何提高 OpenMP 代码的性能？

Question

我目前正在尝试提高我的代码的并行性能，但我对 OpenMP 仍然是新手。我必须迭代一个大容器，在每次迭代中从多个条目读取并将结果写入单个条目。下面是我正在尝试做的一个非常简单的代码示例。

data是一个指向数组的指针，其中存储了许多数据点。在并行区域之前，我创建了一个 Array newData，因此可以用作data只读和newData只写，之后我扔掉旧的data并用于newData进一步的计算。据我了解data，并且newData在线程之间共享，并且并行区域内声明的所有内容都是私有的。data多线程读取会导致性能问题吗？

我用于#critical为 的元素分配新值newData以避免竞争条件。这是必要的吗，因为我访问了每个元素newData一次，而从不通过多个线程访问？

我也不确定日程安排。我是否必须指定是否需要static时间表dynamic？nowait由于所有线程都是相互独立的，我可以使用吗？

array *newData = new array;

omp_set_num_threads (threads);

#pragma omp parallel
{
    #pragma omp for
    for (int i = 0;  i < range; i++)
    {
        double middle = (*data)[i];
        double previous = (*data)[i-1];
        double next = (*data)[i+1];

        double new_value = (previous + middle + next) / 3.0;
        #pragma omp critical(assignment)
        (*newData)[i] = new_value;
    }
}

delete data;
data = newData;

我知道在第一次和最后一次迭代中previous，next无法从 读取data，在实际代码中，这是已处理的，但对于这个最小的示例，您可以从 读取多次data。

Answer 1

首先，摆脱所有不必要的依赖关系。#pragma omp critical(assignment)不是必需的，因为每个索引(*newData)仅在每个循环中写入一次，因此不存在竞争条件。

您的代码现在可能如下所示：

#pragma omp parallel for
for (int i = 0; i < range; i++)
   (*newData)[i] = ((*data)[i-1] + (*data)[i] + (*data)[i+1]) / 3.0;

现在我们正在寻找瓶颈。我提出的潜在候选人名单如下：

• 缓慢分裂
• 缓存抖动
• ILP（指令级并行）
• 内存带宽限制
• 隐藏的依赖项

那么让我们进一步分析它们。

除法速度慢： 有些CPU需要永远计算double/double。要了解您的 CPU 的运行时间和吞吐量，您必须查看其规格。也许替换/3.0为*0.3333..可能会有所帮助，但也许您的编译器已经这样做了。使用扩展指令集（如 SSE/AVX），您可以一次安排多个除法/乘法。

缓存颠簸： 因为您的 CPU 必须一次加载/存储一个缓存行，因此可能会发生冲突。想象一下，如果线程 1 尝试写入 (*newdata)[1]，线程 2 尝试写入 (*newdata)[2]，并且它们位于同一缓存行上。现在他们中的一个必须等​​待另一个。你可以用 来解决这个问题#pragma omp parallel for schedule(static, 64)。

ILP： 如果操作是独立的，CPU 可以将多个操作调度到管道中。为此，您必须展开循环。这可能看起来像这样：

assert(range % 4 == 0);
#pragma omp parallel for
for (int i = 0; i < range/4; i++) {
   (*newData)[i*4+0] = ((*data)[i*4-1] + (*data)[i*4+0] + (*data)[i*4+1]) / 3.0;
   (*newData)[i*4+1] = ((*data)[i*4+0] + (*data)[i*4+1] + (*data)[i*4+2]) / 3.0;
   (*newData)[i*4+2] = ((*data)[i*4+1] + (*data)[i*4+2] + (*data)[i*4+3]) / 3.0;
   (*newData)[i*4+3] = ((*data)[i*4+2] + (*data)[i*4+3] + (*data)[i*4+4]) / 3.0;
}

内存带宽限制： 对于非常简单的循环，请考虑这一点。您需要加载多少内存以及您的 CPU 将忙于处理它多长时间。您正在加载大约 1 个缓存行并计算一些取消引用、一些指针加法、两次加法和一次除法。您达到的限制取决于您的 CPU 规格。现在考虑缓存局部性。您可以修改代码以更好地利用缓存吗？如果一个线程在一次循环迭代中获得 i=3，而在下一次循环迭代中获得 i=7，则必须重新加载 3 (*data)。但如果从 i=3 到 i=4，您可能不需要加载任何内容，因为 (*data)[i+1] 位于先前加载的缓存行中。您可以节省一些 RAM 带宽。要利用它，请展开循环。使用 float 而不是 double 也可以增加这种机会。

隐藏的依赖项： 现在我个人觉得这部分非常棘手。有时您的编译器不确定它是否可以重用某些数据，因为它不知道它没有更改。使用const有助于编译器。但有时您需要restrict给编译器提供正确的提示。但我不太明白这一点，无法解释它。

所以这就是我要尝试的：

const double ONETHIRD = 1.0 / 3.0;
assert(range % 4 == 0);
#pragma omp parallel for schedule(static, 1024)
for (int i = 0; i < range/4; i++) {
   (*newData)[i*4+0] = ((*data)[i*4-1] + (*data)[i*4+0] + (*data)[i*4+1]) * ONETHIRD;
   (*newData)[i*4+1] = ((*data)[i*4+0] + (*data)[i*4+1] + (*data)[i*4+2]) * ONETHIRD;
   (*newData)[i*4+2] = ((*data)[i*4+1] + (*data)[i*4+2] + (*data)[i*4+3]) * ONETHIRD;
   (*newData)[i*4+3] = ((*data)[i*4+2] + (*data)[i*4+3] + (*data)[i*4+4]) * ONETHIRD;
}

然后进行基准测试。进行更多基准测试，再进行更多基准测试。只有基准测试才能告诉您哪些技巧有帮助。

PS：还有一件事需要考虑。如果您发现您的程序严重占用内存带宽。你可以考虑改变算法。也许将两个步骤合二为一。就像从 b[i] := (a[i-1] + a[i] + a[i+1]) / 3.0 到 一样d[i] := (n[i-1] + n[i] + n[i+1]) / 3.0 = (a[i-2] + 2.0 * a[i-1] + 3.0 * a[i] + 2.0 * a[i+1] + a[i+1]) / 3.0。我想这其中的原因你自己就会找到的。

享受优化的乐趣;-)