Należy również pamiętać o wielkości linii pamięci podręcznej. W nowoczesnych procesorach często ma 64 bajty.
John Dibling
3
Oto kolejny bardzo dobry artykuł. Zasady dotyczą programów C / C ++ w dowolnym systemie operacyjnym (Linux, MaxOS lub Windows): lwn.net/Articles/255364
Na współczesnych komputerach tylko struktury pamięci najniższego poziomu ( rejestry ) mogą przenosić dane w pojedynczych cyklach zegara. Rejestry są jednak bardzo drogie, a większość rdzeni komputerowych ma mniej niż kilkadziesiąt rejestrów ( łącznie od kilkuset do może tysiąca bajtów ). Na drugim końcu spektrum pamięci ( DRAM ) pamięć jest bardzo tania (tj. Dosłownie miliony razy tańsza ), ale zajmuje setki cykli po otrzymaniu danych. Aby wypełnić tę lukę między superszybkim i drogim a super wolnym i tanim, są pamięci podręczne, o nazwie L1, L2, L3 o malejącej prędkości i koszcie. Chodzi o to, że większość wykonywanego kodu często uderza w mały zestaw zmiennych, a reszta (znacznie większy zestaw zmiennych) rzadko. Jeśli procesor nie może znaleźć danych w pamięci podręcznej L1, wówczas szuka w pamięci podręcznej L2. Jeśli nie, to pamięć podręczna L3, a jeśli nie, pamięć główna. Każdy z tych „braków” jest z czasem drogi.
(Analogią jest pamięć podręczna pamięci systemowej, ponieważ pamięć systemowa jest zbyt dyskiem twardym. Dysk twardy jest super tani, ale bardzo wolny).
Buforowanie jest jedną z głównych metod zmniejszania wpływu opóźnienia . Parafrazując Herb Sutter (por. Linki poniżej): zwiększenie przepustowości jest łatwe, ale nie możemy kupić drogi wyjścia z opóźnień .
Dane są zawsze pobierane przez hierarchię pamięci (najmniejsze == najszybsze do najwolniejszych). Cache hit / Panna odnosi się zwykle do przeboju / brakuje w najwyższym poziomie w pamięci podręcznej procesora - o najwyższym poziomie to znaczy największa == najwolniej. Współczynnik trafień w pamięci podręcznej ma kluczowe znaczenie dla wydajności, ponieważ każde pominięcie pamięci podręcznej powoduje pobranie danych z pamięci RAM (lub gorzej ...), co zajmuje dużo czasu (setki cykli dla RAM, dziesiątki milionów cykli dla HDD). Dla porównania, odczyt danych z pamięci podręcznej (najwyższego poziomu) zwykle zajmuje tylko garść cykli.
We współczesnych architekturach komputerowych wąskim gardłem wydajności jest opuszczanie procesora (np. Uzyskiwanie dostępu do pamięci RAM lub wyższej). Z czasem sytuacja się pogorszy. Wzrost częstotliwości procesora nie jest obecnie istotny dla zwiększenia wydajności. Problemem jest dostęp do pamięci. W związku z tym wysiłki związane z projektowaniem sprzętu w procesorach koncentrują się obecnie na optymalizacji pamięci podręcznej, pobierania wstępnego, potoków i współbieżności. Na przykład nowoczesne procesory wydają około 85% pamięci na pamięci podręczne i do 99% na przechowywanie / przenoszenie danych!
Na ten temat można wiele powiedzieć. Oto kilka świetnych odniesień do pamięci podręcznych, hierarchii pamięci i właściwego programowania:
Strona Agner Fog . W jego doskonałych dokumentach można znaleźć szczegółowe przykłady obejmujące języki, od asemblera po C ++.
Główne pojęcia dotyczące kodu przyjaznego dla pamięci podręcznej
Bardzo ważnym aspektem kodu przyjaznego dla pamięci podręcznej jest zasada lokalności , której celem jest umieszczenie powiązanych danych w pamięci, aby umożliwić efektywne buforowanie. Jeśli chodzi o pamięć podręczną procesora, należy pamiętać o liniach pamięci podręcznej, aby zrozumieć, jak to działa: Jak działają linie pamięci podręcznej?
Następujące szczególne aspekty mają duże znaczenie dla optymalizacji buforowania:
Lokalizacja czasowa : po uzyskaniu dostępu do danej lokalizacji w pamięci prawdopodobne jest, że w niedalekiej przyszłości ponownie będzie dostępna ta sama lokalizacja. W idealnym przypadku informacje te będą nadal buforowane w tym miejscu.
Lokalizacja przestrzenna : dotyczy to umieszczania powiązanych danych blisko siebie. Buforowanie odbywa się na wielu poziomach, nie tylko w procesorze. Na przykład, gdy czytasz z pamięci RAM, zwykle pobierana jest większa część pamięci niż ta, o którą konkretnie poprosiliśmy, ponieważ bardzo często program będzie wkrótce wymagał tych danych. Pamięci podręczne dysków twardych są zgodne z tą samą myślą. Szczególnie w przypadku pamięci podręcznych procesorów ważne jest pojęcie linii pamięci podręcznej .
Prostym przykładem przyjaznych pamięci podręcznej i nieprzyjaznych pamięci podręcznej jest c ++w std::vectorporównaniu z std::list. Elementy a std::vectorsą przechowywane w ciągłej pamięci, dlatego dostęp do nich jest o wiele bardziej przyjazny dla pamięci podręcznej niż dostęp do elementów w a std::list, które przechowują jego zawartość w dowolnym miejscu. Wynika to z lokalizacji przestrzennej.
Bardzo ładną ilustracją tego jest Bjarne Stroustrup w tym klipie na youtube (dzięki @Mohammad Ali Baydoun za link!).
Nie zaniedbuj pamięci podręcznej w strukturze danych i projekcie algorytmu
W miarę możliwości staraj się dostosowywać struktury danych i kolejność obliczeń w taki sposób, aby maksymalnie wykorzystać pamięć podręczną. Powszechną techniką w tym zakresie jest blokowanie pamięci podręcznej (wersja Archive.org) , która ma ogromne znaczenie w obliczeniach o wysokiej wydajności (np. ATLAS ).
Znać i wykorzystywać ukrytą strukturę danych
Innym prostym przykładem, o którym wielu ludzi w tej dziedzinie czasami zapomina, jest kolumna główna (np. fortran,Matlab) a porządkowanie według rzędów (np. do,c ++) do przechowywania tablic dwuwymiarowych. Rozważmy na przykład następującą macierz:
1234
W porządku rzędów głównych jest to przechowywane w pamięci jako 1 2 3 4; w uporządkowaniu według głównych kolumn byłoby to przechowywane jako 1 3 2 4. Łatwo zauważyć, że implementacje, które nie wykorzystują tego porządku, szybko napotkają (łatwo uniknąć!) Problemy z pamięcią podręczną. Niestety, widzę rzeczy, jak to bardzo często w mojej domeny (uczenia maszynowego). @MatteoItalia pokazał ten przykład bardziej szczegółowo w swojej odpowiedzi.
Podczas pobierania określonego elementu macierzy z pamięci elementy w jego pobliżu zostaną również pobrane i zapisane w linii pamięci podręcznej. Jeśli zostanie wykorzystana kolejność, spowoduje to mniejszy dostęp do pamięci (ponieważ kilka kolejnych wartości potrzebnych do kolejnych obliczeń znajduje się już w linii pamięci podręcznej).
Dla uproszczenia załóżmy, że pamięć podręczna zawiera pojedynczą linię pamięci podręcznej, która może zawierać 2 elementy macierzy i że gdy dany element jest pobierany z pamięci, następny też jest następny. Powiedzmy, że chcemy przejąć sumę nad wszystkimi elementami w powyższej przykładowej macierzy 2x2 (nazwijmy to M):
Wykorzystanie kolejności (np. Zmiana indeksu kolumny najpierw w c ++):
W tym prostym przykładzie wykorzystanie zamówienia w przybliżeniu podwaja szybkość wykonywania (ponieważ dostęp do pamięci wymaga znacznie więcej cykli niż obliczanie sum). W praktyce różnica wydajności może być znacznie większa.
Unikaj nieprzewidywalnych gałęzi
Nowoczesne architektury zawierają potoki, a kompilatory stają się bardzo dobre w zmianie kolejności kodu, aby zminimalizować opóźnienia z powodu dostępu do pamięci. Gdy kod krytyczny zawiera (nieprzewidywalne) gałęzie, pobranie danych jest trudne lub niemożliwe. To pośrednio doprowadzi do większej liczby braków w pamięci podręcznej.
W kontekście c ++, virtualmetody stanowią kontrowersyjny problem z brakami pamięci podręcznej (istnieje ogólna zgoda, że należy ich unikać, jeśli to możliwe, pod względem wydajności). Funkcje wirtualne mogą powodować brak pamięci podręcznej podczas wyszukiwania, ale dzieje się tak tylko wtedy, gdy konkretna funkcja nie jest często wywoływana (w przeciwnym razie prawdopodobnie byłaby buforowana), więc niektórzy uważają to za problem. Aby uzyskać informacje na temat tego problemu, sprawdź: Jaki jest koszt wydajności posiadania metody wirtualnej w klasie C ++?
Częste problemy
Częstym problemem we współczesnych architekturach z wieloprocesorowymi pamięciami podręcznymi jest fałszywe współdzielenie . Dzieje się tak, gdy każdy procesor próbuje użyć danych w innym regionie pamięci i próbuje zapisać je w tej samej linii pamięci podręcznej . Powoduje to, że wiersz pamięci podręcznej - który zawiera dane, których może użyć inny procesor - jest wielokrotnie zastępowany. W efekcie różne wątki zmuszają się do wzajemnego oczekiwania, powodując w tej sytuacji brak pamięci podręcznej. Zobacz także (dzięki @Matt za link): Jak i kiedy wyrównać do rozmiaru linii pamięci podręcznej?
Ekstremalnym objawem słabego buforowania w pamięci RAM (co prawdopodobnie nie jest tym, co masz na myśli w tym kontekście), jest tak zwane thrashowanie . Dzieje się tak, gdy proces w sposób ciągły generuje błędy strony (np. Uzyskuje dostęp do pamięci, której nie ma na bieżącej stronie), które wymagają dostępu do dysku.
być może mógłbyś nieco rozszerzyć odpowiedź, wyjaśniając również, że w wielowątkowym kodzie dane mogą być również zbyt lokalne (np. fałszywe udostępnianie)
TemplateRex
2
Pamięć podręczna może mieć tyle poziomów, ile projektanci układów uznają za przydatną. Na ogół równoważą prędkość z rozmiarem. Gdybyś mógł uczynić pamięć podręczną L1 tak dużą jak L5 i tak szybko, potrzebujesz tylko L1.
Rafael Baptista
24
Zdaję sobie sprawę, że puste stosy zgody są odrzucane na StackOverflow, ale jest to szczerze mówiąc najczystsza, najlepsza odpowiedź, jaką do tej pory widziałem. Świetna robota, Marc.
Jack Aidley
2
@JackAidley dziękuję za pochwałę! Kiedy zobaczyłem, jak wiele uwagi poświęcono temu pytaniu, pomyślałem, że wiele osób może być zainteresowanych dość obszernym wyjaśnieniem. Cieszę się, że to przydatne.
Marc Claesen
1
Nie wspomniałeś o tym, że struktury danych przyjazne dla pamięci podręcznej są zaprojektowane tak, aby pasowały do linii pamięci podręcznej i były dopasowane do pamięci, aby optymalnie wykorzystać linie pamięci podręcznej. Świetna odpowiedź! niesamowite.
Matt
140
Oprócz odpowiedzi @Marc Claesen uważam, że pouczającym klasycznym przykładem nieprzyjaznego dla pamięci podręcznej kodu jest kod, który skanuje tablicę dwuwymiarową C (np. Obraz bitmapowy) pod względem kolumny zamiast wiersza.
Elementy sąsiadujące w rzędzie również sąsiadują w pamięci, a zatem dostęp do nich w kolejności oznacza dostęp do nich w kolejności rosnącej; jest to przyjazne dla pamięci podręcznej, ponieważ pamięć podręczna ma tendencję do pobierania sąsiadujących bloków pamięci.
Zamiast tego dostęp do takich elementów pod względem kolumn jest nieprzyjazny dla pamięci podręcznej, ponieważ elementy w tej samej kolumnie są odległe od siebie w pamięci (w szczególności ich odległość jest równa wielkości wiersza), więc kiedy używasz tego wzorca dostępu, skaczą w pamięci, potencjalnie marnując wysiłek związany z pamięcią podręczną wyszukiwania elementów znajdujących się w pobliżu w pamięci.
I wszystko, czego potrzeba, aby zrujnować wydajność, to przejść
// Cache-friendly version - processes pixels which are adjacent in memoryfor(unsignedint y=0; y<height;++y){for(unsignedint x=0; x<width;++x){... image[y][x]...}}
do
// Cache-unfriendly version - jumps around in memory for no good reasonfor(unsignedint x=0; x<width;++x){for(unsignedint y=0; y<height;++y){... image[y][x]...}}
Efekt ten może być dość dramatyczny (kilka rzędów wielkości w prędkości) w systemach z małymi pamięciami podręcznymi i / lub pracą z dużymi macierzami (np. Ponad 10 megapikseli obrazów 24 bpp na obecnych maszynach); z tego powodu, jeśli musisz wykonać wiele skanów w pionie, często lepiej jest najpierw obrócić obraz o 90 stopni, a następnie wykonać różne analizy, ograniczając nieprzyjazny dla pamięci podręcznej kod tylko do obrotu.
Nowoczesne edytory obrazów używają kafelków jako pamięci wewnętrznej, np. Bloki 64 x 64 pikseli. Jest to o wiele bardziej przyjazne dla pamięci podręcznej dla operacji lokalnych (umieszczanie zimowania, uruchamianie filtra rozmycia), ponieważ sąsiednie piksele są przez większość czasu blisko pamięci w obu kierunkach.
maksymalnie
Próbowałem mierzyć podobny czas na moim komputerze i stwierdziłem, że czasy były takie same. Czy ktoś jeszcze próbował to zrobić?
gsingh2011
@ I3arnon: nie, pierwsza jest przyjazna dla pamięci podręcznej, ponieważ zwykle w C tablice są przechowywane w kolejności głównej (oczywiście jeśli obraz z jakiegoś powodu jest przechowywany w kolejności głównej), odwrotność jest prawdziwa.
Matteo Italia
1
@Gauthier: tak, pierwszy fragment jest dobry; Wydaje mi się, że kiedy to napisałem, pomyślałem w stylu „Wszystko, co [zepsuć działanie działającej aplikacji], to przejść od ... do ...”
Matteo Italia,
88
Optymalizacja użycia pamięci podręcznej sprowadza się w dużej mierze do dwóch czynników.
Lokalizacja odniesienia
Pierwszym czynnikiem (do którego nawiązywali inni) jest lokalizacja odniesienia. Lokalizacja odniesienia ma jednak naprawdę dwa wymiary: przestrzeń i czas.
Przestrzenny
Wymiar przestrzenny sprowadza się również do dwóch rzeczy: po pierwsze, chcemy gęsto upakować nasze informacje, aby więcej informacji zmieściło się w tej ograniczonej pamięci. Oznacza to (na przykład), że potrzebna jest znaczna poprawa złożoności obliczeniowej, aby uzasadnić struktury danych oparte na małych węzłach połączonych wskaźnikami.
Po drugie, chcemy, aby informacje, które będą przetwarzane razem, również były zlokalizowane razem. Typowa pamięć podręczna działa w „liniach”, co oznacza, że gdy uzyskasz dostęp do niektórych informacji, inne informacje z pobliskich adresów zostaną załadowane do pamięci podręcznej wraz z dotkniętą częścią. Na przykład po dotknięciu jednego bajtu pamięć podręczna może załadować 128 lub 256 bajtów w pobliżu tego. Aby z tego skorzystać, zazwyczaj chcesz, aby dane były uporządkowane tak, aby zmaksymalizować prawdopodobieństwo, że użyjesz również innych danych, które zostały załadowane w tym samym czasie.
Na przykład bardzo trywialny przykład może to oznaczać, że wyszukiwanie liniowe może być znacznie bardziej konkurencyjne w przypadku wyszukiwania binarnego, niż można się spodziewać. Po załadowaniu jednego elementu z wiersza pamięci podręcznej korzystanie z reszty danych w tym wierszu pamięci podręcznej jest prawie bezpłatne. Wyszukiwanie binarne staje się zauważalnie szybsze tylko wtedy, gdy dane są na tyle duże, że wyszukiwanie binarne zmniejsza liczbę linii pamięci podręcznej, do których masz dostęp.
Czas
Wymiar czasu oznacza, że wykonując niektóre operacje na niektórych danych, chcesz (w jak największym stopniu) wykonywać wszystkie operacje na tych danych jednocześnie.
Odkąd określili to jako C ++, będę wskazywać na klasyczny przykład konstrukcji stosunkowo cache-nieprzyjazny: std::valarray. valarrayPrzeciążenia najbardziej arytmetyczne operatory, więc może (na przykład) powiedzieć a = b + c + d;(gdzie a, b, ci dsą valarrays) zrobić element mądry dodanie tych tablic.
Problem polega na tym, że przechodzi przez jedną parę danych wejściowych, umieszcza wyniki tymczasowo, przechodzi przez inną parę danych wejściowych i tak dalej. Przy dużej ilości danych wynik jednego obliczenia może zniknąć z pamięci podręcznej, zanim zostanie wykorzystany w następnym obliczeniu, więc kończymy odczytywanie (i zapisywanie) danych wielokrotnie, zanim uzyskamy końcowy wynik. Jeśli każdy element końcowy rezultat będzie coś takiego (a[n] + b[n]) * (c[n] + d[n]);, to na ogół wolą czytać każdy a[n], b[n], c[n]i d[n]raz, wykonać obliczenia, pisać rezultacie przyrost ni powtórzyć „til skończymy. 2)
Udostępnianie linii
Drugim ważnym czynnikiem jest unikanie dzielenia linii. Aby to zrozumieć, prawdopodobnie musimy wykonać kopię zapasową i przyjrzeć się trochę, w jaki sposób organizowane są pamięci podręczne. Najprostsza forma pamięci podręcznej jest mapowana bezpośrednio. Oznacza to, że jeden adres w pamięci głównej można zapisać tylko w jednym konkretnym miejscu w pamięci podręcznej. Jeśli używamy dwóch elementów danych, które są mapowane do tego samego miejsca w pamięci podręcznej, działa to źle - za każdym razem, gdy używamy jednego elementu danych, drugi musi zostać usunięty z pamięci podręcznej, aby zrobić miejsce dla drugiego. Reszta pamięci podręcznej może być pusta, ale te elementy nie będą używać innych części pamięci podręcznej.
Aby temu zapobiec, większość pamięci podręcznych to tak zwane „ustawianie asocjacyjne”. Na przykład w 4-kierunkowej pamięci podręcznej skojarzonej z zestawem dowolny element z pamięci głównej można przechowywać w dowolnym z 4 różnych miejsc w pamięci podręcznej. Kiedy więc pamięć podręczna ma załadować element, szuka ostatnio używanego 3 elementu spośród tych czterech, opróżnia go do pamięci głównej i ładuje nowy element na swoim miejscu.
Problem jest prawdopodobnie dość oczywisty: w przypadku pamięci podręcznej z bezpośrednim odwzorowaniem dwa operandy, które akurat mapują do tej samej lokalizacji pamięci podręcznej, mogą prowadzić do złego zachowania. Pamięć podręczna skojarzona z zestawem N-way zwiększa liczbę z 2 do N + 1. Zorganizowanie pamięci podręcznej na więcej „sposobów” wymaga dodatkowych obwodów i ogólnie działa wolniej, więc (na przykład) 8192-drogowe skojarzenie pamięci podręcznej rzadko jest dobrym rozwiązaniem.
Ostatecznie ten czynnik jest trudniejszy do kontrolowania w przenośnym kodzie. Twoja kontrola nad tym, gdzie znajdują się Twoje dane, jest zwykle dość ograniczona. Co gorsza, dokładne odwzorowanie adresu na pamięć podręczną różni się w zależności od podobnych procesorów. W niektórych przypadkach warto jednak wykonać takie czynności, jak przydzielenie dużego bufora, a następnie użycie tylko części tego, co zostało przydzielone, aby zabezpieczyć dane przed współużytkowaniem tych samych linii pamięci podręcznej (nawet jeśli prawdopodobnie konieczne będzie wykrycie dokładnego procesora i działaj odpowiednio, aby to zrobić).
Fałszywe udostępnianie
Jest jeszcze jeden powiązany element zwany „fałszywym udostępnianiem”. Powstaje to w systemie wieloprocesorowym lub wielordzeniowym, w którym dwa (lub więcej) procesorów / rdzeni ma oddzielne dane, ale mieszczą się w tej samej linii pamięci podręcznej. Zmusza to dwa procesory / rdzenie do koordynowania dostępu do danych, nawet jeśli każdy ma swój własny, osobny element danych. Zwłaszcza, jeśli obydwoje modyfikują dane naprzemiennie, może to prowadzić do ogromnego spowolnienia, ponieważ dane muszą być stale przesyłane między procesorami. Nie można tego łatwo wyleczyć, organizując pamięć podręczną na więcej „sposobów” lub coś w tym rodzaju. Podstawowym sposobem zapobiegania temu jest zapewnienie, że dwa wątki rzadko (najlepiej nigdy) modyfikują dane, które mogą znajdować się w tej samej linii pamięci podręcznej (z tymi samymi zastrzeżeniami dotyczącymi trudności w kontrolowaniu adresów, pod którymi dane są przydzielane).
Ci, którzy dobrze znają C ++, mogą się zastanawiać, czy można to zoptymalizować za pomocą szablonów wyrażeń. Jestem prawie pewien, że odpowiedź brzmi: tak, można by to zrobić i gdyby tak było, prawdopodobnie byłaby to całkiem spora wygrana. Nie wiem jednak, że ktoś to zrobił, a biorąc pod uwagę, jak mało valarraysię przyzwyczaiłem, byłbym przynajmniej trochę zaskoczony, gdy ktoś to zrobił.
W przypadku, gdy ktoś zastanawia się, w jaki sposób valarray(zaprojektowany specjalnie pod kątem wydajności) może być tak bardzo źle, sprowadza się to do jednej rzeczy: został naprawdę zaprojektowany dla maszyn takich jak starsze Crays, które korzystały z szybkiej pamięci głównej i bez pamięci podręcznej. Dla nich był to naprawdę idealny projekt.
Tak, upraszczam: większość pamięci podręcznych tak naprawdę nie mierzy dokładnie ostatnio używanego przedmiotu, ale używa heurystyki, która ma być do tego zbliżona, bez konieczności zachowania pełnego znacznika czasu dla każdego dostępu.
Lubię dodatkowe informacje w twojej odpowiedzi, szczególnie valarrayprzykład.
Marc Claesen
1
+1 Wreszcie: prosty opis zestawu skojarzeń! EDYTUJ dalej: Jest to jedna z najbardziej pouczających odpowiedzi na temat SO. Dziękuję Ci.
Inżynier
32
Witamy w świecie projektowania zorientowanego na dane. Podstawową mantrą jest Sortowanie, Eliminowanie Oddziałów, Partia, Eliminowanie virtualpołączeń - wszystkie kroki w kierunku lepszej lokalizacji.
Po prostu stos: klasyczny przykład kodu nieprzyjaznego dla pamięci podręcznej w porównaniu z kodem przyjaznym dla pamięci podręcznej to „blokowanie pamięci podręcznej” macierzy.
Jeśli Njest duży, np. Jeśli N * sizeof(elemType)jest większy niż rozmiar pamięci podręcznej, wówczas każdy pojedynczy dostęp do src2[k][j]będzie brakiem pamięci podręcznej.
Istnieje wiele różnych sposobów optymalizacji tego pod kątem pamięci podręcznej. Oto bardzo prosty przykład: zamiast czytać jeden element na linię pamięci podręcznej w wewnętrznej pętli, użyj wszystkich elementów:
Jeśli rozmiar linii bufora wynosi 64 bajty, a działamy na liczbach zmiennoprzecinkowych 32-bitowych (4 bajty), wówczas w linii bufora jest 16 elementów. A liczba braków pamięci podręcznej dzięki tej prostej transformacji jest zmniejszona około 16-krotnie.
Bardziej zaawansowane transformacje działają na kafelkach 2D, optymalizują pod kątem wielu pamięci podręcznych (L1, L2, TLB) i tak dalej.
Niektóre wyniki „blokowania pamięci podręcznej” w Google:
Osoby, które to przeczytają, mogą być również zainteresowane moim artykułem na temat mnożenia macierzy, w którym przetestowałem „przyjazny dla pamięci podręcznej” algorytm ikj i nieprzyjazny algorytm ijk przez pomnożenie dwóch macierzy 2000 x 2000.
Martin Thoma
3
k==;Mam nadzieję, że to literówka?
TrebledJ
13
Procesory współdziałają dziś z wieloma poziomami kaskadowych obszarów pamięci. Więc procesor będzie miał sporo pamięci, która znajduje się w samym układzie procesora. Ma bardzo szybki dostęp do tej pamięci. Istnieją różne poziomy pamięci podręcznej, z których każdy ma wolniejszy dostęp (i większy) niż następny, dopóki nie dojdziesz do pamięci systemowej, która nie jest na CPU i jest stosunkowo wolniejsza.
Logicznie, do zestawu instrukcji CPU odwołujesz się tylko do adresów pamięci w gigantycznej wirtualnej przestrzeni adresowej. Gdy uzyskasz dostęp do pojedynczego adresu pamięci, procesor go pobierze. w dawnych czasach pobierał tylko ten jeden adres. Ale dzisiaj procesor pobierze sporo pamięci wokół żądanego bitu i skopiuje go do pamięci podręcznej. Zakłada się, że jeśli poprosiłeś o określony adres, istnieje duże prawdopodobieństwo, że wkrótce poprosisz o adres w pobliżu. Na przykład, jeśli kopiujesz bufor, możesz czytać i pisać z kolejnych adresów - jeden bezpośrednio po drugim.
Więc dzisiaj, kiedy pobierasz adres, sprawdza on pierwszy poziom pamięci podręcznej, aby sprawdzić, czy już odczytał ten adres do pamięci podręcznej, jeśli go nie znajdzie, to jest to brak pamięci podręcznej i musi przejść do następnego poziomu pamięć podręczną, aby ją znaleźć, aż w końcu musi wyjść do pamięci głównej.
Kod przyjazny dla pamięci podręcznej stara się utrzymywać dostęp do pamięci blisko siebie, aby zminimalizować błędy pamięci podręcznej.
Przykładem może być wyobraźnia, że chcesz skopiować gigantyczny 2-wymiarowy stół. Jest on uporządkowany z wierszem zasięgu w pamięci, a jeden wiersz następuje po drugim zaraz po.
Jeśli skopiowałeś elementy pojedynczo od lewej do prawej - byłoby to przyjazne dla pamięci podręcznej. Jeśli zdecydujesz się skopiować tabelę po jednej kolumnie na raz, skopiujesz dokładnie taką samą ilość pamięci - ale byłoby to nieprzyjazne dla pamięci podręcznej.
Należy wyjaśnić, że nie tylko dane powinny być przyjazne dla pamięci podręcznej, ale są równie ważne dla kodu. Jest to dodatek do przewidywania gałęzi, zmiany kolejności instrukcji, unikania faktycznych podziałów i innych technik.
Zazwyczaj im gęstszy kod, tym mniej linii pamięci podręcznej będzie wymaganych do jego przechowywania. Powoduje to, że dla danych dostępnych jest więcej wierszy pamięci podręcznej.
Kod nie powinien wywoływać funkcji w dowolnym miejscu, ponieważ zazwyczaj będą wymagały jednej lub więcej własnych linii pamięci podręcznej, co spowoduje zmniejszenie liczby linii pamięci podręcznej dla danych.
Funkcja powinna rozpoczynać się od adresu przyjaznego do wyrównania linii w pamięci podręcznej. Chociaż istnieją przełączniki kompilatora (gcc), należy pamiętać, że jeśli funkcje są bardzo krótkie, może być marnowanie czasu na zajęcie całej linii pamięci podręcznej. Na przykład, jeśli trzy z najczęściej używanych funkcji mieszczą się w jednej 64-bajtowej linii pamięci podręcznej, jest to mniej marnotrawstwo niż wtedy, gdy każda z nich ma swoją własną linię i powoduje, że dwie linie pamięci podręcznej są mniej dostępne do innych zastosowań. Typowa wartość wyrównania może wynosić 32 lub 16.
Poświęć więc trochę czasu na zagęszczenie kodu. Testuj różne konstrukcje, kompiluj i przeglądaj wygenerowany kod i rozmiar kodu.
Jak wspomniał @Marc Claesen, jednym ze sposobów pisania kodu przyjaznego dla pamięci podręcznej jest wykorzystanie struktury, w której przechowywane są nasze dane. Oprócz tego innym sposobem pisania przyjaznego dla pamięci podręcznej kodu jest: zmiana sposobu przechowywania danych; następnie napisz nowy kod, aby uzyskać dostęp do danych przechowywanych w tej nowej strukturze.
Ma to sens w przypadku, w jaki systemy baz danych linearyzują krotki tabeli i przechowują je. Istnieją dwa podstawowe sposoby przechowywania krotek tabeli, tj. Magazyn wierszy i magazyn kolumn. W magazynie wierszy, jak sama nazwa wskazuje, krotki są przechowywane w wierszach. Załóżmy, że tabela o nazwie, Productktóra jest przechowywana, ma 3 atrybuty, int32_t key, char name[56]a int32_t pricewięc całkowity rozmiar krotki to 64bajty.
Możemy symulować bardzo podstawowe wykonywanie zapytań magazynu wierszy w pamięci głównej, tworząc tablicę Productstruktur o rozmiarze N, gdzie N jest liczbą wierszy w tabeli. Taki układ pamięci nazywany jest również tablicą struktur. Struktura produktu może więc wyglądać następująco:
structProduct{int32_t key;char name[56];int32_t price'}/* create an array of structs */Product* table =newProduct[N];/* now load this array of structs, from a file etc. */
Podobnie możemy symulować bardzo podstawowe wykonanie zapytania do magazynu kolumn w pamięci głównej, tworząc 3 tablice o rozmiarze N, po jednej tablicy dla każdego atrybutu Producttabeli. Taki układ pamięci nazywany jest również strukturą tablic. Zatem 3 tablice dla każdego atrybutu produktu mogą wyglądać następująco:
/* create separate arrays for each attribute */int32_t* key =newint32_t[N];char* name =newchar[56*N];int32_t* price =newint32_t[N];/* now load these arrays, from a file etc. */
Teraz po załadowaniu zarówno tablicy struktur (Układ wierszy), jak i 3 oddzielnych tablic (Układ kolumn), mamy Productw pamięci tabelę wierszy i kolumnę .
Teraz przechodzimy do części przyjaznej pamięci podręcznej. Załóżmy, że obciążenie naszego stołu jest takie, że mamy zapytanie agregacyjne dotyczące atrybutu ceny. Jak na przykład
SELECT SUM(price)
FROM PRODUCT
Dla magazynu wierszy możemy przekonwertować powyższe zapytanie SQL na
int sum =0;for(int i=0; i<N; i++)
sum = sum + table[i].price;
Dla magazynu kolumn możemy przekonwertować powyższe zapytanie SQL na
int sum =0;for(int i=0; i<N; i++)
sum = sum + price[i];
Kod dla magazynu kolumn byłby szybszy niż kod dla układu wierszy w tym zapytaniu, ponieważ wymaga tylko podzbioru atrybutów, a w układzie kolumn robimy tylko to, tj. Tylko dostęp do kolumny ceny.
Załóżmy, że rozmiar linii pamięci podręcznej to 64bajty.
W przypadku układu wiersza podczas odczytywania wiersza pamięci podręcznej odczytywana jest wartość ceny tylko 1 ( cacheline_size/product_struct_size = 64/64 = 1) krotki, ponieważ nasz strukturalny rozmiar wynosi 64 bajty i wypełnia całą naszą linię pamięci podręcznej, więc w przypadku każdej krotki brakuje pamięci podręcznej w przypadku układu wiersza.
W przypadku układu kolumny podczas odczytywania wiersza pamięci podręcznej odczytywana jest wartość ceny 16 ( cacheline_size/price_int_size = 64/4 = 16) krotek, ponieważ 16 ciągłych wartości cen przechowywanych w pamięci jest wprowadzanych do pamięci podręcznej, więc w przypadku każdej szesnastej krotki pamięć podręczna nie występuje w przypadku układ kolumny.
Tak więc układ kolumn będzie szybszy w przypadku danego zapytania i szybszy w takich zapytaniach agregacyjnych w podzbiorze kolumn tabeli. Możesz wypróbować taki eksperyment na własną rękę, korzystając z danych z testu porównawczego TPC-H i porównać czasy działania dla obu układów. Artykuł w Wikipedii na temat systemów baz danych zorientowanych na kolumny również jest dobry.
Tak więc w systemach baz danych, jeśli obciążenie kwerendą jest znane, możemy przechowywać nasze dane w układach, które będą pasować do zapytań w obciążeniu i uzyskać dostęp do danych z tych układów. W przypadku powyższego przykładu utworzyliśmy układ kolumny i zmieniliśmy nasz kod na obliczanie sumy, aby stał się przyjazny dla pamięci podręcznej.
Pamiętaj, że pamięci podręczne nie tylko buforują ciągłą pamięć. Mają wiele linii (co najmniej 4), więc nieciągła i nakładająca się pamięć często może być przechowywana równie skutecznie.
We wszystkich powyższych przykładach brakuje mierzonych wzorców. Istnieje wiele mitów na temat wydajności. Jeśli tego nie zmierzysz, nie wiesz. Nie komplikuj kodu, chyba że masz mierzoną poprawę.
Odpowiedzi:
Czynności wstępne
Na współczesnych komputerach tylko struktury pamięci najniższego poziomu ( rejestry ) mogą przenosić dane w pojedynczych cyklach zegara. Rejestry są jednak bardzo drogie, a większość rdzeni komputerowych ma mniej niż kilkadziesiąt rejestrów ( łącznie od kilkuset do może tysiąca bajtów ). Na drugim końcu spektrum pamięci ( DRAM ) pamięć jest bardzo tania (tj. Dosłownie miliony razy tańsza ), ale zajmuje setki cykli po otrzymaniu danych. Aby wypełnić tę lukę między superszybkim i drogim a super wolnym i tanim, są pamięci podręczne, o nazwie L1, L2, L3 o malejącej prędkości i koszcie. Chodzi o to, że większość wykonywanego kodu często uderza w mały zestaw zmiennych, a reszta (znacznie większy zestaw zmiennych) rzadko. Jeśli procesor nie może znaleźć danych w pamięci podręcznej L1, wówczas szuka w pamięci podręcznej L2. Jeśli nie, to pamięć podręczna L3, a jeśli nie, pamięć główna. Każdy z tych „braków” jest z czasem drogi.
(Analogią jest pamięć podręczna pamięci systemowej, ponieważ pamięć systemowa jest zbyt dyskiem twardym. Dysk twardy jest super tani, ale bardzo wolny).
Buforowanie jest jedną z głównych metod zmniejszania wpływu opóźnienia . Parafrazując Herb Sutter (por. Linki poniżej): zwiększenie przepustowości jest łatwe, ale nie możemy kupić drogi wyjścia z opóźnień .
Dane są zawsze pobierane przez hierarchię pamięci (najmniejsze == najszybsze do najwolniejszych). Cache hit / Panna odnosi się zwykle do przeboju / brakuje w najwyższym poziomie w pamięci podręcznej procesora - o najwyższym poziomie to znaczy największa == najwolniej. Współczynnik trafień w pamięci podręcznej ma kluczowe znaczenie dla wydajności, ponieważ każde pominięcie pamięci podręcznej powoduje pobranie danych z pamięci RAM (lub gorzej ...), co zajmuje dużo czasu (setki cykli dla RAM, dziesiątki milionów cykli dla HDD). Dla porównania, odczyt danych z pamięci podręcznej (najwyższego poziomu) zwykle zajmuje tylko garść cykli.
We współczesnych architekturach komputerowych wąskim gardłem wydajności jest opuszczanie procesora (np. Uzyskiwanie dostępu do pamięci RAM lub wyższej). Z czasem sytuacja się pogorszy. Wzrost częstotliwości procesora nie jest obecnie istotny dla zwiększenia wydajności. Problemem jest dostęp do pamięci. W związku z tym wysiłki związane z projektowaniem sprzętu w procesorach koncentrują się obecnie na optymalizacji pamięci podręcznej, pobierania wstępnego, potoków i współbieżności. Na przykład nowoczesne procesory wydają około 85% pamięci na pamięci podręczne i do 99% na przechowywanie / przenoszenie danych!
Na ten temat można wiele powiedzieć. Oto kilka świetnych odniesień do pamięci podręcznych, hierarchii pamięci i właściwego programowania:
Główne pojęcia dotyczące kodu przyjaznego dla pamięci podręcznej
Bardzo ważnym aspektem kodu przyjaznego dla pamięci podręcznej jest zasada lokalności , której celem jest umieszczenie powiązanych danych w pamięci, aby umożliwić efektywne buforowanie. Jeśli chodzi o pamięć podręczną procesora, należy pamiętać o liniach pamięci podręcznej, aby zrozumieć, jak to działa: Jak działają linie pamięci podręcznej?
Następujące szczególne aspekty mają duże znaczenie dla optymalizacji buforowania:
Użyj odpowiedniego c ++ pojemniki
Prostym przykładem przyjaznych pamięci podręcznej i nieprzyjaznych pamięci podręcznej jest c ++w
std::vector
porównaniu zstd::list
. Elementy astd::vector
są przechowywane w ciągłej pamięci, dlatego dostęp do nich jest o wiele bardziej przyjazny dla pamięci podręcznej niż dostęp do elementów w astd::list
, które przechowują jego zawartość w dowolnym miejscu. Wynika to z lokalizacji przestrzennej.Bardzo ładną ilustracją tego jest Bjarne Stroustrup w tym klipie na youtube (dzięki @Mohammad Ali Baydoun za link!).
Nie zaniedbuj pamięci podręcznej w strukturze danych i projekcie algorytmu
W miarę możliwości staraj się dostosowywać struktury danych i kolejność obliczeń w taki sposób, aby maksymalnie wykorzystać pamięć podręczną. Powszechną techniką w tym zakresie jest blokowanie pamięci podręcznej (wersja Archive.org) , która ma ogromne znaczenie w obliczeniach o wysokiej wydajności (np. ATLAS ).
Znać i wykorzystywać ukrytą strukturę danych
Innym prostym przykładem, o którym wielu ludzi w tej dziedzinie czasami zapomina, jest kolumna główna (np. fortran,Matlab) a porządkowanie według rzędów (np. do,c ++) do przechowywania tablic dwuwymiarowych. Rozważmy na przykład następującą macierz:
W porządku rzędów głównych jest to przechowywane w pamięci jako
1 2 3 4
; w uporządkowaniu według głównych kolumn byłoby to przechowywane jako1 3 2 4
. Łatwo zauważyć, że implementacje, które nie wykorzystują tego porządku, szybko napotkają (łatwo uniknąć!) Problemy z pamięcią podręczną. Niestety, widzę rzeczy, jak to bardzo często w mojej domeny (uczenia maszynowego). @MatteoItalia pokazał ten przykład bardziej szczegółowo w swojej odpowiedzi.Podczas pobierania określonego elementu macierzy z pamięci elementy w jego pobliżu zostaną również pobrane i zapisane w linii pamięci podręcznej. Jeśli zostanie wykorzystana kolejność, spowoduje to mniejszy dostęp do pamięci (ponieważ kilka kolejnych wartości potrzebnych do kolejnych obliczeń znajduje się już w linii pamięci podręcznej).
Dla uproszczenia załóżmy, że pamięć podręczna zawiera pojedynczą linię pamięci podręcznej, która może zawierać 2 elementy macierzy i że gdy dany element jest pobierany z pamięci, następny też jest następny. Powiedzmy, że chcemy przejąć sumę nad wszystkimi elementami w powyższej przykładowej macierzy 2x2 (nazwijmy to
M
):Wykorzystanie kolejności (np. Zmiana indeksu kolumny najpierw w c ++):
Niewykorzystywanie kolejności (np. Zmiana indeksu wierszy najpierw w c ++):
W tym prostym przykładzie wykorzystanie zamówienia w przybliżeniu podwaja szybkość wykonywania (ponieważ dostęp do pamięci wymaga znacznie więcej cykli niż obliczanie sum). W praktyce różnica wydajności może być znacznie większa.
Unikaj nieprzewidywalnych gałęzi
Nowoczesne architektury zawierają potoki, a kompilatory stają się bardzo dobre w zmianie kolejności kodu, aby zminimalizować opóźnienia z powodu dostępu do pamięci. Gdy kod krytyczny zawiera (nieprzewidywalne) gałęzie, pobranie danych jest trudne lub niemożliwe. To pośrednio doprowadzi do większej liczby braków w pamięci podręcznej.
Wyjaśnia to bardzo dobrze (dzięki @ 0x90 dla łącza): Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie nieposortowanej tablicy?
Unikaj funkcji wirtualnych
W kontekście c ++,
virtual
metody stanowią kontrowersyjny problem z brakami pamięci podręcznej (istnieje ogólna zgoda, że należy ich unikać, jeśli to możliwe, pod względem wydajności). Funkcje wirtualne mogą powodować brak pamięci podręcznej podczas wyszukiwania, ale dzieje się tak tylko wtedy, gdy konkretna funkcja nie jest często wywoływana (w przeciwnym razie prawdopodobnie byłaby buforowana), więc niektórzy uważają to za problem. Aby uzyskać informacje na temat tego problemu, sprawdź: Jaki jest koszt wydajności posiadania metody wirtualnej w klasie C ++?Częste problemy
Częstym problemem we współczesnych architekturach z wieloprocesorowymi pamięciami podręcznymi jest fałszywe współdzielenie . Dzieje się tak, gdy każdy procesor próbuje użyć danych w innym regionie pamięci i próbuje zapisać je w tej samej linii pamięci podręcznej . Powoduje to, że wiersz pamięci podręcznej - który zawiera dane, których może użyć inny procesor - jest wielokrotnie zastępowany. W efekcie różne wątki zmuszają się do wzajemnego oczekiwania, powodując w tej sytuacji brak pamięci podręcznej. Zobacz także (dzięki @Matt za link): Jak i kiedy wyrównać do rozmiaru linii pamięci podręcznej?
Ekstremalnym objawem słabego buforowania w pamięci RAM (co prawdopodobnie nie jest tym, co masz na myśli w tym kontekście), jest tak zwane thrashowanie . Dzieje się tak, gdy proces w sposób ciągły generuje błędy strony (np. Uzyskuje dostęp do pamięci, której nie ma na bieżącej stronie), które wymagają dostępu do dysku.
źródło
Oprócz odpowiedzi @Marc Claesen uważam, że pouczającym klasycznym przykładem nieprzyjaznego dla pamięci podręcznej kodu jest kod, który skanuje tablicę dwuwymiarową C (np. Obraz bitmapowy) pod względem kolumny zamiast wiersza.
Elementy sąsiadujące w rzędzie również sąsiadują w pamięci, a zatem dostęp do nich w kolejności oznacza dostęp do nich w kolejności rosnącej; jest to przyjazne dla pamięci podręcznej, ponieważ pamięć podręczna ma tendencję do pobierania sąsiadujących bloków pamięci.
Zamiast tego dostęp do takich elementów pod względem kolumn jest nieprzyjazny dla pamięci podręcznej, ponieważ elementy w tej samej kolumnie są odległe od siebie w pamięci (w szczególności ich odległość jest równa wielkości wiersza), więc kiedy używasz tego wzorca dostępu, skaczą w pamięci, potencjalnie marnując wysiłek związany z pamięcią podręczną wyszukiwania elementów znajdujących się w pobliżu w pamięci.
I wszystko, czego potrzeba, aby zrujnować wydajność, to przejść
do
Efekt ten może być dość dramatyczny (kilka rzędów wielkości w prędkości) w systemach z małymi pamięciami podręcznymi i / lub pracą z dużymi macierzami (np. Ponad 10 megapikseli obrazów 24 bpp na obecnych maszynach); z tego powodu, jeśli musisz wykonać wiele skanów w pionie, często lepiej jest najpierw obrócić obraz o 90 stopni, a następnie wykonać różne analizy, ograniczając nieprzyjazny dla pamięci podręcznej kod tylko do obrotu.
źródło
Optymalizacja użycia pamięci podręcznej sprowadza się w dużej mierze do dwóch czynników.
Lokalizacja odniesienia
Pierwszym czynnikiem (do którego nawiązywali inni) jest lokalizacja odniesienia. Lokalizacja odniesienia ma jednak naprawdę dwa wymiary: przestrzeń i czas.
Wymiar przestrzenny sprowadza się również do dwóch rzeczy: po pierwsze, chcemy gęsto upakować nasze informacje, aby więcej informacji zmieściło się w tej ograniczonej pamięci. Oznacza to (na przykład), że potrzebna jest znaczna poprawa złożoności obliczeniowej, aby uzasadnić struktury danych oparte na małych węzłach połączonych wskaźnikami.
Po drugie, chcemy, aby informacje, które będą przetwarzane razem, również były zlokalizowane razem. Typowa pamięć podręczna działa w „liniach”, co oznacza, że gdy uzyskasz dostęp do niektórych informacji, inne informacje z pobliskich adresów zostaną załadowane do pamięci podręcznej wraz z dotkniętą częścią. Na przykład po dotknięciu jednego bajtu pamięć podręczna może załadować 128 lub 256 bajtów w pobliżu tego. Aby z tego skorzystać, zazwyczaj chcesz, aby dane były uporządkowane tak, aby zmaksymalizować prawdopodobieństwo, że użyjesz również innych danych, które zostały załadowane w tym samym czasie.
Na przykład bardzo trywialny przykład może to oznaczać, że wyszukiwanie liniowe może być znacznie bardziej konkurencyjne w przypadku wyszukiwania binarnego, niż można się spodziewać. Po załadowaniu jednego elementu z wiersza pamięci podręcznej korzystanie z reszty danych w tym wierszu pamięci podręcznej jest prawie bezpłatne. Wyszukiwanie binarne staje się zauważalnie szybsze tylko wtedy, gdy dane są na tyle duże, że wyszukiwanie binarne zmniejsza liczbę linii pamięci podręcznej, do których masz dostęp.
Wymiar czasu oznacza, że wykonując niektóre operacje na niektórych danych, chcesz (w jak największym stopniu) wykonywać wszystkie operacje na tych danych jednocześnie.
Odkąd określili to jako C ++, będę wskazywać na klasyczny przykład konstrukcji stosunkowo cache-nieprzyjazny:
std::valarray
.valarray
Przeciążenia najbardziej arytmetyczne operatory, więc może (na przykład) powiedzieća = b + c + d;
(gdziea
,b
,c
id
są valarrays) zrobić element mądry dodanie tych tablic.Problem polega na tym, że przechodzi przez jedną parę danych wejściowych, umieszcza wyniki tymczasowo, przechodzi przez inną parę danych wejściowych i tak dalej. Przy dużej ilości danych wynik jednego obliczenia może zniknąć z pamięci podręcznej, zanim zostanie wykorzystany w następnym obliczeniu, więc kończymy odczytywanie (i zapisywanie) danych wielokrotnie, zanim uzyskamy końcowy wynik. Jeśli każdy element końcowy rezultat będzie coś takiego
(a[n] + b[n]) * (c[n] + d[n]);
, to na ogół wolą czytać każdya[n]
,b[n]
,c[n]
id[n]
raz, wykonać obliczenia, pisać rezultacie przyrostn
i powtórzyć „til skończymy. 2)Udostępnianie linii
Drugim ważnym czynnikiem jest unikanie dzielenia linii. Aby to zrozumieć, prawdopodobnie musimy wykonać kopię zapasową i przyjrzeć się trochę, w jaki sposób organizowane są pamięci podręczne. Najprostsza forma pamięci podręcznej jest mapowana bezpośrednio. Oznacza to, że jeden adres w pamięci głównej można zapisać tylko w jednym konkretnym miejscu w pamięci podręcznej. Jeśli używamy dwóch elementów danych, które są mapowane do tego samego miejsca w pamięci podręcznej, działa to źle - za każdym razem, gdy używamy jednego elementu danych, drugi musi zostać usunięty z pamięci podręcznej, aby zrobić miejsce dla drugiego. Reszta pamięci podręcznej może być pusta, ale te elementy nie będą używać innych części pamięci podręcznej.
Aby temu zapobiec, większość pamięci podręcznych to tak zwane „ustawianie asocjacyjne”. Na przykład w 4-kierunkowej pamięci podręcznej skojarzonej z zestawem dowolny element z pamięci głównej można przechowywać w dowolnym z 4 różnych miejsc w pamięci podręcznej. Kiedy więc pamięć podręczna ma załadować element, szuka ostatnio używanego 3 elementu spośród tych czterech, opróżnia go do pamięci głównej i ładuje nowy element na swoim miejscu.
Problem jest prawdopodobnie dość oczywisty: w przypadku pamięci podręcznej z bezpośrednim odwzorowaniem dwa operandy, które akurat mapują do tej samej lokalizacji pamięci podręcznej, mogą prowadzić do złego zachowania. Pamięć podręczna skojarzona z zestawem N-way zwiększa liczbę z 2 do N + 1. Zorganizowanie pamięci podręcznej na więcej „sposobów” wymaga dodatkowych obwodów i ogólnie działa wolniej, więc (na przykład) 8192-drogowe skojarzenie pamięci podręcznej rzadko jest dobrym rozwiązaniem.
Ostatecznie ten czynnik jest trudniejszy do kontrolowania w przenośnym kodzie. Twoja kontrola nad tym, gdzie znajdują się Twoje dane, jest zwykle dość ograniczona. Co gorsza, dokładne odwzorowanie adresu na pamięć podręczną różni się w zależności od podobnych procesorów. W niektórych przypadkach warto jednak wykonać takie czynności, jak przydzielenie dużego bufora, a następnie użycie tylko części tego, co zostało przydzielone, aby zabezpieczyć dane przed współużytkowaniem tych samych linii pamięci podręcznej (nawet jeśli prawdopodobnie konieczne będzie wykrycie dokładnego procesora i działaj odpowiednio, aby to zrobić).
Jest jeszcze jeden powiązany element zwany „fałszywym udostępnianiem”. Powstaje to w systemie wieloprocesorowym lub wielordzeniowym, w którym dwa (lub więcej) procesorów / rdzeni ma oddzielne dane, ale mieszczą się w tej samej linii pamięci podręcznej. Zmusza to dwa procesory / rdzenie do koordynowania dostępu do danych, nawet jeśli każdy ma swój własny, osobny element danych. Zwłaszcza, jeśli obydwoje modyfikują dane naprzemiennie, może to prowadzić do ogromnego spowolnienia, ponieważ dane muszą być stale przesyłane między procesorami. Nie można tego łatwo wyleczyć, organizując pamięć podręczną na więcej „sposobów” lub coś w tym rodzaju. Podstawowym sposobem zapobiegania temu jest zapewnienie, że dwa wątki rzadko (najlepiej nigdy) modyfikują dane, które mogą znajdować się w tej samej linii pamięci podręcznej (z tymi samymi zastrzeżeniami dotyczącymi trudności w kontrolowaniu adresów, pod którymi dane są przydzielane).
Ci, którzy dobrze znają C ++, mogą się zastanawiać, czy można to zoptymalizować za pomocą szablonów wyrażeń. Jestem prawie pewien, że odpowiedź brzmi: tak, można by to zrobić i gdyby tak było, prawdopodobnie byłaby to całkiem spora wygrana. Nie wiem jednak, że ktoś to zrobił, a biorąc pod uwagę, jak mało
valarray
się przyzwyczaiłem, byłbym przynajmniej trochę zaskoczony, gdy ktoś to zrobił.W przypadku, gdy ktoś zastanawia się, w jaki sposób
valarray
(zaprojektowany specjalnie pod kątem wydajności) może być tak bardzo źle, sprowadza się to do jednej rzeczy: został naprawdę zaprojektowany dla maszyn takich jak starsze Crays, które korzystały z szybkiej pamięci głównej i bez pamięci podręcznej. Dla nich był to naprawdę idealny projekt.Tak, upraszczam: większość pamięci podręcznych tak naprawdę nie mierzy dokładnie ostatnio używanego przedmiotu, ale używa heurystyki, która ma być do tego zbliżona, bez konieczności zachowania pełnego znacznika czasu dla każdego dostępu.
źródło
valarray
przykład.Witamy w świecie projektowania zorientowanego na dane. Podstawową mantrą jest Sortowanie, Eliminowanie Oddziałów, Partia, Eliminowanie
virtual
połączeń - wszystkie kroki w kierunku lepszej lokalizacji.Ponieważ otagowałeś pytanie C ++, oto obowiązkowa typowa bzdura C ++ . Pułapki programowania obiektowego Tony'ego Albrechta to także świetne wprowadzenie do tematu.
źródło
Po prostu stos: klasyczny przykład kodu nieprzyjaznego dla pamięci podręcznej w porównaniu z kodem przyjaznym dla pamięci podręcznej to „blokowanie pamięci podręcznej” macierzy.
Naiwna macierz mnożenia wygląda następująco:
Jeśli
N
jest duży, np. JeśliN * sizeof(elemType)
jest większy niż rozmiar pamięci podręcznej, wówczas każdy pojedynczy dostęp dosrc2[k][j]
będzie brakiem pamięci podręcznej.Istnieje wiele różnych sposobów optymalizacji tego pod kątem pamięci podręcznej. Oto bardzo prosty przykład: zamiast czytać jeden element na linię pamięci podręcznej w wewnętrznej pętli, użyj wszystkich elementów:
Jeśli rozmiar linii bufora wynosi 64 bajty, a działamy na liczbach zmiennoprzecinkowych 32-bitowych (4 bajty), wówczas w linii bufora jest 16 elementów. A liczba braków pamięci podręcznej dzięki tej prostej transformacji jest zmniejszona około 16-krotnie.
Bardziej zaawansowane transformacje działają na kafelkach 2D, optymalizują pod kątem wielu pamięci podręcznych (L1, L2, TLB) i tak dalej.
Niektóre wyniki „blokowania pamięci podręcznej” w Google:
http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf
http://software.intel.com/en-us/articles/cache-blocking-techniques
Ładna animacja wideo zoptymalizowanego algorytmu blokowania pamięci podręcznej.
http://www.youtube.com/watch?v=IFWgwGMMrh0
Układanie pętli jest bardzo ściśle powiązane:
http://en.wikipedia.org/wiki/Loop_tiling
źródło
k==;
Mam nadzieję, że to literówka?Procesory współdziałają dziś z wieloma poziomami kaskadowych obszarów pamięci. Więc procesor będzie miał sporo pamięci, która znajduje się w samym układzie procesora. Ma bardzo szybki dostęp do tej pamięci. Istnieją różne poziomy pamięci podręcznej, z których każdy ma wolniejszy dostęp (i większy) niż następny, dopóki nie dojdziesz do pamięci systemowej, która nie jest na CPU i jest stosunkowo wolniejsza.
Logicznie, do zestawu instrukcji CPU odwołujesz się tylko do adresów pamięci w gigantycznej wirtualnej przestrzeni adresowej. Gdy uzyskasz dostęp do pojedynczego adresu pamięci, procesor go pobierze. w dawnych czasach pobierał tylko ten jeden adres. Ale dzisiaj procesor pobierze sporo pamięci wokół żądanego bitu i skopiuje go do pamięci podręcznej. Zakłada się, że jeśli poprosiłeś o określony adres, istnieje duże prawdopodobieństwo, że wkrótce poprosisz o adres w pobliżu. Na przykład, jeśli kopiujesz bufor, możesz czytać i pisać z kolejnych adresów - jeden bezpośrednio po drugim.
Więc dzisiaj, kiedy pobierasz adres, sprawdza on pierwszy poziom pamięci podręcznej, aby sprawdzić, czy już odczytał ten adres do pamięci podręcznej, jeśli go nie znajdzie, to jest to brak pamięci podręcznej i musi przejść do następnego poziomu pamięć podręczną, aby ją znaleźć, aż w końcu musi wyjść do pamięci głównej.
Kod przyjazny dla pamięci podręcznej stara się utrzymywać dostęp do pamięci blisko siebie, aby zminimalizować błędy pamięci podręcznej.
Przykładem może być wyobraźnia, że chcesz skopiować gigantyczny 2-wymiarowy stół. Jest on uporządkowany z wierszem zasięgu w pamięci, a jeden wiersz następuje po drugim zaraz po.
Jeśli skopiowałeś elementy pojedynczo od lewej do prawej - byłoby to przyjazne dla pamięci podręcznej. Jeśli zdecydujesz się skopiować tabelę po jednej kolumnie na raz, skopiujesz dokładnie taką samą ilość pamięci - ale byłoby to nieprzyjazne dla pamięci podręcznej.
źródło
Należy wyjaśnić, że nie tylko dane powinny być przyjazne dla pamięci podręcznej, ale są równie ważne dla kodu. Jest to dodatek do przewidywania gałęzi, zmiany kolejności instrukcji, unikania faktycznych podziałów i innych technik.
Zazwyczaj im gęstszy kod, tym mniej linii pamięci podręcznej będzie wymaganych do jego przechowywania. Powoduje to, że dla danych dostępnych jest więcej wierszy pamięci podręcznej.
Kod nie powinien wywoływać funkcji w dowolnym miejscu, ponieważ zazwyczaj będą wymagały jednej lub więcej własnych linii pamięci podręcznej, co spowoduje zmniejszenie liczby linii pamięci podręcznej dla danych.
Funkcja powinna rozpoczynać się od adresu przyjaznego do wyrównania linii w pamięci podręcznej. Chociaż istnieją przełączniki kompilatora (gcc), należy pamiętać, że jeśli funkcje są bardzo krótkie, może być marnowanie czasu na zajęcie całej linii pamięci podręcznej. Na przykład, jeśli trzy z najczęściej używanych funkcji mieszczą się w jednej 64-bajtowej linii pamięci podręcznej, jest to mniej marnotrawstwo niż wtedy, gdy każda z nich ma swoją własną linię i powoduje, że dwie linie pamięci podręcznej są mniej dostępne do innych zastosowań. Typowa wartość wyrównania może wynosić 32 lub 16.
Poświęć więc trochę czasu na zagęszczenie kodu. Testuj różne konstrukcje, kompiluj i przeglądaj wygenerowany kod i rozmiar kodu.
źródło
Jak wspomniał @Marc Claesen, jednym ze sposobów pisania kodu przyjaznego dla pamięci podręcznej jest wykorzystanie struktury, w której przechowywane są nasze dane. Oprócz tego innym sposobem pisania przyjaznego dla pamięci podręcznej kodu jest: zmiana sposobu przechowywania danych; następnie napisz nowy kod, aby uzyskać dostęp do danych przechowywanych w tej nowej strukturze.
Ma to sens w przypadku, w jaki systemy baz danych linearyzują krotki tabeli i przechowują je. Istnieją dwa podstawowe sposoby przechowywania krotek tabeli, tj. Magazyn wierszy i magazyn kolumn. W magazynie wierszy, jak sama nazwa wskazuje, krotki są przechowywane w wierszach. Załóżmy, że tabela o nazwie,
Product
która jest przechowywana, ma 3 atrybuty,int32_t key, char name[56]
aint32_t price
więc całkowity rozmiar krotki to64
bajty.Możemy symulować bardzo podstawowe wykonywanie zapytań magazynu wierszy w pamięci głównej, tworząc tablicę
Product
struktur o rozmiarze N, gdzie N jest liczbą wierszy w tabeli. Taki układ pamięci nazywany jest również tablicą struktur. Struktura produktu może więc wyglądać następująco:Podobnie możemy symulować bardzo podstawowe wykonanie zapytania do magazynu kolumn w pamięci głównej, tworząc 3 tablice o rozmiarze N, po jednej tablicy dla każdego atrybutu
Product
tabeli. Taki układ pamięci nazywany jest również strukturą tablic. Zatem 3 tablice dla każdego atrybutu produktu mogą wyglądać następująco:Teraz po załadowaniu zarówno tablicy struktur (Układ wierszy), jak i 3 oddzielnych tablic (Układ kolumn), mamy
Product
w pamięci tabelę wierszy i kolumnę .Teraz przechodzimy do części przyjaznej pamięci podręcznej. Załóżmy, że obciążenie naszego stołu jest takie, że mamy zapytanie agregacyjne dotyczące atrybutu ceny. Jak na przykład
Dla magazynu wierszy możemy przekonwertować powyższe zapytanie SQL na
Dla magazynu kolumn możemy przekonwertować powyższe zapytanie SQL na
Kod dla magazynu kolumn byłby szybszy niż kod dla układu wierszy w tym zapytaniu, ponieważ wymaga tylko podzbioru atrybutów, a w układzie kolumn robimy tylko to, tj. Tylko dostęp do kolumny ceny.
Załóżmy, że rozmiar linii pamięci podręcznej to
64
bajty.W przypadku układu wiersza podczas odczytywania wiersza pamięci podręcznej odczytywana jest wartość ceny tylko 1 (
cacheline_size/product_struct_size = 64/64 = 1
) krotki, ponieważ nasz strukturalny rozmiar wynosi 64 bajty i wypełnia całą naszą linię pamięci podręcznej, więc w przypadku każdej krotki brakuje pamięci podręcznej w przypadku układu wiersza.W przypadku układu kolumny podczas odczytywania wiersza pamięci podręcznej odczytywana jest wartość ceny 16 (
cacheline_size/price_int_size = 64/4 = 16
) krotek, ponieważ 16 ciągłych wartości cen przechowywanych w pamięci jest wprowadzanych do pamięci podręcznej, więc w przypadku każdej szesnastej krotki pamięć podręczna nie występuje w przypadku układ kolumny.Tak więc układ kolumn będzie szybszy w przypadku danego zapytania i szybszy w takich zapytaniach agregacyjnych w podzbiorze kolumn tabeli. Możesz wypróbować taki eksperyment na własną rękę, korzystając z danych z testu porównawczego TPC-H i porównać czasy działania dla obu układów. Artykuł w Wikipedii na temat systemów baz danych zorientowanych na kolumny również jest dobry.
Tak więc w systemach baz danych, jeśli obciążenie kwerendą jest znane, możemy przechowywać nasze dane w układach, które będą pasować do zapytań w obciążeniu i uzyskać dostęp do danych z tych układów. W przypadku powyższego przykładu utworzyliśmy układ kolumny i zmieniliśmy nasz kod na obliczanie sumy, aby stał się przyjazny dla pamięci podręcznej.
źródło
Pamiętaj, że pamięci podręczne nie tylko buforują ciągłą pamięć. Mają wiele linii (co najmniej 4), więc nieciągła i nakładająca się pamięć często może być przechowywana równie skutecznie.
We wszystkich powyższych przykładach brakuje mierzonych wzorców. Istnieje wiele mitów na temat wydajności. Jeśli tego nie zmierzysz, nie wiesz. Nie komplikuj kodu, chyba że masz mierzoną poprawę.
źródło