c - 为什么此代码的并行执行比顺序执行慢？

Question

#pragma omp parallel
{
 for (i=1; i<1024; i++)
  #pragma omp for
  for (j=1; j<1024; j++)
   A[i][j] = 2*A[i-1][j];
}

我使用 12 个线程来执行这段代码。我有什么建议可以加快速度吗？

Answer 1

假设 A 的类型小于 64 字节，尝试以这种方式并行化内部循环很可能会导致您在缓存行中进行错误共享。

假设 A 是 4 字节整数的对齐数组，您将在同一缓存行中拥有 A[i][0] 到 A[i][15]。这意味着所有 12 个线程将尝试同时读取该行，每个线程都是它需要的部分，如果您将其留在那儿，这可能会导致多个内核共享该行，但您也尝试写回来，引导每个核心尝试获取生产线的所有权以对其进行修改。

CPU 缓存通常基于基于 MESI 的协议(protocol)，使存储尝试发出所有权读取，这将使除请求者之外的每个其他核心中的行无效。发出 12 个并行(或者更确切地说是 6 个，如果你有 6 个核心 * 2 个线程)将导致第一个赢得线路的人很可能在它甚至有机会修改它(尽管这不太可能)。结果相当困惑，并且可能需要一段时间才能将线路依次传送到每个核心、进行修改，然后被另一个核心监听。对于接下来的连续 16 个元素组(同样，假设为 int)中的每一个重复出现这种情况。

你可能会做的是:

• 确保每个单独的线程都在自己的缓存行上工作，但添加一个内部循环来运行每行所需数量的元素，并并行化跳过此数量元素的循环。

然而，这会阻止您发挥 CPU 的全部潜力，因为您失去了代码的空间局部性和流属性。相反，您可以:

• 并行化外部循环，使每个线程处理几行，从而允许它拥有整个连续的内存流。但是，由于您需要在行之间进行排序，因此您可能需要在此处进行一些调整(例如转置)。

这里还有一个缺点，因为如果一个线程遇到太多的流，它可能会失去对它们的跟踪。因此，第三种方法是 -

• 平铺数组 - 将其分成一组，比如 48 行，将它们分布在线程之间，以便每个线程运行几行(转置技巧在这里仍然适用，顺便说一句)，然后继续下一组