Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
se:parallelrechner [2008-12-31 19:13] stefan |
se:parallelrechner [2009-01-06 20:33] stefan |
||
---|---|---|---|
Zeile 11: | Zeile 11: | ||
* keine virtuellen Topologien | * 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 | + | * Matrizenrechnung fliegt raus |
* Bibliotheken für Parallelrechner nur oberflächlich | * Bibliotheken für Parallelrechner nur oberflächlich | ||
* Leseempfehlung | * Leseempfehlung | ||
Zeile 92: | Zeile 92: | ||
* latency hiding: Prozess bekommt andere Aufgaben, während er auf die Antwort eines anderen Prozesses wartet | * latency hiding: Prozess bekommt andere Aufgaben, während er auf die Antwort eines anderen Prozesses wartet | ||
* asynchrone Kommunikation | * asynchrone Kommunikation | ||
+ | |||
+ | ==== Einstieg in MPI ==== | ||
+ | * Standard-Implementierung für message passing, keine Bibliothek sonder nur API-Spezifikation | ||
+ | * MPI-Programme bestehen aus mindestens zwei autonomen Prozessen, die ihren eigenen Code ausführen | ||
+ | * die Prozesse kommunizieren über MPI-Funktionen und werden über ihren Rang identifiziert | ||
+ | * die Anzahl der Prozesse ist nicht zur Laufzeit änderbar, sondern wird beim Aufruf des Programms festgelegt | ||
+ | * MPI-1 wurde 1994 entwickelt vom MPI-Forum, dessen Mitglieder aus 60 Organisationen stammen | ||
+ | * der Standard definiert Namen, Aufrufsequenzen und Rückgabewerte von Funktionen -> Interface | ||
+ | * die Implementierung ist dem jeweiligen Hersteller überlassen -> Optimierung für Plattformen möglich | ||
+ | * MPI ist für viele Plattformen verfügbar | ||
+ | * MPI-2 wurde bereits definiert, ist aber noch nicht auf allen Plattform verfügbar (Features: paralleles I/O, C++-Bindings etc.) | ||
+ | * Ziele von MPI | ||
+ | * Portabilität des Quelltextes | ||
+ | * effiziente Implementierungen für viele Architekturen | ||
+ | * von MPI wird nicht definiert/angeboten | ||
+ | * wie die Programme zu starten sind | ||
+ | * dynamische Änderung der Prozesszahl zur Laufzeit | ||
+ | * MPI kann verwendet werden, wenn | ||
+ | * portabler Code benötigt wird | ||
+ | * Anwendungen beschleunigt werden müssen und Schleifen-Parallelisierung nicht ausreicht | ||
+ | * MPI sollte nicht verwendet werden, wenn | ||
+ | * Schleifen-Parallelisierung ausreicht | ||
+ | * es bereits parallele Bibliothken für den Fachbereich gibt (z.B. mathematische Bibliotheken) | ||
+ | * man überhaupt keine Parallelisierung benötigt | ||
+ | * Typen von MPI-Routinen | ||
+ | * point-to-point communication: 1-zu-1-Kommunikation | ||
+ | * collective communication: 1-zu-viele-Kommunikation, Synchronisierung | ||
+ | * process groups | ||
+ | * Process topologies | ||
+ | * Environment management and inquiry | ||
+ | * point-to-point communication | ||
+ | * elementare Kommunikation zwischen 2 Prozessen: send/receive, beide Prozesse müssen aktiv handeln | ||
+ | * Kommunikation per Nachrichten mit Envelope (source, destination, tag etc.) und Body (Daten) | ||
+ | * Teile des Nachrichten-Bodys: buffer (Speicherplatz der Daten), datatype (primitive oder eigene Datentypen), count (Anzahl der Datentypen) | ||
+ | * MPI definiert eigene Datentypen um unabhängig von der Implementierung z.B. der Gleitkommazahlen auf den unterschiedlichen Plattformen zu bleiben | ||
+ | * Modi des Nachrichtenversands | ||
+ | * standard | ||
+ | * synchron: Senden ist erst nach Bestätigung des Empfängers abgeschlossen | ||
+ | * buffered: Senden ist abgeschlossen, nachdem die Daten in den lokalen Puffer kopiert wurden | ||
+ | * ready | ||
+ | * erfolgreiches Senden bedeutet, dass der ursprüngliche Speicherplatz der Daten überschrieben werden kann | ||
+ | * Receive ist beendet, wenn die Daten tatsächlich angekommen sind | ||
+ | * blockierende Kommunikation: die send-/receive-Routine kehrt erst zurück, wenn die Daten tatsächlich versendet wurden | ||
+ | * nicht-blockierende Kommunikation: die send-/receive-Routine kehrt sofort nach dem Aufruf zurück ohne sicherzustellen, dass die Daten tatsächlich versendet wurden, der Prozess kann andere Aufgaben übernehmen und später prüfen, ob die Daten angekommen sind | ||
+ | * collective communications | ||
+ | * ein communicator ist eine Gruppe von Prozessen, die miteinander kommunizieren dürfen, alle Prozesse gehören stets zu MPI_COMM_WORLD | ||
+ | * collective operations übertragen Daten zwischen allen Prozessen einer Gruppe | ||
+ | * Synchronisation: alle Prozesse warten, bis sie einen bestimmten Punkt erreicht haben | ||
+ | * Datenbewegung: Daten werden an alle Prozesse verteilt | ||
+ | * kollektive Berechnung: ein Prozess einer Gruppe sammelt Daten von anderen Prozessen ein und führt Operationen auf den Daten durch | ||
+ | * Vorteile der collective operations im Gegensatz zu point-to-point | ||
+ | * weniger Fehlermöglichkeiten -> eine Codezeile pro Aufruf | ||
+ | * lesbarerer Quelltext | ||
+ | * meist schneller | ||
+ | * Broadcast: ein Prozess sendet Daten an alle Prozesse seiner Gruppe | ||
+ | * Scatter und Gather: Verteilen und Einsammeln von Daten zwischen Prozessen | ||
+ | * Reduktion: ein Root-Prozess sammelt Daten von mehreren Prozessen ein und berechnet einen Einzelwert | ||
+ | * Prozessgruppe: geordnete Gruppe von Prozessen, die jeweils einen Rang (=ID) haben, Prozesse können Mitglied mehrerer Gruppen sein | ||
+ | * Prozesstopologien: Anordnung von Prozessen in geometrischen Figuren (Grid oder Graph), rein virtuelle Anordnung unabhängig von physikalischer Anordnung der Prozessoren, ermöglichen effiziente Kommunikation und erleichtern die Programmierung | ||
+ | * 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'') |