1

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Organizacja i Architektura

Komputerów

Pamięć cache

2

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wydajność: CPU i pamięć

Memory density and capacity have grown along with the CPU
power and complexity, but memory speed has not kept pace.

1990

1980 2000

2010

1

10

10

R

e

la

ti

ve

per

for

m

a

nc

e

Calendar year

Processor

Memory

3

6

3

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Pamięć cache – koncepcja

z

niewielka, ale szybka pamięć RAM

z

umieszczona między CPU a pamięcią główną
(operacyjną)

z

może być umieszczona w jednym układzie scalonym z
CPU lub poza CPU

4

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Pamięć cache – koncepcja

CPU

Cache

(fast)

memory

Main

(slow)

memory

Reg

file

Cache is transparent to user;
transfers occur automatically

Line

Word

5

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Hierarchiczny system pamięci

Tertiary

Secondary

Main

Cache 2

Cache 1

Reg’s

$Millions

$100s Ks

$10s Ks

$1000s

$10s

$1s

Cost per GB

Access latency

Capacity

TBs

10s GB

100s MB

MBs

10s KB

100s B

min+

10s ms

100s ns

10s ns

a few ns

ns

Speed

gap

Names and key characteristics of levels in a memory hierarchy.

6

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Połączenie CPU z cache

Level-2

cache

Main

memory

CPU

CPU

registers

Level-1

cache

Level-2

cache

Main

memory

CPU

CPU

registers

Level-1

cache

(a) Level 2 between level 1 and main

(b) Level 2 connected to “backside” bus

Cleaner and
easier to analyze

Cache memories act as intermediaries between the superfast
processor and the much slower main memory.

7

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Działanie pamięci cache

z

CPU żąda odczytu pamięci

z

sprawdza się, czy potrzebne dane znajdują się

w cache

z

jeśli tak, następuje szybki odczyt z cache

z

jeśli nie, przesyła się potrzebny blok danych z

pamięci głównej do cache

z

następnie żądane dane są przesyłane do CPU

z

pamięć cache jest wyposażona w znaczniki

(tags) pozwalające ustalić, które bloki pamięci

głównej są aktualnie dostępne w pamięci cache

8

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Zasady lokalności

z

Lokalność w sensie czasu:

jeśli CPU odwołuje się

do określonej komórki pamięci, jest
prawdopodobne, że w najbliższej przyszłości
nastąpi kolejne odwołanie do tej komórki

z

Lokalność w sensie przestrzeni adresowej:

jeśli

CPU odwołuje się do określonej komórki pamięci,
jest prawdopodobne, że w najbliższej przyszłości
nastąpi odwołanie do sąsiednich komórek pamięci

9

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Terminologia

z

cache hit

(trafienie): sytuacja, gdy żądana

informacja znajduje się w pamięci cache

wyższego poziomu

z

cache miss

(chybienie, brak trafienia): sytuacja,

gdy żądanej informacji nie ma w pamięci cache

wyższego poziomu

z

line, slot

(linijka, wiersz, blok): najmniejsza

porcja (kwant) informacji przesyłanej między

pamięcią cache, a pamięcią wyższego poziomu.

Najczęściej stosuje się linijki o wielkości 32

bajtów

10

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Terminologia

cd.

z

hit rate

(współczynnik trafień): stosunek liczby

trafień do łącznej liczby odwołań do pamięci

z

miss rate

(współczynnik chybień): 1 – hit rate

z

hit time

(czas dostępu przy trafieniu): czas

dostępu do żądanej informacji w sytuacji gdy

wystąpiło trafienie. Czas ten składa się z dwóch

elementów:

–

czasu potrzebnego do ustalenia, czy żądana

informacja jest w pamięci cache

–

czasu potrzebnego do przesłania informacji z

pamięci cache do procesora

11

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Terminologia

cd.

z

miss penalty

(kara za chybienie): czas potrzebny

na wymianę wybranej linijki w pamięci cache i
zastąpienie jej taką linijką z pamięci głównej,
która zawiera żądaną informację

z

czas

hit time

jest znacznie krótszy od czasu

miss penalty

(w przeciwnym przypadku

stosowanie pamięci cache nie miałoby sensu!)

12

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Problemy

z

W jaki sposób ustalić, czy żądana informacja znajduje
się w pamięci cache?

z

Jeśli już ustalimy, że potrzebna informacja jest w
pamięci cache, w jaki sposób znaleźć ją w tej pamięci
(jaki jest jej adres?)

z

Jeśli informacji nie ma w pamięci cache, to do jakiej
linijki ją wpisać z pamięci głównej?

z

Jeśli cache jest pełna, to według jakiego kryterium
usuwać linijki aby zwolnić miejsce na linijki sprowadzane
z pamięci głównej?

z

W jaki sposób inicjować zawartość pamięci cache?

13

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Odwzorowanie bezpośrednie

z

direct-mapped cache

z

każdy blok (linijka) w pamięci głównej jest
odwzorowywana (przyporządkowana) tylko
jednej linijce w pamięci cache

z

ponieważ cache jest znacznie mniejsza od
pamięci głównej, wiele różnych linijek pamięci
głównej jest odwzorowanych na tą samą linijkę
w cache

14

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Funkcja odwzorowująca

z

Najprostsza metoda odwzorowania polega na
wykorzystaniu najmniej znaczących bitów
adresu

z

Na przykład, wszystkie linijki w pamięci głównej,
których adresy kończą się sekwencją 000 będą
odwzorowane na tą samą linijkę w pamięci
cache

z

Powyższa metoda wymaga, by rozmiar pamięci
cache (wyrażony w linijkach) był potęgą liczby 2

15

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Odwzorowanie bezpośrednie

00001

00101

01001

01101

10001

10101

11001

11101

00

0

Cache

Memory

00

1

010

01

1

10

0

10

1

11

0

111

16

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Co znajduje się w linijce 000?

z

Wciąż nie wiemy, która linijka z pamięci głównej (z wielu

możliwych) znajduje się aktualnie w konkretnej linijce

pamięci cache

z

Musimy zatem zapamiętać adres linijki przechowywanej

aktualnie w linijkach pamięci cache

z

Nie trzeba zapamiętywać całego adresu linijki, wystarczy

zapamiętać tylko tę jego część, która nie została

wykorzystana przy odwzorowaniu

z

Tę część adresu nazywa się znacznikiem (tag)

z

Znacznik związany z każdą linijką pamięci cache

pozwala określić, która linijka z pamięci głównej jest

aktualnie zapisana w danej linijce cache

17

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Znaczniki – ilustracja

Pamięć główna

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

Znaczniki

Dane

18

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Inicjalizacja cache

z

Początkowo pamięć cache jest pusta

–

wszystkie bity w pamięci cache (włącznie z bitami
znaczników) mają losowe wartości

z

Po pewnym czasie pracy systemu pewna część
znaczników ma określoną wartość, jednak
pozostałe są nadal wielkościami losowymi

z

Jak ustalić, które linijki zawierają rzeczywiste
dane, a które nie zostały jeszcze zapisane?

19

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Bit ważności

(valid bit)

z

Należy dodać przy każdej linijce pamięci cache
dodatkowy bit, który wskazuje, czy linijka zawiera ważne
dane, czy też jej zawartość jest przypadkowa

z

Na początku pracy systemu bity ważności są zerowane,
co oznacza, że pamięć cache nie zawiera ważnych
danych

z

Przy odwołaniach CPU do pamięci, w trakcie
sprawdzania czy potrzebne dane są w cache należy
ignorować linijki z bitem ważności równym 0

z

Przy zapisie danych z pamięci głównej do pamięci cache
należy ustawić bit ważności linijki

20

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Rewizyta w cache

Memory

Valid

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

Tags

Data

21

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Prosta symulacja cache

z

Użyjemy prostej struktury z pamięcią cache L1
zbudowaną tylko z czterech linijek, podobną do
opisanej wcześniej

z

Założymy, że na początku bity ważności zostały
wyzerowane

22

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Założenie: sekwencja odwołań CPU

do pamięci

Adres

Adres binarny

Linijka

hit / miss

3

0011

11 (3)

8

1000

00 (0)

miss

2

0010

10 (2)

miss

4

0100

00 (0)

miss

3

0011

11 (3)

hit

00 (0)

miss

8

1000

miss

23

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Address

Binary Address

Slot

hit or miss

3

0011

11 (3)

8

1000

00 (0)

miss

2

0010

10 (2)

miss

4

0100

00 (0)

miss

3

0011

11 (3)

hit

00 (0)

miss

8

1000

miss

Slot

Tag

Data

V

00

01

10

11

24

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Address

Binary Address

Slot

hit or miss

3

0011

11 (3)

8

1000

00 (0)

miss

2

0010

10 (2)

miss

4

0100

00 (0)

miss

3

0011

11 (3)

hit

00 (0)

miss

8

1000

miss

Slot

Tag

Data

V

Inicjalizacja

bitów

ważności

00

01

10

11

0

0

0

0

25

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Address

Binary Address

Slot

hit or miss

3

00

11

11

(3)

8

1000

00 (0)

miss

2

0010

10 (2)

miss

4

0100

00 (0)

miss

3

0011

11 (3)

hit

00 (0)

miss

8

1000

miss

Slot

Tag

Data

V

First Access

00

01

10

11

0

0

0

1

00

Mem[3]

26

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Address

Binary Address

Slot

hit or miss

3

0011

11 (3)

8

10

00

00

(0)

miss

2

0010

10 (2)

miss

4

0100

00 (0)

miss

3

0011

11 (3)

hit

00 (0)

miss

8

1000

miss

Slot

Tag

Data

V

2nd Access

00

01

10

11

1

0

0

1

00 Mem[3]

10

Mem[8]

27

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Address

Binary Address

Slot

hit or miss

3

0011

11 (3)

8

1000

00 (0)

miss

2

0010

10 (2)

miss

4

0100

00 (0)

miss

3

00

11

11

(3)

hit

00 (0)

miss

8

1000

miss

Slot

Tag

Data

V

3rd Access

00

01

10

11

1

0

0

1

00

Mem[3]

10 Mem[8]

28

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Address

Binary Address

Slot

hit or miss

3

0011

11 (3)

8

1000

00 (0)

miss

2

00

10

10

(2)

miss

4

0100

00 (0)

miss

3

0011

11 (3)

hit

00 (0)

miss

8

1000

miss

Slot

Tag

Data

V

4th Access

00

01

10

11

1

0

1

1

00 Mem[3]

10 Mem[8]

00

Mem[2]

29

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Address

Binary Address

Slot

hit or miss

3

0011

11 (3)

8

1000

00 (0)

miss

2

0010

10 (2)

miss

4

01

00

00

(0)

miss

3

0011

11 (3)

hit

00 (0)

miss

8

1000

miss

Tag

V

Data

Slot

00

01

10

11

1

0

1

1

00 Mem[3]

10

Mem[8]

00 Mem[2]

01

Mem[4]

5th Access

30

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Address

Binary Address

Slot

hit or miss

3

0011

11 (3)

8

1000

00 (0)

miss

2

0010

10 (2)

miss

4

0100

00 (0)

miss

3

0011

11 (3)

hit

00

(0)

miss

8

10

00

miss

Slot

Tag

Data

V

6th Access

01

Mem[4]

00

01

10

11

1

0

1

1

00 Mem[3]

00 Mem[2]

10

Mem[8]

31

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Problem

z

Założenia projektowe:

–

32-bitowe adresy (2

32

bajtów w pamięci głównej, 2

30

słów

4-bajtowych)

–

64 KB cache (16 K słów). Każda linijka przechowuje 1 słowo

–

Odwzorowanie bezpośrednie (Direct Mapped Cache)

z

Ile bitów będzie miał każdy znacznik?

z

Ile różnych linijek z pamięci głównej będzie
odwzorowanych na tę samą linijkę w pamięci cache?

z

Ile bitów będzie zajmować łącznie kompletna linijka w
pamięci cache? (data + tag + valid).

32

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Rozwiązanie

z

Pamięć zawiera 2

30

słów

z

Cache zawiera 16K = 2

14

linijek (słów).

z

Każda linijka może przechowywać jedną z 2

30

/2

14

=

2

16

linijek pamięci głównej, stąd znacznik musi mieć

16 bitów

z

2

16

linijek w pamięci głównej ma łączną pojemność

równą 64K linijek – taki obszar jest
przyporządkowany każdej linijce w pamięci cache

z

Łączna pojemność pamięci cache wyrażona w bitach
wynosi 2

14

x (32+16+1) = 49 x 16K = 784 Kb

(98 KB!)

33

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Problem z zapisem

z

Write through

– zapis jednoczesny: dane są

zapisywane jednocześnie do cache i pamięci głównej.

–

Zaleta:

zapewnienie stałej aktualności danych w pamięci

głównej (memory consistency)

–

Wada:

duży przepływ danych do pamięci

z

Write back

– zapis opóźniony: aktualizuje się tylko

pamięć cache. Fakt ten odnotowuje się w specjalnym
dodatkowym bicie (dirty, updated). Przy usuwaniu
linijki z cache następuje sprawdzenie bitu i
ewentualna aktualizacja linijki w pamięci głównej.

–

Zaleta:

mniejszy przepływ danych do pamięci

–

Wada:

problemy ze spójnością danych w pamięci

34

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Zapis jednoczesny

(write through)

Procesor

Cache

Write Buffer

DRAM

z

W metodzie

write through

procesor zapisuje dane

jednocześnie do cache i do pamięci głównej

–

w zapisie do pamięci głównej pośredniczy bufor

–

przepisywanie danych z bufora do pamięci głównej obsługuje
specjalizowany kontroler

z

Bufor jest niewielką pamięcią FIFO (first-in-first-out)

–

typowo zawiera 4 pozycje

–

metoda działa dobrze, jeśli czestość operacji zapisu jest
znacznie mniejsza od 1 / DRAM write cycle

35

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Projekt cache - przykład

z

Założenia projektowe:

–

4 słowa w linijce

z

do przeprowadzenia odwzorowania pamięci używamy
adresów linijek

z

adres linijek jest określany jako adres/4.

z

przy odwołaniu ze strony CPU potrzebne jest pojedyncze
słowo, a nie cała linijka (można wykorzystać multiplekser
sterowany dwoma najmniej znaczącymi bitami adresu)

–

Cache 64KB

z

16 Bajtów w linijce

z

4K linijek

36

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Projekt cache - rozwiązanie

Address (showing bit positions)

16

12

Byte

offset

V

Tag

Data

Hit

Data

16

32

4K
entries

16 bits

128 bits

Mux

32

32

32

2

32

Block offset

Index

Tag

31

16 15

4 3 2 1 0

37

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wielkość linijki a wydajność

Przykład: DecStation 3100 cache z linijką

o rozmiarze 1 lub 4 słów

Rozmiar

Miss Rate

Program

gcc

1

6.1%

2.1%

5.4%

spice

1

1.2%

1.3%

1.2%

gcc

spice

4

2.0%

1.7%

1.9%

linijki

Instrukcje

Dane

Instr. + Dane

4

0.3%

0.6%

0.4%

38

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Czy duża linijka jest lepsza?

z

Zwiększanie rozmiaru linijki (przy ustalonym rozmiarze
pamięci cache) oznacza, że liczba linijek
przechowywanych w pamięci jest mniejsza

–

konkurencja o miejsce w pamięci cache jest większa

–

parametr miss rate wzrasta

z

Proszę rozważyć skrajny przypadek, gdy cała pamięć
cache tworzy jedną dużą linijkę!

39

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Rozmiar linijki a miss rate

Rozmiar cache (bajty)

Miss
Rate

0%

5%

10%

15%

20%

25%

16

32

64

128

256

1K

4K

16K

64K

256K

Rozmiar linijki (bajty)

40

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Rozmiar linijki a miss penalty

z

Im większy jest rozmiar linijki, tym więcej czasu potrzeba na

przesłanie linijki między pamięcią główną a pamięcią cache

z

W przypadku chybienia czas sprowadzenia linijki wzrasta

(parametr miss penalty ma większą wartość)

z

Można budować pamięci zapewniające transfer wielu bajtów w

jednym cyklu odczytu, ale tylko dla niewielkiej liczby bajtów

(typowo 4)

z

Przykład: hipotetyczne parametry dostępu do pamięci głównej:

–

1 cykl CPU na wysłanie adresu

–

15 cykli na inicjację każdego dostępu

–

1 cykl na transmisję każdego słowa

z

Parametr miss penalty dla linijki złożonej z 4 słów:

1 + 4x15 + 4x1 = 65 cykli.

41

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wydajność cache

z

Średni czas dostępu do pamięci
AMAT –

average memory access time

AMAT = Hit time + Miss rate x Miss penalty

z

Poprawa wydajności pamięci cache polega na
skróceniu czasu AMAT przez:

1.

ograniczenie chybień (zmniejszenie miss rate,
zwiększenie hit rate)

2.

zmniejszenie miss penalty

3.

zmniejszenie hit time

42

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wydajność cache

z

Wydajność cache zależy głównie od dwóch czynników

:

–

miss rate

z

Zależy od organizacji procesora (hardware) i od

przetwarzanego programu (miss rate może się zmieniać).

–

miss penalty

z

Zależy tylko od organizacji komputera (organizacji pamięci

i czasu dostępu do pamięci)

z

Jeśli podwoimy częstotliwość zegara nie zmienimy

żadnego z tych parametrów (czas dostępu do pamięci

pozostanie taki sam)

z

Dlatego parametr speedup wzrośnie mniej niż

dwukrotnie

43

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wydajność cache - przykład

z

Załóżmy, że w pamięci cache z odwzorowaniem

bezpośrednim co 64 element pamięci jest

odwzorowany w tej samej linijce. Rozważmy

program:

for (i=0;i<10000;i++) {

a[i] = a[i] + a[i+64] + a[i+128];

a[i+64] = a[i+64] + a[i+128];

}

z

a[i]

,

a[i+64]

i a[i+128] używają tej samej linijki

z

Pamięć cache jest w powyższym przykładzie

bezużyteczna

44

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Jak zmniejszyć miss rate?

z

Oczywiście zwiększenie pamięci cache
spowoduje ograniczenie chybień, czyli
zmniejszenie parametru miss rate

z

Można też zmniejszyć miss rate ograniczając
konkurencję przy obsadzie linijek pamięci cache

–

Trzeba pozwolić linijkom z pamięci głównej na
rezydowanie w dowolnej linijce pamięci cache

45

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Odwzorowanie skojarzeniowe

z

Fully associative mapping

z

Zamiast odwzorowania bezpośredniego zezwalamy na
lokację linijek w

dowolnym miejscu pamięci cache

z

Teraz sprawdzenie czy dane są w pamięci cache jest
trudniejsze i zajmie więcej czasu (parametr hit time
wzrośnie)

z

Potrzebne są dodatkowe rozwiązania sprzętowe
(komparator dla każdej linijki pamięci cache)

z

Każdy znacznik jest teraz kompletnym adresem linijki w
pamięci głównej

46

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Odwzorowanie skojarzeniowe

Bit

ważności

Pamięć

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

Znaczniki

Dane

47

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Rozwiązanie kompromisowe

z

Odwzorowanie skojarzeniowe jest bardziej

elastyczne, dlatego parametr

miss rate

ma

mniejszą wartość

z

Odwzorowanie bezpośrednie jest prostsze

sprzętowo, czyli tańsze w implementacji

–

Ponadto lokalizacja danych w pamięci cache jest

szybsza (parametr

hit time

ma mniejszą wartość)

z

Szukamy kompromisu między miss rate a hit
time

.

z

Rozwiązanie pośrednie: odwzorowanie

sekcyjno-skojarzeniowe (

set associative

)

48

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Set Associative Mapping

z

Każda linijka z pamięci głównej może być

ulokowana w pewnym dozwolonym podzbiorze

linijek pamięci cache

z

Pojęcie

n-way set associative mapping

(odwzorowanie n-drożne sekcyjno-

skojarzeniowe) oznacza, że istnieje n miejsc

(linijek) w pamięci cache, do których może trafić

dana linijka z pamięci głównej placed.

z

Pamięć cache jest zatem podzielona na pewną

liczbę podzbiorów linijek, z których każdy

zawiera n linijek

49

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Porównanie odwzorowań

Przykład: cache składa się z 8 linijek, rozpatrujemy lokalizację
linijki z pamięci głównej o adresie 12

Linijka 12 może się
znaleźć w jednej z dwóch
linijek zbioru 0

Linijka 12 może się znaleźć
w dowolnej linijce cache

Linijka 12 może się
znaleźć tylko w linijce 4

1
2

Tag

Data

Block # 0 1 2 3 4 5 6 7

Search

Direct mapped

1
2

Tag

Data

Set #

0

1

2

3

Search

Set associative

1
2

Tag

Data

Search

Fully associative

50

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wydajność a n-drożność cache

Performance improvement of caches with increased associativity.

4-way

Direct 16-way

64-way

0

0.1

0.3

Mi

ss

ra

te

Associativity

0.2

2-way 8-way 32-way

51

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Odwzorowanie n-drożne

z

Odwzorowanie bezpośrednie jest szczególnym
przypadkiem n-drożnego odwzorowania sekcyjno-
skojarzeniowego przy n = 1 (1 linijka w zbiorze)

z

Odwzorowanie skojarzeniowe jest szczególnym
przypadkiem n-drożnego odwzorowania sekcyjno-
skojarzeniowego przy n równym liczbie linijek w pamięci
cache

z

Poprzedni przykład pokazuje, że odwzorowanie
4-drożne może nie dawać zauważalnej poprawy
wydajności cache w porównaniu z odwzorowaniem
2-drożnym.

52

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Algorytm wymiany linijek

z

W metodzie odwzorowania bezpośredniego nie
mamy wyboru przy zastępowaniu linijek –
problem strategii wymiany linijek nie istnieje

z

W metodzie odwzorowania sekcyjno-
skojarzeniowego należy określić strategię
wyboru linijek, które mają być usunięte przy
wprowadzaniu do cache nowych linijek

53

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Algorytm LRU

z

LRU

:

Least recently used

.

–

system zarządzania pamięcią cache rejestruje

historię każdej linijki

–

jeśli trzeba wprowadzić do cache nową linijkę, a w

dopuszczalnym zbiorze linijek nie ma wolnego

miejsca, usuwana jest najstarsza linijka.

–

przy każdym dostępie do linijki (hit) wiek linijki jest

ustawiany na 0

–

przy każdym dostępie do linijki wiek wszystkich

pozostałych linijek w danym zbiorze linijek jest

zwiększany o 1

54

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Implementacja LRU

z

Realizacja algorytmu LRU jest wykonywana sprzętowo

z

Obsługa LRU w pamięciach 2-drożnych jest łatwa –
wystarczy tylko 1 bit aby zapamiętać, która linijka (z
dwóch) w zbiorze jest starsza

z

Algorytm LRU w pamięciach 4-drożnych jest znacznie
bardziej złożony, ale stosowany w praktyce

z

W przypadku pamięci 8-drożnych sprzętowa realizacja
LRU staje się kosztowna i skomplikowana. W praktyce
używa się prostszego algorytmu aproksymującego
działanie LRU

55

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wielopoziomowa pamięć cache

z

Wielkość pamięci cache wbudowanej do procesora jest
ograniczona ze względów technologicznych

z

Ekonomicznym rozwiązaniem jest zastosowanie
zewnętrznej pamięci cache L2

z

Zwykle zewnętrzna pamięć cache jest szybką pamięcią
SRAM (czas miss penalty jest znacznie mniejszy niż w
przypadku pamięci głównej)

z

Dodanie pamięci cache L2 wpływa na projekt pamięci
cache L1 – dąży się do tego, by parametr hit time dla
pamięci L1 był jak najmniejszy

56

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wspólna a rozdzielona cache

z

We wspólnej pamięci cache dane i instrukcje są przechowywane

razem (architektura von Neumanna)

z

W rozdzielonej pamięci cache dane i instrukcje są przechowywane w

osobnych pamięciach (architektura harwardzka)

z

Dlaczego pamięć cache przechowująca instrukcje ma znacznie

mniejszy współczynnik miss rate?

Size

Instruction Cache Data Cache

Unified Cache

1 KB

3.06%

24.61%

13.34%

2 KB

2.26%

20.57%

9.78%

4 KB

1.78%

15.94%

7.24%

8 KB

1.10%

10.19%

4.57%

16 KB

0.64%

6.47%

2.87%

32 KB

0.39%

4.82%

2.48%

64 KB

0.15%

3.77%

1.35%

128 KB

0.02%

2.88%

0.95%

57

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wspólna a rozdzielona cache

z

Które rozwiązanie zapewnia krótszy czas dostępu
AMAT?

–

pamięć rozdzielona: 16 KB instrukcje + 16 KB dane

–

pamięć wspólna: 32 KB instrukcje + dane

z

Założenia:

–

należy użyć danych statystycznych dotyczących miss rate z
poprzedniego slajdu

–

zakładamy, że 75% dostępów do pamięci dotyczy odczytu
instrukcji, a 25% dostępów dotyczy danych

–

miss penalty

= 50 cykli

–

hit time

= 1 cykl

–

operacje odczytu i zapisu zajmują dodatkowo 1 cykl, ponieważ
jest tylko jeden port dla instrukcji i danych

58

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Wspólna a rozdzielona cache

AMAT = %instr x (instr hit time + instr miss rate x instr miss penalty) +

%data x (data hit time + data miss rate x data miss penalty)

Dla rozdzielonej pamięci cache:

AMAT = 75% x (1 + 0.64%x 50) + 25% x (1 + 6.47% x 50) =

2.05

Dla wspólnej pamięci cache:

AMAT = 75% x (1 + 2.48%x 50) + 25% x (1 + 2.48% x 50) =

2.24

W rozważanym przykładzie lepszą wydajność (krótszy czas dostępu

AMAT) zapewnia rozdzielona pamięć cache

59

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Przykład – cache w Pentium

Processor Chip

L1 Data

1 cycle latency

16KB

4-way assoc

Write-through

32B lines

L1 Instruction

16KB, 4-way

32B lines

Regs.

L2 Unified

128KB--2 MB

4-way assoc

Write-back

32B lines

Main

Memory

Up to 4GB

60

Wyższa Szkoła Informatyki Stosowanej i Zarządzania

Podsumowanie

z

Zasada lokalności

z

Hierarchiczny system pamięci

z

Koncepcja budowy i działania pamięci cache

z

Metody odwzorowania pamięci głównej i pamięci cache

–

odwzorowanie bezpośrednie (mapowanie bezpośrednie)

–

odwzorowanie asocjacyjne (pełna asocjacja)

–

częściowa asocjacja

z

Zapis danych i problem spójności zawartości pamięci

z

Wydajność pamięci cache, metody optymalizacji,

ograniczenia

z

Wymiana linijek w pamięci cache - algorytm LRU

z

Przykłady organizacji i architektury pamięci cache

z

Wspólna a rozdzielona pamięć cache