Параллельное уменьшение массива на CPU - PullRequest
Новая
       36

Параллельное уменьшение массива на CPU

3 голосов
/ 22 февраля 2012

Есть ли способ сделать параллельное сокращение массива на процессоре в C / C ++ ?. Недавно я узнал, что это невозможно, используя openmp . Любые другие альтернативы?

1 Ответ

7 голосов
/ 22 февраля 2012

Добавлено : обратите внимание, что вы можете реализовать "пользовательское" сокращение с помощью OpenMP, как описано здесь .

Для C ++: с parallel_reduce в TBB Intel (тег SO: ) можно сокращать сложные типы, такие как массивы и структуры. Хотя объем требуемого кода может быть значительно больше по сравнению с пунктом сокращения 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 велико, замена цикла не даст достаточного параллелизма (например, подумайте о вычислении взвешенного центроида из N точек в M-мерном пространстве, где 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.

...