Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
se:parallelrechner [2009-01-01 16:16] stefan |
se:parallelrechner [2009-01-19 16:07] stefan |
||
---|---|---|---|
Zeile 9: | Zeile 9: | ||
* Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln | * Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln | ||
* Leistungsbewertung (Gesetze Amdahl etc.) | * Leistungsbewertung (Gesetze Amdahl etc.) | ||
- | * keine virtuellen Topologien | ||
* OpenMP eher allgemein (Kombination mit MPI) | * OpenMP eher allgemein (Kombination mit MPI) | ||
- | * Matrizenrechnung fliegt raushttp://wiki.stefan-macke.com/doku.php/se:parallelrechner | ||
* Bibliotheken für Parallelrechner nur oberflächlich | * Bibliotheken für Parallelrechner nur oberflächlich | ||
* Leseempfehlung | * Leseempfehlung | ||
* Gesetze Amdahl etc. | * Gesetze Amdahl etc. | ||
* MPI-Standard | * MPI-Standard | ||
+ | * NICHT | ||
+ | * virtuellen Topologien | ||
+ | * Matrizenrechnung | ||
+ | * Lehrbrief ist erlaubt! | ||
- | Lehrbrief ist erlaubt! | + | ===== Einstieg in Parallelrechner ===== |
+ | * Arten von Parallelrechnern | ||
+ | * Symmetrische Multiprozessorsysteme (SMP): übliche Rechner mit mehreren Prozessoren (auch die heutigen MultiCore-PCs) | ||
+ | * Rechner-Cluster: übliche Rechnerknoten verbunden über ein überdurchschnittlich schnelles Netzwerk, keine direkte Eingabemöglichkeit sondern Zugang über Eingangsknoten | ||
+ | * Vernetzte Workstations (NOW): übliche Workstations, die einen ad-hoc Paralllelrechner mit begrenzter Leistung bilden | ||
+ | * Grids: Internet-basierter Zusammenschluss verteilter Rechner (z.B. SETI) | ||
+ | * die meisten Parallelrechner laufen unter Linux und verwenden Standard-APIs für die Programmierung (MPI, OpenMP, ScaLAPACK) | ||
+ | |||
+ | ===== Architekturen und Klassifizierungen von Parallelrechnern ===== | ||
+ | * Speichergekoppelt / shared memory | ||
+ | * {{:se:speichergekoppelteparallelrechner.jpg|}} | ||
+ | * alle Prozessoren müssen den gemeinsamen Speicher über das Verbindungsnetz ansprechen -> Flaschenhals | ||
+ | * 1 Adressraum, n Prozessoren (durch VN begrenzt), alle Speicherzugriffe über das VN (braucht also hohe Bandbreite) | ||
+ | * Programmierung: Parallelsprachen oder parallele Spracherweiterungen, OpenMP, normale Threads | ||
+ | * Nachrichtengekoppelt / message passing | ||
+ | * {{:se:nachrichtengekoppelteparallelrechner.jpg|}} | ||
+ | * viele Prozessoren möglich, VN mit geringer Bandbreite, skalierbar, anwendbar für Cluster/NOW | ||
+ | * n Adressräume, n Prozessoren, Nachrichtenaustausch über VN | ||
+ | * Programmierung: Standardsprachen mit Bibliotheken für Nachrichtenaustausch (MPI) | ||
+ | * Hybridlösungen | ||
+ | * {{:se:hybridparallelrechner.jpg|}} | ||
+ | * Beispiel: verteilter gemeinsamer Speicher, Speicherzugriff außerhalb des eigenen Moduls erfolgt über VN | ||
+ | * Klassifikation nach Flynn | ||
+ | * SISD: ein Befehlsstrom, ein Datenstrom (normaler PC), ein Befehl verarbeitet einen Datensatz (herkömmliche Rechnerarchitektur eines seriellen Rechners) | ||
+ | * SIMD: ein Befehlsstrom, mehrere Datenströme (Cray, Vektorrechner), ein Befehl verarbeitet mehrere Datensätze, z.B. n Prozessoren führen zu einem Zeitpunkt den gleichen Befehl aber mit unterschiedlichen Daten aus | ||
+ | * MISD: mehrere Befehlsströme, ein Datenstrom (praktisch keine), mehrere Befehle verarbeiten den gleichen Datensatz (diese Rechnerarchitektur ist nie realisiert worden) | ||
+ | * MIMD: mehrere Befehlsströme, mehrere Datenströme (Merhprozessorsysteme und verteilte Systeme), unterschiedliche Befehle verarbeiten unterschiedliche Datensätze (dies ist das Konzept fast aller modernen Parallelrechner) | ||
+ | * SPMD und MPMD | ||
+ | * MPMD: Multiple Program, multiple Data (jeder Prozessor führt sein eigenes Programm aus, Master verteilt Arbeit an Worker) | ||
+ | * SPMD: Single Program, multiple Data (ein einziges Programm enthält Abschnitte für Master und Worker) | ||
+ | * Vor-/Nachteile | ||
+ | * SPMD: größere Portabilität, einfacher zu verwalten, viele MPMD-Programme können als SPMD-Programme formuliert werden. | ||
+ | * MPMD: größere Flexibilität, schwieriger zu verwalten | ||
+ | * Zugriffsweise auf den Speicher | ||
+ | * Uniform Memory Access: gleichförmiger Speicherzugriff (Tanzsaal-Architektur) | ||
+ | * Non-Uniform Memory Access: ungleichförmiger Speicherzugriff (z.B. lokaler Cachespeicher und globaler Speicher, Cray) | ||
+ | * Cache-Only Memory Access: nur Cache-Zugriffe | ||
+ | * No Remote Memory Access: nur lokale Speicherzugriffe (Grid, NOW) | ||
+ | * Parallelisierungsstrategien | ||
+ | * Gebietszerlegung (engl. domain decomposition) | ||
+ | * Funktionale Aufteilung (engl. functional decomposition) | ||
+ | * Verteilung von Einzelaufträgen (engl. task farming) | ||
+ | |||
+ | ===== Statische Verbindungsnetze ===== | ||
+ | * {{:se:statischeverbindungsnetze.jpg|}} | ||
+ | * Verbindungsstrukturen bestehen aus festen Links zwischen Rechnern | ||
+ | * regelmäßige Strukturen werden bevorzugt | ||
+ | * einfacheres Routing | ||
+ | * Symmetrie -> leichter verständlich, leichtere Entwicklung, Prozessoren lassen sich leichter tauschen | ||
+ | * Modularität -> leichter erweiterbar und umformbar | ||
+ | * Metriken | ||
+ | * Distanz zwischen zwei Knoten: das Minimum aller Pfadlängen zwischen dem betrachteten Knotenpaar | ||
+ | * Durchmesser: die größtmögliche Distanz in einem Graphen | ||
+ | * Halbierungsbreite: Mindestanzahl der Kanten, die entfernt werden müssen, damit ein Graph in zwei gleichgroße Hälften zerfällt | ||
+ | * typische Netzwerke | ||
+ | * Ring | ||
+ | * Baum | ||
+ | * Fat Tree | ||
+ | * Gitter ohne/mit Wraparound | ||
+ | * Hyperkubus (N = 2<sup>k</sup>) | ||
+ | * wenn k um 1 inkrementiert wird, verdoppelt sich die Knotenzahl und die alten Knoten erhalten ein zusätzliches Bit 0 (die neuen 1) und werden mit den entsprechenden neuen Knoten verbunden | ||
+ | * vollständige Vernetzung | ||
+ | * Stern | ||
+ | * Skalierbarkeit und Emulation | ||
+ | * Was ist das kleinste Netzinkrement, das hinzugefügt werden muss, um das nächstgrößere Netz der gleichen Topologie zu erhalten? | ||
+ | * Wie ist die Abhängigkeit der Effizienz einer Topologie von der Knotenzahl? | ||
+ | * Emulation: Abbildung eines Gastgraphen G auf einen Wirtsgrafen H, bei der alle Knoten von G auf Knoten von H zum Liegen kommen. Jede Kante von G wird auf eine oder mehrere Kanten von H abgebildet. | ||
+ | * Beispiele: Ring im 2D-Torus, Baum im Gitter, Gitter im Hyperkubus | ||
+ | * Verlangsamung durch Emulation | ||
+ | * Knotenlast: die größte Zahl der Gastknoten, die auf einem Wirtsknoten zu liegen kommen | ||
+ | * Dilatation: die Länge des längsten Pfades in H, auf den eine beliebige Kante von G abgebildet wird | ||
+ | * Andrang/Kantenlast: die größte Zahl der Kanten von G, die auf dieselbe Kante in H abgebildet werden | ||
+ | * Beispiele für Dilatation 1: Gitter -> Hyperkubus, Ring -> Gitter | ||
+ | |||
+ | ===== Dynamische Verbindungsnetzwerke ===== | ||
+ | * Verbindungsarten | ||
+ | * Leitungsvermittlung: eine physikalische Verbindung wird für die Dauer der gesamten Übertragung zugewiesen | ||
+ | * Paketvermittlung: ein Paket wird an das VN abgegeben und von diesem über Zwischenknoten an den Zielknoten übertragen | ||
+ | * Routing-Strategien | ||
+ | * Store-and-Forward: jeder Zwischenknoten speichert die Nachricht vollständig, bevor sie dem nächsten Knoten übergeben wird (Übertragungszeit ist proportional zur Knotenzahl) | ||
+ | * Cut-Through: Nachrichten werden in Teile gespalten und sofort weitergeschickt (Knoten müssen gleichzeitig senden und empfangen können) | ||
+ | * Wormhole: Nachricht wird in kleine Teile (Flits, 1-2 Byte) zerteilt und zunächst wird nur der Kopf der Nachricht verschickt, wenn dieser den Knoten verlässt, wird der Rest der Nachricht angefordert | ||
+ | * Vergleich | ||
+ | * Latenz wächst bei SaF mit Knotenzahl, dafür wird Netz nicht belastet, da Knoten sofort wieder zur Verfügung stehen | ||
+ | * beim Wormhole werden die Knoten lange blockiert und es kann zu Deadlocks kommen, allerdings bleibt die Latenz mit steigender Knotenzahl konstant | ||
+ | * typische dynamische Verbindungsnetze | ||
+ | * Merkmale | ||
+ | * Bandbreite (Bits/s) | ||
+ | * Latenzzeit (Verzögerung erster Bit zwischen Sender und Empfänger) | ||
+ | * Fehlertoleranz | ||
+ | * Skalierbarkeit | ||
+ | * einstufig: Bus, Crossbar, Shuffle | ||
+ | * mehrstufig: Banyan, Benes, CLOS | ||
+ | * Bus: höchstens 1 Eingang wird zu allen Ausgängen durchgeschaltet -> sehr verbreitet aber auf kleine Teilnehmerzahl beschränkt | ||
+ | * Crossbar: ermöglicht gleichzeitige Kommunikation zwischen verschiedenen Teilnehmerpaaren | ||
+ | * Shuffle: vereinfachter Crossbar mit eingeschränkten Steuereingängen | ||
+ | * Shuffle mit Broadcast-Erweiterung: zusätzliches Broadcast-Bit zur Erweiterung der Schaltfunktion (1 Eingang -> 2 Ausgänge) | ||
+ | * Banyan: Shuffle in Grundschaltung in mehreren Ebenen, Blockierungen sind möglich | ||
+ | * CLOS: besteht aus Crossbars | ||
+ | |||
+ | ===== Grundbegriffe der Leistungsbewertung ===== | ||
+ | * T<sub>comp</sub> Rechenzeit, T<sub>comm</sub> Kommunikationszeit, T<sub>ser</sub> Ausführungszeit der seriellen Programmversion, T<sub>par</sub> Ausführungszeit der parallelen Programmversion, n Anzahl Knoten | ||
+ | * Granularität: Länge der seriellen Codeabschnitte zwischen Kommunikations- und Synchronisationsbefehlen | ||
+ | * computation / communication ratio: T<sub>comp</sub> / T<sub>comm</sub> | ||
+ | * Beschleunigung: S(n) = T<sub>ser</sub> / T<sub>par</sub> | ||
+ | * Effizienz: S(n) / n | ||
+ | * Kosten: n * T<sub>par</sub> | ||
+ | * Gesetz von Amdahl: S(n) = (s + p) / (s + p/n) | ||
+ | * geht von einem konstanten seriellen Anteil im Programm aus -> Grenze für Speedup, nicht-skalierbare Anwendungen | ||
+ | * Die Verbesserung der Leistung des Gesamtsystems durch Verbesserung einer Komponente ist limitiert durch den Umfang der Verwendung der Komponente. | ||
+ | * Gesetz von Gustavson-Barsis: S<sub>s</sub>(n) = n + (1 - n) s | ||
+ | * geht von einer konstanten Laufzeit des seriellen Anteils im Programm aus -> skalierbare Anwendungen, können bei wachsendem Problem mit mehr Prozessoren ausgestattet werden | ||
+ | * Verbesserung der Genauigkeit/Problemgröße eines parallelen Verfahrens durch Steigerung der Prozessorzahl bei gleich bleibender Ausführungszeit | ||
+ | |||
+ | ===== Nachrichtenaustausch ===== | ||
+ | * Nachrichten werden zwischen den Prozessen verschickt, indem der Absender diese in einen Umschlag mit Empfänger und Sender verpackt und ggfs. mit einem Tag versieht | ||
+ | * Prozesserzeugung | ||
+ | * statisch: alle Prozesse werden vor der Ausführung spezifiziert | ||
+ | * dynamisch: neue Prozesse können während der Ausführung anderer Prozesse erzeugt werden (z.B. Master-Worker-Struktur) | ||
+ | * ein Prozess versendet eine Nachricht, indem er | ||
+ | * den/die Empfänger nennt | ||
+ | * den Wert (Adresse und Datentyp) bereitstellt | ||
+ | * optional die Nachricht mit einem Tag versieht | ||
+ | * ein Prozess empfängt eine Nachricht, indem er | ||
+ | * den Absender nennt (exakt oder beliebiger Absender) | ||
+ | * den Typ der Daten und die Zieladresse nennt | ||
+ | * optional einen Tag angibt (z.B. "dringend") | ||
+ | * synchroner/blockierender Nachrichtenaustausch | ||
+ | * erst Send oder erst Receive möglich | ||
+ | * Prozesse warten, bis die Nachricht übertragen wurde (und blockieren solange) | ||
+ | * asynchroner/nicht blockierender Nachrichtenaustausch | ||
+ | * Empfänger kann ein IRecv absetzen und später mit Wait schauen, ob die Nachricht angekommen ist | ||
===== Online-Kurs ===== | ===== Online-Kurs ===== | ||
Zeile 153: | Zeile 286: | ||
* Management und Abfragen der Umgebung: initialisieren und beenden von Prozessen, Rangermittlung | * Management und Abfragen der Umgebung: initialisieren und beenden von Prozessen, Rangermittlung | ||
+ | ==== MPI Programmstruktur ==== | ||
+ | * grundsätzlicher Aufbau von MPI-Programmen <code>include MPI header file | ||
+ | variable declarations | ||
+ | initialize the MPI environment | ||
+ | ...do computation and MPI communication calls... | ||
+ | close MPI communications</code> | ||
+ | * MPI-Funktionsnamen beginnen immer mit ''MPI_'' und haben ''int'' als Rückgabewert (sollte ''MPI_SUCCESS'' sein) | ||
+ | * Liste aller MPI-Konstanten: http://www.netlib.org/utk/papers/mpi-book/mpi-book.html | ||
+ | * MPI-Datentypen einer Send-/Receive-Kombination müssen übereinstimmen | ||
+ | * MPI-Standarddatentypen: ''MPI_CHAR'', ''MPI_SHORT'', ''MPI_INT'', ''MPI_LONG'', ''MPI_UNSIGNED_CHAR'', ''MPI_UNSIGNED_SHORT'', ''MPI_UNSIGNED'', ''MPI_UNSIGNED_LONG'', ''MPI_FLOAT'', ''MPI_DOUBLE'', ''MPI_LONG_DOUBLE'', ''MPI_BYTE'', ''MPI_PACKED'' | ||
+ | * Spezielle Datentypen: ''MPI_COMM'', ''MPI_STATUS'', ''MPI_DATATYPE'' | ||
+ | * Initialisierung von MPI: <code>int err; | ||
+ | err = MPI_Init(&argc, &argv);</code> | ||
+ | * Prozesse kommunizieren über Communicator miteinander (z.B. ''MPI_COMM_WORLD''), ihren Rang in einem Communicator erhalten sie mit <code>int MPI_Comm_rank(MPI_Comm comm, int *rank);</code> | ||
+ | * Die Anzahl der Prozesse in einem Communicator ermittelt <code>int MPI_Comm_size(MPI_Comm comm, int *size);</code> | ||
+ | * MPI wird beendet mit <code>err = MPI_Finalize();</code> | ||
+ | * HelloWorld mit MPI: <code>#include <stdio.h> | ||
+ | #include <mpi.h> | ||
+ | |||
+ | void main (int argc, char *argv[]) | ||
+ | { | ||
+ | int myrank, size; | ||
+ | |||
+ | MPI_Init(&argc, &argv); // Initialize MPI | ||
+ | MPI_Comm_rank(MPI_COMM_WORLD, &myrank); // Get my rank | ||
+ | MPI_Comm_size(MPI_COMM_WORLD, &size); // Get the total number of processors | ||
+ | printf("Processor %d of %d: Hello World!\n", myrank, size); | ||
+ | MPI_Finalize(); // Terminate MPI | ||
+ | }</code> | ||
+ | |||
+ | ==== Point-to-point Kommunikation ==== | ||
+ | * Punkt-zu-Punkt-Verbindungen stellen die fundamentale Kommunikation zwischen Prozessen dar | ||
+ | * Probleme: welche Nachricht wird verarbeitet, wenn mehrere empfangen werden können; synchrone/asynchrone Kommunikation | ||
+ | * beide Teilnehmer (Sender und Empfänger müssen aktiv partizipieren) | ||
+ | * Sender und Empfänger arbeiten meist asynchron (Sender sendet z.B. erst nachdem der Empfänger schon empfangen will) | ||
+ | * Nachrichten bestehen aus | ||
+ | * Envelope: Source, Destination, Communicator, Tag | ||
+ | * Source wird implizit ermittelt, alle anderen Werte müssen explizit angegeben werden | ||
+ | * Body: Buffer, Datatype, Count | ||
+ | * verschickte, noch nicht empfangene Nachrichten hängen in der pending queue, aus der die empfangenden Prozesse die nächsten Nachrichten auswählen können (nicht nur simple FIFO-Queue) | ||
+ | * Nachricht blockierend versenden: <code>int MPI_Send(void *buf, int count, MPI_Datatype dtype, int dest, int tag, MPI_Comm comm);</code> | ||
+ | * alle Parameter sind Input-Parameter | ||
+ | * Nachricht blockierend empfangen: <code>int MPI_Recv(void *buf, int count, MPI_Datatype dtype, int source, int tag, MPI_Comm comm, MPI_Status *status); </code> | ||
+ | * ''source'', ''tag'' und ''communicator'' müssen den Werten aus ''MPI_Send'' entsprechen (Wildcards sind erlaubt für ''source'' und ''tag'') | ||
+ | * ''buffer'' und ''status'' sind Output-Parameter, der Rest Input | ||
+ | * Sender und Empfänger müssen denselben Datentyp verwenden, sonst kann es zu unvorhergesehenen Ergebnissen kommen | ||
+ | * wenn der Puffer länger ist als angegeben, kommt es zu einem Fehler | ||
+ | * Wildcards beim Empfangen | ||
+ | * ''MPI_ANY_SOURCE'' und ''MPI_ANY_TAG'' sind die Wildcards | ||
+ | * über ''status.MPI_SOURCE'' und ''status.MPI_TAG'' können die konkreten Werte ermittelt werden | ||
+ | * tatsächliche Anzahl an Elementen in der empfangenen Nachricht ermitteln (''count'' ist lediglich das Maximum der möglichen Werte): <code>int MPI_Get_count(MPI_Status *status, MPI_Datatype dtype, int *count);</code> | ||
+ | * Beim Senden können zwei unterschiedliche Dinge passieren | ||
+ | * die Nachricht wird in einen MPI-Puffer kopiert und im Hintergrund verschickt | ||
+ | * die Nachricht bleibt in den Programmvariablen bis der empfangende Prozess bereit zum Empfangen ist | ||
+ | * wenn ''MPI_SEND'' zurückkehrt heißt das nicht, dass die Nachricht angekommen ist, sondern nur, dass sie MPI übergeben wurde | ||
+ | * bei der Kommunikation muss man darauf achten, Deadlocks zu verhindern | ||
+ | * Kommunikation genau planen (z.B. P1 send dann recv, P2 recv dann send) | ||
+ | * auch P1 send dann recv, P2 send dann recv kann zu einem Deadlock führen, wenn die Nachrichten zu groß für den MPI-Puffer sind | ||
+ | * blockierende und nicht-blockierende Kommunikation können gemischt werden (sogar bei derselben Nachricht) | ||
+ | * nicht-blockierende Kommunikation benötigt zwei Aufrufe: posting eines sends und eines receives | ||
+ | * die Aufrufe werden beendet entweder durch "Nachfragen" des Prozesses oder durch Warten des Prozesses | ||
+ | * die postings werdne über ein Request-Handle identifiziert, dass der aufrufende Prozess nutzen kann um den Status abzufragen | ||
+ | * nicht-blockierendes Senden: <code>int MPI_Isend(void *buf, int count, MPI_Datatype dtype, int dest, int tag, MPI_Comm comm, MPI_Request *request);</code> | ||
+ | * das I steht für Initiate | ||
+ | * der Aufruf startet lediglich das Senden, es muss ein zusätzlicher Aufruf erfolgen, um den Vorgang abzuschließen | ||
+ | * die Parameter sollten nicht gelesen oder geschrieben werden, solange die Aktion nicht abgeschlossen ist | ||
+ | * nicht-blockierendes Empfangen: <code>int MPI_Irecv(void *buf, int count, MPI_Datatype dtype, int source, int tag, MPI_Comm comm, MPI_Request *request);</code> | ||
+ | * Warten auf Beendigung des nicht-blockierenden Aufrufs: <code>int MPI_Wait( MPI_Request *request, MPI_Status *status );</code> | ||
+ | * Testen auf Beendigung des nicht-blockierenden Aufrufs: <code>int MPI_Test( MPI_Request *request, int *flag, MPI_Status *status );</code> | ||
+ | * Vorteil von nicht-blockierendem Aufruf: weniger Gefahr durch Deadlocks, Möglichkeit zum latency hiding | ||
+ | * Beispiel für latency hiding mit IRECV: <code>MPI_IRECV(...,request) | ||
+ | ... | ||
+ | arrived=FALSE | ||
+ | while (arrived == FALSE) | ||
+ | { | ||
+ | "work planned for processor to do while waiting for message data" | ||
+ | MPI_TEST(request,arrived,status) | ||
+ | } | ||
+ | "work planned for processor to do with the message data"</code> | ||
+ | * Nachteil: höhere Code-Komplexität -> schwierigeres Debugging und schwierigere Wartung | ||
+ | * Sendemodi (Senden abgeschlossen, wenn...) | ||
+ | * Standard: Puffern der Nachricht durch MPI oder Synchronisieren der beiden beteiligten Prozesse | ||
+ | * synchron: der empfangene Prozess muss begonnen haben, die Nachricht zu empfangen | ||
+ | * Ready: ein passendes receive muss bereits vorliegen | ||
+ | * buffered: MPI muss einen Puffer verwenden, der jedoch manuell gesteuert werden kann (''MPI_BUFFER_ATTACH'' und ''MPI_BUFFER_DETACH'') | ||
+ | |||
+ | ==== Kommunikation nicht-zusammenhängender Daten ==== | ||
+ | * üblicherweise werden Daten übertragen, die den gleichen Datentyp haben und in einem Array zusammenhängen | ||
+ | * es können aber auch Daten übertragen werden, die nicht zusammenhängen | ||
+ | * Beispiel: Submatrix versenden in C: (Anzahl Zeilen) * Nachricht mit (Anzahl Spalten) Elementen <code>for (i=0; i<n; ++i) { | ||
+ | MPI_Send(&a[k+i][l], m, MPI_DOUBLE, dest, tag, MPI_COMM_WORLD); | ||
+ | }</code> | ||
+ | * Vorteil: bekannte Funktionen zum Senden können verwendet werden | ||
+ | * Nachteil: Overhead durch mehrere Sendeoperationen | ||
+ | * Daten vor dem Versenden in einen zusammenhängenden Puffer kopieren und diesen versenden | ||
+ | * <code>p = &buffer; | ||
+ | for (i=k; i<k+n; ++i) { | ||
+ | for(j=l; j<l+m; ++j) { | ||
+ | *(p++) = a[i][j]; | ||
+ | } | ||
+ | } | ||
+ | MPI_Send(p, n*m, MPI_DOUBLE, dest, tag, MPI_COMM_WORLD)</code> | ||
+ | * man sollte nicht in Versuchung geraten, Datentypen vor dem Übertragen eigenmächtig zu casten, da unterschiedliche MPI-Implementierungen die Werte falsch interpretieren könnten | ||
+ | * stattdessen sollte ''MPI_PACK'' verwendet werden, das genau diese Aufgabe übernimmt | ||
+ | * <code>count = 0; | ||
+ | for(i=0; i<n; i++){ | ||
+ | MPI_Pack(&a[k+i][l], m, MPI_DOUBLE, buffer, bufsize, count, MPI_COMM_WORLD); | ||
+ | } | ||
+ | MPI_Send(buffer, count, MPI_PACKED, dest, tag, MPI_COMM_WORLD);</code> | ||
+ | * ''MPI_UNPACK'' muss dann anstatt ''MPI_RECV'' zum Empfangen verwendet werden (mit ''MPI_PACK_SIZE'' kann die hierfür benötigte Größe des Puffers ermittelt werden) | ||
+ | * an den Nachrichten selbst kann man nicht erkennen, ob ''MPI_PACK'' verwendet wurde, man könnte sie also ganz "normal" z.B. als Double empfangen | ||
+ | * Vorteil: man kann Nachrichten sukzessive erstellen und beliebige Datentypen verwenden | ||
+ | * Nachteil: Overhead zum Verpacken der Daten | ||
+ | * abgeleitete Datentypen | ||
+ | * werden aus den Standarddatentypen erstellt und ermöglichen ein "on-the-fly"-Packing: der Puffer und das Hin- und Herkopieren entfallen | ||
+ | * TODO? | ||
+ | |||
+ | ==== Kollektive Kommunikation ==== | ||
+ | * MPI stellt einige Funktionen zur Verfügung, um häufig benötigte Kommunikationsmuster zu implementieren | ||
+ | * die Funktionen übertragen Nachrichten zu allen Prozessen einer Gruppe und daher **muss** jeder Prozess die Funktion aufrufen | ||
+ | * ''int MPI_Barrier ( MPI_Comm comm )'' synchronisiert Prozesse ohne Daten zu übertragen; evtl. Overhead, daher sparsam verwenden | ||
+ | * ''int MPI_Bcast ( void* buffer, int count, MPI_Datatype datatype, int rank, MPI_Comm comm )'' schickt Daten vom Rootprozess an alle anderen | ||
+ | * <code>#include <mpi.h> | ||
+ | void main(int argc, char *argv[]) { | ||
+ | int rank; | ||
+ | double param; | ||
+ | MPI_Init(&argc, &argv); | ||
+ | MPI_Comm_rank(MPI_COMM_WORLD,&rank); | ||
+ | if(rank==5) param=23.0; | ||
+ | MPI_Bcast(¶m,1,MPI_DOUBLE,5,MPI_COMM_WORLD); | ||
+ | printf("P:%d after broadcast parameter is %f \n",rank,param); | ||
+ | MPI_Finalize(); | ||
+ | }</code> | ||
+ | * ''int MPI_Reduce ( void* send_buffer, void* recv_buffer, int count, MPI_Datatype datatype, MPI_Op operation, int rank, MPI_Comm comm ) '': sammelt Daten von den Prozessen ein, reduziert diese Daten auf einen Wert, speichert den reduzierten Wert im Rootprozess | ||
+ | * {{:se:mpi_reduce.gif|}} | ||
+ | * ''count'', ''datatype'', ''rank'' müssen in allen Prozessen gleich sein | ||
+ | * ''operation'' wird auf den Werten durchgeführt (sum, min, max etc.) | ||
+ | * <code>#include <stdio.h> | ||
+ | #include <mpi.h> | ||
+ | void main(int argc, char *argv[]) | ||
+ | { | ||
+ | int rank; | ||
+ | int source,result,root; | ||
+ | /* run on 10 processors */ | ||
+ | MPI_Init(&argc, &argv); | ||
+ | MPI_Comm_rank(MPI_COMM_WORLD,&rank); | ||
+ | root=7; | ||
+ | source=rank+1; | ||
+ | MPI_Barrier(MPI_COMM_WORLD); | ||
+ | MPI_Reduce(&source,&result,1,MPI_INT,MPI_PROD,root,MPI_COMM_WORLD); | ||
+ | if(rank==root) printf("P:%d MPI_PROD result is %d \n",rank,result); | ||
+ | MPI_Finalize(); | ||
+ | }</code> | ||
+ | * ''int MPI_Gather ( void* send_buffer, int send_count, MPI_datatype send_type, void* recv_buffer, int recv_count, MPI_Datatype recv_type, int rank, MPI_Comm comm )'' sammelt Daten von allen Prozessen im Rootprozess | ||
+ | * {{:se:mpi_gather.gif|}} | ||
+ | * wie Send in jedem Prozess und n * Recv im Root | ||
+ | * <code>#include <stdio.h> | ||
+ | #include <mpi.h> | ||
+ | void main(int argc, char *argv[]) | ||
+ | { | ||
+ | int rank,size; | ||
+ | double param[16],mine; | ||
+ | int sndcnt,rcvcnt; | ||
+ | int i; | ||
+ | MPI_Init(&argc, &argv); | ||
+ | MPI_Comm_rank(MPI_COMM_WORLD,&rank); | ||
+ | MPI_Comm_size(MPI_COMM_WORLD,&size); | ||
+ | sndcnt=1; | ||
+ | mine=23.0+rank; | ||
+ | if(rank==7) rcvcnt=1; | ||
+ | MPI_Gather(&mine,sndcnt,MPI_DOUBLE,param,rcvcnt,MPI_DOUBLE,7,MPI_COMM_WORLD); | ||
+ | if(rank==7) | ||
+ | for(i=0;i<size;++i) printf("PE:%d param[%d] is %f \n",rank,i,param[i]]); | ||
+ | MPI_Finalize(); | ||
+ | }</code> | ||
+ | * ''MPI_ALLGATHER'' macht das gleiche wie ''MPI_GATHER'' und anschließend direkt ein ''MPI_BCAST'' -> Daten werden direkt an alle Prozesse verteilt | ||
+ | * ''int MPI_Scatter ( void* send_buffer, int send_count, MPI_datatype send_type, void* recv_buffer, int recv_count, MPI_Datatype recv_type, int rank, MPI_Comm comm )'' sendet Daten vom Rootprozess an alle Prozesse abhängig vom Rank | ||
+ | * {{:se:mpi_scatter.gif|}} | ||
+ | * wie n * Send im Root und Recv in jedem Prozess | ||
+ | * <code>#include <stdio.h> | ||
+ | #include <mpi.h> | ||
+ | void main(int argc, char *argv[]) { | ||
+ | int rank,size,i; | ||
+ | double param[8],mine; | ||
+ | int sndcnt,rcvcnt; | ||
+ | MPI_Init(&argc, &argv); | ||
+ | MPI_Comm_rank(MPI_COMM_WORLD,&rank); | ||
+ | MPI_Comm_size(MPI_COMM_WORLD,&size); | ||
+ | rcvcnt=1; | ||
+ | if(rank==3) { | ||
+ | for(i=0;i<8;++i) param[i]=23.0+i; | ||
+ | sndcnt=1; | ||
+ | } | ||
+ | MPI_Scatter(param,sndcnt,MPI_DOUBLE,&mine,rcvcnt,MPI_DOUBLE,3,MPI_COMM_WORLD); | ||
+ | for(i=0;i<size;++i) { | ||
+ | if(rank==i) printf("P:%d mine is %f n",rank,mine); | ||
+ | fflush(stdout); | ||
+ | MPI_Barrier(MPI_COMM_WORLD); | ||
+ | } | ||
+ | MPI_Finalize(); | ||
+ | }</code> | ||
+ | * MPI_ALLREDUCE — used to combine the elements of each process's input buffer and stores the combined value on the receive buffer of all group members. | ||
+ | * User-Defined Reduction Operations — enable reduction to be defined as an arbitrary operation. | ||
+ | * Gather / Scatter Vector Operations — MPI_GATHERV and MPI_SCATTERV allow a varying count of data from/to each process. | ||
+ | * Other Gather / Scatter Variations — MPI_ALLGATHER and MPI_ALLTOALL | ||
+ | * No root process specified: all processes get gathered or scattered data. | ||
+ | * Send and receive arguments are meaningful to all processes. | ||
+ | * MPI_SCAN — used to carry out a prefix reduction on data throughout the group and returns the reduction of the values of all of the processes. | ||
+ | * MPI_REDUCE_SCATTER combines an MPI_REDUCE and an MPI_SCATTERV. | ||
+ | |||
+ | ==== Kommunikatoren ==== | ||
+ | * Kommunikatoren fassen Prozesse zusammen und ermöglichen ihnen die Kommunikation miteinander | ||
+ | * ''MPI_COMM_WORLD'' enthält alle Prozesse | ||
+ | * es gibt Intrakommunikatoren (Gruppe von Prozessen, die in dieser einen eindeutigen Rang haben) und Interkommunikatoren (Kommunikation zwischen Intrakommunikatoren) | ||
+ | * Erzeugen von Intrakommunikatoren | ||
+ | * MPI-1: Aufspalten (''MPI_Comm_split''), duplizieren (''MPI_Comm_dup'') vorhandener Intrakommunikatoren, erzeugen einer neuen Gruppe aus Prozessen, neu anordnen von Prozessen einer Gruppe | ||
+ | * MPI-2: verbinden zweier Anwendungen und mergen ihrer Prozesse, neue Prozesse erzeugen | ||
+ | * {{:se:mpi_comm_create.gif|}} | ||
+ | * ''MPI_Comm_split(MPI_Comm comm, int color, int key, MPI_Comm *newcomm)'' spaltet einen Kommunikator in Subkommunikatoren | ||
+ | * Reihenfolge nach ''key'', wenn identisch nach Rang in ''comm'' | ||
+ | * ''MPI_Comm_group(MPI_Comm comm, MPI_Group *group)'' extrahiert das Handle einer Prozessgruppe aus einem Kommunikator | ||
+ | * ''MPI_Group_incl(MPI_Group group, int n, int *rank, MPI_Group *newgroup)'' erzeugt eine neue Gruppe aus den in ''rank'' angegebenen Prozessen | ||
+ | * werden in ''rank'' Prozesse angegeben, die nicht in der Gruppe ''group'' sind, bricht MPI mit einem Fehler ab, ebenso bei doppelten Einträgen | ||
+ | * wenn ''n'' 0 ist, ist die neue Gruppe ''MPI_EMPTY_GROUP'' | ||
+ | * ''MPI_Group_excl'' hat die gleiche Syntax und erzeugt eine Gruppe mit den Prozessen außer den in ''rank'' angegebenen | ||
+ | * die Reihenfolge der Ranks in ''rank'' ist unerheblich für die neuen Ranks in ''newgroup'' | ||
+ | * wenn ''n'' 0 ist, ist die neue Gruppe gleich der alten | ||
+ | * ''MPI_Group_union(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup)'', ''MPI_Group_intersection'' und ''MPI_Group_difference'' erzeugt zwei Gruppen eine neue durch Anwendung der entsprechenden Mengenoperation | ||
+ | * Abfragen der Informationen der Gruppen | ||
+ | * ''MPI_Group_size(MPI_Group group, int *size)'' | ||
+ | * ''MPI_Group_rank(MPI_Group group, int *rank)'' | ||
+ | * ''MPI_UNDEFINED'' wenn aufrufender Prozess nicht zur Gruppe gehört | ||
+ | * ''MPI_group_translate_ranks(MPI_Group group1, int n, int *rank1, MPI_Group group2, int *rank2)'' | ||
+ | * ''MPI_Group_compare(MPI_Group group1, MPI_Group group2, int *result)'' | ||
+ | * ''result'': ''MPI_IDENT'', ''MPI_SIMILAR'' oder ''MPI_UNEQUAL'' | ||
+ | * ''MPI_Group_free(MPI_Group *group)'' zerstört eine Gruppe | ||
+ | * ''MPI_Comm_create(MPI_Comm comm, MPI_Group group, MPI_Comm *newcomm)'' erzeugt einen neuen Kommunikator auf Basis einer Gruppe | ||
+ | * muss von allen betroffenen Prozessen aufgerufen werden | ||
+ | * Prozesse, die nicht in der Gruppe sind, erhalten ''MPI_COMM_NULL'' als Rückgabewert | ||
+ | * ''MPI_Comm_free(MPI_Comm *comm)'' zerstört einen Kommunikator | ||
+ | |||
+ | ===== Links ===== | ||
+ | * [[http://www.rz.uni-karlsruhe.de/rz/hw/sp/online-kurs/PARALLELRECHNER/parallelr.html|Parallelrechner und Parallelisierungskonzepte (Universität Karlsruhe)]] | ||
+ | * [[http://pvs.uni-muenster.de/pvs/lehre/SS06/ps/folien/1-06Print.pdf|Parallele Systeme (Universität Münster)]] | ||
+ | * [[http://www.mathematik.uni-marburg.de/~loogen/Lehre/ws08/ParProg/Folien/ParProg0.ppt|Parallele Programmierung (Uni Marburg)]] | ||
+ | |||
+ | ===== ToDo ===== | ||
+ | * <del>Online-Learning anschauen</del> | ||
+ | * externe Quellen suchen | ||
+ | * <del>Gesetze Amdahl etc.</del> | ||
+ | * MPI-Standard | ||
+ | * Architekturen verstehen (Shared Memory etc.) | ||
+ | * <del>Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln</del> | ||
+ | * <del>Leistungsbewertung (Gesetze Amdahl etc.)</del> | ||
+ | * <del>OpenMP eher allgemein (Kombination mit MPI)</del> | ||
+ | * <del>OpenMP-Webcast</del> | ||
+ | * <del>Bibliotheken für Parallelrechner nur oberflächlich</del> | ||
+ | * Lehrbrief korrigieren (falsche Parameter bei MPI-Funktionen) | ||
+ | * <del>Metriken für Baum erstellen</del> |