Reduzindo em array no OpenMP

Eu estou tentando paralelizar o programa a seguir, mas não sei como reduzir em uma matriz. Eu sei que não é possível fazer isso, mas existe uma alternativa? Obrigado. (Eu adicionei redução em m que está errado, mas gostaria de ter um conselho sobre como fazer isso.)

#include  #include  #include  #include  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; } 

Sim, é possível fazer uma redução de matriz com o OpenMP. Em Fortran, ainda tem um constructo para isso. Em C / C ++ você tem que fazer isso sozinho. Aqui estão duas maneiras de fazer isso.

O primeiro método cria uma versão privada de S para cada thread, preenche-os em paralelo e depois os mescla em S em uma seção crítica (veja o código abaixo). O segundo método faz um array com dimensões 10 * nthreads. Preenche essa matriz em paralelo e, em seguida, mescla-a em S sem usar uma seção crítica. O segundo método é muito mais complicado e pode ter problemas de cache, especialmente em sistemas com vários sockets, se você não for cuidadoso. Para obter mais detalhes, consulte Histogramas de preenchimento (redução de matriz) em paralelo com o OpenMP sem usar uma seção crítica

Primeiro método

 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]; } } } 

Segundo método

 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 

Eu tenho duas observações sobre a resposta de Zboson:
1. O método 1 é certamente correto, mas o loop de redução é executado em série, devido ao #pragma omp crítico, que é necessário, naturalmente, já que as matrizes parciais são locais para cada thread e a redução correspondente deve ser feita pelo encadeamento devido ao encadeamento. matriz.
2. Método 2: O loop de boot pode ser movido para fora da seção única e, portanto, tornar-se paralelizável.

O programa a seguir implementa a redução de matriz usando o recurso de redução definida pelo usuário 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  #include  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 ",xv[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++) rv[i]=xv[i]+yv[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){ Sv[n] += A[m]; } } print_m10x1(S); } 

Isto segue literalmente o exemplo de redução numérica complexa na página 97 dos resources do OpenMP 4.0 .

Embora a versão paralela funcione corretamente, provavelmente há problemas de desempenho, que eu não investiguei:

  1. add_m10x1 inputs e saídas são passadas por valor.
  2. O loop em add_m10x1 é executado em série.

Dito "problemas de desempenho" são de minha própria autoria e é completamente simples não apresentá-los:

  1. parameters para add_m10x1 devem ser passados ​​por referência (via pointers em C, referências em C ++)
  2. O cálculo em add_m10x1 deve ser feito no lugar.
  3. add_m10x1 deve ser declarado nulo e a declaração de retorno excluída. O resultado é retornado pelo primeiro parâmetro.
  4. O pragma de redução declare deve ser modificado de acordo, o combinador deve ser apenas uma chamada de function e não uma atribuição (v4.0 especifica p181 linhas 9,10).
  5. O loop for em add_m10x1 pode ser paralelizado via um omp parallel para pragma
  6. O aninhamento paralelo deve ser ativado (por exemplo, via OMP_NESTED = TRUE)

A parte modificada do código é:

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

Se traduzir seu código para Fortran, que pode usar matrizes em operações de redução de OpenMP, não recorrer, você pode usar um monte de variables ​​temporárias. Por exemplo

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

Isso deixa você com a perspectiva desagradável de ter que escrever algum tipo de declaração if ou case para determinar quais dos temporários devem ser atualizados. Se o seu código é apenas um exemplo que você deseja usar para aprender, continue.

Mas se a sua intenção é realmente escrever uma rotina de sum de prefixo paralela, pesquise ao redor. Esse é um bom lugar para começar.