wykl04c

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 lokalnoś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.

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

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

Pamięć podręczna (cache)

•    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 - 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).

Ą £ 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

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

(*) Adrc* pamięci

Struktura pamięci podręcznej

0>) f

BI #1

BI #7

BI #M

■ Długość bloku-(AT słów)

a)    Pamięć główna

b)    Pamięć podręczna (cache)

jC-i

jąu*o*

iłowa"*"

.jfc. Pamięć podręczna zawiera C ^T 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ęć ołó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.

Zagadnienia charakterystyczne dla pamięci podręcznych

-J f- Pojemność pamięci ■J (• Rodzaj odwzorowania:

i

1

bezpośrednie

skojarzeniowe

sekwencyjno - skojarzeniowe

Algorytm wymiany

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

• najrzadziej używany (LFU)

O swobodny

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

jednoczesny

opóźniony

-)(- Rozmiar bloku ^ £ Liczba pamięci podręcznych

• jedno- lub dwupoziomowa t jednolita lub rozszczepiona

Pamięć podręczna - działanie

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

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

N»	Doaqp do pamięci głównej w oelo znalezienia bloku zawierającego RA
		1
	Przydzielenie wiersza pamięci podręczny blokowi z pamięci jttwoej

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 zawierają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 J Rodzaj odwzorowania:

bezpośrednie skojarzeniowe

sekwencyjno - skojarzeniowe

Funkcja odwzorowania

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

<»>

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

blok pamięci głównej o>) Numer    I aktualnie zajmuje wiersz

pamięci podręcznej.

2*-l

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

Odwzorowanie bezpośrednie - cz.ll

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

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

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

Wiera    Słomo

Adm ptraieci jłemnej *

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

Odwzorowanie bezpośrednie - cz.l

#• Najprostsza metoda odwzorowania = odwzorowanie bezpośrednie, polega na odwzorowywaniu każdego bloku pamięci głównej na tylko

jeden wiersz pamięci podręcznej.

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

Cache

_!SL

WUlil)

i _ _

Main Memory

	wo
	w;
	w:
	W!

?

f

Odwzorowanie bezpośrednie - cz.lll

Przykład:

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

4

Organizacja cache:

2¹⁴ (16K) wierszy po 4 bajty każdy.

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

JJ-

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

Znacz* Wicr*z**łowo Dane

OB - przykład odczytu

Adresy 24-bitowe, 16M x bajt

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

Numer

wiersza

1FFF

3FFE

000*

0004

0000

# Jeśli 8-bitowy znacznik jest zgodny ze znacznikiem aktualnie przechowywanym w tym wierszu, to 2-bitowy numer słowa służy do wyboru jednego z 4 bajtów w tym wierszu

------- 00

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

87M4J21 I1275813 IJ5?<)246

0002

0001

0000

000*

0004

0000

000*

0004

0000

*7654321

13570246

K bnóu

Pamięć podręczna 16 K słów

• Pobierane bajty:

(tagx2¹⁶+wierszx2²)+0,

(tagx2¹⁶+wierszx2²)+l,

(tagx2¹⁸+wierszx2²)+3,

Znacauk    Wiciu

—— 32 bity—— Pamięć główna 16 MB

Adres pamięci |townq»

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

000000, 000001 000002, 000003

Wiersz pamięci podręcznej (teoria)	Wiersz pamięci podręcznej (przykład)	Przypisane adresy początkowe (teoria)
r\	n	0, 4xm.....
U	U	4x(2^s -m)
1	1	4, 4x(m+1),..., 4x( 2^s-m+1)

H _m= 16K=2¹⁴

i=jmoduio 2¹⁴.

Przypisane adresy początkowe bloków pamięci głównej (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 skojarzeniowe

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.

pmrc

nwn

FJWF4

Zna- 3«fcy*dowo Omc

znacznika i 2-bitowego numeru bajtu.

Due

1633A0

16339C

163398

000008

000004

000000

24612461
11223344
33333333	! i i ! • ^1
* #	^1 ■ * • ^1 ■ 'iii		Dat
		FTFFTC	24682461
	! i p—.	000000	1234567
	f —	FFFFF4	33333333
	! ' '
17654321	■"!
	^1—1—i—	I6339C	87654321
	— * T —*	FFFFJ	11223344
	1 * 1 1 1	22 bity	-*-32b«y —
	1 1 1 1	PimifC podrycui
■I2WW>	1 1

3FFF

3FH

3PFD

— 32 bity —— P»mW Jtówii li MB

1745021

13579244

OS - przykład odczytu

• Adres pamięci głównej składa się z 22-bitowego

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.

AOra p«mi«c gtownej •

OSS - przykład odczytu

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

24682468 11223344
	> Zmo* Dsae Nuroer Zmcz- Dor | tak Młqi ak
	,---1, ooi U34»« 3FPF 1FT 2402441 " 1 - IFT 11223344 3FFE

17454321

11235813

13579246

Pinifć podręczia U Kitów

Adrtefwmęa głównej *

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"

Sekcji    Słowo

-w— 32 bity —w-PiaifłfttwMltMB

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

t

?

Odwzorowywanie: m = v x k; i = j modulo v gdzie:

i - numer sekcji pamięci 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.

Porównanie

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

•    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

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

Algorytm wymiany

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

najrzadziej używany (LFU) swobodny

Algorytmy wymiany

O Algorytm „najmniej ostatnio używany" (ang. least-recently used - LRU).

Algorytm określa, że 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.

O Algorytm „pierwszy wchodzi - pierwszy wychodzi" {ang. fistin - firstout-

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. /east frequent/y used - LFU).

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

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

Algorytmy wymiany

r

-jff-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

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

Algorytm 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żą:

^ Obserwowanie magistrali z zapisem jednoczesnym

Każdy sterownik pamięci podręcznej monitoruje linie adresowe w celu wykrycia operacji zapisu do pamięci główne 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.

I Sprzętowe zapewnianie spójności {ang. hardware transparenty).

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ęcznej, 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).

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

Problemy zapisu

W Problem spójności

Występuje w przypadku organizacji magistralowej, w której pamięć główna jest wspólna, 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 tylko 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).

Rozmiar bloku

^ W 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ęci 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.

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

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

4 .. 8 słów - blisko optimum

Topologie pamięci

procator

CPU

OptUCfJlM

•y MM

p*™«‘

procwor CPU

p«ai'ć porlrtczna cache

c=:

0))«t,|na MU

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

(f- 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.

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

Współczynnik trafień

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

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 jako współczynnik trafień.

-jff- Średni czas dostępu:

T_s=HxT_l+{\-H)x(T_l+T₂)=T_l+(\-H)xT₂

gdzie:

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

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

T_z * 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).

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 wieloprocesorowych

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.

PP w systemach wieloprocesorowych

Rozwiązania protokołów podglądania

•    Zaois 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 aktualizacją

-    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ół MESI

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

PP w systemach wieloprocesorowych

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ólny

RME - chybienie odczytu, wyłączny

WH - trafienie zapisu

WM - chybienie zapisu

SHR - śledź trafienie odczytu

SHW - śledź trafienie zapisu lub

odczytu z zamiarem modyfikacji

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 inicjują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ólny.

-    (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ół MESI

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