Eigene globale Summierung mit MPI: Butterfly-Algorithmus in C implementieren

Einführung in die parallele Reduktion mit MPI

In diesem Tutorial implementierst du eine eigene globale Summierungsfunktion (äquivalent zu MPI_Allreduce) unter Verwendung von MPI_Send und MPI_Recv. Der Algorithmus basiert auf der Butterfly-Kommunikation, die in Hypercube-Algorithmen verwendet wird. Dieses Konzept ist nicht nur für Hochleistungsrechnen (HPC) relevant, sondern auch in modernen KI-Trainingspipelines und verteilten Datenbanksystemen zu finden – ähnlich wie bei der Synchronisation von Gradienten in verteiltem Deep Learning. Der Butterfly-Algorithmus ermöglicht eine globale Reduktion in log₂(P) Schritten, wobei P die Anzahl der Prozesse (MPI-Ränge) ist.

Grundlagen: Butterfly-Kommunikationsstruktur

Die Butterfly-Struktur ist ein bekanntes Kommunikationsmuster für Hypercube-Architekturen. In jedem Schritt l (von 0 bis log₂(P)-1) tauscht ein Prozess Nachrichten mit einem Partner aus, dessen Rang sich nur im l-ten Bit unterscheidet. Die Partnerberechnung erfolgt mit der bitweisen XOR-Operation: partner = myid ^ (1 << l).

Stell dir vor, du organisierst ein Turnier: In der ersten Runde paaren sich die Spieler (Prozesse) nach dem niederwertigsten Bit, in der zweiten Runde nach dem zweitniederwertigsten usw. Nach jeder Runde haben die Spieler die Summe ihrer bisherigen Ergebnisse – genau wie bei der globalen Summierung. Dieses Muster wird auch in modernen KI-Frameworks wie TensorFlow oder PyTorch für den Allreduce-Befehl genutzt, um Gradienten über viele GPUs zu mitteln – ein aktuelles Thema angesichts des Booms großer Sprachmodelle.

Hypercube-Vorlage für assoziative Operatoren

Die folgende Vorlage kann für jeden assoziativen Operator OP (z. B. Addition, Multiplikation, Maximum) verwendet werden:

procedure hypercube(myid, input, logP, output)
begin
    mydone := input;
    for l := 0 to logP-1 do
    begin
        partner := myid XOR 2^l;
        send mydone to partner;
        receive hisdone from partner;
        mydone = mydone OP hisdone
    end
    output := mydone
end

In C wird die XOR-Operation mit dem ^-Operator realisiert: partner = myid ^ (1 << l);

Implementierung der global_sum-Funktion in C

Hier ist der vollständige Code für die global_sum-Funktion, die die Butterfly-Kommunikation verwendet. Der Code ist für eine beliebige Anzahl von Prozessen ausgelegt, die eine Zweierpotenz ist (P = 2^l).

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

int nprocs; /* Anzahl Prozesse */
int myid;   /* Eigener Rang */

double global_sum(double partial) {
    double mydone = partial;
    double hisdone;
    int partner;
    int l, logP;

    logP = (int)log2(nprocs);
    for (l = 0; l < logP; l++) {
        partner = myid ^ (1 << l);
        MPI_Send(&mydone, 1, MPI_DOUBLE, partner, 0, MPI_COMM_WORLD);
        MPI_Recv(&hisdone, 1, MPI_DOUBLE, partner, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        mydone = mydone + hisdone;
    }
    return mydone;
}

int main(int argc, char *argv[]) {
    double partial, sum, avg;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    MPI_Comm_size(MPI_COMM_WORLD, &nprocs);

    partial = (double) myid;
    printf("Node %d hat %le\n", myid, partial);
    sum = global_sum(partial);

    if (myid == 0) {
        avg = sum / nprocs;
        printf("Globaler Durchschnitt = %le\n", avg);
    }

    MPI_Finalize();
    return 0;
}

Erklärung des Algorithmus

Die Funktion global_sum implementiert die Hypercube-Vorlage für die Addition. Zunächst wird die Anzahl der benötigten Schritte logP berechnet (log2(nprocs)). In jeder Iteration l wird der Partner über myid ^ (1 << l) bestimmt. Jeder Prozess sendet seinen aktuellen Wert mydone an den Partner und empfängt dessen Wert. Anschließend werden die Werte addiert. Dies wird so oft wiederholt, bis alle Prozesse die globale Summe besitzen.

Wichtig: Damit alle Prozesse am Ende das gleiche Ergebnis haben, muss die Kommunikation in einer bestimmten Reihenfolge ablaufen. Die Verwendung von MPI_Send und MPI_Recv in dieser Schleife gewährleistet, dass keine Deadlocks auftreten, da jeder Prozess sowohl sendet als auch empfängt. Bei größeren Prozesszahlen könnte man MPI_Sendrecv verwenden, aber für dieses Tutorial reicht die einfache Variante.

Testlauf mit 4 und 8 Prozessen

Um die Korrektheit zu überprüfen, starte das Programm mit 4 bzw. 8 Prozessen. Die Ausgabe sollte wie folgt aussehen (Beispiel für 4 Prozesse):

Node 0 hat 0.000000
Node 1 hat 1.000000
Node 2 hat 2.000000
Node 3 hat 3.000000
Globaler Durchschnitt = 1.500000

Die globale Summe ist 0+1+2+3 = 6, der Durchschnitt 6/4 = 1.5. Für 8 Prozesse (Ränge 0-7) ergibt sich die Summe 28 und der Durchschnitt 3.5.

Performance und Skalierbarkeit

Der Butterfly-Algorithmus hat eine Kommunikationskomplexität von O(log P). In der Praxis ist die tatsächliche Leistung jedoch von der Netzwerklatenz und -bandbreite abhängig. Dieses Beispiel eignet sich hervorragend, um Skalierbarkeitsanalysen durchzuführen – ein zentrales Thema in Csci596. Du kannst die Laufzeit für verschiedene Prozesszahlen messen und mit der theoretischen Komplexität vergleichen. Ähnliche Techniken werden in modernen Supercomputern und Cloud-Clustern eingesetzt, etwa bei der Verarbeitung großer Datenmengen in Echtzeit oder beim Training neuronaler Netze.

Erweiterungsmöglichkeiten

Du kannst die Funktion leicht für andere assoziative Operatoren anpassen, z. B. Multiplikation (mydone *= hisdone) oder Maximum (if (hisdone > mydone) mydone = hisdone). Auch die Verwendung von MPI_Allreduce als Referenzimplementierung ist sinnvoll, um die Ergebnisse zu validieren. Für eine produktive Umgebung solltest du jedoch auf die integrierte MPI-Funktion zurückgreifen, da sie optimiert ist.

Hinweis: Dieses Tutorial ist für Studierende des Kurses Csci596 gedacht, die praktische Erfahrung mit MPI und parallelen Algorithmen sammeln möchten. Es ergänzt die Vorlesungsunterlagen zu Hypercube-Algorithmen und Skalierbarkeit.

Fazit

Du hast erfolgreich eine eigene globale Summierungsfunktion mit MPI implementiert, die auf dem Butterfly-Algorithmus basiert. Dieses fundamentale Muster wird in vielen parallelen Anwendungen verwendet – von der wissenschaftlichen Simulation bis hin zur KI. Mit diesem Wissen bist du gerüstet, um komplexere Reduktionsoperationen und verteilte Algorithmen zu verstehen.