Optimierung und warum openmp ist viel langsamer als der sequentielle Art und Weise?

Ich bin ein Neuling in der Programmierung mit OpenMp. Ich schrieb ein einfaches c-Programm zu multiplizieren matrix mit einem Vektor. Leider, durch den Vergleich der Ausführung Zeit habe ich festgestellt, dass die OpenMP ist viel langsamer als die Sequentielle Art und Weise.

Hier ist mein code (Hier wird die matrix N*N-int, vector int N, Ergebnis N long long):

#pragma omp parallel for private(i,j) shared(matrix,vector,result,m_size)
for(i=0;i<m_size;i++)
{  
  for(j=0;j<m_size;j++)
  {  
    result[i]+=matrix[i][j]*vector[j];
  }
}

- Und dies ist der code für sequentielle Weise:

for (i=0;i<m_size;i++)
        for(j=0;j<m_size;j++)
            result[i] += matrix[i][j] * vector[j];

Als ich versuchte, diese beiden Implementierungen mit einer 999x999 matrix und einem 999-Vektor, der Zeitpunkt der Ausführung ist:

Sequentiell: 5439 ms
Parallel: 11120 ms

Kann ich wirklich nicht verstehen, warum OpenMP ist viel langsamer als der sequentielle Algorithmus (über 2 mal langsamer!) Wer kann mein problem lösen?

Wie viele Kerne sind Sie mit OpenMP?
Wie Messen Sie die execution time? Verwenden Sie die gefürchtete clock() / CLOCKS_PER_SEC Methode?

InformationsquelleAutor Alex Zhou | 2013-05-04

2

Weil, wenn OpenMP-verteilt die Arbeit unter den threads gibt es eine Menge von Verwaltung/Synchronisierung gehen, um zu gewährleisten, dass die Werte in Ihrem gemeinsamen matrix und Vektor sind nicht irgendwie beschädigt. Auch wenn Sie schreibgeschützt sind: Menschen sehen, dass leicht, dein compiler kann nicht.

Dinge ausprobieren, die für pädagogische Gründe:

0) Was passiert, wenn matrix und vector sind nicht shared?

1) Parallelisieren der innere "j-loop" erste, halten Sie die äußere i-Schleife" serielle. Sehen, was passiert.

2) nicht erfassen die Summe in result[i], sondern in eine variable temp und weisen Sie dessen Inhalt result[i] nur nach dem die innere Schleife beendet ist, um zu vermeiden wiederholte index-lookups. Vergessen Sie nicht, init temp auf 0, bevor die innere Schleife beginnt.
- Vielen Dank für Ihre Antwort! obwohl die beiden ersten Lösungen waren nicht so nützlich, die Letzte hat zwar die Ausführungszeit zu 6838ms
- Froh, dass ich helfen konnte. Könnte man vielleicht teilen, die timings? Das könnte lehrreich sein für andere. Und vielleicht klicken Sie auf den Pfeil nach oben Links zu meinen Antworten 🙂
- Dies ist ein häufiges Missverständnis. Die meisten OpenMP-Implementierungen mit absolut nichts, um die zu schützen, die gemeinsame Variablen möglich, die Daten Rennen. Es ist der programmer ' s job um sicherzustellen, dass keine Rennen auftreten von ausdrücklich hinzufügen Synchronisations-primitive.
InformationsquelleAutor Laryx Decidua
14

Deinen code teilweise leidet unter dem sogenannten false-sharing, typisch für alle cache-kohärente Systeme. Kurz gesagt, viele Elemente der result[] array passen, in der gleichen cache-Zeile. Wenn thread i schreibt result[i] als Ergebnis der += Betreiber, die cache-line holding, die Teil der result[] schmutzig wird. Das cache-Kohärenz-Protokoll dann ungültig macht, alle Kopien der cache-line in den anderen Kernen, und Sie müssen aktualisieren Sie Ihre Kopie von der oberen level-cache oder aus dem Hauptspeicher. Als result ist ein array von long long, dann eine cache line (64 bytes auf x86) besitzt 8 Elemente und neben result[i] es gibt 7 andere array-Elemente in der gleichen cache-Zeile. Daher ist es möglich, dass zwei "benachbarten" Themen werden ständig kämpfen für den Besitz der cache-Zeile (unter der Annahme, dass jeder thread läuft auf einem separaten core).

Mindern false-sharing in deinem Fall die einfachste Sache zu tun ist, um sicherzustellen, dass jeder thread bekommt eine iteration block, dessen Größe teilbar ist durch die Anzahl der Elemente in der cache-Zeile. Zum Beispiel können Sie die schedule(static,something*8) wo something sollte groß genug sein, so dass die iteration Speicherplatz wird nicht zersplittert in zu viele Teile, aber in der gleichen Zeit, sollte es klein genug sein, so dass jeder thread bekommt einen block. E. g. für m_size gleich 999 und 4 threads ein, die Sie anwenden würde, die schedule(static,256) - Klausel, um die parallel for konstruieren.

Andere partielle Grund wird der code langsamer ausgeführt werden könnten, wenn OpenMP aktiviert ist, wird der compiler kann sich nur ungern gelten einige code-Optimierungen, die beim shared-Variablen werden zugeordnet. OpenMP bietet für die sogenannten relaxed memory-Modell, wo es erlaubt ist, dass der lokale Speicher der Blick auf eine gemeinsam genutzte variable in jedes Gewinde ist anders und die flush Konstrukt zur Verfügung gestellt, um die Synchronisierung der Ansichten. Aber Compiler in der Regel unter shared Variablen als implizit volatile wenn Sie nicht nachweisen können, dass andere threads keinen Zugriff auf desynchronised shared-Variablen. Ihr Fall ist einer von denen, da result[i] wird nur zugewiesen, und der Wert von result[i] wird nie durch andere threads. Im seriellen Fall würde der compiler wahrscheinlich erstellen Sie eine temporäre variable, um das Ergebnis der inneren Schleife und würde nur die Zuordnung zu result[i] sobald die innere Schleife fertig ist. Im parallelen Fall könnte es entscheiden, dass dies eine temporäre desynchronised Blick result[i] in die anderen threads und damit entscheiden, die nicht die Anwendung der Optimierung. Nur für das Protokoll, GCC 4.7.1 mit -O3 -ftree-vectorize hat die temporäre variable trick mit den beiden OpenMP aktiviert ist und nicht.
- Das ist ein sehr interessanter Kommentar @Hristo! Ich würde in der Regel Schleife über m_size/256 und der Sprung zu 256*i oder so etwas wie, dass anstelle der Verwendung von schedule(static,256). Ich werde versuchen, einige Ihrer Vorschläge in dieser Woche.
- Ich erzielte einige code als Antwort versuchen Ihren Vorschlag. Es macht für mich keinen Unterschied zum setzen der block Größe. Einstellen der block-Größe ist einer der Bereiche, in denen ich bin, am wenigsten mit mit OpenMP. Vielleicht ist es nicht sicher davon ausgehen, dass OpenMP verteilen die threads in einer Weise, die vermeidet, dass false-sharing im Allgemeinen und so ist es besser, legen Sie die Blockgröße selbst?
- Wie bei vielen anderen Fällen - es hängt davon ab. Einige Szenarien profitieren von der Einstellung einer bestimmten Blockgröße. In anderen Fällen ist die Voreinstellung ausreichend. In diesem speziellen Fall ist es unmöglich zu sagen, was ist der Grund für die Verlangsamung mit so wenig Informationen zur Verfügung gestellt von der OP.
- getan.
InformationsquelleAutor Hristo Iliev

Habe ich dies in Bezug auf Hristo Kommentar. Ich habe versucht, mit Zeitplan(statisch, 256). Für mich macht es nicht helfen, ändern Sie die Standard-chunck size. Vielleicht macht es sogar noch schlimmer. Ich druckte mir die thread-Anzahl und dem index mit und ohne Einstellung des Zeitplans und es ist klar, dass die OpenMP-schon wählt die thread-Indizes zu weit von einander, so dass false-sharing nicht scheinen ein Problem zu sein. Für mich ist dieser code gibt bereits einen guten Schub mit OpenMP.

#include "stdio.h"
#include <omp.h>

void loop_parallel(const int *matrix, const int ld, const int*vector, long long* result, const int m_size) {
    #pragma omp parallel for schedule(static, 250)
    //#pragma omp parallel for
    for (int i=0;i<m_size;i++) {
        //printf("%d %d\n", omp_get_thread_num(), i);
        long long sum = 0;
        for(int j=0;j<m_size;j++) {
            sum += matrix[i*ld +j] * vector[j];
        }
        result[i] = sum;
    }
}

void loop(const int *matrix, const int ld, const int*vector, long long* result, const int m_size) {
    for (int i=0;i<m_size;i++) {
        long long sum = 0;
        for(int j=0;j<m_size;j++) {
            sum += matrix[i*ld +j] * vector[j];
        }
        result[i] = sum;
    }
}

int main() {
    const int m_size = 1000;
    int *matrix = new int[m_size*m_size];
    int *vector = new int[m_size];
    long long*result = new long long[m_size];
    double dtime;

    dtime = omp_get_wtime();
    loop(matrix, m_size, vector, result, m_size);
    dtime = omp_get_wtime() - dtime;
    printf("time %f\n", dtime);

    dtime = omp_get_wtime();
    loop_parallel(matrix, m_size, vector, result, m_size);
    dtime = omp_get_wtime() - dtime;
    printf("time %f\n", dtime);

}

Die Standard-chunk-Größe für das statische loop-scheduling ist das Verhältnis zwischen der Anzahl der Iterationen und die Anzahl der threads. Wie false-sharing wirkt sich auf die Ausführungszeit hängt auch von der Arbeit in Bezug auf die Größe der "collision-domains" (also freigegebene cache-Zeilen). Die Berechnungen hier sind zu einfach und die Anzahl der Iterationen zu klein ist, um zu beurteilen, wenn unterschiedliche chunk-Größe " hat keine Auswirkungen. Auch Sie Messen den overhead für das erzeugen der ersten parallelen region unterschiedlich. Rufen Sie loop_parallel zweimal mit den gleichen Argumenten und Messen nur die zweite Aufruf.
Wenn Sie dies ausführen, und ändern Sie die Reihenfolge der Funktionen, die zweite Funktion wird fast immer schneller fertig.

InformationsquelleAutor

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.