Mapowanie Bezpośrednie Pamięci Cache
Zachęcam do zapoznania się z efektem mojej próby klarownego przedstawienia pojęcia mapowania bezpośredniego (direct mapping). Dokument ten jedynie omawia bardziej skomplikowane elementy zagadnienia przedstawione na wykładzie 9.2 i nie może być traktowany jako zamiennik zwalniający z jego przeczytania. (Przed użyciem skonsultuj się z treścią ulotki bądź z lekarzem lub farmaceutą.) Każdy akapit będzie odpowiedzią na postawione w jego tytule pytanie, gdyż zagadnienie pokrojone na kawałeczki wydaje mi się lżej strawne. Wam pozostawiam już tylko cierpliwe ich przeżucie. ☻
Po co jest funkcja mapujÄ…ca?
Istnienie funkcji mapującej wymusza specyfika budowy i funkcjonowania komputera. Aby CPU - Central Processing Unit (centralna jednostka obliczeniowa) mogła wykonywać obliczenia potrzebuje do nich danych. Dane te odczytuje z pamięci (read), wykonuje obliczenia i efekty swojej pracy do pamięci odsyła, gdzie zostają zapisane (write) do późniejszego odczytu.
Nie tylko same obliczenia dziejÄ… siÄ™ w pewnym czasie, lecz także przesyÅ‚ danych. Naturalnie chcemy by wszystko byÅ‚o zrobione jak najszybciej. Wymaga to by dane byÅ‚y odczytywane, przesyÅ‚ane i zapisywane jak najszybciej. Co wiemy z poprzednich wykÅ‚adów - pamięć w komputerze nie jest idealna i obecnie potrafimy tworzyć jedynie albo szybkÄ… albo pojemnÄ…. CzÄ™sto jednak wykonujemy operacje jedynie na pewnej części wszystkich naszych danych i stÄ…d rozwiÄ…zanie „hybrydowe” gdzie staramy siÄ™ korzystać jednoczeÅ›nie z szybkoÅ›ci dziaÅ‚ania pamiÄ™ci cache oraz pojemnoÅ›ci zapewnianej przez pamięć glównÄ… (main memory). To tak jak z silnikiem hybrydowym w samochodzie, który sprawia, że w pewnych warunkach zadowalamy siÄ™ silnikiem elektrycznym (tak jak CPU cachem), a gdy ten nie wystarcza musimy pozwolić na użycie diesela (tak jak CPU używa pamiÄ™ci głównej). RolÄ… funkcji mapujÄ…cej jest okreÅ›lać gdzie dokÅ‚adnie przerzucać dane z pamiÄ™ci głównej do cache'u, tak byÅ›my jak najczęściej mogli polegać jedynie na nim i zyskiwać na szybkoÅ›ci (tak jak silnik elektryczny pozwala nam zmniejszyć emisje i wydatki na paliwo).
Jakie sÄ… zadania funkcji mapujÄ…cej?
Niezależnie czy mapowanie jest bezpośrednie, asocjacyjne czy asocjacyjne wielodrożne dochodzi do niego wtedy gdy chcemy skopiować coś z wolniejszej pamięci do cache'u lub gdy upewniamy się, że dane obecnie znajdujące się w cache'u są tymi, których właśnie potrzebujemy.
Jak te zadania realizowane są w przypadku mapowania bezpośredniego?
Dane w pamięci głównej oraz cache podzielone są na bloki pamięci (memory blocks) o określonych rozmiarach (np. 4 bajty każdy). Jako o wiele pojemniejsza z pamięci, pamięć główna ma ich o wiele więcej (np. 1024*1024 (około milion - tego słowa będę używać poniżej, bo pisze się je łatwiej niż 1024*1024) razy więcej - jak zawsze w informatyce mamy do czynienia z potęgami dwójki).
Indeksowanie Bloków Pamięci
Każdy z tych bloków ma swój numer. Numeracja zaczyna się jednak od 0 a nie 1, podobnie jak indeksowanie w znanym i lubianym Pythonie, gdzie np. 37 element znajdziemy pod indeksem 36.
Przyporządkowywanie bloków main memory do cache'u
W mapowaniu bezpośrednim każdy z bloków pamięci głównej może zostać przekopiowany tylko i wyłącznie do jednego miejsca w cache'u. W ten oto sposób blok pamięci z pamięci głównej o indeksie 0 może trafić tylko do bloku cache'a o indeksie 0, 1 do 1 itd. aż wyczerpie nam się ilość bloków cache'a. Powiedzmy, że nasz cache ma 214 bloków pamięci, a pamięć główna ma ich 224. Do każdego bloku cache przyporządkowaliśmy już jeden blok pamięci głównej (czyli 214 bloków pamięci głównej cieszy się już przyporządkowaniem w momencie gdy skończą się nam wolne indeksy cache'u) i zostało nam ich około 999999 razy tyle do przyporządkowania. Zapętlamy więc proces i element 214+1 pamięci głównej zostaje przyporządkowany do 0, 214+2 do 1, 214+3 do 2 itd. Proces ten zapętli się nam milion razy i będziemy mieć milion bloków pamięci głównej przyporządkowanych do każdego jednego bloku pamięci cache dlatego, że pamięć główna jest milion razy większa niż cache.
Do czego operacja MODULO?
Gdyby ktoÅ› chciaÅ‚ siÄ™ dowiedzieć do czego przyporzÄ…dkowany jest jakikolwiek z 224 bloków pamiÄ™ci głównej powinien skorzystać z operacji MODULO (dzielenia przez resztÄ™). Wynika to z faktu, iż dzielÄ…c za każdym razem dowolny blok przez milion otrzymamy jego resztÄ™ odpowiadajÄ…cÄ… przyporzÄ…dkowaniu. Np. do bloku cache o indeksie 3 bÄ™dzie przyporzÄ…dkowany bloki pamiÄ™ci głównej o indeksach 3, 3+214, 3+2*214, 3+3*214, 3+4*214 (i tak milion razy…)
Czemu wydzielamy młodsze bity z pamięci głównej gdy chcemy wiedzieć gdzie kopia jej bloku może znajdywać się w cache'u?
Dlatego, iż od cyfr liczby przy jej końcu zależy reszta dzielenia. Niezależnie czy mamy 30000003 czy 40000003 itd. reszta z dzielenia przez milion będzie równa 3. Więc od młodszych bitów (a nie cyfr, gdyż komputer działa w systemie binarnym a nie dziesiętnym) - tych na końcu liczby będzie zależeć gdzie można przekopiować dany blok pamięci głównej do cache'a.
O co chodzi ze strukturą adresu? Jak czytać adresy?
Adres pozwala nam na weryfikacje, czy mamy w cache'u dane, których właśnie potrzebujemy (jeśli tak jest to wtedy cache hit, jeśli nie jest to cache miss). Każdy adres składa się z tagu, slotu i słowa.
Tag |
Linia (Slot) |
SÅ‚owo |
Czy dany adres znajduje się w cache'u sprawdzamy następująco:
Porównujemy Tag szukanej informacji z tagiem znajdującym się w adresie. Jeśli nie zgadza się, oznacza to, że pamięć cache zajmuje nam informacja, która nas interesuje (np. szukamy 3000003 a w cache'u znajduje się w danym momencie 4000003 bo zapisuje się je w tym samym miejscu).
Działanie Tagu: Tag pozwala nam odróżnić indeks 3000003 od 4000003. Liczby te są przyporządkowane do tej samej linii cache'u, więc ich slot będzie taki sam, bo zależy od najmłodszych bitów. Tag natomiast zależy od najstarszych bitów, gdyż wynika z wartości dzielenia obu tych liczb przez milion, a nie reszty z tego dzielenia.
Jeśli Tag nie zgadza się - niestety musimy szukać danych w pamięci głównej i załadować je do cache'u. Jeśli zgadza się - patrzymy w której linii w danym bloku znajduje się potrzebna nam informacja - mówi nam to Linia (Slot) cache'u zależny od młodszych bitów - Linię (slot) cache'u utożsamiać możemy z indeksem bloku opisywanym w poprzednich pytaniach.
Na sam koniec dzięki słowu na samym końcu adresu (uzależnionemu od najmłodszych bitów) dowiadujemy się, które dane z linii chce przyjąć CPU.
Czym jest i po co istnieje Victim Cache?
Przeważnie wykonujemy operacje na danych, znajdujÄ…cych siÄ™ w głównej pamiÄ™ci blisko siebie, np. o indeksach 5000010, 5000011, 5000012 itd. Można wtedy je wszystkie zaÅ‚adować do cache'u i korzystać z jego prÄ™dkoÅ›ci gdyż powyższe dane przyporzÄ…dkowane sÄ… w cache'u do indeksów 10, 11, 12. SÄ… jednak pewne przypadki gdy bÄ™dziemy naprzemiennie korzystać z danych z indeksami z pamiÄ™ci głównej takimi jak np. 5000012 oraz 6000012. Oba przyporzÄ…dkowane sÄ… w cache'u do indeksu 12 wiÄ™c zawsze bÄ™dziemy mieli cache miss i zmusi to nas do Å‚adowania tych wartoÅ›ci z powolnej pamiÄ™ci głównej za każdym razem. Aby tego uniknąć miedzy pamiÄ™ciÄ… cache a main memory umieszczamy victim cache - dodatkowÄ… pamięć o prÄ™dkoÅ›ci cache'u lecz jeszcze mniejszÄ… gdyż używa siÄ™ jej jedynie w przypadku „dublowania siÄ™” indeksów. Unikamy w ten sposób koniecznoÅ›ci użycia pamiÄ™ci głównej i nie tracimy na prÄ™dkoÅ›ci przesyÅ‚u danych.
pod kierownictwem Artura Opalińskiego
napisał Błażej Błażewicz