wykl04c

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:

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.

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


BI #1

Długość bloku -(ATstow)

a)    Pamięć główna

b)    Pamięć podręczna (cache)


Struktura pamięci podręcznej


BI #7
BI #M

.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ęć 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=2n/K bloków.


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

Zagadnienia charakterystyczne dla pamięci podręcznych

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

O najrzadziej używany (LFU)

O swobodny


(• Pojemność pamięci Rodzaj odwzorowania:

•    bezpośrednie

•    skojarzeniowe

•    sekwencyjno - skojarzeniowe


Algorytm wymiany


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

•    jednoczesny

•    opóźniony


•J (■ Rozmiar bloku ^ £. Liczba pamięci podręcznych

•    jedno- lub dwupoziomowa

•    jednolita lub rozszczepiona


Pamięć podręczna - działanie



ładowanie blolni z pamięci ęłbwtwj do wierna pamięci podręcznej


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

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 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 ** 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 aktualnie zajmuje wiersz pamięci podręcznej.


Adres

pamięci


0>) Numer


*..........

Blok(jritow)


-

—-*-


- Długość bloku -(KMw)


M'

Blok


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


a)    Pamięć główna

b)    Pamięć podręczna (cache)




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

Adm futmęci głównej3

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

w 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


Cadit

Main Memorj


?



Odwzorowanie bezpośrednie - cz.lll



Przykład:

O Pojemność cache = 64 KB. Bloki po 4 bajty.
Organizacja cache:
214 (16K) wierszy po 4 bajty każdy.
O Pojemność pamięci głównej 16 MB (16M x 1 bajt) 24-bitowy adres (224 = 16 M).

U

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

Znacz- Wimz*»łowo Dane


OB - przykład odczytu


• Adresy 24-bitowe, 16M x bajt


0008

0004

0000


000#

0004

0000


000#

0004

0000


#7654321

13579246


Czternastobitowy 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 przechowywanym w tym wierszu, to 2-bitowy numer słowa służy do wyboru jednego z 4 bajtów w tym wierszu


Znacz- Dane


i......01


---------00


87654321 11235813 13579246


Numer

wicnrjk

3FFF

JFFE


0002

0001

0000


1 —    32 bif) —► {14 bitów t

8 (mów

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


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


• Pobierane bajty:

(tagx216+wierszx22)+0,

(tagx216+wierszx22)+l,


(tagx216+wierszx22)+3,

Znacmik


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

Adres pamięci główne)1


M m= 16K=214


i-=y modulo 214.


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


Wiersz pamięci podręcznej (teoria)


Wiersz pamięci podręcznej (przykład)


Przypisane adresy początkowe (teoria)

0, 4xm.....

4x(2s -m)

4, 4x(m+1).....

4x( 2s-m+1)


000000, 000001

000002, 000003


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(2s-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.

3 F 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

PFFFFC

FPPFtt

Ffłm


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

1633A0

163)90

1(3391

000006

000004

oooooo

24682468

-“ł

11223344

......t !

33333333

I 1 1 l |

* *

1 1 * ! 1 i * i i

i »

Zraemtk

One

FTFFTC

24652464

! 1 r —•

oooooo

12345(7

FFFFF4

33333333

! ' '

17(34321

K339C

87(54321

FFfTF?

11223344

1

■4 | 1 1

22 bity

-*-32 bity —

1

1

1

1

1

podryent

1

1

.........J

3FFF

3FFE

3PFD

— 32b«ty—^ P>my ttówn U MB


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.


Adres pamięci jkwmij *


Izmzr Sekąnkrwc Dmc


OSS - przykład odczytu


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


Zho- Dae

Numer

Zucz

Due

rnk

akcji

*

- Ó5T

12345674

3FFF

IFF

24642464

■ ipr

11223344

3FTC

- 090

17654321

0002

001

11235813

0001

. 090

13579246

0000

001

77777777

nSS

—-32birr-^

PtBlfćpodręczMUKfłów


87454321

11579246


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

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

nk    Sekcji    Słowo


Aórt» ptfwęa głównej -


-w— 32 bity-w-Paafft głkwoa 16 MB


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


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.

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 = 2d sekcji, a s bitów (znacznik + nr sekcji) określa jeden z 2* bloków pamięci głównej.


EE

V


Carhr

lu^ IXua

Wybór

sekcji

nz

10

i_

11

: (

-L

£

.


Main Mentor)


-M



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. least frequentty 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.

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

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.

Problemy zapisu

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



procwor

CPU

c=:

p«ai'ć

podręczna

cache

c=s

pMlifC

op«rac]f|ni

RAM



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

f


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.


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:

Ts=HxTt    + (\-H)x(T]+T2)=

gdzie:

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

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

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

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


Wyszukiwarka

Podobne podstrony:
wykl04c Wykład 4Pamięć podręczna Lokalność odniesień Zwykle kod i dane nie są „porozrzucane"
wykl04 Wykład 4Pamięć podręczna Lokalność odniesień Zwykle kod i dane nie są „porozrzucane"
wykl04 Wykład 4Pamięć podręczna Lokalność odniesień Zwykle kod i dane nie są „porozrzucane"
Cel ćwiczeń: -Tożsamy z celami uwzględnionymi w celach wykładu. Proponowane podręczniki: •
Cel ćwiczeń: -Tożsamy z celami uwzględnionymi w celach wykładu. Proponowane podręczniki: •
e.    Wykładowca prosi studentów, aby odnieśli znane im już pojęcia do kultury j
INFORMACJA LOKALNA O ZAWODZIEFILOLOG ANGIELSKI -kod 233008 Filolog angielski (kod zawodu-233008) to
Wykład 73. Kwasy nukleinowe - budowa i funkcje 3.3. Kod
Wykład 8 (16) ZMIANY SKÓRNE W PRZEWLEKŁEJ POSTACI GVHB 7 / / Objawy kliniczne są dosyć znamienne i
-    Wykłady w ogólnej liczbie 15 godzin, zwykle 1 godzinę zegarową 1 x w tygodniu
Wykłady w Korpusie Morskim rozpoczynały się zwykle w połowie września, gdy kadeci starszych kursów p
Wykłady z położnictwa Podręcznik dla studentów położnictwa
Wykłady z położnictwa Podręcznik dla studentów położnictwa Adoau Mapłnlr nu Lo*lk a-medJca
img197 197 Utrzymanie odniesionej szybkości transmisji na nie zmienionym poziomie 2lbit/s/Hz] można
3TEMAT NUMERU 9 lutego 2012 Gazeta LokalnaSzok! Zahil konkubinę Will ■ V f I 1 I I   &nb
Rapid Prototyping - Podręcznik Minos (powstaje siatka wielokątna, której powierzchnie są płaskie); o

więcej podobnych podstron