Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
se:parallelrechner [2009-01-10 16:47] 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 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 393: | Zeile 526: | ||
* 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 | ||
+ | |||
+ | ===== 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> |