OpenMP: desempenho ruim de matrizes de heap (matrizes de pilha funcionam bem)
Sou um usuário bastante experiente do OpenMP, mas acabei de encontrar um problema intrigante e espero que alguém aqui possa ajudar. O problema é que um algoritmo de hash simples funciona bem para matrizes alocadas à pilha, mas é ruim para matrizes na pilh
Exemplo abaixo usa i% M (i módulo M) para contar cada M-ésimo número inteiro no respectivo elemento da matriz. Para simplificar, imagine N = 1000000, M = 10. Se N% M == 0, o resultado deve ser que todos os elementos dos compartimentos [] sejam iguais a N / M:
#pragma omp for
for (int i=0; i<N; i++)
bins[ i%M ]++;
Array bins [] é privado para cada thread (somamos os resultados de todos os threads em uma seção crítica posteriormente
Quando os compartimentos [] são alocados na pilha, o programa funciona muito bem, com desempenho dimensionado proporcionalmente ao número de núcleo
No entanto, se os compartimentos [] estiverem na pilha (o ponteiro para os compartimentos [] está na pilha), o desempenho cai drasticamente. E esse é um grande problema!
Eu quero paralelizar o binning (hash) de certos dados em matrizes de heap com o OpenMP, e esse é um grande problema de desempenh
Definitivamente, não é algo tolo como todos os tópicos que tentam gravar na mesma área de memória. Isso ocorre porque cada encadeamento possui sua própria matriz de compartimentos [], os resultados estão corretos com os compartimentos alocados na pilha e na pilha e não há diferença no desempenho para execuções de encadeamento único. Reproduzi o problema em diferentes hardwares (Intel Xeon e AMD Opteron), com os compiladores GCC e Intel C ++. Todos os testes foram no Linux (Ubuntu e RedHat).
Parece não haver razão para que o bom desempenho do OpenMP deva ser limitado a arrays de pilh
Qualquer suposição? Talvez o acesso de threads ao heap passe por algum tipo de gateway compartilhado no Linux? Como faço para corrigir isso?
programa @Complete para brincar está abaixo:
#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;
}
s saídas de amostra do programa estão abaix
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).
e 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).
Eu apreciaria muito qualquer ajuda!