Verwendung rand_r in OpenMP 'für' langsamer mit 2 Fäden

Question

Der folgende Code führt mit 1 Faden besser als bei 2 (4 Threads gibt zu beschleunigen, obwohl):

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

Auf dem Laptop (2 Adern HT, aktiviert) bekomme ich folgende Ergebnisse:

$ 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 

Das Problem weiterhin besteht, ohne Reduktion bringt drand48_r keinen Unterschied, dynamisches Scheduling macht die Sache noch schlimmer. Wenn ich jedoch den Körper der Schleife durch etwas, das nicht zufällig verbunden ist, ersetze, d. H. e. sum += *seedp + i;, alles funktioniert wie erwartet.

Answer 1

Dies ist ein Lehrbuchbeispiel für die Weitergabe von falschen Daten. Wenn Sie ein Array von Seeds verwenden, auf denen jeder Thread ein Element enthält, erzwingen Sie, dass die logisch privaten Variablen physisch nebeneinander im Speicher angeordnet sind. Daher befinden sich alle in der gleichen Cache-Zeile. Dies bedeutet, dass, obwohl kein Thread versucht, den Startwert eines anderen Threads zu ändern, die Cache-Zeile selbst von jedem Thread bei jeder Iteration geändert wird. Und das eigentliche Problem besteht darin, dass das System die Änderungen der Variablen für die Cache-Kohärenz nicht erkennen kann, sondern nur Änderungen der Cache-Zeile. Daher wurde die Cachezeile bei jeder Iteration für jeden Thread von einem anderen Thread geändert und ist aus Sicht des Systems nicht mehr gültig. Es muss aus dem Speicher neu geladen werden (sehr wahrscheinlich aus dem freigegebenen L3-Cache), was zu einer Verlangsamung des Codes führt.

versuchen diese statt (nicht getestet):

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