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-10 13:36]
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 363: Zeile 496:
   * MPI_REDUCE_SCATTER combines an MPI_REDUCE and an MPI_SCATTERV.   * 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.1231591005.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)