减少 OpenMP 中的数组

问题描述 投票：0回答：6

我正在尝试并行化以下程序，但不知道如何减少数组。我知道不可能这样做，但是有其他选择吗？谢谢。 （我在 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;
}
c++ multithreading parallel-processing openmp reduction
6个回答
39
投票

是的，可以使用 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;
15
投票

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

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

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

#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
11
投票

对于Zboson的回答我有两点评论：
1. 方法 1 当然是正确的，但归约循环实际上是串行运行的，因为 #pragma omp critical 这当然是必要的，因为部分矩阵对于每个线程来说是本地的，并且相应的归约必须由线程完成欠矩阵。
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 输入和输出按值传递。
  1. add_m10x1 中的循环是串行运行的。
    3. 所说的“性能问题”是我自己造成的，不介绍它们是完全简单的：

    add_m10x1
  1. 的参数应通过引用传递（通过C中的指针，C++中的引用）
    2. add_m10x1
  2. 中的计算应该就地完成。
    3. add_m10x1
  3. 应声明为 void，并删除 return 语句。结果通过第一个参数返回。 声明减少编译指示应相应修改，组合器应只是函数调用而不是赋值（v4.0 规范 p181 第 9,10 行）。
  4. add_m10x1
  5. 中的for循环可以通过omp并行for pragma来并行化 应启用并行嵌套（例如通过 OMP_NESTED=TRUE）
    7. 修改后的代码部分是：

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}} ) 




    

    
    
    

    

        

            

                

                    
3
投票

                    
                

            

        

        


#pragma omp parallel for
对于外循环.

    





    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        



int S0, S1, S2, ..., S9;
...
#pragma omp parallel for private(...) shared(S0, S1, S2, ..., S9) \
            reduction(+:S0, S1, S2, ..., S9)
for ...




这让您不得不编写某种 
if
 或 
case
 语句来确定要更新哪些临时项，这是一个不吸引人的前景。  如果您的代码只是您想用于学习的示例，请继续。


但是，如果您真的打算编写一个并行前缀和例程，那么请四处搜索。  
这是一个很好的起点。

    




    

    
    
    

    

        

            

                

                    
0
投票

                    
                

            

        

        


#包括 
#包括

#define N 10

int main() {
    double array[N];
    double sum = 0.0;

    for (int i = 0; i < N; i++) {
        array[i] = i;
    }
 
#pragma omp parallel for reduction(+:sum)
    for (int i = 0; i < N; i++) {
        sum += i * array[i];
    }

    return 0;
}


    
	

    

    


  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.