Comprendre et résoudre le faux partage dans les applications multithread avec un problème réel que j'ai rencontré

Récemment, je travaillais sur une implémentation multithread d'une fonction pour calculer la distribution de Poisson (amath_pdist). L'objectif était de répartir la charge de travail sur plusieurs threads pour améliorer les performances, en particulier pour les grandes baies. Cependant, au lieu d’atteindre l’accélération attendue, j’ai remarqué un ralentissement significatif à mesure que la taille du tableau augmentait.

Après quelques investigations, j'ai découvert le coupable : faux partage. Dans cet article, j'expliquerai ce qu'est un faux partage, montrerai le code d'origine à l'origine du problème et partagerai les correctifs qui ont conduit à une amélioration substantielle des performances.

---

Le problème : faux partage dans du code multithread

Le

Faux partage se produit lorsque plusieurs threads fonctionnent sur différentes parties d'un tableau partagé, mais que leurs données résident dans la même ligne de cache. Les lignes de cache sont la plus petite unité de données transférée entre la mémoire et le cache du processeur (généralement 64 octets). Si un thread écrit sur une partie d’une ligne de cache, cela invalide la ligne pour les autres threads, même s’ils travaillent sur des données logiquement indépendantes. Cette invalidation inutile entraîne une dégradation significative des performances due au rechargement répété des lignes de cache.

Voici une version simplifiée de mon code original :

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;
}

---

Où le problème se produit

Dans le code ci-dessus :

• Le tableau pdist est partagé entre tous les threads.
• Chaque thread écrit dans une plage spécifique d'index (interval_a à interval_b).
• Aux limites des segments, les index adjacents peuvent résider dans la même ligne de cache. Par exemple, si pdist[249999] et pdist[250000] partagent une ligne de cache, le thread 1 (travaillant sur pdist[249999]) et le thread 2 (travaillant sur pdist[250000]) invalident mutuellement leurs lignes de cache.

Ce problème évoluait mal avec des tableaux plus grands. Même si le problème des limites peut sembler minime, le grand nombre d'itérations a amplifié le coût des invalidations de cache, entraînant des secondes de surcharge inutile.

---

La solution : aligner la mémoire sur les limites des lignes de cache

Pour résoudre le problème, j'ai utilisé posix_memalign pour m'assurer que le tableau pdist était aligné sur les limites de 64 octets. Cela garantit que les threads fonctionnent sur des lignes de cache complètement indépendantes, éliminant ainsi les faux partages.

Voici le code mis à jour :

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;
}

---

Pourquoi est-ce que ça marche ?

1. Mémoire Alignée :

   • En utilisant posix_memalign, le tableau démarre sur une limite de ligne de cache.
   • La plage attribuée à chaque thread s'aligne parfaitement sur les lignes de cache, évitant ainsi les chevauchements.

2. Pas de partage de ligne de cache :

   • Les threads fonctionnent sur des lignes de cache distinctes, éliminant les invalidations causées par un faux partage.

3. Efficacité du cache améliorée :

   • Les modèles d'accès séquentiel à la mémoire s'alignent bien avec les prérécupérateurs de processeur, améliorant encore les performances.

---

Résultats et points à retenir

Après l'application du correctif, le temps d'exécution de la fonction amath_pdist a considérablement diminué. Pour un ensemble de données que je testais, la durée de l'horloge murale est passée de 10,92 secondes à 0,06 seconde.

Leçons clés :

1. Le Faux partage est un problème subtil mais critique dans les applications multithread. Même de petits chevauchements aux limites des segments peuvent dégrader les performances.
2. L'alignement de la mémoire à l'aide de posix_memalign est un moyen simple et efficace de résoudre les faux partages. L'alignement de la mémoire sur les limites des lignes de cache garantit que les threads fonctionnent de manière indépendante.
3. Analysez toujours votre code pour détecter les problèmes liés au cache lorsque vous travaillez avec de grands tableaux ou un traitement parallèle. Des outils comme perf ou valgrind peuvent aider à identifier les goulots d'étranglement.

Merci d'avoir lu !

Pour toute personne curieuse de connaître le code, vous pouvez le trouver ici

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!