Quero usar a operação de varredura inclusiva no OpenMP para implementar um algoritmo. O que se segue é uma descrição da minha tentativa de fazer isso, e não conseguindo mais do que uma aceleração morna.
A operação inclusiva é definida como segue: para um vetor de entrada, digamos que [x1,x2,x3,x4]ele produz a sequência de somas parciais [x1, x1+x2, x1+x2+x3, x1+x2+x3+x4]. Esta é uma operação altamente paralelizável e aparentemente foi bem implementada no OpenMP.
Dei uma olhada na seguinte referência: https://theartofhpc.com/pcse/omp-reduction.html#Scanprefixoperations (A referência do manual https://www.openmp.org/spec-html/5.0/openmpsu45.html#x68-1940002.9.6 parece muito enigmática para mim agora)
O site artofhpc diz que a cláusula de redução recebe um modificador inscan:
#pragma omp parallel for reduction(inscan,+:sumvar)`
No corpo do loop paralelo há uma diretiva scan que permite que você armazene os resultados parciais. Para scans inclusivos, a variável reduction é atualizada antes do pragma scan:
sumvar // update
#pragma omp scan inclusive(sumvar)
partials[i] = sumvar
Tentei seguir a mesma sintaxe, para medir o desempenho versus redução serial padrão e os resultados foram bem decepcionantes. Meu código está no final do post.
No código, estou apenas fazendo um teste simples considerando um vetor muito grande de tamanho 90 milhões consistindo de valores aleatórios no intervalo [-1,1], e realizando uma varredura nele usando um número crescente de threads e medindo a aceleração. Aqui estão meus resultados (recebo a mesma resposta em execuções repetidas). A CPU do meu laptop tem 16 threads de hardware, mas a aceleração geral é decepcionante 1,36. (Eu esperaria algo substancialmente maior!)
Há algo errado na maneira como estou usando a sintaxe OpenMP para redução?
➜ Desktop gcc -fopenmp scantest.c && ./a.out
NumThreads Speedup
1 0.458
2 1.173
3 1.424
4 1.686
5 1.635
6 1.501
7 1.522
8 1.499
9 1.455
10 1.416
11 1.395
12 1.393
13 1.352
14 1.336
15 1.353
16 1.357
#include<stdio.h>
#include<omp.h>
#include<math.h>
#include<stdlib.h>
#include<assert.h>
int main(int argc, char** argv){
int N = 9e7; // vector size
double* x; // vector to reduce
double* partials_s; // vector to scan into
double* partials_p; // vector to scan into
double end, start; // timing variables
double sumvar;
int tmax = argc>1? atoi(argv[1]):35;
int threadcount ;
// Allocate space for all vectors
x = (double*) malloc(sizeof(double)*N);
partials_s = (double*) malloc(sizeof(double)*N);
partials_p = (double*) malloc(sizeof(double)*N);
// Populate the input vectors
for(int i=0 ; i<N ; ++i){
x[i] = -1+2.0*rand()/(double)RAND_MAX;
partials_s[i] = 0.0;
partials_p[i] = 0.0;
}
//-----------------------------------------
// Serial inclusive scan
//-----------------------------------------
start = omp_get_wtime();
sumvar = 0.0;
for(int i=0 ; i<N ; ++i){
sumvar += x[i];
partials_s[i] = sumvar;
}
end = omp_get_wtime();
double stime = end-start; // Time to run the serial code
//-----------------------------------------------------------------------------
// Performance of parallel inclusive scan. Print ratio of serial/parallel time
//----------------------------------------------------------------------------
printf("\nNumThreads Speedup \n");
for(threadcount=1;threadcount<=tmax;++threadcount){
start = omp_get_wtime();
sumvar = 0.0;
#pragma omp parallel for num_threads(threadcount) reduction(inscan,+:sumvar)
for(int i=0 ; i<N ; ++i){
sumvar = sumvar + x[i]; // updating the value of sumvar
#pragma omp scan inclusive(sumvar)
partials_p[i] = sumvar;
}
end = omp_get_wtime();
double ptime = end-start;
printf("%d \t %.3f\n",threadcount,stime/ptime);
}
//for(int i=0 ; i<N ; ++i){
// printf("%.4f %.4f\n", partials_s[i], partials_p[i]);
//}
// Deallocate
free(x);
free(partials_s);
free(partials_p);
return 0;
}
