ALFA BK UNIVERZITET
FAKULTET ZA MATEMATIKU I RAČUNARSKE NAUKE
SEMINARSKI RAD
KES MEMORIJA
Predmet: ORGANIZACIJA RACUNARA
Profesor: Student:
Prof.dr Negovan Stamenkovic Dragan Radivojević
2016/6015
Beograd 2017 godine
Zubin Potok
1
1.
UVOD
...................................................................................................................................2
2.
OSNOVNI POJMOVI
........................................................................................................2
3.
TEHNIKE PRESLIKAVANJA
........................................................................................4
3.1. Asocijativno preslikavanje.............................................................................................4
3.2. Direktno preslikavanje...................................................................................................7
3.3. Set- asocijativno preslikavanje.....................................................................................10
4
. ZAMENA BLOKOVA KES MEMORIJE
......................................................................16
5.
AZURIRANJE OPERATIVNE MEMORIJE
................................................................23
6.
VIRTUELNA MEMORIJA I JEDINICA ZA UBRZAVANJE
....................................24
6.1.
ORGANIZACIJA VIRTUELNE MEMORIJE
......................................................25
6.1.1. Stranicna organizacija........................................................................................25
6.1.3. Segmentno- stranicna organizacija...................................................................32
6.2.
ORGANIZACIJA JEDINICA PRESLIKAVANJA
..............................................37
6.2.1. Jedinica sa asocijativnim preslikavanjem..........................................................37
6.2.2. Jedinica sa direktnim preslikavanjem................................................................39
7.
ZAKLJUCAK
.....................................................................................................................47
2
S obzirom na to da je keš memorija daleko brža od operativne memorije, u svako takvoj
situaciji čitanje ili upis sadržaja će se realizovati sa vremenom pristupa keš memorije umesto
sa vremenom pristupa operativne memorije.
Efikasnost mehanizma keš memorije direktno zavisi od toga koliko često će se utvrđivati
da se sadržaj sa generisane adrese nalazi u keš memoriji. Analiza tragova generisanih adresa
prilikom izvršavanja tipičnih programa ukazuju na dva efekta koji direktno utiču na efikasnost
mehanizma keš memorije. Prvi je da se jedanput generisana adresa obično posle toga još
nekoliko puta generiše. Ovaj efekat se naziva vremenski lokalitet programa i javlja se kod
generisanja adresa instrukcija i skalarnih veličina u petlji. Drugi je da se posle neke
generisane adrese veoma često generišu adrese koje slede sekvencijalno. Ovaj efekat se
naziva prostorni lokalitet programa i javlja se kod sekvencijalnog izvršavanja instrukcija i
sekvencijalnog pristupa podacima koji predstavljaju elemente vektora. Da bi se iskoristio
potencijal prvof efekta potrebno je sadržaje memorijskih lokacija kojima se pristupa čuvati u
keš memoriji sa sledeće pristupe, a da bi se iskoristio potencijal drugog efekta potrebno je
dovlačiti ne samo sadržaj memorijske lokacije kojoj se pristupa, već blok od nekoliko
susednih memorijskih lokacija.
Naziv za keš memoriju odražava činjenicu da je mehanizam keš memorije "skriven" od
programera i da programer ne može programskim putem da utiče na ono što se dešava u keš
memoriji. Provera da li se sadržaj sa generisane adrese nalazi u keš memoriji, eventualno
dovlačenje bloka podataka iz operativne memorije u keš memoriju, čitanje podatka iz keš
memorije i upis podatka u keš memoriju realizuju se kompletno hardverski. Programer je
"svestan" postojanja mehanizma keš memorije indirektno na osnovu toga što će se program
izvršavati brže u procesoru sa keš memorijom nego u procesoru bez keš memorije. Zbog toga
mehanizam keš memorije ne pripada arhitekturi već organizaciji procesora.
Prilikom realizacije keš memorije postoje tri osnovna pitanja koja treba rešiti. Kapacitet
keš memorije je manji od kapaciteta operativne memorije i postoji potreba da se u keš
memoriji vodi evedincija o tome koji se blokovi operativne memorije nalaze u keš memoriji i
gde se nalaze u keš memoriji. Ovo vođenje evidencije se naziva tehnika preslikavanja.
Kapacitet keš memorije je manji od kapaciteta operativne memorije, pa će se posle određenog
vremena dešavati da se generišu adrese sa kojih se sadržaji ne nalaze u keš memoriji, a keš
memorija je popunjena. Tada postoji potreba da se odluči koji će se blok izbaciti iz keš
memorije da bi se u njoj stvorio prostor za dovlačenje bloka iz operativne memorije kome
pripada generisana adresa. Ovo odlučivanje se realizuje prema nekom od algoritama zamene.
Prilikom operacija upisa i utvrđivanja da u keš memoriji postoji blok kome pripada
generisana adresa, upis će se realizovati u keš memoriju. Time se javlja razlika u vrednosti
kopije sadržaja sa određene adrese u keš memoriji i u operativnoj memoriji. Sadržaji
određenih lokacija operativne memorije se nalaze u keš memoriji samo privremeno radi
ubrzanja pristupa. Zbog tog postoji potreba da se na neki način za sve generisane adrese za
koje je upis izvršen u kopiju sadržaja u keš memoriji obezbedi ažuriranje i kopije sadržaja u
operativnoj memoriji. Načini realizacije zavise od usvojene tehnike ažuriranja sadržaja
operativne memorije. Ova tri pitanja su predmet razmatranja u sledeća tri poglavlja.
4
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.
5
S obzirom da je operativna memorija kapaciteta 2
h+l
reči i da je veličina bloka 2
l
reči,
uzima se kao da je operativna memorija organizovana u 2
h
blokova veličine 2
l
reči. Stoga se
adresa operativne memorije dužine h+l bita može podeliti na sledeći način: viših h bitova
označavaju broj bloka i nižih l bitova označavaju adresu reči u bloku.
Pri generisanju zahteva za čitanje od strane procesora, viših h bitova generisane adrese
vodi se na ulazne linije podataka TI
h-1...0
TAG MEMORIJE da bi se, njihovim istovremenim
upoređivanjem sa sadržajima svih 2
n
ulaza TAG MEMORIJE, utvrdilo da li postoji saglasnost
sa sadržajem nekog ulaza. Za svaki od 2
n
ulaza TAG MEMORIJE postoji poseban signal
saglasnosti M
0
do M
2
n
-1
, koji svojom aktivnom vrednošću određuje da je na datom ulazu
otkrivena saglasnost. Otkrivena saglasnost je važeća, i jedan od signala važećih saglasnosti S
0
do S
2
n
-1
je aktivan, ukoliko je odgovarajući indikator važećih ulaza V aktivan. Signal
saglasnosti SGL, koji se dobija sa izlaza W kodera CD, ima aktivnu vrednost, ukoliko jedan
od signala S
0
do S
2
n
-1
ima aktivnu vrednost. Binarna vrednost broja ulaza u kome je otkrivena
saglasnost je određena sa n bita sa izlaza kodera CD na osnovu signala S
0
do S
2
n
-1
. Ukoliko
postoji saglasnost, sa n bitova sa izlaza kodera CD i l nižih bitova generisane adrese, adresira
se reč DATA MEMORIJE i obavlja čitanje.
Ukoliko saglasnost ne postoji u jedan od ulaza keš memorije treba iz operativne
memorije da se dovuče blok u kome se nalazi željeni sadržaj. Ulaz u koji se dovlači blok
naziva se ulaz za zamenu. Broj ulaza je određen vrednošću UZ
n-1...0
do koje se dolazi na
osnovu nekog od algoritama zamene. Pre dovlačenja željenog bloka proverava se da li se u
ulazu koji je odabran za zamenu nalazi blok koji je nekom od operacija upisa modifikovan.
Ovo se utvrđuje na osnovu sadržaja indikatora D adresiranog vrednošću UZ
n-1...0
. Ukoliko je
indikator D ulaza odabranog za zamenu 1, blok je modifikovan, pa prvo treba dati blok vratiti
u operativnu memoriju pa tek onda dovući željeni blok. Ukoliko je indikator D ulaza
odabranog za zamenu 0, blok nije modifikovan, pa se željeni blok odmah dovlači.
Prilikom vraćanja bloka odabranog za zamenu 2
l
reči datog bloka se čita iz DATA
MEMORIJE sa adresa formiranih od vrednosti UZ
n-1...0
koja daje n starijih bitova adrese i
vrednosti BR
l-1...0
koja je daje l mlađih bitova adrese. Date reči se upisuju u OPERATIVNU
MEMORIJU na adresama formiranih od vrednosti na linijama TO
h-1...0
koja daje n starijih
bitova adrese i vrednosti BR
l-1...0
koja je daje l mlađih bitova adrese. Vrednost na linijama
TO
h-1...0
pročitana je iz TAG MEMORIJE sa adrese određene vrdnošću UZ
n-1...0
.
Prilikom dovlačenja željenog bloka 2
l
reči datog bloka se upisuje u DATA MEMORIJU
na adresama formiranih kao i u slučaju vraćanja bloka od vrednosti UZ
n-1...0
koja daje n starijih
bitova adrese i vrednosti BR
l-1...0
koja je daje l mlađih bitova adrese. Date reči se čitaju iz
OPERATIVNE MEMORIJE sa adresa formiranih od vrednosti bitova A
h-1...0
generisane adrese
koja daje n starijih bitova adrese i vrednosti BR
l-1...0
koja je daje l mlađih bitova adrese. Pored
toga bitovi A
h-1...0
generisane adrese se upisuju u ulaz TAG MEMORIJE čija je adresa
određena vrednošću UZ
n-1...0
. Indikatori V i D ulaza adresiranih vrednošću UZ
n-1...0
postavljaju
se na 1 i 0, respektivno.
Po dovlačenju bloka podataka u keš memoriju, utvrđuje se da sada postoji saglasnost, pa
se na već opisani način adresira reč DATA MEMORIJE i obavlja čitanje.
Pri generisanju zahteva za upis od strane procesora, na isti način se ispituje saglasnost sa
sadržajem keš memorije kao u slučaju operacije čitanja. Ukoliko postoji saglasnost, na isti
način se adresira reč DATA MEMORIJE i vrši upis, pri čemu se sada indikator
modifikovanog ulaza D, adresiran vrednošću US
n-1...0
sa izlaza kodera CD i koja predstavlja
broj ulaza u kome je otkrivena saglasnost, postavlja na 1.
Ako saglasnost ne postoji, na identičan način kao i za operaciju čitanja, se, najpre, blok iz
ulaza keš memorije, određenog vrednošću UZ
n-1...0
, vraća u operativnu memoriju, ukoliko je
modifikovan, a zatim, u isti ulaz keš memorije, dovlači novi blok iz operativne memorije.
7
