Równoległe losowe odczytywanie wydaje się działać dobrze - dlaczego?

Rozważ następujący bardzo prosty program komputerowy:

for i = 1 to n:
    y[i] = x[p[i]]

Tutaj i y są n -elementowe tablice bajtów, a P jest N -elementowe szereg słów. Tutaj n jest duże, np. N = 2 31 (tak, że tylko niewielka część danych mieści się w jakiejkolwiek pamięci podręcznej).$x$$y$$n$$p$$n$$n$$n = 2^{31}$

Załóżmy, że składa się z liczb losowych , równomiernie rozmieszczonych między 1 i n .$p$$1$$n$

Z punktu widzenia nowoczesnego sprzętu powinno to oznaczać:

• odczyt jest tani (odczyt sekwencyjny)$p[i]$
• odczyt jest bardzo kosztowny (losowe odczyty; prawie wszystkie odczyty są błędami pamięci podręcznej; będziemy musieli pobrać każdy pojedynczy bajt z pamięci głównej)$x[p[i]]$
• pisanie jest tanie (zapis sekwencyjny).$y[i]$

I rzeczywiście to obserwuję. Program działa bardzo wolno w porównaniu z programem, który wykonuje tylko sekwencyjne operacje odczytu i zapisu. Świetny.

Teraz pojawia się pytanie: jak dobrze ten program działa równolegle na nowoczesnych platformach wielordzeniowych?

Moja hipoteza była taka, że ​​ten program nie działa dobrze równolegle. W końcu wąskim gardłem jest pamięć główna. Jeden rdzeń już marnuje większość czasu, czekając tylko na dane z pamięci głównej.

Nie tego jednak zaobserwowałem, gdy zacząłem eksperymentować z niektórymi algorytmami, w których wąskim gardłem była tego rodzaju operacja!

Po prostu zamieniłem naiwną pętlę for na równoległą pętlę OpenMP (w zasadzie podzieli on zakres na mniejsze części i równolegle uruchomię te części na różnych rdzeniach procesora).$[1,n]$

Na niskich komputerach przyspieszenia były rzeczywiście niewielkie. Ale na platformach wyższej klasy byłem zaskoczony, że otrzymałem doskonałe przyspieszenia prawie liniowe. Kilka konkretnych przykładów (dokładne czasy mogą być nieco opóźnione, istnieje wiele losowych odmian; były to tylko szybkie eksperymenty):

• 2 x 4-rdzeniowy Xeon (w sumie 8 rdzeni): współczynnik 5-8 przyspieszeń w porównaniu z wersją jednowątkową.

• 2 x 6-rdzeniowy Xeon (łącznie 12 rdzeni): współczynnik 8-14 przyspieszeń w porównaniu z wersją jednowątkową.

To było zupełnie nieoczekiwane. Pytania:

1. Właśnie dlaczego taki program jest tak równoległy ? Co dzieje się w sprzęcie? (Moje obecne przypuszczenie jest coś w tym rodzaju: losowe odczyty z innego wątku są „potokowe”, a średni wskaźnik uzyskiwania odpowiedzi na te pytania jest znacznie wyższy niż w przypadku pojedynczego wątku.)

2. Czy konieczne jest użycie wielu wątków i wielu rdzeni, aby uzyskać jakieś przyspieszenia? Jeśli w interfejsie między pamięcią główną a procesorem rzeczywiście zachodzi jakiś potok, czy aplikacja jednowątkowa nie może poinformować pamięci głównej, że wkrótce będzie potrzebować , x [ p [ i + 1 ] ] , ... a komputer może rozpocząć pobieranie odpowiednich linii pamięci podręcznej z pamięci głównej? Jeśli jest to w zasadzie możliwe, jak mogę to osiągnąć w praktyce?$x[p[i]]$$x[p[i+1]]$

3. Jaki jest właściwy model teoretyczny , którego moglibyśmy użyć do analizy tego rodzaju programów (i do prawidłowego przewidywania wydajności)?

Edycja: Teraz jest dostępny kod źródłowy i wyniki testów porównawczych tutaj: https://github.com/suomela/parallel-random-read

Niektóre przykłady figurek z boiska ( ):$n = 2^{32}$

• około. 42 ns na iterację (losowy odczyt) z jednym wątkiem
• około. 5 ns na iterację (losowy odczyt) z 12 rdzeniami.

Zapomnij na chwilę o wszystkich problemach związanych z dostępem do pamięci głównej i pamięci podręcznej poziomu 3. Z perspektywy równoległej, ignorując te problemy, program idealnie równolegle podczas korzystania z procesorów (lub rdzeni), ze względu na fakt, że po podzieleniu pracy, która ma zostać wykonana przez dekompozycję domeny, każdy rdzeń musi przetworzyć ⌊ $p$lub⌈$\left\lfloor {\frac{n}{p}} \right\rfloor$elementy p ⌉i nie ma narzutu na komunikację i / lub synchronizację, ponieważ nie ma zależności funkcjonalnej między procesorami. Dlatego ignorując problemy z pamięcią, oczekujesz przyspieszenia równegop.$\left\lceil {\frac{n}{p}} \right\rceil$$p$

Teraz weźmy pod uwagę problemy z pamięcią. Superliniowe przyspieszenie, które faktycznie zaobserwowałeś w swoim wysokiej klasy węźle opartym na Xeon, jest uzasadnione w następujący sposób.

$n$$n/p$$p$

$n = 2^{31}$

$n$

Wreszcie, oprócz QSM (kolejkowanie pamięci współdzielonej) , nie znam żadnego innego teoretycznego modelu równoległego, biorąc pod uwagę na tym samym poziomie rywalizację o dostęp do pamięci współdzielonej (w twoim przypadku, gdy używasz OpenMP, pamięć główna jest dzielona między rdzeniami , pamięć podręczna jest zawsze współdzielona także między rdzeniami). W każdym razie, chociaż model jest interesujący, nie odniósł wielkiego sukcesu.

Postanowiłem sam wypróbować __builtin_prefetch (). Zamieszczam go tutaj jako odpowiedź na wypadek, gdyby inni chcieli go przetestować na swoich komputerach. Wyniki są zbliżone do tego, co opisuje Jukka: około 20% skrócenia czasu działania przy pobieraniu 20 elementów z wyprzedzeniem w porównaniu z pobieraniem 0 elementów z wyprzedzeniem.

Wyniki:

prefetch =   0, time = 1.58000
prefetch =   1, time = 1.47000
prefetch =   2, time = 1.39000
prefetch =   3, time = 1.34000
prefetch =   4, time = 1.31000
prefetch =   5, time = 1.30000
prefetch =   6, time = 1.27000
prefetch =   7, time = 1.28000
prefetch =   8, time = 1.26000
prefetch =   9, time = 1.27000
prefetch =  10, time = 1.27000
prefetch =  11, time = 1.27000
prefetch =  12, time = 1.30000
prefetch =  13, time = 1.29000
prefetch =  14, time = 1.30000
prefetch =  15, time = 1.28000
prefetch =  16, time = 1.24000
prefetch =  17, time = 1.28000
prefetch =  18, time = 1.29000
prefetch =  19, time = 1.25000
prefetch =  20, time = 1.24000
prefetch =  19, time = 1.26000
prefetch =  18, time = 1.27000
prefetch =  17, time = 1.26000
prefetch =  16, time = 1.27000
prefetch =  15, time = 1.28000
prefetch =  14, time = 1.29000
prefetch =  13, time = 1.26000
prefetch =  12, time = 1.28000
prefetch =  11, time = 1.30000
prefetch =  10, time = 1.31000
prefetch =   9, time = 1.27000
prefetch =   8, time = 1.32000
prefetch =   7, time = 1.31000
prefetch =   6, time = 1.30000
prefetch =   5, time = 1.27000
prefetch =   4, time = 1.33000
prefetch =   3, time = 1.38000
prefetch =   2, time = 1.41000
prefetch =   1, time = 1.41000
prefetch =   0, time = 1.59000

Kod:

#include <stdlib.h>
#include <time.h>
#include <stdio.h>

void cracker(int *y, int *x, int *p, int n, int pf) {
    int i;
    int saved = pf;  /* let compiler optimize address computations */

    for (i = 0; i < n; i++) {
        __builtin_prefetch(&x[p[i+saved]]);
        y[i] += x[p[i]];
    }
}

int main(void) {
    int n = 50000000;
    int *x, *y, *p, i, pf, k;
    clock_t start, stop;
    double elapsed;

    /* set up arrays */
    x = malloc(sizeof(int)*n);
    y = malloc(sizeof(int)*n);
    p = malloc(sizeof(int)*n);
    for (i = 0; i < n; i++)
        p[i] = rand()%n;

    /* warm-up exercise */
    cracker(y, x, p, n, pf);

    k = 20;
    for (pf = 0; pf < k; pf++) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }
    for (pf = k; pf >= 0; pf--) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }

    return 0;
}

1. Dostęp do pamięci DDR3 jest rzeczywiście potokowy. http://www.eng.utah.edu/~cs7810/pres/dram-cs7810-protocolx2.pdf slajdy 20 i 24 pokazują, co dzieje się w magistrali pamięci podczas operacji odczytu potokowego.

2. (częściowo źle, patrz poniżej) Wiele wątków nie jest koniecznych, jeśli architektura procesora obsługuje wstępne pobieranie pamięci podręcznej. Nowoczesne x86 i ARM, a także wiele innych architektur mają wyraźną instrukcję wstępnego pobierania. Wiele osób próbuje dodatkowo wykryć wzorce w dostępach do pamięci i automatycznie pobiera dane. Obsługa oprogramowania jest specyficzna dla kompilatora, na przykład GCC i Clang mają wbudowane funkcje __builtin_prefech () do jawnego pobierania wstępnego.

Wydaje się, że hyperthreading w stylu Intela działa bardzo dobrze w przypadku programów, które spędzają większość czasu czekając na brak pamięci podręcznej. Z mojego doświadczenia wynika, że ​​przy intensywnym obciążeniu obliczeniowym przyspieszenie bardzo niewiele przekracza liczbę rdzeni fizycznych.

EDYCJA: Myliłem się w punkcie 2. Wydaje się, że chociaż pobieranie wstępne może zoptymalizować dostęp do pamięci dla pojedynczego rdzenia, łączna przepustowość pamięci wielu rdzeni jest większa niż przepustowość pojedynczego rdzenia. O ile większy, zależy od procesora.

Preselektor sprzętowy i inne optymalizacje razem sprawiają, że testy porównawcze są bardzo trudne. Możliwe jest konstruowanie przypadków, w których jawne pobieranie wstępne ma bardzo widoczny lub nieistniejący wpływ na wydajność, przy czym ten test porównawczy jest jednym z tych ostatnich.