Benutzer-Werkzeuge

Webseiten-Werkzeuge


se:parallelrechner

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

se:parallelrechner [2009-01-18 20:37]
stefan
se:parallelrechner [2014-04-05 11:42]
Zeile 1: Zeile 1:
-====== Parallelrechner ====== 
  
-===== Klausur ===== 
-  * Codeabschnitte verifizieren 
-  * Online-Learning anschauen 
-  * Programm als Lückentext 
-  * Verstehen der wichtigsten Funktionen (send/recv) 
-  * Architekturen verstehen (Shared Memory etc.)  ​ 
-  * Metriken verstehen, Metriken (Formeln) für neue Topologie entwickeln 
-  * Leistungsbewertung (Gesetze Amdahl etc.)  
-  * OpenMP eher allgemein (Kombination mit MPI) 
-  * Bibliotheken für Parallelrechner nur oberflächlich ​     ​ 
-  * Leseempfehlung 
-    * Gesetze Amdahl etc. 
-    * MPI-Standard 
-  * NICHT 
-    * virtuellen Topologien 
-    * Matrizenrechnung 
-  * 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 ===== 
- 
-==== Einstieg in parallele Programmierung ==== 
-  * Voraussetzungen für effektive Parallelisierung 
-    * schnelle Verbindung zwischen Prozessoren und Speicher und den einzelnen Prozessen, sowie schnelle Datenübertragung in und aus dem Speicher 
-    * Protokoll für Interprozesskommunikation 
-    * die Algorithmen müssen parallelisierbar sein und in kleine Teilprobleme aufgeteilt werden können 
-    * Mechanismus zur Verteilung der Aufgaben an die Prozesse 
-  * Computerarchitekturen nach Flynn 1972 
-    * Single Instruction Single Data (SISD) 
-    * Multiple Instruction Single Data (MISD) 
-    * Single Instruction Multiple Data (SIMD) 
-      * 1 CPU zur Steuerung und mehrere CPUs mit eigenem Speicher 
-      * Steuer-CPU sendet Broadcasts und die anderen CPU rechnen, abhängig von konditionalen Bedingungen im Code 
-      * Nachteil: viele CPUs bleiben idle 
-    * Multiple Instruction Multiple Data (MIMD) 
-      * jede CPU hat übernimmt sowohl Steuerung als auch Berechnung 
-      * Programme werden von jeder CPU unabhängig von den anderen ausgeführt -> asynchron 
-      * 3 Typen: shared memory (CPUs teilen sich gemeinsamen Speicher), distributed memory (Knoten, die zusammen ein Problem lösen) und SMP (Kombination der beiden vorherigen) 
-  * Shared-Memory MIMD 
-    * Verbindung zwischen CPUs und Speicher via Bus oder Switch 
-    * {{:​se:​shared_mimd.jpg|}} 
-    * CPUs haben zusätzlich internen Speicher: Register und Cache 
-    * Problem bei Verwendung von Cache: Variablen haben nach Änderung durch anderen Prozess vielleicht falschen Wert -> Protokoll wird benötigt zum Ermitteln solcher Fälle 
-  * Distributed-Memory MIMD 
-    * jede CPU hat eigenen Speicher -> Menge von Knoten ergeben den gesamten Parallelrechner 
-    * {{:​se:​mimd.jpg|}} 
-    * da kein Zugriff auf den Speicher der anderen Knoten besteht, müssen geeignete Programmiertechniken verwendet werden, um den Prozessen den Zugriff zu ermöglichen 
-  * SMP Cluster 
-    * Symmetric Multi-Processing 
-    * Netzwerk (-> distributed) aus shared memory Clustern 
-    * Beispiel: Earth Simulator 
-  * Modelle paralleler Programmierung 
-    * message passing model 
-      * Prozesse kommunizieren über Nachrichten 
-      * der Programmierer steuert die Aufteilung der Daten und der Berechnung auf die Prozesse und deren Kommunikation 
-      * wird hauptsächlich bei verteilten Systemen angewendet 
-      * MPI ist der Standard für message passing -> kann auch auf shared memory clustern laufen, schöpft dort aber nicht die Zugriffe auf das shared memory aus 
-    * directives-based data-parallel model 
-      * serieller Code wird durch Quelltextkommentare parallelisiert,​ die den Compiler anweisen, wie er die Daten und Berechnung zu verteilen hat 
-      * Details der Verteilung werden dem Compiler überlassen 
-      * üblicherweise auf shared memory Systemen verwendet 
-      * OpenMP ist ein Standard, ein weiterer ist High Performance Fortran (HPF) 
-      * die Direktiven werden hauptsächlich verwendet um Schleifen zu parallelisieren (small-scale parallelization),​ während MPI auf Programmebene parallelisiert (large-scale) 
-    * Kombination von MPI und OpenMP 
-      * kann Vorteile beider Systeme vereinen: shared memory access und message passing zwischen Nodes 
-  * Design paralleler Programme 
-    * parallele Programme bestehen aus mehreren Instanzen serieller Programme, die über Bibliotheksfunktionen kommunizieren,​ die sich wie folgt einteilen lassen: 
-      * initialize, manage, terminate -> Start der Kommunikation,​ Anzahl der Prozesse ermitteln, Subgroups erstellen 
-      * point-to-point:​ send/​receive zwischen Prozesspaaren 
-      * Kommunikation zwischen Prozessgruppen -> Synchronisation,​ verteilte Berechnung 
-      * Erstellen von Datentypen 
-    * Dekomposition des Problems 
-      * domain decomposition / data parallelism 
-        * Problem lässt sich durch serielle Abarbeitung von mehreren Aufgaben auf mehreren Datenbereichen lösen 
-        * Daten werden aufgeteilt und an die verschiedenen Prozesse verteilt und berechnet, hin und wieder müssen die Prozesse Daten austauschen 
-        * Vorteil: nur ein Steuerungsfluss -> Single Program Multiple Data (SPMD) 
-        * anwendbar, wenn sich Daten leicht auf verschiedene Bereiche aufteilen lassen (z.B. Lösen von Differentialgleichungen) 
-      * functional decomposition / task parallelism 
-        * besser als domain decomposition,​ wenn die Berechnung der einzelnen Teilbereiche der Daten unterschiedlich lange dauert -> alle warten auf den langsamsten Prozess 
-        * Problem lässt sich als Abarbeitung von mehreren Aufgaben gleichzeitig lösen 
-        * implementiert als Client-Server-Modell 
-    * Load Balancing 
-      * Arbeit wird gleichmäßig auf die Prozesse verteilt, damit keine idle sind 
-      * einfach, wenn die gleichen Aufgaben auf mehreren Datenbereichen durchzuführen sind 
-    * Ausführungszeit 
-      * 3 Komponenten wirken sich auf die Ausführungszeit aus 
-        * Berechnungszeit:​ die Zeit, die nur für die Berechnung des Problems verwendet wird 
-        * Wartezeit: Zeit, die ein Prozess auf einen anderen wartet (Beispiel: zentralisierte Kommunikation) 
-        * Kommunikationszeit:​ Zeit, die zum Senden und Empfangen von Nachrichten gebraucht wird (Latenz ist die Zeit um die Kommunikation vorzubereiten,​ Bandbreite ist die Übertragungsgeschwindigkeit),​ muss minimiert werden, da sie Overhead im Vergleich zu serieller Bearbeitung darstellt 
-    * Prozesswartezeit verringern 
-      * latency hiding: Prozess bekommt andere Aufgaben, während er auf die Antwort eines anderen Prozesses wartet 
-      * asynchrone Kommunikation 
- 
-==== Einstieg in MPI ==== 
-  * Standard-Implementierung für message passing, keine Bibliothek sonder nur API-Spezifikation 
-  * MPI-Programme bestehen aus mindestens zwei autonomen Prozessen, die ihren eigenen Code ausführen 
-  * die Prozesse kommunizieren über MPI-Funktionen und werden über ihren Rang identifiziert 
-  * die Anzahl der Prozesse ist nicht zur Laufzeit änderbar, sondern wird beim Aufruf des Programms festgelegt 
-  * MPI-1 wurde 1994 entwickelt vom MPI-Forum, dessen Mitglieder aus 60 Organisationen stammen 
-    * der Standard definiert Namen, Aufrufsequenzen und Rückgabewerte von Funktionen -> Interface 
-    * die Implementierung ist dem jeweiligen Hersteller überlassen -> Optimierung für Plattformen möglich 
-    * MPI ist für viele Plattformen verfügbar 
-  * MPI-2 wurde bereits definiert, ist aber noch nicht auf allen Plattform verfügbar (Features: paralleles I/O, C++-Bindings etc.) 
-  * Ziele von MPI 
-    * Portabilität des Quelltextes 
-    * effiziente Implementierungen für viele Architekturen 
-  * von MPI wird nicht definiert/​angeboten 
-    * wie die Programme zu starten sind 
-    * dynamische Änderung der Prozesszahl zur Laufzeit 
-  * MPI kann verwendet werden, wenn 
-    * portabler Code benötigt wird 
-    * Anwendungen beschleunigt werden müssen und Schleifen-Parallelisierung nicht ausreicht 
-  * MPI sollte nicht verwendet werden, wenn 
-    * Schleifen-Parallelisierung ausreicht 
-    * es bereits parallele Bibliothken für den Fachbereich gibt (z.B. mathematische Bibliotheken) 
-    * man überhaupt keine Parallelisierung benötigt 
-  * Typen von MPI-Routinen 
-    * point-to-point communication:​ 1-zu-1-Kommunikation 
-    * collective communication:​ 1-zu-viele-Kommunikation,​ Synchronisierung 
-    * process groups 
-    * Process topologies 
-    * Environment management and inquiry 
-  * point-to-point communication 
-    * elementare Kommunikation zwischen 2 Prozessen: send/​receive,​ beide Prozesse müssen aktiv handeln 
-    * Kommunikation per Nachrichten mit Envelope (source, destination,​ tag etc.) und Body (Daten) 
-    * Teile des Nachrichten-Bodys:​ buffer (Speicherplatz der Daten), datatype (primitive oder eigene Datentypen),​ count (Anzahl der Datentypen) 
-    * MPI definiert eigene Datentypen um unabhängig von der Implementierung z.B. der Gleitkommazahlen auf den unterschiedlichen Plattformen zu bleiben 
-    * Modi des Nachrichtenversands 
-      * standard 
-      * synchron: Senden ist erst nach Bestätigung des Empfängers abgeschlossen 
-      * buffered: Senden ist abgeschlossen,​ nachdem die Daten in den lokalen Puffer kopiert wurden 
-      * ready 
-    * erfolgreiches Senden bedeutet, dass der ursprüngliche Speicherplatz der Daten überschrieben werden kann 
-    * Receive ist beendet, wenn die Daten tatsächlich angekommen sind 
-    * blockierende Kommunikation:​ die send-/​receive-Routine kehrt erst zurück, wenn die Daten tatsächlich versendet wurden 
-    * nicht-blockierende Kommunikation:​ die send-/​receive-Routine kehrt sofort nach dem Aufruf zurück ohne sicherzustellen,​ dass die Daten tatsächlich versendet wurden, der Prozess kann andere Aufgaben übernehmen und später prüfen, ob die Daten angekommen sind 
-  * collective communications 
-    * ein communicator ist eine Gruppe von Prozessen, die miteinander kommunizieren dürfen, alle Prozesse gehören stets zu MPI_COMM_WORLD 
-    * collective operations übertragen Daten zwischen allen Prozessen einer Gruppe 
-      * Synchronisation:​ alle Prozesse warten, bis sie einen bestimmten Punkt erreicht haben 
-      * Datenbewegung:​ Daten werden an alle Prozesse verteilt 
-      * kollektive Berechnung: ein Prozess einer Gruppe sammelt Daten von anderen Prozessen ein und führt Operationen auf den Daten durch 
-    * Vorteile der collective operations im Gegensatz zu point-to-point 
-      * weniger Fehlermöglichkeiten -> eine Codezeile pro Aufruf 
-      * lesbarerer Quelltext 
-      * meist schneller 
-    * Broadcast: ein Prozess sendet Daten an alle Prozesse seiner Gruppe 
-    * Scatter und Gather: Verteilen und Einsammeln von Daten zwischen Prozessen 
-    * Reduktion: ein Root-Prozess sammelt Daten von mehreren Prozessen ein und berechnet einen Einzelwert 
-  * Prozessgruppe:​ geordnete Gruppe von Prozessen, die jeweils einen Rang (=ID) haben, Prozesse können Mitglied mehrerer Gruppen sein 
-  * Prozesstopologien:​ Anordnung von Prozessen in geometrischen Figuren (Grid oder Graph), rein virtuelle Anordnung unabhängig von physikalischer Anordnung der Prozessoren,​ ermöglichen effiziente Kommunikation und erleichtern die Programmierung 
-  * Management und Abfragen der Umgebung: initialisieren und beenden von Prozessen, Rangermittlung 
- 
-==== MPI Programmstruktur ==== 
-  * grundsätzlicher Aufbau von MPI-Programmen <​code>​include MPI header file 
-variable declarations 
-initialize the MPI environment 
-...do computation and MPI communication calls... 
-close MPI communications</​code>​ 
-  * MPI-Funktionsnamen beginnen immer mit ''​MPI_''​ und haben ''​int''​ als Rückgabewert (sollte ''​MPI_SUCCESS''​ sein) 
-  * Liste aller MPI-Konstanten:​ http://​www.netlib.org/​utk/​papers/​mpi-book/​mpi-book.html 
-  * MPI-Datentypen einer Send-/​Receive-Kombination müssen übereinstimmen 
-  * MPI-Standarddatentypen:​ ''​MPI_CHAR'',​ ''​MPI_SHORT'',​ ''​MPI_INT'',​ ''​MPI_LONG'',​ ''​MPI_UNSIGNED_CHAR'',​ ''​MPI_UNSIGNED_SHORT'',​ ''​MPI_UNSIGNED'',​ ''​MPI_UNSIGNED_LONG'',​ ''​MPI_FLOAT'',​ ''​MPI_DOUBLE'',​ ''​MPI_LONG_DOUBLE'',​ ''​MPI_BYTE'',​ ''​MPI_PACKED''​ 
-  * Spezielle Datentypen: ''​MPI_COMM'',​ ''​MPI_STATUS'',​ ''​MPI_DATATYPE''​ 
-  * Initialisierung von MPI: <​code>​int err; 
-err = MPI_Init(&​argc,​ &​argv);</​code>​ 
-  * Prozesse kommunizieren über Communicator miteinander (z.B. ''​MPI_COMM_WORLD''​),​ ihren Rang in einem Communicator erhalten sie mit <​code>​int MPI_Comm_rank(MPI_Comm comm, int *rank);</​code>​ 
-  * Die Anzahl der Prozesse in einem Communicator ermittelt <​code>​int MPI_Comm_size(MPI_Comm comm, int *size);</​code>​ 
-  * MPI wird beendet mit <​code>​err =  MPI_Finalize();</​code>​ 
-  * HelloWorld mit MPI: <​code>#​include <​stdio.h>​ 
-#include <​mpi.h> ​ 
- 
-void main (int argc, char *argv[]) ​ 
-{ 
-  int myrank, size; 
- 
-  MPI_Init(&​argc,​ &​argv); ​                                     // Initialize MPI  
-  MPI_Comm_rank(MPI_COMM_WORLD,​ &​myrank); ​                     // Get my rank  
-  MPI_Comm_size(MPI_COMM_WORLD,​ &​size); ​                       // Get the total number of processors 
-  printf("​Processor %d of %d: Hello World!\n",​ myrank, size); 
-  MPI_Finalize(); ​                                             // Terminate MPI 
-}</​code>  ​ 
- 
-==== Point-to-point Kommunikation ==== 
-  * Punkt-zu-Punkt-Verbindungen stellen die fundamentale Kommunikation zwischen Prozessen dar 
-  * Probleme: welche Nachricht wird verarbeitet,​ wenn mehrere empfangen werden können; synchrone/​asynchrone Kommunikation 
-  * beide Teilnehmer (Sender und Empfänger müssen aktiv partizipieren) 
-  * Sender und Empfänger arbeiten meist asynchron (Sender sendet z.B. erst nachdem der Empfänger schon empfangen will) 
-  * Nachrichten bestehen aus  
-    * Envelope: Source, Destination,​ Communicator,​ Tag 
-      * Source wird implizit ermittelt, alle anderen Werte müssen explizit angegeben werden 
-    * Body: Buffer, Datatype, Count 
-  * verschickte,​ noch nicht empfangene Nachrichten hängen in der pending queue, aus der die empfangenden Prozesse die nächsten Nachrichten auswählen können (nicht nur simple FIFO-Queue) 
-  * Nachricht blockierend versenden: <​code>​int MPI_Send(void *buf, int count, MPI_Datatype dtype, int dest, int tag, MPI_Comm comm);</​code>​ 
-    * alle Parameter sind Input-Parameter ​   ​ 
-  * Nachricht blockierend empfangen: <​code>​int MPI_Recv(void *buf, int count, MPI_Datatype dtype, int source, int tag, MPI_Comm comm, MPI_Status *status); </​code>​ 
-    * ''​source'',​ ''​tag''​ und ''​communicator''​ müssen den Werten aus ''​MPI_Send''​ entsprechen (Wildcards sind erlaubt für ''​source''​ und ''​tag''​) 
-    * ''​buffer''​ und ''​status''​ sind Output-Parameter,​ der Rest Input 
-    * Sender und Empfänger müssen denselben Datentyp verwenden, sonst kann es zu unvorhergesehenen Ergebnissen kommen 
-    * wenn der Puffer länger ist als angegeben, kommt es zu einem Fehler ​   ​ 
-  * Wildcards beim Empfangen 
-    * ''​MPI_ANY_SOURCE''​ und ''​MPI_ANY_TAG''​ sind die Wildcards 
-    * über ''​status.MPI_SOURCE''​ und ''​status.MPI_TAG''​ können die konkreten Werte ermittelt werden 
-  * tatsächliche Anzahl an Elementen in der empfangenen Nachricht ermitteln (''​count''​ ist lediglich das Maximum der möglichen Werte): <​code>​int MPI_Get_count(MPI_Status *status, MPI_Datatype dtype, int *count);</​code>​ 
-  * Beim Senden können zwei unterschiedliche Dinge passieren 
-    * die Nachricht wird in einen MPI-Puffer kopiert und im Hintergrund verschickt 
-    * die Nachricht bleibt in den Programmvariablen bis der empfangende Prozess bereit zum Empfangen ist 
-  * wenn ''​MPI_SEND''​ zurückkehrt heißt das nicht, dass die Nachricht angekommen ist, sondern nur, dass sie MPI übergeben wurde 
-  * bei der Kommunikation muss man darauf achten, Deadlocks zu verhindern 
-    * Kommunikation genau planen (z.B. P1 send dann recv, P2 recv dann send) 
-    * auch P1 send dann recv, P2 send dann recv kann zu einem Deadlock führen, wenn die Nachrichten zu groß für den MPI-Puffer sind 
-  * blockierende und nicht-blockierende Kommunikation können gemischt werden (sogar bei derselben Nachricht) 
-  * nicht-blockierende Kommunikation benötigt zwei Aufrufe: posting eines sends und eines receives 
-    * die Aufrufe werden beendet entweder durch "​Nachfragen"​ des Prozesses oder durch Warten des Prozesses 
-    * die postings werdne über ein Request-Handle identifiziert,​ dass der aufrufende Prozess nutzen kann um den Status abzufragen 
-  * nicht-blockierendes Senden: <​code>​int MPI_Isend(void *buf, int count, MPI_Datatype dtype, int dest, int tag, MPI_Comm comm, MPI_Request *request);</​code>​ 
-    * das I steht für Initiate 
-    * der Aufruf startet lediglich das Senden, es muss ein zusätzlicher Aufruf erfolgen, um den Vorgang abzuschließen 
-    * die Parameter sollten nicht gelesen oder geschrieben werden, solange die Aktion nicht abgeschlossen ist 
-  * nicht-blockierendes Empfangen: <​code>​int MPI_Irecv(void *buf, int count, MPI_Datatype dtype, int source, int tag, MPI_Comm comm, MPI_Request *request);</​code>​ 
-  * Warten auf Beendigung des nicht-blockierenden Aufrufs: <​code>​int MPI_Wait( MPI_Request *request, MPI_Status *status );</​code>​ 
-  * Testen auf Beendigung des nicht-blockierenden Aufrufs: <​code>​int MPI_Test( MPI_Request *request, int *flag, MPI_Status *status );</​code>​ 
-  * Vorteil von nicht-blockierendem Aufruf: weniger Gefahr durch Deadlocks, Möglichkeit zum latency hiding 
-    * Beispiel für latency hiding mit IRECV: <​code>​MPI_IRECV(...,​request) 
-... 
-arrived=FALSE 
-while (arrived == FALSE) ​ 
-{ 
-   "​work planned for processor to do while waiting for message data" 
-   ​MPI_TEST(request,​arrived,​status) 
-} 
-"work planned for processor to do with the message data"</​code>​ 
-  * Nachteil: höhere Code-Komplexität -> schwierigeres Debugging und schwierigere Wartung 
-  * Sendemodi (Senden abgeschlossen,​ wenn...) 
-    * Standard: Puffern der Nachricht durch MPI oder Synchronisieren der beiden beteiligten Prozesse 
-    * synchron: der empfangene Prozess muss begonnen haben, die Nachricht zu empfangen 
-    * 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>​ 
se/parallelrechner.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)