Benutzer-Werkzeuge

Webseiten-Werkzeuge


se:parallelrechner

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
se:parallelrechner [2009-01-02 18:31]
stefan
se:parallelrechner [2014-04-05 11:42] (aktuell)
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 raus 
   * 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 182: Zeile 315:
   MPI_Finalize(); ​                                             // Terminate MPI   MPI_Finalize(); ​                                             // Terminate MPI
 }</​code>  ​ }</​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(&​param,​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>​
se/parallelrechner.1230917479.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)