CPU上的数组并行减少

Question

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

Answer 1

已添加：请注意，您可以按照here所述的方式使用OpenMP实现“自定义”缩减。

---

对于C++：与Intel's TBBparallel_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个点的加权centroid，其中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无关。