- adresove, teda s adresovym vyberom
- seriove, teda s postupnym vyberom
- asociativne, kde vyberame podla kluca
- LIFO, last in first out (zasobnik)
- FIFO, first in first out (fronta)
Tu by sme si mali povedat nieco o jednotlivych typoch, ako ich realizujeme a ako ich v pocitaci pouzivame.
S adresovym vyberom
Zacnime pamatami s adresovym vyberom. Aby sme mohli vybrat data z takejto pamate, tak potrebujeme poznat ich adresu.
Takato pamat moze mat viac alebo jednu branu. N-branova pamat ma n adresovych vstupov, n (alebo menej) adresovych vstupov a n (alebo menej) datovych vystupov. Napriklad 2-branova pamat by teda vyzerala asi takto
Realizacia takejto pamate moze byt napriklad pomocou registrov.
Spravnu adresu dekodujeme a data zapisujeme do registru. Podla toho, ktory data bus je aktivny, tak podla toho zapisujeme data 1 alebo 2.
Viacbranova pamat teda znamena, ze umoznuje pripojenie viacerych zariadeni (kanalov pre I/O alebo procesorov). Celu tuto srandu riadi radi pamate. V pripade viacbranovej pamate sa nam moze stat, ze dve zariadenia budu chciet zapisovat do pamate naraz a toto musime vzdy nejako vyriesit. Riesenie konkurentnych poziadavkov sa riesi podla priority I/O alebo odobranim cyklov. Pripojenie takejto pamate moze byt priame, cez zbernicu, alebo pomocou prepojovacich sieti.
Dvojbranova pamat je vlastne n branova pamat, pre n = 2, ktora sa da napriklad pouzit ako sada cislovanych registrov. 2 branova pamat ma 2 adresove vstupy, 2 datove vystupy a jeden alebo dva datove vstupy. Sucasne je tak mozne adresovat 2 miesta a citat/zapisovat z/do roznych miest pamate.
Jednobranova pamat, tiez umoznuje prepojenie niekolkych jednotiek cez zbernicu. Kolizia poziadavkov sa potom riesi rezimom pridelovania zbernice. K zbernici pamate mozu byt pripojene podzbernice ako AB, DB, CB.
Aby toho nebolo malo, tak inzinieri na nas pripravili dalsiu fintu a to viacbranovu pamat s autonomnymi blokmi, ktore sa tykaju roznych casti pamatoveho priestoru (neprekryvaju sa, chvalabohu, lebo to uz by fakt bol gulas). Takto organizovana pamat je znazornena na obrazku. Px su pripojene zariadenia, ktore vyuzivaju AB a DB pre pristup k blokom BPx. Vidime, ze pamat je viacbranova. Sucasne zapisovat/citat je mozne len do/z pamatovych miest, ktore su v roznych blokoch.Takto organizovana moze byt napriklad hlavna pamat.
LIFO (last in first out)
LIFO mozme realizovat pomocou seriovo radenych registrov, alebo pomocou registrov urcenych ukazovatkom.
Na obrazku su seriovo radene registre. Vsimnite si, ze datove zbernice su "prepletene" a pri kazdom PUSH/POP musime data prelievat tak, aby sme mali na vrchu ten spravny prvok. Realizacia pomocou registrov urcenych ukazovatkom (to je ale nazov .. ) toto prelievanie odstranuje.
Realizacia pomocou ukazovatiek je znazornena na obrazku vpravo. Vsimnite si, ze registre uz nie su prepletene a read/write je urceny ukazovatkom. Pripomina to zasobnik tak, ako ked ho programujete. Vzdy si potrebujete udrzat ukazatel na top. Dobrou otazkou je, ako je taketo ukazovatko realizovane. Odpoved znie, dekoderom. Jadrom je adresovatelna pamat, alebo teda, kazdy register v realizacii je adresovatelna pamat a to, co z ukazovatka vylezie, je adresa.
Takto vyzera nacrt realizacie ukazovatka. Signaly R/W su spracovane v reverzibilnom citaci. Ak som to pochopil, tak reverzibilny citac je sekv. obvod, ktory je riadeny riadiacim signalom, podla hodnoty ktoreho sa dekrementuje/inkrementuje. Dekrementacia/inkrementacia v nasom pripade znamena prechod medzi vnutornymi stavmi. Neviem, ci nas citac je synchronny alebo nie, ale ukazka 4 bitoveho asynchronneho reverz. citaca je na obrazku nizsie. V praxi to vyzera tak, ze sa jedna o 4 D-ckove klopne obvody. V nasom pripade by mal
- bud preinkrementovat pri PUSH a postdekrementovat pri POP
- alebo predekrementovat pri PUSH a postinkrementovat pri POP
Predstavte si celu tuto srandu tak, ako keby ste ju chceli programovat. Tiez by ste si posuvali ukazovatko a udrziavali by ste sa na pozicii, kde je posledny vlozeny prvok.
Implementacia LIFO sa pouziva ako implementacia HW zasobniku, ktory sa pouziva napr. pri zasobnikovej orientovanej ISA. Zasobnik je ale uzitocny aj pri volani podprogramov, predavani parametrov, rekurzii apod.
FIFO
FIFO sa pouziva ako buffer, alebo inak, vyrovnavacia pamat, napr. na vyrovnanie rychlosti. Vkladaju sa medzi dve jednotky. FIFO moze byt znovu organizovane ako seriovo radene registre, alebo ako registre urcene ukazovatkom. Rozdiel voci LIFO je jasny, tentokrat nepojde prec posledny vlozeny prvok, ale pojde prec prvok, ktory sme tam vlozili ako prvy, takze pekne poporadi, ako v rade na pomarance.
Tu mame realizaciu pomocou seriovo radenych registrov. Rx su registre. Pi su bity platnosti podla hodnoty ktorych vieme, kam budeme zapisovat. Bity platnosti, to je riesenie asynchr. klopnym obvodom R-S a urcuju stav pamati. Ak je Pi = 0, tak je dane miesto prazdne. Ak je Pi = 1, tak je miesto platne a obsadene. Ak P1 je 1, tak pamat je plna a ak Pn je 0, tak je pamat prazdna.
Dajme tomu, ze Pn (vsetky) je 0 a pamat je prazdna. My chceme vlozit A. Vlozime A do 1. registra a posuvame az na poslednu poziciu. Pritom posuvame bity tak, ako na obrazku. Potom vlozime B a znovu posuvame. Vsimnite si nastavovanie bitov platnosti. Ked A chceme vybrat, tka znovu posunieme pozicie a zmenime bity. Zaroven si vsimnite, ze sa kopiruje stav predosleho obvodu. 
Dalsou moznostou je FIFO, kde registre su urcene ukazovatkom. Ukazovatko je opat dekoder, ale bez reverzibilneho citaca. Tentokrat tam prifarime citac v modulo (napr.4). Vsimnite si, ze mame 2 ukazovatka. K tomu mame dva dovody, 1. musime vediet, kam zapisovat a zaroven ukazovat na vrchol buffera (plnim zdola hore) a po druhe, HW FIFO sa pouziva medzi dvoma zariadeniami, takze poziadavka na zapis/citanie moze prist od dvoch roznych zariadeni a dokonca i sucasne, preto pouzijeme 2-branovu pamat.
Problem, ktory musime riesit je problem ukazovatok, ktore sa ocitnu na rovnakej pozicii. Znamena to, ze pamat je uplne plna alebo uplne prazdna (zalezi, ako s nimi pracujeme). Pouzijeme preto jednobitovu pamat, ktora sa nuluje, ak dojde k zhode ukazovatiek pri citani a nastavi do jednicky, ak dojde k zapisu.
Register je realizovany ako 2-branova pamat, ale trosku zjednodusena, nakolko nepotrebujeme 2 brany pre vstup a pre vystup, staci nam jedna. A preco to nie je jednobranova pamat? Pretoze potrebujem adresovat 2 miesta!!! aby som mohol sucasne citat a zapisovat 2 rozne pamatove miesta.
Poslednym typom adresovatelnej pamate, o ktore budeme hovorit je CAM (content accessed memory) asociativna pamat. Asociativna pamat moze mat rozne stupne asociativity. Co to znamena?- Stupen associativity 1 znamena, ze kazda polozka moze mat maximalne jedno miesto v pamati
- Plne asociativna pamat je taka, kde polozky sa mozu nachadzat kdekolvek v pamati a hladat sa musia v celej pamati
- Stupen asociativity s > 1 znamena, ze na jednu adresu mozme ulozit az s poloziek, ktorych kluce maju rovnaku adresu. Je rozdelena na tzv. sety a kazdy z nich obsahuje niekolko blokov. Set je teda priamo mapovany a kazdy set je vlastne priamo mapovany.
Plne asociativna pamat je realizovana tak, ako je na obrazku. K je kluc, P je bit platnosti a D su data. Pre takto organizovanu pamat musime vzdy porovnat kazdy kluc, az kym nenatrafime na ten spravny. Pokial chceme do pamate zapisovat a uz nemame volne miesto, tak musime pouzit nejaky algoritmus na uvolnenie miesta v pamati. 
Ak potrebujeme zapisovat do CAM a uz je plna, tak mame problem, musime si nejako vybrat. Ak je pamat priamo mapovana, tak to nie je taky problem, polozku zneplatnime a mozme ju nahradit (aspon mysli, pozri priamo mapovanu cache). Ak je pamat plne asociativna, alebo s obmedzenym stupnom asociativity, tak pouzijeme nejaky algoritmus.
- Least Recently Used (LRU), znamena to, ze nahradime najdavnejsie pouzitu polozku. LRU je pole s nad 2ma bitov v kazdom riadku a budeme sa nim este zaoberat.
- First In First Out (FIFO). To znamena, ze sa nahradi najstarsia polozka. V kazdom riadku bude log2(s) bitov.
- Random , tak, tento algoritmus ma spolocny citac pre vsetky polozky a log2(s) bitov pre celu pamat.
- Pseudo LRU je vlastne FIFO s ochranou naposledy pouzitej polozky. Ma pole ako LRU, kde sa nachadza citac a cislo naposledy pouzitej polozky. Pole obsahuje 2xlog2(s) bitov v kazdom riadku.
Least Recently Used algoritmus
Tento algoritmus obsahuje pole, kde si znaci polozky. Pole je o velkost s nad 2ma bitou v kazdom riadku (s nad 2 = s! / (s-2)!*2!). Algoritmus si vytvori maticu, kde sa vykasleme na prvky na diagonale, pretoze LRU ich ignoruje. Kazda pouzita polozka i bude mat po pouziti 1 v i-tom riadku a 0 v i-tom stlpci. Najdlhsie nepouzita polozka j bude mat 0 v j-tom riadku a 1-tky v i-tom stlpci. Priklad ukazuje postupne pouzite polozky 2,3,1,2,4.
1. spravime si maticu
1 2 3 4
1 X
2 X
3 X
4 X
2. pouzijeme polozku 2
1 2 3 4
1 X 0
2 1 X 1 1
3 0 X
4 0 X
3. pouzijeme polozku 3
1 2 3 4
1 X 0 0
2 1 X 0 1
3 1 1 X 1
4 0 0 X
4. pouzijeme polozku 1
1 2 3 4
1 X 1 1 1
2 0 X 0 1
3 0 1 X 1
4 0 0 0 X
4. pouzijeme polozku 2
1 2 3 4
1 X 0 1 1
2 1 X 1 1
3 0 0 X 1
4 0 0 0 X
5. pouzijeme polozku 4
1 2 3 4
1 X 0 1 0
2 1 X 1 0
3 0 0 X 0
4 1 1 1 X
Polozka 3 je najdlhsie nepouzitou polozkou.
