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無關。