理解openmp中的collapse子句

Question

我遇到了一个具有崩溃条款的OpenMP代码,这对我来说是新的.我试图理解这意味着什么,但我认为我没有完全理解它的含义; 我发现的一个定义是:

COLLAPSE:指定嵌套循环中应将多少循环折叠到一个大的迭代空间中,并根据schedule子句进行划分.在所有关联循环中顺序执行迭代确定了折叠迭代空间中迭代的顺序.

我以为我理解了这意味着什么,所以我尝试了以下简单的程序:

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's 1' 和's'.但是我得到了

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

所以我的问题是:

1. 我的代码中发生了什么？
2. 我应该在什么情况下使用collapse？
3. 您能举例说明使用collapse和不使用它之间的区别吗？

Answer 1

你的代码的问题是内部循环的迭代依赖于外部循环.根据关于绑定和collapse条款部分描述的OpenMP规范:

如果任何关联循环的执行更改了用于计算任何迭代计数的任何值,则行为未指定.

如果不是这种情况,例如使用方形循环,则可以使用折叠

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

事实上,这是显示何时使用折叠的一个很好的例子.外循环只有四次迭代.如果你有超过四个线程,那么一些将被浪费.但是当你崩溃时,线程将在400次迭代中分布,这可能比线程数大得多.使用折叠的另一个原因是负载分布不均匀.如果您只使用了四次迭代,并且第四次迭代占用了大部分时间,则其他线程会等待.但是如果使用400次迭代,负载可能会更好地分布.

您可以手动融合上面的代码循环,如下所示

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

这是一个示例,显示如何手动融合三重融合环.

最后,这是一个示例,说明如何融合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问题的地图来自

(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的奇数值,地图不完全是矩形,但公式仍然有效.

例如,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);
    }
}