Kieszenie jako warstwa hierarchii
pami ci
Architektura systemów
komputerowych
1
Plan wyk adu
Zasada dzia ania kieszeni
Kiesze pe noasocjacyjna
Kiesze adresowana bezpo rednio
Kiesze zbiorowo  asocjacyjna
Model wydajno ci kieszeni
Reakcja kieszeni na operacje zapisu danych
Systemy kieszeni  inkluzywne i wy czne
Spójno hierarchii pami ci
2
Kieszenie  podstawy
Warstwa hierarchii pami ci umieszczona pomi dzy
rejestrami i pami ci operacyjn
Niewidoczna w u ytkowym modelu programowym
 wspó cze nie oprogramowanie u ytkowe mo e mie
ograniczon kontrole nad prac kieszeni
Stanowi bufor dla pami ci operacyjnej
Niezb dna we wspó czesnych komputerach
z powodu znacz cej dysproporcji pomi dzy
wydajno ci procesora i pami ci operacyjnej
Pierwszy raz wprowadzona w komputerach serii IBM
S/370 oko o 1968 roku
3
Kiesze
adres
pami
procesor
kiesze
operacyjna
dane
4
Dzia anie kieszeni
Przy ka dym odwo aniu procesora do pami ci nast puje sprawdzenie,
czy dana spod okre lonego adresu znajduje si w kieszeni
Brak danej w kieszeni  chybienie kieszeni (cache miss)
 dana zostaje odczytana z pami ci i przestana do procesora
  po drodze dana wraz z jej adresem jest zapisywana do kieszeni
je li kiesze by a pe na  trzeba z niej co usun
 przy nast pnym odwo aniu dana b dzie ju w kieszeni
Odnalezienie danej w kieszeni  trafienie kieszeni (cache hit)
 dana zostaje odczytana z kieszeni
 odwo anie do pami ci operacyjnej jest zb dne
 czas odwo ania do danej w kieszeni jest znacznie krótszy, ni czas
dost pu do pami ci operacyjnej
5
Zasada lokalno ci odwo
W ograniczonym odcinku
p(A) czasu odwo ania procesora
do pami ci s skupione na
niewielkim fragmencie
przestrzeni adresowej
Wykres przedstawia
orientacyjny rozk ad
prawdopodobie stwa odwo
do poszczególnych adresów
w czasie od t0 do
t0 + t, przy za eniu, e
w chwili t0 nast pi o odwo anie
do A0
A
A0
6
Wnioski z zasady lokalno ci
Zakres odwo jest ograniczony
 zakres adresów, do których odwo uje si procesor
w ograniczonym odcinku czasu nazywa si zbiorem roboczym
 stosunkowo niewielki bufor mo e przechowywa znacz cz
obiektów, do których w danym odcinku czasu odwo uje si
procesor
Odwo ania s na ogó powtarzane
 nale y zapami tywa dane, do których procesor wykonuje dost p,
bo zapewne wkrótce b dzie znów ich potrzebowa
Bardzo prawdopodobne s kolejne odwo ania do kolejnych
adresów
 przy nape nianiu bufora wskutek dost pu ze strony procesora
warto pobra z pami ci kilka kolejnych komórek  na zapas
7
Kiesze pe noasocjacyjna
Najbardziej intuicyjny typ kieszeni
Trudna i niezbyt efektywna w implementacji
 ma e pojemno ci
 obecnie nie stosowana
Zbudowana na bazie pami ci asocjacyjnej
 pami asocjacyjna nie ma adresów
 dost p do danej nast puje poprzez porównanie danej w kieszeni
z wzorcem dostarczonym z zewn trz
 pami odpowiada poprzez wystawienie danych zgodnych z wzorcem lub
informacji, e takich danych nie ma w pami ci
 dzia anie mo na wyt umaczy na przyk adzie ksi ki telefonicznej:
szukamy znanego nazwiska
odczytujemy numer telefonu
nie zwracamy uwagi na po enie nazwiska w ksi ce (nr strony, kolumn )
8
Kiesze pe noasocjacyjna  model
adres z procesora
znaczniki
dane
(adresy)
0x1234 0xABCD
dane
9
Kiesze pe noasocjacyjna 
charakterystyka
W ka dej komórce kieszeni mo e by przechowywana dana spod
dowolnego adresu
 kiesze mo e równocze nie przechowywa dane spod dowolnych
adresów  du a elastyczno w porównaniu z innymi
architekturami
Wyznaczanie linii do zast powania  LRU lub losowe
 LRU  algorytm kosztowny w implementacji sprz towej
 algorytm losowy  daje zró nicowane wyniki
Ka da komórka wyposa ona w komparator znacznika
 trudna implementacja
 niewielka pojemno (do ok. 16 KB), ograniczenie szybko ci dost pu
Je li rozmiar zbioru roboczego przekracza pojemno kieszeni 
wszystkie odwo ania b ko czy y si chybieniami
10
Kiesze  konstrukcja
Dane s przechowywane w kieszeni nie w postaci
pojedynczych s ów czy bajtów, lecz bloków, zazwyczaj
o d ugo ci 4x wi kszej od rozmiaru s owa pami ci
 bloki te s wyrównane naturalnie  adres pierwszego bajtu jest
podzielny przez d ugo bloku
Element kieszeni zawieraj cy blok danych i zwi zane
z nim znaczniki (w tym znacznik adresu) jest nazywany lini
Najmniej znacz ca cz adresu s y do wyboru bajtu lub
owa z linii
 kolejne, bity adresu s ywane do stwierdzenia, czy poszukiwana
dana znajduje si w kieszeni
11
Kiesze adresowana bezpo rednio
Zbudowana na bazie zwyk ej, szybkiej pami ci RAM i jednego
komparatora
 bardzo prosta w realizacji, szybka i wydajna
 dzi ki prostocie budowy mo e mie stosunkowo du pojemno
Proste, lecz zupe nie nieintuicyjne dzia anie
 najmniej znacz ce bity adresu s do wyboru bajtu z linii
 rodkowa mniej znacz ca cz adresu procesora s y jako adres
pami ci RAM; na jej podstawie w ka dym cyklu dost pu jest wybierana
pojedyncza linia
 ka da linia zawiera znacznik adresu i dane
 pole znacznika adresu zawiera bardziej znacz cz adresu danej
zapami tanej w polu danych  jest ono porównywane z najbardziej
znacz cz ci adresu wystawionego przez procesor
12
Kiesze adresowana bezpo rednio
adres z procesora
0x1234
0x3
0x12
znaczniki
dane
(adresy)
0x12 Wybrana linia - 16 bajtów
0x4
wybór cz ci s owa
komparator
dane
13
Kiesze adresowana bezpo rednio 
dzia anie
W ka dym cyklu nast puje wybór jednej linii, zaadresowanej
przez mniej znacz cz adresu
Kiesze stwierdza trafienie, je li znacznik adresu wybranej linii
jest równy najbardziej znacz cej cz ci adresu wystawionego
przez procesor
W przypadku trafienia dane s transmitowane z kieszeni do
procesora
W przypadku chybienia wymianie podlega wybrana linia
 w polu znacznika zostaje zapisana najbardziej znacz ca cz
adresu
 w polu danych zostaj zapami tane dane odczytane z pami ci
14
Kiesze adresowana bezpo rednio 
charakterystyka
Niskie koszty, du a pojemno , wysoka wydajno
Algorytm zast powania linii wymuszony przez budow kieszeni
 dane spod okre lonego adresu mog znale si wy cznie w jednej,
z góry okre lonej linii kieszeni
 w kieszeni nie mo na zapami ta dwóch danych, których rodkowe cz ci
adresu s identyczne
w praktyce nie jest to bardzo cz sty przypadek, ale niekiedy si zdarza
Przy ci ym zakresie adresów zbioru roboczego (p tla
programu, tablica) kiesze przyspiesza odwo ania do pami ci,
dopóki zbiór roboczy jest mniejszy ni 2x pojemno kieszeni
 lepiej ni w przypadku kieszeni pe noasocjacyjnej
15
Kiesze zbiorowo-asocjacyjna
Powstaje przez po czenie pewnej liczby kieszeni bezpo rednio
adresowanych (zwanych blokami)
Dana spod okre lonego adresu mo e by przechowywana w tylu
miejscach, ile jest bloków
 w ka dym cyklu dost pu nast puje poszukiwanie danej w pojedynczej linii
ka dego z bloków
 zestaw linii wybieranych w ka dym cyklu jest nazywany zbiorem
 zbiór zachowuje si jak ma a kiesze pe noasocjacyjna
Liczba bloków jest zwana stopniem asocjacyjno ci kieszeni
 ywa si równie okre le  kiesze dwudro na lub  czterodro na
Kiesze zbiorowo-asocjacyjna mo e by rozpatrywana równie
jako z enie pewnej liczby kieszeni pe no asocjacyjnych
16
Kiesze zbiorowo-asocjacyjna
0x1234 adres z procesora
znaczniki znaczniki znaczniki
dane dane dane
(adresy) (adresy) (adresy)
0x3
0x30 0x12 0x11
=? =? =?
0x12
0x4
dane
17
Kiesze zbiorowo-asocjacyjna 
dzia anie
Budowa kieszeni musi gwarantowa , e dana spod
okre lonego adresu mo e zosta zapisana tylko
w jednym bloku
W przypadku chybienia nale y wyznaczy ze zbioru jedn lini
do zast pienia
 mo na u algorytmu LRU, który przy ma ej liczbie linii daje si
zrealizowa w sprz cie
 przy wi kszej liczbie linii  algorytm pseudo LRU lub losowy
Charakterystyka ogólnie podobna do kieszeni bezpo rednio
adresowanej, ale z eliminacj przypadku
z pokrywaj cymi si rodkowymi cz ciami adresu
 mniejsza wra liwo kieszeni na nak adanie si adresów
danych  podobnie jak w przypadku kieszeni pe noasocjacyjnej
18
Rodzaje kieszeni  podsumowanie
Najcz ciej spotykanym typem kieszeni s kieszenie zbiorowo-
asocjacyjne
 charakterystyka lepsza od bezpo rednio adresowanych przy
niewielkim wzro cie komplikacji
 tam, gdzie jest krytyczny czas dost pu  u ywa si kieszeni
o ma ej asocjacyjno ci
Przy bardzo ostrych wymaganiach na szybko ywa si
kieszeni bezpo rednio adresowanych lub dwudro nych
zbiorowo-asocjacyjnych
Kieszenie pe noasocjacyjne nie s stosowane do
przechowywania danych i kodu
 niekiedy znajduj one zastosowanie w innych miejscach
komputera
19
Wspó czynnik trafie (hit ratio)
Definiowany jako stosunek liczby trafie do ca kowitej liczby odwo
w badanym przedziale czasu:
ncache
h
ntotal
Zale y od:
 pojemno ci kieszeni
 organizacji kieszeni i wynikaj cego z niej algorytmu wymiany
 wykonywanego programu
dla ka dej kieszeni mo na poda przyk ad programu o h = 0 i innego,
o h bliskim 1
Wiarygodny pomiar i porównanie wspó czynnika trafie wymaga
uzgodnienia budowy testu
 zwykle u ywa si serii programów o zró nicowanej charakterystyce
odwo , np. kompilatora, edytora, bazy danych, programu
obliczeniowego
20
Wspó czynnik trafie
Wykres przedstawia orientacyjny
przebieg zale no ci wspó czynnika
trafie od pojemno ci kieszeni
W zakresie warto ci od 0 do 0,9
h zale y g ównie od pojemno ci
kieszeni
 warto 0,9 jest osi gana przy
pojemno ci kieszeni rz du
8 kB
W zakresie powy ej 0,9 istotny
wp yw ma równie organizacja
i algorytm wymiany
 wy sza asocjacyjno daje
wy szy wspó czynnik trafie
21
Wspó czynnik trafie a wydajno
Wspó czynnik trafie jest liczb niemianowan
Nie wyra a wzrostu wydajno ci wynikaj cego
z u ycia kieszeni
Kiesze y przyspieszeniu odwo do hierarchii
pami ci
Wydajno mo e by wyra ona poprzez odniesienie
ilo ci danych do czasu
 poprzez szybko transmisji. np. w MB/s
 poprzez redni czas transmisji, w jednostkach czasu na
transfer
niezale nie od cz stotliwo ci procesora  w cyklach procesora
na transfer
22
 redni czas dost pu
redni czas dost pu dla hierarchii pami ci z onej
z kieszeni i pami ci operacyjnej:
tAVG = h�tCACHE + (1  h)�tMEM
h  wspó czynnik trafie kieszeni
m = 1  h  wspó czynnik chybie kieszeni (miss
ratio)
Kiesze do czona do procesora musi by
skonstruowana tak, aby mog a dostarcza dane
z szybko ci wymagan przez procesor (bez
zatrzyma )
dla dalszych rozwa przyjmujemy tCACHE = 1
23
 redni czas dost pu hierarchii pami ci
Tabelka przedstawia redni czas
dost pu w zale no ci od
wspó czynnika trafie
tMEM
i dysproporcji wydajno ci pami ci
h 5 10 50 i kieszeni
Warto ci odpowiadaj warto ci
0,9 1,4 1,9 5,9
spowolnienia procesora
0,95 1,2 1,45 3,45
w stosunku do sytuacji idealnej
0,99 1,04 1,09 1,49 W zakresie  czerwonym procesor
pracuje kilkakrotnie wolniej ni
przy idealnej hierarchii pami ci
24
Wydajno kieszeni  wnioski
Intuicyjnie  wysoki wspó czynnik trafie nie zapewnia zbalansowania
wydajno ci procesora i hierarchii pami ci
 istotny jest nie tyle wspó czynnik trafie , co dysproporcja pomi dzy
wydajno ci kieszeni i pami ci
We wspó czesnych komputerach czas dost pu pami ci mo e by
ponad 100 razy d szy od czasu cyklu procesora
 z tabelki wynika, e nawet bardzo wysoki wspó czynnik trafie nie
umo liwi wyrównania wydajno ci
Pojedyncza kiesze mo e skutecznie zniwelowa ró nic wydajno ci
nie przekraczaj jednego rz du dziesi tnego
Poprawa redniego czasu dost pu wymaga poprawy czasu dost pu
poza kieszeni  mo na to uzyska zast puj c pami operacyjn
kolejnym zestawem kieszeni i pami ci
 w ten sposób powstaje wielopoziomowy system kieszeni
25
Kieszenie wielopoziomowe
Wymóg nad ania kieszeni pierwszego poziomu
(L1) ogranicza jej pojemno i asocjacyjno
 im wi ksza kiesze  tym wolniejsza
 im wy sza asocjacyjno  tym d szy czas dost pu
Kiesze drugiego poziomu (L2) mo e by wolniejsza
(np. 5 razy)  dzi ki temu:
 mo e mie wy sz asocjacyjno
 mo e by znacz co wi ksza
Je li kiesze L2 nie zapewnia odpowiednio krótkiego
redniego czasu dost pu, w strukturze komputera
umieszcza si kiesze L3, wi ksz i wolniejsz od
L2
26
Kiesze a zapis danych
W dotychczasowych rozwa aniach rozpatrywali my wy cznie odczyt
danych lub instrukcji z pami ci
Mo liwe zachowanie kieszeni przy zapisie:
 zapis przezroczysty  zapis wykonywany zawsze do pami ci,
a w przypadku trafienia  równie do kieszeni
 zapis zwrotny  zapis do pami ci wykonywany tylko wtedy, kiedy jest to
niezb dne
Warianty zapisu zwrotnego:
 bez alokacji przy chybieniu zapisu  w razie chybienia zapis zachodzi tylko
do pami ci. w razie trafienia  tylko do kieszeni
 z alokacj przy chybieniu zapisu  zapis jest zawsze wykonywany tylko do
kieszeni
Przy zapisie zwrotnym usuni cie linii z kieszeni mo e wymaga
zapisu usuwanej linii do pami ci
27
Kieszenie  strategie zapisu danych
Typ kieszeni trafienie odczytu chybienie odczytu trafienie zapisu chybienie zapisu
zapis
P C C M, P C P C, P M P M
przezroczysty
zapis zwrotny
C M, C M,
bez alokacji przy P C P C P M
P C
chybieniu zapisu
zapis zwrotny
C M, C M, C M, C M,
z alokacja, przy P C P C
P C P C
chybieniu zapisu
Oznaczenia: C  kiesze , P  procesor, M  pami
Kolor czerwony  dane usuwane z kieszeni w wyniku zastapienia linii
28
Kieszenie inkluzywne
Implementowane do ok. 2000 roku
Przep yw danych: pami L2 L1 procesor
Ka dy obiekt zawarty w wy szej warstwie
jest równie obecny w warstwie ni szej
Efektywna sumaryczna pojemno kieszeni
jest równa pojemno ci najwi kszej z warstw
kieszeni
Pojemno L2 musi by znacz co wi ksza
od L1
29
Kieszenie wy czne
Od oko o 2000 roku
Kiesze L2 jest nape niana wy cznie obiektami usuwanymi z L1
 jest to tzw. kiesze ofiar (victim cache)
okre lenie odnosi si do linii   ofiar algorytmu zast powania
Przep yw danych: pami L1 procesor, L1 L2
L2 zawiera g ównie obiekty nieobecne w L1
Efektywna sumaryczna pojemno kieszeni jest równa sumie
pojemno ci poszczególnych warstw kieszeni
Pojemno L2 mo e by równa lub wi ksza od L1
Asocjacyjno L2 powinna by wi ksza od asocjacyjno ci L1
 w przeciwnym przypadku sprawno przechwytywania ofiar by aby
niewielka
Przyk ady  K7 i K8 firmy AMD, Pentium 4 i Core firmy Intel
30
Kieszenie wy czne  g ówne cie ki
danych
procesor L1 L2 pami
31
Spójno hierarchii pami ci
Hierarchi pami ci musi cechowa spójno :
 ka dy dost p do danego adresu musi zwróci sam warto danej,
niezale nie od warstwy, w której jest fizycznie realizowany
Problem z utrzymaniem spójno ci powstaje, gdy istnieje wi cej
ni jedna cie ka dost pu do hierarchii pami ci, np.:
 procesor o architekturze Harvard-Princeton z oddzielnymi kieszeniami L1
kodu i danych
 dwa procesory z oddzielnymi kieszeniami L1 i wspóln dalsz warstw
hierarchii pami ci
 procesor z kieszeni i sterownik wej cia-wyj cia, wykonuj cy bezpo rednie
dost py do pami ci z pomini ciem kieszeni
Spójno nie wymaga utrzymywania identycznej zawarto ci we
wszystkich warstwach, a jedynie zagwarantowania, e ka dy
dost p b dzie dotyczy aktualnej warto ci danej
32
Metody utrzymywania spójno ci
Uniewa nianie ca ej kieszeni przy wykryciu odwo ania
zewn trznego
 stosowane dawniej przy b. ma ych kieszeniach
Selektywne uniewa nianie linii potencjalnie zawieraj cych adres
odwo ania zewn trznego
 stosowane do ok. 1990 roku przy kieszeniach o pojemno ciach do
kilku KB
Programowe uniewa nianie ca ej kieszeni
 dost pne dla systemu operacyjnego, ograniczone zastosowanie
z powodu spadku wydajno ci
Selektywna zmiana stanu linii po stwierdzeniu zgodno ci adresu,
przes ania mi dzy kieszeniami
 metody u ywane wspó cze nie, wydajne, ale z one w realizacji
 wymagaj realizacji z onych protoko ów utrzymania spójno ci
33
Protoko y utrzymania spójno ci
Automat zrealizowany oddzielnie dla ka dej linii
Stany linii:
 M  modified  linia wa na, jedyna aktualna kopia we w asnej kieszeni,
zawarto pami ci nieaktualna
 E  exclusive  linia wa na, jedyna kopia we w asnej kieszeni, identyczna
z zawarto ci pami ci
 I  invalid  linia niewa na
 S  shared  linia wa na, jednakowa kopia u wszystkich, identyczna
z zawarto ci pami ci
 O  owned  linia wa na, jednakowa kopia u wszystkich, u pozosta ych
stan S, zawarto pami ci nieaktualna
Protoko y  nazwy pochodz od zbioru obs ugiwanych stanów
 MEI, MESI, MOESI
Im wi cej stanów, tym mniej zb dnych uniewa nie
34