smilingbuddha's questions

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

No código colado abaixo, estou executando duas funções f1and f2que realizam exatamente o mesmo trabalho. Pegue um Tarray de números e inteiros arr(que foi inicializado para 0everywhere) e então incremente Tvezes cada elemento de arr Assim, no final de ambos f1e f2, a entrada 0,0...0deve se tornar T,T...T.

O que eu não entendo é por que f1roda muito mais devagar do que f2(cerca de 1,76 vezes mais lento quando Té, digamos, 1 bilhão). Aqui está minha saída

➜ Diferença de tempo do gcc para desktop.c && ./a.out 1000000000 16

-----> Executando f1 <------- Tempo gasto: 15,511 segundos

-----> Executando f2 <------- Tempo gasto: 8,887 segundos%

Aqui Té fornecido ao programa como argv[1]e o comprimento do array como argv[2]. O timing-difference.carquivo é colado abaixo no final deste post.

Basicamente, f1é incrementar diretamente cada arr[i], enquanto f2usa uma variável temporária tmppara o incremento e, em seguida, atribui-la a arr[i] quando terminar.

#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>
#include<time.h>

/*Directly increment arr[i] for each i*/
void f1(int T, int* arr, int arrlength){

  printf("\n-----> Running f1 <-------\n");
  clock_t end, start;
  double cpu_time_used;

  // For each element of arr, increment it T times.
  start = clock();
  for(int i = 0 ;  i<arrlength ;++i){
    for (int j=0 ; j<T ; ++j){
      arr[i] += 1;
    }
  }
  end = clock();
  cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; 

  printf("Time taken: %.3f seconds", cpu_time_used);

}

/*increment arr[i] using temporary variable tmp*/
void f2(int T, int* arr, int arrlength){

  printf("\n-----> Running f2 <-------\n");
  clock_t end, start;
  double cpu_time_used;

  // For each element of arr, increment it T times.
  start = clock();
  for(int i = 0 ;  i<arrlength ;++i){

    int tmp=arr[i];
    for (int j=0 ; j<T ; ++j){
      tmp += 1;
    }
    arr[i] = tmp; 
  }

  end = clock();
  cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; 
  printf("Time taken: %.3f seconds", cpu_time_used);

}

void print_arr(int* arr, int arrlength){
  for(int i = 0 ; i<arrlength ; ++i){
    printf("%d  ", arr[i]);
  }
  printf("\n\n");

}

/*Zero initialize array*/
void initialize_array(int* arr, int arrlength){
  for (int i=0 ; i<arrlength ; ++i){
    arr[i] = 0;
  }

}

int main(int argc, char** argv){

  int T         = atoi(argv[1]);
  int arrlength = atoi(argv[2]);
  int arr[arrlength];
  
  initialize_array(arr, arrlength);
  f1(T,arr,arrlength);  // --> why does this run slower than f2?
  //print_arr(arr, arrlength);
    
  printf("\n\n");

  initialize_array(arr, arrlength);
  f2(T,arr,arrlength); 
  //print_arr(arr, arrlength);
  
  return 0;
}

EDIT : Eu obtenho as mesmas medições de tempo quando chamof2primeiro ef1depois ou mesmo se eu executo várias vezes.

Com -O2 habilitado, obtenho os timings como 0,000 em ambos. Fiquei curioso sobre as configurações padrão que o gcc estava usando para compilar e por que havia uma diferença tão grande no desempenho. A resposta, como wohlstad sugere, deve estar no assembly, mas, infelizmente, não consigo ler o assembly x86 bem :-( para um entendimento informado