在CPU上并行减少一个数组

Question

有没有办法在C/C++中使用CPU进行数组的并行归约？我最近了解到，使用openmp不可能实现此操作。还有其他替代方法吗？

- captain

---

你的意思是“除非你使用一个符合最新标准的Fortran编译器，否则无法使用OpenMP”，对吗？ - talonmies

@talonmies 使用C或C++编程语言。我刚才编辑了它！ - captain

你可以使用前缀和来编写并行化约简算法。http://en.wikipedia.org/wiki/Prefix_sum - perreal

@perreal 我更倾向于使用API/内置算法来完成它。 - captain

Answer 1

新增：请注意，您可以使用OpenMP实现“自定义”约简，方法如此处所述。

---

对于C++：使用Intel's TBB（SO标签：tbb）中的parallel_reduce，您可以对诸如数组和结构体之类的复杂类型进行归约。尽管所需代码量与OpenMP的reduction语句相比可能显著增加。

例如，让我们并行化矩阵乘向量的朴素实现：y=Cx。串行代码由两个循环组成：

double x[N], y[M], C[N][M];
// assume x and C are initialized, and y consists of zeros
for(int i=0; i<N; ++i)
  for(int j=0; j<M; ++j) 
    y[j] += C[i][j]*x[i];

通常，为了并行化它，循环会被交换以使外部循环迭代独立并在并行处理中进行处理：

#pragma omp parallel for
for(int j=0; j<M; ++j) 
  for(int i=0; i<N; ++i)
    y[j] += C[i][j]*x[i];

然而并非总是好的想法。如果 M 很小而 N 很大，则交换循环不会提供足够的并行性（例如，考虑在 M 维空间中计算 N 个点的加权 质心，其中 C 是点的数组，x 是权重的数组）。因此，对数组（即点）进行缩减将是有帮助的。以下是使用 TBB 完成此操作的方法（抱歉，代码未经测试，可能存在错误）：

struct reduce_body {
  double y_[M]; // accumulating vector
  double (& C_)[N][M]; // reference to a matrix
  double (& x_)[N];    // reference to a vector

  reduce_body( double (&C)[N][M], double (&x)[N] )  : C_(C), x_(x) {
    for (int j=0; j<M; ++j) y_[j] = 0.0; // prepare for accumulation
  }
  // splitting constructor required by TBB
  reduce_body( reduce_body& rb, tbb::split ) : C_(rb.C_), x_(rb.x_) { 
    for (int j=0; j<M; ++j) y_[j] = 0.0;
  }
  // the main computation method
  void operator()(const tbb::blocked_range<int>& r) {
    // closely resembles the original serial loop
    for (int i=r.begin(); i<r.end(); ++i) // iterates over a subrange in [0,N)
      for (int j=0; j<M; ++j)
        y_[j] += C_[i][j]*x_[i];
  }
  // the method to reduce computations accumulated in two bodies
  void join( reduce_body& rb ) {
    for (int j=0; j<M; ++j) y_[j] += rb.y_[j];
  }
};
double x[N], y[M], C[N][M];
...
reduce_body body(C, x);
tbb::parallel_reduce(tbb::blocked_range<int>(0,N), body);
for (int j=0; j<M; ++j)
  y[j] = body.y_[j]; // copy to the destination array

免责声明：我与TBB有关联。

- Alexey Kukanov

---

你好 @Alexey，关于数组的parallel_reduce文档不够充分，大部分都是针对简单的reduction。你能提供一个相关的链接吗？ - captain

非常感谢你的代码，@Alexey。但是，我不明白为什么要使用a[j]? - captain

抱歉，我的错误，现在已经修复了。 - Alexey Kukanov