wykl04

Wykład 4

Pamięć podręczna

Lokalność odniesień

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 iokalności odniesień, można je uzasadnić intuicyjnie w następujący sposób:

O 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.

41 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.

O 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.

Można przyjąć z dobrym prawdopodobieństwem (np. 0,9) że większość odwołań do pamięci mieścić się będzie w bloku o rozmiarze nie przekraczającym np. 16 kB.

•    Lokalność odniesień - przesłanki tworzenia pamięci podręcznej

•    Pamięć podręczna - podstawy

•    Struktura pamięci podręcznej

•    Pamięć podręczna - działanie

•    Właściwości pamięci podręcznej

•    Funkcja odwzorowania

-    Odwzorowanie bezpośrednie

-    Odwzorowanie skojarzeniowe

-    Odwzorowanie sekcyjno-skojarzeniowe

•    Algorytmy zastępowania

•    Problemy zapisu

•    Rozmiar bloku

•    Topologie pamięci

•    Liczba pamięci podręcznych

•    Trójpoziomowa pamięć podręczna - ITANIUM

•    Struktura logiczna pamięci podręcznej

•    Współczynnik trafień

Pamięć podręczna (cacha)

Pamięć podręczna - podstawy

■) £ Pamięć podręczna = sposób na zbudowanie pamięci o szybkości

właściwej dla szybkich (ale mało pojemnych pamięci) i pojemności jaką cechują się pamięci o dużej pojemności (ale wolne).

■J t Pamięć podręczna zawiera kopię części zawartości pamięci głównej.

Gdy procesor zamierza odczytać słowo w pamięci, najpierw następuje sprawdzenie, czy słowo to nie znajduje się w pamięci podręcznej. Jeśli tak, to słowo jest dostarczane do procesora. Jeśli nie, to blok pamięci głównej zawierający ustaloną liczbę słów jest wczytywany do pamięci podręcznej, a następnie słowo jest dostarczane do procesora.

Błock Transfer

Word Transfer

CPU

(*) Aidta

Struktura pamięci podręcznej

7^rrmk

BI #1

/

MakUTMw)

• Dfafoić bloku -(T«»)

a)    Pamięć główna

b)    Pamięć podręczna (cache)

BI #7

BI #M

f-i

-jfr Pamięć podręczna zawiera C wierszy zawierających K słów każdy, a liczba wierszy jest znacząco mniejsza od liczby bloków w pamięci głównej (C«M). W każdej chwili, pewien zespół bloków pamięci głównej pozostaje w wierszach pamięci podręcznej.

Pamięć główna składa się z 2" adresowalnych słów, przy czym każde słowo ma jednoznaczny adres n-bitowy. Aby było możliwe odwzorowywanie pamięć ta składa się z pewnej liczby bloków o stałej długości, zawierających K słów każdy. Tak więc występuje M=2ⁿ/K bloków.

Właściwości pamięci podręcznej

Zagadnienia charakterystyczne dla pamięci podręcznych

i £ Pojemność pamięci \ (■ Rodzaj odwzorowania:

•    bezpośrednie

•    skojarzeniowe

•    sekwencyjno - skojarzeniowe

Algorytm wymiany O najmniej ostatnio używany (LRU) \ \ pierwszy wszedł - pierwszy wychodzi (FIFO)

O najrzadziej używany (LFU)

O swobodny ^ £ Spójność. Sposób zapisu

jednoczesny

opóźniony

4 (- Rozmiar bloku ^ Liczba pamięci podręcznych

jedno- lub dwupoziomowa jednolita lub rozszczepiona

Pamięć podręczna - działanie

•ę Jeśli słowo w bloku pamięci jest odczytywane, to odpowiedni blok jest przenoszony do jednego z wierszy pamięci podręcznej.    _w

Ponieważ bloków jest więcej niż wierszy, określony wiersz nie może być jednoznacznie i trwale przypisany określonemu blokowi.

Każdy wiersz zawiera w związku z tym znacznik określający, który blok jest właśnie przechowywany. Znacznik jest zwykle częścią adresu pamięci głównej

Podczas operacji odczytu procesor generuje adres słowa, które ma być odczytane, RA. Jeśli słowo jest zawarte w pamięci podręcznej, jest dostarczane do procesora. W przeciwnym razie blok zawierąjący to słowo jest ładowany do pamięci podręcznej, po czym słowo jest dostarczane do procesora

Właściwości pamięci podręcznej

** Funkcja odwzorowania Rodzaj odwzorowania:

° bezpośrednie ° skojarzeniowe ° sekwencyjno - skojarzeniowe

Funkcja odwzorowania

^ Pamięć podręczna zawiera kopię części zawartości pamięci głównej.

t

w

Wierszy w pamięci podręcznej jest mniej niż bloków pamięci głównej -» wymagany jest aigorytm odwzorowania bloków pamięci głównej w wierszach pamięci podręcznej (metoda określania który

blok pamięci głównej aktualnie zajmuje wiersz pamięci podręcznej.

JSSSL

Wybór funkcji odwzorowania dyktuje organizację pamięd podręcznej.

Odwzorowanie bezpośrednie - cz.ll

i

Funkcja odwzorowywania może być realizowana za pomocą adresu.

Każdy adres pamięd głównej składa się z 3 pól.

Wykorzystanie części adresu jako numeru wiersza pozwala na jednoznaczne odwzorowanie każdego bloku pamięd głównej w pamięd podręcznej

Utaak

Wienz

AdKtptmcciftowmg-

Adres słowa (np. bajtu) w pamięd podręcznej

Najprostsza metoda odwzorowania = odwzorowanie bezpośrednie, polega na odwzorowywaniu każdego bloku pamięci głównej na tylko jeden wiersz pamięci podręcznej. ^    MataMbwj

Odwzorowywanie: i - numer wiersza cache

i=j modulo m

gdzie:

j - numer bloku pamięci głównej,

m - liczba wierszy w pamięci podręcznej

l_ - -

j

Odwzorowanie bezpośrednie - cz.HI

| Przykład:

Pojemność cache = 64 KB. Bloki po 4 bajty.

4

< > Organizacja cache:

2¹⁴ (16K) wierszy po 4 bajty kaidy.

O Pojemność pamięci głównej 16 MB (16M x 1 bajt) <-> 24-bitowy adres (2²⁴ = 16 M).

° Dla odwzorowania pamięć główna = 4 M bloków po 4 bajty każdy.

Znacz* Wiarat+aluwo Dane

OB - przykład odczytu

i Adresy 24-bitowe, 16M x bajt

• Cztemastobitowy numer wiersza jest wykorzystywany jako indeks dostępu do określonego wiersza w pamięci podręcznej

• Jeśli 8-bitowy znacznik jest zgodny ze znacznikiem aktualnie przechowywa-” “ nym w tym wierszu, to 2-bitowy numer t słowa służy do wyboru jednego z 4 * bajtów w tym wierszu

tMMHI 112)5*1) I)52*24*

0002

0001

W przeciwnym razie 22-bitowe pole obejmujące znacznik i wiersz jest wykorzystywane do pobrania bloku z pamięci głównej

0006

0004

0000

FFFt

FFFU

0006

0004

0000

6)654321

1)5)9246

# Pobierane bajty:    *

(tagx2¹⁸+wierszx2^ł)+0, (tagx2^u+wierszx2²)+1,

(tagx2¹⁸+wierszx2²)+3,

*•— 32b*iy —► Parnią gUwM ift MB

Adro pamięci gtó»TK]²

Żadne dwa bloki odwzorowane w tym samym wierszu nie mają takiego samego znacznika.

000000,000001 000002,000003    !

m=16K=2¹⁴

i=/modulo 2¹⁴.

Wiersz pamięci	Wiersz pamięci
podręcznej	podręcznej
(teoria)	(przykład)
0	0
1	1

Przypisane adresy początkowe (teoria)

0, 4xm,... , 4x(2^s-m)

4, 4x(m+1),..., 4x( 2^s-m+1)

Przypisane adresy początkowe bloków pamięci głównej i (przykład) 000000, 010000, ..., FF0000

000004,010004, ..., FF0004

m-1

3FFF

4x(m-1), 4x(2m-1) .....4x(2^s-1)

00FFFC, 01FFFC,..., FFFFFC

Odwzorowanie skojarzeniowo

jk. Odwzorowywanie skojarzeniowe eliminuje wady odwzorowywania bezpośredniego, gdyż umożliwia ładowanie każdego bloku pamięci głównej do dowolnego wiersza pamięci podręcznej.

Sterujące układy logiczne pamięci podręcznej interpretują adres pamięci po prostu jako znacznik i pole słowa

Pole znacznika jednoznacznie określa blok pamięci głównej. W celu stwierdzenia, czy blok znajduje się w pamięci podręcznej, sterujące układy logiczne pamięci podręcznej muszą jednocześnie zbadać zgodność znacznika wszystkich wierszy.

OS - przykład odczytu

* Adres pamięci głównej składa się z 22-bitowego znacznika i 2-bitowego numeru bajtu.

— MW,—»• PmitfiMmWMB

W przypadku każdego wiersza pamięci podręcznej 22-bitowy znacznik musi być przechowywany razem z 32-bitowym blokiem danych.

W przypadku odwzorowania skojarzeniowego blok do zastąpienia jest wybierany elastycznie, kiedy nowy blok jest wczytywany do pamięci podręcznej.

OSS - przykład odczytu

• Przykład: dwa wiersze w każdej sekcji (k=2); 8K sekcji (adresowanych 13-ma bitami)

iweii

112KM3

U52MM

m

mi

MM

Ml

■mtrm •

wc ^lm4	12343471
MN MM MM	11233913 T77T77T7
mc im.
tom	1X9021
0004 0000	13579344

..J

■*—n My—•-

13-bitów nru sekcji identyfikuje sekcję (2 wiersze) i określa nr bloku w pamięci głównej (modulo 2¹³)

Następnie jest sprawdzana zgodność obu wierszy sekcji z numerem znacznika adresu, do którego chcemy uzyskać dostęp.

Pobierany jest bajt o n-rze określonym przez „nr słowa"

Sckqja

Np. do sekcji #0 przypisane bloki 000000, 00A000, .., FF1000

Odwzorowywanie: m = v x k; 1 = J modulo y gdzie:

i - numer sekcji pamięd podręcznej,

J - numer bloku pamięci głównej,

m - liczba wierszy pamięci podręcznej.

Za pomocą d bitów precyzuje się jedną z v = 2^d sekcji, a s bitów (znacznik + nr sekcji) określa jeden z 2⁵ bloków pamięci głównej.

W tej metodzie pamięć podręczna jest dzielona na v sekcji, z których każda składa się z k wierszy.

Blok Bj, może być odwzorowywany na dowolny wiersz sekcji „i".

Sterujące układy logiczne pamięci podręcznej interpretują adres pamięci jako trzy pola: znacznik, sekcja i słowo.

I * I

I . I I    I

*    •    i

i • i

•    •    i

■    i

Mata Mcautry

IV.

Porównani^{1 2}

Właściwości pamięci podręcznej

Algorytm wymiany

o najmniej ostatnio używany (LRU) o pierwszy wszedł - pierwszy wychodzi (FIFO)

° najrzadziej używany (LFU)

T swobodny

Algorytmy wymiany

O Algorytm „najmniej ostatnio używany" (ang. /east-recentfy used - LRU).

Algorytm określa, ie należy zastąpić ten blok w sekcji, który pozostawał w pamięci podręcznej najdłużej bez odwoływania się do niego.

< > Algorytm „pierwszy wchodzi - pierwszy wychodzi” (ang. fist in - First out-

FIFO).

Polega on na zastępowaniu tego bloku w sekcji, który najdłużej pozostawał w pamięci podręcznej.

O Algorytm „najrzadziej używany" {ang. teast frequently used - LFU).

Określa on, że zastępowany jest ten blok w sekcji, którego dotyczyło najmniej odniesień.

O

Metodą abstrahującą od ilości odniesień jest przypadkowy wybór wśród kandydujących wierszy.

Algorytmy wymiany

■^-Gdy do pamięci podręcznej jest wprowadzany nowy blok, jeden z istniejących bloków musi być zastąpiony.

W przypadku odwzorowywania bezpośredniego istnieje tylko jeden możliwy wiersz dla każdego określonego bloku i wybór nie jest możliwy.

! W przypadku metody skojarzeniowej i sekcyjno-skojarzeniowej ^: wymagany jest algorytm zastępowania.

Właściwości pamięci podręcznej

n Sposób zapisu

o jednoczesny o opóźniony

Spójność

** Rozmiar pobieranego bloku

Problemy zapisu

Przed zastąpieniem bloku w pamięci podręcznej należy sprawdzić, czy musi on być zaktualizowany w pamięci głównej.

Aigorytm zapisu jednoczesnego (ang. write through).

Przy jej zastosowaniu wszystkie operacje zapisu są prowadzone jednocześnie zarówno do pamięci głównej, jak i do pamięci podręcznej, co zapewnia stałą aktualność danych w pamięci głównej.

Algorytm zapisu opóźnionego {ang. write back),

Aktualizuje się tylko pamięć podręczną (ustawiany jest bit aktualizacji - UPDATE skojarzony z wierszem pamięci podręcznej).

Przed zastąpieniem blok jest wpisywany do pamięci głównej, gdy UPDATE=1.

ok. 15% udział aktualizacji w operacjach dostępu

Spójność

Do możliwych rozwiązań problemu spójności pamięci podręcznej należą:

4 Obserwowanie magistrali z zapisem jednoczesnym

Każdy sterownik pamięci podręcznej monitoruje linie adresowe w celu wykrycia operacji , zapisu do pamięci głównej dokonywanych przez Inne jednostki nadrzędne magistrali. Jeśli inna jednostka nadrzędna wpisuje dane do takiej lokacji w pamięci wspólnej, która ! występuje również w pamięci podręcznej, to sterownik pamięci podręcznej unieważnia dostęp do pamięci podręcznej. Strategia ta jest uzależniona od tego, czy wszystkie sterowniki pamięci podręcznych posługują się metodą zapisu Jednoczesnego.

^ Sprzętowe zapewnianie spójności {ang. hardware transparency).

Wykorzystywane są dodatkowe rozwiązania sprzętowe zapewniające, że wszystkie aktualizacje pamięci głównej dokonywane za pośrednictwem pamięci podręcznej znajdują odzwierciedlenie we wszystkich pamięciach podręcznych. Jeśli jeden procesor modyfikuje słowo w swojej pamięci podręczną), aktualizacja ta jest wprowadzana również do pamięci głównej. Ponadto, wszystkie odpowiednie słowa w pozostałych pamięciach podręcznych są podobnie aktualizowane.

• Pamięć wyłączona ze współpracy z pamięcią podręczną [ang. non-cachab/e memory).

Tylko część pamięci głównej jest wspólna dla więcej niż jednego procesora I jest oznaczana jako wyłączona ze współpracy z pamięcią podręczną.

W takim systemie wszystkie operacje dostępu do tych lokalizacji odbywają się ! bezpośrednio do pamięci głównej.

^ Problem spójności

Występuje w przypadku organizacji magistralowej, w której pamięć główna jest wspóina, a także gdy więcej niż jedno urządzenie (zwykle procesor) ma pamięć podręczną.

-    procesor zmienia zawartość pamięci podręcznej

-    układ we/wy (inny procesor) zmienia zawartość pamięci głównej

Jeśli dane w jednej pamięci podręcznej są zmieniane, to operacja taka powoduje unieważnienie odpowiedniego słowa nie tyiko w pamięci głównej, ale także w innych pamięciach podręcznych (jeśli to słowo w nich akurat występuje).

Jeśli dane są zmieniane w pamięci głównej, to operacja taka powoduje unieważnienie odpowiedniego słowa w pamięciach podręcznych (jeśli to słowo w nich akurat występuje).

Problemy zapisu

Rozmiar bloku

tW przypadku doboru rozmiaru bloku pobieranego do pamięci podręcznej i jednoczesnego zapewnienia zwiększenia liczby trafień należy brać pod uwagę dwa szczególne zjawiska

O Użycie większych bloków powoduje zmniejszenie liczby bloków, które mieszczą się w pamięd podręcznej. Ponieważ każde wpisanie bloku powoduje usunięcie starej zawartości pamięci podręcznej, mała liczba bloków sprawia, że dane są usuwane niedługo po ich pobraniu.

| O Gdy blok staje się większy, każde dodatkowe słowo jest dalsze od potrzebnego słowa, staje się więc mniej prawdopodobne jego użycie w niedalekiej przyszłości.

■jjfr Związek między rozmiarem bloku a współczynnikiem trafień jest złożony i uzależniony od stopnia lokalnośd określonego programu.

4 .. 8 słów - blisko optimum

Topologio pamięci

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")

Ukł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.

Liczba pamięci podręcznych

Kiedy wprowadzono pamięci podręczne, typowy system miał pojedynczą pamięć podręczną. Ostatnio stało się normą wykorzystywanie wielu pamięci podręcznych. Dwoma aspektami tego zagadnienia projektowego są: liczba poziomów pamięci oraz podział lub scalanie pamięci podręcznych.

O W miarę wzrostu gęstości upakowania układów logicznych stało się możliwe dysponowanie pamięcią podręczną wewnątrz tego samego mikroukładu co procesor: określamy to mianem pamięci podręcznej w procesorze (ang. on-chip cache).

O Większość współczesnych projektów zawiera zarówno pamięć podręczną wewnątrzprocesorowa, jak i zewnętrzną. Wynikająca stąd organizacja jest znana jako dwupoziomowa pamięć podręczna, przy czym pamięć wewnętrzna jest oznaczana jako poziom 1 (LI), a zewnętrzna jako poziom 2 (L2).

O Jeśli zastosowana jest pamięć podręczna L2 SRAM, to często możliwe jest szybkie pobranie brakującej informacji. Jeśli pamięć SRAM jest dostatecznie szybka, aby dostosować się do szybkości magistrali, to możliwy jest dostęp do danych za pomocą transakcji o zerowym czasie oczekiwania, co stanowi najszybszy rodzaj transferów magistralowych.

Na ogół obecność L2 poprawia wydajność (zależy od współczynników trafień w LI i L2)

Właściwości pamięci podręcznej

Liczba pamięci podręcznych

CPU

LI

L2

(L3)

Main mem

Struktura logiczna PP

Gdy po raz pierwszy wprowadzono wewnątrzprocesorową pamięć podręczną, w wielu projektach zawierających pojedynczą pamięć podręczną wykorzystywano ją zarówno do przechowywania danych, jak i rozkazów. Obecnie stało się powszechne dzielenie pamięci podręcznej na dwie: jedną przeznaczoną na rozkazy, drugą zaś na dane.

i > Zalety pamięci jednolitej:

Dla danego rozmiaru pamięci podręcznej pamięć jednolita wyróżnia się większym współczynnikiem trafień niż pamięć podzielona, ponieważ automatycznie równoważy ona pobieranie rozkazów z pobieraniem danych. To znaczy, jeśli struktura rozkazów przewiduje o wiele więcej pobrań rozkazów niż danych, pamięć podręczna będzie wykazywała tendencję do wypełniania się rozkazami. Jeżeli natomiast wymagane jest częstsze pobieranie danych, pamięć ta będzie się wypełniała danymi. Upraszcza się układ procesora.

O Zalety pamięci podzielonej:

Kluczową zaletą podzielonej pamięci podręcznej jest to, że eliminowana jest rywalizacja o pamięć podręczną między procesorem rozkazów a jednostką wykonującą. Jest to ważne w każdym rozwiązaniu wykorzystującym potokowe przetwarzanie rozkazów (p. superskalarne).

■) ( Aby określić średni czas dostępu do obiektu, musimy rozważyć nie tylko szybkości obu poziomów pamięci, ale także prawdopodobieństwo, że poszukiwane dane mogą być znalezione w pamięci Ml. Prawdopodobieństwo to iest znane iako współczynnik trafień.

^ Średni czas dostępuj

T_s=HxT_t +(1-H)x(T₁+T₂)=T_] +(l-H)xT₂

gdzie:

T, - średni (systemowy) czas dostępu,

T, - czas dostępu do pamięci Ml (np. pamięci podręcznej, w tym dyskowej),

T₂ - czas dostępu do pamięci M2 (np. pamięci głównej, pamięci dyskowej),

H - współczynnik trafień (ułamek czasu, w którym odniesienia są odnajdywane w pamięci Ml).

Współczynnik trafień

•Jf- Pamięć wyższego poziomu (Ml) jest mniejsza, szybsza i droższa (na bit) niż pamięć niższego poziomu (M2). Pamięć Ml jest wykorzystywana do tymczasowego przechowywania części zawartości większej pamięci M2. Gdy następuje odniesienie do pamięci, przeprowadzana jest próba znalezienia poszukiwanych danych w pamięci Ml. Jeśli się ona powiedzie, wykonywany jest szybki dostęp. Jeśli nie, to odpowiedni blok pamięci M2 jest kopiowany do pamięci Ml, a dostęp następuje za pośrednictwem pamięci Ml. Ze względu na lokalność, jeśli blok został już doprowadzony do pamięci Ml, powinno nastąpić wiele odniesień do tego bloku, co powoduje przyspieszenie obsługi.

PP w systemach wieloprocesorowych

Problem spójności danych. Musi istnieć taki mechanizm zapisu, który pozwala na uaktualnianie wszystkich kopii zawartości tej samej komórki pamięci głównej.

Rozwiązania programowe

•    Analiza programów w fazie kompilacji i określenie, które dane są narażone na niespójność.

•    System operacyjny i sam program zapobiega kierowaniu takich danych do pamięci podręcznych.

•    Każdy procesor musi je odczytywać zawsze z pamięci głównej i tam zapisywać ich zmiany.

•    Rozwiązanie bardzo nieefektywne pod względem czasu dostępu.

•    Bardziej zaawansowane sposoby polegają na analizie, w którym momencie dane wspólne procesorów mogą być niespójne i tylko wtedy nie są kierowane do cache.

•    W praktyce, część pamięci głównej definiuje się jako wspólną (tak zwaną non-cachable memory), która nie może być kopiowana do pamięci podręcznych. Jeśli dane są narażone na niespójność zapisuje się je właśnie w tym obszarze pamięci głównej systemu.

PP w systemach wialoprocasorowych

Rozwiązania sprzętowe

•    Protokoły katalogowe

-    wprowadzenie tak zwanego katalogu pamięci i specjalnego sterownika, który zapisuje w nim aktualne informacje o kopiach danych przechowywanych przez różne procesory. Sterownik ma możliwość komunikacji ze wszystkimi układami, w wypadku zmiany zawartości pamięci, wysyła do nich rozkazy aktualizacji.

-    Sterownik centralny może zostać przeciążony = zwolnienie pracy systemu.

•    Protokoły podglądania

-    odpowiedzialność za utrzymanie spójności danych rozkłada się na wszystkie sterowniki pamięci podręcznych. Muszą one kontrolować co się dzieje na magistrali komunikacyjnej (podglądać) - w wypadku zmiany danych, których kopia jest w ich cache odpowiednio ją uaktualniać.

-    Muszą tu także być podjęte odpowiednie środki, które zapobiegają przeciążeniu magistrali.

Rozwiązania protokołów podglądania

•    Zapis z unieważnieniem

-    wszystkie dane z pamięci wspólnej są dostępne dla procesorów do odczytu - mogą je kopiować do swoich pamięci podręcznych cache. Jednak jeśli któryś chce zmienić zawartość pamięci, wysyła specjalne powiadomienie - unieważnia wszystkie kopie zmienianego bloku danych pobrane przez inne procesory. Procesor zapisujący musi "dostać" blok wspólnej pamięci na wyłączność na czas jego zmiany. Dopiero po zakończeniu zapisu wszystkie inne procesory mogą z niego korzystać ale teraz odczytają jego aktualną zawartość z pamięci głównej. Przy odwoływaniu się do niego układ cache nie wygeneruje sygnału trafienia, gdyż blok jest już unieważniony w wyniku zmodyfikowania przez inny procesor (status wiersza).

•    Zapis z aktualizacja

-    gdy jeden procesor zmienia jakiś blok pamięci, zostaje on dostarczony do wszystkich innych układów, dzięki czemu pamięci podręczne zawierające jego kopię mogą ją uaktualnić.

Protokół ME8I

•    Trafienie odczytu (RH) to procesor pobiera potrzebne mu dane bez zmiany ich aktualnego statusu niezależnie czy w jego pamięci podręcznej są one w stanie zmodyfikowane, wspólne lub wyłączne.

•    Trafienie zapisu (WH):

-    (Wspólny) procesor sygnalizuje zamiar modyfikacji bloku wspólnego. Wszystkie inne procesory posiadające jego kopię unieważniają ją. Po tej operacji blok jest w stanie wyłącznym - jego kopia jest ważna tylko w cache procesora inicjującego zapis. Dokonuje zapisu i ustawia status bloku na zmodyfikowany.

-    (Wyłączny) procesor inicjujący ma już wyłączną kontrolę nad blokiem więc dokonuje jego modyfikacji.

-    (Zmodyfikowany) procesor inicjujący ma ciągle wyłączną kontrolę nad blokiem i kolejny raz go aktualizuje.

Protokół unieważniania zapisu (MESI: modified, exclusive, shared, invalid)

Bity MESI określają Jeden z czterech możliwych statusów odpowiadającego wiersza:

-    Zmodyfikowany (Modified) - dane w wierszu zostały zmodyfikowane (różnią się od odpowiednika w RAM) i są dostępne tylko w tej pamięci podręcznej.

-    Wyłączny (Exclusive) ■ dane w wierszu są takie same jak w RAM i nie występują w innych pamięciach cache.

-    Wspólny (Shared) - dane w wierszu są takie same jak w RAM i mogą występować w innych pamięciach cache.

-    Nieważny (Invalid) - wierszu nie zawiera ważnych danych

RH - trafienie odczytu

RMS - chybienie odczytu, wspóiny

RME - chybienie odczytu, wyłączny

WH - trafienie zapisu

WM - chybienie zapisu

SHR - śledź trafienie odczytu

SHW - śledź trafienie zapisu lub

odczytu z zamiarem modyfikaęji

Protokół MESI

• Chybienie odczytu (RM) - procesor inicjuje odczyt bloku z pamięci głównej. Umieszcza sygnał na magistrali alarmujący wszystkie pozostałe procesory, żeby śledziły tą operację. Możliwe są następujące sytuacje:

-    (ma wyłączny) jeden z pozostałych procesorów ma kopię tego bloku danych w wierszu o statusie wyłączny. Sygnalizuje, że dysponuje tym blokiem, po czym zmienia status swojej kopii bloku na wspólny. Procesor inicjujący odczyt umieszcza blok danych w swojej pamięci podręcznej (w wolnej linijce) i nadaje linijce status wspólny (RME).

-    (ma wspólny) jeden (wiele) procesorów sygnalizuje, że ma kopię bloku w stanie wspólnym w swojej cache. Wtedy procesor inkjujący też umieszcza blok w wolnym wierszu swojej cache i nadaje mu status wspólny (RMS).

-    (ma zmodyfikowany) jeden z pozostałych procesorów ma zmodyfikowaną kopię bloku danych. Wtedy wysyła sygnał anulujący próbę odczytu danych z pamięci głównej, przejmuje sterowanie magistralą i zapisuje w niej swoją kopię bloku danych. Zmienia status zapisywanego wiersza na wspólny (SHR). Procesor inicjujący ponowi próbę odczytu; - odczyta aktualną kopię danych z pamięci głównej, nadając jej status wspóiny.

-    (nie ma) żaden z procesorów nie sygnalizuje posiadania kopii bloku danych w swojej cache; procesor inicjujący odczytuje potrzebne mu dane umieszcza w swoim wierszu cache nadając jej status wyłączny.

Protokół ME8I

• Chybienie zapisu (WM) następuje gdy procesor chce zapisać dane w bloku określonym adresie, a nie znajduje się on w jego cache. Wtedy inicjowany jest odczyt bloku bez zamiaru modyfikacji. Możliwe są następujące sytuacje:

-    (ma zmodyfikowany) jedna z pozostałych pamięci ma kopię tego bloku w wierszu o statusie zmodyfikowany. W takiej sytuacji procesor inicjujący oddaje sterowanie magistralą. Procesor posiadający zmodyfikowaną kopię danych zapisuje ją do pamięci głównej, jednocześnie ustawia ich status odpowiedniego wiersza w swojej cache na nieważny, bo procesor inicjujący dokona za chwilę modyfikacji bloku (SHW). Następnie procesor inicjujący ponawia odczyt bloku, który jest już ważny wyłącznie w jego pamięci podręcznej i może zostać zmodyfikowany.

-    (nie ma) Jeśli żadna inna pamięć podręczna nie ma zmodyfikowanej kopii bloku. Procesor inicjujący odczytuje blok i zapisuje go w swojej cache, po czym modyfikuje. W tym czasie jeśli inne pamięci mają blok w statusie wyłączny lub wspólny zmieniają jego stan na nieważny (SHW).

1

•    bezpośrednie (direct mapped) - rozłącznym podzbiorom bloków pamięci głównej przypisano unikatowe wiersze pamięci w podręcznej

-    najkrótszy czas kojarzenia - rekord indeksujący adresu (cache index)

-    najmniejszy współczynnik trafień

-    chybienia wskutek konfliktu odwzorowania (conflict miss) - migotanie

•    całkowicie skojarzeniowe (fully associative) - każdy blok pamięci głównej może by skopiowany do dowolnego wiersza pamięci podręcznej

-    wymiana wiersza konieczna tylko wtedy, gdy wszystkie wiersze są użyte największy współczynnik trafień, brak migotania (thrashing)

2

   wielodrożne (set-associative) - rozłącznym podzbiorom bloków pamięci głównej przypisano rozłączne podzbiory (sekcje) wierszy w pamięci podręcznej (bezpośrednie odwzorowanie bloków, pełne skojarzenie w podzbiorze)

-    czas dostępu dłuższy niż dla pamięci z odwzorowaniem bezpośrednim

-    niewielkie migotanie, duży współczynnik trafień

-    konflikt odwzorowania maleje ze wzrostem liczby wierszy w sekcji