Istogrammi di riempimento (riduzione dell'array) in parallelo con OpenMP senza utilizzare una sezione critica

Question

Vorrei riempire gli istogrammi in parallelo usando OpenMP. Sono arrivato con due diversi metodi per farlo con OpenMP in C/C++.

Il primo metodo proccess_data_v1 effettua una variabile istogramma privato hist_private per ciascun filo, li riempie prallel, e poi somma i istogrammi privati ​​verso l'istogramma condivisa hist in una sezione critical.

Il secondo metodo proccess_data_v2 crea una matrice condivisa di istogrammi con dimensione di matrice uguale al numero di thread, riempie questo array in parallelo e quindi somma l'istogramma condiviso hist in parallelo.

Il secondo metodo mi sembra superiore in quanto evita una sezione critica e somma gli istogrammi in parallelo. Tuttavia, richiede conoscere il numero di thread e chiamare omp_get_thread_num(). In genere cerco di evitarlo. C'è un modo migliore per eseguire il secondo metodo senza fare riferimento ai numeri di thread e utilizzando un array condiviso con dimensioni pari al numero di thread?

void proccess_data_v1(float *data, int *hist, const int n, const int nbins, float max) { 
    #pragma omp parallel 
    { 
     int *hist_private = new int[nbins]; 
     for(int i=0; i<nbins; i++) hist_private[i] = 0; 
     #pragma omp for nowait 
     for(int i=0; i<n; i++) { 
      float x = reconstruct_data(data[i]); 
      fill_hist(hist_private, nbins, max, x); 
     } 
     #pragma omp critical 
     { 
      for(int i=0; i<nbins; i++) { 
       hist[i] += hist_private[i]; 
      } 
     } 
     delete[] hist_private; 
    } 
} 

void proccess_data_v2(float *data, int *hist, const int n, const int nbins, float max) { 
    const int nthreads = 8; 
    omp_set_num_threads(nthreads); 
    int *hista = new int[nbins*nthreads]; 

    #pragma omp parallel 
    { 
     const int ithread = omp_get_thread_num(); 
     for(int i=0; i<nbins; i++) hista[nbins*ithread+i] = 0; 
     #pragma omp for 
     for(int i=0; i<n; i++) { 
      float x = reconstruct_data(data[i]); 
      fill_hist(&hista[nbins*ithread], nbins, max, x); 
     } 

     #pragma omp for 
     for(int i=0; i<nbins; i++) { 
      for(int t=0; t<nthreads; t++) { 
       hist[i] += hista[nbins*t + i]; 
      } 
     } 

    } 
    delete[] hista; 
} 

Edit: Sulla base di un suggerimento di @HristoIliev ho creato un metodo migliore chiamato process_data_v3

#define ROUND_DOWN(x, s) ((x) & ~((s)-1)) 
void proccess_data_v2(float *data, int *hist, const int n, const int nbins, float max) { 
    int* hista; 
    #pragma omp parallel 
    { 
     const int nthreads = omp_get_num_threads(); 
     const int ithread = omp_get_thread_num(); 

     int lda = ROUND_DOWN(nbins+1023, 1024); //1024 ints = 4096 bytes -> round to a multiple of page size 
     #pragma omp single 
     hista = (int*)_mm_malloc(lda*sizeof(int)*nthreads, 4096); //align memory to page size 

     for(int i=0; i<nbins; i++) hista[lda*ithread+i] = 0; 
     #pragma omp for 
     for(int i=0; i<n; i++) { 
      float x = reconstruct_data(data[i]); 
      fill_hist(&hista[lda*ithread], nbins, max, x); 
     } 

     #pragma omp for 
     for(int i=0; i<nbins; i++) { 
      for(int t=0; t<nthreads; t++) { 
       hist[i] += hista[lda*t + i]; 
      } 
     } 

    } 
    _mm_free(hista); 
} 

Answer 1

Si potrebbe allocare la grande matrice all'interno della regione in parallelo, dove si può interrogare su il numero effettivo di thread utilizzati:

int *hista; 
#pragma omp parallel 
{ 
    const int nthreads = omp_get_num_threads(); 
    const int ithread = omp_get_thread_num(); 

    #pragma omp single 
    hista = new int[nbins*nthreads]; 

    ... 
} 
delete[] hista; 

Per prestazioni migliori I w Potresti consigliare di arrotondare le dimensioni del blocco di ciascun thread in hista a un multiplo delle dimensioni della pagina di memoria del sistema, anche se questo potrebbe potenzialmente lasciare buchi tra i diversi istogrammi parziali. In questo modo impedirai sia la condivisione falsa che l'accesso alla memoria remota sui sistemi NUMA (ma non nella fase di riduzione finale).