High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen52
MPI und OpenMP• in HPC Anwendungen findet man immer häufiger auch den
gemeinsamen Einsatz von MPI und OpenMP:– OpenMP wird zur thread-parallelen Implementierung des Codes auf
einem einzelnen Rechenknoten (z.B. SMP) eingesetzt– mit Aufruf geeigneter Funktionen aus der MPI-Bibliothek wird die
Kommunikation zwischen den auf den verschiedenen Rechenknoten laufenden parallelen Prozessen implementiert
– MPI-Bibliothek muss hierzu thread-sicher sein (z.B. Sun MPI)!
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen53
Automatische Parallelisierung• Idee: Compiler extrahiert automatisch die Parallelität aus einem
sequentiellem Programm und generiert eine thread-basierteparallele Implementierung
• Ansatz: In den meisten HPC-Anwendungen wird die meiste Rechenzeit für (geschachtelte) Schleifen benötigt
Ist auch eine automatische Parallelisierung von Schleifen durch Compiler möglich ?
• Stand der heutigen Compilertechnik:– Analyse von Datenabhängigkeiten in Schleifen zur Erkennung von sicher
parallelisierbaren Schleifen– Generierung von parallelem Code für einfache Schleifen mit Barrieren-
Synchronisation am Schleifenende– einige einfache Code-Transformationen werden zur Erhöhung der Anzahl
parallelisierbarer Schleifen durchgeführt
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen54
Automatische Parallelisierung (Forts.)• Einfache Schleifen (d.h. ohne Index-Abhängigkeiten zwischen
Iterationen) lassen sich gut automatisch parallelisieren, z.B.:for (i=0 ; i<N ; i++)for (j=0 ; j<M ; j++)a[i][j] = b[i][j] * c[i][j];
oder:for (i=0 ; i<N/2 ; i++)for (j=0 ; j<M/2 ; j++)a[2*i][2*j+1] = a[2*i][2*j+1] + b[3*i][j+2];
oder:for (i=1 ; i<N/2 ; i++)a[2*i] = 0.5 * (a[2*i-1] + a[2*i+1]);
• automatische Parallelisierung z.B. auf Sun durch Aufruf voncc –fast –xautopar –xloopinfo <file>.c –o file
und Setzen der Umgebungsvariablen PARALLEL auf den gewünschten Parallelitätsgrad
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen55
Automatische Parallelisierung (Forts.)• Probleme entstehen bei automatischer Parallelisierung z.B. durch
– Schleifen mit Index-Abhängigkeiten zwischen Iterationen:for (i=1 ; i<N ; i++)a[i] = a[i-1] + b;
oder:for (i=0 ; i<N-2 ; i++) {a[i] = b[i] * c;b[i] = a[i+2] * d;
}
– Schleifen mit Funktionsaufrufen:for (i=0 ; i<N ; i=i+incr(i))a[i] = a[i] + b[i] * c;
oder:for (i=0 ; i<N ; i=i++)a[i] = a[i] + compute(a,b,i);
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen56
Automatische Parallelisierung (Forts.)– auf Zeiger basierende Schleifen:
for (i=min ; i<max ; i++)*p++ = *q--;
– Schleifen mit auf Feldern basierenden Indexausdrücken:for (i=0 ; i<N ; i++)
a[p[i]] = a[q[i]] + b[p[i]] + c;
– Schleifen mit mehreren datenabhängigen Ausgängen:for (i=0 ; i<N ; i++) {if (b[i] == 0) break;a[i] = a[i] / b[i];
}
– Schleifen mit indexabhängigen Bedingungen:for (i=0 ; i<N ; i++)for (j=0 ; j<M ; j++) if (j > i) a[i][j] = a[i][j] + b[i][j] * c;
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen57
Automatische Parallelisierung (Forts.)– Schleifen mit (eventuell versteckten) Reduktionen:
for (i=0 ; i<N ; i++) {y = x + 0.5 * a[i];x = y + 2 * b[i];
}
– Schleifen mit skalaren Werten:for (i=0 ; i<N ; i++) {t = a[i];a[i] = b[i];b[i] = t;
}
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen58
Automatische Parallelisierung (Forts.)• einige Probleme lassen sich (zumindest in einfachen Fällen)
durch Code-Transformationen lösen, z.B. indem– skalare Variablen durch Feldvariablen ersetzt werden – Variablen in Schleifen umbenannt werden– Anweisungen oder Funktionen eingesetzt werden („Inlining“)– Reduktionen von Vektoren automatisch erkannt und durch Aufrufe von
parallelen Reduktionsfunktionen ersetzt werden(z.B. auf Sun möglich durch Angabe der zusätzlichen Option –xreduction)
• eine weitere Leistungssteigerung kann erreicht werden, indem– bei geschachtelten Schleifen innere und äußere Schleife vertauscht werden,
um z.B. Parallelitätsgrad oder Anzahl paralleler Berechnungen zu erhöhen– Schleifen automatisch entrollt werden– mehrere kleine Schleifen mit identischem Indexbereich zusammengefasst
werden
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen59
Automatische Vektorisierung• bei der automatischen Vektorisierung wird aus Schleifen ein
Code für Vektorprozessoren oder Vektoreinheiten generiert:– in geschachtelten Schleifen wird stets nur die innere Schleife vektorisiert– Schleifeniterationen müssen unabhängig sein– nur einfache Zugriffsmuster auf Feldelemente gestattet– die N Iterationen einer Schleife werden derart in Streifen unterteilt, dass
die Zahl k der Feldelemente je Streifen in ein Vektorregisters passt(ggf. Sonderbehandlung für die letzten Iterationen erforderlich, wenn N keinVielfaches von k ist)
– Beispiel: Gegeben sei ein Prozessor mit 128-Bit Vektorregister und eine Schleife mit den float Vektoren a, b und cvor der Vektorisierung: for (i=0; i<N; i++)
c[i] = a[i] * b[i]
nach der Vektorisierung: for (i=0; i<N; i++)c[i:i+3] = a[i:i+3] * b[i:i+3]
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen60
Automatische Vektorisierung (Forts.)• Intel C/C++ Compiler kann ab Version 7.0 automatisch Code für
die Vektoreinheiten MMX, SSE und SSE2 des Intel Pentium 4 Prozessors generieren– Aufruf erfolgt z.B. mit: icc –xW –vec_report3 prog.c
– in aufeinanderfolgenden Iterationen dürfen nur Zugriffe auf benachbarteFeldelemente erfolgen (d.h. mit stride = 1)
– Compiler kann effizienteren Code generieren, wenn Daten auf 16-ByteGrenzen ausgerichtet sind
– es können sowohl for als auch while Schleifen vektorisiert werden; sie dürfen jedoch nur einen Eintritts- und einen Ausgangspunkt aufweisen
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen61
High Performance FORTRAN (HPF)• im Jahre 1993 vom HPF Forum entwickelter Standard als
Ergänzung zu FORTRAN 90• Ziel: architekturunabhängige parallele Programmierung• FORTRAN ermöglicht einfachere Parallelisierung als C, da
– keine Zeiger vorhanden sind– i.a. keine dynamischen Datenstrukturen unterstützt werden
• HPF gestattet explizite datenparallele Programmierung durch– Datenstrukturen (Arrays) für mehrdimensionale Datenfelder– parallele Ausführung auf Feldkomponenten mittels FORALL:
FORALL (I=2:N-2:2, J=1:M) A(I,J) = B(I-1,J)+C(I+1,J)oder durch eine parallele Zuweisung:M(1:N,7) = 0.5
– zusätzliche INDEPENDENT-Direktive zur Kennzeichnung konfliktfrei parallel ausführbarer Schleifen
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen62
HPF (Forts.)einige zentrale Ideen von High Performance FORTRAN:• Definition von Indexräumen („index templates“):
!HPF$ TEMPLATE t(1:100,1:100)
• Angabe des Alignments von Feldern zu Indexräumen oder anderen Feldern:!HPF$ ALIGN A(I,J) WITH t(J,I)!HPF$ ALIGN B(I,J) WITH t(2*I,2*J)
• zusätzliche Layout-Direktive geben an, wie einzelne Index-Dimensionen auf p Prozessoren verteilt (d.h. partitioniert) werden:REAL A(100,100), B(50,50), C(100,100,2)!HPF$ DISTRIBUTE t(BLOCK,*), C(CYCLIC,BLOCK,*)
mit– BLOCK : Datenelement i wird auf Prozessor i DIV p abgebildet– CYCLIC : Datenelement i wird auf Prozessor iMOD p abgebildet– * : Elemente dieser Dimension werden nicht verteilt
• zur Laufzeit Reorganisation der Daten möglich:REDISTRIBUTE bzw. REALIGN (Syntax wie DISTRIBUTE und ALIGN)
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen63
HPF (Forts.)• parallele implizite Kommunikation über Indexausdrücke:
FORALL (I=1:100) A(I,2) = C(I,5,1)
• viele eingebaute Kommunikationsfunktionen: SUM, TRANSPOSE, ...• HPF unterstützt mehrdimensionale virtuelle Prozessortopologien,
Beispiel: Matrix-Multiplikation in HPFREAL*4, DIMENSION(1000,1000) :: A,B,C!HPF$ PROCESSORS GRID(2, 2)!HPF$ DISTRIBUTE C(BLOCK,BLOCK) onto GRID!HPF$ ALIGN A(I,J) WITH C(I,*)!HPF$ ALIGN B(I,J) WITH C(*,J)INTEGER :: I,J,K
DO I = 1, 1000DO J = 1,1000DO K = 1,1000C(I,J) = C(I,J) + A(I,K) * B(K,J)
END DOEND DO
END DO
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen64
Java• und Java?
– höherer Speicherbedarf (ca. 5-fach im Vgl. zu C)– geringere Geschwindigkeit (ca. 25-100% langsamer im Vgl. zu C) durch
• Teilinterpretation des Codes mittels Just-in-time Übersetzer• Probleme bei Gleitkomma-Anwendungen durch Forderung nach exakter
Reproduzierbarkeit von Ergebnissen – genauere Zwischenergebnisse in FPU müssen vor jeder Folgeoperation auf
das von Java vorgeschriebene Zahlenformat gerundet werden!– Verbot von Multiply&AddMaschinenbefehlen
• ineffiziente interne Realisierung von mehrdimensionalen Feldern
– schlechtere Lesbarkeit von Programmen (kein Überladen von Operatoren)Threads sind bereits fester Bestandteil der Sprache:
• Starten eines Threads durch Instantiierung eines Objekts von der Klasse Thread und Aufruf der Methode start()
• gegenseitiger Ausschluss durch Schlüsselwort synchronized
High Performance Computing, SS 2004A. Strey, Universität Ulm
Kapitel 3 : Programmierung von HPC-Systemen65
Java (Forts.)• das Java Grande Forum (www.javagrande.org) versucht,
eine zum Einsatz in HPC Anwendungen besser geeignete Java-Umgebung zu definieren, z.B. durch
neue Schlüsselworte strictfp und fastfp
neue Klassen für mehrdimensionale FelderFestlegen einer Schnittstelle für MPI
• zukünftige Bedeutung von Java für HPC unklar!