Fill-Histogramme (Array-Reduktion) parallel zu OpenMP ohne Verwendung eines kritischen Abschnitts

Question

Ich möchte Histogramme parallel mit OpenMP ausfüllen. Ich habe zwei verschiedene Methoden gefunden, dies mit OpenMP in C/C++ zu tun.

Die erste Methode proccess_data_v1 ein eigenes Histogramm Variable für jeden Thread hist_private macht, füllt sie in prallel und summiert dann die privaten Histogramme in den gemeinsam benutzten Histogramms hist in einem critical Abschnitt.

Die zweite Methode proccess_data_v2 erstellt ein freigegebenes Array von Histogrammen mit Array-Größe gleich der Anzahl der Threads, füllt dieses Array parallel und summiert dann das gemeinsam genutzte Histogramm hist parallel.

Die zweite Methode scheint mir überlegen, da sie einen kritischen Abschnitt vermeidet und die Histogramme parallel summiert. Es erfordert jedoch, die Anzahl der Threads zu kennen und omp_get_thread_num() aufzurufen. Ich versuche das generell zu vermeiden. Gibt es einen besseren Weg, die zweite Methode zu verwenden, ohne auf die Thread-Nummern zu verweisen und ein gemeinsam genutztes Array zu verwenden, dessen Größe der Anzahl der Threads entspricht?

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: Basierend auf einem Vorschlag von @HristoIliev ich ein verbessertes Verfahren 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

Sie genannt erstellt haben, könnte das große Array innerhalb der parallelen Region zuzuordnen, in dem Sie über abfragen die tatsächliche Anzahl der verwendeten Threads:

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; 

Für bessere Leistung I w Es empfiehlt sich, die Größe des Chunks jedes Threads in hista auf ein Vielfaches der Speicherseitengröße des Systems zu runden, auch wenn dies möglicherweise Löcher zwischen den verschiedenen Teilhistogrammen hinterlassen könnte. Auf diese Weise verhindern Sie sowohl die falsche Freigabe als auch den Remote-Speicherzugriff auf NUMA-Systeme (jedoch nicht in der endgültigen Reduzierungsphase).