OpenMP: słaba wydajność tablic sterty (tablice stosu działają dobrze)

Jestem dość doświadczonym użytkownikiem OpenMP, ale właśnie napotkałem zagadkowy problem i mam nadzieję, że ktoś tutaj mógłby pomóc. Problem polega na tym, że prosty algorytm mieszający działa dobrze dla tablic przydzielanych stosem, ale słabo dla tablic na stercie.

Poniższy przykład używa i % m (i modulus M) do zliczania każdej M-tej liczby całkowitej w danym elemencie tablicy. Dla uproszczenia, wyobraź sobie N = 1000000, M = 10. Jeżeli N % M= = 0, to wynik powinien być taki, że każdy element Bina [] jest równy N / M:

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

Pojemniki tablicy [] są prywatne dla każdego wątku(sumuję wyniki wszystkich wątków w sekcji krytycznej).

Gdy pojemniki[] są przydzielane na stosie, program działa świetnie, ze skalowaniem wydajności proporcjonalnie do liczby rdzeni.

Jeśli jednak bins [] znajduje się na stosie (wskaźnik do bins[] znajduje się na stosie), wydajność drastycznie spada. I to jest poważny problem!

Chcę równoległe binowanie (hashowanie) pewnych danych do tablic sterty z OpenMP, a to jest wielki hit wydajności.

To zdecydowanie nie jest coś głupiego, jak wszystkie wątki próbujące zapisać w tym samym obszarze pamięci. Dzieje się tak dlatego, że każdy wątek ma własną tablicę bins [], wyniki są poprawne zarówno dla skrzynek przydzielonych stosem, jak i stosem, i nie ma różnicy w wydajności dla uruchomień pojedynczych wątków. Odtworzyłem problem na innym sprzęcie (Intel Xeon i AMD Opteron), z kompilatorami GCC i Intel C++. Wszystkie testy były na Linuksie (Ubuntu i RedHat).

Wydaje się, że nie ma powodu, dla którego dobra wydajność OpenMP powinna być ograniczona do tablic stosu.

Kompletny program do zabawy znajduje się poniżej:

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

Przykładowe wyniki programu są poniżej:

For 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).

I dla 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).