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.