减少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;}

Answer 1

是的，可以使用OpenMP进行阵列缩减。在Fortran中，它甚至对此具有构造。在C / C ++中，您必须自己做。这有两种方法。

第一种方法S为每个线程创建的私有版本，并行填充它们，然后将它们合并到S关键部分（请参见下面的代码）。第二种方法创建一个具有10 * nthread个尺寸的数组。并行填充此数组，然后在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;

Answer 2

关于Zboson的答案，我有两点评论：

1.方法1当然是正确的，但是归约循环实际上是串行运行的，因为#pragma ompcritical必不可少，因为部分线程对于每个线程都是局部的，并且相应的归约具有通过线程来完成矩阵。

2.方法2：初始化循环可以移到单个部分的外面，因此可以并行化。

以下程序使用openMP v4.0用户定义的还原工具实现 阵列还原：

/* Compile with:

     gcc -Wall -fopenmp -o ar ar.c

   Run with:

     OMP_DISPLAY_ENV=TRUE OMP_NUM_THREADS=10 OMP_NESTED=TRUE ./ar

*/

#include <stdio.h>

#include <omp.h>

struct m10x1 {int v[10];};

int A [] =       {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};  

struct m10x1 S = {{ 0,  0,  0,  0,  0,  0,  0,  0, 0,  0}};

int n,m=0;

void print_m10x1(struct m10x1 x){

  int i;

  for(i=0;i<10;i++) printf("%d ",x.v[i]);

  printf("\n");

}

struct m10x1 add_m10x1(struct m10x1 x,struct m10x1 y){

  struct m10x1 r ={{ 0,  0,  0,  0,  0,  0,  0,  0, 0,  0}};

  int i;

  for (i=0;i<10;i++) r.v[i]=x.v[i]+y.v[i];

  return r;

}

#pragma omp declare reduction(m10x1Add: struct m10x1: \

omp_out=add_m10x1(omp_out, omp_in)) initializer( \

omp_priv={{ 0,  0,  0,  0,  0,  0,  0,  0, 0,  0}} )

int main ()

{

  #pragma omp parallel for reduction(m10x1Add: S)

  for ( n=0 ; n<10 ; ++n )

    {

      for (m=0; m<=n; ++m){

        S.v[n] += A[m];

      }

    }

  print_m10x1(S);

}

这完全按照OpenMP 4.0功能第97页的复数减少示例进行。

尽管并行版本可以正常工作，但可能存在性能问题，我尚未调查：

add_m10x1输入和输出按值传递。

add_m10x1中的循环按顺序运行。

所说的“性能问题”是我自己造成的，完全不介绍它们就很简单：

add_m10x1的参数应通过引用传递（通过C中的指针，C ++中的引用）

add_m10x1中的计算应就位。

应该将add_m10x1声明为void，并删除return语句。结果通过第一个参数返回。

应该相应地减少声明减少编译指示，合并器应该只是函数调用而不是赋值（v4.0规范p181第9,10行）。

add_m10x1中的for循环可以通过omp parallel for pragma并行化

应启用并行嵌套（例如，通过OMP_NESTED = TRUE）

然后，代码的修改部分为：

void add_m10x1(struct m10x1 * x,struct m10x1 * y){

  int i;

  #pragma omp parallel for

  for (i=0;i<10;i++) x->v[i] += y->v[i];

}

#pragma omp declare reduction(m10x1Add: struct m10x1: \

add_m10x1(&omp_out, &omp_in)) initializer( \

omp_priv={{ 0,  0,  0,  0,  0,  0,  0,  0, 0,  0}} )