# Testat - MPI
## Fragenkatalog 1 (leicht)
---
Erklären Sie die Funktionalität von `MPI_Init` inklusive Argumente.
- Alternativfrage: Welches ist typischerweise der erste Befehl eines MPI Programms? Wozu dient dieser?
- Initialisiert die MPI Umgebung
- Muss als erste MPI Funktion aufgerufen werden
- Ausnahme: `MPI_Initialized`
Signatur:
```cqwe
int MPI_Init(int *argc, char ***argv);
```
- MPI spezifiziert zwar keine CLI Argumente
- Aber MPI-Implementationen können optional CLI Argumente verwenden, sofern sie diese benötigen
Commandline Argumente:
- `*argc` Pointer zur Anzahl der spezifierten Argumente in `argv`
- `***argv` Pointer zum Array von Argumenten (Strings)
Rückgabe: Error Code
---
Was ist ein Kommunikator und wie werden sie eingerichtet?
- ein Objekt, das eine Gruppe von Prozessen beschreibt
- Kombiniert die Begriffe (Kommunikations-)Kontext und Gruppe
- Das in Senden oder Empfangen angegebene Ziel oder die Quelle bezieht sich auf den Rang des Prozesses innerhalb der Gruppe
- Arten von Kommunikatoren:
- `MPI_COMM_WORLD`: Umfasst alle Prozesse, die gemeinsam von `mpiexec` (oder einem verwandten Programm) gestartet wurden.
- `MPI_COMM_SELF`: Kommunikator selbst, welcher nur den aktuellen Prozess (local process) enthält
- `MPI_COMM_NULL`: Ein invalider Kommunikator. Routinen, die Kommunikatoren konstruieren, können dies als Ergebnis ausgeben, wenn ein Fehler auftritt.
Rang in einem Kommunikator:
```c
int MPI_Comm_rank(MPI_Comm comm, int *rank)
```
- Bestimmt den Rang (PID) des aufrufenden Prozesses im Kommunikator
- `MPI_Comm`: Kommunikator, welche die Prozesse für die MPI Kommunikation enthält
- `*rank`: Variable, in dem der Rang gespeichert wird
Größe eines Kommunikators:
```c
int MPI_Comm_size(MPI_Comm comm, int *size)
```
- Bestimmt die Größe der Gruppe fest, die einem Kommunikator zugeordnet ist
- `MPI_Comm`: Kommunikator, welcher die Prozesse für die MPI Kommunikation enthält
- `*size`: Variable, in dem die Größe gespeichert wird
Rückgabe: Error Code
---
Wofür steht MPI?
- Message Passing Interface
- Library
- Standard zur Beschreibung von Nachrichtenaustausch bei parallelen Berechnung auf verteilten Computersystemen
- MPI ist eine Spezifikation, keine bestimmte Implementierung
- Gibt Namen, Aufrufsequenzen, Ergebnisse von Funktionen, Unterprogramme an, die für den Kommunikationsaustausch von Nöten sind
- (Sollte auf allen MPI-Implementationen ausführbar sein, ohne Veränderungen)
- Mehrere Prozesse mit jeweils eigenem privaten Adressraum
- Zugriff auf (Remote-)Daten von anderen Prozessen via Senden und Empfangen von Nachrichten
<img src="https://i.imgur.com/U8lcCGD.png" alt="Visualisierung" width="50%" style="display: block; margin-left: auto; margin-right: auto;">
---
Erklären Sie die Funktionalität von `MPI_Request`.
Eine Objekt von `MPI_Request` dient zur Identifikation einer Kommunikation.
Zum Abschluss der Kommunikation wird das Request Objekt an die `MPI_Wait` Funktion gegeben, welche die Ausführung so lange blockiert, bis alle Daten vollständig ausgetauscht wurden.
---
Was versteht man unter hybrider Parallelisierung? Was muss bei der Anwendung beachtet werden?
Hintergrund/Motivation:
- Clusters bestehen überwiegend aus Knoten mit gemensamen Speicher
- Speicher wird durch steigende Anzahl der Kerne pro Chip immer größer
- Verwendung eines MPI Prozess pro Kern beschränkt die Skalierbarkeit & Effizienz
- Zusätzlicher Speicherbedarf für die Aufrechterhaltung getrennter privater Adressräume
- Aufwand für das Kopieren von Daten zwischen diesen Adressräumen
- Viele externe MPI-Verbindungen pro Knoten
$\Rightarrow$ Zusammensetzung aus OpenMP und MPI, um die Anzahl der MPI Prozesse zu reduzieren
- OpenMP für work sharing innerhalb eines Knotens
- MPI zur Parallelisierung verschiedener Knoten
Probleme:
- MPI Prozess ist ein Prozess, der mehrere Threads haben kann
- jeder Thread kann aber MPI Calls (Aufrufe) erteilen --> man muss also sicherstellen, dass mehrere Threads keine störenden MPI Aufrufe initiieren
- Threads sind nicht separat adressierbar
- Ein Rang in einem Sende-/Empfangsaufruf identifiziert einen Prozess, nicht einen Thread
- somit kann eine an einen Prozess gesendete Nachricht von jedem Thread in diesem Prozess empfangen werden ==> ungewollte Überschneidungen
---
## Fragenkatalog 2 (mittel)
---
Erklären Sie die Funktionalität von `MPI_Send` inklusive Argumente.
Alternativfrage: Was ist die Bedeutung der Parameter von `MPI_Send`? (Funktionsignatur)
`MPI_Send` und `MPI_Recv` sind blockierende Anweisungen
```c
int MPI_Send(void *buf, int count, MPI_Datatype datatype,
int dest, int tag,
MPI_Comm comm)
```
- Sendet Daten von Datentyp `datatype` zu einem Zielprozess
- `*buf`: Buffer, welcher die Daten zum Senden enthält (Adresse)
- `count`: Anzahl an Daten, die gesendet werden sollen
- `datatype`: Datentyp der Daten
- `dest`: Prozess ID, welche die Daten empfangen soll
- `tag`: Eine Zahl zum Nachrichtenabgleich ("message matching")
- `comm`: Identifiziert eine Gruppe von Prozessen und eine Kommunikationskontext
---
Erläutern Sie den Unterschied in der Aufgabe 3 (`heated-plate`) zwischen blockierend und nicht blockierenden Anweisungen.
Alternativfrage: Was ist der Unterschied zwischen blocking und non-blocking bei `MPI_Send`/ `MPI_Recv`?
- Der aufrufende Prozess blockiert die Ausführung so lange, bis der Datenaustausch abgeschlossen ist
- Dies garantiert zwar einerseits, dass die Daten bei der anschließenden Verwendung vollständigt vorliegen.
- Andererseits kann der Prozess, während er auf den Abschluss der Kommunikation wartet, keine weitere Arbeit verrichten.
- Der Vorteil an nicht-blockierender Kommunikation ist also, dass schon Arbeit erledigt werden kann, solange der Datenaustausch im Hintergrund abläuft.
---
Erklären Sie die Funktionalität von `MPI_Recv` inklusive Argumente.
- Alternativfrage: Welche Parameter hat `MPI_Recv`?
- `MPI_Send` und `MPI_Recv` sind blockierende Anweisungen
```c
int MPI_Recv(void *buf, int count, MPI_Datatype datatype,
int source, int tag,
MPI_Comm comm, MPI_Status *status)
```
- Empfängt Daten von Datentyp `datatype` von einem Quellprozess
- `*buf`: Buffer, in dem die empfangenen Daten gespeichert werden
- `count`: Anzahl an Daten, die empfangen werden soll
- `datatype`: Datentyp der Daten
- `source`: Prozess ID vom Sender
- Wildcard: `MPI_ANY_SOURCE`
- `tag`: Eine Zahl zum Nachrichtenabgleich oder ein Wildcard `MPI_ANY_TAG`
- `comm`: Identifiziert eine Gruppe von Prozessen und eine Kommunikationskontext
- `status`: Enthält Informationen über die tatsächliche Größe der Nachricht, die Quelle und den Tag
---
Was macht `MPI_Gather`, was macht `MPI_Allgather`? Wie kann man die Funktion "Allgather" implementieren ohne die Funktion `MPI_Allgather` zu verwenden?
- `MPI_Gather`: Sammeln von Daten von allen Prozessen zu einem Prozess (zu root)
<img src="https://i.imgur.com/SvvBML2.png" alt="MPI_Gather" width="50%" style="display: block; margin-left: auto; margin-right: auto;">
- `MPI_Allgather`: Sammelt Daten von allen Prozessen und verteilt die kombinierten Daten an alle Prozessen
<img src="https://i.imgur.com/XTiuuNH.png" alt="MPI_AllGather" width="30%" style="display: block; margin-left: auto; margin-right: auto;">
- `MPI_Allgather` = `MPI_Gather` & `MPI_Bcast` (Broadcast)
<img src="https://i.imgur.com/UbAtnze.png" alt="MPI_Gatger + MPI_Bcast" width="80%" style="display: block; margin-left: auto; margin-right: auto;">
---
Deadlocks in 3 Files finden und erklären, wie die gelöst werden können:
Code 1:
```c
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
int sum;
int value = 5;
int myrank;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
value = myrank * value;
if(myrank != 0) {
MPI_Barrier(MPI_COMM_WORLD);
}
printf("rank: %d, value %d\n", myrank, value);
MPI_Reduce(&value, &sum, 1, MPI_INT, 0, MPI_SUM, MPI_COMM_WORLD);
MPI_Finalize();
}
```
- Barrier wird von Rang 0 nicht erreicht
- `if` entfernen
Code 2:
```c
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
int sum = 0;
int value;
int myrank;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
while(sum < 50) {
value = sum + 1;
MPI_Reduce(&value, &sum, 1, MPI_INT, 0, MPI_SUM, MPI_COMM_WORLD);
}
printf("sum: %d\n", sum);
MPI_Finalize();
}
```
- Alle Prozesse außer dem Master befinden sich in einer Endlosschleife, da die Summe `sum` nur im Masterprozess aktualisiert wird.
- `MPI_Allreduce` verwenden
Code 3:
```c
// Unbekannt
```
Antwort: Master macht Broadcast, Worker aber Recv. So funktioniert der Broadcast aber nicht.
---
Nennen Sie eine kollektive MPI Operation. Was bedeutet "kollektiv" in diesem Zusammenhang?
- Lösungen für wiederkehrende Kommunikationspatterns zwischen Prozessen
- Alle Prozesse innerhalb eines Kommunikators sind involviert
- Manuelle Implementierung aufwändig, fehleranfällig und ggf. ineffizient
- Lösung: Vordefinierte kollektive MPI Operationen
- Implementierungen von vordefinierten kollektiven Operationen können auch spezielle Eigenschaften der Zielplattform ausnutzen
- Arten: $1 \rightarrow n, n \rightarrow 1, n \rightarrow n$
`MPI_Barrier`: Blockiert, bis alle Prozesse im Kommunikator diese Routine erreicht haben.
`MPI_Bcast`: Sendet eine Nachricht vom Prozess mit dem Rang "root" an alle anderen Prozesse des Kommunikators (Broadcast)
<img src="https://i.imgur.com/6d9ZhCi.png" alt="MPI_Bcast" width="50%" style="display: block; margin-left: auto; margin-right: auto;">
`MPI_Gather`: Sammeln von Daten von allen Prozessen zu einem Prozess (zu root)
<img src="https://i.imgur.com/SvvBML2.png" alt="MPI_Gather" width="50%" style="display: block; margin-left: auto; margin-right: auto;">
`MPI_Allgather`: Sammelt Daten von allen Prozessen und verteilt die kombinierten Daten an alle Prozesse
<img src="https://i.imgur.com/XTiuuNH.png" alt="MPI_AllGather" width="40%" style="display: block; margin-left: auto; margin-right: auto;">
`MPI_Scatter`: Sendet Daten von einem Prozess an alle anderen Prozesse in einem Communicator
<img src="https://i.imgur.com/NogAU5K.png" alt="MPI_Scatter" width="50%" style="display: block; margin-left: auto; margin-right: auto;">
`MPI_Reduce`: Kombiniert/reduziert die Werte von allen Prozessen auf einen einzigen Wert
<img src="https://i.imgur.com/4Pebv14.png" alt="MPI_Reduce" width="30%" style="display: block; margin-left: auto; margin-right: auto;">
`MPI_Allreduce`: Kombiniert Werte aus allen Prozessen und verteilt das Ergebnis zurück an alle Prozesse
<img src="https://i.imgur.com/d01IQ5g.png" alt="MPI_Allreduce" width="50%" style="display: block; margin-left: auto; margin-right: auto;">
---
Wie unterscheiden sich blockierende und nicht-blockierende Kommunikation auf der Seite des Senders und Empfängers? Beschreiben Sie eine Situation, in der die Performance nicht durch die Verwendung von nicht-blockierenden Routinen verbessert werden kann.
- Zu den blockierenden Befehlen gehören `MPI_Send` und `MPI_Recv`. Diese Anweisungen blockieren solange die Kommunikation nicht abgeschlossen ist.
- Zu den nicht-blockierenden Befehlen gehören `MPI_Isend` und `MPI_Irecv`. Diese kommen sofort zurück obwohl die versendeten Daten noch nicht geändert werden dürfen bzw. noch keine Daten vorliegen. Um zusehen, dass die Kommunikation beendet ist, muss man `MPI_Wait` und `MPI_Test` aufrufen.
- Die Performance verbessert sich dann nicht durch die Verwendung von nicht-blockierenden Routinen, wenn das Ergebnis der Kommunikation direkt verwendet werden muss.
---
## Fragenkatalog 3 (schwer)
---
Was gibt es für Modi bei `MPI_Send` + Hintergrund?
Alternativfrage: Welche 2 Arten gibt es bei Send (buffered / synchronous) ? Wann ist Synchronous sinnvoll?
- Buffered Send: Sendeprozess kann abgeschlossen sein bevor ein passendes Receive ausgelöst wurde
- Synchronous Send: Sendeprozess schließt erst ab, wenn passendes Receive ausgelöst wurde
- Wahl zwischen Modi hängt von Nachrichtengröße ab (buffered für lange Nachricht 07_SPP_KW49 1:23:38)
- MuLö erwartet eher für kleinere Nachrichten
- Wenn Punktabzug, einfach 07_SPP_KW49 1:23:38 verlinken
- "In unserer Lösung für die Frage steht da dass buffered für kleine Nachrichten eher verwendet wird. Eventuell meinen sie hiermit extrem große Nachrichten, die nicht mehr in den Buffer passen. Es kann durchaus sein, dass MPI auch bei größeren (solange sie noch in den Buffer passen) buffered send favorisiert."
<img src="https://i.imgur.com/YDmY0sT.png" alt="Hintergrund" width="70%" style="display: block; margin-left: auto; margin-right: auto;">
- Source: https://iamsorush.com/posts/mpi-send-types/
---
Was kann man über den Status und Buffer von `MPI_Send` sagen?
- Status: `MPI_Send` gibt abhängig von buffered oder synronous Send etwas zurück (`MPI_Isend` gibt sofort zurück)
- Buffer: TODO
---
Erklären Sie die Funktionalität von `MPI_Reduce` und `MPI_Allreduce`. Worin unterscheiden Sie sich?
`MPI_Reduce`: Kombiniert/reduziert die Werte von allen Prozessen auf einen einzigen Wert
<img src="https://i.imgur.com/4Pebv14.png" alt="MPI_Reduce" width="30%" style="display: block; margin-left: auto; margin-right: auto;">
```c
int MPI_Reduce(void *sendbuf, void *recvbuf, int count,
MPI_Datatype datatype, MPI_Op op,
int root, MPI_Comm comm)
```
- `*sendbuf`: Buffer, welche die Daten zum Senden enthält (Adresse)
- `*recvbuf`: Buffer, welche die Daten zum Empfangen enthält (Adresse)
- `count`:Anzahl an Daten, die gesendet werden sollen
- `datatype`: Datentyp der Daten
- `op`: MPI-Operation (Reduktionsoperationen)
- `root`: Prozess, der die Daten empfangen soll
- `comm`: Identifiziert eine Gruppe von Prozessen und eine Kommunikationskontext
`MPI_Allreduce`: Kombiniert Werte aus allen Prozessen und verteilt das Ergebnis zurück an alle Prozesse
<img src="https://i.imgur.com/d01IQ5g.png" alt="MPI_Allreduce" width="50%" style="display: block; margin-left: auto; margin-right: auto;">
```c
int MPI_Allreduce(void *sendbuf, void *recvbuf, int count,
MPI_Datatype datatype, MPI_Op op,
MPI_Comm comm)
```
- `*sendbuf`: Buffer, welche die Daten zum Senden enthält (Adresse)
- `*recvbuf`: Buffer, welche die Daten zum Empfangen enthält (Adresse)
- `count`:Anzahl an Daten, die gesendet werden sollen
- `datatype`: Datentyp der Daten
- `op`: MPI-Operation (Reduktionsoperationen)
- `comm`: Identifiziert eine Gruppe von Prozessen und eine Kommunikationskontext
---
Mit welchen MPI Befehl können Sie `MPI_Reduce` zu einem `MPI_Allreduce` erweitern? Warum ist es trotzdem besser direkt die Allreduce Operation zu verwenden?
- `MPI_Reduce` & `MPI_Bcast` (Broadcast)
- Intern schon optimiert implementiert & weniger fehleranfälliger
---
Bei dem Versuch, die Kommunikation durch nicht-blockierende Routinen zu optimieren, ist ein Fehler unterlaufen. Finden Sie den Fehler und erläutern Sie, wie dieser behoben werden kann.
```c
#include <mpi.h>
#include <stdio.h>
#define N 5
// Performs expensive computation and modifies the values.
void expensive_computation(int* vals);
int main(int argc, char** argv) {
int myrank, size;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
MPI_Comm_size(MPI_COMM_WORLD, &myrank);
int valus[N], other_vals[N];
// Initialize values
for(int i = 0; i < N; i++) {
vals[i] = myrank + i;
other_vals[i] = 0;
}
for(int i = 0; i < 10; i++) {
// Send values to next ranj
if(myrank <= size - 1) {
MPI_Send(vals, N, MPI_INT, myrank + 1, 0, MPI_COMM_WORLD);
}
// Receive values from previous rank
if(myrank > 0) {
MPI_Recv(other_vals, N, MPI_INT, myrank - 1, 0,
MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}
// Do some computations and modify values expensive_computation(vals);
// Add values receives from other process
for(int j = 0; j < N; j++) {
vals[j] += other_vals[j];
}
}
}
```
- Data Race durch die innere Schleife
- Nach der inneren `for`-Schleife `MPI_Wait`
---
Beschreiben Sie eine Situation, bei der es bei der Verwendung von `MPI_Send` und `MPI_Recv` zu einem Deadlock kommen kann. Nennen Sie zwei Möglichkeiten, das Problem zu lösen.
Alternativfrage: Wann kann man mit `MPI_Send` und `MPI_Recv` einen Deadlock erzeugen?
- Indem zwei Prozesse mit einem synchronen `MPI_Send` etwas an den jeweils anderen schicken und dann eine Antwort erwarten.
- gelöst werden durch --> (1) `MPI_Sendrecv` und (2) non-blocking Operationen
---
Wie können Deadlocks entstehen? Wie können die gelöst werden?
- gelöst werden durch --> (1) `MPI_Sendrecv` und (2) non-blocking Operationen
---
## Zusatz (Potentiell möglich?)
### Einfach
---
Welche Vorteile/Nachteile bietet MPI?
Vorteile:
- Universalität: Funktioniert sowohl auf verteiltem (distributed memory) als auch auf gemeinsam genutztem Speicher (shared memory) Architekturen
- Expressivität: Intuitiv & Vollständiges Modell zum Ausdruck von Parallelität
- Einfaches Debuggen: Einfacheres Debuggen von Message-Passing-Programmen als das Debuggen von Shared-Memory-Programmen
- Performanz und Skalierbarkeit: Bessere Kontrolle der Datenlokalität. Verteilte Speichermaschinen bieten mehr Speicher und Cache
Nachteile:
- Inkrementelle Parallelisierung schwierig: Parallelisierung von seriellen Programmen benötigt meist eine komplette Neugestaltung des Codes
- Low-Level: MPI Primitive relativ auf low-level Niveau
- Kommunikations- und Synchronisationsaufwand (Overhead): Overhead kann zu Engppässen werden (insbesondere Gruppenkommunikation)
- Komplex: Einfache Operationen sind simpel, aber um das volle Potenzial zu verwenden, benötigt man Wissen
---
Erklären Sie die Funktionalität von `MPI_Finalize`.
Bereinigt die MPI-Umgebung und beendet die MPI-Kommunikation. Dieser Befehl muss als letzte MPI Funktion aufgerufen werden.
- Ausnahme: `MPI_Finalized`
Signatur:
```c
int MPI_Finalize();
```
Rückgabe: Error Code
---
### Mittel
---
Welche vordefinierten Reduktionsoperationen gibt es?
- `MPI_MAX`: Maximum
- `MPI_MIN`: Minimum
- `MPI_SUM`: Summe
- `MPI_PROD`: Produkt
- `MPI_LAND`: Logisches Und
- `MPI_BAND`: Bitweises Und
- `MPI_LOR`: Logisches Oder
- `MPI_BOR`: Bitweises Oder
- `MPI_LXOR`: Logisches XOR (Exklusiv Oder)
- `MPI_BXOR`: Bitweises XOR (Exklusiv Oder)
- `MPI_MAXLOC`: Maximumwert und Ort
- `MPI_MINLOC`: Minimumwert und Ort
---
Erklären Sie den Begriff Broadcast?
`MPI_Bcast`: Sendet eine Nachricht vom Prozess mit dem Rang "root" an alle anderen Prozesse des Kommunikators (Broadcast)
<img src="https://i.imgur.com/6d9ZhCi.png" alt="MPI_Bcast" width="50%" style="display: block; margin-left: auto; margin-right: auto;">
---
Erklären Sie die Funktionalität von `MPI_Barrier`.
- Barriere-Synchronisation über alle Mitglieder hinweg in einem Kommunikator
- Blockiert den aufrufenden Prozess bis alle anderen auch angekommen sind
---
### Schwer
---
Erläutern Sie, was man unter Deadlock versteht.
- Kommt dann zwischen zwei Prozessen zustande, wenn jeder der beiden Prozesse auf ein Ereignis wartet, dass nur der jeweils andere herbeiführen kann. Sind mehr als zwei Prozesse involviert, so hat man ein "circular chain"
---
Wie können Deadlocks entstehen und wie können diese gelöst werden?
- Kann zum Beispiel entstehen, wenn zwei Prozesse sich gegenseitig, synchron etwas schicken (also synchrone Sends ausführen), dies von dem jeweils anderen empfangen wird und sie dann auf eine Antwort von dem jeweils anderen Porzess warten. So kann ein Deadlock entstehen.
- Um dem entgegen zu wirken, kann man `MPI_Sendrecv` verwenden. Somit kann man Deadlocks vermeiden.
---
Sign in with Wallet
Connect another wallet