Verstehen und Lösen falscher Freigaben in Multithread-Anwendungen anhand eines tatsächlichen Problems, das ich hatte

Vor kurzem habe ich an einer Multithread-Implementierung einer Funktion zur Berechnung der Poisson-Verteilung (amath_pdist) gearbeitet. Ziel war es, die Arbeitslast auf mehrere Threads aufzuteilen, um die Leistung insbesondere bei großen Arrays zu verbessern. Anstatt jedoch die erwartete Beschleunigung zu erreichen, bemerkte ich mit zunehmender Größe des Arrays eine deutliche Verlangsamung.

Nach einigen Nachforschungen habe ich den Schuldigen entdeckt: falsches Teilen. In diesem Beitrag erkläre ich, was falsches Teilen ist, zeige den ursprünglichen Code, der das Problem verursacht, und teile die Korrekturen, die zu einer erheblichen Leistungsverbesserung geführt haben.

Das Problem: Falsches Teilen in Multithread-Code

Falsches Teilen tritt auf, wenn mehrere Threads an verschiedenen Teilen eines gemeinsam genutzten Arrays arbeiten, sich ihre Daten jedoch in derselben Cache-Zeile befinden. Cache-Zeilen sind die kleinste Dateneinheit, die zwischen Speicher und CPU-Cache übertragen wird (normalerweise 64 Byte). Wenn ein Thread in einen Teil einer Cache-Zeile schreibt, macht er die Zeile für andere Threads ungültig – selbst wenn diese an logisch unabhängigen Daten arbeiten. Diese unnötige Ungültigmachung führt zu erheblichen Leistungseinbußen aufgrund des wiederholten Neuladens von Cache-Zeilen.

Hier ist eine vereinfachte Version meines Originalcodes:

void *calculate_pdist_segment(void *data) {
    struct pdist_segment *segment = (struct pdist_segment *)data;
    size_t interval_a = segment->interval_a, interval_b = segment->interval_b;
    double lambda = segment->lambda;
    int *d = segment->data;

    for (size_t i = interval_a; i < interval_b; i++) {
        segment->pdist[i] = pow(lambda, d[i]) * exp(-lambda) / tgamma(d[i] + 1);
    }
    return NULL;
}

double *amath_pdist(int *data, double lambda, size_t n_elements, size_t n_threads) {
    double *pdist = malloc(sizeof(double) * n_elements);
    pthread_t threads[n_threads];
    struct pdist_segment segments[n_threads];
    size_t step = n_elements / n_threads;

    for (size_t i = 0; i < n_threads; i++) {
        segments[i].data = data;
        segments[i].lambda = lambda;
        segments[i].pdist = pdist;
        segments[i].interval_a = step * i;
        segments[i].interval_b = (i == n_threads - 1) ? n_elements : (step * (i + 1));
        pthread_create(&threads[i], NULL, calculate_pdist_segment, &segments[i]);
    }

    for (size_t i = 0; i < n_threads; i++) {
        pthread_join(threads[i], NULL);
    }

    return pdist;
}

Wo das Problem auftritt

Im obigen Code:

• Das Array pdist wird von allen Threads gemeinsam genutzt.
• Jeder Thread schreibt in einen bestimmten Bereich von Indizes (Intervall_a bis Intervall_b).
• An Segmentgrenzen können sich benachbarte Indizes in derselben Cache-Zeile befinden. Wenn sich beispielsweise pdist[249999] und pdist[250000] eine Cache-Zeile teilen, machen Thread 1 (arbeitet an pdist[249999]) und Thread 2 (arbeitet an pdist[250000]) gegenseitig ihre Cache-Zeilen ungültig.

Dieses Problem ließ sich bei größeren Arrays schlecht skalieren. Obwohl das Grenzproblem klein erscheinen mag, erhöhte die schiere Anzahl der Iterationen die Kosten für Cache-Ungültigmachungen, was zu unnötigem Overhead von Sekunden führte.

Die Lösung: Speicher an Cache-Zeilengrenzen ausrichten

Um das Problem zu beheben, habe ich posix_memalign verwendet, um sicherzustellen, dass das pdist-Array an 64-Byte-Grenzen ausgerichtet war. Dies garantiert, dass Threads auf völlig unabhängigen Cache-Zeilen arbeiten, wodurch falsches Teilen vermieden wird.

Hier ist der aktualisierte Code:

double *amath_pdist(int *data, double lambda, size_t n_elements, size_t n_threads) {
    double *pdist;
    if (posix_memalign((void **)&pdist, 64, sizeof(double) * n_elements) != 0) {
        perror("Failed to allocate aligned memory");
        return NULL;
    }

    pthread_t threads[n_threads];
    struct pdist_segment segments[n_threads];
    size_t step = n_elements / n_threads;

    for (size_t i = 0; i < n_threads; i++) {
        segments[i].data = data;
        segments[i].lambda = lambda;
        segments[i].pdist = pdist;
        segments[i].interval_a = step * i;
        segments[i].interval_b = (i == n_threads - 1) ? n_elements : (step * (i + 1));
        pthread_create(&threads[i], NULL, calculate_pdist_segment, &segments[i]);
    }

    for (size_t i = 0; i < n_threads; i++) {
        pthread_join(threads[i], NULL);
    }

    return pdist;
}

Warum funktioniert das?

1. Ausgerichteter Speicher:

   • Mit posix_memalign beginnt das Array an einer Cache-Zeilengrenze.
   • Der jedem Thread zugewiesene Bereich wird genau an den Cache-Zeilen ausgerichtet und verhindert so Überlappungen.

2. Kein Cache-Line-Sharing:

   • Threads arbeiten auf unterschiedlichen Cache-Zeilen, wodurch Ungültigmachungen durch falsches Teilen vermieden werden.

3. Verbesserte Cache-Effizienz:

   • Sequentielle Speicherzugriffsmuster passen gut zu CPU-Prefetchern und steigern so die Leistung weiter.

Ergebnisse und Erkenntnisse

Nach der Anwendung des Fixes sank die Laufzeit der Funktion amath_pdist erheblich. Für einen Datensatz, den ich testete, sank die Zeit der Wanduhr von 10,92 Sekunden auf 0,06 Sekunden.

Wichtige Lektionen:

1. False Sharing ist ein subtiles, aber kritisches Problem in Multithread-Anwendungen. Selbst kleine Überlappungen an Segmentgrenzen können die Leistung beeinträchtigen.
2. Speicherausrichtung mit posix_memalign ist eine einfache und effektive Möglichkeit, falsches Teilen zu lösen. Durch die Ausrichtung des Speichers an den Cache-Zeilengrenzen wird sichergestellt, dass Threads unabhängig voneinander arbeiten.
3. Analysieren Sie Ihren Code immer auf Cache-bezogene Probleme, wenn Sie mit großen Arrays oder paralleler Verarbeitung arbeiten. Tools wie Perf oder Valgrind können dabei helfen, Engpässe zu lokalisieren.

Danke fürs Lesen!

Wer neugierig auf den Code ist, kann ihn hier finden

Das obige ist der detaillierte Inhalt vonVerstehen und Lösen falscher Freigaben in Multithread-Anwendungen anhand eines tatsächlichen Problems, das ich hatte. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!