c - 了解 openmp 中的 collapse 子句

Question

我遇到了一个包含 collapse 子句的 OpenMP 代码，这对我来说是新的。我试图理解它的含义，但我认为我没有完全理解它的含义；我找到的一个定义是:

COLLAPSE: Specifies how many loops in a nested loop should be collapsed into one large iteration space and divided according to the schedule clause. The sequential execution of the iterations in all associated loops determines the order of the iterations in the collapsed iteration space.

我以为我明白那是什么意思，所以我尝试了以下简单程序:

int i, j;
#pragma omp parallel for num_threads(2) private(j)
for (i = 0; i < 4; i++)
    for (j = 0; j <= i; j++)
        printf("%d %d %d\n", i, j, omp_get_thread_num());

产生了

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

然后我添加了 collapse(2) 子句。我希望在前两列中得到相同的结果，但现在在最后一列中有相同数量的 0 和 1。但是我得到了

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

所以我的问题是:

1. 我的代码中发生了什么？
2. 什么情况下应该使用collapse？
3. 您能否提供一个示例来说明使用 collapse 和不使用它之间的区别？

Answer 1

您的代码的问题在于内循环的迭代取决于外循环。根据绑定(bind)部分和 collapse 子句描述下的 OpenMP 规范:

If execution of any associated loop changes any of the values used to compute any of the iteration counts, then the behavior is unspecified.

如果不是这种情况，您可以使用 collapse，例如方形循环

#pragma omp parallel for private(j) collapse(2)
for (i = 0; i < 4; i++)
    for (j = 0; j < 100; j++)

事实上，这是一个展示何时使用折叠的好例子。外循环只有四次迭代。如果您有四个以上的线程，那么有些线程将被浪费。但是当你崩溃时，线程将分布在 400 次迭代中，这可能比线程数大得多。使用 collapse 的另一个原因是负载分布不均。如果您只使用了四次迭代，而第四次迭代占用了其他线程等待的大部分时间。但是，如果您使用 400 次迭代，负载可能会得到更好的分配。

您可以像这样为上面的代码手动融合一个循环

#pragma omp parallel for
for(int n=0; n<4*100; n++) {
    int i = n/100; int j=n%100;

Here是一个展示如何手动融合三重融合循环的示例。

最后，here是一个示例，显示如何融合未定义 collapse 的三角形循环。

---

这是一个将矩形环映射到 OP 问题中的三角形环的解决方案。这可用于融合 OP 三角环。

//int n = 4;
for(int k=0; k<n*(n+1)/2; k++) {
    int i = k/(n+1), j = k%(n+1);
    if(j>i) i = n - i -1, j = n - j;
    printf("(%d,%d)\n", i,j);
}

这适用于任何 n 值。

OP 问题的 map 来自

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),
(3,0), (3,1), (3,2), (3,3),

到

(0,0), (3,3), (3,2), (3,1), (3,0),
(1,0), (1,1), (2,2), (2,1), (2,0),

对于 n 的奇数值， map 不完全是一个矩形，但公式仍然有效。

例如 n = 3 从

映射

(0,0),
(1,0), (1,1),
(2,0), (2,1), (2,2),

到

(0,0), (2,2), (2,1), (2,0),
(1,0), (1,1),

下面是测试代码

#include <stdio.h>
int main(void) {
    int n = 4;
    for(int i=0; i<n; i++) {
        for(int j=0; j<=i; j++) {
            printf("(%d,%d)\n", i,j);
        }
    }
    puts("");
    for(int k=0; k<n*(n+1)/2; k++) {
        int i = k/(n+1), j = k%(n+1);
        if(j>i) i = n - i - 1, j = n - j;
        printf("(%d,%d)\n", i,j);
    }
}