MPI und OpenMP - Universität · PDF fileHigh Performance Computing, SS 2004 A. Strey, Universität Ulm Kapitel 3 : Programmierung von HPC-Systemen 52 MPI und OpenMP • in

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)!



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



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



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



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;



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;

}



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



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]



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 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



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)



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



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



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!

Documents

MPI und OpenMP - Universität · PDF fileHigh Performance Computing, SS 2004 A. Strey, Universität Ulm Kapitel 3 : Programmierung von HPC-Systemen 52 MPI und OpenMP • in