Die Multiplikation von Matrizen mit OpenMP dauert viel länger als die serialisierte Methode

Question

Wenn ich versuche, zwei große quadratische Matrizen mit OpenMP zu multiplizieren, benötigt der parallele Weg viel mehr Zeit als der serialisierte. Mache ich etwas falsch?

Ein einfacher Test auf einer Maschine mit 4 Kernen (Hyperthreading eingeschaltet) ergibt etwa 100 Sekunden für die parallele Berechnung und 10 Sekunden für die serielle Berechnung!

Das ist mein parallel Code:

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

Und hier ist die Serien ein:

#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

Wie user2357112 wie bereits erwähnt, Ihre Schuld daran ist printf (und auch rand()). Dies sind Funktionen, die auf einen globalen Status Ihres Prozesses zugreifen und ihn (normalerweise) durch einen Mutex schützen. Wenn solche Funktionen in einer zeitkritischen Parallelschleife nicht sinnvoll sind, serialisieren sie Ihre Ausführung zwangsweise.

Auch Sie können Ihre Schmerzen lindern, wenn Sie ein OMP-Programm schreiben. Sie sollten alle Variablen, die Sie deklarieren private nur als lokale Variablen in dem Bereich, in dem sie verwendet werden. Dann ist keine zusätzliche OMP-Anmerkung erforderlich.

Answer 2

In Ihrem Code befindet sich ein Datenrennen, da rand() keine Thread-sichere Funktion ist. Es gibt einen PRNG innerhalb eines Status, der nicht von mehreren Threads ohne Synchronisierung aufgerufen werden kann. Verwenden Sie verschiedene PRNG (wie Xorshift + von Mersenne Twister), verwenden Sie einen Generator pro Gewinde und vergessen Sie nicht, sie mit verschiedenen Startwerte (Vorsicht vor time(NULL)) zu säen.