c - 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. 如果是，使用它有什么好处？没有 它在 2 个线程之间划分作业，就像没有并行性一样 崩溃？如果不是，那么它是如何工作的？

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

Answer 1

OpenMP 规范只是说(Version 4.5 的第 58 页):

If a collapse clause is specified with a parameter value greater than 1, then the iterations of the associated loops to which the clause applies are collapsed into one larger iteration space that is then divided according to the schedule clause. The sequential execution of the iterations in these associated loops determines the order of the iterations in the collapsed iteration space.

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

例如下面的代码:

#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 基于通过调用 GOMP_loop_static_start() 确定的迭代 block (.istart0.3) 的开始。然后它简单地增加 i 和 j 就像人们期望实现循环嵌套一样，即增加 j 直到它达到 100，然后将 j 重置为 0 并增加 i。同时，它还保留了.iter.1中折叠迭代空间的当前迭代次数，基本上是同时迭代单个折叠循环和两个嵌套循环。

对于线程数不除以迭代次数的情况，OpenMP 标准说:

When no chunk_size is specified, the iteration space is divided into chunks that are approximately equal in size, and at most one chunk is distributed to each thread. The size of the chunks is unspecified in this case.

GCC 实现让具有最高 ID 的线程少执行一次迭代。第 61 页的注释中概述了其他可能的分发策略。该列表绝不是详尽无遗的。