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

Question

I have the simple problem of comparing all elements to each other. The comparison itself is symmetric, therefore, it doesn't have to be done twice.

The following code example shows what I am looking for by showing the indices of the accessed elements:

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

The output is:

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

So each element is compared to each other once. When I want to parallelize this code I have the problem that first I have to stick to dynamic scheduling because the calculation time of each iteration does vary to a huge extend AND I can not use collapse due to the fact that the nested iterations are index-dependant from the outer loop.

Using #pragma omp parallel for schedule(dynamic, 3) for the outer loop may lead to single core executions at the end whereas using this for the inner loop may lead to such executions within each iteration of the outer loop.

Is there a more sophisticated way of doing/parallelizing that?

Answer 1

I haven't thought it thoroughly, but you can try some approach like this too:

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