Soy un usuario de OpenMP bastante experimentado, pero acabo de encontrarme con un problema desconcertante y espero que alguien aquí pueda ayudar. El problema es que un algoritmo de hash simple funciona bien para los arrays asignados a la pila, pero deficientemente para los arrays en el montón.

El ejemplo a continuación utiliza i% M (i módulo M) para contar cada número M en el elemento de matriz respectivo. Por simplicidad, imagine N = 1000000, M = 10. Si N% M == 0, entonces el resultado debería ser que cada elemento de los contenedores [] es igual a N / M:

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

Array bins [] es privado para cada hilo (sumo los resultados de todos los hilos en una sección crítica después).

Cuando se asignan bins [] en la pila, el programa funciona muy bien, con una escala de rendimiento proporcional 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 cae drásticamente. ¡Y ese es un gran problema!

Quiero paralelizar la agrupación (hash) de ciertos datos en conjuntos de almacenamiento dinámico con OpenMP, y este es un gran éxito en el rendimiento.

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 al montón y al montón, y no hay diferencia en el rendimiento de las ejecuciones de un solo subproceso. Reproduje el problema en diferentes hardware (Intel Xeon y AMD Opteron), con los compiladores GCC e Intel C ++. Todas las pruebas fueron en Linux (Ubuntu y RedHat).

Parece que no hay razón para que el buen rendimiento de OpenMP se limite a los arreglos de pila.

¿Alguna conjetura? ¿Quizás el acceso de subprocesos al montón pasa por algún tipo de puerta de enlace compartida en Linux? ¿Cómo arreglo eso

l programa completo para jugar es el siguiente:

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

os resultados de @Sample del programa están 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 mucho cualquier ayuda!