En utilisant rand_r dans OpenMP « pour » est plus lent avec 2 fils

Question

Le code suivant fonctionne mieux avec 1 fil que de 2 (en utilisant 4 fils donne accélérer, cependant):

#include <stdlib.h> 
#include <stdio.h> 
#include <omp.h> 

int main(int argc, char **argv) { 
    int n = atoi(argv[1]); 
    int num_threads = atoi(argv[2]); 
    omp_set_num_threads(num_threads); 

    unsigned int *seeds = malloc(num_threads * sizeof(unsigned int)); 
    for (int i = 0; i < num_threads; ++i) { 
    seeds[i] = 42 + i; 
    } 

    unsigned long long sum = 0; 
    double begin_time = omp_get_wtime(); 
    #pragma omp parallel 
    { 
    unsigned int *seedp = &seeds[omp_get_thread_num()]; 
    #pragma omp for reduction(+ : sum) 
    for (int i = 0; i < n; ++i) { 
     sum += rand_r(seedp); 
    } 
    } 
    double end_time = omp_get_wtime(); 

    printf("%fs\n", end_time - begin_time); 
    free(seeds); 
    return EXIT_SUCCESS; 
} 

Sur mon ordinateur portable (2 noyaux , HT activé) Je reçois les résultats suivants:

$ gcc -fopenmp test.c && ./a.out 100000000 1 
0.821497s 
$ gcc -fopenmp test.c && ./a.out 100000000 2 
1.096394s 
$ gcc -fopenmp test.c && ./a.out 100000000 3 
0.933494s 
$ gcc -fopenmp test.c && ./a.out 100000000 4 
0.748038s 

Le problème persiste sans réduction, drand48_r apporte aucune différence, l'ordonnancement dynamique rend les choses encore pire. Cependant, si je remplace le corps de la boucle par quelque chose qui n'est pas lié au hasard, je. e. sum += *seedp + i;, tout fonctionne comme prévu.

Answer 1

Ceci est un exemple de faux partage. En utilisant un tableau de graines sur lequel chaque thread prend un élément, vous forcez les variables logiquement privées à être physiquement situées l'une à côté de l'autre en mémoire. Par conséquent, tous sont dans la même ligne de cache. Cela signifie que bien qu'aucun thread ne tente de modifier la graine d'un autre thread, la ligne de cache elle-même est modifiée par chaque thread à chaque itération. Et le problème réel est que le système ne peut pas détecter les modifications de la variable pour la cohérence de la mémoire cache, uniquement les modifications de la ligne de cache. Par conséquent, à chaque itération pour chaque thread, la ligne de cache a été modifiée par un autre thread et n'est plus valide du point de vue du système. Il doit être rechargé à partir de la mémoire (bien, probablement à partir du cache L3 partagé ici), ce qui conduit à ralentir votre code.

Essayez plutôt celui-ci (non testé):

#include <stdlib.h> 
#include <stdio.h> 
#include <omp.h> 

int main(int argc, char **argv) { 
    int n = atoi(argv[1]); 
    int num_threads = atoi(argv[2]); 
    omp_set_num_threads(num_threads); 

    unsigned long long sum = 0; 
    double begin_time = omp_get_wtime(); 
    #pragma omp parallel 
    { 
    unsigned int seed = 42 + omp_get_thread_num(); 
    #pragma omp for reduction(+ : sum) 
    for (int i = 0; i < n; ++i) { 
     sum += rand_r(&seed); 
    } 
    } 
    double end_time = omp_get_wtime(); 

    printf("%fs\n", end_time - begin_time); 
    return EXIT_SUCCESS; 
}