CPU 上的数组并行缩减

Question

有没有办法在 C/C++ 中并行减少 CPU 上的数组？我最近了解到，使用 是不可能的打开mp。还有其他选择吗？

Answer 1

添加：请注意，您可以使用 OpenMP 实现“自定义”缩减，按照此处。

---

对于 C++：在 Intel 的 TBB 中使用 parallel_reduce （SO 标签：tbb)，您可以减少数组和结构体等复杂类型。尽管与 OpenMP 的缩减条款相比，所需的代码量可能要大得多。

作为示例，让我们并行化矩阵到向量乘法的简单实现：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。