c++ - 与 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);
    }
}

输出是:

0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

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

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

是否有更复杂的方法来执行/并行化它？

Answer 1

我还没有想透，不过你也可以试试这样的方法:

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);
}