Kujtesa cache

Memoria cache është komponente e kompjuterit e cila ruan te dhënat në mënyrë që kerkesat për këto të dhëna të procesohen më shpejt. Cache-i përmban kopje të një pjesë të të dhënave të cilat ndodhen në memorien kryesore. Kur procesori tenton të lexoj një fjalë nga memoria, së pari kontrollon për këto të dhëna në cache memorie, nëse këto të dhëna ndodhet në cache, kjo e fundit i dërgohet procesorit. Ndërkaq nëse fjala e kërkuar nuk gjendet në cache, një bllok i memories kryesore që përmban fjalën e kërkuar lexohet në cache e pastaj fjala e kërkuar i dërgohet procesorit. Cache memoria i jep memories shpejtësi që i afrohet shpejtësisë së memorieve më të shpejta dhe njëkohësisht siguron kapacitet më të madhë të memories në një çmim më të ulët.

Madhësia e cache-it

Madhësia e cache-it duhet të jetë aq e vogël sa qe mesatarja e çmimit për bit të jetë e përafërt me atë të memories kryesore dhe aq e madhe sa që mesatarja e kohës së qasjes të jetë e përafert me qasjen vetëm në cache memorie. Janë edhe disa arsye tjera që na shtyejnë të zvogëlojmë madhesinë e cache-it. Pasiqë sa më e madhe të jetë madhësia e cache-it, aq më i madhë numri i portave të përfshir në adresim drejt cache-it. Rezultati është se cache-i më i madhë është më i ngadalshëm se sa cache-i më i vogël edhe nëse të dy janë ndërtuar me të njëjten teknologji të qarqeve të integruara dhe janë vendosur në të njëjtin vend në qip.

Funksionet e mapimit

Paiqë kemi më pak linja të cache-it se sa blloqe të memories kryesore duhet të zhvillohet një algoritëm i cili do të përcaktoj cilat blloqe te memories do të vendosen në linjat e cache-it. Përdoren tri teknika për mapim: mapimi direkt, mapimi asociativ dhe mapimi set asociativ.

Mapimi direkt

Teknika më e thjeshtë për mapim është mapimi direkt, me këtë metodë çdo bllok i memories kryesore mapohet në një linjë e lirë e cache-it.Figura tregon mekanizmin e përgjithshëm. Mapimi shprehet me formulen

i = j modulo m

i = numri linjës së cache-it j = numri i bllokut të memories kryesore m = numri i linjave të cache-it

Funksioni i mapimit implementohet lehtë duke përdorur adresën. Për qëllim të qasjes në cache, çdo adresë në memorien kryesore mund të konsiderohet si e përbërë nga tri fusha.Bitat më të parëndësishëm(bitat më të djathtë) w e përcaktojnë një fjalë ose bajt të memories kryesore. Bitat e mbetur s përcaktojnë njërin nga 2^s blloqet e memories kryesore. Logjika e cache-it i interpreton këto s bita si një etiketë(tag) prej s - r bitave (bitat më të majtë) dhe një fushë të linjës prej r bitave. kjo fusha e fundit indentifikon njërën nga m = 2^r linjat e cache-it.

Për ta përmbledhur,

Madhësia(gjatësia) e adresës = (s + w) bita
Numri i njësive të adresueshme = 2^{s + w} fjalë ose bajta
Madhësia e bllokut = madhësia e linjës = 2^w fjalë ose bajta
Numri i blloqeve në memorien kryesore = 2^{s + w} / 2^w = 2^s
Numri i linjave në cache = m = 2^r
Madhësia e etiketës = (s - r) bita

Cache memoria është komponente e kompjuterit e cila ruan te dhënat në mënyrë që kerkesat për këto të dhëna të procesohen më shpejt. Cache-i përmban kopje të një pjesë të të dhënave të cilat ndodhen në memorien kryesore. Kur procesori tenton të lexoj një fjalë nga memoria, së pari kontrollon për këto të dhëna në cache memorie, nëse këto të dhëna ndodhet në cache, kjo e fundit i dërgohet procesorit. Ndërkaq nëse fjala e kërkuar nuk gjendet në cache, një bllok i memories kryesore që përmban fjalën e kërkuar lexohet në cache e pastaj fjala e kërkuar i dërgohet procesorit. Cache memoria i jep memories shpejtësi që i afrohet shpejtësisë së memorieve më të shpejta dhe njëkohësisht siguron kapacitet më të madhë të memories në një çmim më të ulët.

Mapimi asociativ

Mapimi asociativ e mbulon mangësinë e mapimit direkt duke lejuar çdo bllok të memories kryesore të vendoset në cilëndo linjë të cache-it. Në këtë rast, logjika kontrolluese e cache-it do të interpretojë adresën e memories si një etiketë(tag) dhe si një fushë të fjalës.Fusha e etiketës e specifikon një bllok të memories kryesore. Që të përcaktojmë se a ndodhet në cache një bllok, logjika kontrolluese e cache-it vazhdimisht konrollon etiketën e çdo linjë të cache-it që të shoh se a përputhen. Figura tregon këtë logjik. Vërejmë se asnjë fushë e adresës nuk korresopodon me numrin e linjave të cache-it andaj përfundojmë se numri i linjave të cache-it nuk përcaktohet nga formati i adresës. Për ta përmbledhur,

Madhësia(gjatësia) e adresës = (s + w) bita
Numri i njësive të adresueshme = 2^{s + w} fjalë ose bajta
Madhësia e blloqeve = madhësia e linjave = 2^w fjalë ose bajta
Numri i blloqeve në memorien kryesore = 2^{s + w} / 2^w = 2^s
Numri i linjave në cache = i papërcaktuar
Madhësia e etiketës = s bita

Me mapimin asociativ ka fleksibilitet në qështjen se cili bllok të zëvendësohet kur një bllok i ri lexohet në cache. Mangësia kryesore e mapimit asociativ është në qarqet komplekse të cilat kërkohen për të ekzaminuar etiketat e të gjitha linjave të cache-it paralelisht.

Mapimi set asociativ

Mapimi set asociativ është një teknikë kompromisë e cila i merr përparësitë e mapimit direkt dhe atij asociativ. Në këtë rast cache-i ndahet në v bashkësi, ku çdonjëra përmban k linja. Lidhjet me tyre janë:

m = v x k i = j modulo v ku: i = numri i bashkësis së cache-it j = numri i bllokut të memories kryesore m = numri i linjave në cache Kjo njihet si k-mënyra e mapimit set asociativ.Me mapimin set asociativ, blloqet B_j mund të mapohen në çdo linjë të bashkësisë i. Në këtë rast, logjika kontrolluese e cache-it interpreton adresën në memoriesi tri fusha: etiketa, bashkësia dhe fjala. d bitat e bashkësisë specifikojnë njëren nga v = 2^d bashkësitë. s bitat e etiketës dhe fushës së bashkësisë specifikojnë njërinë nga 2^s blloqet e memories kryesore.Figura djathtas ilustron logjikën kontrolluese te ky lloj mapimi. për ta përfunduar,

Madhësia(gjatësia) e adresës = (s + w) bita
Numri i njësive të adresueshme = 2^{s + w} fjalë ose bajta
Madhësia e blloqeve = madhësia e linjave = 2^w fjalë ose bajta
Numri i blloqeve në memorien kryesore = 2^{s + w} / 2^w = 2^s
Numri i linjave në një bashkësi = k
Numri i bashkësive = v = s^d
Numri i linjave në cache = kv = k x 2^d
Madhësia e etiketës = (s - d) bita

Algoritmet e zëvendësimit

Kur linjat e cache-it janë mbushur dhe një bllok i ri sjellet në cache njëri nga blloqet duhet të zëvendësohet. Tek mapimi direkt është vetëm një linjë e caktuar për secilin bllok andaj nuk mund të bëjmë zgjidhje. Për mapimin asociativ dhe set asociativ nevojitet një algoritëm i mapimit. Që të arrijmë shpejtësi më të mëdha një algoritëm i tillë duhet të implementohet në hardver.Janë zhvilluar disa algoritme të tilla tri nga këto janë më të zakonshmet:Least Recently Used(LRC),First-in-first-out(FIFO),Least frecuently used(LFU) LRU - Ky algoritëm e zëvendëson atë bllok të bashkësisë i cili ka qëndruar më së gjati në cache pa u referencuar. FIFO - Ky algoritëm zëvendëson atë bllok të cache-it i cili ka qëndruar më së gjati në cache. Kjo teknik implementohet si një teknik rrethore bufer. LFU - Zëvendëson atë bllok në bashkësi i cili ka pranuar më së paku referenca. Kjo teknik mund të implementohet duke e lidhur nga një numërues në çdo linjë.

Referimet

Computer Organization and Architecture "William Stallings"
Advanced Computer Atchitecture "Hwang Kai"
Wikipedia "Cache"
Wikipedia "Cache memory"
Evaluating Associativity in CPU Caches,Hill M.
Gareth Tyson, Andreas Mauthe, Sebastian Kaune, Mu Mu and Thomas Plagemann. Corelli: A Dynamic Replication Service for Supporting Latency-Dependent Content in Community Networks. In Proc. MMCN'09 "pdf"