Skrytki: LRU lub losowe

Dawno, dawno temu mój profesor architektury komputerowej wspomniał, że stosowanie zasad losowego wykluczania pamięci podręcznych naprawdę nie jest takie złe. To losowe wykluczenie nie jest złe, ale może być zaskakujące — jeśli pamięć podręczna się zapełnia i musisz się czegoś pozbyć, wybranie ostatnio używanego (LRU) jest oczywistym wyborem, ponieważ istnieje większe prawdopodobieństwo, że użyjesz czegoś, jeśli korzystałeś z tego niedawno. Jeśli masz ciasną pętlę, LRU będzie idealne, o ile pętla zmieści się w pamięci podręcznej, ale za każdym razem będzie powodować chybienie, jeśli pętla nie będzie pasować. Polityka losowych eksmisji ulega stopniowej degradacji, gdy pętla staje się zbyt duża.

W praktyce przy rzeczywistych obciążeniach algorytm losowy radzi sobie gorzej niż inne algorytmy. Ale co, jeśli wybierzemy dwie losowe wybory (2-losowe) i po prostu użyjemy LRU pomiędzy tymi dwoma wyborami?

Oto względne współczynniki chybień, jakie otrzymujemy dla procesora SPEC z pamięcią podręczną typu Sandy Bridge (odpowiednio 8-kierunkowa pamięć podręczna, 64 tys., 256 tys. i 2 MB pamięci podręcznej L1, L2 i L3). Są to współczynniki (wskaźnik chybień algorytmu : współczynnik chybień losowych); niżej jest lepiej. Każda pamięć podręczna używa tych samych zasad na wszystkich poziomach pamięci podręcznej.

Polityka	L1 (64 tys.)	L2 (256 tys.)	L3(2MB)
2-losowe	0,91	0,93	0,95
FIFO	0,96	0,97	1.02
LRU	0,90	0,90	0,97
losowy	1,00	1,00	1,00

Losowe i FIFO są zdecydowanie gorsze niż LRU lub 2-losowe. LRU i 2-losowe są dość blisko, przy czym LRU ogranicza 2-losowe dla mniejszych pamięci podręcznych i 2-losowe ograniczanie LRU dla większych pamięci podręcznych.

Aby sprawdzić, czy w jakimkolwiek pojedynczym benchmarku dzieje się coś dziwnego, możemy przyjrzeć się surowym wynikom każdego podtestu. Wskaźniki chybień L1, L2 i L3 są wykreślone w tej samej kolumnie dla każdego benchmarku, poniżej:

Jak można się spodziewać, LRU radzi sobie gorzej niż 2-losowy, gdy współczynnik chybień jest wysoki, i lepiej, gdy współczynnik chybień jest niski.

W tym momencie nie jest jasne, czy 2-random pokonuje LRU pod względem współczynnika braków w pamięci podręcznej L3, ponieważ radzi sobie lepiej, gdy pamięci podręczne są duże, czy dlatego, że działa lepiej, ponieważ jest to trzeci poziom w hierarchicznej pamięci podręcznej. Ponieważ linia pamięci podręcznej, która jest aktywnie używana w L1 lub L2, nie jest dotknięta w L3, może nastąpić eksmisja z L3 (co wymusza eksmisję zarówno L1, jak i L2), ponieważ w przypadku L3 linia ta nie była ostatnio używana. To sprawia, że ​​mniej oczywiste jest, że LRU jest dobrą polityką eksmisji dla pamięci podręcznej L3.

Aby oddzielić efekty, przyjrzyjmy się względnym współczynnikom chybień dla niehierarchicznych (jednopoziomowych) i hierarchicznych pamięci podręcznych o różnych rozmiarach. W przypadku hierarchicznej pamięci podręcznej rozmiary L1 i L2 są takie jak powyżej, 64 KB i 256 KB, a zmienia się tylko rozmiar pamięci podręcznej L3. Poniżej przedstawiamy średnie geometryczne współczynników skuteczności każdej polisy (we wszystkich testach cząstkowych SPEC w porównaniu z losową eksmisją). Możliwą wadą tego wskaźnika jest to, że jeśli mamy bardzo niskie współczynniki błędnych wyników, mogą one dominować w średniej, ponieważ niewielkie wahania będą miały duży wpływ na współczynnik, ale możemy sprawdzić rozkład wyników, aby sprawdzić, czy tak jest.

W przypadku hierarchicznym brakuje rozmiarów poniżej 512 kB ze względu na 256 kB L2 — używamy tutaj zintegrowanej pamięci podręcznej L3, więc nie ma sensu mieć L3 mniejszego niż L2. Rozmiary powyżej 16M są pomijane, ponieważ wskaźniki braków pamięci podręcznej zbiegają się, gdy pamięć podręczna staje się zbyt duża, co jest nieciekawe.

Patrząc na przypadek pojedynczej pamięci podręcznej, wydaje się, że LRU działa nieco lepiej niż 2-losowe w przypadku mniejszych pamięci podręcznych (niższy współczynnik chybień jest lepszy), 2-losowe zmniejsza LRU w miarę powiększania się pamięci podręcznej. Historia jest podobna w przypadku hierarchicznym, z tą różnicą, że tak naprawdę nie patrzymy na mniejsze rozmiary pamięci podręcznej, w których LRU jest lepszy.

Porównując oba przypadki, wyniki są różne, ale na tyle podobne, że wygląda na to, że nasze oryginalne wyniki nie były jedynie artefaktem patrzenia na ostatni poziom hierarchicznej pamięci podręcznej.

Poniżej przyjrzymy się całemu rozkładowi, aby zobaczyć, czy średnia współczynników nie jest wypaczona przez drobne wyniki.

Wygląda na to, że dla określonego rozmiaru pamięci podręcznej (jedna kolumna wykresu) algorytmy losowe radzą sobie lepiej, gdy współczynnik chybień jest stosunkowo wysoki, i gorzej, gdy współczynnik chybień jest stosunkowo niski, więc w każdym razie są one w niekorzystnej sytuacji, gdy patrzymy tylko na średnią geometryczną — gdybyśmy wzięli średnią arytmetyczną, wynik byłby zdominowany przez większe wyniki, gdzie 2 losowe wybory i zwykła stara losowość radzą sobie stosunkowo dobrze.

Z tego, co widzieliśmy w przypadku średnich współczynników, tryb 2-losowy wygląda dobrze w przypadku dużych pamięci podręcznych, a z tego, co widzieliśmy w przypadku rozkładu wyników, dzieje się tak pomimo tego, że tryb 2-losowy jest karany przez metrykę średniego współczynnika, co sprawia, że ​​wydaje się całkiem dobry w przypadku dużych pamięci podręcznych.

Jednak powszechne jest wdrażanie zasad pseudo-LRU, ponieważ LRU może być zbyt drogie, aby było wykonalne. Ponieważ tryb 2-losowy wymaga posiadania co najmniej takiej samej ilości informacji jak LRU, przyjrzyjmy się, co się dzieje, używamy trybu pseudolosowego (około 80% dokładności) i pseudolosowego 3 (turniej dwupoziomowy, którego każdy poziom jest dokładny w około 80%).

Ponieważ losowość i FIFO wyraźnie nie są dobrymi politykami zastępczymi, pominę je na poniższych wykresach. Ponadto, ponieważ wyniki były podobne w przypadku pojedynczej i wielopoziomowej pamięci podręcznej, możemy po prostu przyjrzeć się wynikom w bardziej realistycznym przypadku wielopoziomowej pamięci podręcznej.

Ponieważ tryb pseudo2-losowy działa jak losowy w 20% przypadków, a tryb 2-losowy w 80% przypadków, możemy spodziewać się, że będzie on mieścił się gdzieś pomiędzy trybem 2-losowym a losowym, co dokładnie się dzieje. Prostą poprawką mającą na celu ulepszenie trybu pseudolosowego jest wypróbowanie trybu pseudolosowego 3 (eksmitowanie ostatnio używanego z 3 losowych wyborów). Chociaż to wciąż nie jest tak dobre, jak prawdziwe 2-losowe, jest całkiem blisko i wciąż jest lepsze niż LRU (i pseudo LRU) dla pamięci podręcznych większych niż 1M.

Jedyną dużą zmienną, której nie zbadaliśmy, jest skojarzenie zbioru. Aby zobaczyć, jak LRU wypada na tle 2-losowego w różnych rozmiarach pamięci podręcznej, spójrzmy na współczynnik LRU:2-losowy brak (wyższy/czerwony oznacza, że ​​LRU jest lepszy, niższy/zielony oznacza 2-losowy jest lepszy).

Średnio zwiększenie asocjatywności zwiększa różnicę między obiema politykami. Tak jak poprzednio, LRU jest lepsze dla małych pamięci podręcznych, a 2-losowe jest lepsze dla dużych pamięci podręcznych. Powiązania 1 i 2 nie są pokazane, ponieważ powinny być identyczne dla obu algorytmów.

Wciąż mamy do czynienia z kombinatoryczną eksplozją możliwości, których jeszcze nie wypróbowaliśmy. Jedną rzeczą do zrobienia jest wypróbowanie różnych zasad eksmisji na różnych poziomach pamięci podręcznej (LRU dla L1 i L2 z 2-losowymi wartościami dla L3 wydaje się obiecujące). Kolejną rzeczą do zrobienia jest wypróbowanie tej opcji dla różnych typów pamięci podręcznych. Tak się złożyło, że wybrałem pamięci podręczne procesora, ponieważ łatwo jest znaleźć symulatory i ślady testów porównawczych, ale w dzisiejszym świecie „umieszczania na tym pamięci podręcznej” istnieje wiele innych miejsc, w których można zastosować metodę 2-losową.

Na podstawie tych danych podejrzewam, że każdy specjalista ds. komparacji 2-random nie nadąża za politykami adaptacyjnymi, takimi jak DIP (chociaż mógłby — jest to właściwe podejście, ale scharakteryzowano je przy innym obciążeniu pracą przy użyciu innego symulatora, więc nie jest to w 100% jasne). Można jednak wdrożyć politykę pseudolosową, która zużywa ledwo więcej zasobów niż polityka pseudo-LRU, co czyni ją bardzo tanią w porównaniu z DIP. Widzimy również, że pseudolosowość 3 jest znacznie lepsza niż pseudolosowość 2, co wskazuje, że k-losowość jest prawdopodobnie ulepszeniem w stosunku do losowości 2 dla k. Niektóre zasady k-losowe mogą być ulepszeniem w stosunku do DIP.

Widzieliśmy więc, że to działa, ale dlaczego ktoś miałby w ogóle o tym pomyśleć? Potęga dwóch losowych wyborów: przegląd technik i wyników przeprowadzony przez Mitzenmachera, Richę i Sitaramana ma świetne wyjaśnienie. Intuicja matematyczna jest taka, że ​​jeśli (losowo) wrzucimy n piłek do n pojemników, maksymalna liczba piłek w dowolnym pojemniku będzie wynosić O(log n / log log n) z dużym prawdopodobieństwem, co jest w dużej mierze sprawiedliwe O(log n). Ale jeśli (zamiast wybierać losowo) wybierzemy najmniej obciążony z k losowych pojemników, maksimum będzie wynosić O(log log n / log k) z dużym prawdopodobieństwem, tj. nawet przy dwóch losowych wyborach, to w zasadzie O(log log n) a każdy dodatkowy wybór zmniejsza obciążenie jedynie o stały współczynnik.

Okazuje się, że ma to wiele zastosowań; rzeczy takie jak równoważenie obciążenia i dystrybucja skrótu są naturalnym dopasowaniem do modelu kul i pojemników. Istnieje również wiele zastosowań, które nie są w oczywisty sposób analogiczne do modelu kul i pojemników, takich jak wyznaczanie tras obwodów i wykresy Erdősa – Rényi.

Podziękowania dla Jana Eldera i Marka Hilla za bezpłatne udostępnienie dinero IV, Aleksandarowi Milenkovicowi za udostępnienie śladów procesora SPEC, Carlowi Vogelowi, Jamesowi Porterowi, Peterowi Fraenkelowi, Katerinie Barone-Adesi, Jesse Luehrsowi, Lei Albaugh i Kevinowi Lynaghowi za rady dotyczące fabuł i pakietów plotek, Mindy Preston za znalezienie literówki w podziękowaniach, Lindsey Kuper za wskazanie niektórych terminologii, Tomowi Wenischowi za sugestię, abym sprawdził CMP$im do przyszłej pracy, oraz Leah Hanson za obszerne komentarze do całego wpisu.