时间戳

首页 > 解决方案 > 并行化嵌套的 for 循环：分割数据

c++ - 并行化嵌套的 for 循环：分割数据

问题描述

我有两个带整数参数的函数；称他们为f和g。我还有另一个函数h接受两个整数参数。给定一个大小为 D 的正方形 U（意思是：{m0,m0+1,..,m0+D-1}x{n0,n0+1,...,n0+D-1}），我有一个程序用于计算 f(n) g(m) h(n,m) 在时间上在 D 上大致线性的总和，给定数组farr，garr包含 f(m0),f(m0+1),...,f(m0+ D-1) 和 g(n0),g(n0+1),...,g(n0+D-1); 让我们将该过程视为一个黑匣子，例如，我们通过调用 Sum(farr,garr,m0,n0,D) 来调用它。我们可以计算 farr[0]=f(m0),...farr[D-1]=f(m0+D-1) 或 garr[0]=garr(n0),garr[1]=g(n0 +1),...,garr[n0+D-1] 通过调用 Fillf(f,m0,D) 和 Fillg(g,m0,D) 在时间上大致线性地分布在 D 上。

问题是如何有效地计算 {0,1,...,rD-1}x{0,1 中所有 (n,m) 的 f(n) g(m) h(n,m) 之和,...,rD-1} （比如说）并行。这在抽象上很容易——我想知道的是如何在 OpenMP 中做到这一点。

最简单的方法可能是这样的：

S=0;
#pragma omp parallel for collapse(2) schedule(dynamic) private(m0,n0,farr,garr) reduction(+:S)
for(m0=0; m0<r*D; m0+=D)
 for(n0=0; n0<r*D; n0+=D)
  farr = (short *) calloc(D,sizeof(int));
  Fillf(farr,m0,D);
  garr = (short *) calloc(D,sizeof(int));
  Fillg(garr,n0,D);
  S+=Sum(farr,garr,m0,n0,D)
  free(garr);
  free(farr);

这工作得很好，但它的缺点是每个段farr和garr被计算 r 次而不是一次。考虑到整体计算复杂度没有改变（它不会比 O(r^2 D) 更好），这几乎不是悲剧，但仍然是不可取的。

另一种方法是写

S=0;
#pragma omp parallel for schedule(dynamic) private(m0,n0,farr,garr) reduction(+:S)
for(m0=0; m0<r*D; m0+=D) {
 farr = (short *) calloc(D,sizeof(int));
 Fillf(farr,m0,D);
 for(n0=0; n0<r*D; n0+=D) {
  garr = (short *) calloc(D,sizeof(int));
  Fillg(garr,n0,D);
  S+=Sum(farr,garr,m0,n0,D)
  free(garr);
 }
 free(farr);
}

这也是一个可行的解决方案，但是：(a) 的每个段garr仍然被计算 r 次而不是一次，(b) 如果可用线程的数量大大大于r（但小于r^2），则并行化将效率低下。在这里我们不能使用collapse(2)，因为在两个循环之间发生了一些事情。

显然应该可以做得更好。使用 OpenMP 对或多或少明显的过程进行编码的直接方法是什么？（是否应该预先计算大小约为 sqrt(s) D 的段farr，garr其中 s 是可用线程的数量，然后使用collapse(2)for执行嵌套循环m0并n0遍历长度约为 D sqrt(s) 的段？）

标签： c++copenmpnested-loops

解决方案

如果您想避免重复计算farr和garr，那么您至少有两个选择：

  1. 提前计算并存储所有所有garr内容，在一个单独的循环中，并采取与您的第二种选择相同的方法。farr或者，也可以提前计算和存储所有数据。

  2. 修改您的第二个替代方案以并行化内部循环而不是外部循环。这也将使您能够提升farr循环外的分配和释放：

    S = 0;
farr = malloc(D, sizeof(int));
for (int m0 = 0; m0 < r * D; m0 += D) {
    int S2 = 0;
    Fillf(farr, m0, D);
    #pragma omp parallel for private(farr, m0) reduction(+:S2)
    for (int n0 = 0; n0 < r * D; n0 += D) {
        int *garr = calloc(D, sizeof(int));
        Fillg(garr, n0, D);
        S2 += Sum(farr, garr, m0, n0, D)
        free(garr);
    }
    S += S2;
}
free(farr);

另请注意，

  • 如果Fillf()假设它的数组参数最初是零填充的（calloc()确保），那么将内存分配提升到循环之外将需要在每次调用之前手动填充零，但这仍然可能比释放和重新分配便宜。
  • 我删除了调度子句，因为动态调度似乎对这种计算没有任何好处
  • 声明farr私有只使指针私有，而不是它指向的数据。此外，由于在并行循环中既没有farr也没有m0修改，因此将它们声明为私有实际上并没有用处。我private将示例代码中的子句主要作为这些评论的焦点。
  • 重新计算各种值的节省与garr细粒度并行带来的额外开销相抵触。如果内循环每次迭代的工作量还是比较大的话，这更有可能是胜利。

推荐阅读