Practical parallel algorithms with MPI - Exam

Aufgabe 1)

Ein populärer Algorithmus zur numerischen Integration verwendet die Monte-Carlo-Methode. Diese Methode basiert auf der Idee, zufällige Punkte in einem bestimmten Bereich zu generieren und zu prüfen, ob diese Punkte innerhalb der zu integrierenden Funktion fallen. Es sei die Aufgabe, die Fläche unter der Funktion f(x) = x² im Bereich von 0 bis 1 näherungsweise zu berechnen. Dabei soll die Anzahl der zu generierenden Punkte N sehr groß gewählt werden, um eine möglichst genaue Näherung zu ermöglichen.

a)

(a) Domänenzerlegung: Beschreibe eine Strategie zur parallelen Implementierung der Monte-Carlo-Integration des Beispiels durch Domänenzerlegung. Gehe dabei insbesondere auf die folgenden Punkte ein:

• Wie kann der Datenbereich sinnvoll aufgeteilt werden?
• Wie würde die Lastverteilung zwischen den Prozessoren erfolgen?
• Welche Art der Kommunikation ist zwischen den Prozessoren erforderlich?

Lösung:

(a) Domänenzerlegung: Die Domänenzerlegung ist eine gängige Strategie, um die Monte-Carlo-Integration parallel umzusetzen. Dabei wird der Integrationsbereich auf mehrere Prozessoren aufgeteilt, sodass jeder Prozessor einen Teilbereich des Problems bearbeiten kann. Hier ist eine detaillierte Beschreibung der Strategie:

• Aufteilung des Datenbereichs: Der Integrationsbereich [0, 1] kann in mehrere Unterintervalle unterteilt werden. Angenommen, es stehen P Prozessoren zur Verfügung, so kann jedes Intervall eine Länge von 1/P haben. Zum Beispiel, wenn P=4, dann könnte der erste Prozessor für das Intervall [0, 0.25], der zweite für [0.25, 0.5], der dritte für [0.5, 0.75] und der vierte für [0.75, 1] zuständig sein. Dadurch wird der Datenbereich in P gleich große Teile unterteilt.
• Lastverteilung zwischen den Prozessoren: Jeder Prozessor erhält eine gleiche Anzahl von zufällig generierten Punkten N/P. Dies sorgt für eine gleichmäßige Lastverteilung und stellt sicher, dass alle Prozessoren etwa gleich viel Arbeit haben. Durch die zufällige Punktgenerierung innerhalb ihres jeweiligen Intervalls führen die Prozessoren jeweils eine eigene Monte-Carlo-Integration durch.
• Kommunikation zwischen den Prozessoren: Nach der Berechnung sendet jeder Prozessor das Ergebnis seiner Integration an einen Hauptprozessor (Master). Der Master sammelt alle Ergebnisse und summiert die einzelnen Integrationswerte auf, um das Gesamtergebnis zu erhalten. Die Kommunikation kann beispielsweise durch MPI (Message Passing Interface) erfolgen, wo jeder Prozessor die Funktion MPI_Send oder MPI_Gather verwendet, um die Zwischenergebnisse an den Master zu senden, der dann mit MPI_Reduce oder MPI_Recv die Ergebnisse empfängt und summiert.

b)

(b) Datenzentrierte Dekomposition: Angenommen, Du verfügst über ein hochgradig paralleles System, bei dem jeder Knoten N/P (P: Anzahl der Prozessoren) Punkte erzeugt und deren Beitrag zur Gesamtfläche berechnet. Erläutere, wie diese Strategie umgesetzt werden kann. Achte dabei besonders auf die folgenden Aspekte:

• Implementiere in Pseudo-Code einen groben Ablauf der Verteilung und Aggregation der Ergebnisse.
• Diskutiere den Kommunikationsaufwand und mögliche Probleme bei der Lastverteilung.
• Erläutere, wie sichergestellt wird, dass alle Prozessoren ihre Ergebnisse korrekt und effizient beitragen.

Lösung:

(b) Datenzentrierte Dekomposition: Bei der datenorientierten Dekomposition wird die Aufgabe, N Punkte zu generieren und deren Beitrag zur Gesamtfläche zu berechnen, auf P Prozessoren aufgeteilt. Jeder Prozessor erzeugt N/P Punkte und berechnet deren Anteil an der Gesamtfläche. Hier ist eine detaillierte Beschreibung, wie diese Strategie umgesetzt werden kann:

• Pseudo-Code:

  PSEUDO-CODE:1. Initialisiere die Anzahl der Punkte N und Prozessoren P2. Jeder Prozessor i (0 ≤ i < P) führt die folgende Aufgabe aus:    a. Generiere N/P Zufallspunkte (x, y) im Bereich [0, 1] × [0, 1]    b. Zähle die Anzahl der Punkte, die unter der Kurve x² liegen (y ≤ x²), und nenne diese Anzahl Zi    c. Berechne den Flächenanteil des Prozessors als Ai = Zi / (N/P)    d. Sendet Ai an den Master-Prozessor3. Der Master-Prozessor empfängt alle Ai Werte und summiert diese auf, um die Gesamtfläche A zu berechnen:    A = Summe(Ai für alle i von 0 bis P-1)4. Ausgabe der approximierten Fläche A

• Kommunikationsaufwand und mögliche Probleme bei der Lastverteilung: Der Kommunikationsaufwand entsteht hauptsächlich beim Senden der lokal berechneten Integrationswerte (Ai) vom Knoten zum Master-Prozessor. Bei einer hohen Anzahl von Prozessoren und großen N könnte dies zu einer Belastung des Kommunikationsnetzwerks führen. Ein weiteres mögliches Problem: Wenn die zufällig generierten Punkte nicht gleichmäßig verteilt sind, könnte dies zu Ungleichgewichten in der Arbeitslast führen. Dies kann jedoch durch die große Anzahl der Punkte N und die zufällige Verteilung der Punkte minimiert werden.
• Sicherstellung der korrekten und effizienten Beitrag der Ergebnisse: Um sicherzustellen, dass alle Prozessoren ihre Ergebnisse korrekt und effizient beitragen:
  • Nutze eine zuverlässige Kommunikationsbibliothek wie MPI, um die Zwischenergebnisse sicher zu versenden.
  • Setze Barrier-Synchronisationen ein, um sicherzustellen, dass alle Prozessoren ihre Berechnungen abgeschlossen haben, bevor der Master die Resultate summiert.
  • Verifiziere die empfangenen Daten auf dem Master-Prozessor, um sicherzustellen, dass alle nötigen Ergebnisse eingegangen sind.

Aufgabe 2)

Du bist ein Softwareentwickler, der ein paralleles Programm mit MPI schreiben möchte. Dein Programm soll die MPI-Umgebung initialisieren, überprüfen, ob sie korrekt initialisiert wurde, und anschließend einige Berechnungen durchführen. Am Ende soll das Programm die MPI-Umgebung ordnungsgemäß beenden und überprüfen, ob sie erfolgreich beendet wurde.

a)

Schreibe ein MPI-Programm, das Folgendes ausführt:

• Initialisieren der MPI-Umgebung unter Verwendung \texttt{MPI\textunderscore Init};
• Überprüfen, ob die MPI-Umgebung erfolgreich initialisiert wurde mit \texttt{MPI\textunderscore Initialized} und Ausgabe einer entsprechenden Nachricht;
• Eine einfache Berechnung auf dem Hauptprozess (z.B., Addition zweier Zahlen);
• Beenden der MPI-Umgebung mit \texttt{MPI\textunderscore Finalize};
• Überprüfen, ob die MPI-Umgebung erfolgreich beendet wurde mit \texttt{MPI\textunderscore Finalized} und Ausgabe einer entsprechenden Nachricht.

Lösung:

Hier ist ein Beispiel für ein MPI-Programm in C, das die beschriebenen Schritte ausführt:

#include <mpi.h>#include <stdio.h>int main(int argc, char** argv) {    int initialized, finalized;    // Initialisieren der MPI-Umgebung    MPI_Init(&argc, &argv);    // Überprüfen, ob die MPI-Umgebung erfolgreich initialisiert wurde    MPI_Initialized(&initialized);    if (initialized) {        printf('MPI wurde erfolgreich initialisiert.');    } else {        printf('Fehler bei der Initialisierung von MPI.');        return -1;    }    // Eine einfache Berechnung auf dem Hauptprozess    int rank;    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    if (rank == 0) {        int a = 5;        int b = 10;        int sum = a + b;        printf('Die Summe von %d und %d ist %d.', a, b, sum);    }    // Beenden der MPI-Umgebung    MPI_Finalize();    // Überprüfen, ob die MPI-Umgebung erfolgreich beendet wurde    MPI_Finalized(&finalized);    if (finalized) {        printf('MPI wurde erfolgreich beendet.');    } else {        printf('Fehler beim Beenden von MPI.');    }    return 0;}

Die Schritte im Programm werden wie folgt durchlaufen:

• MPI-Umgebung wird mit \texttt{MPI\textunderscore Init} initialisiert;
• Überprüfung der Initialisierung mit \texttt{MPI\textunderscore Initialized} und entsprechende Nachrichtenausgabe;
• Durchführen einer einfachen Addition auf dem Hauptprozess (Rang 0);
• Beenden der MPI-Umgebung mit \texttt{MPI\textunderscore Finalize};
• Überprüfung des erfolgreichen Beendens der MPI-Umgebung mit \texttt{MPI\textunderscore Finalized} und Ausgabe einer entsprechenden Nachricht.

b)

Erweitere Dein Programm aus der ersten Teilaufgabe, sodass es auf mehreren Prozessen eine einfache Berechnung durchführt. Jeder Prozess soll die Addition zweier Zahlen durchführen und das Ergebnis an den Hauptprozess senden, der diese Ergebnisse addiert und das Endergebnis ausgibt. Nutze dafür die entsprechenden MPI-Kommunikationsfunktionen wie \texttt{MPI\textunderscore Send} und \texttt{MPI\textunderscore Recv}. Stelle sicher, dass alle Prozesse korrekt synchronisiert sind und die MPI-Umgebung ordnungsgemäß beendet wird.

Lösung:

Hier ist ein erweitertes MPI-Programm in C, das auf mehreren Prozessen eine einfache Berechnung durchführt und die Ergebnisse an den Hauptprozess sendet:

#include <mpi.h>#include <stdio.h>#define NUM_PROCESSES 4int main(int argc, char** argv) {    int initialized, finalized;    int rank, size;    // Initialisieren der MPI-Umgebung    MPI_Init(&argc, &argv);    // Überprüfen, ob die MPI-Umgebung erfolgreich initialisiert wurde    MPI_Initialized(&initialized);    if (initialized) {        printf('MPI wurde erfolgreich initialisiert.');    } else {        printf('Fehler bei der Initialisierung von MPI.');        return -1;    }    // Holen der Anzahl der Prozesse und der Rangk des aktuellen Prozesses    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    MPI_Comm_size(MPI_COMM_WORLD, &size);    if (size != NUM_PROCESSES) {        printf('Dieses Programm erfordert %d Prozesse.', NUM_PROCESSES);        MPI_Finalize();        return -1;    }    int a = rank + 1; // z.B. einzigartiger Wert für jeden Prozess    int b = rank + 2; // z.B. einzigartiger Wert für jeden Prozess    int local_sum = a + b;    printf('Prozess %d: Summe von %d und %d ist %d.', rank, a, b, local_sum);    int global_sum = 0;    if (rank != 0) {        MPI_Send(&local_sum, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);    } else {        global_sum = local_sum;        for (int i = 1; i < size; i++) {            int temp_sum;            MPI_Recv(&temp_sum, 1, MPI_INT, i, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);            global_sum += temp_sum;        }        printf('Gesamtsumme aller Prozesse ist %d.', global_sum);    }    // Beenden der MPI-Umgebung    MPI_Finalize();    // Überprüfen, ob die MPI-Umgebung erfolgreich beendet wurde    MPI_Finalized(&finalized);    if (finalized) {        printf('MPI wurde erfolgreich beendet.');    } else {        printf('Fehler beim Beenden von MPI.');    }    return 0;}

Die Schritte im Programm werden wie folgt durchlaufen:

• MPI-Umgebung wird mit \texttt{MPI\textunderscore Init} initialisiert;
• Überprüfung der Initialisierung mit \texttt{MPI\textunderscore Initialized} und entsprechende Nachrichtenausgabe;
• Jeder Prozess führt eine einfache Addition durch und gibt das Ergebnis aus;
• Alle Prozesse senden ihr Ergebnis an den Hauptprozess (Rang 0) mit \texttt{MPI\textunderscore Send};
• Der Hauptprozess empfängt die Ergebnisse mit \texttt{MPI\textunderscore Recv} und berechnet die Gesamtsumme;
• Ausgabe der Gesamtsumme durch den Hauptprozess;
• Beenden der MPI-Umgebung mit \texttt{MPI\textunderscore Finalize};
• Überprüfung des erfolgreichen Beendens der MPI-Umgebung mit \texttt{MPI\textunderscore Finalized} und Ausgabe einer entsprechenden Nachricht.

Aufgabe 3)

Betrachten wir ein Szenario, in dem vier Prozesse (P0, P1, P2 und P3) in einer verteilten Umgebung implementiert werden. Jedes dieser Prozesse führt Punkt-zu-Punkt-Kommunikation mit den anderen Prozessen durch, um eine Berechnung zu koordinieren. P0 sendet Daten an P1 und empfängt eine Antwort, während P2 Daten an P3 sendet und ebenfalls eine Antwort erhält. Alle Kommunikationen sollen unter Verwendung von MPI-Funktionen erfolgen.

a)

Implementiere die Funktionalität für die Prozesskommunikation wie oben beschrieben. Stelle sicher, dass Du MPI_Send und MPI_Recv in Deinen Implementationen verwendest und erläutere die Gründe für die getroffenen Designentscheidungen. Achte auf die korrekte Verwendung von rank und tag, sowie MPI_Status zur Überprüfung des Empfangs.

Lösung:

Die Implementierung der Prozesskommunikation unter Verwendung von MPI-Funktionen kann wie folgt durchgeführt werden. Hierbei verwenden wir MPI_Send und MPI_Recv, um Nachrichten zwischen den Prozessen zu senden und zu empfangen. Wichtig ist dabei die korrekte Verwendung von rank zur Identifikation der Prozesse, sowie tag zur Kennzeichnung der Nachrichten. MPI_Status wird genutzt, um den Status des Empfangs einer Nachricht zu überprüfen.

• Gründe für die Designentscheidungen
  • Die Nutzung von MPI_Send und MPI_Recv ermöglicht eine direkte Punkt-zu-Punkt-Kommunikation zwischen den Prozessen.
  • Die Verwendung von rank stellt sicher, dass Nachrichten an die richtigen Prozesse gesendet und von diesen empfangen werden können.
  • Mit tag können die Nachrichten eindeutig identifiziert und verarbeitet werden.
  • Das Überprüfen des Empfangsstatus mit MPI_Status stellt sicher, dass keine Nachrichten verloren gehen.

 #include <mpi.h>#include <stdio.h>int main(int argc, char** argv) {    MPI_Init(&argc, &argv);    int rank;    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    if (rank == 0) {        int data_to_send = 100;        MPI_Send(&data_to_send, 1, MPI_INT, 1, 0, MPI_COMM_WORLD);        printf("P0 hat Daten an P1 gesendet: %d", data_to_send);        int data_received;        MPI_Recv(&data_received, 1, MPI_INT, 1, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);        printf("P0 hat Antwort von P1 empfangen: %d", data_received);    } else if (rank == 1) {        int received_data;        MPI_Recv(&received_data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);        printf("P1 hat Daten von P0 empfangen: %d", received_data);        int response_data = received_data * 2;        MPI_Send(&response_data, 1, MPI_INT, 0, 1, MPI_COMM_WORLD);        printf("P1 hat Antwort an P0 gesendet: %d", response_data);    } else if (rank == 2) {        int data_to_send = 200;        MPI_Send(&data_to_send, 1, MPI_INT, 3, 0, MPI_COMM_WORLD);        printf("P2 hat Daten an P3 gesendet: %d", data_to_send);        int data_received;        MPI_Recv(&data_received, 1, MPI_INT, 3, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);        printf("P2 hat Antwort von P3 empfangen: %d", data_received);    } else if (rank == 3) {        int received_data;        MPI_Recv(&received_data, 1, MPI_INT, 2, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);        printf("P3 hat Daten von P2 empfangen: %d", received_data);        int response_data = received_data * 3;        MPI_Send(&response_data, 1, MPI_INT, 2, 1, MPI_COMM_WORLD);        printf("P3 hat Antwort an P2 gesendet: %d", response_data);    }    MPI_Finalize();    return 0;}

Die oben stehende Implementierung zeigt, wie die Prozesse P0, P1, P2 und P3 miteinander kommunizieren. P0 und P1 sowie P2 und P3 tauschen dabei jeweils Daten aus und senden nach der Verarbeitung eine Antwort zurück. Die Nutzung von MPI_Send und MPI_Recv ermöglicht eine effiziente und strukturierte Kommunikation zwischen den Prozessen. Der korrekte Einsatz von rank, tag und MPI_Status stellt sicher, dass die Nachrichten an die richtigen Empfänger gelangen und ordnungsgemäß verarbeitet werden.

b)

Diskutiere die möglichen Deadlock-Szenarien, die auftreten könnten, falls die Reihenfolge der Send- und Empfangsbefehle nicht beachtet wird. Zeige anhand eines konkreten Beispiels, wie Du einen Deadlock vermeidest, indem Du Blockierende und Nicht-Blockierende Kommunikationsbefehle kombinierst. Erstelle eine Code-Abschnitt, der die Übertragung der Daten so organisiert, dass kein Deadlock auftritt.

Lösung:

Ein Deadlock kann leicht auftreten, wenn beide beteiligten Prozesse gleichzeitig Send- und Empfangsbefehle ausführen und dabei aufeinander warten. Angenommen, P0 und P1 senden und empfangen gleichzeitig Nachrichten, ohne die Reihenfolge zu beachten, kann es zu einer Pattsituation kommen. Hier ein konkretes Beispiel:

• Deadlock-Szenario
  • P0 sendet eine Nachricht an P1 und wartet auf eine Antwort.
  • P1 sendet ebenfalls eine Nachricht an P0 und wartet auf eine Antwort.
  • Beide Prozesse sind blockiert, weil sie darauf warten, dass der andere Prozess seine Nachricht empfängt und eine Antwort zurücksendet.

Dies kann vermieden werden, indem blockierende und nicht-blockierende Kommunikationsbefehle kombiniert werden.

• Vermeidung eines Deadlocks durch Kombination von blockierenden und nicht-blockierenden Befehlen
  • Setze MPI_Isend (nicht-blockierendes Senden) und MPI_Irecv (nicht-blockierendes Empfangen) ein, um sicherzustellen, dass Prozesse nicht aufeinander warten.
  • Verwende MPI_Wait, um zu überprüfen, ob die Kommunikation abgeschlossen ist.

 #include <mpi.h>#include <stdio.h>int main(int argc, char** argv) {    MPI_Init(&argc, &argv);    int rank;    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    MPI_Request request_send, request_recv;    MPI_Status status;    if (rank == 0) {        int data_to_send = 100;        int data_received;        MPI_Isend(&data_to_send, 1, MPI_INT, 1, 0, MPI_COMM_WORLD, &request_send);        MPI_Irecv(&data_received, 1, MPI_INT, 1, 1, MPI_COMM_WORLD, &request_recv);        MPI_Wait(&request_send, &status);        MPI_Wait(&request_recv, &status);        printf("P0 hat Daten an P1 gesendet und Antwort empfangen: %d", data_received);    } else if (rank == 1) {        int received_data;        int response_data;        MPI_Irecv(&received_data, 1, MPI_INT, 0, 0, MPI_COMM_WORLD, &request_recv);        response_data = received_data * 2;        MPI_Isend(&response_data, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &request_send);        MPI_Wait(&request_recv, &status);        MPI_Wait(&request_send, &status);        printf("P1 hat Daten von P0 empfangen und Antwort gesendet: %d", response_data);    } else if (rank == 2) {        int data_to_send = 200;        int data_received;        MPI_Isend(&data_to_send, 1, MPI_INT, 3, 0, MPI_COMM_WORLD, &request_send);        MPI_Irecv(&data_received, 1, MPI_INT, 3, 1, MPI_COMM_WORLD, &request_recv);        MPI_Wait(&request_send, &status);        MPI_Wait(&request_recv, &status);        printf("P2 hat Daten an P3 gesendet und Antwort empfangen: %d", data_received);    } else if (rank == 3) {        int received_data;        int response_data;        MPI_Irecv(&received_data, 1, MPI_INT, 2, 0, MPI_COMM_WORLD, &request_recv);        MPI_Isend(&response_data, 1, MPI_INT, 2, 1, MPI_COMM_WORLD, &request_send);        MPI_Wait(&request_recv, &status);        response_data = received_data * 3;        MPI_Isend(&response_data, 1, MPI_INT, 2, 1, MPI_COMM_WORLD, &request_send);        MPI_Wait(&request_send, &status);        printf("P3 hat Daten von P2 empfangen und Antwort gesendet: %d", response_data);    }    MPI_Finalize();    return 0;}

In diesem Code-Beispiel wird durch die Verwendung von MPI_Isend und MPI_Irecv (nicht-blockierende Kommunikation) sowie MPI_Wait sichergestellt, dass die Prozesse nicht in einer Pattsituation enden. Somit wird ein Deadlock vermieden und die Kommunikation kann erfolgreich abgeschlossen werden.

Aufgabe 4)

Angenommen, Du hast ein paralleles Programm, das in MPI geschrieben ist. Das Programm führt eine Vielzahl von kollektiven Kommunikationsoperationen aus, um Daten zwischen Prozessen zu verteilen und zu sammeln. Diese Operationen sind wesentlich für die Synchronisation und den Datenaustausch in parallelen Algorithmen. Dir stehen folgende kollektive MPI-Operationen zur Verfügung:

• Broadcast (MPI_Bcast)
• Scatter (MPI_Scatter)
• Gather (MPI_Gather)
• Allgather (MPI_Allgather)
• Alltoall (MPI_Alltoall)
• Reduce (MPI_Reduce)
• Allreduce (MPI_Allreduce)

a)

Erkläre die Hauptunterschiede zwischen MPI_Bcast und MPI_Scatter. In welchen Szenarien würdest Du die eine Operation der anderen vorziehen? Begründe Deine Antwort mit einem Beispiel, idealerweise unter Verwendung von C oder Python. Implementiere ein einfaches Beispielprogramm, das zeigt, wie man mit MPI_Bcast ein Array von einem Prozess an alle anderen verteilt.

Lösung:

Die Hauptunterschiede zwischen MPI_Bcast und MPI_Scatter liegen in der Art und Weise, wie die Daten von einem Prozess auf andere Prozesse verteilt werden:

• MPI_Bcast: Diese Operation sendet eine Nachricht von einem Ausgangsprozess (Root-Prozess) an alle anderen Prozesse in der Kommunikator-Gruppe. Jeder Prozess erhält eine Kopie derselben Nachricht. Man verwendet MPI_Bcast, wenn alle Prozesse die gleichen Daten benötigen. Beispiel: Man möchte ein Konfigurationsobjekt an alle Worker-Prozesse schicken. In diesem Fall eignet sich MPI_Bcast, da jeder Prozess dieselbe Konfiguration benötigt.
• MPI_Scatter: Diese Operation teilt ein Datenblock aus dem Root-Prozess in gleich große Teile und sendet je einen Teil davon an die anderen Prozesse. Jeder Prozess erhält einen anderen Teil der Daten. Man verwendet MPI_Scatter, wenn jeder Prozess nur einen Teil der Daten benötigt. Beispiel: Man hat einen großen Datensatz, der auf verschiedene Worker-Prozesse zum parallelen Bearbeiten aufgeteilt werden soll. Hier eignet sich MPI_Scatter, da jeder Prozess nur einen Teil des gesamten Datensatzes benötigt und verarbeitet.

Hier ist ein einfaches Beispielprogramm in Python, das zeigt, wie man mit MPI_Bcast ein Array von einem Prozess an alle anderen verteilt:

  import mpi4py.MPI as MPI import numpy as np comm = MPI.COMM_WORLD rank = comm.Get_rank() size = comm.Get_size() root = 0 if rank == root: data = np.arange(10, dtype=int) else: data = np.empty(10, dtype=int) comm.Bcast(data, root=root) print(f'Rank {rank} empfing Daten: {data}')  

In diesem Programm:

• Der Root-Prozess (im Beispiel als Prozess 0 definiert) erzeugt ein Array mit dem Namen data, das die Werte von 0 bis 9 enthält.
• Alle anderen Prozesse initialisieren ein leeres Array, das für die empfangenen Daten genutzt werden soll.
• MPI_Bcast wird verwendet, um das Array data vom Root-Prozess an alle anderen Prozesse zu senden.
• Jeder Prozess druckt das empfangene Array aus, um zu zeigen, dass er die gleichen Daten erhalten hat.

b)

Nehmen wir an, Du hast eine Matrix mit den Abmessungen 4x4 gleichmäßig auf 4 Prozesse aufgeteilt. Jeder Prozess enthält eine Zeile der Matrix. Erkläre, wie Du mithilfe von MPI_Gather alle Zeilen der Matrix beim Root-Prozess sammelst. Implementiere ein C- oder Python-Programm, das dies demonstriert. Erkläre zudem, wie sich diese Operation von MPI_Allgather unterscheidet, und gebe an, wann welche Operation vorteilhaft wäre.

Lösung:

Um eine Matrix mit den Abmessungen 4x4 mithilfe von MPI_Gather beim Root-Prozess zu sammeln, wenn jeder Prozess eine Zeile der Matrix enthält, folgt man diesen Schritten:

• Jeder Prozess initialisiert das Teilstück der Matrix, das er besitzt. In diesem Fall ist es eine Zeile mit 4 Elementen.
• Verwende MPI_Gather, um alle Zeilen im Root-Prozess zu sammeln und die vollständige Matrix zu rekonstruieren.

Mithilfe von MPI_Gather wird jede Zeile an den Root-Prozess gesendet, wodurch dieser die gesamte Matrix zusammenfügen kann.

Hier ist ein Beispielprogramm in Python:

  from mpi4py import MPI import numpy as np comm = MPI.COMM_WORLD rank = comm.Get_rank() size = comm.Get_size() root = 0 # Initialisiere die lokale Zeile, die jeder Prozess besitzt local_data = np.array([rank*4 + i for i in range(4)], dtype=int) print(f'Rank {rank} hat die lokale Zeile: {local_data}') # Initialisiere eine Matrix nur im Root-Prozess, um die gesammelten Daten zu speichern if rank == root: gathered_data = np.empty(16, dtype=int) else: gathered_data = None # Sammle alle Zeilen der Matrix im Root-Prozess comm.Gather(local_data, gathered_data, root=root) if rank == root: gathered_data = gathered_data.reshape(4, 4) print(f'Rank {rank} hat die gesammelte Matrix:{gathered_data}')  

In diesem Programm:

• Jeder Prozess initialisiert seine Zeile der Matrix, die Werte von rank*4 bis rank*4 + 3 enthält.
• Der Root-Prozess (Prozess 0) initialisiert gathered_data, ein Array, das alle gesammelten Zeilen enthält.
• MPI_Gather wird verwendet, um die Zeilen der Matrix im Root-Prozess zu sammeln.
• Wenn der Root-Prozess die gesammelten Daten erhält, formatiert er diese in eine 4x4-Matrix um und druckt sie aus.

Unterschied zu MPI_Allgather:

• MPI_Allgather funktioniert ähnlich wie MPI_Gather, aber anstatt die gesammelten Daten nur an den Root-Prozess zu senden, wird das Ergebnis an alle Prozesse im Kommunikator verteilt.
• Vorteile:
  • Verwende MPI_Gather, wenn nur der Root-Prozess das vollständige Ergebnis benötigt.
  • Verwende MPI_Allgather, wenn alle Prozesse die kompletten gesammelten Daten benötigen.

c)

Angenommen, jeder Prozess in einem parallelen System berechnet einen Teilbetrag für eine bestimmte Funktion. Beschreibe, wie Du mit MPI_Reduce die Berechnungen zu einem Gesamtergebnis zusammenführen kannst. Verwende dabei die Summe als Aggregationsoperation. Implementiere dies in C oder Python und erläutere, wie sich eine MPI_Allreduce-Operation hiervon unterscheidet. Welche Vorteile bietet MPI_Allreduce in einem realen Anwendungsfall?

Lösung:

Um mit MPI_Reduce die Berechnungen zu einem Gesamtergebnis zusammenzuführen, können wir die Summe als Aggregationsoperation verwenden. Das bedeutet, dass jeder Prozess einen Teilbetrag berechnet und MPI_Reduce diese Teilbeträge zu einem Gesamtergebnis zusammenführt, das dann beim Root-Prozess verfügbar ist.

Hier ist ein Python-Beispiel, das zeigt, wie man MPI_Reduce verwendet, um die Teilbeträge zu summieren:

  from mpi4py import MPI comm = MPI.COMM_WORLD rank = comm.Get_rank() size = comm.Get_size() # Jeder Prozess berechnet seinen Teilbetrag (z.B. rank + 1) local_sum = rank + 1 print(f'Rank {rank} hat Teilbetrag: {local_sum}') # Gesamtergebnis wird im Root-Prozess gesammelt und berechnet total_sum = comm.reduce(local_sum, op=MPI.SUM, root=0) if rank == 0: print(f'Gesamtergebnis: {total_sum}')  

In diesem Beispiel:

• Jeder Prozess berechnet seinen Teilbetrag. In diesem Fall ist es einfach der Wert von rank + 1.
• MPI_Reduce wird verwendet, um alle Teilbeträge zu summieren. Das Ergebnis wird im Root-Prozess (Prozess 0) gespeichert.
• Wenn Rank 0 die Gesamtsumme erhält, druckt er das Gesamtergebnis aus.

Unterschied zu MPI_Allreduce:

• MPI_Allreduce ist ähnlich wie MPI_Reduce, jedoch wird das Ergebnis der Reduktionsoperation an alle Prozesse im Kommunikator gesendet, nicht nur an den Root-Prozess.

Vorteile von MPI_Allreduce:

• MPI_Allreduce ist nützlich, wenn alle Prozesse das Gesamtergebnis der Reduktion benötigen. Dies spart Kommunikationsaufwand, da das Ergebnis direkt an alle verteilt wird, anstatt dass jeder Prozess zusätzliche Kommunikation mit dem Root-Prozess durchführen muss.

Ein Beispiel für MPI_Allreduce in Python:

  from mpi4py import MPI comm = MPI.COMM_WORLD rank = comm.Get_rank() size = comm.Get_size() # Jeder Prozess berechnet seinen Teilbetrag (z.B. rank + 1) local_sum = rank + 1 print(f'Rank {rank} hat Teilbetrag: {local_sum}') # Gesamtergebnis wird von allen Prozessen empfangen total_sum = comm.allreduce(local_sum, op=MPI.SUM) print(f'Rank {rank} sieht Gesamtergebnis: {total_sum}')  

In diesem Beispiel:

• Jeder Prozess berechnet seinen Teilbetrag genauso wie bei MPI_Reduce.
• MPI_Allreduce wird verwendet, um alle Teilbeträge zu summieren und das Ergebnis an alle Prozesse zu senden.
• Jeder Prozess druckt das Gesamtergebnis aus, das er durch MPI_Allreduce erhalten hat.