Jak dostroić algorytm do cache procesora?

Odpowiedz Nowy wątek
2019-07-08 06:50
0

Zdawać by się mogło że bubble sort jest przyjazny dla cache bo rzeźbi lokalnie a quick sort nie.
Mam porównanie algorytmów do tworzenia Suffix Arrays, ten naiwny właśnie wykorzystuje quick sort.
Algorytm SA-IS dla bloku 150 kilo dzała na typowym tekście (Wikipedia) ponad 4x szybciej niż naiwny, ale gdy mam 10 mega tylko 1.1 x. Natomiast karkkainen-sanders) jest dla dużych bloków ponad 2x wolniejszy.
Takie zachowanie może wynikać z cache procesora. Naiwny, mimo że korzysta z quicksorta, który skacze po indeksach to jednak rekurencyknie najpierw zajmuje się pierwszą a potem drugą połową, natomiast tutaj jest jakieś inne sortowanie, które nie działa dobrze z cache, jak można to zmienić? jakie narzędzia analizują cache? Czy dałoby radę przerobić na "external", aby w zwykłym przypadku działał trochę wolniej , ale w przypadku gdy rozmiar danych przekracza cache, działał szybciej?

edytowany 1x, ostatnio: Borneq, 2019-07-08 07:11

Pozostało 580 znaków

2019-07-08 07:24
1

Tu chodzi jak algorytm często nie trafia w dane z cache oraz jaki algorytm (wewnętrznie w procesorze) odpowiada za wymianę. Tez ważne ilu drożny jest cache. To jak tak się bawisz to warto wyłączyć optymalizacje bo kompilator i tak ci ten kod pozmienia. Np. Rozwinąłeś pętle do rozmiaru cache ale działa wolni bo licznik trafił do ram a nie do rejestru i co iteracje cały cache jest wymieniany bo trzeba licznik inkrementowac. Pokaz kod, na czym to kompilujesz i czym.

Tez ważne ilu drożny jest cache. ilu drożny może być cache? - Pijak 2019-07-08 08:00
Ofc jak to u nas - drożność to potęgi dwójki ;) W zależności od poziomu cache może być 2, 4 8 drożny. Od tego wynika w ile cykli wymieni się cały cache. Poczytaj o architekturze procesora i mapowaniu pamięci, nie ma sensu, żebym przeklejał tutaj wykłady z jakiejś polskiej uczelni. - somedev 2019-07-08 08:22
A więc jak jest niedrożność, to wywołuje się popłoch jądra? - Pijak 2019-07-08 11:00

Pozostało 580 znaków

2019-07-08 08:43
0

Takie zachowanie może wynikać z cache procesora. - brzmi jakbyś nie był tego pewien. W pierwszej kolejności zmierz utylizację cache'a, a dopiero później bierz się za takie optymalizacje.
Pod Linuksem możesz mierzyć za pomocą, np. http://man7.org/linux/man-pages/man1/perf.1.html

Do cache podnoszona jest cała linia (blok danych), której rozmiar może się różnić w zależności od architektury (w PCtach najczęściej będzie to 64 bajty). Dużo będzie zależało od tego jak w pamięci te dane do sortowania wyglądają. Możesz rozważyć dwa przypadki:
a) pamięć, na której operuje algorytm wypełniona jest "pełnymi strukturami" - tj. klucz względem, którego porównujesz + reszta danych
b) pamięć, na której operuje algorytm wypełniona jest "indeksami" - tj. klucz względem, którego porównujesz + wskaźnik do oryginalnych danych

W przypadku b) do jednej linii cache może (pomijając patologiczne przypadki, że sortujesz po wszystkich atrybutach) zmieścić się więcej danych, które masz sortować.

Przykład struktury dla a) - obiekt nie zmieści się w jednym bloku cache'a.

struct {
  int wiek;
  char[64] imie;
  char[64] nazwisko;
}

Przykład struktury dla b) - w jednym bloku cache może zmieścić się kilka (64 / sizeof(int) + sizeof(void*)) rekordów.

struct {
   int wiek;
   void *obiekt;
}

W przypadku b) będziesz miał szybsze odczyty danych, ale czy to znacznie przyspieszy Twój algorytm, to nie wiem ;-)

Popraw te structy, bo teraz są w C/# - Pijak 2019-07-08 10:59
@Pijak: Dla omawianego problemu wg mnie nie ma znaczenia w pseudo-Czym te struktury są ilustrowane. - yarel 2019-07-08 11:25

Pozostało 580 znaków

2019-07-09 11:00
1

Jak nie jesteś pewien, co może spowalniać dany algorytm, to przecież zawsze możesz sięgnąć po:

  • profile wykonania kodu (ile czasu siedzisz w której funkcji/pętli/bloku itp itp)
  • narzędzia do analizy wykorzystania pamięci - czy to bazujące na licznikach procesora (bodajże perf stat ale nie pamiętam) czy symulujące pamięć cache L1 i LL (cachegrind).

Tylko uważaj z tą analizą pamięci, najlepiej użyj kilku różnych narzędzi i odrzuć najbardziej odstające wyniki - z jednej strony te oparte o liczniki mogą dawać mało miarodajne wyniki. Procesory wykonują znacznie bardziej złożone, wielostopniowe operacje niż kiedyś, i przełożenie tych operacji na konkretną liczbę np. odwołań do cache może być lekko tricky ;) Z drugiej strony to, co zliczy cachegrind na jakimś teoretycznym modelu pamięci, robiąc przy okazji uproszczenia (np. uwzględnia tylko cache pierwszego i ostatniego poziomu, z pominięciem L2 jeśli masz 3 poziomy) może się różnić od tego, co finalnie zrobi Twój procesor.

No ale tak orientacyjnie będziesz widział, że np. jeden algorytm ma dobrą ilość trafień, ale robi horrendalne ilości odwołań do pamięci, a drugi np. mniej, ale b. często pudłuje w L1 i w efekcie grzebie ciągle w L2/L3 i tak dalej.


Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)

Pozostało 580 znaków

2019-07-09 11:44
4

Zdawać by się mogło że bubble sort jest przyjazny dla cache bo rzeźbi lokalnie a quick sort nie.

No niespecjalnie. Sortowanie bąbelkowe przelatuje przez tablicę wejściową N razy, więc potencjalnie ładujesz wszystkie dane z RAMu O(N) razy (bo często tablice nie mieszczą się w całości w cache). Sortowanie szybkie ma typowo złożoność O(N lg N), więc ładujesz dane z RAMu O(lg N) razy.

Ponadto sortowanie szybkie właśnie jest algorytmem, który (w pewnym stopniu) automatycznie dostraja się do struktury pamięci podręcznej. Załóżmy, że mamy do posortowania tablicę wielokrotnie większą od pojemności wszystkich poziomów cache razem wziętych. Początkowe poziomy rekurencji będą w kółko ładować dane z RAMu, ale na pewnym poziomie rekurencji np aktualny wycinek tablicy będzie się mieścił w L3. Stąd każdy dalszy etap rekurencji na tym wycinku tablicy będzie korzystał z poziomów cache L3 lub wyższych. Analogicznie, któryś kolejny poziom rekurencji będzie operował na wycinku tablicy mieszczącym się w L2 - wtedy sortowanie tego wycinka będzie wymagać dostępu tylko do L2 i wyższych.

Jak dostępy do pamięci wyglądają przy sortowaniu bąbelkowym? Załóżmy, że tablica jest np 10x większa niż sumaryczny rozmiar cache. Przy pierwszym przebiegu sortowania wszystko musi być załadowane z RAMu (to oczywiste, bo na początku cache jest pusty). Co się dzieje przy drugim przebiegu? No, cache zawiera dane z końca tablicy, a my przelatujemy tablicę znowu od początku. Musimy więc przeładować cały cache danymi wprost z RAMu. Jak to więc sumarycznie wygląda? Dla powiedzmy 80% przebiegów tablicy dane w cache będą bezużyteczne. Ilość pracy jest proporcjonalna do kwadratu rozmiaru tablicy. A więc praca na danych w cache to zaledwie 0,2 * 0,2 = 0,04 = 4% całej pracy. Bardzo słabo.

Dużo inaczej działa sortowanie danych liniowych, a dużo inaczej danych z pośrednim indeksowaniem, referencjami, etc Procesory posiadają wbudowane prefetchery, czyli układy pobierające dane z wyprzedzeniem do pamięci podręcznej. Gdy dane mają prostą strukturę (mamy np płaską tablicę intów) to prefetchery działają bezbłędnie i procesor nie musi czekać na dane. Jeśli jednam nasze dane są dość skomplikowane (sortujemy suffiksy reprezentowane jako indeksy do głównego bufora - tak się dzieje podczas sortowania tablic suffiksów - suffix arrays) to prefetcher raczej wysiada, nie pomaga w pobieraniu danych z wyprzedzeniem i dostrojenie algorytmu do struktury pamięci podręcznej nabiera dużego znaczenia. Prefetchery działają dobrze dla prostych przypadków. Dla przykładu prostymi przypadkami jest liniowe skanowanie pamięci - takie jest w sortowaniu bąbelkowym i szybkim. Nieliniowe dostępy do pamięci są np w sortowaniu przez kopcowanie, tam zamiast przechodzić do elementu o kolejnym lub poprzednim indeksie przechodzi się np do elementu o indeksie dwa razy większym lub dwa razy mniejszym.

Ogólnie temat jest dość nieintuicyjny, podobnie jak działanie wskaźników dla większości programistów :) Ciężko go jasno przedstawić w poście na forum. Pasowałoby pokazać jakieś obrazki, studium przypadku, itd a komu się będzie chciało to robić dla anonima na forum 4p? :]

Smaczki dla zaawansowanych:
W przypadku sortowania przez kopcowanie (heapsort) prefetcher w procesorze nie pomaga, ale pomaga (o dziwo) przewidywanie skoków i spekulatywne wykonywanie instrukcji. Dzięki temu, że procesor przewidzi sobie skoki zacznie pobierać dane z kilku poziomów kopca naraz. Zwykle predykcja się nie udaje, ale i tak to nie neguje tutaj korzyści ze spekulacji. Otóż ładowanie pamięci z RAMu odbywa się w 64-bajtowych kawałkach (linie pamięci podręcznej - cache line), a więc nawet jeśli predykcja spowoduje załadowanie elementów o lekko nietrafionym indeksie to i tak jest duże prawdopodobieństwo, że właściwy element leży w tej samej cache line i dzięki temu procesor nie musi ponownie czekać na dane. Tego typu smaczki jeszcze bardziej utrudniają (wersja dla pesymistów) dostrajanie algorytmu do pamięci podręcznej, bądź (wersja dla optymistów) otwierają nowe możliwości optymalizacji.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
+1 za wyczerpujący wpis i dałbym +1 dla siebie za lekturę w całości z uwagą ;) Temat wykorzystania cache bardzo ciekawy, ale osobiście nie spotkałem się z problemem, który wymagałby strojenia/optymalizacji algorytmów pod wykorzystanie cache procesora. Możliwe, że to specyfika branży i np. w sofcie do "high frequency trading" jest to chleb powszedni. - yarel 2019-07-09 11:53
Ja drążyłem temat budowy procesora (i reszty kompa) i sposobu jego działania przy okazji tworzenia algorytmów kompresji i sortowania. Część z tych programów jest na moim GH: https://github.com/tarsa?tab=repositories&type=source Jednak jest to moje hobby, a w pracy nigdy się tym nie zajmowałem. W typowej pracy ważne są bardziej rzędy złożoności niż stałe w oszacowaniu. Jak ktoś zrobi algorytm O(n*n) to praktycznie zawsze jest sporo gorzej niż z algorytmem O(n lg n), a z takimi przypadkami nierzadko się spotykałem. Analogicznie problem N + 1 zapytań zamiast np 2. Dość częsty. - Wibowit 2019-07-09 13:35

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0