OpenMP-Parallelisierung der Matrixmultiplikation durch eine dreifache for-Schleife (performance-Problem)

Ich Schreibe ein Programm für die matrix-Multiplikation mit OpenMP, dass, für den cache die Bequemlichkeit, implementiert die Multiplikation A x B(transponiert) Zeilen X Zeilen anstelle der klassischen A-x B Zeilen x Spalten, für eine bessere cache-Effizienz. Dies zu tun, vor denen ich Stand, eine interessante Tatsache für mich ist das illogic: wenn in diesem code habe ich parallelisieren der extern-Schleife das Programm ist langsamer als wenn ich die OpenMP-Anweisungen in der innersten Schleife, in meinem computer die Zeiten sind 10.9 vs 8,1 Sekunden.

//A and B are double* allocated with malloc, Nu is the lenght of the matrixes 
//which are square

//#pragma omp parallel for
for (i=0; i<Nu; i++){
  for (j=0; j<Nu; j++){
    *(C+(i*Nu+j)) = 0.;
#pragma omp parallel for
    for(k=0;k<Nu ;k++){
      *(C+(i*Nu+j))+=*(A+(i*Nu+k)) * *(B+(j*Nu+k));//C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
  }
}

Von tweaking omp Parameter habe ich 200% Geschwindigkeit auf meiner Maschine. original: llcomp.googlecode.com/hg/examples/mxm.c Strom: codepad.org/nSfZHp03
Schöne Lösung. Ja, OpenMP, ist ein bischen tricky
Code, der verwendet 'fortran' Speicher-layout für die B matrix läuft 4-8 schneller (der größte Vorteil) für 1000x1000-Matrizen (Gewinde-version nimmt 0.5 Sekunden). gist.github.com/790865
Haben Sie schätzt Ihren Gflops/s? Sollte es 2.0*n^3/Zeit. Vergleichen Sie das mit den max für deine CPU: Häufigkeit * (SIMD_width)* (2 ILP) * (Anzahl der Kerne). e.g auf meinem 2600k ist (4GHz) * 4(AVX) * 2 (ILP) * 4 Kerne = 128 DP-Gflops/s. Wahrscheinlich, Ihr Wirkungsgrad ist weniger als 10%.

InformationsquelleAutor sdffadsf | 2011-01-18

4

Versuchen zu schlagen, die dadurch weniger Häufig. Dies bedingt eine cacheline-sharing und verhindert, dass der Betrieb parallel laufen. Verwenden eine lokale variable, sondern erlauben die meisten der schreibt in den einzelnen Kern-L1 cache.

Auch, die Verwendung von restrict helfen kann. Ansonsten der compiler kann nicht garantieren, dass schreibt C ändern sich nicht A und B.

Versuchen:
```
for (i=0; i<Nu; i++){
  const double* const Arow = A + i*Nu;
  double* const Crow = C + i*Nu;
#pragma omp parallel for
  for (j=0; j<Nu; j++){
    const double* const Bcol = B + j*Nu;
    double sum = 0.0;
    for(k=0;k<Nu ;k++){
      sum += Arow[k] * Bcol[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
    Crow[j] = sum;
  }
}
```
Außerdem denke ich, Elalfer ist Recht Geschehnissen zu reduzieren, wenn Sie parallelisieren, wird die innerste Schleife.
- danke für die Antwort, ich werde es versuchen dann werde ich wieder kommen
- Incredibile, die Zeit wurde nur 4,2 s mit der innersten Schleife und 4.4 mit den meisten äußeren (!), während der code mit #pragma wie in dem code, den Sie geschrieben Zeit >17, ich weiß nicht, warum. vielen Dank wirklich an alle, auch wenn Sie nicht verstehen, warum mit den meisten äußeren ist etwas langsamer als die meisten inneren
- Überprüfen Sie die Ergebnisse, Sie haben nicht die richtige Ausgabe, wenn die Parallelisierung der innersten Schleife, ohne Angabe einer Reduktion operation.
- ja, du hast Recht, auch auf dieser. Ich beging mehrere Fehler während des Programms, und Ihre Vermutung ist richtig, mit der Senkung der inneren Werke (4,2 s), aber die meisten äußeren ist das effizienter (3,9 s!), während die zentrale ist sehr langsam, etwa 20, ich denke, dies ist aufgrund der cacheline (die Adresse variiert bei mir sehr schnell), so das scheinbare Paradoxon offenbart, morgen habe ich die Prüfung auf wissenschaftlichen Programmierung...nochmals vielen Dank an Sie und Elalfer
- es ist ein Tippfehler in Bcol = B + i*Nu es sollte j.
- Danke, behoben.
InformationsquelleAutor Ben Voigt
4

Könnten Sie wahrscheinlich einige Abhängigkeiten in den Daten, wenn Sie parallelisieren der äußeren Schleife und der compiler ist nicht in der Lage, um es herauszufinden, und fügt zusätzliche sperren.

Wahrscheinlich entscheidet, dass unterschiedliche äußere schleifendurchläufe schreiben konnte, in der gleichen (C+(i*Nu+j)) und es fügt access-sperren zu schützen.

Compiler könnte wahrscheinlich herausfinden, dass es keine Abhängigkeiten gibt, wenn Sie werden parallelisieren, die 2. Schleife. Aber herauszufinden, dass es keine Abhängigkeiten gibt, die Parallelisierung der äußeren Schleife ist nicht so trivial für einen compiler.

UPDATE

Einige performance-Messungen.

Hallo, mal wieder. Es sieht aus wie 1000 Doppelzimmer * und + ist nicht genug, um die Kosten zu decken von threads-Synchronisation.

Ich habe getan, einige kleine tests und einfache Vektor-Skalar-Multiplikation ist nicht wirksam, mit der openmp-es sei denn, die Anzahl der Elemente ist weniger als ~10'000. Im Grunde größer das array ist, mehr Leistung bekommst du von der Verwendung von openmp.

So Parallelisierung der innersten Schleife müssen Sie separate Aufgabe zwischen verschiedenen threads und sammeln Daten wieder 1'000'000 mal.

PS. Versuchen Sie, Intel ICC, es ist ein bisschen frei für Studenten und open-source-Projekte. Ich erinnere mich, dass mit openmp für die kleineren, die 10'000-Elemente-arrays.

UPDATE 2: Reduzierung Beispiel
```
    double sum = 0.0;
    int k=0;
    double *al = A+i*Nu;
    double *bl = A+j*Nu;
    #pragma omp parallel for shared(al, bl) reduction(+:sum)
    for(k=0;k<Nu ;k++){
        sum +=al[k] * bl[k]; //C(i,j)=sum(over k) A(i,k)*B(k,j)
    }
    C[i*Nu+j] = sum;
```
- hat die Schleife nicht durchgeführt Abhängigkeit, alle Iterationen sind unabhängig
- Sie können es sehen, aber der compiler ist nicht ein AI und konnte es vermissen 😉 ich bin eigentlich hatten viele Schlachten mit OpenMP & icc in Bezug auf dieses Zeug.
- sorry für meine Arroganz, Sie werden sicher mehr Experte als ich, ich werde zu prüfen. Wenn ich das parallelisieren der zweiten Schleife das Ergebnis ist mehr als 15 Sekunden.
- Ein Hinweis: Haben Sie versucht, zu verwenden reduction - Klausel für die innere Schleife? Ich werde versuchen, diesen code später. Es sieht aus wie Spaß, sich zu erinnern, wie die Arbeit mit OpenMP. Welche compiler verwenden Sie? gcc oder icc? Und was ist die Größe der matrix?
- wenn Sie wollen, kann ich Ihnen meinen code.Die matrix ist ein großer (1000x1000). Ich sehe keinen Raum zu nutzen-Reduktion (C ist ein Zeiger), in die äußere Schleife, die Sie verwenden können nicht in jedem Fall (auf das, was Sie reduct?). Das problem ist, dass ich nicht bin ein computer-Ingenieur, ich weiß nicht, wie die computer-Speicher "arbeitet" in einem physischen Weg, ich weiß, wie die cache-Zeile, und wie Sie sehen können habe ich, dass Informationen, die für die Vermehrung Zeilen x Zeilen, aber mein wissen endet hier. Für mich ist das problem in der Nutzung von cache, nur dieses Features können Sie die ganze Zeit ausführen. Danke für die Antwort, ich freue mich für Ihre Ideen
- ich bin mit gcc auf ubuntu, aber ich habe versucht auch mit visualstudio Professional auf windows
- danke für Eure Vorschläge, ich wirklich zu schätzen.
- Wie ich sehe sind Sie neu hier. Nur vergessen Sie nicht, Abstimmung für die Antworten, die Sie möchten, um danke zu sagen. Als auch die Stimme für gute Fragen 😉
- Wie haben Sie die Zeit Messen, die Differenz? Mit omp_get_wtime() ?
- Ich hätte einfach verwendet time ./bin. Es war vor 6 Jahren 😉
InformationsquelleAutor Elalfer

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.