Pamięć wewnętrzna

Kodowanie Hamminga,
pamięć cache, pamięć DRAM

Wyższa Szkoła Biznesu
Architektura i organizacja
komputerów
Wykład 6

Kodowanie Hamminga

Na rysunku (następny slajd) do zilustrowania wykorzystania tego

kodu w odniesieniu do słów 4-bitowych (M=4) zostały

wykorzystane wykresy Venna.
W przypadku trzech krzyżujących się okręgów mamy do

czynienia z siedmioma przedziałami. Przypisujemy 4 bity danych

przedziałom wewnętrznym (rys. a). Pozostałe przedziały są

wypełniane tzw. bitami parzystości. Bit parzystości jest

wybierany tak, że całkowita liczba jedynek w jego okręgu jest

parzysta. Wobec tego, ponieważ okrąg A zawiera 3 jedynki

danych, bit parzystości w tym okręgu jest ustawiany na 1. Jeśli

teraz błąd spowoduje zmianę jednego z bitów danych (rys. c),

jest on łatwy do wykrycia. Sprawdzając bity parzystości,

wykrywamy sprzeczności w okręgach A i C, ale nie w B. Tylko

jeden z 7 przedziałów znajduje się w A i C, ale nie w B. Błąd

może więc być poprawiony przez zmianę tego bitu.

Kod korekcyjny

Hamminga

- wykres Venna

Przykład

W celu wyjaśnienia wykorzystanej koncepcji opracujemy

kod, który może posłużyć do wykrycia i skorygowania 1-

bitowego błędu w słowach 8-bitowych.
Na wstępie określmy wymaganą długość kodu. Zgodnie z

rys. (ostatni rysunek na poprzednim wykładzie: Działanie

kodu

korekcyjnego)

logiczne

układy

porównujące

otrzymują na wejściu dwie wartości K-bitowe.
Porównanie bit po bicie jest przeprowadzane przy użyciu

bramki LUB wyłączne (exclusive-or-EXOR) o 2 ejściach.

Wynik jest określany jako słowo-syndrom. Tak więc, każdy

bit syndromu jest 0 lub 1 zależnie od tego, czy jest, czy też

nie ma zgodności bitów na dwóch wejściach.

Niezbędna ilość bitów

Słowo-syndrom ma więc K bitów i zakres

wartości 2

K

(pomiędzy 0 a 2

K

- 1). Wartość 0

wskazuje, że nie został wykryty żaden błąd, zaś

2

K

-1 wartości służy do wskazania błędu i jego

lokalizacji bitowej. Ponieważ błąd może wystąpić

w każdym z M bitów danych i K bitów

kontrolnych, musimy mieć

2

K

- 1 ≥ M + K

Równanie to określa liczbę bitów wymaganą do

skorygowania błędu 1-bitowego w słowie

zawierającym M bitów danych.

Ile liczb bitów kontrolnych jest

wymaganych w przypadku słów o

różnej długości ?

Równanie to określa liczbę bitów wymaganą do skorygowania
błędu 1-bitowego w słowie zawierającym M bitów danych.

Liczba

bitów

danych

Poprawianie

pojedynczego błędu

Poprawianie

pojedynczego,

wykrywanie

podwójnego błędu

Bity

kontrolne

% wzrostu

Bity

kontrolne

% wzrostu

8

4

50

5

62,5

16

5

31,25

6

37,5

32

6

18,75

7

21,875

64

7

10,94

8

12,5

128

8

6,25

9

7,03

256

9

3,52

10

3,91

Przykład cd.

Widzimy w tej tabeli, że słowo zawierające 8 bitów

danych wymaga 4 bitów kontrolnych. Dla wygody

chcielibyśmy generować syndrom 4-bitowy o

następujących własnościach.
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. Wówczas

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.

Obliczanie bitów

kontrolnych

W celu uzyskania takich własności bity danych i bity

kontrolne są aranżowane w postaci słowa 12-bitowego w

sposób pokazany na rys. na następnym slajdzie.
Pozycje bitowe są ponumerowane od 1 do 12. Pozycje

bitowe, których numery są potęgą 2, są wyznaczone jako

bity kontrolne. Bity kontrolne są obliczane następująco

(symbol  oznacza operację LUB wykluczające):

Rozkład bitów danych i

bitów kontrolnych

Każdy bit kontrolny działa na każdej

pozycji bitu danych, której numer zawiera

1 w odpowiedniej pozycji kolumny.
Tak więc pozycje bitowe danych 3, 5, 7, 9

i 11 zawierają człon 2

0

; pozycje bitowe 3,

6, 7 i 10 zawieraj ą człon 2

1

; pozycje

bitowe 5, 6, 7 i 12 - człon 2

2

, a pozycje

bitowe 9, 10, 11 i 12 - 2

3

.

Inaczej mówiąc, pozycja bitowa n jest

sprawdzana przez bity C

i

takie, że ∑i = n.

Na przykład pozycja 7 jest sprawdzana

przez bity znajdujące się na pozycjach 4,

2 i 1; zachodzi więc 4 + 2 + 1 = 7.

Przykład cd.

Sprawdźmy na przykładzie, jak funkcjonuje ten
schemat. Załóżmy, że 8-bitowym słowem wejściowym
jest 00111001, z bitem danych M1 na najbardziej
znaczącej pozycji. Obliczenia są następujące:

Załóżmy teraz, że bit danych 3 zawiera błąd i jest
zmieniony z 0 na 1. Po ponownym przeliczeniu bitów
kontrolnych mamy:

Wyznaczanie błędnej

pozycji

Gdy teraz nowe bity kontrolne porównamy ze starymi,

tworzymy słowo-syndrom:

Wynikiem jest 0110, co wskazuje, że pozycja bitowa 6 (M3),

zawierająca bit danych 3, jest błędna.
Na rysunku (następny slajd) są zilustrowane powyższe

obliczenia. Bity danych i bity kontrolne zostały odpowiednio

umieszczone w słowie 12-bitowym. Dzięki ułożeniu

numerów każdego z bitów danych w kolumny, jedynki w

każdym wierszu wskazują bity danych sprawdzane przez bit

kontrolny przypisany temu wierszowi.

Generowanie bitów

kontrolnych

Ponieważ wynik jest zmieniany tylko przez jedynki, tylko kolumny

zawierające jedynki zostały zakreślone dla identyfikacji. Bity kontrolne

mogą być następnie obliczone wzdłuż wierszy. Pokazano wyniki dla

pierwotnych bitów danych oraz dla bitów danych zawierających błąd.

SEC, SEC-DED

Omówiony właśnie kod jest znany jako kod poprawiania

pojedynczego błędu (ang. single-error-correcting - SEC).
Częściej pamięć półprzewodnikowa jest wyposażana w kod

poprawiania pojedynczego i podwójnego błędu (SEC-DED). Jak

były widać w tabeli (slajd nr 6 na początku wykładu), takie kody

wymagają jednego dodatkowego bitu w porównaniu z kodami

SEC.
Na rysunku (następny slajd) jest pokazane, jak działa taki kod,

znów dla przypadku 4-bitowego słowa danych.
Przedstawiona sekwencja ujawnia, że jeśli występują dwa błędy

(rys. c), procedura kontrolna jest błędna i pogarsza problem,

tworząc trzeci błąd (rys. e). W celu pokonania tej trudności,

dodany jest ósmy bit, taki że całkowita liczba jedynek na wykresie

jest parzysta. Dodatkowy bit parzystości umożliwia wychwycenie

błędu (rys. f).

Kod Hamminga SEC-DEC

Pamięć podręczna i

pamięć główna

Pamięci podręczne stosuje
się w celu uzyskania
pamięci o takiej szybkości,
jaką

mają

najszybsze

osiągalne

pamięci,

z

jednoczesnym uzyskaniem
dużego rozmiaru pamięci
w cenie tańszych rodzajów
pamięci
półprzewodnikowych.
Koncepcja

ta

jest

zilustrowana na rys.

Cache - zasada działania

Występuje tu względnie duża i wolniejsza pamięć główna

obok mniejszej i szybszej pamięci podręcznej.
Pamięć podręczna zawiera kopię części zawartości pamięci

głównej. Gdy procesor zamierza odczytać słowo w pamięci,

najpierw następuje sprawdzenie, czy słowo to nie znajduje się

w pamięci podręcznej. Jeśli tak, to słowo jest dostarczane do

procesora. Jeśli nie, to blok pamięci głównej zawierający

ustaloną liczbę słów jest wczytywany do pamięci podręcznej,

a następnie słowo jest dostarczane do procesora.
Ze względu na zjawisko lokalności odniesień, jeśli blok

danych został pobrany do pamięci podręcznej w celu

zaspokojenia pojedynczego odniesienia do pamięci, jest

prawdopodobne, że przyszłe odniesienia będą dotyczyły

innych słów zawartych w tym samym bloku.

Struktura pamięci

podręcznej

i pamięci głównej

Na rysunku (następny slajd) jest pokazana struktura

systemu pamięć podręczna/pamięć główna.
Pamięć główna składa się z 2

n

adresowalnych słów,

przy czym każde słowo ma jednoznaczny adres n-

bitowy.
Aby było możliwe odwzorowywanie pamięć ta składa

się z pewnej liczby bloków o stałej długości,

zawierających K słów każdy. Tak więc występuje

M=2

n

/K bloków. Pamięć podręczna zawiera C wierszy

zawierających K słów każdy, a liczba wierszy jest

znacząco mniejsza od liczby bloków w pamięci

głównej (C << M).

Struktura pamięci podręcznej i

pamięci głównej:

(a) pamięć główna; (b) pamięć

podręczna

Znaczniki

W każdej chwili, pewien zespół bloków pamięci

pozostaje w wierszach pamięci podręcznej.
Jeśli słowo w bloku pamięci jest odczytywane, to

odpowiedni blok jest przenoszony do jednego z

wierszy pamięci podręcznej.
Ponieważ bloków jest więcej niż wierszy, określony

wiersz nie może być jednoznacznie i trwale

przypisany określonemu blokowi. Każdy wiersz

zawiera w związku z tym znacznik określający, który

blok jest właśnie przechowywany. Znacznik jest

zwykle częścią adresu pamięci głównej, o czym

powiemy w dalszej części wykładu.

Odczyt

Na

rysunku

jest

pokazana

operacja

odczytu.
Procesor generuje adres

słowa, które ma być

odczytane, RA.
Jeśli słowo jest zawarte

w pamięci podręcznej,

jest

dostarczane

do

procesora.
W przeciwnym razie blok

zawierający to słowo jest

ładowany do pamięci

podręcznej, po czym

słowo jest dostarczane

do procesora.

Właściwości pamięci

podręcznych

Pojemność pamięci

Sposób zapisu

Rodzaj
odwzorowywania

jednoczesny

bezpośrednie

opóźniony

skojarzeniowe

jednokrotny

sekcyjno-skojarzeniowe

Rozmiar bloku

Algorytm wymiany

Liczba pamięci
podręcznych

najmniej

ostatnio

uzywany (LRU)

jedno- lub dwupoziomowa

pierwszy

wszedł

-

pierwszy wychodzi (FIFO)

jednolita

lub

rozszczepiona

najrzadziej używany (LFU)
swobodny

Rozmiar pamięci

podręcznej

Chcielibyśmy, żeby rozmiar pamięci podręcznej był na tyle

mały, żeby ogólny przeciętny koszt na bit był zbliżony do

tego kosztu samej pamięci głównej, oraz na tyle duży, żeby

ogólny przeciętny czas dostępu był zbliżony do czasu

dostępu samej pamięci podręcznej.
Im większa jest pamięć podręczna, tym większa jest też

liczba bramek służących do adresowania tej pamięci. W

rezultacie duże pamięci podręczne są nieco wolniejsze niż

małe - nawet jeśli są wykonane za pomocą tej samej

technologii układów scalonych i umieszczone w tym samym

miejscu w mikroukładzie i w obwodzie drukowanym.
Rozmiar pamięci podręcznej jest również limitowany

dostępną powierzchnią mikroukładu i obwodu drukowanego.

Funkcja odwzorowania

Ponieważ wierszy w pamięci podręcznej jest mniej

niż bloków pamięci głównej, wymagany jest

algorytm odwzorowywania bloków pamięci głównej

w wierszach pamięci podręcznej.
Ponadto potrzebne są środki do określania, który

blok pamięci głównej aktualnie zajmuje wiersz

pamięci podręcznej. Wybór funkcji odwzorowywania

dyktuje organizację pamięci podręcznej.
Mogą

być

wykorzystywane

trzy

metody:

bezpośrednia,

skojarzeniowa

i

sekcyjno-

skojarzeniowa.

Przykład

Omówimy je kolejno. W każdym przypadku rozpatrzymy

strukturę ogólną, a następnie przykład. Dla wszystkich

trzech przypadków przykład zawiera następujące elementy:

1. Pamięć podręczna może przechowywać 64 KB.
2. Dane są przenoszone między pamięcią główną a pamięcią

podręczną w blokach po 4 bajty. Oznacza to, że pamięć

podręczna jest zorganizowana w postaci 16K=2

14

wierszy

po 4 bajty każdy.

3. Pamięć główna składa się z 16 MB, przy czym każdy bajt

jest bezpośrednio adresowalny za pomocą 24-bitowego

adresu

(2

24

=16M).

Tak

więc,

aby

umożliwić

odwzorowywanie, możemy traktować pamięć główną jako

składającą się z 4M bloków po 4 bajty każdy.

Odwzorowanie

bezpośrednie

Najprostsza metoda, znana jako odwzorowanie

bezpośrednie,

polega

na

odwzorowywaniu

każdego bloku pamięci głównej na tylko jeden

możliwy wiersz pamięci podręcznej. Schemat tej

metody jest pokazany na rys. (następny slajd)
Odwzorowywanie jest wyrażane jako

i=j mod m

gdzie:

i - numer wiersza pamięci podręcznej,
j - numer bloku pamięci głównej,
m - liczba wierszy w pamięci podręcznej.

Organizacja pamięci

podręcznej o

bezpośrednim

odwzorowaniu

Organizacja pamięci

podręcznej o

bezpośrednim

odwzorowaniu

Funkcja odwzorowywania może być z łatwością realizowana

za pomocą adresu. W celu uzyskania dostępu do pamięci

podręcznej każdy adres pamięci głównej może być

widziany jako składający się z 3 pól.
Najmniej znaczące bity w określają jednoznacznie słowo lub

bajt w bloku pamięci głównej; w najnowocześniejszych

maszynach adres jest formułowany na poziomie bajtów.
Pozostałych s bitów określa jeden z 2

s

bloków pamięci

głównej. Układy logiczne pamięci podręcznej interpretują te

s bitów jako znaczniki w postaci s - r bitów (najbardziej

znacząca część) oraz pole linii złożone z r bitów. To ostatnie

pole identyfikuje jeden z m = 2

r

wierszy pamięci

podręcznej.

Wynik odwzorowania

Wynikiem tego odwzorowywania jest to, że bloki pamięci

głównej są przypisane do wiersza pamięci podręcznej

następująco:

Wykorzystanie części adresu jako numeru wiersza pozwala na

jednoznaczne odwzorowanie każdego bloku pamięci głównej w

pamięci podręcznej. Gdy blok jest właśnie wczytywany do

przypisanego wiersza, konieczne jest zaznaczenie danych, aby

odróżnić je od innych bloków, które mogą pasować do tego

wiersza. Do tego celu służą najbardziej znaczące bity s - r.

Przypisane bloki pamięci głównej

Wiersz pamięci podręcznej

0, m, ..., 2

S

-m

0

1, m + 1, ..., 2

S

-m + 1

1

...

...

m-1, 2m-1, ..., 2

S

- 1

m-1

Przykład: Operację

odczytu

System pamięci podręcznej jest prezentowany za pomocą

adresów 24-bitowych.
Czternastobitowy numer wiersza jest wykorzystywany jako

indeks dostępu do określonego wiersza w pamięci

podręcznej.
Jeśli 8-bitowy znacznik jest zgodny ze znacznikiem aktualnie

przechowywanym w tym wierszu, to 2-bitowy numer słowa

służy do wyboru jednego z 4 bajtów w tym wierszu. W

przeciwnym razie 22-bitowe pole obejmujące znacznik i

wiersz jest wykorzystywane do pobrania bloku z pamięci

głównej.
Adres użyty do tego pobierania składa się z tych 22 bitów

powiązanych z dwoma bitami zerowymi, tak więc na granicy

bloku są pobierane 4 bajty.

Metoda

odwzorowywania

bezpośredniego jest prosta i

tania przy wdrażaniu. Jej

główną wadą jest to, że dla

danego bloku istnieje stała

lokalizacja

w

pamięci

podręcznej.
W rezultacie, jeśli program

będzie się często odwoływał

do słów z dwóch różnych

bloków przypisanych do tego

samego wiersza, to bloki te

będą ciągle przenoszone do

pamięci

podręcznej,

co

obniży ogólną szybkość.

Przykład

odwzorowania

bezpośredniego

Odwzorowywanie

skojarzeniowe

Odwzorowywanie

skojarzeniowe

eliminuje

wady

odwzorowywania bezpośredniego, gdyż umożliwia ładowanie
każdego bloku pamięci głównej do dowolnego wiersza pamięci
podręcznej.
W tym przypadku sterujące układy logiczne pamięci
podręcznej interpretują adres pamięci po prostu jako znacznik
i pole słowa.
Pole znacznika jednoznacznie określa blok pamięci głównej. W
celu stwierdzenia, czy blok znajduje się w pamięci podręcznej,
sterujące układy logiczne pamięci podręcznej muszą
jednocześnie zbadać zgodność znacznika każdego wiersza. Na
rysunku jest pokazany taki właśnie schemat logiczny.

Organizacja w pełni

skojarzeniowej pamięci

podręcznej

Przykładowa pamięć z

odwzorowaniem

skojarzeniowym

Na kolejnym rysunku można będzie zobaczyć naszą przykładową

pamięć w wersji odwzorowywania skojarzeniowego.
Adres pamięci głównej składa się z 22-bitowego znacznika i 2-

bitowego numeru bajtu. W przypadku każdego wiersza pamięci

podręcznej 22-bitowy znacznik musi być przechowywany razem

z 32-bitowym blokiem danych.
W przypadku odwzorowywania skojarzeniowego blok do

zastąpienia jest wybierany elastycznie, kiedy nowy blok jest

wczytywany do pamięci podręcznej. Opracowano algorytmy

zastępowania służące do maksymalizacji współczynnika trafień,

które omówimy w dalszej części tego podrozdziału. Główną wadą

odwzorowywania skojarzeniowego są złożone układy wymagane

do równoległego badania znaczników wszystkich wierszy pamięci

podręcznej.

Przykład

odwzorowania

skojarzeniowego

Odwzorowywanie

sekcyjno-skojarzeniowe

Odwzorowywanie

sekcyjno-skojarzeniowe

stanowi

kompromis

łączący

zalety

odwzorowywania

bezpośredniego i skojarzeniowego; jest ono pozbawione

wad charakteryzujących te metody. W tym przypadku

pamięć podręczna jest dzielona na v sekcji, z których

każda składa się z k wierszy. Zależności są następujące:

m = v  k

i=j modulo v

gdzie:

i - numer sekcji pamięci podręcznej,
j - numer bloku pamięci głównej,
m - liczba wierszy pamięci podręcznej.

Odwzorowywanie

sekcyjno-skojarzeniowe

W

przypadku

odwzorowywania

sekcyjno-

skojarzeniowego blok B

j

może być odwzorowywany

na dowolny wiersz sekcji i.
W tym przypadku sterujące układy logiczne

pamięci podręcznej interpretują adres pamięci jako

trzy pola: znacznik, sekcja i słowo.
Za pomocą d bitów sekcji precyzuje się jedną z v =

2

d

sekcji, a s bitów znacznika w połączeniu z polem

sekcji określa jeden z 2

S

bloków pamięci głównej.

Na rysunku są przedstawione sterujące układy

logiczne pamięci podręcznej.

Dwudrożna sekcyjno-

skojarzeniowa organizacja

pamięci podręcznej

Przykład. Sekcyjno-

skojarzeniowa organizacja

pamięci podręcznej.

Na rysunku jest pokazana nasza
przykładowa

pamięć

w

wersji

odwzorowywania

sekcyjno-

skojarzeniowego z dwoma wierszami
w każdej sekcji; układ można określić
jako

dwudrożny

sekcyjno-

skojarzeniowy.

Przykład. Sekcyjno-

skojarzeniowa organizacja

pamięci podręcznej.

Za pomocą 13-bitowego numeru sekcji identyfikuje się

jednoznacznie określoną sekcję złożoną z 2 wierszy wewnątrz

pamięci skojarzeniowej. Określa się także numer bloku w

pamięci głównej, modulo 2

13

, co umożliwia odwzorowanie

bloków na wierszach. Tak więc bloki 000000, 00A000, ...,

FF1000 pamięci głównej są przypisane sekcji 0 pamięci

podręcznej.
Dowolny z tych bloków może być załadowany do jednego z

dwóch wierszy tej sekcji. Zauważmy, że żaden z dwóch bloków

przypisanych tej samej sekcji pamięci podręcznej nie ma

takiego samego numeru znacznika. W przypadku operacji

odczytu 13-bitowy numer sekcji jest wykorzystywany do

określenia, która sekcja ma być badana. Następnie jest

sprawdzana zgodność obu wierszy sekcji z numerem znacznika

adresu, do którego chcemy uzyskać dostęp.

Dwudrożne

odwzorowanie

sekcyjno-

skojarzeniowe

Ilość wierszy w sekcji

W krańcowym przypadku, gdy v=m, k=1, metoda

sekcyjno-skojarzeniowa redukuje się do odwzorowywania

bezpośredniego, a przy v=1, k=m - redukuje się do

odwzorowywania skojarzeniowego.
Wykorzystywanie dwóch wierszy na sekcję (v=m/2, k=2)

jest najbardziej powszechną organizacją sekcyjno-

skojarzeniową. Poprawia ona znacząco współczynnik

trafienia w stosunku do odwzorowywania bezpośredniego.
Czterodrożne odwzorowywanie sekcyjno-skojarzeniowe

(v=m/4, k-2) umożliwia uzyskanie umiarkowanej poprawy

w zamian za względnie mały koszt dodatkowy.
Dalsze zwiększanie liczby wierszy w sekcji przynosi małe

efekty.

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 odwzorowywania 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 i sekcyjno-

skojarzeniowej wymagany jest algorytm zastępowania.
Aby uzyskać dużą szybkość, algorytm taki musi być

wbudowany w postaci sprzętowej.
Wypróbowano wiele algorytmów. Wspomnimy o

czterech najbardziej powszechnych.

Algorytm LRU

Prawdopodobnie najbardziej efektywny jest algorytm „najmniej

ostatnio używany” (ang. least-recently used - LRU). 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.
W

przypadku

dwudrożnego

odwzorowywania

sekcyjne-

skojarzeniowego jest to łatwe do wdrożenia. Każdy wiersz

zawiera bit wykorzystania (USE). Gdy wiersz jest adresowany,

jego bit USE jest ustawiany na 1, a bit USE pozostałego wiersza

w tej sekcji jest ustawiany na 0. Jeśli blok ma być wczytany do

sekcji, wykorzystuje się wiersz, którego bit USE ma wartość 0.

Ponieważ zakładamy, że niedawno wykorzystywane lokacje

pamięci są bardziej prawdopodobne do wykorzystania w

przyszłości, LRU powinien dawać najlepszy współczynnik trafień.

Algorytmy FIFO, LFU a

może losowo

Inną możliwość stwarza algorytm „pierwszy wchodzi -

pierwszy wychodzi” (FIFO). Polega on na zastępowaniu tego

bloku w sekcji, który najdłużej pozostawał w pamięci

podręcznej. Algorytm FIFO jest łatwy do wdrożenia w postaci

metody cyklicznego buforowania.
Jeszcze inną możliwość stanowi algorytm „najrzadziej

używany” (LFU). Określa on, że zastępowany jest ten blok w

sekcji, którego dotyczyło najmniej odniesień. Algorytm LFU

można wdrożyć przez skojarzenie licznika z każdym wierszem.
Ostatnią z metod jest jest przypadkowy wybór wśród

kandydujących wierszy. Jest ona niezależna od ilości odniesień.

Badania symulacyjne wykazały, że losowe zastępowanie

prowadzi do niewiele tylko mniejszej wydajności w stosunku

do pozostałych algorytmów.

Algorytm zapisu

Zanim blok pozostający w pamięci podręcznej będzie

mógł być zastąpiony, konieczne jest rozważenie, czy

musi on być zmieniony w pamięci podręcznej, a nie w

pamięci głównej.
Jeśli nie musi, to stary blok w pamięci podręcznej

może być nadpisany.
Jeśli musi, to znaczy, że na słowie zawartym w tej linii

pamięci podręcznej musi być przeprowadzona

przynajmniej jedna operacja zapisu, a pamięć główna

musi być odpowiednio zaktualizowana.
Możliwe są różne algorytmy zapisu wykorzystujące

współzależności dotyczące wydajności i ekonomii.

Problemy konstrukcyjne

Do pamięci głównej może mieć dostęp więcej niż jedno

urządzenie. Na przykład, moduł wejścia-wyjścia może być

zdolny do odczytu/zapisu bezpośrednio w pamięci. Jeśli

słowo byłoby zmienione tylko w pamięci podręcznej, to

odpowiednie słowo w pamięci głównej byłoby nieaktualne.

Ponadto, jeśli moduł wejścia-wyjścia zmieniłby słowo w

pamięci głównej, to odpowiednie słowo w pamięci

podręcznej byłoby nieważne.
Bardziej złożony problem występuje, gdy mamy do czynienia

z wieloma procesorami podłączonymi do tej samej magistrali

i wyposażonymi we własne, lokalne pamięci podręczne. Jeśli

w takiej sytuacji byłoby zmienione słowo w jednej pamięci

podręcznej, spowodowałoby to unieważnienie słowa w

innych pamięciach podręcznych.

I inne kłopoty

W przypadku organizacji magistralowej, w której więcej niż

jedno urządzenie (zwykle procesor) ma pamięć podręczną,

a pamięć główna jest wspólna, powstaje nowy problem.
Jeśli dane w jednej pamięci podręcznej są zmieniane, to

operacja taka powoduje unieważnienie odpowiedniego

słowa nie tylko w pamięci głównej, ale także w innych

pamięciach podręcznych (jeśli to słowo w nich akurat

występuje). Jeśli nawet jest stosowana metoda zapisu

jednoczesnego, to inne pamięci podręczne mogą zawierać

nieaktualne dane.
System, który zapobiega temu problemowi, jest nazywany

systemem zapewniającym spójność pamięci podręcznej.

Zapis jednoczesny

Najprostsza

metoda

jest

określana

jako

zapis

jednoczesny (ang. write through). Przy jej zastosowaniu

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.
Jakikolwiek inny moduł, procesor - pamięć podręczna

może monitorować przesyłanie do pamięci głównej w

celu zachowania spójności (consistency) swojej pamięci

podręcznej.
Główną wadą tej metody jest to, że generuje ona

znaczny przepływ danych do pamięci i może przez to

spowodować występowanie wąskich gardeł.

Zapis opóźniony

Metoda alternatywna, nazwana metodą zapisu opóźnionego

(ang. write back), minimalizuje ilość operacji zapisu do pamięci. W

przypadku tej metody 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 jest ustanowiony bit UPDATE.
Problemem tej metody jest to, że część zawartości pamięci głównej

jest nieaktualna, przez co dostęp modułów wejścia-wyjścia jest

możliwy tylko za pośrednictwem pamięci podręcznej.
Komplikuje to układy i stwarza możliwość wąskich gardeł.

Doświadczenie wykazało, że udział zapisów w operacjach dostępu

do pamięci jest rzędu 15%

Obserwowanie magistrali

z zapisem jednoczesnym

Do możliwych rozwiązań problemu spójności pamięci

podręcznej należą:
Obserwowanie magistrali z zapisem jednoczesnym.

Każdy sterownik pamięci podręcznej monitoruje linie

adresowe w celu wykrycia operacji zapisu do pamięci

dokonywanych przez inne jednostki nadrzędne

magistrali. Jeśli inna jednostka nadrzędna wpisuje dane

do takiej lokacji w pamięci wspólnej, która występuje

również w pamięci podręcznej, to sterownik pamięci

podręcznej unieważnia dostęp do pamięci podręcznej.

Strategia ta jest uzależniona od tego, czy wszystkie

sterowniki pamięci podręcznych posługują się metodą

zapisu jednoczesnego.

Sprzętowe zapewnianie

spójności

Sprzętowe zapewnianie spójności (ang. hardware
transparency). Wykorzystywane są dodatkowe
rozwiązania sprzętowe zapewniające, że wszystkie
aktualizacje pamięci głównej dokonywane za
pośrednictwem

pamięci

podręcznej

znajdują

odzwierciedlenie

we

wszystkich

pamięciach

podręcznych. Jeśli jeden procesor modyfikuje słowo
w swojej pamięci podręcznej, aktualizacja ta jest
wprowadzana również do pamięci głównej. Ponadto,
wszystkie

odpowiednie

słowa

w

pozostałych

pamięciach podręcznych są podobnie aktualizowane.

Pamięć wyłączona ze

współpracy z pamięcią

podręczną

Pamięć wyłączona ze współpracy z pamięcią

podręczną (ang. non-cachable memory). Tylko część

pamięci głównej jest wspólna dla więcej niż jednego

procesora i ta właśnie część jest oznaczana jako

wyłączona ze współpracy z pamięcią podręczną. W

takim systemie wszystkie operacje dostępu do pamięci

wspólnej nie dotyczą pamięci podręcznych, ponieważ

pamięć wspólna nigdy nie jest kopiowana do pamięci

podręcznych. Pamięć wyłączona ze współpracy z

pamięcią podręczną może być identyfikowana za

pomocą układów logicznych wyboru mikroukładu lub

najbardziej znaczących bitów adresu.

Rozmiar bloku

Gdy blok danych jest pobierany i umieszczany w pamięci

podręcznej, pobierane jest nie tylko żądane słowo, lecz również

pewna liczba sąsiednich słów.
Gdy zwiększamy rozmiar bloku od bardzo małego do dużego,

współczynnik trafień najpierw wzrasta ze względu na zasadę

lokalności: wysokie prawdopodobieństwo, że dane sąsiadujące z

wywołanym słowem będą potrzebne w niedalekiej przyszłości.

W miarę wzrostu rozmiaru bloku do pamięci podręcznej

doprowadzana jest coraz większa ilość użytecznych danych.
Przy dalszym wzroście współczynnik trafień zacznie jednak

maleć, a prawdopodobieństwo wykorzystania nowo pobieranych

informacji stanie się mniejsze niż prawdopodobieństwo

ponownego użycia informacji, która jest zastępowana.

Dlaczego nie używamy

bardzo dużych bloków

Grają tu rolę dwa szczególne zjawiska:

Użycie większych bloków powoduje zmniejszenie
liczby bloków, które mieszczą się w pamięci
podręcznej.

Ponieważ

każde

wpisanie

bloku

powoduje usunięcie starej zawartości pamięci
podręcznej, mała liczba bloków sprawia, że dane są
usuwane niedługo po ich pobraniu.
Gdy blok staje się większy, każde dodatkowe słowo
jest dalsze od potrzebnego słowa, staje się więc
mniej prawdopodobne jego użycie w niedalekiej
przyszłości.

Liczba pamięci

podręcznych

Kiedy wprowadzono pamięci podręczne,
typowy system miał pojedynczą pamięć
podręczną.
Ostatnio stało się normą wykorzystywanie
wielu pamięci podręcznych.
Dwoma

aspektami

tego

zagadnienia

projektowego są: liczba poziomów pamięci
oraz

podział

lub

scalanie

pamięci

podręcznych.

Pamięć

wewnątrzprocesorowa

W miarę wzrostu gęstości upakowania układów

logicznych stało się możliwe dysponowanie

pamięcią podręczną wewnątrz tego samego

mikroukładu co procesor: określamy to mianem

pamięci podręcznej w procesorze (ang. on-chip

cache).
W porównaniu z pamięcią osiągalną za pomocą

zewnętrznej

magistrali

wewnątrzprocesorowa

pamięć

podręczna

umożliwia

zmniejszenie

aktywności procesora w magistrali zewnętrznej i

przez to skraca się czasy wykonywania operacji i

zwiększa się ogólną wydajność systemu.

Zalety stosowania

pamięci

wewnątrzprocesorowej

Jeśli wymagane rozkazy lub dane znajdują się w

wewnątrzprocesorowej

pamięci

podręcznej,

konieczność dostępu do magistrali jest eliminowana.
Ze względu na krótsze ścieżki danych wewnątrz

procesora w porównaniu z długościami magistrali,

dostęp do wbudowanej pamięci podręcznej jest

wyraźnie szybszy w porównaniu z cyklem magistrali,

nawet w stanie nie wymagającym oczekiwania.
Ponadto, w tym okresie magistrala pozostaje wolna i

mogą zachodzić inne transfery.

Pamięci podręczna L1 i L2

Wbudowanie pamięci podręcznej do procesora pozostawia otwarte

pytanie, czy nadal jest pożądana zewnętrzna (poza mikroukładem

procesora) pamięć podręczna. Odpowiedź brzmi zwykle: tak.
Większość współczesnych projektów zawiera zarówno pamięć

podręczną wewnątrzprocesorowa, jak i zewnętrzną. Wynikająca

stąd organizacja jest znana jako dwupoziomowa pamięć

podręczna, przy czym pamięć wewnętrzna jest oznaczana jako

poziom 1 (L1), a zewnętrzna jako poziom 2 (L2).
Przyczyna wprowadzania pamięci L2 jest następująca. Jeśli nie

byłoby

pamięci

podręcznej

L2,

a

procesor

zgłosiłby

zapotrzebowanie na dostęp do lokacji pamięci nie występującej w

pamięci podręcznej L1, to procesor musiałby sięgać do pamięci

DRAM lub ROM poprzez magistralę. Ze względu na typowo

niewielką szybkość magistrali oraz stosunkowo długi czas dostępu

do pamięci rezultatem będzie zmniejszona wydajność.

Zwykle co najmniej 2

poziomy

Z drugiej strony, jeśli zastosowano pamięć podręczną L2

SRAM, to często możliwe jest szybkie pobranie

brakującej informacji.
Jeśli pamięć SRAM jest dostatecznie szybka, aby

dostosować się do szybkości magistrali, to możliwy jest

dostęp do danych za pomocą transakcji o zerowym

czasie oczekiwania, co stanowi najszybszy rodzaj

transferów magistralowych.
Potencjalne oszczędności wynikające z zastosowania

pamięci podręcznej L2 zależą od współczynników trafień

zarówno pamięci L1, jak i L2. W kilku badaniach

wykazano, że na ogół zastosowanie pamięci podręcznej

drugiego poziomu poprawia wydajność.

Jednolita a podzielona

pamięć podręczna

Gdy

po

raz

pierwszy

wprowadzono

wewnątrzprocesorową pamięć podręczną, w
wielu projektach zawierających pojedynczą
pamięć

podręczną

wykorzystywano

ją

zarówno do przechowywania danych, jak i
rozkazów.
Obecnie stało się powszechne dzielenie
pamięci

podręcznej

na

dwie:

jedną

przeznaczoną na rozkazy, drugą zaś na dane.

Zalety pamięci jednolitej

Dla danego rozmiaru pamięci podręcznej pamięć

jednolita wyróżnia się większym współczynnikiem

trafień

niż

pamięć

podzielona,

ponieważ

automatycznie równoważy ona pobieranie rozkazów

z pobieraniem danych. To znaczy, jeśli struktura

rozkazów przewiduje o wiele więcej pobrań rozkazów

niż danych, pamięć podręczna będzie wykazywała

tendencję do wypełniania się rozkazami. Jeżeli

natomiast wymagane jest częstsze pobieranie

danych, pamięć ta będzie się wypełniała danymi.
Tylko

jedna

pamięć

podręczna

musi

być

zaprojektowana i wdrożona.

Zwykle pamięć podzielona

Mimo tych zalet występuje tendencja do stosowania

pamięci podzielonych, szczególnie w przypadku

maszyn superskalarnych, jak rodziny Pentium i

PowerPC, co akcentuje równoległe wykonywanie

rozkazów

i

wstępne

pobieranie

rozkazów

przewidywanych do wykonywania.
Kluczową zaletą podzielonej pamięci podręcznej jest

to, że eliminowana jest rywalizacja o pamięć

podręczną między procesorem rozkazów a jednostką

wykonującą.
Jest

to

ważne

w

każdym

rozwiązaniu

wykorzystującym potokowe przetwarzanie rozkazów.

Zwykle pamięć podzielona

Typowo procesor pobiera rozkazy z wyprzedzeniem i napełnia bufor -

rejestr potokowy - rozkazami, które mają być wykonane. Załóżmy

teraz, że mamy do dyspozycji jednolitą pamięć podręczną dla

rozkazów i danych. Gdy jednostka wykonująca sięga do pamięci w

celu załadowania i przechowania danych, zapotrzebowanie jest

doprowadzane do jednolitej pamięci podręcznej.
Jeśli w tym samym czasie układ wyprzedzającego pobierania

rozkazów wysyła zapotrzebowanie na odczytanie rozkazu z pamięci

podręcznej, to zapotrzebowanie to zostanie czasowo zablokowane,

żeby pamięć podręczna mogła najpierw obsłużyć jednostkę

wykonującą, pozwalając jej na zakończenie właśnie wykonywanego

rozkazu.
Ta rywalizacja o pamięć podręczną może spowodować zmniejszenie

wydajności, interferując z wydajnym wykorzystaniem potoku

rozkazów. Struktura podzielonej pamięci podręcznej umożliwia

pokonanie tej trudności.

Pamięć EDRAM

Być może najprostszą z nowych architektur DRAM jest

wzbogacona pamięć DRAM (EDRAM), opracowana w firmie

Ramtron [BOND94]. Pamięć EDRAM zawiera małą pamięć

podręczną SRAM w typowym mikroukładzie DRAM.
Na rysunku jest pokazana 4-megabitowa wersja pamięci

EDRAM. W pamięci podręcznej SRAM jest przechowywana

cała zawartość ostatnio odczytywanego wiersza, który

składa się z 2048 bitów lub z 512 porcji 4-bitowych.
W komparatorze jest przechowywany 11-bitowy adres

ostatnio wybieranego wiersza. Jeśli następny dostęp

dotyczy tego samego wiersza, to wymagane jest tylko

dotarcie do szybkiej pamięci podręcznej SRAM.

Wzbogacona dynamiczna

pamięć RAM (EDRAM)

Zalety EDRAM

Pamięć

EDRAM

ma

kilka

innych

własności

poprawiających wydajność.
Operacje

odświeżania

mogą

być

prowadzone

równolegle

z

operacjami

odczytu

z

pamięci

podręcznej, co minimalizuje czas, w którym

mikroukład jest nieosiągalny z powodu odświeżania.
Zauważmy też, że ścieżka odczytu z pamięci

podręcznej wiersza do portu wyjściowego jest

niezależna od ścieżki zapisu z modułu wejścia-wyjścia

do wzmacniaczy odczytu. Dzięki temu kolejny dostęp

do pamięci podręcznej związany z odczytem może być

realizowany równolegle z kończeniem operacji zapisu.

Synchroniczna pamięć

DRAM (SDRAM)

Zupełnie inne podejście do poprawiania wydajności
pamięci DRAM przyjęto w synchronicznej pamięci
DRAM (SDRAM) opracowanej wspólnie przez pewną
liczbę firm.
W przeciwieństwie do typowej pamięci DRAM, która
jest asynchroniczna, wymiana danych między
pamięcią

SDRAM

a

procesorem

jest

synchronizowana przez sygnał zegara zewnętrznego
i zachodzi z pełną szybkością magistrali procesor-
pamięć bez narzucania stanów oczekiwania.

Typowa praca DRAM

W typowej pamięci DRAM procesor przekazuje adresy i

sygnały sterujące do pamięci, wskazując że zbiór danych

o określonej lokacji w pamięci powinien być albo

odczytany z pamięci DRAM, albo do niej zapisany.
Po pewnym opóźnieniu (czas dostępu) pamięć DRAM albo

odczytuje, albo zapisuje dane.
Podczas opóźnienia związanego z czasem dostępu,

pamięć DRAM realizuje różne funkcje wewnętrzne, takie

jak aktywowanie dużych pojemności linii wierszy i

kolumn, odczytywanie danych i wyprowadzanie ich przez

bufory wyjściowe.
Procesor musi po prostu przeczekać to opóźnienie,

zmniejszając wydajność systemu.

Praca SDRAM

W przypadku dostępu synchronicznego pamięć

DRAM przenosi dane do wewnątrz i na zewnątrz

pod kontrolą zegara systemowego.
Procesor lub inna jednostka nadrzędna wydaje

rozkaz i podaje informację adresową, które są

zatrzaskiwane w pamięci DRAM.
Pamięć DRAM udziela odpowiedzi po upływie

pewnej liczby cykli zegara. W tym czasie

jednostka

nadrzędna

może

bezpiecznie

realizować inne cele, a pamięć SDRAM

przetwarza zgłoszone zapotrzebowanie.

Tryb pakietowy (ang.

burst mode)

Na rysunku są pokazane wewnętrzne układy logiczne

pamięci SDRAM.
Wykorzystuje ona tryb pakietowy w celu wyeliminowania

czasu ustalania adresu oraz czasu wstępnego ładowania

linii wiersza i kolumny po pierwszej operacji dostępu.
W przypadku trybu pakietowego ciągi bitów danych

mogą być szybko wyprowadzone za pomocą zegara tuż

po uzyskaniu dostępu do pierwszego bitu. Taki tryb

pracy jest użyteczny, gdy wszystkie pożądane bity

danych są ułożone szeregowo w tym samym wierszu

matrycy, którego dotyczyła początkowa operacja

dostępu.

Synchronicz

na,

dynamiczna

pamięć RAM

(SDRAM)

Rejestr trybu

Zwróćmy ponadto uwagę, że pamięć SDRAM ma

dwusegmentową architekturę wewnętrzną, która umożliwia

poprawę warunków równoległych działań w ramach

mikroukładu.
Rejestr trybu i związane z nim sterujące układy logiczne

stanowią jeszcze jedną istotną własność odróżniającą pamięć

SDRAM od konwencjonalnych pamięci DRAM. Pozwalają one

na dostosowanie pamięci SDRAM do specyficznych wymagań

systemowych.
Rejestr trybu ustala długość porcji danych, która jest liczbą

oddzielnych

jednostek

danych

synchronicznie

doprowadzanych do magistrali. Rejestr ten umożliwia także

programiście regulowanie zwłoki między otrzymaniem

zapotrzebowania na odczyt a rozpoczęciem transferu danych.

Zastosowanie SDRAM

Pamięć SDRAM sprawuje się najlepiej, gdy
dokonuje szeregowego transferu dużych
bloków danych, co ma miejsce w takich
zastosowaniach,

jak

przetwarzanie

tekstów, arkusze kalkulacyjne i multimedia.

RDRAM

Pamięć RDRAM, opracowana w firmie Rambus,

stanowi

bardziej

rewolucyjne

rozwiązanie

problemu szerokości pasma pamięci.
Mikroukłady RDRAM mają obudowy pionowe, ze

wszystkimi końcówkami po jednej stronie.
Mikroukład wymienia dane z procesorem

poprzez 28 połączeń nie dłuższych niż 12 cm.

Magistrala umożliwia adresowanie do 320

mikroukładów RDRAM i może przenosić 500

Mbit/s. Można to porównać z wielkością około 33

Mbit/s dla synchronicznych pamięci DRAM.

RDRAM

Specjalna magistrala RDRAM dostarcza informacje adresowe

i

sterujące,

wykorzystując

asynchroniczny

protokół

przesyłania danych blokami.
Po początkowym czasie dostępu 480 ns osiągana jest

szybkość przekazywania danych równa 500 Mbit/s. Tym, co

umożliwia taką szybkość, jest sama magistrala, dla której

bardzo dokładnie określono impedancje, taktowanie i

sygnały.
Zamiast sterowania za pomocą jasno określonych sygnałów

RAS, CAS, R/W i CE stosowanych w konwencjonalnych

pamięciach DRAM, w przypadku pamięci RDRAM dostęp do

danych zachodzi poprzez magistralę o dużej szybkości.

Żądanie dostępu do danych zawiera adres, rodzaj operacji

oraz liczbę bajtów w operacji.

DDRAM

Obecnie najczęściej używana pamięć.
W porównaniu z SDRAM pozwala na
odczyt/zapis w trakcie narastania i
opadania sygnału zegarowego co
podwaja wydajność.