使用OpenMP乘以矩陣需要比序列化的方式花費更多的時間

Question

當我嘗試使用OpenMP乘以兩個大方形矩陣時，並行方式比序列化方法花費的時間要多得多。我做錯了什麼？

對4核心（超線程）機器的簡單測試將導致並行計算大約需要100秒，而串行計算需要10秒！

這是我的並行代碼：

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

#define MATSIZE 500 
#define MAXRAND 100 

int main (int argc, char *argv[]) 
{ 
    double startTime = 0.0, stopTime = 0.0; 
    startTime = omp_get_wtime(); 

    int i, j, k; 
    static int a[MATSIZE][MATSIZE],b[MATSIZE][MATSIZE],c[MATSIZE][MATSIZE]; 

    srand(time(NULL)); 

    #pragma omp parallel shared(a,b,c) private(i,j,k) 
    { 
     #pragma omp for 
     for (i=0; i<MATSIZE; i++) 
      for (j=0; j<MATSIZE; j++){ 
       a[i][j]= rand()%MAXRAND; 
       b[i][j]= rand()%MAXRAND; 
       c[i][j]= 0; 
      } 
    } 

    printf("Matrix A:\n"); 
    for (i=0; i<MATSIZE; i++){ 
     for (j=0; j<MATSIZE; j++) 
      printf("%d ", a[i][j]); 
     printf("\n"); 
    } 
    printf("******************************************************\n"); 
    printf("Matrix B:\n"); 
    for (i=0; i<MATSIZE; i++){ 
     for (j=0; j<MATSIZE; j++) 
      printf("%d ", b [i][j]); 
     printf("\n"); 
    } 
    printf("******************************************************\n"); 

    #pragma omp parallel shared(a,b,c) private(i,j,k) 
    { 
     #pragma omp for 
     for (i=0; i<MATSIZE; i++){ 
      for(j=0; j<MATSIZE; j++)  
       for (k=0; k<MATSIZE; k++){ 
        c[i][j] += a[i][k] * b[k][j]; 
        printf("."); 
       } 
     } 
    } 

    printf("\nResult Matrix:\n"); 
    for (i=0; i<MATSIZE; i++){ 
     for (j=0; j<MATSIZE; j++) 
      printf("%d ", c[i][j]); 
     printf("\n"); 
    } 
    stopTime = omp_get_wtime(); 
    printf("Elapsed time = %f \n", stopTime - startTime); 
} 

這裏是串行一個：

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

#define MATSIZE 500 
#define MAXRAND 100 

int main (int argc, char *argv[]) 
{ 
    double startTime = 0.0, stopTime = 0.0; 
    startTime = omp_get_wtime(); 

    int i, j, k; 
    static int a[MATSIZE][MATSIZE],b[MATSIZE][MATSIZE],c[MATSIZE][MATSIZE]; 

    srand(time(NULL)); 

    for (i=0; i<MATSIZE; i++) 
     for (j=0; j<MATSIZE; j++){ 
      a[i][j]= rand()%MAXRAND; 
      b[i][j]= rand()%MAXRAND; 
      c[i][j]= 0; 
     } 

    printf("Matrix A:\n"); 
    for (i=0; i<MATSIZE; i++){ 
     for (j=0; j<MATSIZE; j++) 
      printf("%d ", a[i][j]); 
     printf("\n"); 
    } 
    printf("******************************************************\n"); 
    printf("Matrix B:\n"); 
    for (i=0; i<MATSIZE; i++){ 
     for (j=0; j<MATSIZE; j++) 
      printf("%d ", b [i][j]); 
     printf("\n"); 
    } 
    printf("******************************************************\n"); 

    for (i=0; i<MATSIZE; i++){ 
     for(j=0; j<MATSIZE; j++)  
      for (k=0; k<MATSIZE; k++){ 
       c[j][i] += a[j][k] * b[k][i]; 
       printf("."); 
      } 
    } 

    printf("\nResult Matrix:\n"); 
    for (i=0; i<MATSIZE; i++){ 
     for (j=0; j<MATSIZE; j++) 
      printf("%d ", c[i][j]); 
     printf("\n"); 
    } 
    stopTime = omp_get_wtime(); 
    printf("Elapsed time = %f \n", stopTime - startTime); 
} 

Answer 1

由於user2357112如已經mentionned，您的罪魁禍首是printf（也rand()）。這些功能可以訪問您的進程的全局狀態並通過互斥體（通常）保護它。所以在一個時間關鍵的並行循環中有這樣的功能根本沒有意義，他們強行將您的執行序列化。

您還可以在編寫OMP程序時緩解自己的痛苦。您應該將所有這些變量聲明爲private，就像它們在使用範圍中的局部變量一樣。那麼不需要額外的OMP註釋。

Answer 2

代碼中存在數據競爭，因爲rand()不是線程安全函數。有一個PRNG裏面有一個狀態，因此無法在沒有同步的情況下被多個線程調用。使用不同的PRNG（例如Mersenne Twister的Xorshift +），每個線程使用一個生成器，並且不要忘記使用不同的種子值（謹防time(NULL)）對它們進行種子處理。