Điền vào biểu đồ (giảm mảng) song song với OpenMP mà không cần sử dụng phần quan trọng

Question

Tôi muốn điền biểu đồ song song bằng cách sử dụng OpenMP. Tôi đã đưa ra hai phương pháp khác nhau để làm điều này với OpenMP trong C/C++.

Phương pháp đầu tiên proccess_data_v1 tạo ra một biểu đồ biến tin hist_private cho mỗi thread, lấp đầy chúng trong prallel, và sau đó tóm tắt các biểu đồ tin vào histogram chia sẻ hist trong một phần critical.

Phương thức thứ hai proccess_data_v2 tạo một mảng biểu đồ được chia sẻ với kích thước mảng bằng số lượng chuỗi, điền mảng này song song và sau đó tổng hợp biểu đồ được chia sẻ hist song song.

Phương pháp thứ hai có vẻ vượt trội so với tôi vì nó tránh được phần quan trọng và tổng các biểu đồ song song. Tuy nhiên, nó đòi hỏi phải biết số lượng các chủ đề và gọi số omp_get_thread_num(). Tôi thường cố tránh điều này. Có cách nào tốt hơn để làm phương pháp thứ hai mà không tham khảo các số thread và sử dụng một mảng chia sẻ với kích thước bằng số lượng các chủ đề?

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: Dựa trên một gợi ý bởi @HristoIliev Tôi đã tạo ra một phương pháp cải tiến gọi là 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

Bạn có thể bố trí các mảng lớn bên trong khu vực song song, nơi bạn có thể truy vấn về số lượng chủ đề thực tế đang được sử dụng:

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; 

Để có hiệu suất tốt hơn tôi w ould khuyên bạn nên làm tròn kích thước của đoạn của mỗi thread trong hista đến một bội số của kích thước trang bộ nhớ của hệ thống, ngay cả khi điều này có khả năng có thể để lại lỗ giữa các biểu đồ một phần khác nhau. Bằng cách này, bạn sẽ ngăn chặn cả việc chia sẻ sai và truy cập bộ nhớ từ xa trên các hệ thống NUMA (nhưng không phải trong giai đoạn giảm cuối cùng).