Architektúra vyrovnávacej pamäte.
V závislosti od spôsobu určovania vzájomnej korešpondencie medzi riadkom vyrovnávacej pamäte a oblasťou hlavnej pamäte sa rozlišujú tri architektúry vyrovnávacej pamäte: vyrovnávacia pamäť s priamym mapovaním, plne asociatívna vyrovnávacia pamäť, čiastočne alebo asociatívna vyrovnávacia pamäť.
Priamo mapovaná vyrovnávacia pamäť.
V cache s priamym mapovaním adresa pamäte, ku ktorej sa pristupuje, jednoznačne určuje riadok cache, v ktorom sa môže nachádzať požadovaný blok. Princíp fungovania takejto cache si vysvetlíme na príklade nesektorovej cache 256 KB s veľkosťou riadku 32 bajtov a cache kapacitou hlavnej pamäte 64 MB - typická cache základnej dosky Pentium. Štruktúra vyrovnávacej pamäte v takomto systéme je znázornená na obr. 1. Hlavná pamäť vo vyrovnávacej pamäti je podmienene rozdelená na stránky (v tomto prípade každá 256 KB), ktorých veľkosť sa zhoduje s veľkosťou vyrovnávacej pamäte (256 KB). Pamäť vyrovnávacej pamäte (a podmienečne stránky hlavnej pamäte) je rozdelená na riadky (256 KB / 32 bajtov - 8 K riadkov). Architektúra priameho mapovania znamená, že každý riadok vyrovnávacej pamäte môže mapovať iba riadok, ktorý mu zodpovedá, z ktorejkoľvek stránky pamäte vyrovnávacej pamäte. Keďže množstvo hlavnej pamäte je oveľa väčšie ako veľkosť vyrovnávacej pamäte, každý riadok vyrovnávacej pamäte môže byť nárokovaný mnohými pamäťovými blokmi s rovnakou časťou adresy nižšej úrovne, ktorá sa nazýva offset v rámci stránky (0 - sada, 1-set, 2-set ... N-set 32-bajtových blokov ). Jeden riadok môže obsahovať kópiu iba jedného z týchto blokov v danom čase. Číslo riadku je adresa riadku vo vyrovnávacej pamäti a tag nesie informáciu o tom, ktorý blok tento riadok zaberá (tag je vysoká časť adresy nastavenej procesorom pri prístupe do pamäte alebo inými slovami číslo stránky ). Pamäť značky musí mať počet buniek rovný počtu riadkov vyrovnávacej pamäte a jej šírka musí byť dostatočná na umiestnenie najvýznamnejších bitov adresy vyrovnávacej pamäte, ktoré nespadajú do adresovej zbernice vyrovnávacej pamäte. Okrem adresovej časti tagu je každý riadok vyrovnávacej pamäte spojený s bitmi znakov platnosti a modifikácie údajov. Na začiatku každého prístupu do RAM radič vyrovnávacej pamäte najprv načíta bunku pamäte tagu s adresou riadku určenou bitmi A17-A5, porovná obsah tohto riadku pamäte tagu s bitmi A25-A18 pamäte. adresu nastavenú procesorom a analyzuje znak reality.
Ryža. 1. Priamo mapovaná vyrovnávacia pamäť.
Táto analýza sa vykonáva v špeciálnej sledovacej slučke, niekedy nazývanej slučka dotazov. Ak analýza odhalí, že požadovaný blok nie je vo vyrovnávacej pamäti, vygeneruje sa (alebo bude pokračovať) cyklus prístupu do hlavnej pamäte (cache miss). Ak zasiahne, požiadavku obslúži vyrovnávacia pamäť. V prípade zmeškania, po prečítaní informácií z hlavnej pamäte prijímačom, sa nové údaje umiestnia do vyrovnávacej pamäte (ak je čistá) , a najvýznamnejšie bity adresy sa umiestnia do jeho tagu a nastaví sa platnosť údajov. Bez ohľadu na množstvo údajov požadovaných do vyrovnávacej pamäte z hlavnej pamäte sa prepíše celý riadok (keďže indikátor platnosti sa vzťahuje na všetky jeho bajty). Ak radič vyrovnávacej pamäte implementuje čítanie dopredu, potom sa v nasledujúcich cykloch voľnej zbernice aktualizuje aj ďalší riadok (ak bol čistý) ). Čítanie „v zálohe“ umožňuje v prípade potreby vykonať dávkový cyklus čítania z vyrovnávacej pamäte cez hranicu linky. Táto vyrovnávacia pamäť má najjednoduchšiu hardvérovú implementáciu a používa sa v sekundárnej vyrovnávacej pamäti väčšiny základných dosiek. Má to však vážnu nevýhodu. Ak počas vykonávania programu procesor striedavo pristupuje k rovnakej adrese riadku, ale s rôznymi alebo cyklicky sa meniacimi číslami tagov, potom sa budú neustále zaznamenávať chýbajúce pamäte cache a pamäť cache namiesto zrýchlenia spomalí výmenu s pamäťou. Prepínanie stránok v multitaskingových operačných systémoch (OS) tiež znižuje počet prístupov do vyrovnávacej pamäte, čo ovplyvňuje výkon systému. Zväčšenie veľkosti vyrovnávacej pamäte pri zachovaní architektúry priameho mapovania nebude mať veľmi významný vplyv, pretože rôzne úlohy si budú vyžadovať rovnaké riadky vyrovnávacej pamäte. Bez zväčšenia veľkosti vyrovnávacej pamäte môžete zvýšiť efektivitu ukladania do vyrovnávacej pamäte zmenou jej štruktúry, o ktorej sa bude diskutovať nižšie.
Niekedy popis cache priamej mapy obsahuje termín set, ktorý sa používa namiesto termínu riadok v sektorovej cache priamej mapy a sektor sa potom nazýva riadok. So množinou (rovnako ako s riadkom vyrovnávacej pamäte bez sektorov) je spojená informácia o značke, ktorá sa vzťahuje na všetky prvky množiny (riadky alebo sektory). Okrem toho má každý prvok množiny (riadok alebo sektor) svoj vlastný bit platnosti (obr. 2).
Ryža. 2. Sectored Direct Mapping Cache
Set-asociatívna (čiastočne asociatívna) vyrovnávacia pamäť.
Architektúra vyrovnávacej pamäte asociatívnej množiny (obrázok 3) umožňuje každému bloku pamäte cache nárokovať si jeden z niekoľkých riadkov vyrovnávacej pamäte kombinovaných do sady. V tejto architektúre je akoby niekoľko paralelných a koordinovaných priamych mapovacích kanálov, kde sa musí radič vyrovnávacej pamäte rozhodnúť, do ktorého z riadkov sady umiestni ďalší dátový blok. Napríklad v najjednoduchšom prípade sa každý pamäťový blok môže zmestiť do jednej zo štyroch nastavených riadkov (štvorcestná vyrovnávacia pamäť asociatívna s množinami). Nastavené číslo, v ktorom sa môže požadovaný dátový blok zobraziť, je jednoznačne určené strednou časťou adresy (ako číslo riadku v cache priameho mapovania). Riadok množiny predstavujúci požadovaný blok je určený porovnaním značiek (ako v asociatívnej vyrovnávacej pamäti) vykonávaným paralelne pre všetky riadky pamäte značiek danej sady (kanály vyrovnávacej pamäte). Okrem toho musí byť ku každému setu priradený znak, ktorý definuje riadok setu, ktorý sa má nahradiť novým dátovým blokom v prípade vynechania vyrovnávacej pamäte (na obrázku ukazuje šípka v jej smere).
Ryža. 3. Štvorkanálová sada-asociačná vyrovnávacia pamäť
Kandidátom na nahradenie je zvyčajne riadok, ku ktorému sa nepristupovalo najdlhšie (LRU – algoritmus najmenej nedávno použitého). Pri relatívne veľkom počte kanálov (riadkov v sade) sa uchýli k určitému zjednodušeniu - algoritmus Pseudo-LRU pre štyri riadky umožňuje robiť rozhodnutia iba pomocou 3 bitov.
Je tiež možné použiť náhradný algoritmus FIFO (prvý dovnútra, prvý von) alebo dokonca náhodné nahradenie, čo je jednoduchšie, ale menej efektívne. Set-asociatívna architektúra je široko používaná pre primárnu vyrovnávaciu pamäť moderných procesorov.
Asociačná vyrovnávacia pamäť.
Na rozdiel od predchádzajúcich má plne asociatívna cache ľubovoľný riadok dokáže namapovať akýkoľvek pamäťový blok, čo výrazne zvyšuje efektivitu využívania obmedzeného priestoru vyrovnávacej pamäte. V tomto prípade všetky bity
Ryža. 4. Plne asociatívna vyrovnávacia pamäť.
Adresy bloku vo vyrovnávacej pamäti mínus bity, ktoré určujú polohu (offset) údajov v riadku, sú uložené v pamäti tagov. V takejto architektúre (obr. 4) sa na zistenie prítomnosti požadovaných dát vo vyrovnávacej pamäti použije porovnanie s vysokou časťou adresy tagu všetkých riadkov pamäte tagu, a nie jedného alebo viacerých, ako pri priamom mapovaní resp. množinová asociatívna architektúra. Sekvenčné počítanie pamäťových buniek tagov je eliminované. (to zaberie príliš veľa času), takže zostáva paralelné porovnanie značiek všetkých buniek, a to je zložitá hardvérová úloha, ktorú možno prijateľne vyriešiť len pre malé objemy primárnej vyrovnávacej pamäte (procesor M2 Cyrix).
Vývojári vyrovnávacej pamäte čelili problému, že potenciálne akákoľvek bunka v obrovskej hlavnej pamäti môže skončiť vo vyrovnávacej pamäti. Ak je pracovná množina údajov používaných programom dostatočne veľká, znamená to, že veľa častí hlavnej pamäte bude súťažiť o každé umiestnenie vyrovnávacej pamäte. Ako už bolo uvedené, nie je nezvyčajné, že pomer medzi vyrovnávacou pamäťou a hlavnou pamäťou je 1 až 1 000.
3.3.1 Asociativita
Bolo by možné implementovať vyrovnávaciu pamäť, v ktorej by každý riadok vyrovnávacej pamäte mohol uchovávať kópiu ľubovoľného pamäťového miesta. To sa nazýva plne asociatívna vyrovnávacia pamäť (plne asociatívna vyrovnávacia pamäť). Na prístup k riadku vyrovnávacej pamäte by jadro procesora muselo porovnať značky každého riadku vyrovnávacej pamäte s označením požadovanej adresy. Značka bude musieť uložiť celú adresu, ktorá nebude mať v riadku vyrovnávacej pamäte posun (to znamená, že hodnota S zobrazená na obrázku v časti 3.2 bude nula).
Existujú cache, ktoré sú implementované týmto spôsobom, ale pohľad na veľkosť L2 cache, ktoré sa v súčasnosti používajú, ukazuje, že je to nepraktické. Všimnite si, že 4 MB vyrovnávacia pamäť so 64 B riadkami vyrovnávacej pamäte by mala 65 536 záznamov. Aby sa dosiahol primeraný výkon, logika vyrovnávacej pamäte musí byť schopná v priebehu niekoľkých cyklov vybrať spomedzi všetkých týchto záznamov ten, ktorý sa zhoduje s daným tagom. Náklady na implementáciu takejto schémy by boli obrovské.
Obrázok 3.5: Schematické znázornenie plne asociatívnej vyrovnávacej pamäte
Každý riadok vyrovnávacej pamäte vyžaduje, aby komparátor vykonal veľké porovnanie značiek (všimnite si, že S je nula). Písmeno vedľa každého spojenia označuje šírku spojenia v bitoch. Ak nie je uvedené nič, šírka pripojenia je jeden bit. Každý komparátor musí porovnávať dve hodnoty, z ktorých každá má šírku T bitov. Potom by sa na základe výsledku mal načítať a sprístupniť obsah zodpovedajúceho riadku vyrovnávacej pamäte. Ak to chcete urobiť, musíte skombinovať toľko sád dátových liniek O, koľko je segmentov vyrovnávacej pamäte. Počet tranzistorov potrebných na implementáciu jedného komparátora bude veľký, čiastočne preto, že komparátor musí pracovať veľmi rýchlo. Nie je možné použiť iteračný komparátor. Jediný spôsob, ako ušetriť na počte porovnávačov, je znížiť ich počet pomocou iteratívneho porovnávania značiek. Toto nie je vhodné z rovnakého dôvodu, pre ktorý nie sú vhodné iteračné komparátory: bude to trvať príliš dlho.
Plne asociatívna vyrovnávacia pamäť je praktická pre malé veľkosti vyrovnávacej pamäte (napríklad vyrovnávacia pamäť TLB v niektorých procesoroch Intel je plne asociatívna), vyrovnávacia pamäť však musí byť malá – skutočne malá. Hovoríme maximálne o niekoľkých desiatkach rekordov.
L1i, L1d a vyrovnávacie pamäte vyššej úrovne vyžadujú odlišný prístup. Jediné, čo môžete urobiť, je zúžiť vyhľadávanie. V najextrémnejšom prípade je každý tag namapovaný presne na jeden záznam cache. Výpočet je jednoduchý: pre 4MB/64B vyrovnávaciu pamäť so 65 536 položkami môžeme priamo pristupovať ku každému prvku a použiť na to bity adresy 6 až 21 (16 bitov). Spodných 6 bitov je index riadku vyrovnávacej pamäte.
Obrázok 3.6: Schematické znázornenie priamej mapovanej cache
Ako je možné vidieť na obrázku 3.6, implementácia napr priama mapovaná vyrovnávacia pamäť (priamo mapovaná vyrovnávacia pamäť) môže byť rýchle a jednoduché. Vyžaduje si to len jeden komparátor, jeden multiplexor (v tomto diagrame sú dva, pretože značka a údaje sú oddelené, ale nie je to striktná požiadavka na dizajn) a určitá logika na výber obsahu, ktorý obsahuje platné riadky vyrovnávacej pamäte. Porovnávač je zložitý kvôli požiadavkám na rýchlosť, ale teraz je len jeden; v dôsledku toho môžete vynaložiť viac úsilia, aby ste to urobili rýchlejšie. Skutočná zložitosť tohto prístupu spočíva v multiplexeroch. Počet tranzistorov v jednoduchom multiplexore rastie podľa zákona O(log N), kde N je počet riadkov vyrovnávacej pamäte. To je prijateľné, ale môže to viesť k pomalému multiplexeru, v takom prípade je možné rýchlosť zvýšiť investovaním do tranzistorov v multiplexeroch a paralelizáciou niektorých prác na zvýšenie rýchlosti. Celkový počet tranzistorov bude rásť pomaly vzhľadom na veľkosť vyrovnávacej pamäte, čo z neho robí veľmi atraktívne riešenie. Tento prístup má však nevýhodu: funguje iba vtedy, ak sú adresy použité v programe rovnomerne rozdelené vzhľadom na bity použité na priame mapovanie. Ak to tak nie je, a to je zvyčajne tento prípad, niektoré položky vyrovnávacej pamäte sa aktívne používajú, a preto sa opakovane uvoľňujú, zatiaľ čo iné sa takmer vôbec nepoužívajú alebo zostanú prázdne.
Obrázok 3.7: Schematické znázornenie multiasociativity cache
Tento problém je možné vyriešiť použitím vyrovnávacej pamäte s viacnásobná asociativita (nastaviť asociatívne). Multi-asociativity cache kombinuje funkcie plnej asociatívnej cache a priamo mapovanej cache, aby sa do značnej miery vyhlo nevýhodám týchto riešení. Obrázok 3.7 ukazuje návrh vyrovnávacej pamäte s viacerými asociáciami. Pamäť pre tagy a dáta je rozdelená do sád, ktorých výber sa vykonáva podľa adresy. Je to podobné ako pri priamej mapovanej vyrovnávacej pamäti. Ale namiesto použitia samostatného prvku pre každú hodnotu v množine sa rovnaká množina používa na ukladanie malého počtu hodnôt do vyrovnávacej pamäte. Tagy pre všetky prvky množiny sa porovnávajú paralelne, čo je podobné ako pri plne asociatívnej vyrovnávacej pamäti.
Výsledkom je vyrovnávacia pamäť, ktorá je primerane odolná voči chybám v dôsledku zlého alebo zámerného výberu adries s rovnakými nastavenými číslami súčasne a veľkosť vyrovnávacej pamäte nie je obmedzená počtom porovnávačov, ktoré môžu bežať paralelne. Ak sa pamäť cache zvýši (pozri obrázok), zvýši sa iba počet stĺpcov, nie počet riadkov. Počet riadkov sa zvyšuje iba vtedy, ak sa zvyšuje asociativita vyrovnávacej pamäte. Dnešné procesory používajú pre vyrovnávaciu pamäť L2 úrovne asociatívnosti až 16 a vyššie. Vyrovnávacia pamäť L1 je zvyčajne nastavená na úroveň 8.
Tabuľka 3.1: Vplyv veľkosti vyrovnávacej pamäte, asociativita a veľkosť riadku vyrovnávacej pamäte
| Veľkosť rýchla vyrovnávacia pamäť L2 |
Asociativita | |||||||
|---|---|---|---|---|---|---|---|---|
| Priame zobrazenie | 2 | 4 | 8 | |||||
| CL = 32 | CL = 64 | CL = 32 | CL = 64 | CL = 32 | CL = 64 | CL = 32 | CL = 64 | |
| 512 tis | 27 794 595 | 20 422 527 | 25 222 611 | 18 303 581 | 24 096 510 | 17 356 121 | 23 666 929 | 17 029 334 |
| 1 mil | 19 007 315 | 13 903 854 | 16 566 738 | 12 127 174 | 15 537 500 | 11 436 705 | 15 162 895 | 11 233 896 |
| 2 mil | 12 230 962 | 8 801 403 | 9 081 881 | 6 491 011 | 7 878 601 | 5 675 181 | 7 391 389 | 5 382 064 |
| 4M | 7 749 986 | 5 427 836 | 4 736 187 | 3 159 507 | 3 788 122 | 2 418 898 | 3 430 713 | 2 125 103 |
| 8 mil | 4 731 904 | 3 209 693 | 2 690 498 | 1 602 957 | 2 207 655 | 1 228 190 | 2 111 075 | 1 155 847 |
| 16 mil | 2 620 587 | 1 528 592 | 1 958 293 | 1 089 580 | 1 704 878 | 883 530 | 1 671 541 | 862 324 |
Ak máme vyrovnávaciu pamäť 4 MB/64B a 8-cestnú asociativitu, potom budeme mať vo vyrovnávacej pamäti 8192 sád a na adresovanie sád vyrovnávacej pamäte bude potrebných iba 13 bitov značiek. Ak chcete určiť, ktorý záznam (ak existuje) obsahuje adresovateľný riadok vyrovnávacej pamäte v sade vyrovnávacej pamäte, bude potrebné porovnať 8 značiek. Dá sa to urobiť vo veľmi krátkom čase. Ako vidno z praxe, má to zmysel.
Tabuľka 3.1 ukazuje počet vynechaní vyrovnávacej pamäte L2 pre niektorý program (v tomto prípade kompilátor gcc, ktorý vývojári jadra Linuxu považujú za najdôležitejší benchmark) ako veľkosť vyrovnávacej pamäte, veľkosť riadku vyrovnávacej pamäte a hodnotu viacnásobnej asociativity. V časti 7.2 predstavíme nástroj na simuláciu vyrovnávacej pamäte potrebnej na tento test.
Len v prípade, že to ešte nie je zrejmé, vzťah medzi všetkými týmito hodnotami je taký, že veľkosť vyrovnávacej pamäte sa rovná
veľkosť riadku vyrovnávacej pamäte x asociativita x počet sád
Mapovanie adries do vyrovnávacej pamäte sa vypočíta ako
O = log2 veľkosti riadku vyrovnávacej pamäte
S = log2 počtu sád
podľa obrázku v časti 3.2.
Obr.3.8: Veľkosť vyrovnávacej pamäte a úroveň asociatívnosti (CL=32)
Ryža. 3.8 robí údaje v tabuľke zrozumiteľnejšie. Obrázok ukazuje údaje pre riadok vyrovnávacej pamäte pevnej veľkosti rovnajúcej sa 32 bajtom. Ak sa pozriete na čísla pre danú veľkosť vyrovnávacej pamäte, môžete vidieť, že asociativita môže v skutočnosti výrazne znížiť počet chýbajúcich vyrovnávacej pamäte. V prípade vyrovnávacej pamäte s veľkosťou 8 MB sa prechodom z priameho mapovania na dvojcestnú asociatívnu vyrovnávaciu pamäť ušetrí takmer 44 % vyrovnávacej pamäte. V prípade použitia vyrovnávacej pamäte s viacerými asociáciami môže procesor uložiť do vyrovnávacej pamäte väčšiu pracovnú množinu ako v prípade vyrovnávacej pamäte s priamym mapovaním.
V literatúre sa niekedy môžete dočítať, že zavedenie asociativity má rovnaký efekt ako zdvojnásobenie veľkosti vyrovnávacej pamäte. Toto, ako je vidieť v prípade prechodu z vyrovnávacej pamäte s veľkosťou 4 MB na vyrovnávaciu pamäť s veľkosťou 8 MB, platí v niektorých extrémnych prípadoch. Ale to, samozrejme, nie je pravda s následným nárastom asociatívnosti. Ako je zrejmé z údajov, následné zvýšenie asociatívnosti poskytuje výrazne menší zisk. Túto skutočnosť by sme však nemali úplne ignorovať. V našom vzorovom programe je maximálne využitie pamäte 5,6 MB. Takže pri veľkosti vyrovnávacej pamäte 8 MB budú rovnaké sady vyrovnávacej pamäte použité viackrát (viac ako dvakrát). Keď sa pracovná sada zvyšuje, úspory sa môžu zvyšovať, pretože, ako vidíme, s menšou veľkosťou vyrovnávacej pamäte bude prínos z používania asociatívnosti väčší.
Vo všeobecnosti sa zdá, že zvýšenie asociatívnosti vyrovnávacej pamäte nad 8 má malý vplyv na pracovné zaťaženie jedného vlákna. S príchodom viacjadrových procesorov, ktoré využívajú zdieľanú vyrovnávaciu pamäť L2, sa situácia mení. Teraz máte v podstate dva programy, ktoré pristupujú k rovnakej vyrovnávacej pamäti, čo by v praxi malo zdvojnásobiť výhodu asociativity (alebo štvornásobok pri štvorjadrových procesoroch). Môžeme teda očakávať, že so zvyšujúcim sa počtom jadier by sa mala zvyšovať aj asociativita zdieľanej vyrovnávacej pamäte. Keďže sa to stane nemožným (16-cestná asociativita je už ťažko implementovateľná), dizajnéri procesorov začnú používať zdieľanú vyrovnávaciu pamäť L3 a mimo nej, zatiaľ čo vyrovnávaciu pamäť L2 budú potenciálne zdieľať niektoré podmnožiny jadier.
Ďalší efekt, ktorý môžeme vidieť na obrázku 3.8, je, ako zvýšenie veľkosti vyrovnávacej pamäte zlepšuje výkon. Tieto údaje nemožno interpretovať bez znalosti veľkosti pracovného súboru. Je zrejmé, že vyrovnávacia pamäť veľká ako hlavná pamäť by mala produkovať lepšie výsledky ako menšia vyrovnávacia pamäť, takže vo všeobecnosti neexistujú žiadne obmedzenia na zvýšenie veľkosti vyrovnávacej pamäte a dosiahnutie významných výhod.
Ako je uvedené vyššie, veľkosť pracovnej sady na svojom vrchole je 5,6 MB. Táto hodnota nám neumožňuje vypočítať veľkosť pamäte, ktorá by poskytla maximálny úžitok, ale umožňuje nám túto veľkosť odhadnúť. Problém je v tom, že celá pamäť sa nevyužíva nepretržite, a preto máme spory aj pri 16M vyrovnávacej pamäti a veľkosti pracovnej sady 5,6M (pamätajte na výhodu obojsmernej asociatívnej vyrovnávacej pamäte 16 MB oproti verzii s priamym zobrazením). Môžeme však s istotou povedať, že pri takomto zaťažení bude výhoda vyrovnávacej pamäte 32 MB zanedbateľná. Kto však povedal, že pracovný súbor by mal zostať nezmenený? S rastúcim pracovným zaťažením by sa mala zvyšovať aj veľkosť vyrovnávacej pamäte. Pri nákupe strojov a rozhodovaní o tom, koľko vyrovnávacej pamäte zaplatiť, stojí za to zmerať veľkosť pracovnej sady. Prečo je to dôležité, je možné vidieť na obr. 3.10.
Obr.3.9: Umiestnenie pamäte použitej pri testovaní
Vykonávajú sa dva typy testov. V prvom teste sa prvky spracovávajú postupne. Testovací program používa ukazovateľ n, ale prvky poľa sú vo vzájomnom vzťahu, takže sa prechádzajú v poradí, v akom sa objavujú v pamäti. Táto možnosť je zobrazená v spodnej časti Obr. 3.9. Z posledného prvku prichádza jeden spätný odkaz. V druhom teste (horná časť obrázku) sa prvky poľa prechádzajú v náhodnom poradí. V oboch prípadoch tvoria prvky poľa cyklický, jednoducho prepojený zoznam.
Známe možnosti mapovania hlavnej pamäte na vyrovnávaciu pamäť možno zredukovať na tri typy: priamy, plne asociatívny A čiastočne asociatívne.
O priame zobrazenie riadková adresa i cache pamäť, do ktorej je možné blok namapovať j z OP, je jednoznačne určený výrazom: i = j mod m, Kde m– celkový počet riadkov vo vyrovnávacej pamäti, t. j. na počet riadkov vyrovnávacej pamäte i každý z nich je zobrazený m bloku OP, ak počítanie začína od bloku, ktorého číslo je i.
Priame mapovanie je jednoduchá a lacná metóda mapovania na implementáciu. Jeho hlavnou nevýhodou je rigidné priradenie jedného riadku vo vyrovnávacej pamäti k určitým OP blokom. Ak teda program striedavo pristupuje k slovám z dvoch rôznych blokov mapovaných na rovnaký riadok vyrovnávacej pamäte, tento riadok sa bude neustále aktualizovať a pravdepodobnosť zásahu bude nízka.
Plne asociatívny displej umožňuje prekonať nevýhodu priameho, čo umožňuje načítanie ľubovoľného bloku OP do ľubovoľného riadku vyrovnávacej pamäte. Asociatívne mapovanie poskytuje flexibilitu pri výbere riadku pre novo zapísaný blok. Základnou nevýhodou tejto metódy je, že vyžaduje kontrolu všetkých riadkov vyrovnávacej pamäte.
Čiastočne asociatívne mapovanie je jedným z možných kompromisov, ktorý spája výhody metód priameho a asociatívneho mapovania a je do určitej miery zbavený ich nevýhod. Cache pamäť je rozdelená na v podmnožiny (množiny), z ktorých každá obsahuje k struny (zvyčajne sa hovorí, že sada má k vstupy). Závislosť medzi množinou a OP blokmi je rovnaká ako pri priamom mapovaní: na čiary zahrnuté v množine i, môžu byť mapované iba dobre definované bloky hlavnej pamäte v súlade so vzťahom i = j mod v, Kde j– adresa bloku OP. Zároveň je umiestnenie blokov pozdĺž línií modulu ľubovoľné a na nájdenie požadovaného riadku v module sa používa asociatívny princíp.
V extrémnych prípadoch, kedy v = m, k= 1, množinové asociatívne mapovanie sa zredukuje na priame a kedy v = 1,k = m- asociatívne.
V závislosti od spôsobu určenia vzájomnej korešpondencie medzi riadkom vyrovnávacej pamäte a bloku hlavnej pamäte sa rozlišujú tri architektúry vyrovnávacej pamäte:
· plne asociatívna vyrovnávacia pamäť;
Priamo mapovaná vyrovnávacia pamäť
· set-asociatívna vyrovnávacia pamäť.
IN plne asociatívna vyrovnávacia pamäťľubovoľný blok hlavnej pamäte môže byť umiestnený v ľubovoľnom riadku vyrovnávacej pamäte alebo ľubovoľný riadok vyrovnávacej pamäte sa môže mapovať na akýkoľvek blok hlavnej pamäte. V tomto prípade sa do adresára vložia najvýznamnejšie bity adresy údajov vo vyrovnávacej pamäti mínus bity, ktoré určujú polohu (offset) údajov v riadku (bloku), a použijú sa ako značka. V takejto architektúre je na určenie, či sú v cache na konkrétnej adrese dáta, potrebné porovnať bity vyššieho rádu tejto adresy s tagmi všetkých riadkov v adresári cache. Ak sa takéto porovnanie vykoná postupne, zaberie to príliš veľa času a vyrovnávacia pamäť stráca zmysel kvôli nízkemu výkonu. Preto sa takéto porovnanie musí vykonávať paralelne pre všetky značky. Túto požiadavku najlepšie spĺňa asociatívna pamäť, to znamená, že tag musí byť uložený v pamäti cache pre tagy.
Takáto organizácia vyrovnávacej pamäte je komplexný hardvérový problém, ktorý je možné vyriešiť len pre malé objemy, t. j. plne asociatívna vyrovnávacia pamäť nemôže mať vzhľadom na svoju zložitosť veľký objem a používa sa spravidla na pomocné účely. Napríklad procesory Intel používajú na zostavenie plne asociatívnu vyrovnávaciu pamäť v stránkovacom bloku asociatívny prekladový buffer TLB (Translation Look aside Buffer), navrhnutý na urýchlenie prístupu k veľmi využívaným stránkam.
Opačná architektúra je priama vyrovnávacia pamäť mapy. V priamo mapovanej vyrovnávacej pamäti môže byť špecifický blok hlavnej pamäte umiestnený iba v presne definovanom riadku vyrovnávacej pamäte. Hlavná pamäť je konvenčne rozdelená na stránky, ktorých veľkosť sa zhoduje s veľkosťou vyrovnávacej pamäte. Architektúra priameho mapovania znamená, že každý riadok vyrovnávacej pamäte môže mapovať iba blok, ktorý mu zodpovedá, z ktorejkoľvek stránky hlavnej pamäte. Bloky s rovnakými číslami strán skončia v rovnakom riadku vyrovnávacej pamäte. V dôsledku toho je každý riadok vyrovnávacej pamäte nárokovaný mnohými blokmi hlavnej pamäte s rovnakými číslami na stránke. Jeden riadok môže obsahovať kópiu iba jedného z týchto blokov. Značka je číslo stránky, ktorej blok zaberá príslušný riadok vyrovnávacej pamäte. V takejto architektúre je na určenie, či sú v cache na konkrétnej adrese dáta, potrebné porovnať číslo stránky, ku ktorej táto adresa patrí, s tagom toho riadku v adresári cache, ktorý zodpovedá bloku na stránke. obsahujúcu danú adresu, t. j. je potrebné porovnať iba jednu vec.
Priama mapovaná vyrovnávacia pamäť má najjednoduchšiu hardvérovú implementáciu, pretože vyrovnávacia pamäť má štruktúru bežnej priamo adresovateľnej pamäte a je potrebné iba jedno porovnávacie zariadenie. Preto môže byť takáto vyrovnávacia pamäť veľká.
Je prostredníkom medzi plne asociatívnou vyrovnávacou pamäťou a vyrovnávacou pamäťou s priamym mapovaním set-asociatívna vyrovnávacia pamäť, ktorý sa používa najmä v moderných mikroprocesoroch. V cache asociatívnej množiny, na rozdiel od cache s priamym mapovaním, si každý blok hlavnej pamäte môže nárokovať jeden z niekoľkých riadkov cache kombinovaných do sady. To zvyšuje pravdepodobnosť úspešného odvolania. Zjednodušene môžeme uvažovať, že množinová asociatívna vyrovnávacia pamäť je niekoľko paralelných a koordinovaných priamych mapovacích kanálov, v ktorých riadky s rovnakými číslami tvoria zodpovedajúcu množinu. Nastavená čiara predstavujúca požadovaný blok hlavnej pamäte je určená porovnaním značiek (ako v asociatívnej vyrovnávacej pamäti), ktoré sa vykonáva paralelne na všetkých kanáloch vyrovnávacej pamäte. Každá sada má priradený atribút, ktorý špecifikuje riadok sady, ktorý sa má nahradiť novým blokom v prípade vynechania vyrovnávacej pamäte. Kandidátom na nahradenie je zvyčajne riadok, ku ktorému sa nepristupovalo najdlhšie (algoritmus LRU - Najmenej nedávno použité). Je tiež možné použiť náhradný algoritmus FIFO alebo dokonca náhodné nahradenie, čo je jednoduchšie, ale menej efektívne.
Prečo vidíme neustále zvyšovanie výkonu jednovláknových programov? Momentálne sa nachádzame v štádiu vývoja mikroprocesorových technológií, kedy nárast rýchlosti jednovláknových aplikácií závisí len od pamäte. Počet jadier rastie, no frekvencia je pevne stanovená na 4 GHz a neposkytuje nárast výkonu.
Rýchlosť a frekvencia prevádzky pamäte je hlavná vec, prostredníctvom ktorej dostaneme „náš kúsok koláča zadarmo“ (odkaz). Preto je dôležité využívať pamäť čo najefektívnejšie a najmä tak rýchlo ako vyrovnávaciu pamäť. Na optimalizáciu programu pre konkrétny počítač je užitočné poznať vlastnosti vyrovnávacej pamäte procesora: počet úrovní, veľkosť, dĺžka riadku. To je dôležité najmä vo vysokovýkonnom kóde – jadrách systému, matematických knižniciach.
Ako určiť vlastnosti automatickej vyrovnávacej pamäte? (Samozrejme, parsovanie cpuinfo neprichádza do úvahy, už len preto, že by sme v konečnom dôsledku chceli získať algoritmus, ktorý možno ľahko implementovať v iných operačných systémoch. Pohodlné, však?) Presne toto teraz urobíme.
Trochu teórie
V súčasnosti sa bežne používajú tri typy vyrovnávacej pamäte: vyrovnávacia pamäť s priamym mapovaním, pridružená vyrovnávacia pamäť a viacasociačná vyrovnávacia pamäť.Vyrovnávacia pamäť priameho mapovania
- daný riadok RAM môže byť namapovaný na jeden riadok vyrovnávacej pamäte, ale na každý riadok vyrovnávacej pamäte môže byť priradených veľa možných riadkov pamäte RAM.Plne asociatívna vyrovnávacia pamäť
- každá linka RAM môže byť namapovaná na akúkoľvek linku cache.Multiasociačná vyrovnávacia pamäť
- Vyrovnávacia pamäť je rozdelená do niekoľkých „bánk“, z ktorých každá funguje ako priamo mapovaná vyrovnávacia pamäť, takže riadok RAM nemožno mapovať na jeden možný záznam vyrovnávacej pamäte (ako by to bolo v prípade priameho mapovania ), ale do jednej z viacerých bánk; Výber banky sa vykonáva na základe LRU alebo iného mechanizmu pre každý riadok umiestnený vo vyrovnávacej pamäti.LRU - vysťahovanie „najdlhšej nepoužívanej“ linky, vyrovnávacia pamäť.
Nápad
Ak chcete určiť počet úrovní vyrovnávacej pamäte, musíte zvážiť poradie prístupov k pamäti, v ktorom bude prechod jasne viditeľný. Rôzne úrovne vyrovnávacej pamäte sa líšia predovšetkým rýchlosťou odozvy pamäte. V prípade zmeškania vyrovnávacej pamäte, vyrovnávacia pamäť L1 vyhľadá údaje v nasledujúcich úrovniach pamäte a ak je veľkosť údajov väčšia ako L1 a menšia ako L2, potom rýchlosť odozvy pamäte bude rýchlosť odozvy L2. Predchádzajúce tvrdenie platí aj vo všeobecných prípadoch.Je jasné, že musíme vybrať test, na ktorom jasne uvidíme chýbajúce vyrovnávacie pamäte a otestovať ho na rôznych veľkostiach údajov.
Keďže poznáme logiku vyrovnávacích pamätí s pridruženými súbormi, ktoré fungujú pomocou algoritmu LRU, nie je ťažké prísť s algoritmom, v ktorom vyrovnávacia pamäť „padá“, nie je nič zložité - prechádza cez linku. Za kritérium efektívnosti budeme považovať čas jedného prístupu do pamäte. Prirodzene, musíte postupne pristupovať ku všetkým prvkom riadku a mnohokrát to zopakovať, aby ste spriemerovali výsledok. Napríklad môžu nastať prípady, keď sa linka zmestí do cache, ale pri prvom prechode linku načítame z RAM a dostaneme teda úplne neadekvátny čas.
Chcel by som vidieť niečo podobné ako kroky, kráčať po líniách rôznej dĺžky. Ak chcete určiť povahu krokov, zvážte príklad prechodu riadkov pre priamu a asociatívnu vyrovnávaciu pamäť; prípad s vyrovnávacou pamäťou s priradenou množinou bude priemerom medzi vyrovnávacou pamäťou s priamym mapovaním a pridruženou vyrovnávacou pamäťou.
Asociačná vyrovnávacia pamäť
Keď veľkosť údajov prekročí veľkosť vyrovnávacej pamäte,
Plne asociatívna vyrovnávacia pamäť chýba pri každom prístupe do pamäte.
Priama vyrovnávacia pamäť
Pozrime sa na rôzne veľkosti čiar. - zobrazuje maximálny počet chýb, ktoré procesor strávi na prístup k prvkom poľa pri ďalšom prechode cez linku.
Ako môžete vidieť, doba prístupu do pamäte sa nezväčšuje prudko, ale so zvyšujúcim sa objemom dát. Keď veľkosť údajov prekročí veľkosť vyrovnávacej pamäte, dôjde k vynechaniu každého prístupu do pamäte.
Preto pri asociatívnej vyrovnávacej pamäti bude krok vertikálny, zatiaľ čo pri priamej vyrovnávacej pamäti sa bude postupne zvyšovať až na dvojnásobok veľkosti vyrovnávacej pamäte. Viacasociačná vyrovnávacia pamäť bude priemerným prípadom, „nárazom“, už len preto, že čas prístupu nemôže byť lepší ako priamy.
Ak hovoríme o pamäti, tak najrýchlejšia je cache, nasleduje operačná pamäť, najpomalšia je swap, o tom sa v budúcnosti baviť nebudeme. Na druhej strane rôzne úrovne vyrovnávacej pamäte (dnes majú procesory spravidla 2-3 úrovne vyrovnávacej pamäte) majú rôznu rýchlosť odozvy pamäte: čím vyššia úroveň, tým nižšia je rýchlosť odozvy. A preto, ak je riadok umiestnený do vyrovnávacej pamäte prvej úrovne (ktorá je mimochodom úplne asociatívna), čas odozvy bude kratší ako pri riadku podstatne väčšej veľkosti, než je veľkosť vyrovnávacej pamäte prvej úrovne. Preto na grafe času odozvy pamäte verzus veľkosť riadku bude niekoľko plató – plató odozvy pamäte a plató spôsobené rôznymi úrovňami vyrovnávacej pamäte.
*Plató funkcie - ( i:x, f(xi) - f(xi+1)< eps: eps → 0 }
Začnime s implementáciou
Na implementáciu použijeme C (ANSI C99).Kód bol napísaný rýchlo, zvyčajný prechod cez riadky rôznych dĺžok, menej ako 10 MB, vykonaný mnohokrát. (Uvedieme malé časti programu, ktoré nesú sémantickú záťaž).
Pre (i = 0; i< 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }
Pozrieme sa na graf a vidíme jeden veľký krok. Ale teoreticky všetko funguje ako má. Preto musíte pochopiť: prečo sa to deje? A ako to opraviť?
Je zrejmé, že sa to môže stať z dvoch dôvodov: buď procesor nemá vyrovnávaciu pamäť, alebo je procesor taký dobrý v hádaní prístupov k pamäti. Keďže prvá možnosť má bližšie k sci-fi, dôvodom všetkého je dobrá predpoveď hovorov.
Faktom je, že dnešné ďaleko od špičkových procesorov okrem princípu priestorovej lokality predpovedajú aj aritmetický postup v poradí prístupu k pamäti. Preto je potrebné randomizovať prístupy do pamäte.
Dĺžka randomizovaného poľa by mala byť porovnateľná s dĺžkou hlavného reťazca, aby sa zbavila veľkej zrnitosti volaní, a dĺžka poľa by nemala byť mocninou dvoch, z tohto dôvodu sa vyskytli „prekrývania“. - čo by mohlo viesť k odľahlým hodnotám. Najlepšie je nastaviť konštantu zrnitosti, a to aj vtedy, ak je zrnitosť prvočíslo, potom sa môžete vyhnúť účinkom prekrytí. A dĺžka randomizovaného poľa je funkciou dĺžky reťazca.
pre (i = 0; i< j; i++) {
for (m = 0; m < L; m++) {
for (x = 0; x < M; x++){
v = A[ random[x] + m ];
}
}
}
Potom sme prekvapili dlho očakávaným „obrázkom“, o ktorom sme hovorili na začiatku.
Program je rozdelený na 2 časti - testovanie a spracovanie dát. Je len na vás, či napíšete skript v 3 riadkoch, aby ste ho spustili, alebo ho spustite 2-krát manuálne.
Výpis súboru size.file v systéme Linux
#include
Výpis veľkosti súboru.zo systému Windows
#include
Vo všeobecnosti si myslím, že je všetko jasné, ale rád by som objasnil niekoľko bodov.
Pole A je deklarované ako nestále – táto direktíva nám zaručuje, že pole A bude vždy prístupné, to znamená, že ho „nevystrihne“ ani optimalizátor, ani kompilátor. Za zmienku tiež stojí, že celé výpočtové zaťaženie sa vykonáva pred meraním času, čo nám umožňuje znížiť vplyv pozadia.
Súbor je preložený do assembleru na Ubuntu 12.04 a kompilátore gcc 4.6 - cykly sú uložené.
Spracovanie dát
Na spracovanie údajov je logické používať deriváty. A napriek tomu, že šum narastá s rastúcim poradím diferenciácie, využije sa druhá derivácia a jej vlastnosti. Bez ohľadu na to, ako hlučná je druhá derivácia, nás zaujíma iba znamienko druhej derivácie.Nájdeme všetky body, v ktorých je druhá derivácia väčšia ako nula (s určitou chybou, pretože druhá derivácia, okrem toho, že je vypočítaná numericky, je veľmi hlučná). Funkciu nastavíme v závislosti od znamienka druhej derivácie funkcie na veľkosti cache. Funkcia nadobúda hodnotu 1 v bodoch, kde je znamienko druhej derivácie väčšie ako nula, a nulu, ak je znamienko druhej derivácie menšie alebo rovné nule.
Body „vzletu“ sú začiatkom každého kroku. Pred spracovaním údajov je tiež potrebné odstrániť jednotlivé odľahlé hodnoty, ktoré nemenia význam údajov, ale vytvárajú znateľný šum.
Výpis súboru data_pr.c
#include
Testy
Pre každý test budú uvedené kľúče CPU/OS/kernelu/kompilátora/kompilácie.
Intel Pentium CPU P6100 @ 2,00 GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrtL1 = 0,05 Mb
L2 = 0,2 Mb
L3 = 2,7 Mb- Nebudem uvádzať všetky dobré testy, radšej sa porozprávajme o „Rake“
Poďme sa rozprávať o "hrabe"
Rake bol zistený pri spracovaní údajov na serverovom procesore Intel Xeon 2.4/L2 = 512 kb/Windows Server 2008Problém spočíva v malom počte bodov spadajúcich do intervalu dosiahnutia plató, preto je skok v druhej derivácii nepostrehnuteľný a berie sa ako šum.
Tento problém môžete vyriešiť pomocou metódy najmenších štvorcov alebo spustiť testy pri identifikácii zón plató.
Chcel by som počuť vaše návrhy na riešenie tohto problému.
Bibliografia
- Makarov A.V. Počítačová architektúra a nízkoúrovňové programovanie.
- Ulrich Drepper Čo by mal vedieť každý programátor o pamäti
· cache s priamym mapovaním (umiestnením);
· plne asociatívna vyrovnávacia pamäť;
· viacnásobná asociatívna vyrovnávacia pamäť alebo čiastočne asociatívna.
Priama mapovaná vyrovnávacia pamäť(ubytovanie) je najviac
jednoduchý typ vyrovnávacej pamäte. Adresa pamäte jednoznačne identifikuje reťazec
cache, do ktorej bude blok informácií umiestnený. Zároveň je to výhodné
Predpokladá sa, že RAM je rozdelená na bloky a každý
ktorému bloku vo vyrovnávacej pamäti je pridelený iba jeden riadok. Toto je jednoduchá a lacná metóda zobrazenia na implementáciu. Jeho hlavnou nevýhodou je rigidné priradenie jedného riadku vo vyrovnávacej pamäti k určitým OP blokom. Ak teda program striedavo pristupuje k slovám z dvoch rôznych blokov namapovaných na rovnaký riadok vyrovnávacej pamäte, tento riadok sa bude neustále aktualizovať a pravdepodobnosť zásahu bude nízka.
Plne zmapovaná vyrovnávacia pamäť umožňuje prekonať nevýhodu priameho, čo umožňuje načítanie ľubovoľného bloku OP do ľubovoľného riadku vyrovnávacej pamäte. Riadiaca logika prideľuje v adrese OP dve polia: pole značky a pole slova. Pole tagu sa zhoduje s adresou bloku OP. Ak chcete skontrolovať, či je kópia bloku vo vyrovnávacej pamäti, logika správy vyrovnávacej pamäte musí súčasne kontrolovať značky všetkých riadkov v porovnaní s poľom značky adresy. Asociatívne mapovanie poskytuje flexibilitu pri výbere riadku pre novo zapísaný blok. Zásadnou nevýhodou tejto metódy je nutnosť použitia drahej asociatívnej pamäte.
Multiasociačný typ alebo čiastočne asociatívny typ mapovania – Ide o jeden z možných kompromisov, spájajúci výhody priamych a asociatívnych metód. Vyrovnávacia pamäť (tagy aj dáta) je rozdelená do niekoľkých modulov. Závislosť medzi modulom a blokmi OP je rovnako prísna ako pri priamom mapovaní. Ale umiestnenie blokov pozdĺž línií modulu je ľubovoľné a na nájdenie požadovaného riadku v module sa používa asociatívny princíp. Tento spôsob zobrazovania sa najčastejšie používa v moderných mikroprocesoroch.
Mapovanie OP sektorov vo vyrovnávacej pamäti.
Tento typ mapovania sa používa vo všetkých moderných počítačoch a spočíva v tom, že celý OP je rozdelený na sektory pozostávajúce z pevného počtu po sebe nasledujúcich blokov. Pamäť cache je tiež rozdelená na sektory obsahujúce rovnaký počet riadkov. Umiestnenie blokov v sektore OP a sektore cache je úplne identické. Mapovanie sektora do vyrovnávacej pamäte sa vykonáva asociatívne, ktorýkoľvek sektor z OP môže byť umiestnený v akomkoľvek sektore vyrovnávacej pamäte. Počas prevádzky sa teda ALU pri hľadaní ďalšieho príkazu obráti na OP, v dôsledku čoho sa do vyrovnávacej pamäte načíta celý sektor informácií z OP (ak tam nie je blok obsahujúci tento príkaz) a podľa princíp lokality, vďaka tomu sa výrazne zvyšuje výkon systému.
Hierarchický model vyrovnávacej pamäte
Pamäť cache má zvyčajne viacúrovňovú architektúru. Napríklad na počítači s 32 KB internej (v jadre CPU) a 1 MB externej (v puzdre CPU alebo základnej dosky) vyrovnávacej pamäte by sa prvá považovala za vyrovnávaciu pamäť úrovne 1 (L1) a druhá by sa považovala za úroveň vyrovnávacej pamäte. 2. vyrovnávacia pamäť. úroveň (L2). V moderných serverových systémoch môže byť počet úrovní vyrovnávacej pamäte až štyri, hoci najčastejšie sa používa dvoj- alebo trojúrovňová schéma.
V niektorých architektúrach procesorov je vyrovnávacia pamäť úrovne 1 rozdelená na vyrovnávaciu pamäť inštrukcií (InstructionCache, I-cache) a dátovú vyrovnávaciu pamäť (DataCache, D-cache), pričom nemusí mať nevyhnutne rovnakú veľkosť. Z hľadiska návrhu obvodu je jednoduchšie a lacnejšie navrhnúť samostatnú I-cache a D-cache: načítanie príkazov sa vykonáva pomocou I-boxu a vzorkovanie dát sa vykonáva pomocou E-boxu a F-boxu, hoci v oboch prípadoch sa používa A-box a C-box. Všetky tieto bloky sú veľké a poskytnúť im súčasný a rýchly prístup k jednej vyrovnávacej pamäti je problematické. Okrem toho by si to nevyhnutne vyžadovalo zvýšenie počtu prístupových portov, čo tiež komplikuje úlohu návrhu.
Keďže I-cache a D-cache musia poskytovať veľmi nízke latencie prístupu (to platí pre akúkoľvek L1 cache), musia obetovať svoju veľkosť – zvyčajne je to od 16 do 32 KB. Koniec koncov, čím menšia je veľkosť vyrovnávacej pamäte, tým ľahšie je dosiahnuť nízke latencie prístupu.
Vyrovnávacia pamäť úrovne 2 je zvyčajne jednotná, čo znamená, že môže obsahovať pokyny aj údaje. Ak je zabudovaný do jadra CPU, potom hovoria o S-cache (SecondaryCache, sekundárna vyrovnávacia pamäť), inak - o B-cache (BackupCache, zálohovacia vyrovnávacia pamäť). V moderných serverových CPU sa veľkosť S-cache pohybuje od jedného do niekoľkých megabajtov, aB-cache - až 64 MB. Ak dizajn CPU obsahuje vstavanú vyrovnávaciu pamäť L3, nazýva sa T-cache (TernaryCache). Každá ďalšia úroveň vyrovnávacej pamäte je spravidla pomalšia, ale väčšia ako predchádzajúca. Ak má systém B-cache (ako poslednú úroveň modelu vyrovnávacej pamäte), potom ju môže ovládať CPU aj systémová logika.
Ak v čase vykonania určitého príkazu nie sú preň žiadne údaje v registroch, potom budú vyžiadané z najbližšej úrovne vyrovnávacej pamäte, t. j. z D-cache. Ak nie sú v D-Cache, požiadavka sa odošle do S-cache atď. V najhoršom prípade sa dáta doručia priamo z pamäte. Možný je však ešte smutnejší scenár, keď sa podsystému správy virtuálnej pamäte operačného systému (OS) podarí vytlačiť ich do stránkovacieho súboru na pevnom disku. V prípade doručovania z RAM sa strata času na získanie potrebných dát môže pohybovať v desiatkach až stovkách cyklov CPU a v prípade dát umiestnených na pevnom disku sa už môžeme baviť o miliónoch cyklov.
Asociatívnosť vyrovnávacej pamäte
Jedna zo základných charakteristík vyrovnávacej pamäte, úroveň asociatívnosti, odráža jej logickú segmentáciu. Faktom je, že postupné prehľadávanie všetkých riadkov vyrovnávacej pamäte pri hľadaní potrebných údajov by vyžadovalo desiatky hodinových cyklov a negovalo by všetky zisky z používania pamäte zabudovanej v CPU. Preto sú bunky RAM pevne viazané na riadky vyrovnávacej pamäte (každý riadok môže obsahovať údaje z pevnej sady adries), čo výrazne znižuje čas vyhľadávania. Každé miesto RAM môže mať priradených viac ako jeden riadok vyrovnávacej pamäte: napríklad n-waysetassociative znamená, že informácie na danej adrese RAM môžu byť uložené v n miestach vyrovnávacej pamäte.
Výber miesta je možné vykonať pomocou rôznych algoritmov, medzi ktorými sú najčastejšie používané princípy nahradenia LRU (LeastRecentlyUsed, naposledy požadovaný záznam je nahradený) a LFU (LeastFrequentlyUsed, záznam najmenej často požadovaný), hoci existujú modifikácie. týchto zásad. Napríklad plne asociatívna vyrovnávacia pamäť, v ktorej môžu byť informácie umiestnené na ľubovoľnej adrese v RAM umiestnené v ľubovoľnom riadku. Ďalšou možnosťou je priame mapovanie, pri ktorom je možné informácie, ktoré sa nachádzajú na ľubovoľnej adrese v RAM, umiestniť iba na jedno miesto vo vyrovnávacej pamäti. Prirodzene, táto možnosť poskytuje najvyšší výkon, pretože pri kontrole dostupnosti informácií sa bude musieť kontrolór „pozerať“ iba na jeden riadok vyrovnávacej pamäte, ale je tiež najmenej efektívny, pretože kontrolór nezvolí „optimálne“ umiestnenie. pri písaní. Vzhľadom na rovnakú veľkosť vyrovnávacej pamäte bude plne asociatívna schéma najmenej rýchla, ale najefektívnejšia.
V praxi sa nachádza plne asociatívna vyrovnávacia pamäť, ale spravidla má veľmi malú veľkosť. Napríklad CPU Cyrix 6x86 využívalo 256 bajtov tejto vyrovnávacej pamäte inštrukcií pred zjednotenou vyrovnávacou pamäťou L1 s veľkosťou 16 alebo 64 kB. Plne asociatívna schéma sa často používa pri navrhovaní TLB (o čom sa bude diskutovať nižšie), medzipamäte adries vetvy, vyrovnávacej pamäte na čítanie a zápis atď. Úrovne asociatívnosti I-cache a D-cache sú spravidla dosť nízke (až na štyri kanály) - ich zvýšenie je nepraktické, pretože vedie k zvýšeniu oneskorenia prístupu a v konečnom dôsledku má negatívny vplyv na výkon. Ako určitá kompenzácia sa zvyšuje asociativita S-cache (zvyčajne až 16 kanálov), keďže oneskorenia pri prístupe k tejto vyrovnávacej pamäti nie sú dôležité. Napríklad podľa výsledkov štúdií často používaných celočíselných problémov stačila štvorkanálová D-cache Intel Pentium III 16 KB na pokrytie asi 93 % požiadaviek a štvorkanálová I-cache 16 KB. pokrývať 99 % žiadostí.
Riadok vyrovnávacej pamäte a veľkosť značky
Dôležitou charakteristikou vyrovnávacej pamäte je veľkosť riadku. Typicky existuje jeden záznam adresy na riadok (nazývaný tag), ktorý označuje, ktorej adrese v RAM riadok zodpovedá. Je zrejmé, že číslovanie jednotlivých bajtov je nepraktické, pretože v tomto prípade bude objem servisných informácií vo vyrovnávacej pamäti niekoľkonásobne väčší ako objem samotných údajov. Preto sa jeden tag zvyčajne spolieha na jeden riadok, ktorý má zvyčajne veľkosť 32 alebo 64 bajtov (skutočné maximum je 1024 bajtov) a zodpovedá štyrom (niekedy ôsmim) šírkam FSB. Okrem toho je každý riadok vyrovnávacej pamäte sprevádzaný niektorými informáciami na zabezpečenie odolnosti voči chybám: jeden alebo viac paritných bitov alebo osem alebo viac bajtov na detekciu a opravu chýb (ECC, ErrorCheckingandCorrecting), hoci hromadné riešenia často nepoužívajú ani jeden iný.
Veľkosť značky vyrovnávacej pamäte závisí od troch hlavných faktorov: veľkosť vyrovnávacej pamäte, maximálne množstvo pamäte RAM, ktorú možno uložiť do vyrovnávacej pamäte, a asociativita vyrovnávacej pamäte. Matematicky sa táto veľkosť vypočíta podľa vzorca:
Stag=log2(Smem*A/Scache),
kde Stag je veľkosť jedného tagu cache v bitoch; Smem - maximálne množstvo pamäte RAM uložené vo vyrovnávacej pamäti v bajtoch; Scache - veľkosť vyrovnávacej pamäte v bajtoch; A - asociativita vyrovnávacej pamäte v kanáloch.
To znamená, že systém s 1 GB RAM a 1 MB dvojcestnej asociatívnej vyrovnávacej pamäte by vyžadoval 11 bitov na značku. Je pozoruhodné, že skutočná veľkosť riadku vyrovnávacej pamäte žiadnym spôsobom neovplyvňuje veľkosť značky, ale nepriamo ovplyvňuje počet značiek. Malo by byť zrejmé, že nemá zmysel zmenšovať veľkosť riadku vyrovnávacej pamäte ako je šírka systémovej dátovej zbernice, ale mnohonásobné zvýšenie veľkosti povedie k nadmernému zaneseniu vyrovnávacej pamäte zbytočnými informáciami a nadmernému zaťaženiu systémová zbernica a pamäťová zbernica. Okrem toho, maximálne množstvo vyrovnávacej pamäte, ktorú možno uložiť do vyrovnávacej pamäte, nemusí zodpovedať maximálnemu možnému množstvu nainštalovanej pamäte RAM v systéme. Ak nastane situácia, keď je viac pamäte RAM, ako je možné uložiť do vyrovnávacej pamäte, vyrovnávacia pamäť bude obsahovať informácie iba z nižšieho segmentu pamäte RAM. Presne taká bola situácia s platformou Socket7/Super7. Čipsety pre túto platformu umožňovali použitie veľkého množstva pamäte RAM (od 256 MB do 1 GB), pričom objem vo vyrovnávacej pamäti bol často obmedzený na prvých 64 MB (hovoríme o B-cache umiestnenej na základnej doske) kvôli použitiu lacných 8-bitových mikroobvodov SRAM tagov (z toho 2 bity boli vyhradené pre indikátory platnosti a modifikáciu reťazca). To viedlo k citeľnému poklesu výkonu.
