了解 openmp 中的 collapse 子句

Question

我遇到了一个包含崩溃子句的 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());

产生了

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

所以我的问题是：

我的代码中发生了什么？
什么情况下应该使用collapse？
你能提供一个例子来说明使用 collapse 和不使用它的区别吗？

Answer 1

您的代码的问题在于内循环的迭代取决于外循环。根据绑定部分和 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.

您可以在不是这种情况时使用折叠，例如方形循环

#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 问题的地图来自

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

Answer 2

如果您的目的是在增加的行上平衡负载，假设每个项目的工作负载是规则的或分散的，那么如何将行索引对折，而忘记 collapse 子句？

#pragma omp for
for (int iy0=0; iy0<n; ++iy0){
  int iy = iy0;
  if (iy0 >= n/2) iy = n-1 -iy0 +n/2;
  for (int ix=iy+1; ix<n; ++ix){
    work(ix, iy);
  }
}

了解 openmp 中的 collapse 子句

Understanding the collapse clause in openmp

c

openmp