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

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