Aktualizowanie tablicy dublu z operacjami atomowymi

Question

Próbuję pisać (aktualizować) w tablicy podwójnej w sposób równoległy za pomocą OpenMP. Chodzi o to, że element, który wymaga aktualizacji, może być aktualizowany więcej niż jeden raz, a sam element jest obliczany w locie. To czyni go bardzo podatnym na warunki wyścigowe, chyba że "zablokuję" obszar pamięci odpowiadający elementowi, który jest aktualizowany operacją atomową. W poniższym przykładzie:

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

int main() 
{ 

    double *x=NULL, contribution = 1234.5; 
    size_t xlen=1000, i, n; 

    if ((x = (double *) calloc(xlen,sizeof(double))) == NULL) exit(-1) 

    #pragma omp parallel for shared(x) private(n,contribution) 
    for (i=0; i<xlen; i++) { 
     n = find_n_on_the_fly(i); 

     #pragma omp atomic update 
     x[n]+=contribution; // in the more complicated case contributions are different 

    } 

    return 0; 
} 

Z takim podejściem wciąż jestem w wyścigu. Próbowałem używać krytycznych sekcji, ale całkowicie mnie to zabija, ponieważ tablice są duże, a liczba aktualizacji jest również duża.

Pytanie: co jest nie tak z tym podejściem? Czy istnieje lepszy sposób radzenia sobie z tym?

Uwaga: Aby sobie z tym poradzić, robię coś głupiego, tworząc kopie tablic dla każdego wątku i zmniejszając je później. Ale ograniczenia pamięci nie pozwalają mi iść dalej.

Answer 1

Przedmowie to poprzedzę słowami: "Jestem nowy w dziedzinie przetwarzania równoległego", co może nie być opłacalne w zależności od przypadku użycia.

Jednym z pomysłów, który może być przydatny, jest oddzielenie aspektów obliczeniowych i aktualizacyjnych programu. Ustanowienie procesu nadrzędnego/kontrolnego/wątku, który ma wyłączny dostęp do tablicy i wykonuje aktualizacje w sposób podobny do kolejki na podstawie informacji zebranych z procesów/wątków podrzędnych/obliczeniowych. Może to służyć zminimalizowaniu potrzeby blokowania w tradycyjnym sensie.

Mam nadzieję, że przynajmniej zapewni inny sposób patrzenia na problem.

Answer 2

Dla mnie powyższy kod wydaje się być skuteczny.

jednak, masz dwie opcje, aby ją poprawić:

1- użyciu funkcji alokacji pamięci o nazwie _mm_malloc z rozmiaru linii pamięci podręcznej jako jeden z wejścia zamiast calloc które zostało użyte. Największą rzeczą, z którą teraz się spotykasz, jest Fałszywe Udostępnianie. Aby pominąć efekty FS, używając powyższej metody, zasadniczo zmuszasz bazową bibliotekę do alokacji pamięci (lub twojej tablicy) w taki sposób, aby każdy element znajdował się w wierszu pamięci podręcznej. W ten sposób wątki nie będą walczyć o linię pamięci podręcznej, aby pobrać dwie różne zmienne wspólne. Innymi słowy, uniemożliwi przydział dwóch zmiennych w linii pamięci podręcznej. To zwiększy wydajność w wielowątkowym programie. Google _mm_malloc, aby uzyskać więcej informacji. Jednak poniższe są podstawowe użycie. W większości nowoczesnych komputerów, linia pamięci podręcznej ma wartość 64.

#if defined(__INTEL_COMPILER) 
#include <malloc.h> 
#else 
#include <mm_malloc.h> 
#endif 

int CPU_Cache_line_size = 64; 

int xlen = 100; 
double *ptr = _mm_malloc(xlen*sizeof(double), CPU_Cache_line_size); 
/* 
    do something ... 
*/ 
_mm_free(ptr); 

__CPU_CACHE_LINE_SIZE__ można przeszukiwać dla swojego systemu w następujący sposób: komenda

• Linux:

  getconf LEVEL1_DCACHE_LINESIZE

• Programowo:

  int CPU_Cache_line_size = sysconf (_SC_LEVEL1_DCACHE_LINESIZE);

• Szczegółowe informacje dotyczące pamięci podręcznej:

  /sys/devices/system/cpu/cpu0/cache/

2- Wspomniałeś ten sam ale ograniczenia są dotkliwe dla danej sytuacji: przy użyciu tablicy na wątek, a następnie zmniejszyć je. Takie podejście jest bardziej wydajne. Zastanów się, czy użyć tego podejścia, jeśli możesz.