Keš centralne procesorske jedinice

Keš centralne procesorske jedinice je keš koji koristi CPU (engl. central processing unit - centralna procesorska jedinica) računara da bi se smanjilo prosečno vreme pristupa memoriji. Ako je keš manji, brža je memorija, koja čuva kopije podataka iz često korišćenih glavnih memorijskih lokacija. Sve dok su većina pristupa memoriji keširane memorijske lokacije, prosečna latentncija pristupa memoriji će biti bliža latenciji keša nego latenciji glavne memorije.

Pregledi

Kada procesor treba da se čita ili piše u nekoj lokaciji u glavnoj memoriji, on prvo proverava da li je kopija tih podataka u kešu. Ako je tako, procesor odmah čita ili piše iz keša, što je mnogo brže nego čitanje ili pisanje iz glavne memorije.

Većina modernih desktopa i serverskih CPUs imaju najmanje tri nezavisna keša: instrukciju keša radi brzine donošenja izvršnih instrukcija, podatke keša radi brzine donošenja podataka i skladištenja, i translation lookaside buffer (TLB) koji se koristi radi virtuelnog-u-fizički adresni prevod i za izvršne instrukcije i podatake. Keš podaci se obično organizuju kao hijerarhije keša višeg-nivoa (L1, L2, itd, vidi keševi višeg nivoa).

Keš ulazi

Podaci se prenose između memorije i keša u blokovima fiksne veličine, koji se zovu keš linije. Kada se keš linija kopira iz memorije u keš, kreira se keš ulaz. Keš ulaz će obuhvatiti kopirane podatke, kao i traženu memorijsku lokaciju (sada se zove tag).

Kada procesor treba da čita ili ispisuje lokaciju u glavnoj memoriji, on prvo proverava odgovarajući ulaz u kešu. Keševi proveravaju sadržaj zahtevane memorijske lokacije u svakoj od linija keša, koja može da sadrži tu adresu. Ako procesor utvrdi da je memorijska lokacija u kešu, javlja se keš pogodak. Međutim, ako procesor ne pronađe memorijsku lokaciju u kešu, javlja se promašaj keša. U slučaju:

• keš pogodka, procesor odmah čita ili ispisuje podatke u keš liniji
• keš promašaja, keš dodeljuje novi ulaz, i kopira u podacima iz glavne memorije; zatim, zahtev se ispunjava iz sadržaja keša.

Keš performanse

Procenat pristupa koji rezultuje u keš pogodku je poznat kao brzina pogodka, a može biti mera efikasnosti keša za dati program ili algoritam.

Promašaji čitanja odlažu izvršenje, jer oni zahtevaju da se podaci prenose iz memorije mnogo sporije nego iz samog keša. Ispisani promašaji mogu da dođu bez te kazne, jer procesor može da nastavi izvršenje dok se u pozadini podaci kopiraju na glavnoj memoriji.

Politika zamene

Da bi se napravilo mesta za novi ulaz na keš promašaj, keš mora da izbaci jedan od postojećih ulaza. Heuristički, da koristi izbor ulaza da bi izvršio izbacivanje, a što se zove politika zamene. Osnovni problem sa bilo kojom politikom zamene je da mora da se predvidi za koji postojeći ulaz keša je najmanje verovatno da će se koristiti u budućnosti. Predviđanje budućnosti je teško, tako da ne postoji savršen način da se izabere između različitih raspoloživih politika zamene.

Jedna popularna politika zamene, najmanje skoro korišćena, LRU (LRU - Least Recently Used), zamenjuje najmanje nedavno pristupni ulaz.

Obeležavanjem nekog memorijskog opsega kao ne-keša mogu da se poboljšaju performanse, izbegavanjem keširanja memorijskog regiona koji su retko ponovo pristupačni. Ovim se nešto izbegavaju režijski troškovi opterećenja u kešu, bez bilo kakvog ponovnog korišćenja.

• Keš ulazi takođe mogu biti isključeni ili zaključani u zavisnosti od konteksta.

Politika ispisa

Ako se podaci upisuju u keš, u nekom trenutku oni moraju da budu napisani na glavnoj memoriji. Tajming ovog pisanja je poznat kao politika ispisa.

• Pri pravovremenom ažuriranju (write-through) keša, svaki ispis keša izaziva ispis na glavnoj memoriji.
• Alternativno, u kešu vraćenog ažuriranja (write back) ili odloženog ažuriranja (copy back), ispisi se odmah ne preslikavaju na glavnu memoriju. Umesto toga, keš traži čije su lokacije ispisane preko drugih lokacija (ove lokacije se označavaju prljavim). Podaci u ovim lokacijama se ispisuju nazad u glavnu memoriju samo kada su podaci izbačeni iz keša. Iz tog razloga, promašaji čitanja u vraćenom ažurirajućem kešu mogu ponekad da zahtevaju dva memorijska pristupa: jedan da prvo ispiše prljavu lokaciju u memoriji, a zatim još da pročita novu lokaciju memorije.

Postoje pravila politike. Keš može da bude pravovremeno ažuriran, ali ispisi se mogu držati u privremenom redu skladišnih podataka, obično tako da više skladišta može da se obradi zajedno (što može da smanji bas preokrete i poboljša bas iskorišćenost).

Podaci u glavnoj memoriji keša mogu da se promene od strane drugih subjekata (npr. periferije koriste direktan pristup memoriji ili procesor sa više-jezgara), u kom slučaju kopija u kešu može da postane zastarela ili ustajala. Alternativno, kada CPU u procesoru sa više-jezgara ažurira podatke u kešu, kopije podataka u kešu, koje će se povezati sa drugim jezgrima, postaće ustajale. Komunikacioni protokoli između keš menadžera, koji održavaju doslednost podataka, su poznati kao keš koherentni protokoli.

CPU zastoji

Vreme potrebno da se donese jedna keš linija iz memorije (čitaj latencije) je bitno jer će CPU ostati bez stvari koje treba da uradi dok čeka na keš liniju. Kada CPU dostigne ovo stanje, to se zove zastoj.

Kako CPUs postaju brži, zastoj usled keš promašaja se pomera ka većim mogućnostima računanja; moderni CPUs mogu da izvršavaju stotine uputstva za vreme potrebno da se donese jedna keš linija iz glavne memorije. Različite tehnike se upotrebljavaju da bi se CPU održao radno aktivnim za to vreme.

• CPUs van funkcije (out-of-order) (Pentium Pro i kasnije Intel dizain, na primer) pokušavaju da izvrše nezavisne instrukcije posle instrukcije koja se čeka za keš promašene podatake.
• Još jedna tehnologija, koja se koristi od strane mnogih procesora, je simultani multitreding (simultaneous multithreading - SMT), ili - u Intel terminologiji – hipertreding (hyper-threading - HT), koji omogućavaju da alternativna nit koristi CPU jezgro, dok prva nit čeka da podaci dođu iz glavne memorije.

Keš ulazna struktura

Keš ulazni red obično je sledeće strukture:

tag

blok podataka

zastava bita(flag bits)

Blok podaci (keš linija) sadrže stvarne podatke učitane iz glavne memorije. Tag sadrži (deo od) adresu stvarnih podataka preuzetih iz glavne memorije. Flag bitovi su diskutovani u daljem tekstu.

Veličina keša je količina podataka glavne memorije koju on može da drži. Ova veličina se može izračunati kao broj bajtova koji se nalaze u svakom bloku podataka puta broj blokova smeštenih u kešu. (Broj taga i flag bitova je irelevantan za ovaj obračun, mada to ne utiče na fizičko područje keša).

Efektivna memorijska adresa je podeljena (MSB do LSB) na tag, indeks i blok ofset:

tag

indeks

blok ofset

Indeks opisuje koji je keš red (koja keš linija) unutar koga će se staviti podaci. Dužina indeksa je $\lceil \log _{2}({\text{cache rows}})\rceil$ bita. Blok ofset specificira željene podatke u sačuvanim podacima bloka u keš redu. Tipična efektivna adresa je u bajtovima, pa dužina blok ofseta je $\lceil \log _{2}(bytes\_per\_data\_block)\rceil$ bita. Tag sadrži najznačajnije adrese bitova, koje se proveravaju u odnosu na trenutni red (red je preuzet od strane indeksa) da se vidi da li je to onaj što nam treba ili drugi, nebitna memorijska lokacija gde se dogodio isti indeksni bit koji želimo. Oznaka dužina u bitovima je:$\mathrm {address\_length} -\mathrm {index\_length} -\mathrm {block\_offset\_length}$.

Neki autori blok ofset jednostavno zovu "ofset", ili "premeštanje“.

Primer

Originalni Pentium 4 ima četvorosmerni skup udruženih L1 keš podataka veličine 8 KB sa 64-bajt keš blokova. Dakle, postoji 8 KB/64= 128 keš blokova. To podrazumeva 128/4 = 32 skupa (a samim tim i 2 ^ 5 = 32 različita indeksa). Postoji 64 = 2 ^ 6 mogućih odstupanja. Pošto je adresa CPU od 32 bita, to znači 32 = 21 + 5 + 6, a samim tim podrazumeva 21 bita tag polja. Originalni Pentium 4 je takođe imao na osam-načina udruženi skup L2 integrisanog keša veličine 256 KB sa 128 bajt keš blokova. To podrazumeva 32 = 17 + 8 + 7, a samim tim i 17 bita tag polja.

Zastava (flag) bitovi

Keš instrukcija zahteva samo jedan flag bit po ulasku u red keša: važeći bit. Važeći bit označava da li je ili nije keš blok opterećen validnim podacima.

Pri uključenju računara, hardver postavlja sve važeće bitove u svim keševima na "nevažeće“. U drugim prilikama, neki sistemi takođe postavljaju važeći bit na "nevažeći", kao kada multi-master bus-snooping hardver u kešu jednog procesora sluša prenos adresa iz nekog drugog procesora, i shvata da su određeni blokovi podataka u lokalnom kešu sada ustajali i trebalo bi da budu označeni kao nevažeći.

Keš podatak obično zahteva dva flag bita po ulasku u keš red: važeći bit i takođe prljav bit. Prljav bit pokazuje da li je blok bio nepromenjen pošto je bio pročitan iz glavne memorije - "čist" - odnosno da li je procesor napisao podatke u tom bloku (a novu vrednost nije još napravio u glavnoj memoriji) - "prljav“.

Asocijativnost

Which memory locations can be cached by which cache locations

Politika zamene odlučuje gde će u kešu ići kopija određenog ulaza glavne memorije. Ako je politika zamene slobodna da izabere bilo koji ulaz u kešu da održi kopiju, keš se zove potpuno asocijativni (povezan). Sa druge strane, ako svaki ulaz u glavnoj memoriji može da ide na samo jedno mesto u kešu, keš je direktno mapiran. Mnogi keševi ispunjavaju kompromis u kome svaki ulaz u glavnoj memoriji može da ide u bilo koje od N-mesta u kešu, a opisani su kao N-načina asocijativnog skupa. Na primer, keš podaci nivoa-1 u AMD Athlon su dvosmerni asocijativni skup, što znači da bilo koja određena lokacija u glavnoj memoriji može da se sačuva u jednoj od dve lokacije u keš podacima nivoa-1.

Asocijativnost je kompromis. Ako postoji deset mesta na kojima politika zamene može imati mapirane memorijske lokacije, a zatim proveru da li je lokacija u kešu, moraju se pretražiti deset keš ulaza. Provera više mesta traži više energije, čip zona, i potencijalno vreme. S druge strane, keševi sa više asocijativnosti trpe manje promašaje (pogledati promašaje sukoba, dole), tako da procesor troši manje vremena za čitanje iz spore glavne memorije. Pravilo palca je da udvostručenje asocijativnosti, od direktno mapiranih u dvosmer, ili od dva puta do četiri puta, ima otprilike isti efekat na brzinu pogotka kao udvostručenje veličine keša. Asocijativnost povećana preko četiri puta ima mnogo manje uticaja na brzinu pogotka, i uglavnom se izvršava iz drugih razloga (vidi virtuelno izobličenje, dole).

U cilju lošijeg, ali jednostavno bolje nego složenog:

• direktni mapirani keš - najbolji (najbrži) pogodak vremena, i tako najbolji kompromis za "velike" kešove
• dvosmerni skup asocijativnog keša
• dvosmerni iskrivljeni asocijativni keš – 1993. godine, ovo je najbolji kompromis za keš čije su veličine bile u opsegu 4-8 KB
• četvorosmerni skup asocijativnog keša
• potpuno asocijativni keš - najbolje (najniže) promašene brzine, pa je najbolji kompromis kada je kazna za promašaj veoma visoka.

Direktno-mapirani keš

Ovde svaka lokacija u glavnoj memoriji može da ide samo na jedan ulaz u kešu. Ovde nema politike zamene kao takve, jer ne postoji izbor u kojem će keš ulazni sadržaji da se izbace. To znači da, ako se dve lokacije preslikavaju u isti ulaz, one mogu stalno da kucaju jedna drugoj. Mada jednostavnije, direktno mapirani keš mora da bude mnogo veći nego asocijativni da bi dao uporedive performanse, i više je nepredvidiv. Neka "k" bude broj bloka u kešu, "y" da bude blok broj memorije, i "n" da bude broj blokova u kešu, tada se mapiranje vrši pomoću jednačine k = y mod n.

Dvosmerni skup asocijativnog keša

Ako svaka lokacija u glavnoj memoriji može biti sačuvana u jednom od dve lokacije u kešu, jedno logično pitanje je: koja je od te dve? Najjednostavnija i najčešće korišćena šema, što je prikazano na desnoj slici iznad, je da se koriste najmanje značajni bitovi memorijskog lokacijskog indeksa kao indeksa za keš memoriju, kao i da postoje dva ulaza za svaki indeks. Jedna od prednosti ovog programa je da tagovi, koji se čuvaju u kešu, ne moraju da uključe taj deo glavne memorijske adrese, koja je prisutna u memorijskom keš indeksu. Pošto keš tagovi imaju manje bitova, oni uzimaju manju površinu na čipu mikroprocesora i mogu da se čitaju i brže porede. Takođe LRU je posebno jednostavan, jer samo jedan bit treba da se sačuva za svaki par.

Razmatranje izvršenja

Jedna od prednosti direktnog mapiranog keša je u tome što omogućava jednostavno i brzo razmišljanje. Kada je adresa izračunata, poznat je jedan keš indeks koji može imati kopiju te lokacije u memoriji. Taj keš ulaz može da se čita, a procesor može da nastavi da radi sa tim podacima pre nego što završi proveru da tag zapravo odgovara traženoj adresi.

Ideja da procesor koristi keširane podatke, pre nego što se tag kompletira može da se primeni na asocijativni keš. Podskup tag, zove se nagoveštaj, i može da se koristi za izbor samo jednog od mogućih keš ulaza koji mapiraju u traženoj adresi. Ulaz koji se selektuje nagoveštavanjem može tada da se koristi paralelno sa proverenim punim tagom. Tehnika nagoveštaja najbolje deluje kada se koristi u kontekstu adrese prevoda, kao što je objašnjeno u nastavku.

Dvosmerni iskrivljeni asocijativni keš

Predložene su i druge šeme, kao što je iskrivljni keš, gde je indeks za put 0 direktan, kao gore, ali indeks za put 1 se formira sa hash funkcijom. Dobra hash funkcija ima svojstvo da adrese koje se sukobljavaju sa direktnim mapiranjem, ne teže sukobu kada se mapira sa hash funkcijom, pa je manje verovatno da će program biti opterećen sa neočekivano velikim brojem promašenih sukoba, što potiče od patološkog pristupa obrascu. Loša strana sa računanjem hash funkcijom je ekstra kašnjenje. Pored toga, kada dođe vreme da se učita nova linija i izbaci stara linija, može da se desi da ona teško može da odredi koja postojeća linija je najmanje nedavno korišćena, jer se nove linije sukobljavaju sa podacima različitih indeksa u svakom putu; LRU traganje za neiskrivljene keševe se obično radi na po-skup bazama Ipak, iskrivljeni-asocijativni keš ima velike prednosti u odnosu na konvencionalne skup-asocijativne.

Pseudo asocijativni keš

Pravi skup-asocijativni keš istovremeno testira sve moguće načine, koristeći nešto kao sadržajno adresabilnu memoriju. Pseudo-asocijativni keš testira svaki mogući način, jedan po jedan. Primeri pseudo-asocijativnog keša su hash-rehash keš i kolona-asocijativni keš.

U uobičajenom slučaju pronalaženja pogotka, u prvom načinu testiranja, pseudo-asocijativni keš je brz kao i direktno-mapirajući keš, i ima mnogo manji sukob brzine promašaja nego direktno-mapirani keš, bliži promašaju brzine potpuno asocijativnog keša.

Keš promašaj

Keš promašaj se odnosi na neuspele pokušaje čitanja i ispisa dela, podataka u kešu, što rezultuje mnogo dužom latencijom u pristupu glavne memorije. Postoje tri vrste keša: instrukcije promašaja čitanja, podaci promašaja čitanja, i podaci promašaja ispisa.

'Keš promašaji čitanja iz instrukcija keša uglavnom izazivaju najveće kašnjenje, jer procesor, ili bar nit izvršenja, moraju da čekaju (oduglovače) dok se instrukcija preuzme iz glavne memorije.

Keš promašaji čitanja iz keš podataka obično izaziva manje kašnjenje, jer instrukcije ne zavise od keša čitanja i mogu da se izdaju i nastave izvršenje sve dok se podaci ne vrate iz glavne memorije, i zavisne instrukcije mogu da nastave izvršenje.

Keš promašeni ispisi u keš podacima obično izazivaju najmanje kašnjenje, jer ispisivanja mogu biti na čekanju i postoji nekoliko ograničenja na izvršenje naknadnih instrukcija. Procesor može da nastavi sa radom sve dok puni red.

U cilju smanjenja keš promašene brzine, veliki deo analiza je urađen u vezi keš ponašanja, u pokušaju da se pronađe najbolja kombinacija veličine, asocijativnosti, veličine bloka, i tako dalje. Sekvence memorijskih referenci koje obavljaju benchmark (mera vrednosti, standard odnosno važni (glavni) pokazatelj koji se koristi za komparativne svrhe) programi se čuvaju kao adresni tragovi. Shodno tome, analize simuliraju veći broj različitih mogućih keš dizajna na ovim dugim adresnim tragovima. Osećaj o tome kako mnoge promenljive utiču na keš brzinu pogotka može biti prilično zbunjujuć. Značajan doprinos ovoj analizi dao je Mark Hil, koji je odvojio promašaje u tri kategorije (poznate kao tri ZS):

• Obavezni promašaji su oni promašaji izazvani od strane prve reference u lokaciji u memoriji. Veličina keša i asocijativnost ne prave razliku u broju obaveznih promašaja. Prethodno donošenje može ovde da pomogne, kao što može veća veličina keš bloka (oblik prethodno donošenja). Obavezni promašaji se ponekad nazivaju i hladni promašaji.
• Kapacitet promašaja su oni propusti koji se javljaju bez obzira na asocijativnost ili veličinu bloka, i isključivo se javljaju zbog konačnih veličina keševa. Kriva kapaciteta brzine promašaja u odnosu na veličinu keša daje neku meru vremenskog lokaliteta. Treba imati na umu da ne postoji koristan pojam keša "pun" ili "prazan", ili "bliski kapacitet": CPU keševi gotovo uvek imaju skoro svaku liniju ispunjenu sa kopijom nekog reda u glavnoj memoriji, a skoro svaka dodela novih linija zahteva izbacivanje stare linije.
• Promašaji sukoba su oni promašaji koji su se mogli izbeći, da keš nije ranije izbacio ulaz. Konflikt promašaji mogu dalje da se dele na mapirane promašaje, koji neizbežno daju posebnu količinu asocijativnosti, i zamenu promašaja, koji potiču od naročitog izbora žrtve politike zamene.

Miss rate versus cache size on the Integer portion of SPEC CPU2000

Grafikon sa desne strane rezimira učinak keša koji se vidi na celobrojnom delu SPEC CPU2000 benchmark dat od strane Hila i Kantina. Ovi benchmarks su sa ciljem da predstave vrstu posla da bi se inženjerska računarska radna stanica mogla videti bilo kog dana. Čitalac treba da ima ima u vidu da je veoma teško pronaći benchmarks, koji uvek moraju korisno da zastupaju mnoge programe, i uvek će biti važni programi sa vrlo različitim ponašanjem.

Mogu da se vide različiti efekti tri Cs u ovom grafikonu.

Na krajnjem desnom delu grafikona, sa veličinom keša sa oznakom "inf", nalaze se obavezni promašaji. Ako se želi poboljšanje performansi jedne mašine na SpecInt2000, povećavanje veličine keša preko 1 MB, suštinski je beskorisno. To je uvid dat pomoću obaveznih promašaja.

Potpuno asocijativni keš brzine promašaja je većinom predstavnik kapaciteta brzine promašaja. Razlika je u tome što predstavljeni podaci jesu iz simulacija koje pretpostavljaju LRU politike zamene. Prikaz kapaciteta promašene brzine zahteva savršenu politiku zamene, tj. proročanstvo koje gleda u budućnost da se pronađe ulaz keša, koji u stvari neće biti pogodak.

Treba imati na umu da približavanje kapacitetu promašene brzine pada strmo između 32 KB i 64 KB. Ovo ukazuje da benchmark ima radni skup od grubo 64 KB. CPU keš dizajner, koji ispituje ovaj benchmark, imaće jak podsticaj u skupu keša veličine 64 KB, pre nego 32 KB. Treba imati na umu, za ovaj benchmark, da nikakva količina asocijativnosti ne može napraviti 32 KB keš da izvršava isto što i 64 KB 4-puta, ili čak direktno mapirani 128 KB keš.

Konačno, treba imati na umu da između 64 KB i 1 MB postoji velika razlika između direktno mapiranih i potpuno asocijativnog keša. Ova razlika je sukob promašene brzine. Uvid u sukobe promašenih brzina pokazuje da sekundarni keš koristi mnogo iz visoke asocijativnosti.

Ova pogodnost je dobro poznata u kasnim 1980-im i ranim 1990.im godinama, kada CPU dizajneri nisu mogli da sklope velike keševe na-čipu, i nisu mogli da dobiju dovoljno propusnog opsega za bilo keš memorijske podatake bilo keš tag memorije za primenu visoke asocijativnosti u van-čip keševima. Očajno hakovanje su pokušali: MIPS R8000 koji je koristio skup van-čip posvećen tag SRAMs, koji je bio namenjen tag komparatorima i velikim drajverima na meč linijama, kako bi se sproveo 4 MB četvorosmerni asocijativni keš. MIPS R10000 koristi obične SRAM čipove za tag. Tag pristup za oba puta uzima dva ciklusa. Za smanjenje latencije, R10000 pretpostavlja na koji način bi keš pogodio na svakom pristupu.

Adresne promene

Većina CPUs opšte namene primenjuju neku vrstu virtuelne memorije. Rezime, ili svaki program koji radi na mašini vidi svoj pojednostavljeni adresni prostor, koji sadrži šifru i podatke za taj program, ili svi programi se pokreću u zajedničkom virtuelnom adresnom prostoru. Program koristi virtuelni adresni prostor u kome može da radi bez obzira gde određene lokacije u tom adresnom prostoru postoje u fizičkoj memoriji.

Virtuelna memorija zahteva da procesor prevodi virtuelne adrese koje generišu program u fizičkoj adresi u glavnoj memoriji. Deo procesora koji radi ovaj prevod je poznat kao memorijska upravljačka jedinica (memory management unit - MMU). Brz put kroz MMU može da obavi te prevode koji su uskladišteni u prevodu bafera TLB (translation lookaside buffer), koji je keš mapira iz operativne sistemske strane tabele, segmentnog stola ili oba.

Za potrebe ove diskusije, postoje tri važne odlike adresnog prevoda:

• Latencija: fizička adresa je dostupna neki put iz MMU, možda nekoliko ciklusa, pošto je virtuelna adresa dostupna iz adresnog generatora.
• Pseudonim (Aliasing): više virtuelnih adresa mogu da se mapiraju na jednu fizičku adresu. Većina procesora garantuje da će se sve ispravke u toj jednoj fizičkoj adresi desiti u programskom redu. Da bi se ovo garantovalo, procesor mora da osigura da se samo jedna kopija fizičke adrese nalazi u kešu u bilo kom trenutku.
• Granulacija: virtuelni adresni prostor je podeljen na stranice. Na primer, 4 GB virtuelni adresni prostor može biti isečen na 1048576 stranica veličine 4 KB, od kojih svaki može samostalno da se mapira. Može biti više podržanih veličina stranica; vidi virtuelnu memoriju za izradu.

Istorijska napomena: neki rani virtuelni memorijski sistemi su bili veoma spori, jer su zahtevali pristup stranici tabele (držana u glavnoj memoriji) pre svakog programiranog pristupa glavnoj memoriji. Bez keševa, ovo efektivno smanjuje upola brzinu mašine. Prvi keš hardver koji se koristio u računarskom sistemu nije zapravo podatak ili keš instrukcija, već TLB.

Keš se može podeliti na 4 vrste, na osnovu toga da li indeks ili tag odgovaraju fizičkim ili virtuelnim adresama:

• Fizički indeksirani, fizički tagirani (PIPT) keševi koriste fizičku adresu i za indeks i za tag. Iako je ovo jednostavno i izbegava probleme sa pseudonimom, takođe je sporo, kako se fizička adresa mora pogledati (što bi moglo uključiti TLB promašaj i pristup glavnoj memoriji) pre nego što se adresa može pogledati u kešu.
• Virtuelno indeksirani, virtuelno tagirani (VIVT) keševi koriste virtuelnu adresu i za indeks i za tag. Ova keširana šema može da dovede do mnogo brže pretrage, jer MMU ne treba prvo konsultovanje određivanja fizičke adrese za datu virtuelnu adresu. Međutim, VIVT pati od pseudonim problema, gde nekoliko različitih virtuelnih adresa mogu da se odnose na istu fizičku adresu. Rezultat je da će takva adresa biti keširana odvojeno, što ukazuje na istu memoriju, koja uzrokuje probleme koherentnosti. Drugi problem je homonim, gde iste virtuelne adrese mapiraju u nekoliko različitih fizičkih adresa. Nije moguće napraviti razliku između ovih mapiranja, gledajući samo u virtualni indeks, mada potencijalna rešenja uključuju: ispiranje keša nakon konteksta prekidača, primoravajući adresne prostore da budu ne-preklapajući, tagiranje virtuelne adrese sa adresnim prostorom ID (ASID), ili korišćenje fizičkih tagova. Pored toga, postoji problem koji može menjati virtuelno-na-fizičko mapiranje, što bi zahtevalo ispiranje keš linije, kako VAs više neće važiti.
• Virtualno indeksirani, fizički tagirani (VIPT) kešovi koriste virtuelnu adresu za indeks i fizičku adresu u tagu. Prednost nad PIPT je manja latencija, kako se keš linija može gledati paralelno sa TLB prevodom, međutim tag ne može da se poredi dok nije dostupna fizička adresa. Prednost nad VIVT je, da budući da tag ima fizičku adresu, i keš može detektovati homonime. VIPT zahteva više tag bita, kako indeks bitovi više ne predstavljaju istu adresu.
• Fizički indeksirani, virtualni tag (PIVT) keševi su samo teoretski, jer u suštini bi bili beskorisni.

Brzina ovog recidiva (opterećenje latencije) je od ključnog značaja za CPU performanse, pa tako većina modernih keševa nivoa-1 su virtualno indeksirani, što barem dozvoljava MMU-ovom TLB pronalaženju da se odvija paralelno sa preuzimanjem podataka iz keš RAMa.

Ali virtuelno indeksiranje nije najbolji izbor za sve nivoe keša. Troškovi koji se odnose na virtuelni pseudonim rastu sa keš memorije, a kao rezultat toga većina keševa nivoa-2 i većeg su fizički indeksirani.

Keševi istorijski koriste i virtuelne i fizičke adrese za keš tag, iako je sada virtuelno tagiranje neobično. Ako se TLB pronalaženje može završiti pre pronalaženja keš RAMa, onda je fizička adresa dostupna na vreme za tag poređenje, i nema potrebe za virtuelnim tagiranjem. Veliki keševi, onda, imaju tendenciju da budu fizički tagirani, a samo mali, veoma niske latencije keševi su virtualno tagirani. U nedavnim opšte namenskim CPUs, virtuelno tag označavanje zamenjeno je sa vhints, kao što je opisano u nastavku.

Problemi homonima i sinonima

Keš koji se oslanja na virtuelno indeksiranje i tagiranje postaje nedosledno nakon što se ista virtuelna adresa preslika u različite fizičke adrese (homonim). Ovo se može rešiti korišćenjem fizičke adrese za tagiranje ili čuvanjem adresnog prostora ID u keš liniji. Međutim, drugi od ova dva pristupa ne pomaže u rešenju sinonim problema, gde nekoliko keš linija završava čuvanje podataka za istu fizičku adresu. Pisanje u takvoj lokaciji može ažurirati samo jednu lokaciju u kešu, ostavljajući druge sa nedoslednim podacima. Ovaj problem se može rešiti pomoću ne-preklapajućeg memorijskog rasporeda za različite adresne prostore ili inače keš (ili njehov deo) mora da bude ispran kada se menja mapiranje.

Virtualni tag i hint

Velika prednost virtualnih tagova je da, za asocijativne keševe, oni dozvoljavaju da tag nastavi meč pre nego se izvrši virtuelni fizički prevod. Međutim,

• povezanost probi i izbacivanja predstavljaju fizičku adresu za akciju. Hardver mora da ima neka sredstva za pretvaranje fizičke adrese u keš indeks, generalno gledano, pomoću fizičkih tagova, kao i virtuelnih tagova. Za poređenje, fizički tagirani keš ne mora da drži virtuelne tagove, što je jednostavnije.
• Kada se virtuelno fizičko mapiranje briše iz TLB, keš ulazi sa tim virtuelnim adresama će morati nekako da se isteraju. Alternativno, ako se keš ulazi dozvoljeni na stranicama ne mapiraju pomoću TLB, onda će ti ulazi morati da se isteraju, kada se na pravi način pristupi tim stranicama promene na stranici tabele.

Takođe, moguće je za obezbeđenje operativnog sistema da se nijedan od virtualnih pseudonima istovremeno nalazi u kešu. Operativni sistem daje ovu garanciju za sprovođenje obojenja stranice, što je opisano u nastavku. Neki rani RISC procesori (SPARC, RS/6000) uzimaju ovaj pristup. On se nije nedavno koristio, kada su pali troškovi hardvera i izbacivanje virtuelnog pseudonima i povećani su složenost softvera i kaznene performanse savršenog bojenja stranice.

To može biti korisno u razlikovanju dve tag funkcije u asocijativnim kešu: one se koriste da bi se odredio izbor načina ulaza skupa, i one se koriste za utvrđivanje da li postoji keš pogodak ili promašaj. Druga funkcija uvek mora da bude tačna, ali je dozvoljeno za prvu funkciju da odgovori, i da povremeno pogrešno odgovori.

Neki procesori (npr. rani SPARCs) imaju keševe sa virtualnim i fizičkim tagovima. Virtuelni tagovi se koriste za način selekcije, a fizički tagovi se koriste za određivanje pogodka ili promošaja. Ova vrsta keša uživa prednost latencije virtualno tagiranog keša, kao i jednostavan softverski interfej fizički tagiranog keša. Ovo donosi dodatne troškove dupliranja taga. Takođe, u toku obrade promašaja, alternativni načini keš indeksiranih linija treba da budu istraženi za virtualne pseudonime i bilo koje prilagodljivo izbacivanje.

Dodatni prostor (i neka latencija) može da se ublaži držanjem virtualnog hints (nagoveštaja) sa svakim keš ulazom umesto virtualnih tagova. Ovi hints su podskup ili seckani virtualni tag, a koriste se za izbor načina keš iz kojeg bi se dobili podaci i fizički tag. Kao virtualni tag keš, može biti virtualni hint meč, ali fizički neusklađen tag, u kom slučaju keš ulaz sa odgovarajućim hint mora da bude izbačen, tako da će keš pristupi posle popune keša na ovoj adresi imati samo jednu hint meč. Pošto virtuelni hints imaju manje bitova od virtuelnih tagova koji se razlikuju jedan od drugog, virtualni hint keš pati od više sukobljenih promašaja nego virtualni tagirani keš.

Možda krajnja redukcija virtualnih hints se može naći u Pentium 4 (Willamette i Northwood jezgrima). U ovim procesorima virtuelni hint je efektivno 2 bita, a keš je na 4-načina asocijativni skup. Efektivno, hardver održava jednostavnu permutaciju iz virtuelne adrese u keš indeksu, tako da nijedan CAM (content-addressable memory - sadržajne-adresirane memorije) nije potreban u izboru jednog pravog od četiri učitanih načina.

Bojenje strane

Veliki fizički indeksirani keš (obično sekundarni keš) pokreću problem: operativni sistem, a ne aplikacija upravlja stranicama koje se sudaraju jedna sa drugom u kešu. Razlike u dodeli stranice iz jednog programa, koji se kreće u sledeći, dovodi do razlike u obrascima keš sudara, što može dovesti do veoma velikih razlika u programskom izvođenju. Ove razlike mogu da učine da on veoma teško dobije konzistentno i ponovljivo vreme za benchmark tok.

Da bi se razumeo problem, treba da se zamisli CPU sa 1 MB fizički indeksiranim direktno mapiranim kešom nivoa-2 i 4 KB virtualno memorijskom stranicom. Sekvencijalne fizičke stranice prave mapu u sekvencijalnim lokacijama u kešu sve dok se posle 256 strana obrazac obavije okolo. Može da se obeleži svaka fizička stranica sa bojom od 0-255 za označavanje gde u kešu ona može da ide. Mesta unutar fizičkih stranica sa različitim bojama ne mogu da se sukobe u kešu.

Programer, koji pokušava da napravi maksimalnu korist od keša, može da organizuje svoj programski pristup obrascima, tako da samo 1 MB podataka treba da bude keširan u svakom trenutku, čime se izbegava kapacitetni promašaj. Ali on takođe treba da osigura da pristup obrascima neće imati sukob promašaja. Jedan od načina da se razmišlja o ovom problemu jeste da se podele virtuelne stranice koje program koristi i njima dodele virtuelne boje na isti način kao što su ranije fizičke boje bile dodeljivane fizičkim stranicama. Programer onda može da organizuje pristup obrascima njegovog koda, tako da ne postoje dve stranice sa istom virtuelnom bojom u upotrebi u isto vreme. Postoji široka literatura o takvim optimizacijama (npr. Loop nest optimization), koja u velikoj meri dolazi iz zajednice High Performance Computing (HPC).

Prepreka je ta, da dok su sve stranice u upotrebi, u svakom trenutku mogu da imaju različite virtuelne boje, a neke mogu imati iste fizičke boje. U stvari, ako operativni sistem dodeljuje fizičke stranice na virtualne stranice nasumično i ravnomerno, veoma je verovatno da će neke stranice imati istu fizičku boju, a zatim od lokacije tih stranica će se sudariti u kešu (ovo je rođendanski paradoks).

Rešenje je da postoji pokušaj operativnog sistema da dodeli različite fizičke bojene stranice u različitim virtualnim bojama, tehnikom koja se zove bojenje stranica. Iako je stvarno mapiranje iz virtuelne u fizičke boje nebitno za sistemske performanse, neparno mapiranje je teško pratiti i od male je koristi, tako da većina pristupa bojenju stranica jednostavno pokušava da zadrži iste fizičke i virtuelne bojene stranice.

Ako operativni sistem može da garantuje da svaka fizička stranica mapuje (preslikava) u samo jednoj virtuelnoj boji, onda nema virtualnih pseudonima, a procesor može da koristi virtualno indeksirani keš, bez potrebe za dodatnim probama virtualnih pseudonima tokom rukovanja promašajem. Alternativno, O/S može da isprazni stranicu iz keša kad god se ona menja od jedne do druge virtuelne boje. Kao što je već pomenuto, ovaj pristup je korišćen nešto ranije za SPARC i RS/6000 dizain.

Keš hijerarhija na modernim procesorima

Memory hierarchy of an AMD Bulldozer server.

Moderni procesori imaju više interaktivnih keševa na čipu.

Rad partikularnih keš memorija može biti potpuno određen:

• Veličinom keša
• Veličinom keš bloka
• Brojem blokova u skupu
• Politikom zamenjivanja keša
• Politikom upisivanja u keš (write-through ili write-back)

Iako su svi keš blokovi u određenom kešu iste veličine i imaju istu asocijativnost, tipični keševi „nižih-nivoa“ ("lower-level" cashs) (kao L1 keš) su manje veličine, imaju manje blokove, i manji broj blokova u skupu, dok su keševi „viših-nivoa“ ("higher-level" cashs) (kao L3 keš) veći, imaju veće blokove i više blokova u skupu.

Specijalizovani keševi

Dovodna linija CPUs pristupne momorije iz više tačaka u dovodnoj liniji: donošenje uputstva, prevođenje virtuelnih u fizičke adrese i donošenje podataka (vidi classic RISC pipeline). Prirodni dizain koristi više keševa za svaku od ovih stavki, tako da ni jedan fizički resurs ne bi morao da bude planiran da obavlja dve stari u dovodnoj liniji. Tako da se dovodna linija prirodno završava sa najmanje tri razdvojena keša (instrukcija, TLB i podatak), od kojih je svaki specijalizovan sa određenu ulogu.

Žrtveni keš

Žrtveni keš je keš koji se koristi da čuva izbačene blokove od CPU keša nakon zamene. Žrtveni keš leži između glavnog keša i njegovih puteva dopune, a čuva samo blokove koji su izbačeni iz glavnog keša. Žrtveni keš je obično potpuno asocijativan, i pokušava da smanji broj konfliktnih promašaja. Većina često korišćenih programa ne zahteva asocijativno mapiranje za sve pristupe. U stvari, samo mali deo memorijskog pristupa programa zahteva visoku asocijativnost. Žrtveni keš eksploatiše ovo svojstvo tako što omogućava visoku asocajativnost samo ovim pristupima. Uveo ga je u upotrebu Norman Jouppi 1990.

Intelova Crystal Well varijanta Haswell procesora, opremljena sa Intelovim Iris Pro GT3e integrisanom grafikom i 128MB eDRAM-a, uvela je keš nivoa-4 na čipu, koji se koristi kao žrtveni keš za procesorski keš novoa-3.

Trag keš

Jedan od ekstemnijih primera specijalizacije keša je trag keš koji se javlja u mikroprocesoru Intel Pentiuma 4. Trag keš je mehanizam za povaćavanje protoka za donos instrukcija i smanjenja potrošnje energije (u slučaju Pentium 4) skladištenjem traga instrukcija koje su već bile preuzete i dekodirane.

Najraniji zapis za široku akademsku publiku vezan je za: Eric Rotenberg, Steve Bennett, i Jim Smith u njeihovom članku "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching."

Rana publikacija je bila data u US patent 5381533, Alex Peleg and Uri Weiser of Intel Corp., "Dynamic flow instruction cache memory organized around trace segments independent of virtual address line" , Alex Peleg i Uri Weiser iz Intel Corp. „Dinamičan tok instrukcija keš memorije je organizovan oko toka segmanta nezavisnog od virtualne adrese linije“, nastavak podnesene prijave 1993. godine, koja je kasnije napuštena.

Trag keš čuva instrukcije, ili nakon što su bile dekodovane, ili jer su povučene. Generalno, instrukcije se u grupama dodaju trag kešu, predstavljajuću ili bazični blok ili dinamični trag instrukcija. Dinamični trag („put traga“) sadrži samo instrukcije čiji se rezultat koristi, a eliminiše instrukcije nakon uzetih grana (pošto se one neizvršavaju); dinamični trag može biti sastavljen od više bazičnih blokova. Ovo omogućava da uputstva donesu jedinici procesora nekoliko bazičnih blokova, bez brige na grane u izvršenju toka.

Trag linije se čuva u trag kešu baziranom na programskom brojaču prve instrukcije u tragu i skupu predviđenih grana. Ovo omogućava da se različiti trag putevi čuvaju na istoj adresi, od kojih svaka reprezentuje drugu granu na izlazu. U instrukcijskom stanju donošenja dovodne linije, trenutni programski brojač zajedno sa skupom grana predviđanja se proverava u trag kešu radi pogotka. Ako postoji pogodak, za preuzimanje se isporučuje trag linija, koja ne mora da ide do regularnog keša ili do memoraije za te instrukcije. Trag keš nastavlja da hrani donetu jedinicu sve dok se trag put ne završi ili dok ne dođe do nepredviđenih događaja u dovodnoj liniji. Ako je promašaj, novi trag počinje da se gradi.

Pentium 4 trag keš skladišti mikrooperacije dobijene dekodiranjem x86 instrukcija, i takođe omogućava funkcionisanje mikrooperacija keša. Imajući ovo, sledeći put kada je instrukcija potrebna, ona ne mora ponovo da se dekoduje u mikrooperatore.

Mikrooperacioni (uop) keš

Mikrooperacioni keš (uop Cache, UC) je specijalizovan keš koji čuva mikrooperacije dekodovanih instrukcija, koje je primio direktno od instrukcijskog dekodera ili od instrukcijskog keša. Kada se instrukcija mora dekodovati, uop keš se provarava za njegovu dekodovanu formu koja se ponovo koristi ako je keširana; ako nije dostupna, instrukcija se dekoduje pa tek onda kešira.

Jedan od najranijih radova koji opisuje uop keš kao alternativu sa prednjeg kraja za Intel P6 pprocesor familiju, je članak iz 2001. godine "Micro-Operation Cache: A Power Aware Frontend for Variable Instruction Length ISA". Kasnije, Intel je uključio uop keš u Sandy Bridge procesore i u uspešne mikroarhitekture kao Ivy Bridge i Haswell.

Donošenje završeno predekodiranih instrukcija eliminiše potrebu da se u više navrata dekodira dužina promenljive kompleksnim instrukcijama u prostije fiksirane-dužine mikrooperacije, a pojednostavljuje procese predviđanja, privlačenja, rotiranja i svrstavanja privučenih instrukcija. Uop keš efektno rasterećuje donos i hardver za dekodovanje, tako smanjuje potrošnju energije i poboljšava snabdevanje sa prednje strane dekodovanim mikrooperacijama. Uop keš takođe povećava perfomanse zato što konstantnije isporučuje dekodovane mikrooperacije na kraj i eliminiše razna uska grla u CPU's donešenju i logici dekodovanja.

Uop keš ima dosta sličnosti sa trag kešom, iako je uop keš mnogo jednostavniji i obezbeđuje bolju potrošnju energije. Glavni nedostatak trag keša, vodi do njegove potrošnje energije, odnosi se na hardversku složenost potrebnu za njengovo heurističko odlučivanje o keširanju i ponovnim korišćenjem dinamičko kreiranih tragova instrukcije.

Keševi sa više nivoa

Drugi problem je fundamentalni kompromis između keš kašnjenja i brzine pogotka. Veći keševi imaju bolju brzinu pogađanja ali veće kašnjenje. Da bi se postigao kompromis, mnogi računari koriste keš u više nivoa, sa malim brzim kešom koji je potpomognut većim, sporijim kešom.

Keševi višeg nivoa operišu tako što prvo proveravaju najmanji keš nivoa-1 (L1); ako je pogodak, procesor nastavlja velikom brzinom. Ako je mali keš promašaj, sledeći veći keš (L2) se proverava, i tako dalje, pre nego što se proveri spoljašnja memorija.

Pošto latencija (kašnjenje) između glavne memorije i brze keš memorije postaje sve veće, neki procesori su počeli da koriste čak tri nivoa keša na čipu. Na primer, Alpha 21164 (1995) je imao 1 do 64 MB van-čipa L3 keš; IBM POWER4 (2001) imao je van-čipa L3 keš od 32 MB po procesoru, podeljen između nekoliko procesora; Itanium 2(2003) imao je 6 MB ujedinjeni L3 keš na-čipu; Itanium 2 (2003) MX 2 Module obuhvata dva Itanium2 procesora sa deljenim 64 MB L4 keš memorijom na multi-čip modulu koji je pinski kompatibilan sa Madison procesorom; Intel-ov XeonMP proizvod pod kodnim nazivom "Tulsa" (2006) ima 16 MB na-čipu L3 keša koji učestvuje između dva procesorska jezgra; AMD Phenom II (2008) ima do 6 MB na-čipu ujedinjenu L3 keš memoriju; i Intel Core i7 (2008) ima 8 MB na-čipu ujedinjenu L3 keš memoriju koja je inkluzivna, koju dele sva jezgra. Korist od L3 keša zavisi od pristupa aplikaciji za obrasce.

Konačno, na drugom kraju memorijske hijerarhije, CPU registrski fajl se može smatrati najmanjim, najbrži kešom u sistemu, sa posebnim karakteristikama koje su planirane u softveru – obično pomoću kompajlera, jer on dodeljuje registru da čuva vrednost preuzetu iz glavne memorije. (Posebno vidi petlje optimizacije gnezda.) Registarski fajlovi ponekad imaju hijerarhiju: Cray-1 (oko 1976) je imao osam adresa "A" i osam skalarnih podataka "S" registra koji su generalno bili upotrebljivi. Tu je bio i skup od 64 adresa "B" i 64 skalarnih podataka "T" registra kojima je trebalo više vremena za pristup, ali su bili brži od glavne memorije. "B" i "T" regisri su obezbeđeni zato što Cray-1 nije imao keš podatke. (Cray-1 je, međutim, imao keš instrukcije.)

Čipovi sa više jezgara

Kada uzmemo u razmatranje čip sa više jezgara, postavlja se pitanje da li keševi treba da budu podeljeni ili lokalni za svako jezgro. Implementacija deljenog keša nesumnjivo uvodi više žičanog voda i veću kompleksnost. Ali tada, kada imamo jedan keš po čipu, radije nego po jezgru, značajno smanjujemo potrebni prostor, i zato se može dobiti veći keš. Obično se nalazi da je podeljen L1 keš nepoželjan pošto se povećava latencija, pa tako će svako jezgro raditi monogo sporije nego jendo-jezgreni čip. Ali tada, za najviši nivo (poslednji koji se zove pre pristupanja memoriji), iz više razloga poželjno je da se ima globalni keš. Na nprimer, osmo-jezgarni čip sa tri novoa može da ima L1 keš za svako jezgro, i L3 deljeni keš sa svim jezgarima, i sa L2 srednjim kešom, npr. jedan za svaki par jezgara.

Podeljeni naspram ujedinjenih

U strukturi podeljenog keša, instrukcije i podaci se odvojeno keširaju, što znači da se keš linije koriste za keširanje ili instrukcije ili podatke, ali ne i oba. U ujedinjenom, ova ograničenja su ukinuta.

Ekskluzivni naspram ingluzivnog

Keš sa više nivoa uvodi nova dizajnerska rešenja. Na primer, u nekim procesorima, svi podaci u L1 kešu moraju takođe biti negde u L2 kešu. Ovi keševi se zovu strogo inkluzivni. Drugi procesori (kao AMD Athlon) imaju ekskluzivni keš – garantuje se da su podaci u najviše jednom kešu L1 ili L2, nikada u oba. Neki drugi procesori (kao Intel Pentium II, III i 4) ne zahtevaju da podaci u L1 kešu budu i u L2 kešu, iako se to često može učiniti. Ne postoji jedinstveno prihvaćeno ime za ovu srednju politiku.

Prednost ekskluzivnog keša je da skladišti više podataka. Ova prednost je veća kada je ekskluzivni L1 keš uporediv sa L2 kešom, a umanjuje se ako je L2 keš nekoliko puta veći od L1 keša. Kada su L1 promašaj i L2 pogodak na pristupu, pogođena keš linija u L2 kešu se menja sa linijom u L1 kešu. Ovaj proces razmenjivanja zadaje malo više posla od običnog kopiranja iz L2 u L1, a to je ono šta inkluzivni keš radi.

Jedna prednost striktno inkluzivnog keša je da kada eksterni uređaj ili drugi procesor u multiprocesorskom sistemu poželi da ukloni keš liniju iz procesora, procesor treba samo da proveri L2 keš. U keš hijerarhiji koja ne primenjuje inkluziju, L1 se takođe mora proveriti. Kao mana, postoji korelacija između asocijativnih L1 i L2 keša: ako L2 keš nema barem onoliko puteva kao što imaju svi L1 keševi zajedno, efikasna asocijativnost L1 je ograničena. Još jedna mana inkluzivnog keša je ta da kada god se dešava izbacivanje iz L2 keša, (možda) odgovarajuće linije u L1 takođe moraju biti izbačene da bi se sačuvala inkluzivnost. Ovde je malo više posla, i rezultuje većim promašajima u L1 kešu.

Još jedna mana inkluzivnog keša je ta da veći keš koristi veće keš linije, koji smanjuju veličinu taga na sekundarnom kešu. (Ekskluzivni keš zahteva da oba keša imaju keš linije iste veličine, tako da bi se linije mogle zameniti prilikom L1 promašaja i L2 pogotka). Ako je sekundarni keš za red veličine veće od primarnog, a keš podaci za jedan red veličine veći od keš taga, ovaj sačuvana oblast taga može biti upoređivan u inkrementalnoj oblasti koja je potrebna da skladišti L1 keš podatke u L2.

Primer: K8

Da bi ilustovali specijalizovani keš u više nivoa, ovde je prikazana keš hijerarhija K8 jezgara u AMD Athlon 64CPU.

Primer K8 keš hijerarhije

K8 ima 4 specijalizovana keša: instrukcioni keš, instrukcioni TLB, TLB za podatke, i keš za podatke. Svaki od ovih keševa je specijalizovan:

• Instrukcioni keš čuva kopije 64 bajtne linije memorije, i preuzima 16 bajta svakog ciklusa. Svaki bajt u ovom kešu se čuva u deset bita pre nego 8, sa ekstra bitovima koji obeležavaju granice instrikcija (primer predešifrovanja). Keš ima samo ravnopravnu zaštitu pre nego ECC, zato što je zaštita ravnopravnosti manja i svi oštećeni podaci se mogu zameniti novim podacima denešenim iz memorije (koja uvek ima aktuelne kopije instrukcija).
• Instrukcioni TLB čuva kopije ulaza tabela stranice (PTEs). Svaki ciklus donošenja instrukcija ima svoju virtuelnu adresu koja se prevodi kroz TLB u fizičku adresu. Svaki ulaz je sa ili 4 ili 8 bajta u memoriji. Pošto K8 ima promenljivu veličinu strane, svaki od TLB-ova se deli na dva dela, jedan čuva PTEs koje mapira 4KV, a druga čuva PTEs koja mapira strane od 4MV ili 2MV. Deljenje omogućava potpuno jednostavnu asocijativnost svakog ravnopravnog kola u svakom delu. Operativni sistem mapira različite delove virtuelne adrese sa različitom veličinom PTEs.
• TLB za podatke ima dve kopije koje čuvaju identične ulaze. Dve kopije dozvoljavaju dva pristupa podacima po ciklusu radi prevođenja vituelne adrese u fizičku. Kao instrukcioni TLB, ovaj TLB za podatke je takođe podeljen na dva tipa ulaza.
• Keš za podatke čuva kopije 64 bajtnih linija memorije. On je podeljen na 8 delova (od kojih svaki čuva 8KV) i može doneti podatke od 8 bajta svakog ciklusa, sve dok su ti podaci u različitim delovima. Postoje dve kopije taga, zato što je svaka linija od 64 bajta raširena među 8 delova. Svaka kopija taga radi sa jednim od dva pristupa po ciklusu.

K8 takođe ima keševe sa više nivoa. Postoji drugi nivo instrukcija i podataka TLB, koje skladište samo PTEs koji mapiraju 4KV. Oba keša za instrukcije i podatake, i razni TLB, mogu da se popune iz velikog L2 keša. Ovaj keš je ekskluzivan za L1 instrukciju i za keš podatke, što znači da bilo koja 8 bajtna linija može biti samo u jednom od L1 instrukcijskog keša, L1 keša podataka ili L2 keša. To je, međutim moguće za liniju u keš podacima da imaju PTE, koji je takođe u jednom od TLB – operativni sistem je odgovoran za čuvanje TLB-a koherentnim izbacivanjem njegovih delova kada se obnovi tabela stranice u memoriji.

K8 takođe kešira informacije koje se nikada ne čuvaju u memoriji - predviđanje informacija. Ovi keševi nisu prikazani u gornjem dijagramu. Kao što je uobičajeno za ovu klasu procesora, K8 ima prilično složeno predviđanje grananja, sa tabelama koje pomažu u predviđanju da li su te grane preuzete i druge tabele koja predviđaju ciljeve grana i skokove. Neke od ovih informacija su povezane sa instrukcijama, instrukcijskim kešom nivoa-1 i jedinstvenim sekundarnim kešom.

K8 koristi zanimljiv trik za skladištenje predviđenih informacija sa uputstvima u sekundarnoj keš memoriji. Linije u sekundarnoj keš memoriji su zaštićene od slučajnih korupcija podataka (npr. štrajk alfa čestica) od strane ECC ili ravnopravnosti, u zavisnosti od toga da li su te linije izbačene iz podataka ili iz keševa osnovnih instrukcija. Pošto ravnopravnost koda uzima manje bitova nego ECC kod, linije iz instrukcijskog keša imaju nekoliko rezervnih bitova. Ovi bitovi se koriste za keširanje previđenog grananja informacija u vezi sa ovim instrukcijama. Čist rezultat je to da predviđač grananja ima veću efektivnu tabelu istorije, pa ima i bolju preciznost.

Više hijerarhije

Drugi procesori imaju i druge vrste predskazivača (npr čuvanje-u-opterećenom bajpas predskazivaču u DEC Alpha 21264) i razne specijalizovane predskazivače koji će verovatno napredovati u budućim procesorima.

Ovi predikatori su keš memorije u kojima se skladište informacije koje se skupe za izračunavanje. Neka terminologija koja se koristi prilikom diskusije o predikatorima je isto kao za keševe (jedan govori o pogotku u grani predikatora), ali se u osnovi ne misli da su predikatori deo keš hijerarhije.

K8 čuva instrukcije i podatke u keševima koherentnim u hardveru, što znači da će čuvanje u instrukciji, koja pažljivo prati sačuvanu instrukciju, menjati tu sledbenu instrukciju. Drugi procesori, poput onih iz Alpha i MIPS porodice, oslanjali su se na softver, da bi instrukcije keša ostale koherntne. Čuvanje ne garantuje da će se pojaviti u instrukcijskom toku sve dok program poziva operativni sistem da obezbedi koherentnost objekta.

Implementacija

Keš čitanja su najčešće procesorske operacije koje traju više od jednog ciklusa. Program za vreme izvršenja ima tendenciju da bude veoma osetljiv na latenciju keš pogotka novoa-1. Mnogo napora pri dizajnu, a često i energija i silikon, su potrebni da bi keš bio što je mogugće brži.

Najjednostavniji keš je praktično indeksiran direktno-mapiran keš. Virtuelna adresa se izračunava pomoću sabirača, relelevantni delovi ekstrahovane adrese se koriste za indeksiranje SRAM, koji vraća učitane podatke. Podatak je bajtovski poravnat u bajt pomeraču, a odatle je premošćen sa sledećom operacijom. Nema potrebe za bilo kakvu tag proveru u unutrašnjoj petlji - u stvari, tagovi se ne moraju ni čitati. Kasnije u pripremi, ali pre nego što se učitana instrukcija povuče, tag za učitane podatke mora da se pročita, i proverava u odnosu na virtuelnu adresu, kako bi se uverili da je keš pogodak. Na promašaj, keš se ažurira sa traženom keš linijom i „dovodna linija“ se restartuje.

Asocijativni keš je komplikovaniji, jer se neki oblici taga moraju pročitati da bi se odredio koji ulazak keša treba izabrati. N-put skupa-asocijativnog keša nivoa-1 obično čita sve N moguće tgagove i N podatke u paraleli, i tada izabira podatke koji su prikladno udruženi sa tagom. Keševi nivoa-2 neki put uštede energiju čitajući prvo tagove, tako da se samo jedan element podataka čita iz podataka SRAM.

Pročitaj deo za asocijativni keš na 2 načina

Dijagram desno je previđen da razjasni način kako se koriste različita polja adresa. Adresni bit 31 je najznačajniji, bit 0 je najmanje značajan. Dijagram prikazuje SRAM, indeksiranje, i višestrukost za 4KV, 2-načina asicijativnog skupa, viruelno indeksiranje i virtuelni tagirani keš sa 64 bajt (V) linije, 32-bitnu širinu čitanja i 32-bitnu virtuelnu adresu.

Pošto je keš 4KV i ima 64 V linje, postoji samo 64 linije u kešu, a mi čitamo dve istovremeno iz Tag SRAM koji ima 32 reda, svaki sa parom od 21 bit taga. Iako svaka funkcija virtuelnih adresnih bitova 31 kroz 6, može da se koristi za indeksiranje taga i podataka SRAM, najjednostavnije je da se koriste najmanje važni bitovi.

Slično, pošto je keš 4 KV i ima 4V čitajućih putanja i čita dva puta za svaki pristup, Data SRAM je sa 512 reda sa po 8 bajtova širine.

Moderniji keš može da bude 16 KV, 4-puta asocijativni skup, virtualno indeksiran, virtualno nagovešten, i fizički tagovan, sa 32 V linije, 32 bitne širine čitanja i sa 36 bitne fizičke adrese. Vraćanje puta čitanja za takav keš izgleda vrlo slično gornjem putu. Umesto taga, čita se vhints, i usmerava se protiv podskupa virtualne adrese. Kasnije u dovodnoj liniji, virtualna adresa se prevodi u fizičku adresu pomoću TLB, i čita se fizički tag (samo jedan, kako vhint snabdeva koji put keša je za čitanje). Konačno fizička adresa se poredi u fizičkom tagu da se utvrdi da li je došlo do pogodka.

Neki SPARC dizajni poboljšali su brzinu svojih L1 keševa za neka vrata kašnjenja rušenjem virtuelnih adresa sabirača u SRAM dekoderima. Pogledajte Ukupni adresirani dekoder.

Istorija

Rana istorija keš tehnologije je usko povezana sa pronalaskom i korišćenjem virtuelne memorije. Zbog oskudice i cene polu-provodničkih memorija, rani glavni okviri računara 1960. godine koristili su složenu hijerarhiju fizičke memorije, mapirane na ravnu viruelnu memoriju, koju koriste programi. Tehnologija meomorije obuhvata polu-provodnike, magnetna jezgra, doboš i disk. Programi vide i koriste virtuelnu memoriju i biće ravni i keširanje će se koristiti za donošenje podataka i instrukcija u najbržoj memoriji ispred procesorskog pristupa. Obimne studije su urađene di bi se opimizovala veličina diska. Opimalna veličina zavisi od korišćenja programskog jezika, Najmanje keša je trebalo za Algol dok su Fortran i Kobol koristili najviše keša.

U ranim danima tehnilogije mikroračunara, pristup memoriji je bio malo sporiji u odnosu na pristup registrima. Ali od 1980. godine razlike u perfomansama između procesora i memorije su rasle. Mikroprocesori su napredovali mnogo brže nego memorija, pogotovo u frekvenci rada, pa su tako memorijske performanse postale usko grlo. Iako je tehnički moguće da imamo sve glavne memorije brze kao procesor, uzet je više ekonomski održiv put: korišćenje dosta memorija male brzine, ali i uvođenje i malo brže keš memorije da bi se smanjio jaz izmeću perfomansi. Ovo je za red veličine dalo veće kapacitete - za istu cenu - sa samo malo lošijim zajedničkim perfomansama.

Prva TLB implementacija

Prvo dokumentovano korišćenje TLB-a bili su na GE 645 i IBM 360/67,; oba su koristili asocijativnu memoriju kao TLB.

Prvi keš podataka

Prva dokumentovana upotreba keša za podatke je bila na IBM System/360 Model 85.

U x86 mikroprocesoru

Kada je mikroprocesor x86 dostigao radni takt od 20 MHz i preko u 386, mala količina brze keš memorije je počela da se pojavljuje u sistemima radi povećanja perfomansi. Ovo je bilo zato što se DRAM koristio za glavnu memoriju a imao je značajno kašnjenje, do 120 ns, kao i ciklus osvežavanja. Keš je bio izgrađen od skupljeg, ali znatno bržeg, SRAM, koji je tada imao kašnjenje oko 10 ns. Rani keševi su bili spoljni u procesoru i obično su se nalazili na matičnoj ploči u vidu osam ili devet DIP uređaja, plasiranih u podnožju (sockets) da omoguće kešu da bude dodatna oprema ili karakteristika nadogradnje.

Neke verzije Intel 386 procesora su mogle da podrže od 16 do 64KB spoljnjeg keša.

Sa 486 procesorom, keš od 8KB je direktno integrisan u procesor. Ovaj keš je nazvan nivo-1 ili L1 keš, da bi se razlikovao od sporijeg na matičnoj ploči ili nivo-2 (L2) keš. Ovi keševi na matičnoj ploči su bili mnogo veći, najčešće 256 KB. Popularnost keševa na matičnoj ploči se nastavila kroz eru Pentium MMX, ali je napravljen od zastarelog uvedenog SDRAM i rasla je nejednakost između magistrale takta i takta na procesoru, koji je uzrokovao da keševi na matičnoj ploči budu samo malo brži od glavne memorije.

Sledeći razvoj u keš implementaciji u x86 mikroprocesorima počinje sa Pentium Pro, koji je doneo sekundarane keš memorije na istom paketu kao mikroprocesor, koji radi na istoj frekveniji kao mikroprocesor. Keševi na matičnoj ploči uživaju u produženoj popularnosti zahvaljujući AMD K6-2 i AMD K6-III procesorima, koji su još uvek koristili drevni Soket 7, koji je ranije koristio Intel sa keševima na matičnoj ploči. K6-III je je uključivao 256 KB na čipu keša L2 i iskoristio je prednost keša na matičnoj ploči kao nivo-3, nazvan L3 (proizvodile su se matične ploče sa keš memorijom do 2 MB). Kada je Soket 7 zastareo, keš memorije na matičnim pločama su nestale sa x86 sistema.

Keš memorije od tri nivoa su se ponovo počeli koristiti uveđenjem procesora sa više jezgara, gde je L3 keš bio dodat na procesorski čip. Postalo je uobičajeno da ukupna veličina keša bude postepeno veća u novijim generacijama procesora, a od skora (od 2011. godine) nije neuobičajeno naći na nivou-3 nekoliko desetina megabajta. Ovaj trend izgleda da će biti nastavljen i u budućnosti.

Intel je predstavio nivo-4 keš na-čipu u Haswell mikroarhitekturi. Crystal Well Haswell procesori, opremeljeni sa GT3e varijantom Intel's integrisane Iris Pro grafike, efikasno imaju 128MB ugrađen DRAM (eDRAM) na istom čipu. Ovaj L4 keš je dinamički deljen između na-čipu GPU i CPU, i služi kao žrtveni keš za L3 keš procesora.

Trenutna istraživanja

Raniji dizajni keša su se u potpunosti fokusirali na direktini trošak za keš memoriju i RAM i prosečne brzine izvršavanja. Noviji keš dizajni takođe razmatraju energetsku efikasnost, toleranciju grešaka i druge ciljeve.

Postoji nekolika alata na raspolaganju za računarske arhitekture da pomognu u istraživanju kompromisa između: vremena ciklusa keša, energije i prostora. Ovi alati uključuju i otvoreni-izvorni CACTI keš simulator i otvoreni-izvorni SimpleScalar simulator instrukcijskog skupa.

Multi-portovan keš (više-portovan keš)

Multi-portovan keš je keš koji može izvršiti više od jednog zahteva u isto vreme. Prilikom pristupa tradicionalnom kešu obično se koristi jedna memorijska adresa, dok je kod multi-portovanog keša moguće tražiti N adresa instovremeno – gde je N broj portova koji su povezani preko procesora i keša. Prednost ovoga je da dovodna linija procesora može pristupiti memoriji iz različitih faza u svojoj dovodnoj liniji. Još jedna prednost je u tome što omogućava koncept super skalarnih procesora kroz različite nivoe keša.

Vidi još

• Algoritmi keširanja
• Keš memorija

Literatura

• Kilburn, T.; Payne, R. B.; Howarth, D. J. (1961). „The Atlas Supervisor”. Computers - Key to Total Systems Control. Conferences Proceedings. 20 Proceedings of the Eastern Joint Computer Conference Washington, D.C. Macmillan. str. 279—294. 
• Sumner, F. H.; Haley, G.; Chenh, E. C. Y. (1962). „The Central Control Unit of the 'Atlas' Computer”. Information Processing 1962. IFIP Congress Proceedings. Proceedings of IFIP Congress 62. Spartan. 
• Cragon, Harvey G. (1996). Memory Systems and Pipelined Processors. Jones & Bartlett Learning. str. 209. ISBN 978-0-86720-474-2. 
• Patterson, David A.; Hennessy, John L. (2008). Computer Organization and Design, Fourth Edition: The Hardware/Software Interface. Morgan Kaufmann. str. 484. ISBN 978-0-08-092281-2. 
• Hennessy, John L.; Patterson, David A. (2012). Computer Architecture: A Quantitative Approach. Elsevier. str. 120. ISBN 978-0-12-383872-8.