Les performances des multiplications matricielles restent inchangées avec OpenMP en C++

Question

auto t1 = chrono::steady_clock::now(); 
    #pragma omp parallel 
    { 

     for(int i=0;i<n;i++) 
     { 
      #pragma omp for collapse(2) 
      for(int j=0;j<n;j++) 
      { 

       for(int k=0;k<n;k++) 
       { 
        C[i][j]+=A[i][k]*B[k][j]; 
       } 

      } 
     } 
    } 
auto t2 = chrono::steady_clock::now(); 

auto t = std::chrono::duration_cast<chrono::microseconds>(t2 - t1).count(); 

Avec et sans parallélisation la variable t reste assez constante. Je ne suis pas sûr de la raison pour laquelle cela arrive. En outre, une fois en temps t est 0. sorti je suis face à un problème de plus est que si j'augmente la valeur de n à quelque chose comme 500, le compilateur ne peut pas exécuter le programme. (Ici, j'ai pris n = 100) J'utilise code :: blocks avec le compilateur GNU GCC.

Answer 1

La parallélisation OpenMP proposée n'est pas correct et peut conduire à des résultats erronés. Lors de la spécification collapse(2), les threads exécutent "simultanément" les itérations (j, k). Si deux (ou plusieurs) threads travaillent sur le même j mais différent de k, ils accumulent le résultat de A[i][k]*B[k][j] au même emplacement de tableau C[i][j]. Il s'agit d'une condition de concurrence, c'est-à-dire "deux threads ou plus peuvent accéder aux données partagées et ils essaient de les changer en même temps" (What is a race condition?). Les courses de données ne conduisent pas nécessairement à des résultats erronés malgré le fait que le code n'est pas OpenMP valide et peuvent produire des résultats erronés en fonction de plusieurs facteurs (planification, implémentation du compilateur, nombre de threads, ...). Pour résoudre le problème dans le code ci-dessus, OpenMP offre la clause reduction:

#pragma omp parallel 
    { 
     for(int i=0;i<n;i++) { 
      #pragma omp for collapse(2) reduction(+:C) 
      for(int j=0;j<n;j++) { 
       for(int k=0;k<n;k++) { 
        C[i][j]+=A[i][k]*B[k][j]; 

de sorte que « une copie privée est créée dans chaque tâche implicite (...) et est initialisé avec la valeur d'initialisation de la réduction -identifiant.Après la fin de la région, l'élément de liste d'origine est mis à jour avec les valeurs des copies privées en utilisant le combineur associé à l'identificateur de réduction "(http://www.openmp.org/wp-content/uploads/openmp-4.5.pdf). Notez que la réduction sur les tableaux en C est directement supportée par le standard depuis OpenMP 4.5 (vérifiez si le compilateur le supporte, sinon il y a d'anciennes façons manuelles de le réaliser, Reducing on array in OpenMp).

Cependant, le code donné, il devrait être probablement plus adéquat pour éviter la parallélisation de la boucle la plus interne de sorte que la réduction ne soit pas nécessaire du tout:

#pragma omp parallel 
    { 
     #pragma omp for collapse(2) 
     for(int i=0;i<n;i++) { 
      for(int j=0;j<n;j++) { 
       for(int k=0;k<n;k++) { 
        C[i][j]+=A[i][k]*B[k][j]; 

série peut être plus rapide que la version OpenMP pour petites tailles de matrices et/ou petit nombre de fils. Sur ma machine Intel en utilisant jusqu'à 16 cœurs, n = 1000, compilateur GNU V6.1 la pause même est d'environ 4 cœurs lorsque l'optimisation de -O3 est activée pendant la pause même est d'environ 2 noyaux en compilant avec -O0. Pour plus de clarté, je rapport, les performances mesurées: je

Serial  418020 
----------- WRONG ORIG -- +REDUCTION -- OUTER.COLLAPSE -- OUTER.NOCOLLAPSE - 
OpenMP-1 1924950  2841993  1450686   1455989 
OpenMP-2 988743  2446098   747333   745830 
OpenMP-4 515266  3182262   396524   387671 
OpenMP-8 280285  5510023   219506   211913 
OpenMP-16 2227567  10807828   150277   123368 

En utilisant la réduction de la perte de performance est spectaculaire (accélération inversée). La parallélisation externe (w ou w/o effondrement) est la meilleure option.

En ce qui concerne votre échec avec de grandes matrices, une raison possible est liée à la taille de la pile disponible. Essayez d'agrandir le système et les tailles de pile OpenMP, c'est-à-dire

ulimit -s unlimited 
export OMP_STACKSIZE=10000000 

Answer 2

La directive collapse peut en être responsable, car l'index j est recréé à l'aide de divide/mod operations.

Avez-vous essayé sans collapse?