Zasada działania pamięci cache (pamięć podręczna)

Czas: 3 godziny lekcyjne.
Cele dydaktyczne: Zapoznanie uczniów z zasadą działania pamięci cache.
Cele kształcące: Uczniowie po lekcji powinni umieć:
- Wyjaśnić pojęcie pamięć komputera;
- Omówić zasadę działania pamięci cache;
- Wyjaśnić skrót MESI
- Omówić Wirte Trougch (zapis jednoczesny) oraz Wirte Back (zapis opóźniony);
Metoda: Wykład, pogadanka, pokaz, ćwiczenia.
Środki dydaktyczne: Tablica, kreda, kości pamięci.

Przebieg lekcji:

1. Sprawy organizacyjne.
- sprawdzenie listy obecności;
- zapisanie tematu na tablicy;
- podanie nowego materiału;
- podsumowanie.

2. Podanie tematu i jego uzasadnienie.
Uczniowie poznają budowę i organizację pamięci cache, sposoby zapisywania danych: write trougch, write back.
3. Rozwinięcie tematu.
Budowa i organizacja pamięci cache (podręcznej)
Ze względu na bardzo dużą szybkość działania współczesnych procesorów, w komputerach PC stosowana jest szybka pamięć podręczna (Cache Memory), służą do często używanych danych, stanowiąca bufor pomiędzy wolną dynamiczną pamięcią operacyjną, a szybkim procesorem. Wszystkie obecnie produkowane procesory wyposażone są w wewnętrzną pamięć Cache
o pojemności kilkunastu, kilkudziesięciu kilobajtów. Pamięć ta oznaczana jest symbolem L1.Ponadto na płytach głównych umieszcza się tzw. pamięć zewnętrzną Cache (zwaną też L2). Do tego celu wykorzystuje się bardzo szybkie pamięci statyczne RAM (ang. Static RAM, SRAM) o niewielkiej pojemności (256K - 1M.) i o krótkim czasie dostępu (rzędu kilkunastu nanosekund). Obecnie produkuje się specjalne, scalone kontrolery (Cache Controller, np. 82385 firmy Intel), które sterują pracą pamięci podręcznej. Działanie kontrolera pamięci podręcznej wyjaśnimy na przykładzie odczytu danych przez procesor z pamięci operacyjnej: żądanie odczytu danych przez procesor jest przechwytywane przez kontroler, który sprawdza czy dane, które procesor chce odczytać znajdują się w pamięci podręcznej. W sytuacji trafienia (ang. Cache Hit), kontroler przesyła te dane do procesora, bez konieczności czytania ich z wolnej pamięci operacyjnej, a tym samym, bez konieczności wprowadzania cykli niegotowości. W przypadku chybienia, kontroler odczytuje dane z pamięci operacyjnej, przesyła je do procesora oraz jednoczenie wpisuje je do pamięci podręcznej. Liczba trafień do całkowitej liczby odczytów jest większa niż 90%, co oznacza że ponad 90% odczytów jest dokonywanych z pamięci podręcznej, a tylko 10% ze znacznej wolniejszej pamięci głównej. Pozwala to wydatnie zwiększyć szybkość pracy komputera. Zapis danych przesyłanych z procesora do pamięci operacyjnej DRAM odbywa się z wykorzystaniem jednej z dwóch metod: metody Write Through (zapis równoczesny) i Write Back (zapis opóźniony).
Pamięć cache jest zorganizowana w linijki (o rozmiarach 16 lub 32 bajty - 128 lub 256 bitów), w których są przechowywane informacje pobrane z RAM w postaci słów binarnych. Jedna linijka jest najmniejszą porcją informacji - blokiem danych jaki układ cache wymienia z pamięcią operacyjną RAM.
W różnych linijkach może być więc zapisana kopia zawartości odległych bloków z pamięci głównej. Wewnętrzną organizację cache najlepiej jest przedstawić posługując się praktycznym przykładem. Poniżej opisano budowę 32-bajtowej linijki pamięci podręcznej L1 w procesorze Pentium (rys. 1).
W innych procesorach mogą być zastosowane trochę inne rozwiązania, jednak ogólna zasada organizacji cache w linijki pozostaje taka sama.

Rys. 1. Organizacja linijki w procesorze Pentium.
Procesor Pentium posiada oddzielną pamięć podręczną poziomu L1 dla kodu programu (8kB) i oddzielną dla danych (8kB). Każda z nich jest podzielona na 256 linijek (256 x 32 B = 8kB). Aby zbiór takich linijek był dla procesora użyteczną strukturą, w której łatwo odszukać potrzebne dane, musi istnieć mechanizm zapisywania i kodowania dodatkowych informacji na temat każdej linijki. Przede wszystkim potrzebna jest informacja o tym, które fragmenty zawartości pamięci RAM są aktualnie skopiowane w poszczególnych linijkach.
Jest to niezbędne, aby podczas żądania procesora odczytu z pamięci, kontroler cache mógł poprawnie określić czy dane są dostępne w linijkach, czy trzeba je sprowadzić z RAM. Wszystkie te informacje przechowuje się w katalogu cache (czasem określanym skrótem TAG-RAM). Jest on częścią pamięci podręcznej, która zawiera rekordy odpowiadające każdej linijce cache. Są w nich zakodowane informacje na temat danych aktualnie zapisanych w odpowiednich linijkach. Wartości poszczególnych pół tych rekordów mogą także wskazywać, że dana linijka jest wolna. W procesorze Pentium katalog jest podzielony na dwie równe części (opisywane jako katalog 1 i katalog 2), każda zawiera 128 rekordów. Jeden rekord odpowiada jednej linijce cache (razem jest więc 256 linijek). Z każdą parą rekordów o tym samym indeksie w katalogu 1 i katalogu 2 (0 do 127) jest dodatkowo związany jeden bit LRU. Budowę tak zorganizowanej pamięci cache przedstawia rysunek 2.

Rys. 2. Organizacja wewnętrznej pamięci podręcznej procesora Pentium.
Każdy rekord z katalogu składa się z następujących części:
- znacznik (20 - bitowy) jest to dwadzieścia najstarszych bitów adresu wskazującego odwzorowany w skojarzonej z rekordem linijce obszar pamięci RAM;
- dwa bity MESI, które pozwalają zakodować cztery możliwe statusy danych
w odpowiadającej rekordowi linijce. Określa się na tej podstawie czy linijki cache zawierają aktualną kopię danych z RAM, lub są wolne (dokładny opis wszystkich statusów znajduje się w dalszej części tego rozdziału).
Strukturę adresu, który jednoznacznie wskazuje dane zgromadzone w tak zorganizowanej pamięci cache pokazuje rysunek 3.

Rys. 3. Struktura adresu pamięci procesora Pentium.
Podczas dostępu procesora do cache układy logiczne dzielą przekazywany przez niego adres na następujące części:
- Znacznik (20 bitów) jest porównywany ze znacznikiem w katalogu cache
(rys. 2). Na podstawie porównania znaczników określa się, czy potrzebne procesorowi dane są w linijce cache (określanie trafienia).
- Wiersz (7 bitów) określa, która pozycja (indeks) w katalogu 1 i katalogu 2
rys 2. może odwzorowywać potrzebne dane.
- Słowo (3 bity) pozwala na określenie, które z ośmiu 32-bitowych słów przechowywanych w linijce zawiera dane potrzebne procesorowi.
- Bajt (2 bity) określa, który bajt w 32- bitowym słowie jest aktualnie potrzebny mikroprocesorowi.
W wypadku braku trafienia, tak zbudowany adres wskazuje blok w pamięci operacyjnej RAM, zawierający potrzebne dane (dokładnie opisuje to rozdział omawiający sposoby odwzorowania). Zgodnie z zasadą działania cache, po odczytaniu zawartości bloku z RAM musi ona być zapisana do pamięci podręcznej. Na podstawie bitu LRU oraz części adresu (pola wiersz) jest wyznaczana linijka, do której można dokonać zapisu. Dokładnie te problemy opisują następne rozdziały.
Skrót MESI używany do określania bitów w katalogu cache, został utworzony od pierwszych liter angielskich określeń czterech możliwych stanów linijki (Modified, Exclusive, Schared, Invalid). Zamieszczona niżej Tabela 1 przedstawia te stany oraz opisuje ich znaczenie w układzie cache procesora Pentium.

Tabela 1
Stan linijki Modified
zmodyfikowany Exclusive
wyłączny Shared
wspólny Invalid
nieważny
Ważność
Linijki ważna ważna ważna nieważna
Aktualność kopii danych w RAM nieaktualna aktualna aktualna linijka nie zawiera ważnych danych
Kopie w innych pamięciach podręcznych brak brak możliwe możliwe
Zapis danych w tym bloku pamięci może być w cache może być w cache ze zmianą statusu musi być w cache i w RAM musi być w RAM
Jak wynika z tabeli, procesor może odczytywać dane zapisane w linijkach cache, gdy ich status jest zmodyfikowany, wyłączny, lub wspólny. Wtedy na pewno linijka zawiera określony blok danych przepisanych z RAM. Stan nieważny oznacza, że linijka jest wolna i może być w razie potrzeby wypełniona danymi. Na podstawie stanu bitów MESI można także określić, czy dane w poszczególnych linijkach są także zapisane w innych poziomach pamięci podręcznej.
Stan bitów MESI zmienia się również podczas modyfikacji danych w pamięci. Dotychczas omawiane były jedynie zagadnienia związane ze skróceniem czas dostępu do danych i rozkazów podczas ich odczytu. Jednak procesor nie tylko odczytuje z pamięci RAM. W trakcie wykonywania programu musi też tam zapisywać wyniki swoich operacji, modyfikować pewne zmienne i dane. Niektóre z nich mogą być w tym czasie skopiowane także do pamięci podręcznej. Wiąże się z tym konieczność zadbania o aktualność obu kopii danych.
Do pamięci operacyjnej oprócz procesora mogą też mieć dostęp inne urządzenia. Mogą one zapisywać i odczytywać RAM bez udziału mikroprocesora. Jeśli dokonają zmiany słowa w RAM, którego kopia aktualnie jest przechowywana w cache, mogą spowodować, że procesor posiada w pamięci podręcznej nieaktualne dane. Również gdy procesor w trakcie programu dokona zmiany danych tylko w cache, inne urządzenia mogą odczytać bezpośrednio z RAM stare błędne wartości. Należy zaznaczyć, że taka niespójność może występować tylko dla pamięci podręcznej danych.
W oddzielnej pamięci podręcznej kodu programu procesor nie zapisuje swoich wyników, gdyż przechowuje ona jedynie dla niego instrukcje - kolejne rozkazy.
Są różne rozwiązania problemu spójności danych stosowane w różnych procesorach, jednakże generalnie można wyróżnić dwa sposoby:
Write Trougch (zapis jednoczesny)
W tym sposobie każdy zapis danych wykonywany jest jednocześnie zarówno do pamięci głównej jak i do cache. Każdy zapis wymaga więc dostępu procesora do pamięci RAM. Również każdy bezpośredni zapis do RAM wykonywany przez inne urządzenia musi być monitorowany przez procesor. W ten sposób może on w razie potrzeby uaktualnić zawartość cache. Jest to więc najbardziej naturalny sposób, jednak generuje znaczny przepływ danych między pamięciami co powoduje duże opóźnienia.
Wirte Back (zapis opóźniony)
W tym trybie przy zapisie procesor aktualizuje tylko pamięć podręczną. Jednocześnie dla zmodyfikowanych linijek układ cache ustawia odpowiednie statusy (na bitach MESI - opisane w Tabeli 1). Zawartość pamięci głównej jest aktualizowana później na żądanie. Może ono być wyrażone przez instrukcję programową WBINVO (Write Back and Invalid Data Cache), lub specjalny sterujący sygnał sprzętowy.
Aktualizacja jest też wyzwalana w wyniku braku trafienia w fazie odczytu z pamięci głównej. Gdy trzeba dokonać wymiany linijki cache, zawartość linijki usuwanej mającej status zmodyfikowany (zakodowany na bitach MESI), musi być koniecznie zapisana do RAM.
Taka implementacja sposobu utrzymania spójności danych jest bardziej wydajna, minimalizuje ilość cyklów zapisu do pamięci głównej. Problemem jest jednak to, że bezpośredni dostęp zewnętrznych modułów wejścia-wyjścia do RAM także powoduje konieczność uaktualniania pamięci cache co może powodować pewne opóźnienia.
W trakcie wykonywania programu może też nastąpić konieczność zapisu danych w obszarach RAM, które nie są aktualnie skopiowane do pamięci podręcznej (sytuacja zaznaczona w ostatnim wierszu i ostatniej kolumnie Tabeli 1). Niektóre procesory w takim wypadku mogą po prostu dokonywać zapisu w RAM z pominięciem układu cache. W nowszych generacjach procesorów stosuje się mechanizm, w którym zapis danych pociąga za sobą skopiowanie odpowiedniego bloku RAM do linijki cache, gdzie jest on modyfikowany.
Dzięki temu ewentualny odczyt lub zapis tych samych danych w następnych rozkazach procesora może przebiegać już bez konieczności odwoływania się do RAM.
Problemy związane z zapisem w RAM komplikują się jeszcze bardziej w układach wieloprocesorowych, gdzie kilka procesorów mających własne pamięci podręczne a w nich kopie niektórych danych, współpracuje z jednym układem pamięci głównej. Wykorzystuje się w nich specjalny protokół sprawdzania aktualności linijek cache w oparciu o bity MESI.