Kes memorija

Maturski, seminarski i diplomski radovi iz informatike.

Osim RAM memorije, za privremeno smeštanje podataka na računarima, postoji i tzv. keš memorija (engl. Cache memory). Ovo je memorija skrivena za programera, odnosno programer ne može da utiče na nju. To je memorija koja je realizovana hardverski i obično se nalazi na samom procesoru. Razlog za postojanje keš memorije je taj, što su normalni DRAM čipovi suviše spori u odnosu na frekvenciju takta procesora, koji zato mora da čeka za dodatne cikluse takta da bi dobio podatke iz DRAM-a. Zato se između DRAM-a i CPU-a implementira brza statička memorija (SRAM), poznata kao keš. U keš memoriji nalaze se oni sadržaji iz radne memorije kojima se najčešće pristupa. Pri čitanju podataka prvo se proverava da li se podaci nalaze u kešu, a potom, ukoliko ih tu nema pristupa se radnoj memoriji. Pošto je vreme pristupa keš memoriji veoma brzo (za red veličine manje od vremena prisrupa radnoj memoriji), tako od keš memorije u najvećoj meri zavise performanse procesora, pa se sa povećanjem keš memorije značajno povećavaju performanse i samih procesora, kao i računara u celini.
Možda bi najbolji primer za opis funkcionisanja keš memorije bio poređenje sa recimo, bibliotekom. Recimo da ste u biblioteci i da radite na nekom naučnom radu. Da bi ste uradili ovakav rad potreban vam je velik broj knjiga koje će vam pomoći u dolaženju do neophodnih informacija za vaš rad. Police sa knjigama bi u ovom slučaju bile radna memorija. U njoj se nalaze neophodne informacije odnosno na policama su knjige koje su vam potrebne. Međutim osim onih knjiga koje su vam neophodne tu je i velik broj drugih knjiga. Vi cete odabrati par knjiga koje su vam se ucinile neophodnim i stavicete ih na vas sto kako bi vam u svakom trenutku bile dostupne i pri ruci. Upravo taj sto i tih par knijga na njemu simbolički predstavljaju keš memoriju racunara. Moglo bi se reći da i procesor radi na sličnom principu. On takođe dovlači informacije koje su mu u datom trenutku neophodne iz RAM memorije i smešta ih u keš memoriju. Podsetimo se da se u RAM memoriji nalaze i drugi podaci koji nisu baš procesoru neophodni za određen zadatak. Na ovaj način podaci koji su mu potrebni, oni su mu i dostupni „pri ruci“ u kratkom vremenskom roku, bas kao i nase knjige na stolu. Ali šta kada vam je potrebna još neka knjiga sa police? Da bi ste na sto stavili još knjiga moraćete neke i da vratite na policu. Verovatno ćete vratiti one za koje mislite da vam više nisu neophodne. Ili možda one koje ste prve pogledali. Bas tako radi i procesor. Naime kada se keš memorija napuni (podsetimo se da je keš memorija malog kapaciteta u odnosu na RAM) procesor mora neke od informacija da vrati u RAM. Postavlja se pitanje koje informacije vratiti? Zato postoji određen broj algoritama koji služe upravo da kažu procesoru koje informacije da vrati u RAM. Procesor po određenom algoritmu vraća informacije nazad i na taj način oslobađa prostor za nove podatke. Baš kao što biste i vratili knjige na policu i potom uzeli nove. Postoji više ovakvih algoritama, ali o njihovim osobinama i načinima na koji rade će biti više reči kasnije.

PRINCIP KEŠ MEMORIJE

Princip keš memorije zasniva se na kombinovanju prednosti brzih i skupih SRAM čipova sa jeftinim ali i sporijim DRAM čipovima da bi se dobio najefektivniji memoriski sistem. Između CPU-a i RAM-a se postavlja brzi keš SRAM čip, kome se privremeno pamte često korišćeni podaci i veoma brzo se mogu staviti na raspolaganje procesoru. Jedinica keša sastoji se iz keš kontrolera i keš SRAM-a, koji mobu biti uključeni na istom čipu kao i CPU (on chip cache), ili postoje kao zasebne komponente. Postoje i kombinacije kod kojih je keš kontroler uključen na CPU čipu, a stvarna keš memorija je formirana od eksternih SRAM čipova. Kapacitet keš memorije znatno je manji od kapaciteta DRAM-a i iznosi obično 128 KB do 512 KB. Pošto se većina sukcesivnih pristupa memoriji odnosi na manje adresne oblasti, podaci kojima se najčešće pristupa čuvaju se u maloj brzoj memoriji: kešu. Na taj način je omogućeno značajno redukovanje vremena pristupa, koje, zajedno sa mnogim pristupima memoriji u okviru kratkog vremenskog intervala, omogućava veliko povećanje brzine. Većina podataka se retko adresira u nizu. Zato je moguće veliko deo podataka smestiti u sporiji RAM, bez velikog redukovanja brzine obrade. Princip keša koji koristi malu SRAM keš memoriju i veću, ali sporiju RAM memoriju kombinuje prednosti obe vrste memorije, bez drastičnog povećanja cene.
Kada čita podatke, CPU traži odgovarajuću adresu u memoriji. Međutim, između procesora i RAM adrese se nalazi keš kontroler. On utvrđuje da li se zahtevani podatak nalazi u SRAM kešu. Ako se nalazi, nastupa tzv. pogodak keša (cache hit). Sa druge strane, ako je podatak raspoloživ samo u RAM-u, došlo je do promašaja keša (cache miss). U prvom slučaju keš kontroler čite podatke iz brze keš memorije i prenosi ih do CPU-a. Ovo se, obično, izvodi bez čekanja, tj. sa maksimalnom brzinom magistrale. Pristup radi čitanja presreće keš i RAM ne zna ništa o tome.

BRZ I SKUP: SRAM

Verovatno je pitanje koje se odmah nameće: zašto se baš SRAM memorija koristi za izradu keša? Odgovor leži u činjenici da je SRAM memorija daleko brža od DRAM memorije. Zbog čega je to tako? U SRAM-u se informacija ne smešta u obliku punjenja u kondezatoru kao što je to slučaj sa DRAM memorijom, već sa održava kao stanje flip-flop kola. Takvo flip-flop kolo ima dva stabilna stanja koja mogu biti prebacivana jakim eksternim signalom. Na donjoj slici je prikazana struktura memoriske ćelije u SRAM-u.
Odmah se može videti da je SRAM struktura ćelije daleko komplikovanija od DRAM memorijske ćelije, koja je ilustrovana desno na gornjoj slici. Dok se DRAM ćelija sastoji samo od pristupnog tranzistora Tra i kondenzatora koji sadrži punjenja u skladu sa smeštenim podatkom, u tipičnoj SRAM ćeliji prisutna su dva pristupna tranzistora Tra i flip-flop sa dva memorijska tranzistora Tra isto kao što su prisutna dva elementa učitavanja. Stoga je integrisanost SRAM memorijske ćelije moguća samo uz mnogo tehnickog napora. SRAM čipovi su, stoga, mnogo skuplji i mogu smestiti manje podataka od DRAM čipova. Zbog toga, SRAM čipovi se prvenstveno koriste za male, brze keš memorije, a DRAM čipovi za veće i relativno sporije glavne memorije (RAM). Današnji SRAM čipovi kada se koriste, na primer, u eksternom L2 kešu na Socket 7 pločama, imaju vreme pristupa od 6 ns, u poređenju sa čipovima sa vremenom pristupa od 10:15 ns, koji se nalaze u starijim sistemima.

VREME PRISTUPA I KAPACITET KEŠ MEMORIJE

Keš memoriju karakteriše određen broj osobina kao što su: vreme pristupa, kapacitet, dimenzija bloka, tehnika preslikavanja, algoritam zamene, kao i način ažuriranja radne memorije. Svaka od ovih osobina podjednako je važna za keš memoriju, mada vreme pristupa i kapacitet najviše utiču na brzinu kompletnog sistema.
Vreme pristupa keš memoriji predstavlja vreme koje protekne od izdavanja zahteva od strane procesora za nekim podatkom koji se nalazi u keš memoriji, pa do dobijanja traženog podatka. Upravo ovo vreme predstavlja glavni razlog postojanja keš memorije i najveću prednost ove memorije u odnosu na RAM. Naime, pošto se keš memorija, kao što je i poznato, nalazi na samom procesoru to je i vreme pristupa njoj veoma kratko. Obično keš memorija radi na istom taktu kao i procesor, što znači da procesor u jednom taktu može pokupiti podatke iz keš memorije. Ako se uzme u obzir da je brzina RAM memorije oko 60 nanosekundi, a mikroprocesori mogu imati takt u trajanju od 2 nanosekunde jasno je koliko vremena se gubi na čekanju. Upravo ovde leži velika prednost keša a to je njegova implementacija na samom procesoru, što i omogućava rad na istom taktu procesora i keša, kao i prenos podataka procesorskom brzinom.
Kapacitet je takođe jedna od bitnih stavki pri projektovanju i implementaciji keš memorije. Za razliku od RAM-a gde je poželjan veći kapacitet, kod keš memorije situacija je nešto drugačija. Naime nije moguće koristiti velike kapacitete, pre svega zbog cene same memorije pošto je ona, kada je u pitanju keš memorija, veoma visoka što bi značajno uticalo na konačnu cenu procesora. Takođe veća količina keš memorije zahteva i veće napajanje, a samim tim i proizvodi veću toplotu što opet utiče na zagrevanje i ostalih bliskih komponenti. Međutim jedan drugi, važniji razlog je taj što bi se velikim povećanjem keš memorije povećalo i vreme koje je potrebno procesoru da pronađe odgovarajuće podatke u samom kešu. Zapravo oko 90% podataka sa kojima procesor svo vreme radi nalaze se u kešu. Takođe veličine keša obično se kreću od 8 do 128 KB, dok je veličina RAM-a reda MB (danas čak i GB). Ipak keševi su projektovani tako da imaju preko 90% pogodaka. Postavlja se pitanje kako je ovo moguće? Odgovor leži u činjenici da svi programi koji su veličine par desetina ili stotina megabajta, veći deo vremena ponavljaju određeni isti deo svog koda nakon što se učitaju u RAM memoriju. Baš taj deo koda koji se često ponavlja i čija je veličina veoma mala u poređenju sa čitavim programom, nalazi se u kešu. Na taj način se obezbeđuje brzo reagovanje na zahtev procesora odnosno procesor radi sa podacima iz keša. Na primer, kada otvorimo Word on će se najpre učitati u RAM memoriju, nakon čega ćemo otvoriti dokument i početi sa unosom nekog teksta. Sve dalje akcije koje izvodimo su ustvari jedna petlja koja se ponavlja: unos teksta, brisanje teksta, skrolovanje, zatvaranje i otvaranje novih dokumenata, kopiranje itd. Keš kontroler će u keš memoriju smestiti one linije koda nekog programa koje se najčešće ponavljaju. Zato je važno da veličina keša bude optimalna jer ukoliko je prevelika, možda bi se povećao broj pogodaka keša, ali bi se i u keš istovremeno učitala velika količina podataka što bi povećalo vreme koje je potrebno procesoru da pronađe neophodne podatke. Da bi se prevazišao ovaj problem, uvode se keševi drugog nivoa odnosno keševi koji su keširani od strane keševa prvog nivoa. Zapravo podaci koji procesoru nisu trenutno potrebni se prebacuju sada u keš drugog nivoa a tek potom u RAM memoriju. Pošto su keševi drugog nivoa takođe brži od RAM-a, dobija se na brzini uz oslobađanje od nepotrebnih podataka iz L1 keša.

ALGORITMI ZAMENE

Keš kontroler koristi različite algoritme pomoću kojih određuje koji će se podaci iz keša prebaciti u RAM, kako bi se dobio prostor za dovlačenje novih blokova podataka. Najzastupljeniji je LRU algoritam ili Last Recently Used. Ovaj algoritam radi na principu izbacivanja onih blokova podataka kojima se najmanje pristupalo. Zapravo potrebno je pri svakom pristupu kešu, setovati odgovarajuće LRU bite kako bi se odredilo koji su podaci najaktivniji. Ovi biti se ažuriraju nakon svakog pristupa kešu a brišu nakon svakog resetovanja odnosno ispiranja keša. Kontroler na osnovu bita utvrđuje kojim se blokovima već duže vremena nije pristupalo i označava ih kao zamenjive. Nakon toga pri sledećem pristupu, podaci će se prebaciti u RAM, a na njihovo mesto će se ubaciti novi blokovi podataka. Mana ovog algoritma je što mora postojati logika zamene što ga čini sporijim kao i težim za implementiranje od recimo Random algoritma.
Algoritam random se zasniva na slučajnom odabiru blokova podataka koji će se izbaciti iz keša. Ne postoji nikakva logika ni proračun već kontroler izbacuje neki