OpenMPを使用して行列を掛け合わせると、直列化された方法よりもはるかに時間がかかります

Question

OpenMPを使用して2つの大きな正方行列を掛けようとすると、並列化は直列化よりも時間がかかります。私は間違って何かしていますか？

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); 
} 

そして、ここでは、シリアル1である：

#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 +など）を使用し、スレッドごとに1つのジェネレータを使用し、異なる種値の（注意：time(NULL)）を使用することを忘れないでください。