openMP COLLAPSE如何在内部工作？

Question

我正在尝试openMP并行性，使用2个线程乘以2个矩阵。我理解外循环并行是如何工作的（即没有“collapse（2）”工作）。

现在，使用崩溃。

#pragma omp parallel for collapse(2) num_threads(2)
    for( i = 0; i < m; i++)
        for( j = 0; j < n; j++)
        {
            s = 0;
            for( k = 0; k < p; k++)
                s += A[i][k] * B[k][j];
            C[i][j] = s;
        }

从我收集的东西，崩溃“折叠”循环到一个大循环，然后在大循环中使用线程。所以，对于前面的代码，我认为它将等同于这样的东西：

#pragma omp parallel for num_threads(2)
for (ij = 0; ij <n*m; ij++)
{ 
    i= ij/n; 
    j= mod(ij,n);
    s = 0;
    for( k = 0; k < p; k++)
        s += A[i][k] * B[k][j];
    C[i][j] = s;
}

我的问题是：

1. 它是如何工作的？我没有找到关于它如何“折叠”循环的任何解释。
2. 如果是，使用它有什么好处？它是不是将两个线程之间的作业完全分开，就像没有崩溃的并行性一样？如果没有，那么它是如何工作的？

PS：现在我想的更多一点，如果n是奇数，比如3，没有崩溃，一个线程将有2次迭代，而另一个只有一次。这导致线程的作业不均匀，效率稍低。如果我们使用我的崩溃等价物（如果崩溃确实有效），每个线程将进行“1.5”迭代。如果n非常大，那真的不重要，不是吗？更何况，每次都做那个i= ij/n; j= mod(ij,n);，它会降低性能，不是吗？

Answer 1

OpenMP规范只是说（Version 4.5的第58页）：

如果使用大于1的参数值指定collapse子句，则子句应用的关联循环的迭代将折叠为一个更大的迭代空间，然后根据schedule子句进行划分。在这些关联循环中顺序执行迭代确定了折叠迭代空间中迭代的顺序。

所以，基本上你的逻辑是正确的，除了你的代码相当于schedule(static,1) collapse(2)的情况，即迭代块大小为1.在一般情况下，大多数OpenMP运行时都有默认的schedule(static)调度，这意味着块大小将是（大约）等于迭代次数除以线程数。然后，编译器可以使用一些优化来实现它，例如，为外循环运行部分内循环以获得固定值，然后使用完整内循环运行整数个外迭代，然后再运行部分内循环。

例如，以下代码：

#pragma omp parallel for collapse(2)
for (int i = 0; i < 100; i++)
    for (int j = 0; j < 100; j++)
        a[100*i+j] = i+j;

由GCC的OpenMP引擎转换为：

<bb 3>:
i = 0;
j = 0;
D.1626 = __builtin_GOMP_loop_static_start (0, 10000, 1, 0, &.istart0.3, &.iend0.4);
if (D.1626 != 0)
  goto <bb 8>;
else
  goto <bb 5>;

<bb 8>:
.iter.1 = .istart0.3;
.iend0.5 = .iend0.4;
.tem.6 = .iter.1;
D.1630 = .tem.6 % 100;
j = (int) D.1630;
.tem.6 = .tem.6 / 100;
D.1631 = .tem.6 % 100;
i = (int) D.1631;

<bb 4>:
D.1632 = i * 100;
D.1633 = D.1632 + j;
D.1634 = (long unsigned int) D.1633;
D.1635 = D.1634 * 4;
D.1636 = .omp_data_i->a;
D.1637 = D.1636 + D.1635;
D.1638 = i + j;
*D.1637 = D.1638;
.iter.1 = .iter.1 + 1;
if (.iter.1 < .iend0.5)
  goto <bb 10>;
else
  goto <bb 9>;

<bb 9>:
D.1639 = __builtin_GOMP_loop_static_next (&.istart0.3, &.iend0.4);
if (D.1639 != 0)
  goto <bb 8>;
else
  goto <bb 5>;

<bb 10>:
j = j + 1;
if (j <= 99)
  goto <bb 4>;
else
  goto <bb 11>;

<bb 11>:
j = 0;
i = i + 1;
goto <bb 4>;

<bb 5>:
__builtin_GOMP_loop_end_nowait ();

<bb 6>:

这是程序的抽象语法树的类似C的表示，可能有点难以阅读，但它的作用是，它仅使用模运算一次来计算基于迭代开始的i和j的初始值阻止（.istart0.3）由GOMP_loop_static_start()的召唤决定。然后它只是增加i和j，因为人们期望实现一个循环嵌套，即增加j直到它达到100，然后将j重置为0并增加i。同时，它还保留.iter.1中折叠迭代空间的当前迭代次数，基本上同时迭代单个折叠循环和两个嵌套循环。

至于线程数没有划分迭代次数的情况，OpenMP标准说：

当没有指定chunk_size时，迭代空间被分成大小大致相等的块，并且最多一个块被分配给每个线程。在这种情况下，未指定块的大小。

GCC实现使具有最高ID的线程执行少一次迭代。其他可能的分发策略在第61页的说明中列出。该清单并非详尽无遗。

Answer 2

标准本身未指定确切的行为。但是，该标准要求内循环对外循环的每次迭代具有完全相同的迭代。这允许以下转换：

#pragma omp parallel
{
    int iter_total = m * n;
    int iter_per_thread = 1 + (iter_total - 1) / omp_num_threads(); // ceil
    int iter_start = iter_per_thread * omp_get_thread_num();
    int iter_end = min(iter_iter_start + iter_per_thread, iter_total);

    int ij = iter_start;
    for (int i = iter_start / n;; i++) {
        for (int j = iter_start % n; j < n; j++) {
            // normal loop body
            ij++;
            if (ij == iter_end) {
                goto end;
            }
        }
    }
    end:
}

通过略读拆卸，我相信这与GCC的做法类似。它确实避免了每次迭代除法/模数，但每个内部迭代器需要一个寄存器和加法。当然，它会因不同的调度策略而有所不同。

折叠循环确实增加了可以分配给线程的循环迭代次数，从而有助于实现负载平衡，甚至可以首先暴露足够的并行工作。