High performance computing: http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/Literatur.html
MPI: http://www.mpi-forum.org/docs/
http://de.wikipedia.org/wiki/Mooresches_Gesetz
Nach dem Mooresche Gesetz (Moore's Law, 1965) verdoppelt sich die Komplexität integrierter Schaltkreise etwa alle zwei Jahre (18 Monate). Ein Ende dieses exponentiellen Wachstums für sequentielle Rechner ist absehbar.
2003 wurde zwar noch argumentiert, dass das Mooresche Gesetz noch 10 Jahre gelten wird, aber diese Frist läuft auch bald ab. http://news.cnet.com/2100-1001-984051.html
Diskussion der Graphik http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/png/flopsrz.png
Auch die Leistungsdichte auf der Chipfläche begrenzt das weitere Wachstum:
Der Bedarf an Rechenleistung wächst jedoch weiter. Ein Ausweg scheint derzeit nur in parallelem Programmieren zu liegen. Dabei werden mehrere Einzel-CPUs mit begrenzter Leistung zu einem leistungsfähigerem Gesamtsystem zusammengeschaltet.
Nach Flynn können alle Rechnerarchitekturen mit dem folgendem Schema klassifiziert werden:
| SD (single data) | MD (multiple data) | |
| SI (single instruction) | SISD | SIMD |
| MI (multiple instruction) | MISD | MIMD |
SIMD: (Flynn); Single Instruction Multiple Data; Ein Befehlswerk holt und analysiert Befehle. Die eigentliche Ausführung wird von einem Array mehrerer Prozessoren übernommen, die dann mit mehreren Datenströmen unabhängig dieselbe Befehlssequenz durchführen können. Beispiele sind klassische Vektorrechner wie die CDC Star-100 oder moderne Graphikprozessoren wie GeForce von Nvidia.
MISD: (Flynn); Multiple Instruction Single Data; eigentlich überflüssige Einstufung, die nur zur Vervollständigung von SISD, SIMD, MISD, MIMD eingeführt wurde. Um dem Ausdruck nachträglich doch noch Sinn zu verleihen, wurden hier Pipeline-Architekuren, die ja hintereinander mit demselben Datum arbeiten, subsummiert. Eigentlich jedoch liegt aber nach jedem Pipeline-Schritt ein anderes modifiziertes Datum vor. Weiter werden hier fehlerredundante Mehrfacharchitekturen genannt, wo mehrere Prozessoren mit demselben Datum rechnen, deren Ergebnis nur akzeptiert wird, wenn es überall gleich ist.
MIMD: (Flynn); Multiple Instruction Multiple Data; mehrere unabhängige Prozessoren bearbeiten mehrere Befehlsströme mit unabhängigen Daten.
Die Flynnsche Klassifizierung differenziert zu wenig die eigentlichen Parallelrechner (MIMD). Deshalb wird diese Gruppe zusätzlich nach der Speicherarchitektur differenziert.
| SMP | symmetric multiprocessor | gemeinsamer Speicher für alle Prozessoren |
| NUMA | non uniform memory access | jedem Rechner ist ein Teil des gemeinsamen |
| Speichers für schnellen Zugriff zugeordnet | ||
| ccNUMA | cache coherent NUMA | |
| DMP | distributed memory processor | jeder Rechner hat eigenen Speicher |
| alle Rechner kommunizieren über ein Datennetz |
Heutige Parallelrechner sind meistens Hybridrechner, in denen mehrere Architekturmodelle vereinigt sind. Ein Linuxcluster ist ein DMP-Rechner aus vielen Knoten mit einem schnellen Vernindungsnetz. Jeder Knoten enthält mehrere Chips mit oder ohne gemeinsamem Speicher. Jeder Chip ist heute eine Multicore-CPU mit gemeinsamem Speicher, also ein SMP-Rechner. Enthält der Cluster zusätzliche Graphikprozessoren, dann können diese als klassischer Vektorrechner (SIMD) benutzt werden.
Die Programmiermodelle sind wesentlich einfacher. Man unterscheidet hier nur
| Thread-parallel | pthreads oder openMP | |
| Message passing | PVM oder MPI | |
| PGAS | partitioned global address space | UPC, coarray-Fortran oder Titanium |
| Darpa | Chapel, X10 oder Fortress |
BAU06, Seite 10
BAU06, Seite 16
RAU07, Seite 65
Lesenswerte, wenn auch etwas ältere Beschreibungen. Vor allem Decomposing the Potentially Parallel ist in Teilen immer noch gültig:
http://www.epcc.ed.ac.uk/library/training/
Sequentielle Programme:
Parallele Programme:
Informationen im WWW:
Compiler:
Kurse:
siehe 1 auf Seite pageref
| 1989 | PVM (Parallel virtual machine) | |
| PThread | ||
| OpenMP | ||
| 1992 | Beginn der MPI-Entwicklung | |
| 11'1992 | Draft | |
| 2'1993 | Draft | |
| 11'1993 | Draft | |
| 5.5.1994 | MPI 1.0 (236 S) | Static at runtime |
| Point-Point | ||
| Collective communication | ||
| Groups, Contexts, Communicators | ||
| Process topologies | ||
| Environment | ||
| Profiling interface | ||
| C/Fortran 77 | ||
| 6'1995 | MPI 1.1 | Fehler |
| 18.7.1997 | MPI 1.2 (= MPI-1) | Version identification |
| 30.5.2008 | MPI 1.3 | Fehler |
| 15.11.2003 | MPI 2.0 | Parallel IO |
| Dynamic process management | ||
| Remote memory operations | ||
| One sided communication | ||
| Fortran 90/ C++ | ||
| Creation of new MPI processes | ||
| Communication to other processes | ||
| MPI_Comm_spawn, accept, connect, join | ||
| 23.6.2008 | MPI 2.1 (=MPI-2) | |
| 4.9.2009 | MPI 2.2 | Korrekturen |
| C++ entsorgt (entgültig?) |
Mit wenigen Ausnahmen (MPI_Init) wird hier nur der Prototyp in C angegeben. Die Deklarationen der anderen Sprachen können problemlos hergeleitet werden.
In Fortran wird der Name komplett groß geschrieben; statt des Funktionsergebnisses wird die Fehlerinformation in einem zusätzlichen Argument IERROR gespeichert.
In C++ erfolgt der Aufruf mit dem Namespace MPI::. Weiter wurde eine minimale (lightweight) Menge von Klassen definiert. Vererbung kommt vor, virtuelle Funktionen nicht. Seit MPI-2.2 gilt die C++-Schnittstelle als deprecated (nicht mehr gültig, zu vermeiden und in alten Programmen zu ersetzen) und C++-Programmierer sollten die C-Schnittstelle oder einen C++-Wrapper anderer Herkunft verwenden. Da die Verwendung der C++-Schnittstelle als sehr gering eingestuft wurde, wurde diese Schnittstelle in MPI-2.2 entfernt, genauer als deprecated deklariert. Als Ersatz können verfügbare Wrapper-Bibliotheken verwendet werden. Eine dieser Bibliotheken ist die Boost-Library http://www.boost.org/doc/libs/1_46_1/doc/html/mpi.html In späteren Versionen kann die C++-Schnittstelle wieder aktiviert werden, wenn die Einschätzung der Verwendung revidiert wird.
Die in C fehlenden Namespaces werden ersetzt durch das Präfix MPI_. Das C-Funktionsergebnis ist immer ein Fehlercode und sollte mindestens mit MPI_SUCCESS verglichen werden. Differenzierte Fehlercodes stehen im Standard auf Seite 284.
Create erzeugt immer neues Objekt; Get liefert Informationen; Set setzt Informationen; Delete löscht Informationen; Is fragt Eigenschaften und Einstellungen.
IN: Eingabeargument; OUT: Ausgabeargumente; INOUT: beides (weitgehend vermieden)
Blockierend, Nichtblockierend
lokal, nichtlokal
kollektiv
vordefiniert und abgeleitet (Datentypen)
portabel (Datentypen)
äquivalent (Datentypen)
opak (Datentypen)
Alle MPI-Programme sollen in jeder Umgebung ohne Änderung des Programmtextes übersetzbar und lauffähig sein. Das wird während des Programmlaufes durch die Funktion Init sichergestellt. Sie erledigt alle vor Beginn einer MPI-Kommunikation notwendigen Vorbereitungen. Das kann eine leere Tätigkeit sein, wenn der launcher schon alles erledigt hat. Im anderen Extremfall werden alle Threads gestartet, die Kommunikationshardware initialisiert und die gesamte Programmumgebung eingestellt.
| int MPI_Init (int * argc, char *** argv) | C |
| int MPI_Init (NULL, NULL) | C |
| int MPI::Init () | C++ |
| int MPI::Init (int & argc, char **& argv) | C++ |
| MPI_INIT (IERROR) | Fortran |
MPI-Programme müssen genau einen Aufruf von MPI_Init enthalten. Vorher dürfen lediglich die Funktionen MPI_Get_version, MPI_Initialized und MPI_Finalized aufgerufen werden.
int MPI_Finalize (void)
Die Funktion beendet den MPI-Teil eines Programms. Der Aufruf ist zwingend und darf nicht entfallen. Danach sind lediglich die Funktionen MPI_Get_version, MPI_Initialized und MPI_Finalized erlaubt. Beim Aufruf von Finalize dürfen keine unabgeschlossenen Kommunikationen existieren.
int MPI_Abort (MPI_Comm comm, int errorcode)
Alle Threads der angegebenen Kommuniatorgruppe comm werden mit dem Fehlercode errorcode beendet. Falls die Beendigung der Threads einzeln nicht möglich ist, dürfen auch alle weiteren beteiligten Threads mitbeendet werden. Die Umgebung kann den Fehlercode verarbeiten, ist aber dazu nicht verpflichtet. Posix-Umgebungen sollten das jedoch tun.
int MPI_Initialized (int * flag)
In der Variablen flag steht nach dem Aufruf der Wert true, wenn MPI_Initialize schon aufgerufen wurde.
int MPI_Finalized (int * flag)
In der Variablen flag steht nach dem Aufruf der Wert true, wenn MPI_Finalize schon aufgerufen wurde.
int MPI_Get_version (int * version, int subversion)
Selbsterklärend. 2010 sind beide Werte 2 (MPI 2.2).
rank
size
name
Gerade im Hochleistungsrechnen ist die genaue Messung von Rechenzeit von großer Bedeutung. Die normale Rechneruhr ist oft nicht genau genug. In Clustern sind spezielle Uhren eingebaut, die in MPI direkt angesprochen werden können. In Programmen mit MPI sind andere Uhrenmechanismen weitgehend unnötig.
double MPI_Wtime (void)
Die Funktion liefert im lokalen Thread mit hoher Zeitauflösung die verstrichene Zeit in Sekunden mit einem festen Zeitnullpunkt.
Der Wert MPI_WTIME_IS_GLOBAL ist true wenn die Uhren aller Threads synchronisiert sind, also denselben Wert bei gleichzeitigem Aufruf erhalten. Die Ungenauigkeit der Synchronisierung darf die halbe Zeitdauer einer MPI-Message der Länge 0 nicht übersteigen.
double MPI_Wtick (void)
Die Funktion liefert die Zeitauflösung in Sekunden, also die Genauigkeit der Uhr.
time Linux-Kommando
Die Übersetzung von MPI-Programmen kann direkt erfolgen, wird aber besser mit einem Compiler-Wrapper abgewickelt. Das genaue vom Wrapper erzeugte Kommando wird mit der Option -show (manchmal showme!) ausgegeben.
Die Wrapper sind mpicc, mpif77, mpicxx und mpif90
Der Start von MPI-Programmen wurde von den meisten Implementierungen mit Hilfe eines getrennten launchers durchgeführt. Er muss dann nicht mehr auf derselben Maschine erfolgen, auf der das gestartete Programm abläuft. Dieser launcher ist nicht standardisiert, hat aber auf vielen Anlagen mittlerweile gleiche oder ähnliche Eigenschaften. Der Standard schlägt folgenden Aufruf vor:
mpirun mpirunArgs exec execArgs
Genauer, aber immer noch nicht verpflichtend definiert der Standard den launcher mpiexec. Dabei orientiert sich der Vorschlag an der MPI-Funktion MPI_Comm_spawn:
mpiexec -n maxprocnmb exec execArgs
Weitere Optionen sind -soft -host -arch -wdir -path -file.
Es können mehrere Programme in einem Kommando getrennt durch : gestartet werden.
mpiexec -n maxprocnmb exec execArgs : -n maxprocnmb exec execArgs : -n maxprocnmb exec execArgs ...
Die Argumente von mpiexec können auch aus einer bereitgestellten Datei geholt werden. Die durch : getrennten Angaben stehen zeilenweise in dieser Datei:
mpiexec -configfile filename
Die folgende Skizze enthält die wichtigsten Wege einer Nachricht zwischen zwei Knoten mit MPI. Die MPI-Funktionsnamen stehen immer an ihrem jeweiligen zeitlichen Endpunkt. Die Zahlen in der Skizze verweisen auf den MPI-2.2 Standard. Die senkrechten Pfeile deuten die Wartezeit in den jeweiligen Funktionen seit dem zeitlichen Beginn des Aufrufs an. Waagrechte Pfeile und Kreise sind wartezeitfreie Aufrufe.
| MPI_Send (buf, n, type, dest, tag, comm); | 26 | buffered or synchronous |
| MPI_Rsend | 41 | don't! nearly never! |
| MPI_Bsend | 40 | buffered |
| MPI_Ssend | 40 | synchronous |
| MPI_Recv (buf, n, type, source, tag, comm, &status); | 30 | receive |
| MPI_Buffer_attach (buf, n); | 46 | provide buffer |
| MPI_Buffer_detach (&bufadr, &n); | 46 | free provided buffer |
| status.MPI_SOURCE | 29,32 | contains sender |
| status.MPI_TAG | 29,32 | contains tag |
| status.MPI_ERROR | 29,32 | contains error code of received message |
| MPI_Get_count (&status, type, &n); | 32 | number of enrties of received message |
| MPI_Isend (buf, n, type, dest, tag, comm, &request); | 50 | |
| MPI_Irsend | 51 | don't! nearly never! |
| MPI_Ibsend | 50 | |
| MPI_Issend | 51 | |
| MPI_Irecv | 52 | |
| MPI_Wait (&request, &status); | 53 | eine bestimmte Nachricht |
| MPI_Waitany (m, requests[], &index, &status); | 57 | die nächste Nachricht |
| MPI_Waitall (m, requests[], status[]); | 59 | alle Nachrichten |
| MPI_Waitsome (m, requests[], &mbar, indices[], statuses[]); | 61 | mindestens eine, aber alle zu diesem Zeitpunkt bekannten |
| MPI_Test (&request, &flag, &status); | 54 | |
| MPI_Testany (m, requests[], &index, &status); | 58 | |
| MPI_Testall (m, requests[], status[]); | 60 | |
| MPI_Testsome (m, requests[], &mbar, indices[], statuses[]); | 62 | |
| MPI_Iprobe | 65 | nur envelope ohne eigentliche Nachricht empfangen |
| MPI_Probe | 66 | |
| MPI_Sendrecv | 74 | |
| Daten, Konversionen | 37 | |
| Regeln, Fairness, Ressourcen | 38,42,43,56 |
| MPI datatype | Fortran datatype |
| MPI_INTEGER | INTEGER |
| MPI_REAL | REAL |
| MPI_DOUBLE_PRECISION | DOUBLE PRECISION |
| MPI_COMPLEX | COMPLEX |
| MPI_LOGICAL | LOGICAL |
| MPI_CHARACTER | CHARACTER(1) |
| MPI_BYTE | |
| MPI_PACKED |
| MPI datatype | C datatype |
| MPI_CHAR | char |
| (treated as printable character) | |
| MPI_SHORT | signed short int |
| MPI_INT | signed int |
| MPI_LONG | signed long int |
| MPI_LONG_LONG_INT | signed long long int |
| MPI_LONG_LONG (as a synonym) | signed long long int |
| MPI_SIGNED_CHAR | signed char |
| (treated as integral value) | |
| MPI_UNSIGNED_CHAR | unsigned char |
| (treated as integral value) | |
| MPI_UNSIGNED_SHORT | unsigned short int |
| MPI_UNSIGNED | unsigned int |
| MPI_UNSIGNED_LONG | unsigned long int |
| MPI_UNSIGNED_LONG_LONG | unsigned long long int |
| MPI_FLOAT | float |
| MPI_DOUBLE | double |
| MPI_LONG_DOUBLE | long double |
| MPI_WCHAR | wchar_t |
| (defined in <stddef.h>) | |
| (treated as printable character) | |
| MPI_C_BOOL | _Bool |
| MPI_INT8_T | int8_t |
| MPI_INT16_T | int16_t |
| MPI_INT32_T | int32_t |
| MPI_INT64_T | int64_t |
| MPI_UINT8_T | uint8_t |
| MPI_UINT16_T | uint16_t |
| MPI_UINT32_T | uint32_t |
| MPI_UINT64_T | uint64_t |
| MPI_C_COMPLEX | float _Complex |
| MPI_C_FLOAT_COMPLEX (as a synonym) | float _Complex |
| MPI_C_DOUBLE_COMPLEX | double _Complex |
| MPI_C_LONG_DOUBLE_COMPLEX | long double _Complex |
| MPI_BYTE | |
| MPI_PACKED |
| MPI datatype | C datatype | Fortran datatype |
| MPI_AINT | MPI_Aint | INTEGER (KIND=MPI_ADDRESS_KIND) |
| MPI_OFFSET | MPI_Offset | INTEGER (KIND=MPI_OFFSET_KIND) |
2. MPI_BYTE hat kein Fortran- oder C-Äquivalent. Es werden 8 Bit lange Bytes ohne Interpretation übertragen.
3. MPI_PACKED überträgt Daten, die im Speicher nichtzusammenhängend stehen und vorher mit MPI_Pack verdichtet wurden. Nach dem Empfang können sie mit MPI_Unpack compilergerecht entzerrt werden.
4. MPI_AINT und MPI_OFFSET sind von MPI definiert und in Fortran als auch in C verwendbar.
| Name | Beschreibung | C | Fortran | C+* |
| source | Sendernummer | status.MPI_SOURCE | status(MPI_SOURCE) | MPI::status.Get_source() |
| destination | Empfängernummer | |||
| tag | Etikett der Nachricht | status.MPI_TAG | status(MPI_TAG) | MPI::status.Get_tag() |
| communicator | Kommunikatormenge der Nachricht | |||
| Fehler | status.MPI_ERROR | status(MPI_ERROR) | MPI::status.Get_error() | |
| Anzahl der Pufferdaten | MPI_Get_count (&status, type, &count) | MPI_GET_COUNT (STATUS, TYPE, COUNT, ERROR) | MPI::status.Get_count(type) |
2. Die Umschlagdaten werden vom Empfänger getrennt ausgewertet.
3. Die Umschlagdaten werden in der Statusvariablen bereitgestellt. Der Status enthält weitere Informationen.
4. In C ist status eine Struktur.
5. In Fortran ist status ein INTEGER-Feld.
6. In C++ werden Memberfunktionen im Namespaceobjekt status aufgerufen.
1. Der Empfangspuffer muss groß genug sein, um die übertragene Nachricht speichern zu können. Ist er zu klein, erzeugt MPI einen Fehler.
2. Eine empfangene Nachricht verändert nur die benötigten Plätze im Empfangspuffer.
3. Vom selben Sender stammende Nachrichten überholen sich nicht. Wenn mehrere Nachrichten empfangen werden können, wird zuerst die Nachricht empfangen, die auch zuerst gesendet wurde.
4. Von verschiedenen Sendern stammende Nachrichten werden nicht in garantierter Reihenfolge empfangen. Eine Nachricht kann dauerhaft von Nachrichten anderer Sender am Empfang gehindert werden (keine Fairness)
5. Fortschrittsgarantie: Wenn ein Sender und ein Empfänger eine Nachricht austauschen wollen, wird mindestens einer der beiden seine MPI-Operation erfolgreich abschließen. Es kann sein, dass am erfolgreichen Abschluß ein Dritter beteiligt ist.
Eine Arbeitslast der Größe n kann numeriert werden von 0 bis n−1 und soll gleichmäßig auf S Prozessoren, numeriert von R=0 bis S−1, verteilt werden (rank, size). Das ist immer gegeben, wenn in MPI ein C-Feld elementweise mit jeweils derselben Tätigkeit bearbeitet werden muss.
Alle angegebenen Formeln sind oft verwendete Standardformeln.
Vorteil: Einfache und übersichtliche Schleife.
for (i = rank; i < n; i += size)
q = n/S; r = n%S; e = (R+1)*q; if (R == S-1) e = n; for (i = R*q; i < e; i ++)
Nachteil: Der letzte Prozessor bekommt zusätzlich den Rest und hat eine größere Last, schlimmstenfalls bist fast zur doppelten.
q = (n+S-1)/S; r = n - q*S; e = (R+1)*q; if (e > n) e = n; for (i = R*q; i < e; i ++)
Nachteil: Zwar bearbeitet jeder Prozessor mindestens ein Element, aber abhängig vom Rest der Division hat der letzte Rechner weniger Last.
q = n/S; r = n%S; if (R < r) { a = R*(q+1); e = (R+1)*(q+1); } else { a = R*q+r; e = (R+1)*q+r; } for (i = a; i < e; i ++)
Vorteil: Der Lastunterschied beträgt maximal ein Element, weil der Divisionsrest auf die ersten Prozessoren verteilt wird.
TTH-Seite: