Phép nhân song song OpenMP bằng phép nhân ba cho vòng lặp (vấn đề hiệu suất)

Question

Tôi đang viết một chương trình nhân ma trận với OpenMP, để thuận tiện cho bộ đệm, thực hiện phép nhân A x B (chuyển vị) hàng X hàng thay vì cổ điển Một x B hàng x cột, cho hiệu quả bộ nhớ cache tốt hơn. Làm điều này tôi phải đối mặt với một thực tế thú vị cho tôi là vô lý: nếu trong đoạn mã này tôi song song với vòng lặp bên ngoài, chương trình sẽ chậm hơn nếu tôi đặt chỉ thị OpenMP trong vòng lặp bên trong nhất, trong máy tính của tôi thời gian là 10,9 so với 8,1 giây.

//A and B are double* allocated with malloc, Nu is the lenght of the matrixes 
//which are square 

//#pragma omp parallel for 
for (i=0; i<Nu; i++){ 
    for (j=0; j<Nu; j++){ 
    *(C+(i*Nu+j)) = 0.; 
#pragma omp parallel for 
    for(k=0;k<Nu ;k++){ 
     *(C+(i*Nu+j))+=*(A+(i*Nu+k)) * *(B+(j*Nu+k));//C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    } 
} 

Answer 1

Hãy thử đánh kết quả ít thường xuyên hơn. Điều này gây ra chia sẻ bộ nhớ đệm và ngăn hoạt động chạy song song. Thay vào đó, sử dụng biến cục bộ sẽ cho phép hầu hết các lần ghi diễn ra trong bộ đệm L1 của mỗi lõi.

Ngoài ra, việc sử dụng restrict có thể hữu ích. Nếu không trình biên dịch không thể đảm bảo rằng ghi vào C không thay đổi A và B.

Hãy thử:

for (i=0; i<Nu; i++){ 
    const double* const Arow = A + i*Nu; 
    double* const Crow = C + i*Nu; 
#pragma omp parallel for 
    for (j=0; j<Nu; j++){ 
    const double* const Bcol = B + j*Nu; 
    double sum = 0.0; 
    for(k=0;k<Nu ;k++){ 
     sum += Arow[k] * Bcol[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    Crow[j] = sum; 
    } 
} 

Ngoài ra, tôi nghĩ Elalfer là đúng về việc cần giảm nếu bạn parallelize vòng lặp trong cùng.

Answer 2

Bạn có thể có một số phụ thuộc trong dữ liệu khi bạn song song vòng lặp bên ngoài và trình biên dịch không thể tìm ra và thêm khóa bổ sung.

Hầu hết có thể quyết định rằng các vòng lặp lặp ngoài khác nhau có thể ghi vào cùng một (C+(i*Nu+j)) và nó thêm khóa truy cập để bảo vệ nó.

Trình biên dịch có thể tìm ra rằng không có phụ thuộc nếu bạn sẽ song song vòng lặp thứ hai. Nhưng tìm ra rằng không có sự phụ thuộc nào song song với vòng lặp bên ngoài không quá nhỏ nhặt đối với trình biên dịch.

CẬP NHẬT

Một số phép đo hiệu suất.

Xin chào một lần nữa. Có vẻ như 1000 đôi * và + không đủ để trang trải chi phí đồng bộ hóa chủ đề.

Tôi đã thực hiện một vài thử nghiệm nhỏ và phép nhân vô hướng vectơ đơn giản không hiệu quả với openmp trừ khi số lượng phần tử nhỏ hơn ~ 10'000. Về cơ bản, mảng của bạn càng lớn, bạn sẽ nhận được nhiều hiệu suất hơn từ việc sử dụng openmp.

Vì vậy, song song vòng lặp bên trong nhất bạn sẽ phải tách nhiệm vụ giữa các luồng khác nhau và thu thập dữ liệu ngược lại 1.000 lần.

PS. Hãy thử Intel ICC, nó hoàn toàn miễn phí cho sinh viên và các dự án nguồn mở. Tôi nhớ đang sử dụng openmp cho các mảng yếu tố 10'000 nhỏ hơn.

UPDATE 2: Giảm dụ

double sum = 0.0; 
    int k=0; 
    double *al = A+i*Nu; 
    double *bl = A+j*Nu; 
    #pragma omp parallel for shared(al, bl) reduction(+:sum) 
    for(k=0;k<Nu ;k++){ 
     sum +=al[k] * bl[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j) 
    } 
    C[i*Nu+j] = sum;