Jak napisać kod, który najlepiej wykorzystuje pamięć podręczną procesora, aby poprawić wydajność?

To może brzmieć jak subiektywne pytanie, ale szukam konkretnych przypadków, z którymi mogłeś się spotkać w związku z tym.

1. Jak sprawić, by kod był efektywny w pamięci podręcznej / przyjazny dla pamięci podręcznej (więcej trafień w pamięci podręcznej, jak najmniej braków w pamięci podręcznej)? Z obu perspektyw, pamięć podręczna danych i pamięć podręczna programu (pamięć podręczna instrukcji), czyli jakie rzeczy w kodzie, związane ze strukturami danych i konstrukcjami kodu, należy zadbać, aby pamięć podręczna była efektywna.

2. Czy istnieją jakieś szczególne struktury danych, których należy używać / unikać, czy też istnieje określony sposób uzyskiwania dostępu do elementów tej struktury itp., Aby pamięć podręczna kodu była efektywna.

3. Czy są jakieś konstrukcje programu (if, for, switch, break, goto, ...), code-flow (wewnątrz if, if inside a for, etc ...), których należy przestrzegać / unikać w tej sprawie?

Z niecierpliwością czekam na indywidualne doświadczenia związane z generowaniem wydajnego kodu pamięci podręcznej. Może to być dowolny język programowania (C, C ++, Assembly, ...), dowolny cel sprzętowy (ARM, Intel, PowerPC, ...), dowolny system operacyjny (Windows, Linux, S ymbian, ...) itp. .

Różnorodność pomoże lepiej ją głębiej zrozumieć.

Pamięć podręczna ma na celu zmniejszenie liczby przypadków, w których procesor zatrzymałby się w oczekiwaniu na wypełnienie żądania pamięci (unikając opóźnienia pamięci ), a jako drugi efekt, prawdopodobnie w celu zmniejszenia całkowitej ilości danych, które muszą być przesłane (zachowując przepustowość pamięci ).

Techniki unikania opóźnień w pobieraniu pamięci są zazwyczaj pierwszą rzeczą do rozważenia i czasami pomagają na dłuższą metę. Ograniczona przepustowość pamięci jest również czynnikiem ograniczającym, szczególnie w przypadku wielordzeniowych i wielowątkowych aplikacji, w których wiele wątków chce używać magistrali pamięci. Inny zestaw technik pomaga rozwiązać ten ostatni problem.

Poprawa lokalności przestrzennej oznacza, że ​​każda linia pamięci podręcznej jest używana w całości po zmapowaniu jej do pamięci podręcznej. Kiedy przyjrzeliśmy się różnym standardowym testom porównawczym, zauważyliśmy, że zaskakująco duża część z nich nie wykorzystuje 100% pobranych wierszy pamięci podręcznej, zanim wiersze pamięci podręcznej zostaną eksmitowane.

Poprawa wykorzystania linii pamięci podręcznej pomaga w trzech aspektach:

• Zmienia bardziej przydatne dane w pamięci podręcznej, zasadniczo zwiększając efektywny rozmiar pamięci podręcznej.
• Ma tendencję do umieszczania bardziej przydatnych danych w tej samej linii pamięci podręcznej, zwiększając prawdopodobieństwo, że żądane dane można znaleźć w pamięci podręcznej.
• Zmniejsza wymagania dotyczące przepustowości pamięci, ponieważ będzie mniej pobrań.

Typowe techniki to:

• Używaj mniejszych typów danych
• Uporządkuj swoje dane, aby uniknąć dziur w wyrównaniu (sortowanie elementów struktury poprzez zmniejszenie rozmiaru jest jednokierunkowe)
• Uważaj na standardowy dynamiczny alokator pamięci, który może wprowadzać dziury i rozprowadzać dane w pamięci podczas jej rozgrzewania.
• Upewnij się, że wszystkie sąsiednie dane są rzeczywiście używane w gorących pętlach. W przeciwnym razie rozważ rozbicie struktur danych na komponenty gorące i zimne, tak aby pętle gorące używały danych gorących.
• unikaj algorytmów i struktur danych wykazujących nieregularne wzorce dostępu i preferuj liniowe struktury danych.

Powinniśmy również zauważyć, że istnieją inne sposoby ukrywania opóźnień pamięci niż używanie pamięci podręcznych.

Nowoczesne procesory często mają jeden lub więcej sprzętowych modułów wstępnych . Trenują na chybieniach w skrytce i próbują dostrzec prawidłowości. Na przykład, po kilku chybieniach w kolejnych wierszach pamięci podręcznej, moduł wstępnego pobierania hw rozpocznie pobieranie wierszy pamięci podręcznej do pamięci podręcznej, przewidując potrzeby aplikacji. Jeśli masz regularny wzorzec dostępu, sprzętowy moduł wstępnego pobierania zwykle wykonuje bardzo dobrą robotę. A jeśli twój program nie wyświetla regularnych wzorców dostępu, możesz poprawić rzeczy, dodając samodzielnie instrukcje pobierania wstępnego .

Instrukcje przegrupowania w taki sposób, że te, które zawsze są pomijane w pamięci podręcznej, występują blisko siebie, procesor może czasami nakładać się na te pobrania, tak że aplikacja może wytrzymać tylko jedno uderzenie w opóźnienie ( równoległość poziomu pamięci ).

Aby zmniejszyć ogólne obciążenie magistrali pamięci, musisz zacząć zajmować się tym, co nazywa się lokalnością czasową . Oznacza to, że musisz ponownie wykorzystać dane, dopóki nie zostały one usunięte z pamięci podręcznej.

Łączenie pętli, które dotykają tych samych danych ( fuzja pętli ) i stosowanie technik przepisywania znanych jako kafelkowanie lub blokowanie, ma na celu uniknięcie tych dodatkowych pobrań pamięci.

Chociaż istnieją pewne praktyczne zasady dotyczące tego ćwiczenia przepisywania, zwykle trzeba dokładnie rozważyć zależności danych przenoszonych w pętli, aby upewnić się, że nie wpłynie to na semantykę programu.

Są to rzeczy, które naprawdę się opłaca w świecie wielordzeniowym, w którym zazwyczaj nie widać dużej poprawy przepustowości po dodaniu drugiego wątku.

Nie mogę uwierzyć, że nie ma więcej odpowiedzi na to. W każdym razie jednym z klasycznych przykładów jest iteracja wielowymiarowej tablicy „na lewą stronę”:

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

Przyczyną tego, że pamięć podręczna jest nieefektywna, jest to, że nowoczesne procesory ładują linię pamięci podręcznej „bliskimi” adresami pamięci z pamięci głównej, gdy uzyskujesz dostęp do pojedynczego adresu pamięci. Przechodzimy przez wiersze „j” (zewnętrzne) w tablicy w pętli wewnętrznej, więc przy każdym przejściu przez pętlę wewnętrzną wiersz pamięci podręcznej spowoduje opróżnienie i załadowanie linią adresów, które są bliskie [ j] [i] wpis. Jeśli zostanie to zmienione na odpowiednik:

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]

Będzie działać znacznie szybciej.

Podstawowe zasady są w rzeczywistości dość proste. Problematyczne jest to, jak stosują się do Twojego kodu.

Pamięć podręczna działa na dwóch zasadach: lokalności czasowej i lokalności przestrzennej. Pierwsza z nich polega na tym, że jeśli niedawno użyłeś określonej porcji danych, prawdopodobnie wkrótce będziesz jej ponownie potrzebować. To ostatnie oznacza, że ​​jeśli ostatnio używałeś danych pod adresem X, prawdopodobnie wkrótce będziesz potrzebować adresu X + 1.

Pamięć podręczna próbuje to uwzględnić, zapamiętując ostatnio używane fragmenty danych. Działa z liniami pamięci podręcznej, zwykle o rozmiarze 128 bajtów, więc nawet jeśli potrzebujesz tylko jednego bajtu, cała linia pamięci podręcznej, która go zawiera, zostanie wciągnięta do pamięci podręcznej. Więc jeśli później będziesz potrzebować następującego bajtu, będzie on już w pamięci podręcznej.

A to oznacza, że ​​zawsze będziesz chciał, aby Twój własny kod wykorzystywał te dwie formy lokalności w jak największym stopniu. Nie przeskakuj całej pamięci. Wykonuj tyle pracy, ile możesz na jednym małym obszarze, a następnie przejdź do następnego i wykonaj tam tyle pracy, ile możesz.

Prostym przykładem jest przechodzenie przez tablicę 2D, które pokazała odpowiedź z 1800 roku. Jeśli przechodzisz przez wiersz na raz, czytasz pamięć sekwencyjnie. Jeśli zrobisz to na podstawie kolumn, przeczytasz jeden wpis, a następnie przeskoczysz do zupełnie innej lokalizacji (początek następnego wiersza), przeczytasz jeden wpis i skoczysz ponownie. A kiedy w końcu wrócisz do pierwszego wiersza, nie będzie go już w pamięci podręcznej.

To samo dotyczy kodu. Skoki lub rozgałęzienia oznaczają mniej wydajne wykorzystanie pamięci podręcznej (ponieważ nie czytasz instrukcji po kolei, ale skaczesz na inny adres). Oczywiście małe instrukcje if prawdopodobnie niczego nie zmienią (pomijasz tylko kilka bajtów, więc nadal znajdziesz się w obszarze pamięci podręcznej), ale wywołania funkcji zwykle sugerują, że skaczesz do zupełnie innego adres, który nie może być zapisany w pamięci podręcznej. Chyba że został ostatnio wywołany.

Jednak użycie pamięci podręcznej instrukcji jest zwykle znacznie mniejszym problemem. To, o co zwykle musisz się martwić, to pamięć podręczna danych.

W strukturze lub klasie wszystkie składowe są rozmieszczone w sposób ciągły, co jest dobre. W tablicy wszystkie wpisy są również ułożone w sposób ciągły. Na listach połączonych każdy węzeł jest przydzielany w zupełnie innej lokalizacji, co jest złe. Wskaźniki na ogół wskazują na niepowiązane adresy, co prawdopodobnie spowoduje pominięcie pamięci podręcznej, jeśli ją wyłuskujesz.

A jeśli chcesz wykorzystać wiele rdzeni, może to być naprawdę interesujące, jak zwykle tylko jeden procesor może mieć dany adres w swojej pamięci podręcznej L1 na raz. Więc jeśli oba rdzenie stale uzyskują dostęp do tego samego adresu, spowoduje to ciągłe chybienia pamięci podręcznej, ponieważ walczą o adres.

Polecam przeczytanie 9-częściowego artykułu Ulricha Dreppera Co każdy programista powinien wiedzieć o pamięci , jeśli interesuje Cię interakcja pamięci i oprogramowania. Jest również dostępny jako 104-stronicowy plik PDF .

Sekcjami szczególnie istotnymi dla tego pytania mogą być Część 2 (pamięci podręczne procesora) i Część 5 (Co mogą zrobić programiści - optymalizacja pamięci podręcznej).

Oprócz wzorców dostępu do danych, głównym czynnikiem w kodzie przyjaznym dla pamięci podręcznej jest rozmiar danych . Mniej danych oznacza, że ​​więcej mieści się w pamięci podręcznej.

Jest to głównie czynnik związany ze strukturami danych wyrównanymi do pamięci. „Konwencjonalna” mądrość mówi, że struktury danych muszą być wyrównane na granicach słów, ponieważ procesor ma dostęp tylko do całych słów, a jeśli słowo zawiera więcej niż jedną wartość, musisz wykonać dodatkową pracę (odczyt-modyfikacja-zapis zamiast prostego zapisu) . Ale pamięci podręczne mogą całkowicie unieważnić ten argument.

Podobnie tablica logiczna Java wykorzystuje cały bajt dla każdej wartości, aby umożliwić bezpośrednie działanie na poszczególnych wartościach. Możesz zmniejszyć rozmiar danych o współczynnik 8, jeśli używasz rzeczywistych bitów, ale wtedy dostęp do poszczególnych wartości staje się znacznie bardziej złożony, wymagając operacji przesunięcia bitów i maskowania ( BitSetklasa robi to za Ciebie). Jednak ze względu na efekty pamięci podręcznej może to być nadal znacznie szybsze niż użycie wartości logicznej [], gdy tablica jest duża. IIRC I osiągnęło kiedyś w ten sposób przyspieszenie o współczynnik 2 lub 3.

Najbardziej efektywną strukturą danych dla pamięci podręcznej jest tablica. Pamięci podręczne działają najlepiej, jeśli struktura danych jest ułożona sekwencyjnie, podczas gdy procesory odczytują całe linie pamięci podręcznej (zwykle 32 bajty lub więcej) na raz z pamięci głównej.

Każdy algorytm, który uzyskuje dostęp do pamięci w kolejności losowej, kasuje pamięci podręczne, ponieważ zawsze potrzebuje nowych wierszy pamięci podręcznej, aby pomieścić losowo dostępną pamięć. Z drugiej strony algorytm, który działa sekwencyjnie w tablicy, jest najlepszy, ponieważ:

1. Daje to procesorowi szansę na odczyt z wyprzedzeniem, np. Spekulacyjnie umieszczenie większej ilości pamięci w pamięci podręcznej, do której będzie później potrzebny. Ten odczyt z wyprzedzeniem zapewnia ogromny wzrost wydajności.

2. Uruchamianie ścisłej pętli na dużej macierzy pozwala również procesorowi na buforowanie kodu wykonywanego w pętli, aw większości przypadków pozwala na wykonanie algorytmu całkowicie z pamięci podręcznej bez konieczności blokowania dostępu do pamięci zewnętrznej.

Jednym z przykładów, które widziałem w silniku gry, było przenoszenie danych z obiektów do ich własnych tablic. Obiekt gry, który podlegał fizyce, może mieć również dołączonych wiele innych danych. Ale podczas pętli aktualizacji fizyki wszystko, o co dbał silnik, dotyczyło danych o pozycji, prędkości, masie, obwiedni itp. Wszystko to zostało więc umieszczone we własnych tablicach i zoptymalizowane tak bardzo, jak to możliwe dla SSE.

Tak więc podczas pętli fizyki dane fizyczne były przetwarzane w kolejności tablicowej przy użyciu matematyki wektorowej. Obiekty gry używały swojego identyfikatora obiektu jako indeksu w różnych tablicach. Nie był to wskaźnik, ponieważ wskaźniki mogłyby zostać unieważnione, gdyby trzeba było przenieść tablice.

Pod wieloma względami naruszało to wzorce projektowe zorientowane obiektowo, ale znacznie przyspieszyło kod, umieszczając blisko siebie dane, które musiały być obsługiwane w tych samych pętlach.

Ten przykład jest prawdopodobnie nieaktualny, ponieważ spodziewam się, że większość nowoczesnych gier korzysta z gotowego silnika fizycznego, takiego jak Havok.

Poruszył go tylko jeden post, ale pojawia się duży problem podczas udostępniania danych między procesami. Chcesz uniknąć sytuacji, w których wiele procesów próbuje jednocześnie modyfikować tę samą linię pamięci podręcznej. Coś, na co należy zwrócić uwagę, to „fałszywe” udostępnianie, w którym dwie sąsiednie struktury danych współdzielą linię pamięci podręcznej, a modyfikacje jednej unieważniają linię pamięci podręcznej dla drugiej. Może to powodować niepotrzebne przemieszczanie się linii pamięci podręcznej między pamięcią podręczną procesora udostępniającą dane w systemie wieloprocesorowym. Aby tego uniknąć, należy wyrównać i uzupełnić struktury danych, aby umieścić je w różnych wierszach.

Uwaga dotycząca „klasycznego przykładu” użytkownika 1800 INFORMACJE (zbyt długi na komentarz)

Chciałem sprawdzić różnice czasu dla dwóch rzędów iteracji („zewnętrzny” i „wewnętrzny”), więc wykonałem prosty eksperyment z dużą tablicą 2D:

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
    sum += A[ x + y*N ];
measure::stop();

a drugi przypadek z rozszerzeniem for zamienionymi pętlami.

Wolniejsza wersja („x first”) miała 0,88 sekundy, a szybsza 0,06 sekundy. To jest moc buforowania :)

Użyłem gcc -O2i nadal pętle nie zostały zoptymalizowane. Komentarz Ricardo, że „większość współczesnych kompilatorów potrafi samodzielnie to rozgryźć” nie jest trafny

Mogę odpowiedzieć (2), mówiąc, że w świecie C ++ połączone listy mogą łatwo zabić pamięć podręczną procesora. W miarę możliwości lepszym rozwiązaniem są tablice. Brak doświadczenia, czy to samo dotyczy innych języków, ale łatwo sobie wyobrazić, że pojawią się te same problemy.

Pamięć podręczna jest ułożona w „wierszach pamięci podręcznej”, a (rzeczywista) pamięć jest odczytywana i zapisywana we fragmentach o tym rozmiarze.

Struktury danych zawarte w pojedynczej linii pamięci podręcznej są zatem bardziej wydajne.

Podobnie algorytmy, które uzyskują dostęp do ciągłych bloków pamięci, będą bardziej wydajne niż algorytmy, które przeskakują przez pamięć w losowej kolejności.

Niestety rozmiar linii pamięci podręcznej różni się znacznie między procesorami, więc nie ma sposobu, aby zagwarantować, że struktura danych optymalna na jednym procesorze będzie wydajna na innym.

Aby zapytać, jak utworzyć kod, buforować efektywną pamięć podręczną i większość innych pytań, zwykle zapytać, jak zoptymalizować program, ponieważ pamięć podręczna ma tak ogromny wpływ na wydajność, że każdy zoptymalizowany program jest pamięcią podręczną przyjazny dla efektywnej pamięci podręcznej.

Sugeruję przeczytanie o optymalizacji, na tej stronie jest kilka dobrych odpowiedzi. Jeśli chodzi o książki, polecam książkę Computer Systems: A Programmer's Perspective, która zawiera drobny tekst na temat prawidłowego korzystania z pamięci podręcznej.

(btw - tak źle, jak może być brak pamięci podręcznej, jest gorzej - jeśli program stronicuje z dysku twardego ...)

Było wiele odpowiedzi dotyczących ogólnych porad, takich jak wybór struktury danych, wzorzec dostępu, itp. W tym miejscu chciałbym dodać kolejny wzorzec projektowania kodu, zwany potokiem oprogramowania, który wykorzystuje aktywne zarządzanie pamięcią podręczną.

Pomysł jest zapożyczony z innych technik potokowych, np. Potokowania instrukcji procesora.

Ten typ wzoru najlepiej pasuje do procedur, które

1. można podzielić na rozsądne wielokrotne podetapy, S [1], S [2], S [3], ... których czas wykonania jest w przybliżeniu porównywalny z czasem dostępu do pamięci RAM (~ 60-70ns).
2. pobiera pakiet danych wejściowych i wykonuje na nich wyżej wymienione wiele czynności, aby uzyskać wynik.

Weźmy prosty przypadek, w którym jest tylko jedna procedura podrzędna. Zwykle kod chciałby:

def proc(input):
    return sub-step(input))

Aby uzyskać lepszą wydajność, możesz chcieć przekazać wiele danych wejściowych do funkcji w partii, aby zamortyzować narzut wywołania funkcji, a także zwiększyć lokalność pamięci podręcznej kodu.

def batch_proc(inputs):
    results = []
    for i in inputs:
        // avoids code cache miss, but still suffer data(inputs) miss
        results.append(sub-step(i))
    return res

Jednak, jak wspomniano wcześniej, jeśli wykonanie kroku jest mniej więcej takie samo jak czas dostępu do pamięci RAM, możesz dalej ulepszyć kod do czegoś takiego:

def batch_pipelined_proc(inputs):
    for i in range(0, len(inputs)-1):
        prefetch(inputs[i+1])
        # work on current item while [i+1] is flying back from RAM
        results.append(sub-step(inputs[i-1]))

    results.append(sub-step(inputs[-1]))

Przepływ wykonania wyglądałby następująco:

1. pobieranie wstępne (1) żąda od CPU pobrania wstępnego danych wejściowych [1] do pamięci podręcznej, gdzie instrukcja pobierania wstępnego pobiera P cykli i powraca, aw tle wejście [1] przychodzi do pamięci podręcznej po R cyklach.
2. works_on (0) cold miss on 0 i działa na nim, co zabiera M
3. prefetch (2) wyda kolejne pobieranie
4. works_on (1) jeśli P + R <= M, to dane wejściowe [1] powinny znajdować się w pamięci podręcznej już przed tym krokiem, aby uniknąć utraty danych w pamięci podręcznej
5. works_on (2) ...

Może być zaangażowanych więcej kroków, wtedy możesz zaprojektować wieloetapowy potok, o ile czas kroków i opóźnienie dostępu do pamięci pasują do siebie, cierpiałbyś na niewielką utratę pamięci podręcznej kodu / danych. Jednak proces ten wymaga wielu eksperymentów, aby znaleźć prawidłowe grupowanie kroków i czas pobierania wstępnego. Ze względu na wymagany wysiłek, widzi większą adaptację w wydajnym przetwarzaniu strumieni danych / pakietów. Dobry przykład kodu produkcyjnego można znaleźć w DPDK QoS Enqueue pipeline design: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Rozdział 21.2.4.3. Kolejkuj potok.

Więcej informacji można znaleźć:

https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

Napisz swój program tak, aby miał jak najmniejszy rozmiar. Dlatego nie zawsze dobrym pomysłem jest stosowanie optymalizacji -O3 dla GCC. Zajmuje większy rozmiar. Często -Os jest tak samo dobre jak -O2. Wszystko zależy jednak od używanego procesora. YMMV.

Pracuj z małymi porcjami danych naraz. Dlatego mniej wydajne algorytmy sortowania mogą działać szybciej niż szybkie sortowanie, jeśli zestaw danych jest duży. Znajdź sposoby na podzielenie większych zbiorów danych na mniejsze. Inni to sugerowali.

Aby pomóc ci lepiej wykorzystać lokalność czasową / przestrzenną instrukcji, możesz chcieć przestudiować, w jaki sposób twój kod jest konwertowany na asembler. Na przykład:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

Dwie pętle generują różne kody, mimo że po prostu analizują tablicę. W każdym razie twoje pytanie jest bardzo specyficzne dla architektury. Tak więc jedynym sposobem ścisłej kontroli wykorzystania pamięci podręcznej jest zrozumienie, jak działa sprzęt i optymalizacja kodu.

Oprócz wyrównywania struktury i pól, jeśli twoja struktura jest przydzielona sterta, możesz chcieć użyć alokatorów, które obsługują wyrównane alokacje; jak _aligned_malloc (sizeof (DANE), SYSTEM_CACHE_LINE_SIZE); w przeciwnym razie możesz mieć losowe fałszywe udostępnianie; pamiętaj, że w systemie Windows domyślna sterta ma 16-bajtowe wyrównanie.