与 C++/OpenMP 的所有相对所有比较的对称性并行化嵌套 for 循环

Question

我有一个比较所有元素的简单问题。比较本身是对称的，因此不必进行两次。

以下代码示例通过显示所访问元素的索引显示了我正在寻找的内容：

int n = 5;
for (int i = 0; i < n; i++)
{
    for (int j = i + 1; j < n; j++)
    {
        printf("%d %d\n", i,j);
    }
}

输出为：

因此每个元素相互比较一次。当我想并行化这段代码时，我遇到了一个问题，首先我必须坚持动态调度，因为每次迭代的计算时间确实变化很大而且我不能使用崩溃，因为嵌套迭代是索引 -依赖于外循环。

对外部循环使用#pragma omp parallel for schedule(dynamic, 3)可能会导致最后执行单核，而对内部循环使用#pragma omp parallel for schedule(dynamic, 3)可能会导致在外部循环的每次迭代中执行此类操作。

有没有更复杂的方法doing/parallelizing？

Answer 1

的确，OpenMP 标准对于崩溃的说法是：

The iteration count for each associated loop is computed before entry to the outermost loop. If execution of any associated loop changes any of the values used to compute any of the iteration counts, then the behavior is unspecified.

所以你不能折叠你的循环，这是最简单的方法。但是，由于您对索引对的计算顺序不是特别感兴趣，因此可以按如下方式稍微更改循环：

for ( int i = 0; i < n; i++ ) { 
    for ( int j = 0; j < n / 2; j++ ) {
        int ii, jj;
        if ( j < i ) {
            ii = n - 1 - i;
            jj = n - 1 - j;
        }
        else {
            ii = i;
            jj = j + 1;
        }
        printf( "%d %d\n", ii, jj );
    }
}

这应该会以某种混乱的顺序为您提供您想要的所有对，但具有固定的迭代限制，可以实现平衡的并行化，甚至可以根据需要进行循环崩溃。简单地说，如果 n 是偶数，对应于 n/2 的列将显示两次，因此您要么接受它，要么稍微修改算法以避免...

Answer 2

我还没想好，不过你也可以试试这样的方法：

int total = n * (n-1) / 2; // total number of combinations
#pragma omp parallel for
for (int k = 0; k < total; ++k) {
  int i = first(k, n);
  int j = second(k, n, i);
  printf("%d %d\n", i,j);
}

int first(int k, int n) {
  int i = 0;
  for (; k >= n - 1; ++i) {
    k -= n - 1;
    n -= 1;
  }
  return i;
}

int second(int k, int n, int i) {
  int t = i * (2*n - i - 1) / 2;
  return (t == 0 ? k + i + 1 : (k % t) + i + 1);
}

Answer 3

我之前在以下方面取得了不错的成绩：

#pragma omp parallel for collapse(2)
for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
                if (j <= i)
                        continue;
                printf("%d %d\n", i, j);
        }
}

请记住，printf 不会只执行任何并行工作负载，因此最好根据您的具体工作对其进行概要分析。您可以尝试添加 schedule(dynamic, 10) 或大于 10 的内容，具体取决于您执行的迭代次数。

与 C++/OpenMP 的所有相对所有比较的对称性并行化嵌套 for 循环

Parallelize nested for loop with respect to symmetry of all -against-all comparison with C++/OpenMP

c++

parallel-processing

loops

nested

openmp