các vòng lặp lồng nhau, song song vòng lặp bên trong, sử dụng lại các chủ đề

Question

Tuyên bố từ chối trách nhiệm: ví dụ sau đây chỉ là một ví dụ giả để nhanh chóng hiểu được vấn đề. Nếu bạn đang suy nghĩ về vấn đề thế giới thực, hãy nghĩ đến bất kỳ chương trình động nào.

Vấn đề: Chúng tôi có một m ma trận n *, và chúng tôi muốn sao chép các yếu tố từ dòng trước đó như trong đoạn mã sau:

for (i = 1; i < n; i++) 
    for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 

Cách tiếp cận: lặp loop Outer phải được thực hiện theo thứ tự, chúng sẽ được thực hiện tuần tự. Vòng lặp bên trong có thể được song song. Chúng tôi muốn giảm thiểu chi phí của việc tạo và tiêu diệt các chuỗi, vì vậy chúng tôi muốn tạo nhóm các chủ đề chỉ một lần, tuy nhiên, điều này có vẻ như là một nhiệm vụ không thể trong OpenMP.

#pragma omp parallel private(j) 
{ 
    for (i = 1; i < n; i++) 
    { 
     #pragma omp for scheduled(dynamic) 
     for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
    } 
} 

Khi chúng tôi áp dụng ordered tùy chọn trên vòng ngoài, mã sẽ được thực hiện cách tuần tự, vì vậy sẽ không có đạt được hiệu suất. Tôi đang tìm cách giải quyết cho kịch bản trên, ngay cả khi tôi đã phải sử dụng một số cách giải quyết khác.

Tôi đang thêm mã thực của mình. Điều này thực sự chậm hơn so với seq. phiên bản. Vui lòng xem lại:

/* load input */ 
for (i = 1; i <= n; i++) 
    scanf ("%d %d", &in[i][W], &in[i][V]); 

/* init */ 
for (i = 0; i <= wc; i++) 
    a[0][i] = 0; 

/* compute */ 
#pragma omp parallel private(i,w) 
{ 
    for(i = 1; i <= n; ++i) // 1 000 000 
    { 
     j=i%2; 
     jn = j == 1 ? 0 : 1; 

     #pragma omp for 
     for(w = 0; w <= in[i][W]; w++) // 1000 
      a[j][w] = a[jn][w]; 

     #pragma omp for 
     for(w = in[i][W]+1; w <= wc; w++) // 350 000 
      a[j][w] = max(a[jn][w], in[i][V] + a[jn][w-in[i][W]]); 
    } 
} 

Đối với đo lường, Tôi đang sử dụng một cái gì đó như thế này:

double t; 
t = omp_get_wtime(); 
// ... 
t = omp_get_wtime() - t; 

Answer 1

Tổng hợp song song trong OpenMP cho trường hợp cụ thể này: Nó không phải là giá trị nó.

Tại sao? Hoạt động trong các vòng trong rất đơn giản. Mã được biên dịch với -O3, do đó, max() cuộc gọi có thể được thay thế bằng mã của phần thân hàm. Overhead trong rào cản ngầm có thể đủ cao, để bù lại hiệu suất đạt được, và tổng chi phí là đủ cao để làm cho mã song song thậm chí còn chậm hơn so với mã tuần tự. Tôi cũng phát hiện ra, không có đạt được hiệu suất thực trong xây dựng như:

#pragma omp parallel private(i,j) 
{ 
    for (i = 1; i < n; i++) 
    { 
     #pragma omp for 
     for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
    } 
} 

vì hiệu suất của nó cũng tương tự như này một

for (i = 1; i < n; i++) 
{ 
    #pragma omp parallel for private(j) 
    for (j = 0; j < m; j++) 
     x[i][j] = x[i-1][j]; 
} 

nhờ tích hợp trong chủ đề tái sử dụng trong GCC libgomp, theo cho bài viết này: http://bisqwit.iki.fi/story/howto/openmp/

Vì vòng lặp bên ngoài không thể được so sánh (không có tùy chọn ordered) có vẻ như không có cách nào để cải thiện đáng kể hiệu suất của p rogram trong câu hỏi bằng cách sử dụng OpenMP. Nếu ai đó cảm thấy tôi đã làm điều gì đó sai, và có thể, tôi sẽ rất vui khi thấy và kiểm tra giải pháp.