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

159

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ć.

złoty środek
źródło
1
Jako intro tej rozmowie daje dobry przegląd youtu.be/BP6NxVxDQIs
schoetbi
Wydaje się, że powyższy skrócony adres URL już nie działa, oto pełny adres URL do rozmowy: youtube.com/watch?v=BP6NxVxDQIs
Abhinav Upadhyay

Odpowiedzi:

119

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.

Mats N
źródło
5
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. Czy mogę zapytać, jakiego rodzaju narzędzia do profilowania dostarczają takich informacji i w jaki sposób?
Dragon Energy
„Uporządkuj swoje dane, aby uniknąć dziur w wyrównaniu (sortowanie elementów struktury poprzez zmniejszanie rozmiaru jest jednokierunkowe)” - dlaczego kompilator sam tego nie optymalizuje? dlaczego kompilator nie zawsze może „sortować członków po zmniejszeniu rozmiaru”? Jaka jest korzyść, jeśli członkowie są nieposortowani?
javapowered
Nie znam początków, ale po pierwsze, kolejność członków jest kluczowa w, powiedzmy, komunikacji sieciowej, w której możesz chcieć przesyłać całe struktury bajt po bajcie przez sieć.
Kobrar
1
@javapowered Kompilator może to zrobić w zależności od języka, chociaż nie jestem pewien, czy którykolwiek z nich to robi. Powodem, dla którego nie możesz tego zrobić w C, jest to, że całkowicie poprawne jest adresowanie członków przez adres bazowy + przesunięcie zamiast nazwy, co oznacza, że ​​zmiana kolejności członków całkowicie zepsuje program.
Dan Bechard,
56

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.

1800 INFORMACJE
źródło
9
na studiach mieliśmy zadanie z mnożenia macierzy. Okazało się, że szybciej było najpierw dokonać transpozycji macierzy "kolumn" i pomnożyć wiersze po wierszach, a nie wiersze po kolumnach, właśnie z tego powodu.
ykaganovich
11
w rzeczywistości większość współczesnych kompilatorów może samodzielnie to rozgryźć (z włączonymi optymalizacjami)
Ricardo Nolde
1
@ykaganovich To również przykład w artykule Ulricha Dreppersa: lwn.net/Articles/255364
Simon Stender Boisen
Nie jestem pewien, czy to zawsze jest poprawne - jeśli cała tablica mieści się w pamięci podręcznej L1 (często 32k!), Oba zamówienia będą miały taką samą liczbę trafień i chybień w pamięci podręcznej. Być może wstępne pobieranie pamięci może mieć jakiś wpływ, jak sądzę. Oczywiście szczęśliwy, że zostałem poprawiony.
Matt Parkins
kto kiedykolwiek wybierze pierwszą wersję tego kodu, jeśli kolejność nie ma znaczenia?
silver_rocket
45

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.

jalf
źródło
4
+1, dobra i praktyczna rada. Jeden dodatek: połączenie lokalności czasowej i lokalności przestrzennej sugeruje, że na przykład dla operacji macierzowych może być wskazane podzielenie ich na mniejsze macierze, które całkowicie mieszczą się w linii pamięci podręcznej lub których wiersze / kolumny pasują do linii pamięci podręcznej. Pamiętam, jak robiłem to dla wizualizacji wielu elementów. dane. Zapewniało to poważnego kopa w spodnie. Warto pamiętać, że cache zawiera więcej niż jedną „linię”;)
AndreasT
1
Mówisz, że tylko 1 procesor może mieć dany adres w pamięci podręcznej L1 na raz - zakładam, że masz na myśli linie pamięci podręcznej, a nie adres. Słyszałem również o fałszywych problemach z udostępnianiem, gdy co najmniej jeden z procesorów wykonuje zapis, ale nie, jeśli oba wykonują tylko odczyty. Więc przez „dostęp” masz na myśli pisanie?
Joseph Garvin
2
@JosephGarvin: tak, miałem na myśli pisze. Masz rację, wiele rdzeni może mieć te same linie pamięci podręcznej w swoich pamięciach podręcznych L1 w tym samym czasie, ale kiedy jeden rdzeń zapisuje na te adresy, zostaje unieważniony we wszystkich innych pamięciach podręcznych L1, a następnie muszą go ponownie załadować, zanim będą mogli to zrobić cokolwiek z tym. Przepraszamy za nieprecyzyjne (niewłaściwe) sformułowanie. :)
jalf
44

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

Tomi Kyöstilä
źródło
16
Powinieneś dodać podsumowanie głównych punktów z artykułu.
Azmisov
Świetnie się czyta, ale kolejną książką, o której MUSI zostać tutaj wymieniona, jest Hennessy, Patterson, Computer Architecture, A Quantitiative Approach , która jest już dostępna w piątym wydaniu.
Haymo Kutschbach
15

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.

Michael Borgwardt
źródło
9

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.

Grover
źródło
@Grover: O twoim punkcie 2. więc można powiedzieć, że jeśli w ciasnej pętli wywoływana jest funkcja dla każdej liczby pętli, to pobierze nowy kod w całości i spowoduje brak pamięci podręcznej, zamiast tego, jeśli możesz umieścić tę funkcję jako kod w samej pętli for, bez wywołania funkcji, byłoby szybsze z powodu mniejszej liczby braków w pamięci podręcznej?
goldenmean
1
Tak i nie. Nowa funkcja zostanie załadowana do pamięci podręcznej. Jeśli jest wystarczająco dużo miejsca w pamięci podręcznej, przy drugiej iteracji będzie już mieć tę funkcję w pamięci podręcznej, więc nie ma powodu, aby ją ponownie ładować. Więc to trafienie od pierwszego połączenia. W C / C ++ możesz poprosić kompilator o umieszczenie funkcji tuż obok siebie za pomocą odpowiednich segmentów.
grover
Jeszcze jedna uwaga: jeśli wywołasz pętlę i nie ma wystarczającej ilości miejsca w pamięci podręcznej, nowa funkcja zostanie załadowana do pamięci podręcznej niezależnie. Może się nawet zdarzyć, że oryginalna pętla zostanie wyrzucona z pamięci podręcznej. W takim przypadku wywołanie pociągnie za sobą do trzech kar za każdą iterację: jedna za załadowanie celu wywołania, a druga za przeładowanie pętli. I trzecia, jeśli końcówka pętli nie znajduje się w tej samej linii pamięci podręcznej, co adres zwrotny połączenia. W takim przypadku skok do głowicy pętli również wymaga nowego dostępu do pamięci.
grover
8

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.

Zan Lynx
źródło
2
+1 Wcale nieaktualne. Jest to najlepszy sposób organizowania danych dla silników gier - utwórz bloki danych ciągłymi i wykonaj wszystkie operacje danego typu (powiedzmy AI) przed przejściem do następnej (powiedzmy fizyki), aby wykorzystać bliskość / lokalizację pamięci podręcznej odniesienie.
Inżynier
Widziałem ten dokładny przykład w filmie gdzieś kilka tygodni temu, ale od tego czasu straciłem do niego link / nie pamiętam, jak go znaleźć. Czy pamiętasz, gdzie widziałeś ten przykład?
będzie
@will: Nie, nie pamiętam dokładnie, gdzie to było.
Zan Lynx,
Na tym polega idea systemu komponentów encji (ECS: en.wikipedia.org/wiki/Entity_component_system ). Przechowuj dane jako struktury tablic, a nie bardziej tradycyjne tablice struktur, do których zachęcają praktyki OOP.
BuschnicK
7

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.

RussellH
źródło
7

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

Jakub M.
źródło
Nie jestem pewien, czy to rozumiem. W obu przykładach nadal uzyskujesz dostęp do każdej zmiennej w pętli for. Dlaczego jedna droga jest szybsza niż druga?
wyd-
ostatecznie intuicyjnie rozumiem, jak to wpływa :)
Laie
@EdwardCorlew Wynika to z kolejności, w jakiej są uzyskiwane. Pierwsza kolejność Y jest szybsza, ponieważ uzyskuje dostęp do danych sekwencyjnie. Kiedy żądany jest pierwszy wpis, pamięć podręczna L1 ładuje całą linię pamięci podręcznej, która zawiera żądany int plus następne 15 (zakładając 64-bajtową linię pamięci podręcznej), więc nie ma opóźnienia procesora czekającego na następne 15. X -pierwsza kolejność jest wolniejsza, ponieważ element, do którego uzyskiwany jest dostęp, nie jest sekwencyjny i przypuszczalnie N jest na tyle duże, że pamięć, do której uzyskiwany jest dostęp, zawsze znajduje się poza pamięcią podręczną L1, a więc każda operacja zatrzymuje się.
Matt Parkins
4

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.

Andrzej
źródło
@ Andrew: A co ze strukturami. Czy są wydajne w pamięci podręcznej? Czy mają jakieś ograniczenia rozmiaru, aby były wydajne w pamięci podręcznej?
goldenmean
Struktura to pojedynczy blok pamięci, więc dopóki nie przekracza rozmiaru twojej pamięci podręcznej, nie zobaczysz wpływu. Tylko wtedy, gdy masz kolekcję struktur (lub klas), zobaczysz trafienia w pamięci podręcznej i zależy to od sposobu organizacji kolekcji. Tablica styka obiekty ze sobą (dobrze), ale połączona lista może zawierać obiekty w całej przestrzeni adresowej z łączami między nimi, co oczywiście niekorzystnie wpływa na wydajność pamięci podręcznej.
Andrew,
Pewnym sposobem korzystania z list połączonych bez zabijania pamięci podręcznej, najbardziej efektywnym w przypadku niewielkich list, jest utworzenie własnej puli pamięci, to znaczy - przydzielenie jednej dużej tablicy. wtedy zamiast „malloc” (lub „new” in C ++) pamięci dla każdego małego połączonego elementu listy, który może być przydzielony w zupełnie innym miejscu w pamięci, i marnować miejsce na zarządzanie, dajesz mu pamięć z puli pamięci, znacznie zwiększając prawdopodobieństwo, że logicznie zamykają się członkowie listy, znajdą się razem w pamięci podręcznej.
Liran Orevi
Jasne, ale uzyskanie std :: list <> i in. To dużo pracy. aby użyć własnych bloków pamięci. Kiedy byłem młodym whippersnapperem, absolutnie szedłem tą ścieżką, ale teraz ... zbyt wiele innych rzeczy do rozwiązania.
Andrew,
4

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.

Alnitak
źródło
niekoniecznie. po prostu uważaj na fałszywe udostępnianie. czasami musisz podzielić dane na różne linie pamięci podręcznej. skuteczność pamięci podręcznej zawsze zależy od sposobu jej wykorzystania.
DAG
4

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

Liran Orevi
źródło
4

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

Wei Shen
źródło
1

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.

sybreon
źródło
Ciekawy punkt. Czy pamięci podręczne z wyprzedzeniem przyjmują założenia na podstawie kierunku pętli / przejścia przez pamięć?
Andrew,
1
Istnieje wiele sposobów projektowania spekulacyjnych pamięci podręcznych danych. Te oparte na krokach mierzą „odległość” i „kierunek” dostępu do danych. Te oparte na treści ścigają łańcuchy wskaźników. Istnieją inne sposoby ich zaprojektowania.
sybreon
1

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.

aracntido
źródło