multithreading - OpenMP: rendimiento deficiente de las matrices de almacenamiento dinámico(las matrices de pila funcionan bien)

performance stack

Question

Soy un usuario de OpenMP bastante experimentado, pero acabo de encontrar un problema desconcertante, y tengo la esperanza de que alguien aquí pueda ayudar. El problema es que un algoritmo de hashing simple funciona bien para las matrices asignadas a la pila, pero mal 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, el resultado debería ser que cada elemento de los contenedores [] sea igual a N / M:

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

Los contenedores de arrays [] son ​​privados para cada subproceso (luego sumo los resultados de todos los subprocesos en una sección crítica).

Cuando se asignan bandejas [] en la pila, el programa funciona muy bien, con un escalamiento de rendimiento proporcional al número de núcleos.

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

Quiero paralelizar el agrupamiento (hashing) de ciertos datos en matrices de almacenamiento dinámico con OpenMP, y este es un gran éxito de 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 a pila y pila, y no hay diferencia en el rendimiento para las ejecuciones de un solo subproceso. Reproducí el problema en diferentes hardware (Intel Xeon y AMD Opteron), con compiladores GCC e Intel C ++. Todas las pruebas se realizaron en Linux (Ubuntu y RedHat).

No parece haber ninguna razón por la que el buen rendimiento de OpenMP deba limitarse a los arreglos de apilamiento.

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

El programa completo para jugar está abajo:

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

Las salidas de muestra 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).

¡Apreciaría mucho cualquier ayuda!

Answer 1

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

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 la línea 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);

)

entonces me pongo

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 el intercambio falso . El malloc predeterminado es muy eficiente (en espacio) y coloca las pequeñas asignaciones solicitadas en un bloque de memoria, uno al lado del otro; pero como las asignaciones son tan pequeñas que múltiples caben en la misma línea de caché, eso significa que cada vez que un hilo actualiza sus valores, ensucia la línea de caché de los valores de los hilos vecinos. Al hacer que la memoria solicitada sea lo suficientemente grande, esto ya no es un problema.

Incidentalmente, debería quedar claro por qué el caso asignado por pila no ve este problema; subprocesos diferentes, pilas diferentes, memoria lo suficientemente alejada como para que compartir falsamente no sea un problema.

Como punto lateral, en realidad no importa para M del tamaño que está utilizando aquí, pero si su M (o la cantidad de hilos) fuera mayor, el omp crítico sería un gran cuello de botella serial; Puede utilizar las reducciones de OpenMP para sumar la suma de control de manera más eficiente.

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

Answer 2

La pregunta inicial implicaba que las matrices de almacenamiento dinámico son más lentas que las matrices de pila. Desafortunadamente, la razón de esta lentitud relacionada con un caso particular de choques de línea de caché en aplicaciones de subprocesos múltiples. No justifica la implicación de que, en general, las matrices de almacenamiento dinámico son más lentas que las matrices de pila. Para la mayoría de los casos, no hay una diferencia significativa en el rendimiento, especialmente cuando las matrices son mucho más grandes que el tamaño de la línea de caché. A menudo, puede ocurrir lo contrario, ya que el uso de matrices de almacenamiento dinámico asignables, orientadas al tamaño requerido puede dar lugar a ventajas de rendimiento sobre matrices de tamaño fijo más grandes, que demandan más transferencias de memoria.