A. Myśliński – materiały pomocnicze do wykładu ASK

1

Wykład 9

Pamięci komputerów

1. Przegląd systemów pamięci komputerowych

Pamięć komputera jest zorganizowana hierarchicznie. Obejmuje ona:

•

rejestry (rozmiar: kilkaset B czas dostępu < 1ns),

•

pamięć podręczną (na różnych poziomach: L1 – kilkanaście kB, kilka ns, L2,

L3 – kilka MB, kilka ns),

•

pamięć główną (DRAM – dynamic random access memory, kilka GB,

kilkadziesiąt ns),

•

pamięć zewnętrzną (dysk twardy, kasety ZIP, dysk optyczny, taśma

magnetyczna – kilkaset GB, kilka ms).

Podstawowe własności komputerowych systemów pamięciowych:

a)

Położenie – procesor, pamięć wewnętrzna (główna), pamięć zewnętrzna
(pomocnicza)

b)

Pojemność – rozmiar słowa (8,16,32 bity), liczba słów (liczba bajtów)

c)

Jednostka transferu – słowo, blok

d)

Sposób dostępu

Dostęp sekwencyjny – rekordy; dostęp w sekwencji liniowej;

Dostęp bezpośredni – realizowany przez dostęp do najbliższego
otoczenia po którym następuje sekwencyjne szukanie;

Dostęp swobodny - pojedyncze słowa w pamięci są dostępne
bezpośrednio

za

pomocą

wbudowanych

układów

logicznych

adresowania.

Dostęp skojarzeniowy – rodzaj dostępu swobodnego

e)

Wydajność

Czas dostępu, czas cyklu, szybkość transferu

f)

Rodzaj fizyczny

Pamięć półprzewodnikowa, magnetyczna, optyczna, magnetooptyczna

g)

Własności fizyczne

Ulotna/nieulotna

Wymazywalna/niewymazywalna

h)

Organizacja – fizyczne uporządkowanie bitów w celu uformowania słów

1.2 Półprzewodnikowa pamięć główna

Komórka pamięci jest podstawowym elementem pamięci półprzewodnikowej. Każda
komórka pamięci półprzewodnikowej ma dwa stabilne stany służące do reprezentowania
liczb binarnych 1 i 0, umożliwia zapis (przynajmniej jednokrotny) i/lub odczyt.
Najczęściej komórka ma 3 końcówki funkcyjne służące do przenoszenia sygnału
elektrycznego:

•

końcówka wyboru – służy do wybierania komórki pamięci w celu odczytu lub zapisu

•

końcówka sterowania – umożliwia wskazanie rodzaju operacji (zapis lub odczyt). W
przypadku zapisu przez inną końcówkę wprowadzany jest sygnał elektryczny, który
ustala stan komórki na 1 lub 0. W przypadku odczytu ta sama końcówka służy do
wyprowadzania sygnału o stanie komórki.

A. Myśliński – materiały pomocnicze do wykładu ASK

2

a)

Sterowanie

b)

Sterowanie

Wejście

Wybór

danych

Wybór

Odczyt

KOMÓRKA

KOMÓRKA

Rys. 9.1.1. Działanie pojedynczej komórki pamięci: a) zapis, b) odczyt

Rodzaje pamięci półprzewodnikowych zebrano w

Rodzaj pamięci

Kategoria

Wymazywanie

Sposób zapisu

Ulotność

RAM - Pamięć o dostępie
swobodnym

odczyt

zapis

elektryczne, na

poziomie bajta

elektryczny

ulotna

ROM – Pamięć stała

tylko

odczyt

niemożliwe

maski

nieulotna

Programowalna pamięć stała
PROM

elektryczny

EPROM

wymazywalna

PROM

głównie

odczyt

światłem UV, na

poziomie mikroukładu

Pamięć błyskawiczna

elektrycznie , na

poziomie bloku

Elektrycznie wymazywalna
PROM (EEPROM)

elektrycznie , na

poziomie bajta

Tabela 9.1.1 Rodzaje pamięci półprzewodnikowych.

Wszystkie pamięci z Tabeli 9.1.1 są pamięciami o dostępie swobodnym. Cechy pamięci:

a)

RAM (Random Access Memory) – pamięć ulotna

•

Możliwe odczytywanie danych z pamięci, zapis do niej nowych danych – za pomocą
sygnałów elektrycznych

•

Ulotność danych – pamięć RAM musi mieć źródło stałego zasilania. Jeśli zasilanie
jest przerwane, dane są tracone

•

Wymazywanie elektryczne, na poziomie bajta

•

Pamięci RAM można podzielić na:

Statyczne (SRAM)

•

wartości binarne są przechowywane za pomocą
przerzutnikowych konfiguracji bramek logicznych

•

zachowują tak długo dane, jak długo są zasilane

•

ulotne

•

statyczne pamięci RAM są nieco szybsze niż dynamiczne

Dynamiczne (DRAM)

•

wykonane z komórek, które przechowują dane podobnie jak
kondensatory przechowują ładunek elektryczny

A. Myśliński – materiały pomocnicze do wykładu ASK

3

•

wymagają okresowego odświeżania (układów odświeżania)

•

ulotne

•

dynamiczna pamięć RAM jest gęściej upakowana (mniejsze
komórki) i tańsza niż odpowiadająca jej statyczna pamięć RAM

b)

ROM (Read Only Memory) – zawierają trwały wzór danych który nie może być
zmieniony.

•

zastosowanie pamięci ROM:

mikroprogramowanie

podprogramy biblioteczne dla często używanych funkcji

programy systemowe

tablice funkcji

•

dane lub program na stałe pozostają w pamięci głównej i nigdy nie
wymagają ładowania z urządzeń pamięci wtórnej

•

pamięć ROM powstaje, jak wszystkie mikroukłady scalone, przy
czym dane są wbudowywane podczas procesu wytwarzania

c)

PROM – programowalna pamięć ROM; niewielkie rozmiary, nieulotna, zapis
jednokrotny realizowany elektrycznie i może być wykonany przez dostawcę lub przez
klienta już po wyprodukowaniu mikroukładu; do zapisu wymagane są specjalne
urządzenia

;

zapewniają elastyczność i wygodę

d)

EPROM – odczytywalna i zapisywalna elektrycznie; przed zapisem wszystkie komórki
muszą być wymazane

•

odczytywana i zapisywana elektrycznie

•

przed operacją zapisu wszystkie komórki muszą być wymazane
przez naświetlenie znajdującego się już w obudowie układu
promieniowaniem ultrafioletowym

•

proces wymazywania może być wykonywany wielokrotnie – każde
wymazanie trwa ok. 20 minut

•

nielotna

e)

Flash Memory – pamięć pośrednia pomiędzy EPROM i EEPROM

•

Wprowadzona po raz pierwszy w połowie lat 80.

•

Wymazywana elektrycznie (nawet w ciągu kilku sekund)

•

Możliwe

wymazywanie

bloków

pamięci

zamiast

całego

mikroukładu

•

Niemożliwe wymazywanie na poziomie bajtów

•

Wysoka gęstość upakowania (jeden tranzystor na bit)

f)

EEPROM – zapisywalna bez wymazywania poprzedniej zawartości

•

Może być zapisywana bez wymazywania poprzedniej zawartości;
aktualizowany jest tylko bajt (lub bajty) adresowane

•

Nieulotna

•

EEPROM jest mniej gęsto upakowana niż EPROM

1.3 Układy logiczne mikroukładów pamięciowych

Pamięć półprzewodnikowa jest w postaci obudowanego mikroukładu. Każdy mikroukład
zawiera zestaw komórek pamięci. Powszechne są mikroukłady o pojemności 4 MB,
wprowadzane są do użytku mikroukłady o pojemności 16 MB.

A. Myśliński – materiały pomocnicze do wykładu ASK

4

W hierarchicznym układzie pamięci występują współzależności między szybkością,
pojemnością a kosztem. Takie współzależności występują również kiedy rozpatrujemy
organizację komórek pamięci i funkcjonalne układy logiczne zawarte w mikroukładzie. W
przypadku pamięci półprzewodnikowych jednym z kluczowych problemów projektowych jest
liczba bitów danych, które mogą być jednocześnie zapisywane lub odczytywane. W
przypadku organizacji, w której fizyczne uporządkowanie komórek w układzie jest takie
samo, jak uporządkowanie logiczne (postrzegane przez procesor) słów w pamięci, komórki są
zorganizowane w postaci W słów B-bitowych. Natomiast w przypadku organizacji 1-bitowej
w określonym czasie zapisuje się lub odczytuje tylko jeden bit.

Rys. 9.1.2 Typowa pamięć DRAM 16MB.

Organizacja mikroukładów pamięciowych na przykładzie 16-megabitowej pamięci DRAM:

•

jednocześnie mogą być odczytywane lub zapisywane 4 bity

•

zespół pamięci zorganizowany w postaci 4 kwadratowych układów 2048 na 2048
elementów

•

elementy zespołu połączone przez linie poziome (wiersze) i pionowe (kolumny).
Każda linia pozioma jest połączona z końcówkami „wybór” każdej komórki w
wierszu, każda linia pionowa połączona jest z końcówkami „zapis/odczyt” każdej
komórki w kolumnie

•

linie adresowe dostarczają adres słowa, które ma być wybrane – łącznie potrzeba
log2W linii. W naszym przykładzie wymaganych jest 11linii w celu wybrania 1 z
2048 wierszy. Linie to doprowadzane są do dekodera wiersza mającego 11 linii
wejściowych i 2048 wyjściowych. Układ logiczny dekodera aktywuje jedną z 2048
linii zależnie od wzoru bitowego na 11 liniach wejściowych (211 = 2048).

•

Dodatkowe 11 linii adresu wybiera 1 z 2048 kolumn, przy czym na jedną kolumnę
przypadają 4 bity

•

11 sygnałom adresowym określającym adres wiersza w zespole, 11 pozostałym
sygnałom adresowym określającym adres kolumny towarzyszą sygnały:

wyboru adresu wiersza RAS

wyboru adresu kolumny CAS

umożliwiające sterowanie czasowe mikroukładu.

•

Wszystkie pamięci DRAM wymagają operacji odświeżania

A. Myśliński – materiały pomocnicze do wykładu ASK

5

1.4 Korekcja błędów

Rys 9.1.3 Działanie kodu korekcyjnego

W systemach pamięci półprzewodnikowych występują błędy. Można je podzielić na błędy:

•

Stałe – permanentny defekt fizyczny powodujący, że uszkodzona komórka lub
komórki pamięciowe nie są w stanie niezawodnie przechowywać danych, lecz
pozostają w stanie 0 lub 1, albo błędnie przeskakują między 0 a 1. mogą być
wywołane przez działanie ostrych narażeń środowiskowych, defekty produkcyjne lub
zużycie.

•

Przypadkowe – losowe i nieniszczące zjawisko, które zmienia zawartość jednej lub
wielu komórek pamięciowych, bez uszkodzenia samej pamięci. Mogą być
spowodowane przez problemy zasilania lub cząsteczki alfa.

Większość współczesnych systemów pamięci głównych zawiera układy logiczne
wykrywające i korygujące błędy. Gdy dane mają być wczytane do pamięci, przeprowadza się
na tych danych obliczenia, w celu utworzenia kodu do korekty. Zarówno kod jak i dane są
przechowywane. W rezultacie, jeśli ma być zapisane M-bitowe słowo danych, a kod ma
długość K bitów, to aktualna długość przechowywanego słowa wynosi M+K bitów.
Gdy uprzednio zmagazynowane słowo jest odczytywane, kod jest wykorzystywany do
wykrywania i ewentualnej korekty błędów. Generowany jest nowy zestaw K bitów kodowych
z M bitów danych, po czym porównuje się go z pobranymi bitami kodowymi. Porównanie
prowadzi do jednego z 3 wyników:

•

Nie wykryto błędów

•

Wykryto błąd, którego korekta jest możliwa – bity danych i bity korekty błędu są
doprowadzane do układu korektora, który tworzy poprawiony zestaw M bitów
przeznaczony do wysłania

•

Wykryto błąd niemożliwy do poprawienia – stan ten jest zgłaszany.

Kody funkcjonujące w ten sposób są określane jako kody korekcyjne. Kod jest
charakteryzowany przez liczbę błędów w słowie którą może on wykryć i
poprawić.Najprostszym kodem jest kod Hamminga, opracowany przez Richarda Hamminga
z Bell Laboratories. Oparty jest o bity parzystości.

A. Myśliński – materiały pomocnicze do wykładu ASK

6

Bitem parzystości nazywamy bit kontrolny, który przyjmuje wartość 1, gdy liczba jedynek w
przesyłanej wiadomości jest nieparzysta lub 0, gdy odwrotnie. Innymi słowy – bit parzystości
sprawia, że wiadomość ma zawsze parzystą liczbę jedynek.

Rys. 9.1.4. Diagramy Venna.

Ponieważ błąd może wystąpić w każdym z M bitów danych lub K bitów kontrolnych
zachodzi związek:

2

K

– 1 ≥ M + K

określający liczbę bitów kontrolnych wymaganą do skorygowania błędu 1 bitowego w słowie
zawierającym M bitów danych. Na przykład 8 bitów danych wymaga 4 bitów kontrolnych.
Rozważmy przykład wyznaczania kodu Hamminga w przypadku transmisji słów 8 bitowych
na następującym przykładzie:

Przykład 1. Załóżmy, że 8 bitowym słowem danych zapisanym w pamięci jest X=001 110
01. Posługując się algorytmem Hamminga określ bity kontrolne jakie powinny być zapisane
w pamięci wraz z tym słowem danych.

•

Bity danych i bity kontrolne są aranżowane w postaci słów 12 bitowych.

•

Pozycje bitowe których numery są potęgą 2 są wyznaczone jako bity kontrolne. Bity
kontrolne są wyznaczone następująco:

C1 = D1

⊕

D2

⊕

D4

⊕

D5

⊕

D7

C2 = D1

⊕

D3

⊕

D4

⊕

D6

⊕

D7

C4 = D2

⊕

D3

⊕

D4

⊕

D8

C8 = D5

⊕

D6

⊕

D7

⊕

D8

o

Symbol

⊕

oznacza operację EXOR (LUB wyłączające) zdefiniowaną

następująco

P Q P XOR Q

0

0

0

0

1

1

1

0

1

1

1

0

A. Myśliński – materiały pomocnicze do wykładu ASK

7

•

Każdy bit kontrolny działa na pozycji bitu danych której numer zawiera 1 w
odpowiedniej pozycji kolumny. Pozycja bitowa n jest sprawdzana przez bity C

i

takie że

ich suma ∑

i

= n.

Dla słowa wejściowego X bity kontrolne mają wartość:

C1 = 1

⊕

0

⊕

1

⊕

1

⊕

0 = 1

C2 = 1

⊕

0

⊕

1

⊕

1

⊕

0 = 1

C4 = 0

⊕

0

⊕

1

⊕

0 = 1

C8 = 1

⊕

1

⊕

0

⊕

0 = 0

Sekwencja C8C4C2C3=0111 tworzy kod Hamminga dla słowa X. Załóżmy, że bit danych 3
zawiera błąd i jest zmieniony z 0 na 1. Po ponownym przeliczeniu bitów kontrolnych mamy:

C1 = 1

⊕

0

⊕

1

⊕

1

⊕

0 = 1

C2 = 1

⊕

1

⊕

1

⊕

1

⊕

0 = 0

C4 = 0

⊕

1

⊕

1

⊕

0 = 0

C8 = 1

⊕

1

⊕

0

⊕

0 = 0

Gdy nowe bity kontrolne porównamy ze starymi utworzymy słowo syndrom:

C8 C4 C2 C1

0

1

1

1

⊕

0

0

0

1

0

1

1

0

W słowie – syndrom 0 wskazuje na zgodność bitów na obu wejściach, 1 na niezgodność.
Ponadto:

Jeśli syndrom zawiera same 0 to znaczy, że nie został wykryty żaden błąd

Jeśli syndrom zawiera jedną i tylko jedną 1 błąd wystąpił w jednym z bitów
kontrolnych. Korekta jest niepotrzebna.

Jeśli syndrom zawiera więcej niż jedną 1 to wartość numeryczna syndromu wskazuje
pozycję błędnego bitu danych. Korekta polega na inwersji tego bitu.

W przykładzie wynikiem porównania jest 0110 co wskazuje, że pozycja bitowa 6 zawierająca
bit danych 3 jest błędna. Rozważania powyższe zostały zebrane w tabeli:

Pozycja
bitowa

12

11

10

9

8

7

6

5

4

3

2

1

Numer
pozycji

1100

1011

1010

1001

1000

0111

0110

0101

0100

0011

0010

0001

Bit
danych

D8

D7

D6

D5

D4

D3

D2

D1

Bit
kontrolny

C8

C4

C2

C1

Słowo
zapisane
jako

0

0

1

1

0

1

0

0

1

1

1

1

Słowo
pobrane
jako

0

0

1

1

0

1

1

0

1

1

1

1

Numer
pozycji

1100

1011

1010

1001

1000

0111

0110

0101

0100

0011

0010

0001

Bit
kontrolny

0

0

0

1

Tabela 9.1.2. Obliczanie bitów kontrolnych.

A. Myśliński – materiały pomocnicze do wykładu ASK

8

Wykład 10

Pamięć podręczna – budowa, podstawy działania

2. Pamięć podręczna (cache)

Pamięć podręczna - warstwa hierarchii pamięci umieszczona na płycie głównej pomiędzy
rejestrami i pamięcią operacyjną. Stanowi bufor dla pamięci operacyjnej. Niewidoczna w
użytkowym modelu programowym (współcześnie oprogramowanie użytkowe może mieć
ograniczoną kontrolę nad pracą kieszeni). 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.

•

Optymalne wykorzystanie pamięci podręcznej ma kluczowe znaczenie dla
wydajności programów

•

Nie ma bezpośrednich (z poziomu programu lub kompilatora) sposobów sterowania
wykorzystaniem pamięci podręcznej

Rys 9.2.1 Pamięc podręczna i pamięc główna.

Rys 9.2.2. Struktura pamięci podręcznej i pamięci głównej.

Organizacja pamięci podręcznej:

•

linie pamięci o pojemności kilku słów (np. 64B, 128B)

A. Myśliński – materiały pomocnicze do wykładu ASK

9

•

odwzorowanie obszarów (bloków) pamięci głównej w linie pamięci podręcznej

o

statyczne – bezpośrednie, direct mapped (każdy blok ma swoją linię)

o

dynamiczne:

skojarzeniowe, fully associative (każdy blok może być odwzorowany w
dowolną linię całej pamięci)

sekcyjno skojarzeniowe, set associative (każdy blok może być
odwzorowany w dowolną linię z pewnej grupy)

architektura harvardzka: osobna pamięć podręczna dla danych,

osobna dla kodu

Rys 9.2.3. Typowa organizacja pamięci podręcznej.

2.1. Zasada działania pamięci podręcznej

•

Pamięć główna składa się z 2

n

adresowalnych słów przy czym każde słowo ma

jednoznaczny adres n-bitowy. Pamięć ta składa się z pewnej liczby bloków o stałej
długości zawierających K słów każdy. Liczba bloków M = 2

n

/K.

•

Pamięć podręczna zawiera C wierszy zawierających K słów każdy przy czym liczba
wierszy jest dużo niższa niż liczba bloków pamięci głównej tj C << M.

•

W każdej chwili pewien zespół bloków pamięci głównej pozostaje w wierszach pamięci
podręcznej.

o

Ponieważ bloków jest więcej niż wierszy to określony wiersz nie może być
przypisany trwale określonemu blokowi. Każdy wiersz zawiera znacznik
(część adresu pamięci głównej) określający który blok jest aktualnie
zapisywany.

A. Myśliński – materiały pomocnicze do wykładu ASK

10

Pamięć podręczna - zasada działania:

•

Przy każdym odwołaniu procesor-pamięć 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 przesłana do procesora

„po drodze” dana wraz z jej adresem jest zapisywana do kieszeni

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

2.2. Lokalność odniesień

Przydatność pamięci podręcznej zależy od stopnia lokalności odniesień do danych w
programie:

lokalność czasowa: dane raz użyte niedługo zostaną użyte ponownie (warto je
zachować w szybszej pamięci)

lokalność przestrzenna: jeśli w programie użyto jakichś danych to za chwile zostaną
użyte dane sąsiadujące w pamięci (warto pobierać do pamięci podręcznej całe bloki)

Miarą lokalności odniesień w trakcie wykonywania programu jest współczynnik trafień (hit
ratio) czyli proporcja trafień do chybień.

Zastosowanie pamięci podręcznej przynosi zazwyczaj wzrost wydajności, gdyż wiele
programów ma w sposób naturalny wysoki stopień lokalności odniesień (w praktyce
stosunek trafień do chybień sięga nawet powyżej 90%)

Chcąc zwiększać wydajność programów dzięki optymalnemu wykorzystaniu pamięci
podręcznej należy maksymalizować stopień lokalności odniesień w kodzie (grupować
odniesienia do tych samych i sąsiadujących danych w jedno miejsce)

2.3 Elementy projektowania pamięci podręcznych

Rozmiar pamięci podręcznej

Metoda zapisu

Odwzorowanie

Zapis jednoczesny

Bezpośrednie

Zapis opóźniony

Skojarzeniowe

Zapis jednorazowy

Sekcyjno - skojarzeniowe

Algorytm zastępowania

Rozmiar wiersza

Najdawniej używany (LRU)

Liczba pamięci podręcznych

FIFO

Jedno lub dwu poziomowa

Najrzadziej używany (LFU)

Jednorodna lub podzielona

Przypadkowy

Tabela 9.2.1 Elementy projektowania pamięci podręcznych

2.3.1 Rozmiar pamięci podręcznej

Kompromis pomiędzy koszt/bit oraz krótki czas dostępu (rozmiar vs
szybkość)

A. Myśliński – materiały pomocnicze do wykładu ASK

11

2.3.2 Funkcja odwzorowania (bloków pamięci głównej w wiersze pamięci podręcznej)

Metoda bezpośrednia

Kieszeń bezpośrednio adresowana - budowa

•

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 nie intuicyjne działanie:

o

najmniej znaczące bity adresu służą do wyboru bajtu z linii

o

„środkowa”, mniej znacząca część adresu procesora służy jako adres pamięci
RAM; na jej podstawie w każdym cyklu dostępu jest wybierana pojedyncza
linia

o

każda linia zawiera znacznik adresu i dane

•

Pole znacznika adresu zawiera bardziej znaczącą część adresu danej zapamiętanej w
polu danych - jest ono porównywane z najbardziej znaczącą częścią adresu
wystawionego przez procesor.

Kieszeń bezpośrednio adresowana - działanie:

•

W każdym cyklu następuje wybór jednej linii, zaadresowanej przez mniej znaczącą
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

o

w polu znacznika zostaje zapisana najbardziej znacząca część adresu

o

w polu danych zostają zapamiętane dane odczytane z pamięci

Kieszeń bezpośrednio adresowana - cechy:

•

Niskie koszty, duża pojemność, wysoka wydajność.

•

Algorytm

zastępowania

linii

wymuszony

przez

budowę

kieszeni:

o

dane spod określonego adresu mogą znaleźć się wyłącznie w jednej, z góry
określonej linii kieszeni

o

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ągł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ż 2 *
pojemność kieszeni (lepiej niż w przypadku kieszeni pełno asocjacyjnej).

A. Myśliński – materiały pomocnicze do wykładu ASK

12

Rys. 9.2.4. Organizacja pamięci podręcznej o bezpośrednim odwzorowaniu.

Metoda skojarzeniowa (asocjacyjna)

Kieszeń pełno asocjacyjna – budowa

•

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.

•

Porównanie działania : książka telefoniczna

wyszukujemy nazwisko

odczytujemy numer telefonu

nie zwracamy uwagi na położenie nazwiska w książce (nr strony,
kolumnę)

•

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 następnymi architekturami

A. Myśliński – materiały pomocnicze do wykładu ASK

13

Rys. 9.2.5. Odwzorowanie a) bezpośrednie b) skojarzeniowe.

•

Wyznaczanie linii do zastępowania - LRU lub losowe

LRU (Least Recently Used) - 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ędą kończyły
się chybieniami.

Kieszeń pełnoasocjacyjna - budowa:

•

Dane są przechowywane w kieszeni nie w postaci pojedynczych słów czy bajtów, lecz
bloków, zazwyczaj o długości 4* 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ą.

A. Myśliński – materiały pomocnicze do wykładu ASK

14

•

Najmniej znacząca część adresu służy do wyboru bajtu lub słowa z linii. Kolejne, bity
adresu są używane do stwierdzenia, czy poszukiwana dana znajduje się w kieszeni.

Metoda sekcyjno - skojarzeniowa

Kieszeń zbiorowo-asocjacyjna - cechy:

•

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łno asocjacyjna

•

Liczba bloków jest zwana stopniem asocjacyjności kieszeni.

•

Kieszeń zbiorowo-asocjacyjna może być rozpatrywana również jako złożenie pewnej
liczby kieszeni pełno asocjacyjnych.

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żyć algorytmu LRU, który przy małej liczbie linii daje się
zrealizować sprzętowo

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.

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ść używa się kieszeni bezpośrednio
adresowanych lub dwudrożnych zbiorowo-asocjacyjnych.

•

Kieszenie pełno asocjacyjne nie są stosowane do przechowywania danych i kodu,
niekiedy znajdują one zastosowanie w innych miejscach komputera.

A. Myśliński – materiały pomocnicze do wykładu ASK

15

Rys. 9.2.6. Odwzorowania wielodrożne.

2.3.3 Algorytm zastępowania

Gdy do pamięci podręcznej jest wprowadzany nowy blok jeden z istniejących bloków musi
być zastąpiony. W przypadku odwzorowania 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 oraz sekcyjno – skojarzeniowej wymagany jest algorytm zastępowania.
Algorytm taki jest wbudowany w postaci sprzętowej aby zapewnić dużą szybkość.

•

Algorytm LRU (least recently used – najdawniej używany) – 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.

•

Algorytm FIFO (first in first out – pierwszy wchodzi pierwszy wychodzi) - polega na

zastępowaniu tego bloku w sekcji który najdłużej pozostawał w pamięci podręcznej. Jest
łatwy do wdrożenia w postaci metody cyklicznego buforowania.

•

Algorytm LFU (last frequently used – najrzadziej używany) – polega na zastępowaniu

bloku w sekcji którego dotyczyło najmniej odniesień.

•

Algorytm przypadkowy – losowy wybór wśród kandydujących wierszy

2.3.4 Algorytm zapisu

•

Zapis jednoczesny (write through) – 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. Wadą tej metody jest generowanie znacznego przepływu
danych do pamięci co może spowodować powstanie „wąskich gardeł”.

A. Myśliński – materiały pomocnicze do wykładu ASK

16

•

Zapis opóźniony (write back) – aktualizuje się tylko pamięć podręczną. Gdy następuje taka

aktualizacja określana jest wartość bitu aktualizacji (UPDATE) skojarzonego z wierszem
pamięci podręcznej. Jeśli następnie blok jest zastępowany to podlega on wpisaniu do
pamięci głównej tylko wtedy gdy ustanowiony jest bit UPDATE.

Problem spójności pamięci podręcznej – powstaje gdy pamięć główna jest wspólna a więcej
niż jedno urządzenie (zwykle procesor) ma pamięć podręczną. Problem ten jest
rozwiązywany poprzez:

•

obserwowanie magistrali z jednoczesnym zapisem

•

sprzętowe zapewnienie przezroczystości

•

wyłączenie pamięci ze współpracy z pamięcią podręczną (tylko część pamięci głównej
jest wspólna dla więcej niż jednego procesora i ta część jest wyłączona ze współpracy z
pamięcią podręczną)

2.3.5 Rozmiar wiersza

Rozmiar wiersz jest uzależniony od wielkości bloku. Dobór wielkości bloku uzależnia się od
zapewnienia możliwie wysokiego współczynnika trafienia. Gdy zwiększamy rozmiar bloku
od bardzo małego do dużego współczynnik trafienia wzrasta. Przy dalszym zwiększaniu
rozmiaru bloku współczynnik trafienia zaczyna maleć bo prawdopodobieństwo
wykorzystania nowo pobieranych informacji staje się mniejsze niż prawdopodobieństwo
ponownego użycia informacji która jest zastępowana.

2.3.6 Liczba pamięci podręcznych.

a) Pamięci podręczne wielopoziomowe

•

pamięć podręczna L1 – wewnętrzna pamięć podręczna

•

pamięć podręczna L2 – zewnętrzna pamięć podręczna

•

pamięć podręczna L3 - zewnętrzna pamięć podręczna

b) Jednolita a podzielona pamięć podręczna

•

Pamięć podzielona – jedna część przeznaczona na przechowywanie rozkazów a

druga na przechowywanie danych

•

Pamięć jednolita – jedna pamięć do przechowywania zarówno danych jak i

adresów

Wyższy współczynnik trafienia niż pamięć podzielona

Literatura:
1)

W. Stallings, Organizacja i architektura systemu komputerowego, WNT, Warszawa,
2008.

2)

S.H.A. Clarke, W sercu PC, Helion, Gliwice, 2003.