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 [2009-01-10 15:48] stefan |
se:parallelrechner [2009-01-18 18:40] 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 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) | ||
+ | * 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 | ||
===== Online-Kurs ===== | ===== Online-Kurs ===== | ||
Zeile 376: | Zeile 479: | ||
* ''MPI_Group_incl(MPI_Group group, int n, int *rank, MPI_Group *newgroup)'' erzeugt eine neue Gruppe aus den in ''rank'' angegebenen Prozessen | * ''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 | * werden in ''rank'' Prozesse angegeben, die nicht in der Gruppe ''group'' sind, bricht MPI mit einem Fehler ab, ebenso bei doppelten Einträgen | ||
- | * die Reihenfolge der Ranks in ''rank'' ist unerheblich für die neuen Ranks in ''newgroup'' | + | * wenn ''n'' 0 ist, ist die neue Gruppe ''MPI_EMPTY_GROUP'' |
- | * wenn ''n'' 0 ist, ist die neue Gruppe gleich der alten | + | |
* ''MPI_Group_excl'' hat die gleiche Syntax und erzeugt eine Gruppe mit den Prozessen außer den in ''rank'' angegebenen | * ''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 | * ''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 | * Abfragen der Informationen der Gruppen | ||
Zeile 392: | Zeile 496: | ||
* Prozesse, die nicht in der Gruppe sind, erhalten ''MPI_COMM_NULL'' als Rückgabewert | * Prozesse, die nicht in der Gruppe sind, erhalten ''MPI_COMM_NULL'' als Rückgabewert | ||
* ''MPI_Comm_free(MPI_Comm *comm)'' zerstört einen Kommunikator | * ''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.) | ||
+ | * Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln | ||
+ | * 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> |