Distributed Memory#

Bei Distributed Memory Systemen tauschen sich die Prozessoren über Nachrichten aus. Diese werden mit expliziten Send- und Empfangsbefehlen über ein Netzwerk geschickt. Das Netzwerk ist ein breiter Begriff und kann über verschiedene Technologien abgebildet werden, z.B.:

(Gigabit-)Ethernet oder Spezial-Netzwerke bei verschiedenen Rechnern
Busse auf dem Mainboard bei Multiprozessor-Systemen mit NUMA-Architektur
Virtuelles Netzwerk über Shared Memory bei Multicore-Systemen mit uniformen Speicher

_images/distributedmemory.svg — Fig. 10 Distributed Memory Architektur#

Lange Zeit war die Topologie des Netzwerks ein großes Thema. Die Topologie bestimmt welche Rechner mit welchen anderen Rechner direkt verbunden ist und in Konsequenz welche Verbindungen nur über ein oder mehrere Zwischenschritte indirekt verbunden sind. Dadurch beinflusst ist die Latenz und Bandbreite des Netzwerks:

Latenz: wie lange dauert es bis eine Nachricht von einem Rechner zu einem anderen kommt. Besonders wichtig, wenn viele kleine Nachrichten ausgetauscht werden. Wird durch die Anzahl der benötigten Zwischenschritte stark beeinflusst.
Bandbreite: wie viele Daten können pro Zeiteinheit übertragen werden. Besonders wichtig, wenn große Nachrichten ausgetauscht werden. Wird durch die Geschwindigkeit einer einzelnen Verbindung und die Anzahl der Verbindungen beeinflusst.

Topologien sind heute weniger wichtig geworden, da einige Einschränkungen abgeschwächt sind:

Genügend Rechenpower um Switches zu bauen und damit höhere Vernetzungsgrade
Glasfaser reduziert die Bedeutung von physikalischer Entfernung zwischen Knoten

INFO
Übersicht zu Topologien und deren Eigenschaften:
Lecture 9, Folien 4 - 18, CS267 der UC Berkeley

MPI#

MPI ist ein Standard zur verteilten Ausführung von Programmen. Im Supercomputing ist MPI sehr verbreitet auch in Kombination mit OpenMP und GPU-Programmierung für die Programmierung der einzelnen Nodes. Im breiter gefassten “neuen High Performance Computing” also insbesondere wenn es um Energieeffizienz oder Datenanalyse geht ist die Bedeutung deutlich geringer. Dies liegt unter anderem am sehr niedrigen Abstraktionslevel von MPI. Eine Ausführliche Kritik findet sich unter: https://www.dursi.ca/post/hpc-is-dying-and-mpi-is-killing-it

Aus diesen Gründen halten wir die Darstellung eher kurz und kommen im späteren Verlauf auf Distributed Memory Computing mit Tools auf höherer Abstraktionsebene. Ein ausführlicheres Tutorial zu MPI ist zu finden unter: https://github.com/ljdursi/mpi-tutorial/blob/master/presentation/presentation.md

Erstellen und Ausführen von MPI-Programmen#

MPI bietet eine Reihe von Bibiliotheksfunktionen an. Um Programme zu übersetzen bietet die meisten Installationen ein Hilfsprogramm mpicc an. Dies ruft den C-Compiler mit den passenden Pfaden zu Bibliotheken und Include-Dateien auf. Ebenso gibt es meist ein Hilfsprogramm mpirun oder mpiexec das dafürt sorgt, dass das Programm auf allen Rechenknoten gestartet wird. Die Anzahl der Knoten lässt sich über den Parameter -n <Anzahl der Prozesse> steuern. Je nach Umgebung werden dann auf dem lokalen Rechner oder im Rechencluster entsprechend viele Instanzen des Programms ausgeführt.

Arbeitsaufteilung#

Im Prinzip wird das gleiche MPI-Programm auf allen Knoten gestartet. Um die Arbeit aufzuteilen muss jeder Prozess seinen rank rausfinden - eine fortlaufende Nummerierung der Prozesse in einer Gruppe. Das folgende einfache MPI-Beispielprogramm

initialisiert MPI (MPI_Init)
erfragt die gesamte Anzahl der Prozesse (size)
erfragt die eigene Prozessnummer und den Prozessornamen (rank und len)
gibt ein Helloworld aus mit Angabe der erfragten Informationen
beendet die MPI-Umgebung (MPI_Finalize)

#include <mpi.h>
#include <stdio.h>

int main() {
    MPI_Init(NULL, NULL);
    int size;
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    int rank;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);

    char name[MPI_MAX_PROCESSOR_NAME];
    int len;
    MPI_Get_processor_name(name, &len);

    printf("Hello world from rank %d out of %d (%s)\n", rank, size, name);

    MPI_Finalize();
}

Übersetzt wird das Programm mit mpicc oder z.B. bei MSMPI unter Windows mit gcc mit gcc -I$(MSMPI_INC) -L$(MSMPI_LIB64) -lmsmpi hellopmpi.c. Die Ausführung auf einem einzelnen Multi-Core System:

$ mpirun -n 6 a.out
Hello world from rank 4 out of 6 (fkc.hft-stuttgart.de)
Hello world from rank 1 out of 6 (fkc.hft-stuttgart.de)
Hello world from rank 2 out of 6 (fkc.hft-stuttgart.de)
Hello world from rank 5 out of 6 (fkc.hft-stuttgart.de)
Hello world from rank 0 out of 6 (fkc.hft-stuttgart.de)
Hello world from rank 3 out of 6 (fkc.hft-stuttgart.de)

Kommunikation#

Im Normalfall ist eine Kommunikation zwischen einzelnen Prozessen notwendig und wenn es nur die Zusammenführung der Ergebnisse von trivial parallelisierbaren Einzelberechnungen sind. Die einfachste Form ist die Nutzung von:

MPI_Send(void *data, int count, MPI_Datatype datatype, int dest, int tag, MPI_COMM comm)
MPI_Recv(void *data, int count, MPI_Datatype datatype, int source, int tag, MPI_COMM comm, MPI_Status *status)

Die Daten werden vom Pointer data gelesen (Send) bzw. dorthin geschrieben (Recv). Die Datenmenge bestimmt sich aus der Anzahl der Werte (count) und dem Datentype (datatype, z.B. MPI_DOUBLE).

Das Ziel beim Senden bzw. die Quelle beim Empfangen muss angegeben werden und es werden nur Nachrichten empfangen, die über einstimmen in:

rank (dest oder source)
Prozessgruppe (comm) - in unseren Anwendungen immer MPI_COMM_WORLD
Einem tag das es erlaubt verschiedene Nachrichtentypen zwischen den gleichen Partnern auszutauschen - wenn nicht gewünscht kann hier MPI_ANY_TAG eingetragen werden

MPI_Recv blokciert so lange bis eine entsprechende Nachricht empfangen wurde. MPI_Send blockiert bis die Nachricht zum Zielsystem übertragen wurde - das bedeutet nicht unbedingt, dass der empfangende Prozess sie abgerufen hat.

Beispiel:

#include <mpi.h>
#include <stdio.h>

int main() {
    MPI_Init(NULL, NULL);
    int size;
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    int rank;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);

    if(rank == 0) {
        for(int i=1;i<size;i++) {
            MPI_Send(&i, 1, MPI_INT, i, 0, MPI_COMM_WORLD);
        }
    } else {
        MPI_Status status;
        int received_rank;
        MPI_Recv(&received_rank, 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
        printf("Received %d\n", received_rank);
    }
    MPI_Finalize();
}

Beispiel-Output:

$ mpirun -n 6 a.out
Received 5
Received 1
Received 2
Received 3
Received 4
$

Vorsicht ist geboten mit den blockierenden Aufrufen, damit kein Deadlock generiert wird:

#include <mpi.h>
#include <stdio.h>

int main() {
    MPI_Init(NULL, NULL);
    int size;
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    int rank;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);

    if(size != 2) {
        printf("Example only for two processes\n");
    }
    int partner_rank = 1- rank;

    int message_received;
    MPI_Recv(&message_received, 1, MPI_INT, partner_rank, MPI_ANY_TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    printf("Received %d\n", message_received);
    MPI_Send(&rank, 1, MPI_INT, partner_rank, 0, MPI_COMM_WORLD);

    MPI_Finalize();
}

Hier warten beide Ranks darauf eine Message vom anderen Rank zu bekommen bevor sie selbst eine senden. Dies führt unweigerlich zum Deadlock. Wenn wir die Reihenfolge der Send und Recv Operationen tauschen könnte es trotzdem zum Deadlock kommen, insbesondere wenn es sich um große Nachrichten handelt, die erst vollständig übertragen werden, wenn der Empfänger das passende Recv aufruft. Eine zuverlässige Lösung ergibt sich nur, wenn eine Reihenfolge vorgegeben wird wie z.B.:

Rank 0 empfängt erst und sendet dann
Rank 1 sendet erst und empfängt dann

Dies zeigt auch noch mal die Wichtigkeit für jeden Prozess seinen Rank zu kennen und in welchen Mustern Berechnungen und Kommunikation zu erfolgen hat. Es gibt auch einen kombinierten MPI_Sendrecv-Befehl, wenn zwei Ranks bidirektional Daten austauschen sollen - hier kümmert sich MPI um die Deadlock-Vermeidung.

Weiterhin gibt es Funktionen für die asynchrone (nicht blockierende) Kommunikation.

Collective Communication#

Neben der Punkt-zu-Punkt-Kommunikation mit MPI_Send und MPI_Recv zwischen zwei Prozessen gibt es auch “Collectives”, die Kommunikation in einer gesamten Prozessgruppe beschreiben. Eine Übersicht gibt es im Abschnitt “Globale Kommunikation” unter https://de.wikipedia.org/wiki/Message_Passing_Interface

ÜBUNG: Collective Communication mit MPI

Siehe hier.

HPC Skript

Distributed Memory

Contents