OpenMP: hiệu suất kém của mảng heap (mảng ngăn xếp hoạt động tốt)

Question

Tôi là một người dùng OpenMP khá kinh nghiệm, nhưng tôi đã gặp một vấn đề khó hiểu, và tôi hy vọng rằng ai đó ở đây có thể giúp đỡ. Vấn đề là một thuật toán băm đơn giản hoạt động tốt cho các mảng được phân bổ stack, nhưng kém cho các mảng trên heap.

Ví dụ dưới đây sử dụng i% M (i modulus M) để đếm mọi số nguyên M thứ trong phần tử mảng tương ứng. Để đơn giản, hãy tưởng tượng N = 1000000, M = 10. Nếu N% M == 0, thì kết quả nên được rằng mọi phần tử của thùng [] là bằng N/M:

#pragma omp for 
    for (int i=0; i<N; i++) 
    bins[ i%M ]++; 

Mảng thùng [] là tin cho mỗi thread (kết quả tổng hợp I của tất cả các chủ đề trong một phần quan trọng sau đó).

Khi thùng [] được cấp phát trên ngăn xếp, chương trình hoạt động tốt, với tỷ lệ hiệu suất tương ứng với số lượng lõi.

Tuy nhiên, nếu thùng [] nằm trên heap (con trỏ tới thùng [] nằm trên ngăn xếp), hiệu suất giảm mạnh. Và đó là một vấn đề lớn!

Tôi muốn song song binning (băm) của dữ liệu nhất định thành mảng heap với OpenMP và đây là lần truy cập hiệu suất chính.

Nó chắc chắn không phải là một cái gì đó ngớ ngẩn như tất cả các chủ đề cố gắng để viết vào cùng một khu vực của bộ nhớ. Đó là bởi vì mỗi luồng có các thùng [] của riêng nó, kết quả là chính xác với cả thùng phân bổ và ngăn xếp ngăn xếp, và không có sự khác biệt về hiệu suất cho các luồng đơn. Tôi đã sao chép vấn đề trên phần cứng khác (Intel Xeon và AMD Opteron), với trình biên dịch GCC và Intel C++. Tất cả các bài kiểm tra đều có trên Linux (Ubuntu và RedHat).

Có vẻ như không có lý do tại sao hiệu suất tốt của OpenMP nên được giới hạn trong mảng ngăn xếp.

Có dự đoán nào không? Có thể truy cập các luồng tới đống đi qua một số loại cổng chia sẻ trên Linux? Làm cách nào để khắc phục điều đó?

chương trình Complete để chơi xung quanh với dưới:

#include <stdlib.h> 
#include <stdio.h> 
#include <omp.h> 

int main(const int argc, const char* argv[]) 
{ 
    const int N=1024*1024*1024; 
    const int M=4; 
    double t1, t2; 
    int checksum=0; 

    printf("OpenMP threads: %d\n", omp_get_max_threads()); 

    ////////////////////////////////////////////////////////////////// 
    // Case 1: stack-allocated array 
    t1=omp_get_wtime(); 
    checksum=0; 
#pragma omp parallel 
    { // Each openmp thread should have a private copy of 
    // bins_thread_stack on the stack: 
    int bins_thread_stack[M]; 
    for (int j=0; j<M; j++) bins_thread_stack[j]=0; 
#pragma omp for 
    for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
     const int j=i%M; 
     bins_thread_stack[j]++; 
     } 
#pragma omp critical 
    for (int j=0; j<M; j++) checksum+=bins_thread_stack[j]; 
    } 
    t2=omp_get_wtime(); 
    printf("Time with stack array: %12.3f sec, checksum=%d (must be %d).\n", t2-t1, checksum, N); 
    ////////////////////////////////////////////////////////////////// 

    ////////////////////////////////////////////////////////////////// 
    // Case 2: heap-allocated array 
    t1=omp_get_wtime(); 
    checksum=0; 
    #pragma omp parallel 
    { // Each openmp thread should have a private copy of 
    // bins_thread_heap on the heap: 
    int* bins_thread_heap=(int*)malloc(sizeof(int)*M); 
    for (int j=0; j<M; j++) bins_thread_heap[j]=0; 
    #pragma omp for 
    for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
     const int j=i%M; 
     bins_thread_heap[j]++; 
     } 
    #pragma omp critical 
    for (int j=0; j<M; j++) checksum+=bins_thread_heap[j]; 
    free(bins_thread_heap); 
    } 
    t2=omp_get_wtime(); 
    printf("Time with heap array: %12.3f sec, checksum=%d (must be %d).\n", t2-t1, checksum, N); 
    ////////////////////////////////////////////////////////////////// 

    return 0; 
} 

kết quả đầu ra mẫu của chương trình là dưới đây:

cho OMP_NUM_THREADS = 1

OpenMP threads: 1 
Time with stack array: 2.973 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array: 3.091 sec, checksum=1073741824 (must be 1073741824). 

và cho OMP_NUM_THREADS = 10

OpenMP threads: 10 
Time with stack array: 0.329 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array: 2.150 sec, checksum=1073741824 (must be 1073741824). 

Tôi rất cảm kích sự giúp đỡ của bạn!

Answer 1

Đây là vấn đề dễ thương: với mã như trên (gcc4.4, Intel i7) với 4 chủ đề tôi nhận được

OpenMP threads: 4 
Time with stack array:  1.696 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array:  5.413 sec, checksum=1073741824 (must be 1073741824). 

nhưng nếu tôi thay đổi dòng malloc để

int* bins_thread_heap=(int*)malloc(sizeof(int)*M*1024); 

(Cập nhật: hoặc thậm chí

int* bins_thread_heap=(int*)malloc(sizeof(int)*16); 

)

sau đó tôi nhận được

OpenMP threads: 4 
Time with stack array:  1.578 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array:  1.574 sec, checksum=1073741824 (must be 1073741824). 

Sự cố ở đây là false sharing. Các malloc mặc định đang được rất (không gian) hiệu quả, và đưa các yêu cầu phân bổ nhỏ tất cả trong một khối bộ nhớ, bên cạnh nhau; nhưng kể từ khi phân bổ quá nhỏ mà nhiều phù hợp trong cùng một dòng bộ nhớ cache, có nghĩa là mỗi lần một thread cập nhật các giá trị của nó, nó dirties dòng bộ nhớ cache của các giá trị trong các chủ đề lân cận. Bằng cách làm cho bộ nhớ được yêu cầu đủ lớn, điều này không còn là vấn đề nữa.

Ngẫu nhiên, phải rõ ràng lý do khiến trường hợp được phân bổ theo chồng không thấy vấn đề này; chủ đề khác nhau - ngăn xếp khác nhau - bộ nhớ đủ xa appart rằng chia sẻ sai không phải là một vấn đề.

Là một điểm phụ - nó không thực sự quan trọng đối với M kích thước bạn đang sử dụng ở đây, nhưng nếu M của bạn (hoặc số lượng các chủ đề) lớn hơn, quan trọng nhất sẽ là một nút cổ chai nối tiếp lớn; bạn có thể sử dụng OpenMP reductions để tính tổng kiểm tra hiệu quả hơn

#pragma omp parallel reduction(+:checksum) 
    { // Each openmp thread should have a private copy of 
     // bins_thread_heap on the heap: 
     int* bins_thread_heap=(int*)malloc(sizeof(int)*M*1024); 
     for (int j=0; j<M; j++) bins_thread_heap[j]=0; 
#pragma omp for 
     for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
      const int j=i%M; 
      bins_thread_heap[j]++; 
     } 
     for (int j=0; j<M; j++) 
      checksum+=bins_thread_heap[j]; 
     free(bins_thread_heap); 
}