Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- se:parallelrechner [2009-01-06 20:33]
stefan
+++ se:parallelrechner [2009-01-18 20:37]
stefan
@@ Zeile 9: / Zeile 9: @@
   * Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln
   * Leistungsbewertung (Gesetze Amdahl etc.)
-  * keine virtuellen Topologien
   * OpenMP eher allgemein (Kombination mit MPI)
-  * Matrizenrechnung fliegt raus
   * Bibliotheken für Parallelrechner nur oberflächlich
   * Leseempfehlung
     * Gesetze Amdahl etc.
     * 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)
+    * SIMD: ein Befehlsstrom, mehrere Datenströme (Cray, Vektorrechner)
+    * MISD: mehrere Befehlsströme, ein Datenstrom (praktisch keine)
+    * MIMD: mehrere Befehlsströme, mehrere Datenströme
+  * 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)
+  * 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)
+===== 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)
+  * Gesetz von Gustavson-Barsis: S<sub>s</sub>(n) = n + (1 - n) s
+===== 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 =====
@@ Zeile 238: / Zeile 360: @@
     * 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
+===== ToDo =====
+  * <del>Online-Learning anschauen</del>
+  * externe Quellen suchen
+    * Gesetze Amdahl etc.
+    * MPI-Standard
+  * Architekturen verstehen (Shared Memory etc.)
+  * <del>Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln</del>
+  * Leistungsbewertung (Gesetze Amdahl etc.)
+  * <del>OpenMP eher allgemein (Kombination mit MPI)</del>
+    * <del>OpenMP-Webcast</del>
+  * Bibliotheken für Parallelrechner nur oberflächlich
+  * Lehrbrief korrigieren (falsche Parameter bei MPI-Funktionen)
+  * <del>Metriken für Baum erstellen</del>

Stefans Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge