Jak dostroić algorytm do cache procesora?

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?

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.

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 ;-)

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.

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.

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