Benutzer-Werkzeuge
se:parallelrechner
Unterschiede
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 17:23] stefan |
se:parallelrechner [2009-01-18 20:37] stefan |
||
|---|---|---|---|
| Zeile 17: | Zeile 17: | ||
| * virtuellen Topologien | * virtuellen Topologien | ||
| * Matrizenrechnung | * 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 ===== | ===== Online-Kurs ===== | ||
| Zeile 401: | Zeile 522: | ||
| * MPI-Standard | * MPI-Standard | ||
| * Architekturen verstehen (Shared Memory etc.) | * Architekturen verstehen (Shared Memory etc.) | ||
| - | * Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln | + | * <del>Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln</del> |
| * Leistungsbewertung (Gesetze Amdahl etc.) | * Leistungsbewertung (Gesetze Amdahl etc.) | ||
| - | * OpenMP eher allgemein (Kombination mit MPI) | + | * <del>OpenMP eher allgemein (Kombination mit MPI)</del> |
| - | * OpenMP-Webcast | + | * <del>OpenMP-Webcast</del> |
| * Bibliotheken für Parallelrechner nur oberflächlich | * Bibliotheken für Parallelrechner nur oberflächlich | ||
| * Lehrbrief korrigieren (falsche Parameter bei MPI-Funktionen) | * Lehrbrief korrigieren (falsche Parameter bei MPI-Funktionen) | ||
| + | * <del>Metriken für Baum erstellen</del> | ||
se/parallelrechner.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
