0

I'm trying to parallelize a code. My code looks like this -

    #pragma omp parallel private(i,j,k)
    #pragma omp parallel for shared(A)
    for(k=0;k<100;<k++)
     for(i=1;i<1024;<i++)
      for(j=0;j<1024;<j++)
       A[i][j+1]=<< some expression involving elements of A[i-1][j-1] >>

On executing this code I'm getting a different result from serial execution of the loops. I'm unable to understand what I'm doing wrong.

I've also tried the collapse()

    #pragma omp parallel private(i,j,k)
    #pragma omp parallel for collapse(3) shared(A)
    for(k=0;k<100;<k++)
     for(i=1;i<1024;<i++)
      for(j=0;j<1024;<j++)
       A[i][j+1]=<< some expression involving elements of A[][] >>

Another thing I tried was having a #pragma omp parallel for before each loop instead of collapse().

The issue, as I think, is the data dependency. Any idea how to parallelize in case of data dependency?

4

2 回答 2

0

您只是在并行化外部“k”for 循环。每个并行线程都在执行“i”和“j”循环，它们都写入相同的“A”结果。由于它们都在 A 中读取和写入相同的插槽，因此最终结果将是不确定的。

从您的问题中不清楚任何并行性都是可能的，因为每一步似乎都依赖于前面的每一步。

于 2013-10-05T19:19:46.083 回答
0

如果这确实是您的用例，只需对外部循环进行并行化k，这应该足以满足您在常见架构上的适度并行性。

如果你想要更多，你必须重新编写你的循环，这样你就有一个没有依赖关系的内部部分。在您的示例情况下，这相对容易，您必须通过“对角线”（外循环，顺序）进行处理，然后在对角线内部进行处理，您将是独立的。

for (size_t d=0; d<nDiag(100); ++d) {
   size_t nPoints = somefunction(d);
#pragma omp parallel
   for (size_t p=0; p<nPoints; ++p) {
      size_t x = coX(p, d);
      size_t y = coY(p, d);
      ... your real code ...
   }

}

其中一部分可以自动完成，但我不认为这些工具已经在日常 OMP 中很容易实现。这是一个活跃的研究方向。

还要注意以下几点

  • int索引很少是一个好主意，特别是如果您访问矩阵。如果你必须自己计算一个条目的绝对位置（并且你看到你可能在这里），这很容易溢出。int通常是 32 位宽，在这 32 个中，您甚至浪费了一个作为标志。在 C 中，对象大小是用 计算的size_t，大多数情况下是 64 位宽，并且在任何情况下都是平台设计人员选择的正确类型。
  • 将局部变量用于循环索引和其他临时变量，正如您所见，编写 OMP pragma 变得容易得多。局部性是并行性的关键之一。通过正确表达这一点来帮助自己和编译器。
于 2013-10-05T06:48:47.590 回答