减少 OpenMP 中的数组

Question

我正在尝试并行化以下程序，但不知道如何减少数组。我知道这样做是不可能的，但有其他选择吗？谢谢。 （我在 m 上添加了减少，这是错误的，但想就如何做到这一点提出建议。）

 #include <iostream>
#include <stdio.h>
#include <time.h>
#include <omp.h>
using namespace std;

int main ()
{
  int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
  int S [10];

  time_t start_time = time(NULL);
  #pragma omp parallel for private(m) reduction(+:m)
  for (int n=0 ; n<10 ; ++n ){
    for (int m=0; m<=n; ++m){
      S[n] += A[m];
    }
  }
  time_t end_time = time(NULL);
  cout << end_time-start_time;

  return 0;
}

原文由 user2891902 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

是的，可以使用 OpenMP 进行数组缩减。在 Fortran 中，它甚至为此进行了构造。在 C/C++ 中，你必须自己做。这里有两种方法。

第一种方法为每个线程创建私有版本 S ，并行填充它们，然后在临界区将它们合并到 S 中（参见下面的代码）。第二种方法创建一个维度为 10*nthreads 的数组。并行填充此数组，然后将其合并到 S 而不使用临界区。第二种方法要复杂得多，如果您不小心，可能会出现缓存问题，尤其是在多插槽系统上。有关更多详细信息，请参阅 与 OpenMP 并行的填充直方图（数组缩减），而不使用关键部分

第一种方法

int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10] = {0};
#pragma omp parallel
{
    int S_private[10] = {0};
    #pragma omp for
    for (int n=0 ; n<10 ; ++n ) {
        for (int m=0; m<=n; ++m){
            S_private[n] += A[m];
        }
    }
    #pragma omp critical
    {
        for(int n=0; n<10; ++n) {
            S[n] += S_private[n];
        }
    }
}

第二种方法

int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10] = {0};
int *S_private;
#pragma omp parallel
{
    const int nthreads = omp_get_num_threads();
    const int ithread = omp_get_thread_num();

    #pragma omp single
    {
        S_private = new int[10*nthreads];
        for(int i=0; i<(10*nthreads); i++) S_private[i] = 0;
    }
    #pragma omp for
    for (int n=0 ; n<10 ; ++n )
    {
        for (int m=0; m<=n; ++m){
            S_private[ithread*10+n] += A[m];
        }
    }
    #pragma omp for
    for(int i=0; i<10; i++) {
        for(int t=0; t<nthreads; t++) {
            S[i] += S_private[10*t + i];
        }
    }
}
delete[] S_private;

原文由 Z boson 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

由于没有提到其他答案，我添加了这个答案。

我正在尝试并行化以下程序，但不知道如何减少数组。我知道这样做是不可能的，但是有 > 替代方案吗？

使用 OpenMP 4.5 ，您可以使用 pragma 减少数组，即：

 #pragma omp parallel for reduction(+:S)

一个完整的运行示例：

 #define S_SIZE 10
#include <stdio.h>
#include <time.h>
#include <omp.h>
int main ()
{
  int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
  int S [S_SIZE] = {0};

  #pragma omp parallel for reduction(+:S[:S_SIZE])
  for (int n=0 ; n<S_SIZE ; ++n ){
    for (int m=0; m<=n; ++m){
      S[n] += A[m];
    }
  }
  int expected_output [] = {84, 114, 209, 303, 339, 412, 464, 487, 489, 502};
  for(int i = 0; i < S_SIZE; i++){
      if(S[i] == expected_output[i])
        printf("%d\n", S[i]);
     else
       printf("ERROR! it should have been %d instead of %d\n", expected_output[i], S[i]);
  }

  return 0;
}

输出：

 84
114
209
303
339
412
464
487
489
502

原文由 dreamcrash 发布，翻译遵循 CC BY-SA 4.0 许可协议