OpenMP: bajo rendimiento de las matrices de pila (las matrices de pila funcionan bien)

Question

Soy un usuario de OpenMP bastante experimentado, pero acabo de encontrarme en un problema desconcertante, y tengo la esperanza de que alguien aquí pueda ayudar. El problema es que un algoritmo simple de hash funciona bien para las matrices asignadas a la pila, pero deficiente para las matrices en el montón.

El siguiente ejemplo utiliza i% M (i módulo M) para contar cada M-ésimo entero en el elemento de matriz respectivo. Para simplificar, imagine N = 1000000, M = 10. Si N% M == 0, entonces el resultado debería ser que cada elemento de contenedores [] es igual a N/M:

#pragma omp for 
    for (int i=0; i<N; i++) 
    bins[ i%M ]++; 

bins array [] es privada para cada hilo (resultados de suma I de todas las discusiones en una sección crítica después).

Cuando bins [] está asignado en la pila, el programa funciona muy bien, con una escala de rendimiento proporcionalmente al número de núcleos.

Sin embargo, si los contenedores [] están en el montón (el puntero a los contenedores [] está en la pila), el rendimiento disminuye drásticamente. ¡Y ese es un gran problema!

Quiero agrupar en paralelo (hash) ciertos datos en matrices de montón con OpenMP, y este es un golpe de rendimiento importante.

Definitivamente no es algo tonto como todos los hilos que intentan escribir en la misma área de memoria. Esto se debe a que cada subproceso tiene su propia matriz de bins [], los resultados son correctos con los bins asignados tanto en pila como en pila, y no hay diferencia en el rendimiento para ejecuciones de subproceso único. Reproduje el problema en diferentes hardware (Intel Xeon y AMD Opteron), con compiladores GCC e Intel C++. Todas las pruebas fueron en Linux (Ubuntu y RedHat).

No parece haber ninguna razón por la que el buen rendimiento de OpenMP deba limitarse a las matrices de pila.

¿Alguna conjetura? ¿Tal vez el acceso de los hilos al montón pasa a través de algún tipo de puerta de enlace compartida en Linux? ¿Cómo arreglo eso?

programa completo para jugar con es a continuación:

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

int main(const int argc, const char* argv[]) 
{ 
    const int N=1024*1024*1024; 
    const int M=4; 
    double t1, t2; 
    int checksum=0; 

    printf("OpenMP threads: %d\n", omp_get_max_threads()); 

    ////////////////////////////////////////////////////////////////// 
    // Case 1: stack-allocated array 
    t1=omp_get_wtime(); 
    checksum=0; 
#pragma omp parallel 
    { // Each openmp thread should have a private copy of 
    // bins_thread_stack on the stack: 
    int bins_thread_stack[M]; 
    for (int j=0; j<M; j++) bins_thread_stack[j]=0; 
#pragma omp for 
    for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
     const int j=i%M; 
     bins_thread_stack[j]++; 
     } 
#pragma omp critical 
    for (int j=0; j<M; j++) checksum+=bins_thread_stack[j]; 
    } 
    t2=omp_get_wtime(); 
    printf("Time with stack array: %12.3f sec, checksum=%d (must be %d).\n", t2-t1, checksum, N); 
    ////////////////////////////////////////////////////////////////// 

    ////////////////////////////////////////////////////////////////// 
    // Case 2: heap-allocated array 
    t1=omp_get_wtime(); 
    checksum=0; 
    #pragma omp parallel 
    { // Each openmp thread should have a private copy of 
    // bins_thread_heap on the heap: 
    int* bins_thread_heap=(int*)malloc(sizeof(int)*M); 
    for (int j=0; j<M; j++) bins_thread_heap[j]=0; 
    #pragma omp for 
    for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
     const int j=i%M; 
     bins_thread_heap[j]++; 
     } 
    #pragma omp critical 
    for (int j=0; j<M; j++) checksum+=bins_thread_heap[j]; 
    free(bins_thread_heap); 
    } 
    t2=omp_get_wtime(); 
    printf("Time with heap array: %12.3f sec, checksum=%d (must be %d).\n", t2-t1, checksum, N); 
    ////////////////////////////////////////////////////////////////// 

    return 0; 
} 

salidas de ejemplo del programa son a continuación:

para OMP_NUM_THREADS = 1

OpenMP threads: 1 
Time with stack array: 2.973 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array: 3.091 sec, checksum=1073741824 (must be 1073741824). 

y para OMP_NUM_THREADS = 10

OpenMP threads: 10 
Time with stack array: 0.329 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array: 2.150 sec, checksum=1073741824 (must be 1073741824). 

¡Agradecería cualquier ayuda!

Answer 1

Este es un lindo problema: con el código anterior (gcc4.4, Intel i7) con 4 hilos de recibo

OpenMP threads: 4 
Time with stack array:  1.696 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array:  5.413 sec, checksum=1073741824 (must be 1073741824). 

pero si cambio de la línea de malloc a

int* bins_thread_heap=(int*)malloc(sizeof(int)*M*1024); 

(actualización: o incluso

int* bins_thread_heap=(int*)malloc(sizeof(int)*16); 

)

luego obtengo

OpenMP threads: 4 
Time with stack array:  1.578 sec, checksum=1073741824 (must be 1073741824). 
Time with heap array:  1.574 sec, checksum=1073741824 (must be 1073741824). 

El problema aquí es false sharing. El malloc predeterminado es muy eficiente (espacio) y coloca todas las asignaciones pequeñas solicitadas en un bloque de memoria, una al lado de la otra; pero dado que las asignaciones son tan pequeñas que caben múltiples en la misma línea de caché, eso significa que cada vez que un subproceso actualiza sus valores, ensucia la línea de caché de los valores en los subprocesos vecinos. Al hacer que la memoria solicitada sea lo suficientemente grande, ya no es un problema.

Por cierto, debe quedar claro por qué el caso asignado a la pila no ve este problema; diferentes hilos, diferentes pilas, memoria lo suficientemente lejos, que el intercambio falso no es un problema.

Como punto adicional: realmente no importa M del tamaño que está usando aquí, pero si su M (o el número de subprocesos) era más grande, el OMP crítico sería un gran cuello de botella en serie; puede usar OpenMP reductions para sumar la suma de verificación más eficientemente

#pragma omp parallel reduction(+:checksum) 
    { // Each openmp thread should have a private copy of 
     // bins_thread_heap on the heap: 
     int* bins_thread_heap=(int*)malloc(sizeof(int)*M*1024); 
     for (int j=0; j<M; j++) bins_thread_heap[j]=0; 
#pragma omp for 
     for (int i=0; i<N; i++) 
     { // Accumulating every M-th number in respective array element 
      const int j=i%M; 
      bins_thread_heap[j]++; 
     } 
     for (int j=0; j<M; j++) 
      checksum+=bins_thread_heap[j]; 
     free(bins_thread_heap); 
}