Pamięć cache

Cache to mechanizm w którym ostatnio pobierane dane dostępne ze źródła o wysokiej latencji i niższej przepustowości są trzymane w pamięci o lepszych parametrach.

Cache jest elementem właściwie wszystkich systemów - współczesny procesor ma 2 albo 3 poziomy pamięci cache oddzielającej go od pamięci RAM. Dostęp do dysku buforowany jest w cache w pamięci RAM, a dokumenty HTTP są cache'owane przez programy http proxy oraz przez przeglądarkę.

ZADANIA

Systemy te są tak wydajne dzięki lokalności odwołań - jeśli nastąpiło odwołanie do pewnych danych, jest duża szansa że w najbliższej przyszłości będą one potrzebne ponownie. Niektóre systemy cache próbują przewidywać które dane będą potrzebne i pobierają je wyprzedzając żadania. Np. cache procesora pobiera dane w pakietach po kilkadziesiąt czy też więcej bajtów, cache dysku zaś nawet do kilkuset kilobajtów kolejnych właśnie czytanego pliku.

Niektóre systemy pamięci cache umożliwiają informowanie systemu na temat charakteru danych by umożliwiać bardziej efortywny caching. Służy temu np. wywołanie systemowe madvise

Cache - (pamięć buforowa, pamięć notatnikowa lub pamięć podręczna) to rodzaj bardzo szybkiej pamięci podręcznej, służącej do buforowania danych, przesyłanych pomiędzy twardym dyskiem a pamięcią operacyjną; cache twardego dysku wywiera bardzo istotny wpływ na wydajność całego systemu; w sposób niezauważalny dla użytkownika system przenosi dane do pamięci cache i kopiuje je na twardy dysk dopiero w momencie, kiedy procesor jest mniej zajęty; pamięć cache przesyła dane do procesora około 100 000 razy szybciej, niż twardy dysk; stąd proporcjonalnie do wielkości pamięci cache zwiększa się również wydajność systemu; łatwo to zauważyć po różnicy w szybkości działania systemu, kiedy dysponuje on 32 MB pamięci operacyjnej, a kiedy w systemie dostępnych jest tylko 8 lub 16 MB.

Typy organizacji i informacji w pamięci CACHE: 1. Asocjacyjna 2. Bezpośrednia 3. Zbiorowe odwzorowanie asocjacyjne

Zasady lokalności CACHE: 1. Lokalność przestrzenna - dane umieszczane są stosunkowo blisko siebie 2. Lokalność czasowa - dane pobierane są z pamięci wielokrotnie 

TYPY

cache poziomu pierwszego(32 kb) i drugiego 512KB trzeciego (1024KB) czwartego(2048KB)

Cache (8kB pamięci podręcznej danych i 8kB pamięci podręcznej kodu programu), pamięć Cache
32-bajtowe (256 bitowe); Jeśli podczas operacji odczytu poszukiwanych danych nie ma w posiada komórki podręcznej pamięci wewnętrznej, procesor sięga po nie do zewnętrznej pamięci Cache (zwanej w tym przypadku pamięcią drugiego poziomu).
Zastosowanie funkcji seryjnego zapisu i odczytu (Burst Write and Read Function); Seryjny odczyt polega na jednokrotnym wystawieniu na szynie adresowej (podczas pierwszego cyklu zegarowego), adresu odczytywanego słowa z pamięci RAM, a następnie w czterech kolejnych cyklach zegarowych odczytanie czterech 64-bitowych danych, w ten sposób, w ciągu pięciu cykli
zegarowych zostaje skompletowane 256-bitowe słowo danych, ładowane do 256-bitowej komórki pamięci Cache.

Pamięć podręczna Cache może pracować w trybie Write-Back i Write- Trough. Tryb Write-Back (z opóźnionym zapisem) polega na zapisie danych najpierw do pamięci Cache a dopiero później dane przepisywane są do pamięci RAM. Tryb Write-Trough dotyczy jednoczesnego zapisu danych do pamięci Cache i RAM.
Struktura super skalarna i przetwarzanie danych dwu potokowe

Oprócz standardowej pamięci operacyjnej procesor dysponuje jeszcze szybką pamięcią (cache memory) służąca do przechowywania ostatnio używanych informacji.

Znaczenie

Dane aktualnie używane są trzymane w szybszej pamięci, natomiast te aktualnie niepotrzebne w wolniejszej, ale większej. Ponieważ różnice w czasie dostępu między kolejnymi poziomami są często rzędu 10:1, dobre wykorzystanie właściwości pamięci cache ma zazwyczaj większe znaczenie niż liczba cykli procesora koniecznych do wykonania algorytmu.

Cel stosowania pamięci cache w procesorach

    Aby określić cel stosowania pamięci podręcznej cache, należy w skrócie omówić zasadę działania mikroprocesora.

    Jest on układem cyfrowym taktowanym przez sygnał zegarowy, który realizuje zadany program - ciąg rozkazów umieszczony w pamięci operacyjnej. Program ma zwykle zadanie przetworzenia określonych danych pobranych z pamięci (lub urządzeń zewnętrznych), oraz zapisanie wyników ich przetwarzania, też w pamięci (lub przekazanie do urządzeniach zewnętrznych). Schemat blokowy mikroprocesora przedstawiono na rysunku 1.1. Na schemacie znajduje się też  blok pamięci operacyjnej, który fizycznie stanowi oddzielny układ.

Rys. 1.1 Schemat blokowy mikroprocesora.
 

OZNACZENIA RAM (Random Acces Memory) - pamięć operacyjna BU (Bus Unit) - układ zarządzający magistralami AU (Addresing Unit) - układ obliczania adresu połączony z MMU (Memory Management Unit) układem zarządzania pamięcią IU (Instruction Unit) - dekoder instrukcji EU (Execution Unit) -moduł wykonawczy zawiera ALU (Aritmetic-Logic Unit) jednostkę arytmetyczno-logiczną FPU (Floating Point Unit) jednostkę zmiennoprzecinkową

Połączenie mikroprocesora z pamięcią operacyjną realizuje się za pomocą dwóch magistral adresowej i
danych. Do sterowania ruchem na tych magistralach wykorzystuje się zbiór sygnałów sterujących.

Realizacja programu przez taki układ przebiega następująco:

 Kod rozkazów jest odczytywany z pamięci RAM i umieszczany w kolejce instrukcji.

 Poszczególne instrukcje (słowa binarne) trafiają z kolejki do dekodera IU, który rozkodowuje rozkazy przeznaczone do wykonania. Wykorzystuje przy tym informacje o sposobie kodowania rozkazów zawarte w pamięci stałej ROM umieszczonej w strukturze procesora.

 Zależnie od rozkazu dekoder często musi wydzielić z kodu instrukcji zawarte w niej argumenty, lub adresy danych, które procesor będzie wykorzystywał. Są one przesyłane odpowiednio do bloku wykonującego instrukcje EU i bloku adresowego AU.

 Blok adresowy AU i zarządzania pamięcią MMU wypracowuje na tej podstawie odpowiednie sygnały i dane przekazywane do bloku zarządzania magistralami BU. Po wystawieniu adresu na magistrali adresowej generowane są sygnały sterujące, które powodują odczyt danych z pamięci - układ pamięci wystawia dane na magistrali danych.

 Dane są przekazywane do bloku wykonującego instrukcje lub (jeśli są kodami następnych rozkazów programu do kolejki instrukcji).

 Blok wykonujący instrukcje EU zawiera jednostkę arytmetyczno-logiczną ALU, która dokonuje porównań lub działań matematycznych na argumentach stałoprzecinkowych. Argumenty zmienno-przecinkowe są przetwarzane w jednostce do tego celu wyspecjalizowanej FPU.

 Wyniki przetwarzania trzeba często zapisać w pamięci pod określonym adresem - blok wykonujący instrukcje przekazuje odpowiednie dane do bloku zarządzania pamięcią i bloku sterującego magistralami.     Wszystko musi być odpowiednio synchronizowane w czasie, dlatego układ wykonujący instrukcje EU wypracowuje też różne sygnały sterujące, przez które ma możliwość wpływu na pracę innych bloków. Układ wykonujący instrukcje często też przechowuje wyniki pośrednie przetwarzania danych we własnych rejestrach. Jednak aby nie zaciemniać schematu na rys. 1.1 nie przedstawiano szczegółowej budowy wyróżnionych bloków.

Szybkość wykonywania programu zależy w znacznej mierze od czasu dostępu procesora do układu pamięci operacyjnej. Nie bez znaczenia jest także pojemność pamięci (ile danych można w niej zapisać). Stosowane we współczesnych komputerach wielozadaniowe systemy operacyjne umożliwiają uruchamianie wielu programów jednocześnie. Dobrze jest więc gdy procesor ma do dyspozycji dużą pamięć operacyjną RAM. Ważnym czynnikiem pozostaje też koszt zastosowanego układu pamięci. Naturalnie w przypadku praktycznego systemu musi on być jak najniższy.

Istnieją wzajemne zależności pomiędzy wszystkimi opisywanymi wyżej parametrami.
 

 mniejszy czas dostępu - większy koszt

 większa pojemność - większy czas dostępu

    Z tego wynika, że nie jest możliwe wyprodukowanie idealnej pamięci o maksymalnie dużej pojemności, a przy tym małym czasie dostępu i minimalnym koszcie. Możliwe jest budowanie szybkich układów, ale stosunkowo drogich i o małej pojemności. Istnieją też duże pamięci o małych kosztach w przeliczeniu na bajt, ale cechujące się mniejszą efektywnością w zakresie czasu dostępu.

We współczesnych procesorach stosuje się rozwiązanie kompromisowe, polegające na zastosowaniu pamięci wewnętrznej dwupoziomowej. Mikroprocesor wyposaża się we względnie dużą i wolniejszą pamięć główną, oraz w mniejszą ale szybszą pamięć podręczną cache. Ilustruje to schemat blokowy przedstawiony na rysunku 1.2. Takie rozwiązanie pozwala na korzystanie z pamięci o dużej pojemności, jednocześnie możliwe jest umieszczenie najpotrzebniejszych danych, w szybkiej pamięci podręcznej.
Pamięć podręczna zawiera kopię części zawartości pamięci głównej. Gdy procesor zamierza odczytać słowo z pamięci, najpierw następuje sprawdzenie, czy słowo to nie znajduje się w pamięci podręcznej. Jeśli tak, to słowo to jest szybko dostarczane do procesora. Jeśli nie, to blok pamięci głównej RAM zawierający określoną liczbę kolejnych słów jest wczytywany do pamięci podręcznej, a następnie potrzebne słowo (zawarte w tym bloku) jest dostarczane do procesora. Następne odwołania do tego samego słowa i sąsiednich zawartych w przepisanym bloku będą realizowane już znacznie szybciej.
    Organizacja współpracy procesora z takimi pamięciami wymaga zastosowania dodatkowego układu - kontrolera cache, który steruje tym procesem.

Rys 1.2 Podłączenie cache do procesora

Rys 1.3 Algorytm dostępu procesora do pamięci

    Efektywność stosowania cache zależy w znacznej mierze od sposobu ułożenia kodu programów i danych pobieranych z pamięci przez mikroprocesory. Zwykle kod i dane nie są "porozrzucane" przypadkowo po całej dostępnej przestrzeni adresowej w pamięci RAM. Większość odwołań do pamięci w trakcie wykonywania programu odbywa się przez pewien czas pracy mikroprocesora w wąskim obszarze. Zjawisko to jest określane mianem lokalności odniesień.

Lokalność odniesień można uzasadnić intuicyjnie w następujący sposób:

• Z wyjątkiem rozkazów skoku i wywołania procedury, realizacja programów ma charakter sekwencyjny. Tak więc, w większości przypadków następny rozkaz przewidziany do pobrania z pamięci następuje bezpośrednio po ostatnio pobranym rozkazie.

• Rzadkością jest występowanie w programach długich, nieprzerwanych sekwencji wywołań procedury (procedura wywołuje procedurę itd.), a potem długiej sekwencji powrotów z procedur. Wymagałoby to ciągłego odwoływania się do oddalonych od siebie obszarów pamięci głównej, zawierających kody poszczególnych procedur.

• Większość pętli (konstrukcji bardzo często występujących w programach) składa się z małej liczby wielokrotnie powtarzanych rozkazów. Podczas iteracji następuje kolejne powtarzanie zwartej części programu.

• W wielu programach znaczna część obliczeń obejmuje przetwarzanie struktur danych, takich jak tablice lub szeregi rekordów ułożone kolejno w pamięci operacyjnej. Tak więc procesor pobiera dane zapisane w sposób uporządkowany w małym jej fragmencie.

    Oczywiście w długim czasie wykonywania programu procesor potrzebuje dane rozmieszczone w różnych odległych miejscach pamięci. Zwykle jednak, po wykonaniu skoku następne odniesienia odbywają się już lokalnie. Przepisanie bloku kolejnych komórek pamięci do szybkiego układu cache może więc skutecznie przyspieszyć dostęp do pamięci.

    Na drodze rozważań teoretycznych i różnych symulacji wyznaczono rozmiar tego wąskiego obszaru, do którego odwołuje się procesor. Stwierdzono, iż można przyjąć z prawdopodobieństwem 0,9 że większość odwołań do pamięci mieścić się będzie w bloku o rozmiarze nie przekraczającym 16 kB. Potwierdzają to praktyczne testy. Tak więc wystarczy naprawdę mały układ pamięci podręcznej cache, aby skutecznie przyspieszyć działanie mikroprocesora. Rozmiary całej pamięci RAM współczesnych komputerów są rzędu 64 - 128 MB, podczas gdy rozmiary cache w popularnych procesorach to 8 - 512 kB.

Przedstawione wyżej schematy przedstawiają układ cache w dużym uproszczeniu. Istnieje możliwość zastosowania rozwiązania, w którym ten pierwszy poziom cache przyspiesza dostęp do następnego układu pamięci podręcznej, ten z kolei może wymieniać dane jeszcze z następnym, lub z pamięcią główną RAM.  W niektórych stosowanych obecnie układach procesorowych można wyróżnić aż trzy poziomy pamięci podręcznej cache. W praktyce stosuje się wielopoziomową pamięć podręczną.  W stosowanych obecnie rozwiązaniach można wyróżnić następujące poziomy pamieci podręcznej.

• L1 - (level 1) zintegrowana z procesorem - umieszczona wewnątrz jego struktury.

• L2 - (level 2) umieszczona w jednej obudowie układu scalonego mikroprocesora lub na wspólnej płytce hybrydowej (Pentium II ).

• L3 - (level 3) występuje w bezpośrednim sąsiedztwie procesora ITANIUM.

Pamięć podręczna najniższego poziomu (L1) jest stosunkowo mała, ale dane w niej zgromadzone są szybko dostępne dla procesora. W wypadku braku potrzebnych w danym momencie danych (braku trafienia), następuje odwołanie do pamięci kolejnych, wyższych poziomów. Po ich odczycie następuje przepisanie do niższych poziomów, tak by były szybciej dostępne w kolejnych odwołaniach. Jeśli dane nie są aktualnie buforowane w cache, następuje odczyt bloku pamięci głównej RAM, który je zawiera i wymiana zawartości cache.
Pamięci niższych poziomów mogą mieć mniejszą pojemność i być bardziej efektywne. Procesor może szybko odczytywać mniejsze porcje danych w jednym cyklu zegara. Wyższe poziomy cache mają większe pojemności, dzięki czemu odwołania do RAM mogą odbywać się rzadziej. Można też w jednym odczycie przepisać większą porcję danych z RAM. Dobrze to obrazuje schemat przepływu danych w procesorze ITANIUM (rys. 1.3). Na tym schemacie pokazano też blok rejestrów procesora (Register File), w których zapisuje on odczytane z pamięci argumenty i wyniki działania rozkazów.

Rys 1.3 Schemat przepływu danych w procesorze ITANIUM
 

Jak wynika z rysunku, odczyt danych z pamięci RAM może odbywać się większymi porcjami z prędkością 2.1 GB na sekundę. Dzięki zastosowaniu odpowiedniej magistrali BSB (Back Side Bus) przepływ danych z pamięci podręcznej poziomu L3 do L2 odbywa się z prędkością 16 bajtów w ciągu jednego cyklu zegara. Możliwy jest również odczyt pojedynczych słów bezpośrednio do rejestrów co zaznaczono przerywaną linią. Z cache L2 procesor odczytuje już w jednym cyklu bloki danych wielkości 32 B. Pamięć poziomu L1 najbardziej efektywna w zakresie czasu dostępu, udostępnia procesorowi już pojedyncze słowa - zmienne przetwarzane w kolejnych rozkazach.

Schemat 1.3 najpełniej obrazuje korzyści jakie daje układ pamięci podręcznych cache.

Ważnym zagadnieniem, jest podział pamięci podręcznej na oddzielny blok dla kodu programu i oddzielny blok dla danych. W taki sposób jest podzielona pamięć poziomu L1 procesora ITANIUM - rys 1.3. Pamięć cache poziomów L2 i L3 jest już wspólna dla rozkazów i danych.
W wielu (szczególnie starszych) procesorach wykorzystuje się również jednolitą pamięć podręczną poziomu L1. Takie rozwiązanie też posiada pewne zalety. Poniżej przedstawiono korzyści płynące z zastosowania pamięci oddzielnej i jednolitej.

Pamięć oddzielna kod i dane
Eliminowana jest rywalizacja o dostęp do pamięci między układem pobierania i dekodowania rozkazów w procesorze, a jednostką wykonującą w tym samym czasie inne, poprzednio pobrane rozkazy, które mogą wymagać odczytu pewnych zmiennych z cache. Ma to szczególne znaczenie w przypadku procesorów superskalarnych, w których kilka rozkazów jest wykonywanych równolegle. Dlatego we współczesnych procesorach poziom pamięci podręcznej L1 jest zawsze dzielony na blok danych i instrukcji.

Pamięć łączna dla kodu i danych
Poprawia się współczynnik trafień w tak zorganizowanej pamięci podręcznej, dzięki temu, że  naturalnie równoważy się zapotrzebowanie na przechowywanie rozkazów i danych. Jeśli na przykład program wymaga ciągłego pobierania rozkazów i w małym stopniu korzysta z danych, dostępna pamięć podręczna zapełni się w większości rozkazami. Oddzielna cache dla danych w takiej sytuacji pozostałaby nie wykorzystana.
Drugą zaletą jest to, że upraszcza się układ procesora - łatwiej jest zrealizować w jego strukturze jeden bufor pamięci cache niż dwa.

Sposoby dołączania pamięci cache do procesora

    Układ cache jest w obecnych procesorach ściśle związany z ich strukturą - właściwie poziom L1 fizycznie stanowi integralną część mikroprocesora.  Jednak aby łatwiej było przedstawić zasadę działania i sposoby dostępu procesora do pamięci podręcznej, ta część programu traktuje je ją jako oddzielny blok logiczny, dołączony do mikroprocesora, nie zajmując się jej fizycznym umiejscowieniem. Pisząc o sposobach dołączania, mamy więc na myśli sposób umieszczenia bloku cache na drodze procesor - pamięć.

    Obecnie stosuje się trzy podstawowe sposoby dostępu procesora do pamięci podręcznej.

•       Look - Aside (dostęp bezpośredni)

Procesor odwołuje się do cache wykorzystując magistralę pamięciową. Pamięć podręczna jest podłączona równolegle z pamięcią operacyjną RAM.  W takim układzie częstotliwość pracy obu pamięci jest taka sama (komunikacja odbywa się po wspólnej magistrali), tylko czas dostępu dzięki szybkości cache może ulec skróceniu. Wykorzystanie tej samej magistrali nie jest korzystne. Jest ona blokowana przy każdym dostępie procesora do cache i nie może być w tym samym czasie udostępniona innym urządzeniom.




• Look - Throgh (dostęp "przez")

Układ pamięci podręcznej pośredniczy w dostępie procesora do RAM. Procesor odwołuje się do układu cache, natomiast ten układ jest dołączony przez magistralę pamięciową do RAM.




•   Backside (dostęp "z tyłu")

UIkład pamięci podręcznej jest dołączony do procesora przez oddzielną magistralę nazywaną BSB (Back Side Bus). Druga magistrala FSB (Front Side Bus) łączy procesor z pamięcią główną.  W tym układzie częstotliwości obu magistral są zupełnie niezależne. Możliwe jest też wykorzystanie magistrali FSB przez inne urządzenia zapisujące do pamięci RAM, w czasie gdy procesor komunikuje się z cache po BSB.

Budowa i organizacja pamięci podręcznej





     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. 4.6).  W innych procesorach mogą być zastosowane trochę inne rozwiązania, jednak ogólna zasada organizacji cache w linijki pozostaje taka sama.




Rys 4.6 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 4.7.




Rys. 4.7 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 4.8.




Rys 4.8. 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.  4.7). 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 4.7. 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	aieaktualna	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 (opisanych dokładnie w rozdziale 4.7), 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.

Sposoby odwzorowania pamięci RAM w cache, zalety i wady
poszczególnych rozwiązań





     W małym buforze pamięci podręcznej (8- 512 kB) przechowywane są aktualnie używane przez procesor kopie zawartości fragmentów dużej pamięci RAM, która ma rozmiary rzędu 64 - 128 MB. Musi istnieć mechanizm, który pozwala na identyfikację fragmentów RAM umieszczonych w poszczególnych linijkach cache. Problem ten już był sygnalizowany w poprzednim rozdziale.

•  Mapowanie bezpośrednie (Direct Mapped) - określane też jako odwzorowanie bezpośrednie




Rys 4.9 Organizacja pamięci podręcznej o bezpośrednim odwzorowaniu

    W tym rozwiązaniu pamięć operacyjna RAM jest podzielona na bloki - grupy kolejnych adresów. Blok zawiera określoną liczbę słów i odpowiada rozmiarem linijce cache. W każdej linijce pamięci podręcznej mogą być przechowywane tylko określone bloki z RAM.
    Jak wynika z rysunku 4.9, adres przekazywany przez procesor jest interpretowany przez układy logiczne cache jako trzy pola (znacznik + wiersz + słowo). Przypisanie linijek do konkretnych fragmentów RAM jest jednoznacznie określone przez część adresu stanowiącą r- bitowe pole wiersz. Przykładowo w linijce 0 pamięci podręcznej mogą być przechowywane tylko te bloki z RAM, w adresach których r- bitowe pole wiersz jest równe 0. W linijce 1 tylko te, dla których pole wiersz zawiera liczbę 1 itd.
    Tak więc w zależności od rozmiarów cache (ilości dostępnych linijek) i wielkości odwzorowywanej pamięci głównej, dzieli się pamięć RAM na  bloki, a te z kolei grupuje się przypisując do konkretnych linijek. Przy czym rozmiar linijki jest równy wielkości bloku, a ilość linijek wyznacza wielkość grupy bloków możliwych do odwzorowania w przeznaczonej dla nich linijce. Taką organizację określają ilości bitów z adresu przeznaczone dla kolejnych pól: znacznik, wiersz i słowo (oznaczonych na rysunku 4.9 literami s, r, w).
Pole oznaczone jako znacznik (s- bitowy) - tworzą najstarsze bity adresu w RAM. W momencie kopiowania bloku pamięci operacyjnej do linijki cache, pole to jest zapisywane w odpowiadającym tej linijce rekordzie w katalogu cache.
Najmłodsza część adresu - słowo (w - bitowe) oznacza numer słowa w konkretnej linijce lub w bloku RAM, do którego odwołuje się procesor.
    W momencie gdy procesor chce odczytać z pamięci określone dane wyznacza ich adres w RAM. Układy logiczne cache na podstawie pola wiersz wiersz (części tego adresu) określają, która linijka cache może te dane zawierać. Następnie porównywany jest odpowiadający jej znacznik z katalogu cache z najstarszą częścią adresu. W wypadku zgodności znaczników układ porównujący generuje sygnał trafienia (wtedy dane są szybko odczytywane z pamięci podręcznej), lub sygnał chybienia (wtedy następuje odczyt z RAM).

Aby ułatwić użytkowi zrozumienie tego zagadnienia poniżej przedstawiono praktyczny przykład takiego odwzorowania:
- pamięć RAM ma rozmiar 16 MB
- pamięć podręczna ma rozmiar 64 kB
- adres który jednoznacznie wyznacza wszystkie bajty w pamięci RAM musi być 24- bitowy (2²⁴ = 16 MB).
- pamięć podręczna jest zorganizowana w linijki 16- bajtowe - musi więc zawierać 4 K linijek (4 K x 16 B = 64 kB).
- pole wiersz wyznaczające linijkę jest 12- bitowe (2¹² = 4K).
- ponieważ jest 16 bajtów w jednej linijce pole słowo musi być czterobitowe.
- najstarsze osiem bitów adresu stanowi pole znacznik.

Strukturę adresu przedstawia poniższy rysunek.




Rys 4.9.1. Przykład struktury adresu w pamięci przy odwzorowaniu bezpośrednim.

Poniżej przedstawiono tabelę określającą przypisanie konkretnych bloków pamięci RAM do poszczególnych linijek cache.




Z analizy tabeli wynika, że nigdy nie może się zdarzyć taka sytuacja aby w jednym wierszu pamięci cache mogły być odwzorowane bloki pamięci, których adres zawiera taką samą wartość w polu znacznik

Podsumowując opis odwzorowania bezpośredniego można przedstawić następujące zalety tego rozwiązania:
- prostota konstrukcji - łatwo jest zbudować układ porównujący i wydzielający poszczególne pola z adresu.
- szybkość wyszukiwania informacji - sprawdzenie czy potrzebny blok jest w cache wymaga jednej operacji porównania (pola znacznik).

Zasadniczą wadą jest mała efektywność działania takiego układu, szczególnie w sytuacji gdy procesor potrzebuje często dane z różnych bloków pamięci RAM, których odwzorowanie jest przewidziane w tej samej linijce.  Za każdym razem kontroler cache musi usunąć z linijki pamięci podręcznej aktualny blok i wpisać inny, chociaż jest prawie pewne, że w następnym rozkazie będzie on potrzebny ponownie. Przykładowo w pamięci opisanej w powyższej tabeli taka sytuacja występuje przy odczytywaniu na przemian adresów 000000  i  010000 (zapis szesnastkowy). Zgodnie z zasadą odwzorowania bezpośredniego musi być wtedy na przemian wymieniana zawartość linijki 0 - wypełniana blokami 16 kolejnych bajtów o adresach 00000(0-F) i 01000(0-F).




• Pełna asocjacja (Fully Asociative) określana też jako odwzorowanie w pełni skojarzeniowe.




Rys 4.10 Organizacja pamięci podręcznej w pełni skojarzeniowej

    Procesor określa potrzebne mu dane przekazując ich adres, który układy logiczne cache dzielą na pole znacznik i słowo (zgodnie z rysunkiem 4.10). Układ cache sprawdza, czy w katalogu pamięci podręcznej znajduje się rekord, który zawiera znacznik identyczny z najstarszą częścią adresu. Jeśli taki rekord zostanie odnaleziony, odpowiadająca mu linijka zawiera potrzebne procesorowi dane (jest trafienie). W przeciwnym wypadku układ porównujący wysyła sygnał chybienia w pamięci podręcznej, co oznacza konieczność odczytu z RAM. Odczyt danych nie odwzorowanych z pamięci głównej wiąże się z ich zapisem do wolnej linijki, oraz skopiowaniem s- bitowego znacznika z adresu do odpowiadającego jej rekordu w katalogu cache.
    Taka organizacja pozwala na składowanie dowolnego bloku RAM w dowolnym miejscu pamięci podręcznej. Jest to bardzo elastyczna konstrukcja i umożliwia dużą skuteczność cache niezależną od ułożenia kodu programów i danych w RAM. Jednak ma bardzo dużą wadę - odszukiwanie informacji w pamięci podręcznej wymaga przeglądania dużego katalogu znaczników.

Poniżej przedstawiono praktyczny przykład odwzorowania w pełni skojarzeniowego dla pamięci RAM 16 MB i pamięci cache 64 kB zorganizowanej w 16- B linijki. Strukturę adresu przedstawia poniższy rysunek.




  Rys 4.9.2 Przykład struktury adresu w pamięci przy odwzorowaniu skojarzeniowym

    Największym problemem w tym sposobie odwzorowania jest zbudowanie układu, który porównuje równolegle znaczniki z częścią adresu przekazanego przez procesor. Jak przedstawia schemat logiczny (rys. 4.10), układ ten musi generować sygnał trafienia w taki sposób, aby wiadomo było, która linijka zawiera potrzebne dane. Stwierdzenie braku trafienia w pamięci cache o rozmiarze 64 KB, zorganizowanej w 16 bajtowe linijki, wymaga od układu porównania 4096 znaczników (sprawdzenia 4 K linijek).




• Asocjacja zespołowa (Set Asociative) - określana też jako odwzorowanie sekcyjno-skojarzeniowe

    Jest to rozwiązanie najczęściej spotykane w obecnych procesorach. Łączy ono w sobie zalety dwóch poprzednich, opisanych wyżej sposobów odwzorowania. Po części zostało już przedstawione przy omawianiu organizacji pamięci podręcznej procesora Pentium w rozdziale 4.3.




Rys 4.11 Dwudrożna sekcyjno-skojarzeniowa organizacja pamięci podręcznej

    Pamięć cache jest tu podzielona na sekcje (zespoły), w każdej sekcji znajduje się pewna liczba linijek. Na rysunku 4.11 schemat logiczny przedstawia rozwiązanie z dwoma linijkami w jednej sekcji takie jak zastosowano w procesorze Pentium (opis. w rozdz. 4.3). Tak więc, jedna sekcja to dwie linijki o tym samym numerze - indeksie z katalogu 1 i katalogu 2 (rys. 4.7 rozdział 4.3). Tak zorganizowaną pamięć określa się jako dwudrożną (lub dwukanałową). Często stosowane są też rozwiązania z czterema linijkami w jednej sekcji, wtedy pamięć podręczna jest czterokanałowa.
Jak wynika z rysunku 4.11, adres przekazywany przez procesor jest rozkładany na trzy składniki:
- Słowo - oznacza miejsce, pozycję danej w linijce cache lub bloku RAM (analogicznie jak w innych sposobach odwzorowania)
- Sekcja - wyznacza jednoznacznie dwie linijki zgrupowane w jednej sekcji, w której dany blok może być odwzorowany.
-  Znacznik - jest wykorzystywany do określenia, czy potrzebne procesorowi dane są aktualnie w cache i w której z linijek w sekcji są zapisane. W wypadku pamięci dwudrożnej w celu określenia trafienia należy dokonać dwóch porównań znaczników.

Po wnikliwej analizie opisanych wcześniej dwóch poprzednich rozwiązań, zrozumienie zasady działania układu z rysunku 4.11 nie powinno sprawić trudności użytkownikowi programu wspomagającego nauczanie.
Jeśli ten model (rys. 4.11) ograniczy się do jednej sekcji zawierającej wszystkie linijki cache, to będzie to odwzorowanie w pełni skojarzeniowe (wtedy część adresu oznaczona jako sekcja staje się zbędna, więcej bitów musi natomiast zawierać pole znacznik). Jeśli w układzie będzie występowało tyle sekcji ile linijek (jedna linijka w jednej sekcji) to będzie to odwzorowanie bezpośrednie - sekcja oznacza wtedy jednoznacznie numer wiersza (pole wiersz na rysunku 4.9 ) czyli linijki w cache.
W odwzorowaniu sekcyjno-skojarzeniowym występuje problem podjęcia decyzji, którą z linijek w obrębie sekcji należy wykorzystać, w wypadku potrzeby zapisania w cache nowego bloku odczytanego z RAM. Na podstawie jego adresu przekazanego przez procesor (pola sekcja) określa się, w której sekcji blok może być odwzorowany. Dodatkowe informacje z katalogu cache (bity LRU) służą do wyznaczania linijki w tej sekcji, która jest wolna lub zawiera najmniej potrzebne dane - jest to omówione w rozdziale 4.6.

Praktyczny przykład takiego sposobu odwzorowania jest taki sam jak opisywane przy omawianiu poprzednich układów:
- 16 MB pamięci RAM jest odwzorowane w 64 KB cache
- linijki 16 bajtowe (razem 4K linijek)
- pamięć cache jest podzielona na katalog 1 (2 K linijek) i katalog 2 (2 K linijek)
- 11- bitowe pole sekcja jednoznacznie wskazuje dwie linijki które ją tworzą (2¹¹=2048    -  2K)
- w wyniku porównania 9-bitowego znacznika sprawdza się, która z linijek odwzorowuje dany blok z pamięci lub stwierdza się brak trafienia.




  Rys 4.9.3 Przykład struktury adresu przy odwzorowaniu sekcyjno-skojarzeniowym.

Przykładowo w sekcji 0 tak zorganizowanej pamięci mogą być odwzorowane następujące bloki RAM: 00000(0-F), 00800(0-F), 01800(0-F), ........., FF800(0-F). Adres żadnego z przypisanych do tej samej sekcji bloków nie może mieć takich samych dziewięciu najstarszych bitów (takiego samego znacznika).

http://pojeciownik.komputery.szkola.net/str_ca.htm

http://pl.wikipedia.org/wiki/Cache

http://pojeciownik.komputery.szkola.net/str_ca.htm

http://bszx.iinf.polsl.gliwice.pl/dyplomy/1/prakt11.htm

E.I. gr. II Kochan Marcin

---