2 
#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 个线程来执行此代码。有什么建议我必须做些什么来加快速度？

4

2 回答 2

1

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

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

CPU 缓存通常基于基于 MESI 的协议，使存储尝试发出读取所有权，这将使除请求者之外的其他内核中的行无效。发出 12 个并行（如果您有 6 个核心 * 2 个线程，则更确切地说是 6 个）将导致一场比赛，第一个赢得该行的人很可能在它甚至有机会修改它之前就被窥探者抢占了（虽然这不太可能）。结果非常混乱，并且可能需要一段时间才能让线路依次到达每个核心，被修改，然后被另一个核心窥探。这在接下来的每组 16 个元素中重复出现（再次假设为 int）。

你可能会做的是：

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

但是，这会阻止您充分发挥 CPU 的潜力，因为您会失去代码的空间局部性和流式传输属性。相反，您可以：

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

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

  • 平铺数组 - 将其分成一组，例如 48 行，将它们分布在线程之间，以便每个线程都运行在几行完整的行上（顺便说一句，转置技巧仍然适用），然后继续下一组
于 2013-10-06T19:05:22.083 回答
0

1）你有多少个核心？您无法获得比这更多的并行加速，并且正如其他人所说，可能要少得多。

2）看起来内部索引j应该从0开始，而不是1。

3) 内部循环急需指针和展开，如

double* pa = &A[i][0];
double* pa1 = &A[i-1][0];
for (j = 0; j < 1024; j += 8){
    *pa++ = 2 * *pa1++;
    *pa++ = 2 * *pa1++;
    *pa++ = 2 * *pa1++;
    *pa++ = 2 * *pa1++;
    *pa++ = 2 * *pa1++;
    *pa++ = 2 * *pa1++;
    *pa++ = 2 * *pa1++;
    *pa++ = 2 * *pa1++;
}

或者...

double* pa = &A[i][0];
double* paEnd = &A[i][1024];
double* pa1 = &A[i-1][0];
for (; pa < paEnd; pa += 8, pa1 += 8){
    pa[0] = 2 * pa1[0];
    pa[1] = 2 * pa1[1];
    pa[2] = 2 * pa1[2];
    pa[3] = 2 * pa1[3];
    pa[4] = 2 * pa1[4];
    pa[5] = 2 * pa1[5];
    pa[6] = 2 * pa1[6];
    pa[7] = 2 * pa1[7];
}

哪个更快。

于 2013-10-06T19:58:54.613 回答