Keš memorija
1.UVOD
U ovom poglavlju se najpre daju osnovni pojmovi vezani za ubrzavanje pristupa
memorijskim lokacijama korišćenjem keš memorije. Zatim se razmatraju osnovna pitanja
vezana za realizaciju keš memorije, i to tehnika preslikavanja, zamena blokova keš memorije i
ažuriranje sadržaja operativne memorije. Na kraju se daju neka specifična rešenja čijim se
korišćenjem poboljšava rad keš memorija.
2.OSNOVNI POJMOVI
Mehanizam keš memorije podrazumeva da u procesoru postoji posebna memorija, koja se
naziva keš memorija (slika 1). Keš memorija se realizuje sa memorijskim komponentama čije
je vreme pristupa daleko manje od vremena pristupa memorijskih komponenata operativne
memorije i veoma blisko vremenu prenosa podataka između registara. Zbog toga je cena po
bitu keš memorije daleko veća od cene po bitu operativne memorije. To ima za posledicu da
je kapacitet keš memorije daleko manji od kapaciteta operativne memorije.
O STA LI
D E LO V I
C P U
K E Š
C P U
M E M
A
D
A D R E SA
PO D A C I
PO D A C I
A D R E SA
Slika 1 Keš memorija
Algoritam izvršavanja instrukcija u računarima sa keš memorijom je takav da se, pri
svakom generisanju adrese operativne memorije od strane nekog dela procesora radi čitanja ili
upisa, najpre, vrši provera da li se sadržaj sa generisane adrese nalazi u keš memoriji. Na
početku dati sadržaj nije u keš memoriji. Zbog toga se sadržaj sa date i nekoliko susednih
adresa, koje čine blok, najpre, prebacuje iz operativne u keš memoriju, pa se potom ili čita
sadržaj iz keš memorije i prosleđuje onom delu procesora koji je adresu generisao ili upisuje u
keš memoriju sadržaj iz onog dela procesora koje je adresu generisao.
Za nekoliko sledećih generisanih adresa operativne memorije verovatno će se i dalje
utvrđivati da se sadržaji takođe ne nalaze u keš memoriji, pa će se odgovarajući blokovi
dovlačiti iz operativne memorije u keš memoriju i sa keš memorijom realizovati čitanje ili
upis. Time će se broj blokova operativne memorije dovučenih u keš memoriju povećavati.
Zbog toga će se od određenog trenutka za neke od generisanih adresa operativne memorije
utvrđivati da se sadržaji nalaze u keš memoriji. U svakoj takvoj situaciji sadržaj će se ili čitati
iz keš memorije umesto iz operativne memorije ili upisivati u keš memoriju umesto u
operativnu memoriju.
2
3.TEHNIKE PRESLIKAVANJA
Tehnika preslikavanja određuje način vođenja evidencije o tome koji se blokovi
operativne memorije nalaze u pojedinim blokovima keš memorije. Koriste se tri tehnike
preslikavanja i to: asocijativno, direktno i set
asocijativno.
3.1.ASOCIJATIVNO PRESLIKAVANJE
Kod tehnike asocijativnog preslikavanja, keš memorija se sastoji iz DATA MEMORIJE
i TAG MEMORIJE (slika 2). U DATA MEMORIJU se smeštaju blokovi preneti iz operativne
u keš memoriju. U TAG MEMORIJU se, za blokove prenete iz operativne u keš memoriju,
smeštaju brojevi blokova operativne memorije, koji se nazivaju
tag
ovi. Za realizaciju DATA
MEMORIJE i TAG MEMORIJE koriste se RAM memorija i asocijativna memorija,
respektivno. Ukoliko u DATA MEMORIJU može da se smesti 2
n
blokova, kaže se da keš
memorija ima 2
n
ulaza. Za svaki ulaz DATA MEMORIJE postoji odgovarajući ulaz TAG
MEMORIJE.
2
l
reči
h
bita
K E Š M E M O RIJA
O PE RAT IV N A M E M O RIJA
TA G
M E M O RIJA
D AT A
M E M O RIJA
l
h
blok
reč
G E N E RISA N A A D RE SA
0
2
n
1
blok 0
blok (2
h
1)
2
l
reči
blok 1
...
...
Slika 2 Asocijativno preslikavanje
U slučaju keš memorije realizovane u tehnici asocijativnog preslikavanja, zamišlja se
kao da je operativna memorija podeljena na 2
h
blokova. Ukoliko se uzme da je dimenzija
bloka 2
l
reči, tada generisana adresa ima sledeću strukturu: nižih
l
bitova određuju adresu reči
unutar bloka i viših
h
bitova određuju broj bloka u operativnoj memoriji.
U tehnici asocijativnog preslikavanja bilo koji blok operativne memorije može da se smesti
u bilo koji ulaz keš memorije, prilikom dovlačenja iz operativne u keš memoriju.
4
Pošto u
i
tom ulazu DATA MEMORIJE može da se nađe bilo koji od 2
h
blokova
operativne memorije, u
i
tom ulazu TAG MEMORIJE se čuva broj bloka operativne
memorije kome pripada dati blok. S obzirom da u operativnoj memoriji ima 2
h
blokova, širina
memorijske reči TAG MEMORIJE je
h
bita.
Realizacija keš memorije sa asocijativnim preslikavanjem je data na slici 3.
A
T
M
n-
1
A
T
M
0
0
K
E
Š
M
E
M
O
R
IJ
A
T
O
h-
1.
..0
T
I
h-
1.
..0
h
h
M
0
.
.
.
M
V
0
V
0
1
M
P
h
G
E
N
E
R
IS
A
N
A
A
D
R
E
S
A
B
R
O
JA
Č
R
E
Č
I
0
1
M
P
l
l
h
h
h
l
l
h
l
...
S
0
.
.
.
S
.
.
.
S
G
L
C
D
0
W
.
.
.
0
n-
1
U
S
n-
1.
..0
M
P
0
1
n
n
n
l
0
D
O
w
-1
...
0
D
I
w
-1
...
0
w
w
A
D
M
l+
n-
1
A
D
M
0
A
D
M
l
A
D
M
l-
1
...
O
P
E
R
A
T
IV
N
A
M
E
M
O
R
IJ
A
0
2
h+
l
-1
M
O
w
-1
...
0
M
I
w
-1
...
0
w
w
A
O
M
1+
h-
1
A
O
M
l
A
O
M
0
A
O
M
l-
1
...
T
A
G
M
E
M
O
R
IJ
A
D
A
T
A
M
E
M
O
R
IJ
A
0
V
A
V
n-
1
A
V
0
...
V
0
D
A
D
n-
1
A
D
0
...
D
2
n
-1
2
n
-1
2
n
-1
2
n
-1
2
n
-1
...
...
...
2
n+
l
-1
2
n
-1
2
n
-1
A
h+
1-
1.
..0
A
1-
1.
..0
B
R
1-
1.
..0
...
W
D
M
W
O
M
W
T
M
U
Z
n-
1.
..0
n
W
V
W
D
Slika 3 Keš memorija sa asocijativnim preslikavanjem
5
Potom se ponovo, na već opisani način, vrši provera da li postoji saglasnost, utvrđuje da
postoji saglasnost i realizuje upis.
3.2.DIREKTNO PRESLIKAVANJE
Kod tehnike direktnog preslikavanja, keš memorija se sastoji iz DATA MEMORIJE i
TAG MEMORIJE (slika 4). U DATA MEMORIJU se smeštaju blokovi preneti iz operativne u
keš memoriju. U TAG MEMORIJU se, za blokove prenete iz operativne u keš memoriju,
smeštaju brojevi grupa operativne memorije, koji se nazivaju
tag
ovi. Za realizaciju DATA
MEMORIJE i TAG MEMORIJE, koristi se RAM memorija. Ukoliko u DATA MEMORIJU
može da se smesti 2
k
blokova operativne memorije, kaže se da keš memorija ima 2
k
ulaza. Za
svaki ulaz DATA MEMORIJE postoji odgovarajući ulaz TAG MEMORIJE.
2
l
reči
m
bita
K E Š M E M O RIJA
O PE RAT IV N A M E M O RIJA
TA G
M E M O RIJA
D AT A
M E M O RIJA
l
k
m
grupa
blok
reč
G E N E RISA N A A D RE SA
0
2
k
1
blok 0
blok (2
k
1)
blok 2
k
blok (2
m
2
k
1)
blok (2
k
1)
2
l
reči
0
1
(2
k
1 )
0
1
0
1
(2
k
1 )
(2
k
1 )
grupa
0
grupa
1
grupa
(2
m
1)
blok 1
blok (2
2
k
1)
...
...
...
...
...
...
...
...
Slika 4 Direktno preslikavanje
U slučaju keš memorije sa 2
k
ulaza realizovane u tehnici direktnog preslikavanja,
zamišlja se kao da je operativna memorija kapaciteta 2
m
k
blokova podeljena na 2
m
grupa, pri
čemu veličina grupe odgovara veličini DATA MEMORIJE i iznosi 2
k
blokova. Ukoliko se
uzme da je dimenzija bloka 2
l
reči, tada generisana adresa ima sledeću strukturu: najnižih
l
bitova određuju adresu reči unutar bloka, srednjih
k
bitova određuju broj bloka unutar grupe i
najviših
m
bitova određuju broj grupe u operativnoj memoriji kojoj pripada blok.
U tehnici direktnog preslikavanja svaki blok operativne memorije ima fiksno definisan
ulaz u keš memoriji u koji se smešta prilikom dovlačenja iz operativne u keš memoriju. Tako
i
ti blok iz bilo koje od 2
m
grupa operativne memorije prilikom dovlačenja može da se smesti
jedino u
i
ti ulaz DATA MEMORIJE.
Pošto u
i
tom ulazu DATA MEMORIJE može da se nađe
i
ti blok iz bilo koje od 2
m
grupa
operativne memorije, u
i
tom ulazu TAG MEMORIJE se čuva broj grupe kojoj pripada dati
7
