Pamięć (część 2)

scalonym rzadko udaje się zrealizować wymagania konstruktorów posługując się pojedynczą
kością. Dysponując wieloma kośćmi o różnych parametrach katalogowych zazwyczaj chcemy
albo powiększyć liczbę słów zachowując oferowaną przez producenta liczbę bitów w słowie
(długość słowa) albo powiększyć długość słowa zachowując oferowaną ich liczbę.

Zwiększanie długości słowa polega na takim połączeniu układów scalonych, aby ich linie

danych stanowiły kolejne bity tworzonego słowa. Na rysunku 9.7 pokazano schemat pamięci
1M×9b powstałej z połączenia dwóch kości pamięci 1M×4b i jednej 1M×1b.

Wejścia/wyjścia danych

adres

1M×9b

R/W

1M×9b

R/W

1M×1b

R/W

Rysunek 9.7. Rozszerzanie długości słowa pamięci

Pamięć (część 2)

Wejście adresowe są zwarte, tak że ten sam adres wybiera bity d

z kości pierwszej, bity

z kości drugiej i bit d

z kości trzeciej. Są to bity tego samego słowa powstałego układu

złożonego. Podobnie zwarte są linie R/W i E (wejście aktywujące) wszystkich układów
składowych tworząc analogiczne (tj. R/W i E) linie nowego układu. Opisany sposób stosowany
jest np. przy budowie modułów SIMM (ang. single in line module)

Zwiększanie ilości słów wymaga zwiększenia liczby adresów, co pociąga za sobą rozszerzenie

szyny adresowej. Natomiast linie danych układów składowych są ze sobą zwarte. Idea
konstrukcji nowego układu polega na tym, aby każdy układ składowy realizował część
przestrzeni adresowej nowo tworzonej „dużej” pamięci. Wybór układu składowego, w którym
dla konkretnego adresu znajduje się komórka pamięci dokonuje się za pomocą dekodera. Wejścia
dekodera stają się ostatnimi bitami adresu układu finalnego.

Konstrukcję pamięci 1M×4b z 4 układów 256K×4b pokazano na rysunku 9.8 (patrz niżej).

Układy 256K×4b mają 18-bitowe adresy: linie a

- a

. Układ finalny (1M×4b) ma ich w sumie 20

(18 bitów z układów składowych: linie a

- a

i dwa od dekodera: linie a

- a

). Linie danych d

układów składowych są ze sobą zwarte.

-d

256K×4b 256K×4b 256K×4b

256K×4b

E R/W

R/W

- a

Rysunek 9.8. Powiększenie ilości słów pamięci

9.2.4

Pamięć kieszeniowa

Idea pamięci kieszeniowych powstała ze skojarzenia dwóch faktów:

istnienia dużych, ale wolnych pamięci dynamicznych oraz małych ale szybkich pamięci
statycznych;

istnienia zjawiska tzw. lokalności (ang. locality) w adresach generowanych przez

wykonujący się program, które to zjawisko objawia się niewielkim rozrzutem
wspomnianych adresów (precyzyjnie: prawdopodobieństwo wygenerowania adresów z

Pamięć (część 2)

bliskiego sąsiedztwa jest istotnie większe od prawdopodobieństwa wygenerowania
adresów leżących poza nim).

Pojęcie bliskie sąsiedztwo można utożsamiać z obszarem pamięci zajmowanym przez program.

Przekopiowanie komórek odpowiadającym bliskiemu sąsiedztwu z pamięci dynamicznej do
szybkiej pamięci statycznej nazywanej pamięcią kieszeniową (ang. cache memory)
spowodowałoby, że odwołania do pamięci w trakcie wykonywania programu z dużym
prawdopodobieństwem mogłyby być kierowane właśnie do tego obszaru. Jeżeli adres
pamięciowy wygenerowany przez procesor w trakcie wykonywania programu istotnie jest
adresem komórki znajdującej sie w pamięci kieszeniowej to mówimy o tzw. trafieniu. Jeżeli
adres ten jest adresem komórki znajdującej poza pamięcią kieszeniową to nazywamy ten fakt
chybieniem. Jeżeli zaszło chybienie, to należy wymienić zawartość części pamięci kieszeniowej
kopiując do niej komórki z adresami bliskimi adresu chybionego, bo szansa na to, że kolejne
odwołania do pamięci będą dotyczyły właśnie tych adresów jest duża.

Opisana idea okazała sie na tyle atrakcyjna, że jest dzisiaj powszechnie stosowna. Ze względu

na lokalizację wyróżnia sie trzy poziomy pamięci kieszeniowej:

L1 – pamięć jest zintegrowana z procesorem (jest jego częścią albo inaczej znajduje sie w

jego wnętrzu);

L2 – pamięć umieszczone jest w jednej obudowie z procesorem;
L3 – pamięć jest poza procesorem, najczęściej w bezpośrednim jego sąsiedztwie.

Pojemność pamięci zależy od jej poziomu. Dla poziomu L1 typowe wartości wartości nie

przekraczją kilkudziesięciu KB (można przyjąć, że nie więcej niż 128 KB); dla poziomu L2:
kilkadziesiąt KB do pojedynczych MB; dla poziomu L3 są to wartości nawet rzędu 100 MB.
Prędkość tych pamięci jest od kilku do kilkunastu razy większa od prędkości dynamicznej
pamięci operacyjnej. Ze względu na dynamiczny rozwój technologii wartości te szybko ulegają
zmianie. Podsumowanie wartości parametrów pamięci kieszeniowych znajduje sie w tabeli 9.2.

Poziom

Pojemność

Czas dostępu

≤128KB

~1ns

128KB÷4MB

1÷2ns

≤144MB

2÷5ns

Tabela 9.2. Zestawienie parametrów różnych poziomów pamięci kieszeniowej

9.2.4.1

Organizacja dostępu do procesora

Wyróżniamy trzy typy organizacji dostępu procesora do pamięci kieszeniowej:

dostęp bezpośredni (ang. look-aside);

dostęp „przez” (ang. look-through);

dostęp od tyłu (ang. look-backside).

Pokrótce opiszemy każdy z nich. Zaczniemy od dostępu bezpośredniego. W tym trybie

procesor odwołuje się do pamięci kieszeniowej wykorzystując magistralę pamięciową (patrz
rysunek 9.9 niżej). Pamięć kieszeniowa jest podłączona równolegle z pamięcią operacyjną. 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 pamięci kieszeniowej może ulec
skróceniu. Wykorzystanie tej samej magistrali nie jest korzystne. Jest ona blokowana przy

Pamięć (część 2)

każdym dostępie procesora do pamięci kieszeniowej i nie może być w tym samym czasie
udostępniona innym urządzeniom.

magistrala pamięci

Procesor

Pamięć operacyjna

Pamięć

kieszeniowa

Rysunek 9.9. Architektura dostępu pamięci do procesora: tryb bezpośredni

W trybie dostępu „przez” pamięć kieszeniowa pośredniczy w dostępie procesora do pamięci

operacyjnej. Procesor odwołuje się do pamięć kieszeniowej, która jest połączona przez magistralę
pamięciową z pamięcią operacyjną RAM (patrz rysunek 9.10).

Pamięć

Procesor

kieszeniowa

operacyjna

Rysunek 9.10. Architektura dostępu pamięci do procesora: tryb „przez”

W trybie dostępu „od tyłu” pamięć kieszeniowa jest dołączony do procesora przez oddzielną

magistralę nazywaną pomocniczą (ang. BSB; Back Side Bus). Druga magistrala nazywana
główną (ang. FSB Front Side Bus) łączy procesor z pamięcią operacyjną (patrz rysunek 9.11). W
tym układzie obie magistrale są zupełnie niezależne (mogą pracować z różnymi
częstotliwościami). Możliwe jest też wykorzystanie magistrali FSB przez inne urządzenia
zapisujące do pamięci operacyjnej, w czasie gdy procesor komunikuje się z pamięcią
kieszeniową przez magistralę pomocniczą.

magistrala

FSB

Pamięć

Procesor

operacyjna

magistrala

BSB

Pamięć

kieszeniowa

Rysunek 9.11. Architektura dostępu pamięci do procesora: tryb „od tyłu”

Pamięć (część 2)

9.2.4.2

Budowa i działanie

Ogólna zasada konstrukcji pamięci kieszeniowych polega na podziale pamięci operacyjnej na k

bloków po q słów każdy, a pamięci kieszeniowej na linie (ang. slot), w której mieści się jeden
blok oraz jego numer nazywany etykietą (ang. tag). Aby obliczyć długość linii (w bitach) należy
wyznaczyć liczbę bitów, jaką zajmie etykieta. Zróbmy to przy założeniu, że mamy k bloków.
Jeżeli szukaną liczbę oznaczymy przez x to musi być ono tak dobrane, aby na x bitach można
było zapisać każdy możliwy numer bloku. Ilość numerów, jakie można zapisać na x bitach równa
jest ilości różnych ciągów zero-jedynkowych o długości x, czyli 2

. Mamy więc:

= k

czyli, że

x = log

(1)

Długość linii w bitach, zakładając, że słowo jest 8-bitowe wynosi więc:

s = log

k + 8∙q

(2)

Na rysunku 9.12 pokazane są schematy pamięci operacyjnej i kieszeniowej skonstruowanych

według omówionych zasad.

Przy projektowaniu pamięci kieszeniowej należy rozwiązać trzy kluczowe zagadnienia:

1.  odwzorowanie adresów pamięci operacyjnej i pamięci kieszeniowej;
2.  algorytmy wymiany pamięci operacyjnej i kieszeniowej;
3.  strategia aktualizacji zawartości pamięci operacyjnej i kieszeniowej.

Omówimy je posługując się przykładową pamięcią operacyjną o pojemności 64K = 2

słów

podzieloną na 8-słowowe bloki (q=8) i również przykładową pamięcią kieszeniową o pojemności
m = 128 linii po 8 słów w linii. Z tych danych wynika, że mamy k = 2

/8 = 2

= 2

= 8192

bloków.

log

q słów

1 blok

.....

q-1

2 blok

k-1 blok

m-2

m-1

k blok

Rysunek 9.12. Schemat pamięci operacyjnej (a) i kieszeniowej (b).

Pamięć (część 2)

Odwzorowanie pamięci operacyjnej na pamięć kieszeniową organizuje się według jednej z

trzech metod: bezpośredniej, skojarzeniowe lub skojarzeniowej zmodyfikowanej.

W metodzie bezpośredniej (ang. direct mapping) każdej linii pamięci kieszeniowej przydziela

się pewien ustalony zbiór bloków pamięci operacyjnej. Tylko bloki tego zbioru mogą być
kopiowane do i z ustalonej linii. Liczba bloków zbioru równa jest liczbie bloków przypadających
na jedną linię i wynosi:

k/m = 8192/128 = 2

= 2

= 64

Zgodnie z zasadami konstrukcji pamięci kieszeniowej podanymi wcześniej każdy blok tego

zbioru ma swoją etykietę o długości x bitów, gdzie x można wyliczyć korzystając z wzoru 1
(patrz wyżej) ale odnosząc go do liczby bloków w zbiorze. Tak więc:

x = log

(k/m) = log

64 = log

= 6

Ponieważ każdą linię pamięci kieszeniowej tworzy etykieta i odpowiadający jej blok, to

długość linii (przy założeniu, że mamy 8-bitowe słowa) zgodnie z wzorem 2 (patrz wyżej)
wynosi:

s = 6 + 8∙8 = 70 bitów.

Na rysunku 9.13 (patrz niżej) pokazany jest schemat pamięci kieszeniowej z mapowaniem

bezpośrednim wraz ze sposobem wyboru boków tworzących zbiory przypisywane
poszczególnym liniom tej pamięci. Wewnątrz niektórych prostokątów przedstawiających
pojedyncze, kolejne bloki pamięci wypisane są kolejne numery bloków tworzących zbiór
przypisany do wybranej dla przykładu pierwszej linii (tj. linii o numerze 0) pamięci kieszeniowej.
Niezależnie pokazują to strzałki skierowane do tej i do niektórych wybranych linii. Zgodnie z
tym schematem linii 0 przypisane są 64 bloki o numerach: 0, 128, 256, ... , 8064. Natomiast linii
pierwszej przypisane są 64 bloki o numerach: 1, 129, 257, ... , 8065. Ostatniej linii (ma numer
127) przypisane są 64 bloki o numerach: 127, 255, ... , 8191.

nr bloku

0 1

127
128 2
129
130

255

8064 64

127

70 bitów

8191

Rysunek 9.13. Odwzorowanie bloków pamięci operacyjnej na pamięć kieszeniową w metodzie

bezpośredniej.

Pamięć (część 2)

Pokazany schemat organizacji znajduje swoje odzwierciedlenie w interpretacji adresu

generowanego przez procesor (pamiętajmy, że taki adres zawsze wskazuje słowo w pamięci
operacyjnej). Przy 64K pamięci adresy są 16 bitowe, a każde 16 bitów dzielimy na 3 grupy:

  6-bitowa etykieta wskazująca numer bloku w ramach 64-blokowego zbioru;
  7-bitowy adres wskazujący numer linii w pamięci kieszeniowej;
  3-bitowy adres wskazujący numer słowa w 8-słowowym bloku.

nr linii pamięci nr słowa

etykieta kieszeniowej w bloku

6 bitów 7 bitów 3 bity

Rysunek 9.14. Interpretacja bitów adresu wytworzonego przez procesor w metodzie bezpośredniej.

Procesor, który wytworzy adres, odczytuje z pamięci kieszeniowej etykietę w linii wskazanej

grupą 7 bitów tego adresu i porównuje ją z etykietą adresu wytworzonego. Zgodność oznacza
trafienie. Wtedy z pamięci kieszeniowej odczytywane jest słowo o numerze wskazanym przez
grupę 3 ostatnich bitów adresu. Niezgodność oznacza chybienie i wtedy należy dokonać
wymiany całej linii pamięci kieszeniowej. Polega to na zapisaniu aktualnej zawartości linii do
pamięci operacyjnej, a następnie odczytaniu z niej żądanego bloku, zapisania go do pamięci
kieszeniowej i sięgnięciu do słowa wskazanego przez grupę 3 ostatnich bitów adresu.

W metodzie skojarzeniowej (ang. associative mapping) dopuszcza się, aby każdy blok mógł

być przypisany do dowolnej linii pamięci kieszeniowej. W naszym przykładzie mamy 8192 = 2

bloków co oznacza konieczność wydłużenia etykiety do 13 bitów, a długości linii do s =

13 + 8∙8

= 77 bitów (patrz wzór 2 wyżej). Schemat takiej pamięci pokazano na rysunku 9.15.

1
2

nr słowa

etykieta

w bloku

13 bitów

3 bity

127

adres pamięci operacyjnej

i+1

i+2

77 bitów

8191

Rysunek 9.15. (a) Odwzorowanie bloków pamięci operacyjnej na pamięć kieszeniową w metodzie

skojarzeniowej; (b) odpowiadająca jej struktura adresu pamięci operacyjnej.

Sprawdzenie czy w tak zorganizowanej pamięci znajduje się zawartość wytworzonego adresu

polega na przejrzeniu wszystkich linii w celu stwierdzenia czy znajduje się tam linia z
poszukiwaną etykietą. Jest to czasochłonne i znacznie spowolniłoby działanie pamięci. Dlatego
do realizacji sprawdzania obecności linii o zadanej etykiecie używa się tzw. pamięci
skojarzeniowej albo asocjacyjnej, która dała nazwę całej metodzie.

Pamięć asocjacyjna jest to pamięć RAM (w naszym przykładzie jej rozmiary to 128 słów 13

bitowych – bo tyle jest etykiet) z dodatkowymi wejściami w liczbie równej ilości bitów słowa tej
pamięci (u nas: 13) oraz dodatkowymi wyjściami odpowiedzi w liczbie równej ilości słów

Pamięć (część 2)

pamięci (u nas 128). Działa ona w ten sposób, że generuje na wyjściu numer i jedynkę, jeżeli w i-
tym słowie znajduje się podana na wejścia kombinacja bitów (tzn. generuje kod 1 z n; tu 1 z
128). Jeżeli wszystkie wyjścia pamięci asocjacyjnej skierujemy do kodera, to na jego wyjściu
uzyskamy zakodowany binarnie numer linii pamięci kieszeniowej, pod którym znajduje się
poszukiwany blok. Jeżeli na wyjściu pamięci asocjacyjnej będą same zera, to oznacza to
chybienie i wtedy pamięć kieszeniowa nie jest odczytywana (patrz rysunek 9.16).

128

Pamięć asocjacyjna

Koder

128×13b

Rysunek 9.16. Układ testujący zawartość pamięci kieszeniowej

Wadą tej metody jest wysoki koszt pamięci asocjacyjnej, który na dodatek szybko rośnie wraz

ze wzrostem pojemności pamięci. Można wtedy posłużyć się zmodyfikowaną metodą
skojarzeniową.

W zmodyfikowanej metodzie skojarzeniowej (ang. set-associative mapping) rozmiary

pamięci asocjacyjnej nie są tak duże, a nawet można z niej zrezygnować. Generalnie metoda
polega na zmniejszeniu ilości linii pamięci kieszeniowej kosztem ich wydłużenia. Dzieje się tak
przez umieszczenie w jednej linii wielu bloków. Z daną linią mogą być skojarzone tylko
określone bloki (podobnie jak w metodzie bezpośredniej). Miejsce ich zapisu wewnątrz linii jest
dowolne. Przykładowa realizacja dla naszego przykładu z dwoma blokami w linii pokazana jest
na rysunku 9.17.

blok0

blok1 0

blok 2

blok3 1

nr linii

pamięci nr słowa

etykieta kieszeniowej w bloku

7 bitów 6 bitów 3 bity

blok 126

blok 127 63 adres pamięci operacyjnej

64
65

2 × 71 bitów

8191

Rysunek 9.17. Odwzorowanie bloków pamięci operacyjnej na pamięć kieszeniową w zmodyfikowanej

metodzie skojarzeniowej (a); odpowiadająca jej struktura adresu pamięci operacyjnej (b)

Pojemność pokazanej pamięci wynosi 64 linie142 bitowe. Z zasady konstrukcji tego rodzaju

pamięci wynika, że długość linii powinna wynosić 70 bitów (ze względu na podobieństwo do
metody bezpośredniej). Dodatkowy, 71 bit jest potrzebny, aby oznaczyć miejsce bloku w linii:
przy dwóch blokach wystarczy na to 1 bit. Liczba ta pomnożona przez 2 (dwa bloki w linii) daje
142.

Podstawową zaletą te metody jest możliwość wyeliminowania całkowicie drogiej pamięci

asocjacyjnej.

Pamięć (część 2)

Opiszemy teraz algorytmy wymiany zawartości pamięci kieszeniowej. Wymiana taka ma

miejsce wtedy, gdy procesor żąda dostępu do komórki pamięci, której nie ma w pamięci
kieszeniowej. W metodzie bezpośredniej wymian zachodzi pomiędzy dwoma określonymi
blokami. W pozostałych metodach istnieje możliwość wyboru bloku, który ma zostać usunięty z
pamięci kieszeniowej, aby w zwolnione miejsce zapisać potrzebny blok. Wyboru dokonuje się
stosując jeden z trzech algorytmów:

1. Algorytm usuwania najdłużej nieużywanego bloku: LRU (ang. least recently used). Jest on

stosowany dla zmodyfikowanej metody skojarzeniowej. Jeżeli przez p oznaczymy liczbę
bloków zapisanych w jednej linii, to algorytm ten wymaga dopisania dodatkowych log

bitów na blok. W naszym przykładzie p = 2, co daje 1 dodatkowy bit. Początkowo wszystkie
bity są zerowane. Trafienie w blok ustawia wartość bitu tego bloku na jeden. Przy
konieczności wymiany usuwa się blok z zerowym bitem. Trafienie w blok, który już ma
ustawioną jedynkę ustawia 0 w drugim bloku. Jeżeli bloków w linii jest więcej, to na
dodatkowych bitach organizuje sie licznik trafień. Polityka podbijania i obniżania wartości
liczników jest taka jak dla jednego bitu. W przypadku, gdy bloków, które spełniają kryteria
usunięcia jest więcej jak jeden wybiera się przypadkowy z nich.

2. Algorytm usuwania bloku najdłużej przebywającego w pamięci: FIFO (ang. first in firdt out).

Jego implementacja wymaga zainstalowania dodatkowego pola, w którym dla każdego bloku
zapisuje się numer wskazujący kolejność załadowania do pamięci kieszeniowej. Usuwany
jest blok z najmniejszą wartością numeru.

3. Algorytm usuwania najrzadziej używanego bloku; LFU (ang. least frequently used). Jego

implementacja wymaga zainstalowania dodatkowego pola, w którym dla każdego bloku
zapisuje się liczbę odwołań do tego bloku. Usuwany jest blok z najmniejszą wartością
licznika.

Ostatnim z listy zagadnień projektowych był problem aktualizacji zawartości pamięci

kieszeniowej i operacyjnej. Jest on znany również pod nazwą problemu synchronizacji
zawartości obu rodzajów pamięci. Konieczność takiej synchronizacji wynika z dwóch powodów:

1. zawartość pamięci kieszeniowej może zostać zmieniona na skutek wykonywania programu,

podczas gdy odpowiadająca jej zawartość pamięci operacyjnej pozostanie nie zmieniona;

2. zawartość pamięci operacyjnej może zostać zmieniona w wyniku transmisji realizowanych

przez DMA bądź inne urządzenie zewnętrzne, podczas gdy odpowiadająca jej zawartość
pamięci kieszeniowej pozostanie nie zmieniona.

Aby utrzymać stan spójności (koherentność) pamięci należy aktualizować zawartość obu

pamięci. Można dokonywać tego po każdej zmianie. Ten sposób nosi nazwę zapisu
natychmiastowego (ang. write through). Jego wadą jest spowolnienie działania systemu.
Alternatywą są metody: powtórnego zapisu (ang. write back lub copy back) oraz
natychmiastowej sygnalizacji (ang. write once). Pierwsza z nich polega na utrzymywaniu dla
każdego bloku 1-bitowego wskaźnika aktualizacji (ang. update). Zapis do bloku ustawia ten
wskaźnik na 1. Przy usuwaniu bloku bada się wskaźnik i zapisuje się do pamięci operacyjnej
wyłącznie bloki z ustawionym wskaźnikiem. Pozostałe są po prostu nadpisywane.

Metoda natychmiastowej sygnalizacji stosowana jest w systemach wieloprocesorowych i jej

omawianie wykracza poza ramy tego opracowania.

Pamięć (część 2)

Na zakończenie omawiania zagadnień związanych z pamięcią kieszeniową powiedzmy kilka

słów o wydajności pamięci operacyjnej wspartej pamięcią kieszeniowa. Miarą wydajności jest
tzw. współczynnik trafień h (ang. hit ratio) definiowany jako procentowy udział odwołań do tych
komórek pamięci, które zostały znalezione w pamięci kieszeniowej w stosunku do wszystkich
odwołań. Jednocześnie przez współczynnik chybień rozumie się wielkość 1 – h. Wprowadzenie
powyższych określeń pozwala zdefiniować średni czas dostępu w systemie z pamięcią
kieszeniową jako:

= t

+ (1-h)∙t

gdzie t

jest czasem dostępu pamięci kieszeniowej, a t

jest czasem dostępu pamięci operacyjnej.

0,9

q=64

q=16

0,6

q=8

0,3

10 15 20 (KB) pojemność

pamięci

kieszeniowej

Rysunek 9.18. Zależność współczynnika trafienia od pojemności pamięci kieszeniowej

Na rysunku 9.18 pokazano zależność współczynnika trafień od pojemności pamięci

kieszeniowej zmierzone dla komputera PDP 11. Parametrem jest wielkość bloku pamięci (q). Jak
wynika z tego rysunku wartość współczynnika początkowo rośnie wraz ze wzrostem pojemności
pamięci. Jednak powyżej pewnej granicy nie ma sensu dalsze zwiększanie pojemności pamięci
kieszeniowej, ponieważ wartość współczynnika trafień przyrasta już bardzo niewiele. Powodem
może być osiągnięcie takiego stanu, w którym w pamięci kieszniowej mieści się całość instrukcji
i danych, na których w danym momencie operuje program.

Document Outline