CPU cache

Mezipaměť CPU je mezipaměť používaná CPU počítače ke snížení průměrné doby přístupu do paměti . Jedná se o malý, ale velmi rychlý typ paměti, který uchovává kopie dat, k nimž se nejčastěji přistupuje, v hlavní paměti . Ten je součástí procesoru a je umístěn velmi blízko něj. Není viditelný softwarem , ale je řízen a spravován hardwarem . To je součástí smartphonů a tabletů a lze je vidět přímo ze softwaru.

Funkce

Porovnání mezi pamětí RAM a mezipamětí CPU

Diagram vlevo ukazuje dvě paměti, hlavní a mezipaměť. Každé umístění mezipaměti obsahuje data ( řádek mezipaměti ), která se mezi různými typy mezipaměti pohybuje mezi 512 bajty a 8 MB velikost umístění vyrovnávací paměti je normálně menší než u normální paměti, která se obvykle pohybuje mezi 1 a 16 GB . Každé paměťové místo má index, což je jedinečný identifikátor používaný k odkazování na toto konkrétní místo. Index umístění v hlavní paměti se nazývá adresa paměti. Každé umístění mezipaměti má také značku, která obsahuje hlavní index paměti tam načtených dat. V mezipaměti dat se tyto hodnoty nazývají bloky mezipaměti nebo řádky mezipaměti. Dokud je většina přístupů do paměti pro data uložená v mezipaměti, průměrná latence přístupu do paměti bude blíže latenci mezipaměti než hlavní paměť, takže výkon bude lepší.

Když procesor potřebuje číst nebo zapisovat do daného umístění v hlavní paměti, nejprve zkontroluje, zda je obsah tohoto umístění načten do mezipaměti. To se provádí porovnáním adresy místa v paměti s jakýmikoli štítky v mezipaměti, které mohou obsahovat data na této adrese. Pokud procesor zjistí, že umístění paměti je v mezipaměti, označuje se to jako zásah do mezipaměti, jinak chyba mezipaměti. V případě zásahu do mezipaměti procesor okamžitě čte nebo zapisuje data do řádku mezipaměti. Poměr návštěv mezipaměti k celkovému počtu se také nazývá míra shody a je nepřímým měřítkem účinnosti algoritmu vyrovnávací paměti.

V případě cache miss následuje (u většiny cache) vytvoření nové entity, která obsahuje procesorem právě vyžádaný štítek a kopii dat v hlavní paměti. Taková porucha je relativně pomalá, protože vyžaduje přenos dat z hlavní paměti, v některých případech po vymazání dat, která již nejsou platná.

To je důvod, proč velmi velká mezipaměť, i když je spravována účinným algoritmem, může být za určitých okolností z hlediska výkonu kontraproduktivní. Ve skutečnosti proces mazání prošlých a neplatných dat v mezipaměti a načítání správných dat do mezipaměti obvykle trvá déle, než když CPU čte data přímo z hlavní paměti bez použití mezipaměti. Jinými slovy, velká mezipaměť může ve specifických výpočetních situacích, například neiterativních, vést k vyššímu počtu vynechání mezipaměti než k vyhledání mezipaměti, a to s výrazným snížením výkonu.

Některé provozní detaily

Aby se v případě vynechání mezipaměti uvolnilo místo pro nová data , musí mezipaměť obecně smazat obsah jednoho z řádků. Heuristika , kterou používá k výběru dat k odstranění, se nazývá politika nahrazení. Zásadním problémem jakékoli zásady nahrazování je předvídat data z mezipaměti, která budou v budoucnu méně pravděpodobně vyžadována.

Předpovídání budoucnosti je obtížné, zejména pro hardwarové mezipaměti, které musí využívat pravidla, která lze snadno implementovat do obvodů, takže existuje řada zásad pro nahrazení a žádnou z nich nelze považovat za dokonalou. Jeden z nejpopulárnějších, LRU (z anglického Least Last Last Used , které se používá méně nedávno ), ve skutečnosti nahrazuje data, ke kterým se přistupovalo méně nedávno.

Když jsou data zapsána do mezipaměti, musí být po určité době stále zapsána do hlavní paměti . Rozhodnutí o tom, kdy by k tomuto zápisu mělo dojít, je řízeno zásadami psaní. V mezipaměti pro zápis vede každý zápis do mezipaměti k současnému zápisu do hlavní paměti. Alternativně mezipaměť pro zpětný zápis neprovede tuto akci okamžitě: naopak, mezipaměť sleduje řádky, které obsahují data, která mají být aktualizována, vhodným nastavením toho, co se nazývá nečistý bit . Data se ve skutečnosti zapisují do paměti pouze tehdy, když je třeba je vymazat z mezipaměti, aby se uvolnilo místo pro nové informace. Z tohoto důvodu neúspěšné vyhledávání v mezipaměti se zpětným zápisem často generuje dva přístupy do paměti: jeden pro čtení nových dat a druhý pro zápis starých informací (pokud je indikován nečistým bitem). Jak zpětný zápis, tak i zápis slouží k udržení konzistence mezi úrovněmi paměti.

Existují také některé přechodné politiky. Mezipaměť by například mohla být propisována, ale zápisy by mohly být dočasně zařazeny do fronty, aby bylo možné zpracovat více zápisů společně a optimalizovat tak přístup ke sběrnici .

Data v hlavní paměti, jejichž kopie existuje v mezipaměti, by mohla být změněna jinými příčinami (není nepravděpodobná událost, například ve víceprocesorovém systému ), proto by data v mezipaměti mohla být zastaralá. Komunikační protokoly mezi systémy správy mezipaměti, které udržují konzistenci dat, se nazývají protokoly konzistence.

Doba potřebná k načtení dat z paměti (latence čtení) je důležitá, protože CPU často může dokončit frontu operací, zatímco čeká na doručení požadovaných dat. Když mikroprocesor dosáhne tohoto stavu, nazývá se to zastavení CPU. Jak se mikroprocesory zrychlují, zastavování kvůli chybě mezipaměti plýtvá velkým množstvím výpočetního výkonu; moderní procesory mohou ve skutečnosti provádět stovky instrukcí za stejnou dobu, kterou zabere načtení jediného kusu dat z paměti. Proto byly studovány různé techniky, jak „udržet CPU zaneprázdněný“ během této fáze. Některé mikroprocesory, jako je Pentium Pro , se pokoušejí provádět operace, které následují po tom, který čeká na data, pokud jsou na nich nezávislé (z tohoto důvodu se jim v angličtině říká out-of-order ). Pentium 4 používá simultánní multithreading (nazývaný HyperThreading v terminologii Intelu ), který umožňuje jinému programu používat CPU, zatímco první program čeká na data z hlavní paměti.

Asociativita

Která paměťová místa lze načíst do kterých míst mezipaměti

Zásada nahrazení rozhoduje o tom, kde v mezipaměti může být umístěna kopie konkrétního paměťového místa. Pokud si zásada nahrazení může svobodně vybrat, do které řádky mezipaměti se mají data načíst, mezipaměť se nazývá plně asociativní (nebo dokonce plně asociativní). Na druhou stranu, pokud lze nějaká data v paměti umístit pouze do určitého řádku mezipaměti, nazývá se to přímé mapování (nebo dokonce přímé mapování). Většina mezipamětí však implementuje kompromis zvaný asociativní (nebo dokonce částečně asociativní) sada. Například mezipaměť dat AMD Athlon úrovně 1 je 2-cestná nastavená asociativní , tj. konkrétní paměťové místo může být uloženo do mezipaměti ve dvou odlišných umístěních v mezipaměti dat úrovně 1.

Pokud lze každé umístění v hlavní paměti načíst do dvou různých umístění, vyvstává otázka: která? Nejčastěji používané schéma je znázorněno v diagramu na straně: nejméně významné bity indexu umístění paměti se používají jako indexy pro mezipaměť a ke každému z těchto indexů jsou přidruženy dva řádky mezipaměti. Dobrou vlastností tohoto schématu je, že popisky dat načtených do mezipaměti nesmí obsahovat tu část indexu, která je již zakódována zvoleným řádkem mezipaměti. Protože jsou tagy vyjádřeny na méně bitech, zabírají méně paměti a doba jejich zpracování je kratší.

Byla navržena jiná schémata, jako je skewed cache , kde index cesty 0 je přímý, jak je uvedeno výše, zatímco index pro cestu 1 se vypočítává pomocí hashovací funkce. Dobrá hašovací funkce má tu vlastnost, že adresy, které jsou v rozporu s přímým mapováním, mají tendenci nekolidovat při mapování na hašovací funkci, takže je méně pravděpodobné, že program bude trpět nepředvídatelně velkým počtem kolizí v důsledku hašovací funkce. přístup. Nevýhodou je dodatečné zpoždění potřebné k výpočtu výsledku hashovací funkce. Kromě toho, když je nutné načíst nový řádek a odstranit starý, může být obtížné určit, který ze stávajících řádků byl použit nejméně nedávno, protože nový řádek koliduje s různými „sadami“ řádků pro každý řádek. způsob"; ve skutečnosti se trasování LRU normálně vypočítává pro každou sadu linek.

Asociativita je kompromis. Pokud existuje deset pozic, může politika nahrazení vyplnit nový řádek, ale při hledání dat musí být zaškrtnuto všech 10 pozic. Ovládání více pozic vyžaduje více síly, plochy a času. Na druhou stranu, keše s větší asociativitou trpí menším počtem vynechaných cache (viz také níže). Pravidlem je, že zdvojnásobení asociativity má na míru zásahu přibližně stejný účinek jako zdvojnásobení velikosti mezipaměti, z jednosměrného ( přímé mapování ) na čtyřsměrné. Zvýšení asociativnosti nad 4-cestné má mnohem menší vliv na míru zásahu a obecně se používá z jiných důvodů (viz virtuální aliasing níže).

Jednou z výhod přímé mapované cache je to, že umožňuje rychlé a snadné spekulativní provádění . Jakmile je adresa vypočtena, je známo, který řádek mezipaměti může obsahovat data. To lze přečíst a procesor může pokračovat v práci s těmito daty, než dokončí kontrolu, zda štítek skutečně odpovídá požadované adrese.

Myšlenku, že procesor využívá data v cache ještě předtím, než je ověřena korespondence mezi štítkem a adresou, lze aplikovat i na asociativní cache. Podmnožinu štítku, anglicky nazývanou hint , lze použít k dočasnému výběru jednoho z řádků mezipaměti spojených s požadovanou adresou. Tato data může CPU používat paralelně, zatímco je štítek plně zkontrolován. Tato technika funguje nejlépe při použití v kontextu překladu adres, jak je vysvětleno níže.

Cache miss

Chyba mezipaměti označuje neúspěšný pokus o čtení nebo zápis části dat do mezipaměti, což má za následek mnohem delší latenci v přístupu k hlavní paměti. V případě selhání čtení z mezipaměti instrukcí musí procesor počkat ( stall ), dokud se instrukce nenačte z hlavní paměti. Selhání mezipaměti způsobené načítáním dat může být méně bolestivé, protože lze stále provádět další instrukce, které s tím nesouvisejí, pokud lze provést operaci, která vyžaduje načtení dat. Data se však často používají ihned po instrukci načtení. Poslední případ chyby mezipaměti , tedy selhání zápisu, je nejméně znepokojující, protože zápis je obvykle uložen do vyrovnávací paměti. Procesor může bezpečně pokračovat, dokud není vyrovnávací paměť plná. (Nedochází k selhání zápisu do mezipaměti instrukcí, protože jsou pouze pro čtení.)

Aby se minimalizovala míra vynechání mezipaměti , bylo provedeno mnoho analýz chování mezipaměti, abychom našli nejlepší kombinaci velikosti, asociativnosti, velikosti bloku a tak dále. Referenční sekvence paměti vytvořené srovnávacími programy jsou uloženy jako stopy adres . Další analýza simuluje mnoho různých možností implementace mezipaměti na základě těchto tras dlouhých adres . Pochopení toho, jak více proměnných mění míru přístupu do mezipaměti, může být docela matoucí. Významně přispěl Mark Hill, který rozdělil různá selhání mezipaměti do tří kategorií (známých jako „tři C“ ):

• Povinná vynechání jsou ta selhání způsobená prvním odkazem na danou věc. Velikost mezipaměti a asociativita nemají žádný vliv na počet povinných chyb . Zde může pomoci předběžné načítání, stejně jako velké velikosti bloků mezipaměti (což je typ předběžného načítání).
• Chybějící kapacita jsou taková selhání, která bude mít mezipaměť dané velikosti, bez ohledu na asociativitu nebo velikost bloku. Křivka frekvence vynechání kapacity versus velikost mezipaměti poskytuje určitou míru dočasného umístění určitého referenčního proudu.
• Vynechání konfliktu jsou taková selhání, kterým by se dalo předejít, kdyby mezipaměť předtím nevymazala data. Conflict misses by mohla být dále rozdělena na mapping misss , která jsou nevyhnutelná vzhledem k určité asociativitě, a nahrazení miss , která jsou způsobena konkrétní volbou pravidla nahrazení.

Četnost chyb vs velikost mezipaměti na celočíselné části SPEC CPU2000

Graf napravo shrnuje výkon mezipaměti pozorovaný při benchmarkech celočíselné části procesoru SPEC CPU2000, které provedli Hill a Cantin [1] . Tyto benchmarky slouží k reprezentaci typu pracovní zátěže, kterou může pracovní stanice zažít v kterýkoli daný den. V tomto grafu můžeme vidět různé účinky tří C.

Zcela vpravo, když velikost mezipaměti nabývá hodnoty „Inf“ (která, jinými slovy, má tendenci k nekonečnu), máme povinné miss . Pokud bychom chtěli vylepšit vlastnosti SpecInt2000, zvýšení velikosti cache nad 1 MB by bylo prakticky zbytečné.

Míra selhání plně asociativní mezipaměti plně představuje míru chybějících kapacit . V simulacích bylo zvoleno pravidlo nahrazení LRU: to ukazuje, že by bylo potřeba dokonalé pravidlo pro nahrazení, aby se minimalizovala frekvence vynechání kapacity , jako kdyby například věštec hledal v budoucnosti místo, kde se nenachází být použit.

Všimněte si, jak v naší aproximaci frekvence nedostatků kapacity má graf prudký pokles mezi 32 kB a 64 kB. To znamená, že benchmark má pracovní sadu přibližně 64 kB. Návrhář mezipaměti, který se dívá na tyto benchmarky, by byl silně v pokušení nastavit velikost mezipaměti těsně nad 64 kB, spíše než těsně pod tuto hodnotu. Je třeba také poznamenat, že v této simulaci nemůže žádný druh asociativnosti spustit 32KB mezipaměť stejně jako 64KB 4-cestnou, nebo dokonce přímo mapovanou 128KB.

Nakonec si všimněte, že mezi 64 kB a 1 MB je velký rozdíl mezi přímo mapovanou a plně asociativní mezipamětí. Tento rozdíl je četností konfliktů . Podle údajů z roku 2004 mají mezipaměti druhé úrovně namontované přímo na čipu procesoru tendenci zůstat v tomto rozsahu, protože malé mezipaměti jsou dostatečně rychlé na to, aby byly mezipaměti první úrovně, zatímco větší jsou příliš drahé na to, aby byly levně namontovány na samotný čip ( Itanium 2 má 9MB mezipaměť třetí úrovně, největší mezipaměť na čipu dostupná na trhu v roce 2004). Z hlediska četnosti konfliktů se zdá, že cache druhé úrovně čerpá velkou výhodu z vysoké asociativnosti.

Tato výhoda byla dobře známá na konci 80. a počátkem 90. let 20. století , kdy návrháři CPU nedokázali umístit velké mezipaměti na čipy a neměli dostatečnou šířku pásma pro implementaci vysoké asociativnosti na mezipaměti mimo čip procesoru. Byla vyzkoušena různá řešení: MIPS R8000 používal drahé vyhrazené off-chip SRAM , které zahrnovaly komparátory štítků a velké ovladače, k implementaci 4MB 4cestné asociativní vyrovnávací paměti. MIPS R10000 používal pro štítky běžné čipy SRAM. Přístup k štítkům v obou směrech vyžadoval dva cykly: pro snížení latence se R10000 pro každý přístup snažil předpovědět, který režim mezipaměti bude ten správný.

Cache hit

Zásah do mezipaměti místo toho odkazuje na úspěch procesoru při hledání adresy umístění paměti mezi různými štítky mezipaměti, které ji mohou obsahovat. V případě úspěchu může procesor číst ( Cache Read Hit ) nebo zapisovat ( Cache Write Hit ) data na řádku mezipaměti.

V případě čtecího zásahu procesor čte slovo přímo z mezipaměti bez zapojení hlavní paměti. Pokud jde o přístup k zápisu , podívejte se prosím na hloubkovou analýzu zásad mezipaměti zápisu

Překlad adres

Většina běžně používaných CPU implementuje nějaký druh virtuální paměti . V praxi každý program běžící na stroji vidí zjednodušeně svůj vlastní paměťový prostor, který obsahuje kód a data pro samotný program. Každý program ukládá vše do svého vlastního paměťového prostoru, aniž by se staral o to, co ostatní programy ve svých příslušných paměťových prostorech dělají.

Virtuální paměť vyžaduje, aby procesor přeložil virtuální adresy generované programem na fyzické adresy v hlavní paměti. Část procesoru, která provádí tento překlad, se nazývá jednotka správy paměti (MMU). MMU může rychle přistupovat k překladové tabulce prostřednictvím Translation Lookaside Buffer (TLB), což je mezipaměť mapování pro tabulku stránek operačního systému .

Překlad adres má tři důležité funkce:

• Latence: Obecně platí, že MMU zpřístupní fyzickou adresu několik cyklů poté, co je virtuální adresa vypočítána generátorem adres.
• Aliasing: Více virtuálních adres může odkazovat na stejnou fyzickou adresu. Většina procesorů zajišťuje, že všechny aktualizace jedné fyzické adresy probíhají v pořádku. Aby to bylo možné, musí procesor zajistit, aby v mezipaměti existovala vždy pouze jedna kopie každé fyzické adresy.
• Granularita: Virtuální adresní prostor je rozdělen na stránky. Například 4GB virtuální adresní prostor lze rozdělit na 1048576 4Kb stránek, z nichž na každou lze odkazovat nezávisle. Podporu stránek s proměnnou velikostí naleznete v položce virtuální paměť .

Historická poznámka: rané systémy virtuální paměti byly velmi pomalé a vyžadovaly přístup k tabulce stránek (rezidentní v paměti) před jakýmkoli plánovaným přístupem do paměti. Bez mezipaměti to snižuje rychlost přístupu do paměti stroje na polovinu. Z tohoto důvodu první hardwarová mezipaměť použitá v počítači nebyla datová nebo instrukční mezipaměť, ale místo toho TLB.

Existence fyzických a virtuálních adres vyvolává otázku, kterou z nich použít pro popisky a indexy mezipaměti. Motivací pro používání virtuálních adres je rychlost: datová mezipaměť s virtuálními indexy a štítky vylučuje MMU z načítání a používání dat z paměti. Zpoždění způsobené načítáním dat z RAM ( latence zatížení ) je zásadní pro výkon CPU: z tohoto důvodu je většina mezipamětí úrovně 1 indexována virtuálními adresami, což umožňuje MMU prohledávat TLB paralelně s načítáním dat z mezipaměti RAM.

Virtuální adresování není vždy tou nejlepší volbou: přináší například problém virtuálních aliasů , tj. cache může uchovávat hodnotu stejné fyzické adresy na více místech. Náklady na správu virtuálních aliasů rostou s velikostí mezipaměti a v důsledku toho je většina mezipamětí úrovně 2 a vyšší indexována fyzickými adresami.

Použití virtuálních adres pro štítky ( virtuální značkování ) však není běžné. Pokud by vyhledávání v TLB skončilo před vyhledáváním v mezipaměti RAM, byla by fyzická adresa k dispozici včas pro porovnání štítků a nebylo by tedy nutné virtuální značkování. Velké keše proto bývají fyzicky označeny a pouze malé keše s nízkou latencí jsou virtuálně označeny. V novějších CPU bylo virtuální značkování nahrazeno vhinty , jak je popsáno níže.

Virtuální indexování a virtuální aliasy

Typický způsob, jak procesor zajišťuje, aby virtuální aliasy fungovaly správně, je seřadit je tak, aby v jednom okamžiku mohl být v mezipaměti pouze jeden virtuální alias.

Pokaždé, když je do mezipaměti přidána nová hodnota, procesor hledá další virtuální aliasy a odstraňuje je. To se provádí pouze v případě selhání mezipaměti. Během zásahu do mezipaměti není vyžadována žádná zvláštní práce, což pomáhá udržovat rychlou cestu v mezipaměti co nejrychlejší.

Nejjednodušší způsob, jak najít aliasy, je namapovat je všechny do stejné oblasti cache. K tomu například dochází, pokud má TLB stránky o velikosti 4 kB a mezipaměť je přímo mapována na 4 kB nebo méně.

Moderní mezipaměti nejvyšší úrovně jsou mnohem větší než 4 kB, ale stránky virtuální paměti zůstaly stejné. Pokud je například mezipaměť 16KB a je virtuálně indexována, lze každou fyzickou adresu adresovat ze 4 různých míst v mezipaměti, a to pro tolik virtuálních adres. Pokud mezipaměť selže, je třeba zkontrolovat všechna čtyři umístění a zjistit, zda jejich odpovídající fyzické adresy skutečně odpovídají fyzické adrese neúspěšného přihlášení.

Tyto ovládací prvky jsou stejné, jaké používá sada asociativní mezipaměti k výběru konkrétní shody. Pokud se tedy se stránkami virtuální paměti o velikosti 4 kB používá prakticky 16KB indexovaná mezipaměť, 4-cestná sada asociativní, není potřeba žádná další práce k odstranění virtuálních aliasů v případě chybějící mezipaměti, protože kontroly již byly provedeny. .

Použijme opět AMD Athlon jako příklad: má 64KB datovou mezipaměť nejvyšší úrovně, se 4KB stránkami, 2-cestnou asociativní sadou. Když selže datová mezipaměť nejvyšší úrovně, 2 ze 16 (= 64KB / 4KB) možných virtuálních aliasů již byly zkontrolovány a k dokončení eliminace dalších virtuálních aliasů je zapotřebí sedm dalších cyklů smyčky kontroly štítků.

Virtuální značky a vhinty

Virtuální značkování je také možné. Velkou výhodou virtuálního tagu je, že u asociativních mezipamětí umožňují porovnávání štítků před provedením virtuálního překladu do fyzického. Tak jako tak,

• Kontroly konzistence a odstranění představují fyzickou adresu na akci. Hardware musí mít nějakou metodu převodu fyzické adresy na adresu mezipaměti, obecně ukládáním fyzických štítků i virtuálních štítků. Pro srovnání, fyzicky označená mezipaměť nemusí uchovávat virtuální štítky, což je jednodušší.
• Když je z TLB vymazán odkaz mezi virtuálními a fyzickými objekty, bude nutné nějakým způsobem vyprázdnit informace mezipaměti s těmito virtuálními adresami. Pokud jsou informace mezipaměti povoleny na stránkách, které nejsou mapovány TLB, bude nutné tyto informace vymazat, když se v tabulce stránek změní přístupová práva na těchto stránkách.

Operační systém může zajistit, aby v mezipaměti bylo současně uloženo více virtuálních aliasů. Operační systém to zajišťuje namáháním vybarvení stránky , které je popsáno níže. Některé nedávné RISC procesory (SPARC, RS / 6000) zvolily tento přístup. V poslední době se nepoužíval, protože náklady na hardware pro zjišťování a odstraňování virtuálních aliasů klesly, zatímco cena za složitost a výkon dokonalého softwaru pro vybarvování stránek vzrostla.

Může být užitečné rozlišit dvě funkce označování v asociativní mezipaměti: používají se k určení, který režim informační sady vybrat, a používají se k určení, zda mezipaměť selže nebo ne. Druhá funkce musí být vždy správná, ale první funkci je dovoleno hádat a občas se může stát, že odpověď bude chybná.

Některé procesory (jako například nejnovější SPARC) mají mezipaměti s virtuálními i fyzickými štítky. Virtuální štítky se používají pro výběr režimu a fyzické štítky se používají k určení středu nebo selhání. Tento typ mezipaměti upřednostňuje výhodu latence virtuální mezipaměti štítků a jednoduché softwarové rozhraní fyzické mezipaměti štítků. Podporuje však dodatečné náklady na duplicitní štítky. I během selhání procesů musí být alternativní režimy linky mezipaměti zkontrolovány na virtuální aliasy a na odstranění jakýchkoli shod.

Dodatečnou oblast (a určitou latenci) lze zmírnit tím, že místo virtuálních štítků budete uchovávat virtuální rady s informacemi o mezipaměti. Tyto rady jsou podmnožinou nebo hash virtuálního štítku a používají se k výběru režimu mezipaměti, kterým se mají načítat data a fyzické štítky. U virtuálně označené mezipaměti může docházet ke shodě virtuálních nápověd, ale k neshodě fyzického štítku, v tomto případě musí být informace v mezipaměti s odpovídající nápovědou odstraněny, aby po naplnění mezipaměti na této adrese přistupovaly do mezipaměti pouze mít shodu s jedinou nápovědou. Protože nápovědy mají méně bitů než virtuální štítky, aby je bylo možné od sebe odlišit, mezipaměť s virtuálními radami trpí více konfliktními nedostatky než virtuální mezipaměť štítků.

Snad finální redukci virtuálních nápověd najdeme v Pentiu 4 (jádra Willamette a Northwood). V těchto procesorech je virtuální nápověda ve skutečnosti pouze 2 bitová a mezipaměť je 4cestná asociativní. Hardware ve skutečnosti udržuje jednoduchou permutaci z virtuálních adres na adresy mezipaměti, takže k výběru správného ze čtyř režimů získávání není potřeba žádný CAM.

Vybarvení stránky

Fyzicky velké indexované mezipaměti (obvykle sekundární mezipaměti) narazí na problém: operační systém spíše než aplikace řídí, které stránky v mezipaměti spolu kolidují. Rozdíly v přidělování stránek z programu vedou k další úrovni rozdílů v cestách kolizí mezipaměti, což může vést k velmi velkým rozdílům ve výkonu programu. Tyto rozdíly mohou velmi ztížit získání konzistentního a opakovatelného času pro spouštění programů, což vede placené a nespokojené inženýry k tomu, aby po autorech operačního systému požadovali vyřešení problému.

Chcete-li problém pochopit, zvažte CPU s 1 MB fyzicky indexované přímo mapované mezipaměti úrovně 2 a 4 kB stránek virtuální paměti. Sekvenční fyzické stránky se mapují na sekvenční umístění v mezipaměti, dokud se po 256 stránkách cesta nevrátí k sobě. Každou fyzickou stránku můžeme označit barvou od 0 do 255, která označuje, kam v mezipaměti může jít. Umístění na fyzických stránkách s různými barvami nemůže být v mezipaměti konfliktní.

Programátor, který chce maximálně využít mezipaměť, by mohl uspořádat přístupy ke svým programům tak, aby bylo třeba najednou ukládat do mezipaměti pouze 1 MB dat, a to vše a přitom se vyhnout výpadkům kapacity. Mělo by se ale také ujistit, že přihlášení nebudou mít konfliktní selhání. Jedním ze způsobů, jak o tomto problému přemýšlet, je rozdělit virtuální stránky, které program používá, a přiřadit jim virtuální barvy stejným způsobem, jakým byly fyzické barvy dříve přiřazeny fyzickým stránkám. Programátor pak může uspořádat přístupy ke svému kódu tak, aby se dvě stránky se stejnou virtuální barvou nepoužívaly současně. O těchto optimalizacích existuje rozsáhlá literatura (např . Loop nest optimization ), většinou pocházející z komunity High Performance Computing (HPC).

Koncept spočívá v tom, že zatímco všechny stránky, které se v daný okamžik používají, mohou mít různé virtuální barvy, některé mohou mít stejnou fyzickou barvu. Ve skutečnosti, pokud operační systém přiřazuje fyzické stránky virtuálním stránkám náhodným a jednotným způsobem, velmi pravděpodobné, že některé stránky mají stejnou fyzickou barvu, a proto se pozice z těchto stránek v mezipaměti shodují (toto je narozeninový paradox ).

Řešením je nechat se operační systém pokusit přiřadit různě barevné fyzické stránky různým virtuálním barvám, což je technika zvaná vybarvování stránek . Ačkoli skutečné mapování barev mezi virtuálními a fyzickými je pro výkon systému irelevantní, lichá mapování je obtížné vysledovat a mají malé výhody, takže většina přístupů k vybarvování stránek se jednoduše snaží zachovat barvu fyzických a virtuálních stránek stejným způsobem.

Pokud operační systém může zaručit, že každá fyzická stránka odkazuje na jednu virtuální barvu, pak neexistují žádné virtuální aliasy a procesor může používat virtuálně indexované mezipaměti bez nutnosti dalších kontrol virtuálních aliasů během správy selhání. Alternativně může operační systém vymazat stránku z mezipaměti, i když se změní z jedné virtuální barvy na druhou. Jak již bylo zmíněno dříve, tento přístup byl používán některými nedávnými návrhy SPARC a RC / 6000.

Hierarchie mezipaměti v moderním procesoru

Moderní procesory mají na čipu více mezipamětí, se kterými mohou komunikovat. K rozvoji současné hierarchie mezipaměti vedly zejména dva důvody.

Specializované keše

Prvním důvodem je, že zřetězené procesory přistupují k paměti z více bodů v kanálu: získávání instrukcí, překlad virtuální adresy do fyzické a získávání dat. Pro jednoduchý příklad: Classic RISC Pipeline . Přirozenou implementací je použití různých fyzických mezipamětí pro každý z těchto bodů, takže není třeba programovat žádné fyzické zdroje pro obsluhu dvou bodů v potrubí. Ačkoli potrubí přirozeně končí nejméně třemi samostatnými mezipaměti (instrukce, TLB a data), každá se specializuje na určitou roli.

Mezipaměť obětí

Mezipaměť obětí je mezipaměť používaná k udržení bloků odstraněných z mezipaměti CPU kvůli konfliktu nebo nedostatku kapacity. Mezipaměť obětí je umístěna mezi primární mezipamětí a základní pamětí a uchovává pouze bloky odstraněné po chybě. Tato technika se používá ke snížení trestu za selhání mezipaměti, protože se může stát, že data, která jsou v mezipaměti oběti, jsou požádána o nějaký čas později, a pak místo prohlášení o chybě a přechodu do paměti k načtení těchto dat mezipaměť obětí se zkontroluje a použijí se data, která v ní stále jsou.

Původní mezipaměť obětí na HP PA7200 byla malá, plně asociativní mezipaměť. Pozdější procesory, jako je AMD Athlon , Athlon XP a Athlon 64 , používají velmi velkou sekundární mezipaměť jako mezipaměť obětí, aby se zabránilo opakování ukládání kontextu na primární mezipaměti.

Trace cache

Jedním z nejextrémnějších příkladů specializace mezipaměti je mezipaměť trasování používaná v mikroprocesorech Pentium 4 . Mezipaměť trasování je mechanismus pro zvýšení šířky pásma načítání instrukcí ukládáním tras instrukcí, které již byly uloženy. Mechanismus poprvé navrhli Eric Rotenberg , Steve Bennett a Jim Smith ve svém článku z roku 1996: " Trace Cache: Přístup s nízkou latencí k načítání instrukcí s vysokou šířkou pásma. "

Mezipaměť trasování ukládá instrukce i poté, co byly provedeny, nebo když jsou staženy. Obecně se instrukce přidávají do mezipaměti trasování ve skupinách, které představují jak základní jednotlivé bloky, tak dynamické trasování instrukcí. Základní blok se skládá ze skupiny nevětvených (nerozdělených) instrukcí, které končí větví. Dynamické trasování ("trasování cesty" nebo "trasování cesty") sestává pouze z příkazů, jejichž výsledek je skutečně použit, a eliminuje následující příkazy, které se větví (protože nejsou provedeny); dynamická stopa může být zřetězením násobků základních bloků. To umožňuje jednotce pro vyhledávání instrukcí získat několik základních bloků bez obav z větvení do toku provádění.

Řádky trasování jsou uloženy v mezipaměti trasování na základě programového čítače prvního příkazu trasování a sady předpovědí větvení. To umožňuje ukládání různých tras cest začínajících stejnou adresou, z nichž každá představuje různé výsledky větvení. Ve fázi ukládání instrukcí potrubí instrukcí je aktuální čítač programu spolu se sadou předpovědí větvení zkontrolován v mezipaměti trasování, zda neobsahuje zásah. Pokud dojde k zásahu, je k dispozici trasovací řádek pro načtení toho, který z nich nemusí pro tyto příkazy přecházet do běžné mezipaměti nebo paměti. mezipaměť trasování pokračuje v zásobování načítací jednotky, dokud trasovací linka neskončí nebo dokud není v kanálu chybná předpověď . Pokud dojde k poruše, začne se vytvářet nová stopa. Výhodou oproti normálním mezipaměti kódu je, že všechny instrukce následující po větvi, které jsou nepodmíněné nebo předpovězené jako nenásledované, nejsou ukládány do mezipaměti: výsledkem je, že se nevytvářejí žádné "bubliny" nepoužitého kódu, které plýtvají místem.

Trace cache se také používají v procesorech, jako je Intel Pentium 4 k ukládání již dekódovaných mikro operací nebo překladů složitých x86 instrukcí, takže při příštím požadavku na stejnou instrukci již nemusí být dekódována.

Myšlenka trasovací mezipaměti spočívá v tom, že v procesorech CISC, které interně používají instrukce RISC , jako je Pentium 4, je dekódování instrukcí extrémně nákladná operace a její výsledek by měl být plně využit. Použití mezipaměti trasování místo normální mezipaměti má právě tuto výhodu: není nutné dekódovat příkaz, který se již objevil během provádění programu.

Trace cache se v poslední době kvůli některým nedostatkům moc netěší. První je, že mnoho instrukcí RISC je přeloženo do jediné instrukce CISC v jediném hodinovém cyklu a instrukcí, které vyžadují více hodinových cyklů k převedení do více instrukcí RISC, je relativně málo a málo časté, takže skutečný přínos trasovací mezipaměti je omezený. . K tomu se přidává skutečnost, že v případě architektury Intel mají instrukce CISC obecně proměnnou délku mezi 1 a 6 bajty (mezi 8 a 48 bity), zatímco všechny interně používané instrukce RISC mají pevnou délku 118 bitů. . Proto při stejné velikosti obsahuje mezipaměť trasování mnohem méně instrukcí než normální mezipaměť. Tyto nevýhody vedly Intel k tomu, že nepoužíval trace cache ve svých nejnovějších architekturách: Intel Core a Intel Core 2 .

Viz text Smith, Rotenberg a Bennettův papír . Získáno 30. listopadu 2019 (archivováno z originálu 3. dubna 2008) . v Citeseeru .

Víceúrovňová mezipaměť

Druhým důvodem je zásadní kompromis mezi latencí mezipaměti a návštěvností. Větší mezipaměti jsou pomalejší a mají lepší míru návštěvnosti. Aby se tento kompromis zlepšil , mnoho systémů používá více úrovní mezipaměti, přičemž malé a rychlé mezipaměti se opírají o větší a pomalejší mezipaměti. Jak se rozdíl v latenci mezi hlavní pamětí a rychlejšími mezipaměti zvětšil, některé procesory začaly používat také tři úrovně mezipaměti na čipu. Například v roce 2003 se Itanium II začalo dodávat se 6MB unifikovanou on-chip cache úrovně 3. Řada IBM Power 4 má 256 MB mezipaměti úrovně 3 mimo čip, sdílenou mezi několika procesory.

Víceúrovňové cache obecně fungují tak, že nejprve zkontrolují cache úrovně 1; pokud dojde k zásahu, procesor běží vysokou rychlostí. Pokud menší mezipaměť "selže", pak se zkontroluje větší a tak dále, dokud není nutné přistupovat k hlavní paměti.

Víceúrovňové cache zavádějí nový model rozhodování. Například u některých procesorů (jako je Intel Pentium 2 , 3 a 4 a také u mnoha RISC ) mohou být data v mezipaměti L1 také v mezipaměti L2. Tyto keše jsou označovány jako inkluzivní. Jiné procesory (např. AMD Athlon ) mají exkluzivní mezipaměti, kde je zaručeno, že data budou maximálně v jedné z mezipamětí L1 nebo L2.

Výhodou exkluzivních mezipamětí je, že ukládají více dat. Tato výhoda se zvyšuje s většími cache (implementace Intel x86 nejsou). Výhodou inkluzivních mezipamětí je to, že když externí zařízení nebo jiné procesory ve víceprocesorovém systému chtějí z procesoru odstranit linku mezipaměti, musí procesor nechat zkontrolovat pouze mezipaměť L2. V hierarchiích mezipaměti, které nepoužívají zahrnutí, musí být zkontrolovány také mezipaměti L1. Existuje korelace mezi asociativitou L1 a L2 cache: pokud L2 cache nemají alespoň tolik režimů jako všechny L1 dohromady, skutečná asociativita L1 cache je omezená.

Další výhodou inkluzivních mezipamětí je, že větší keše mohou používat větší řádky mezipaměti, což snižuje velikost štítků sekundárních mezipamětí. Pokud je sekundární vyrovnávací paměť řádově větší než primární a data mezipaměti jsou řádově větší než štítky mezipaměti, lze tyto uložené štítky dat porovnat s přírůstkovou oblastí potřebnou k uložení dat. Mezipaměť L1 a L2.

Jak již bylo zmíněno dříve, velké počítače mají někdy další mezipaměť mezi L2 a hlavní pamětí nazývanou L3 cache. Tato mezipaměť je obecně implementována na čipu odděleném od CPU a stejně jako v roce 2004 má kapacitu 2 až 256 MB. Vybudování těchto mezipamětí bude stát hodně přes 1 000 USD a jejich výhody budou záviset na přístupových cestách aplikací. High-end x86 pracovní stanice a servery jsou nyní k dispozici s možností L3 cache.

A konečně, na druhé straně paměťové hierarchie lze soubor CPU Register považovat za nejmenší, nejrychlejší mezipaměť v systému, přičemž speciální funkce je volána softwarem - obvykle kompilátorem, protože přiděluje registry, které musí obsahovat hodnoty. načteno z hlavní paměti.

Příklad: architektura AMD K8

Pro ilustraci specializace i víceúrovňové mezipaměti uvádíme hierarchii mezipaměti procesoru AMD Athlon 64 , jehož základní implementace je známá jako architektura K8 .

Příklad hierarchie, K8

K8 má 4 specializované mezipaměti: mezipaměť instrukcí, mezipaměť instrukcí TLB , mezipaměť dat a mezipaměť dat TLB. Každá z těchto keší je specializovaná:

1. Mezipaměť instrukcí udržuje 64 bajtové řádkové kopie paměti a načítá 16 bajtů za cyklus. Každý bajt v této mezipaměti je uložen v 10 bitech místo 8, přičemž extra bity označují hranice instrukcí (Toto je příklad předkódování). Mezipaměť má spíše ochranu paritou než ECC , protože parita je menší a jakákoli poškozená data lze nahradit čerstvými daty z paměti (která má vždy aktualizovanou kopii pokynů).

1. Instrukce TLB uchovává kopii informací v tabulce stránek (PTE). Každý cyklus načítání instrukce má svou virtuální adresu přeloženou prostřednictvím tohoto TLB na fyzickou. Každá informace má v paměti 4 i 8 bajtů. Každý TLB je rozdělen do dvou sekcí, z nichž jedna udržuje 4KB mapování PTE a druhá 4MB nebo 2MB mapování PTE. Poddělení umožňuje jednoduchý obvod pro plně asociativní srovnání v každé sekci. Operační systém mapuje různé části virtuálního adresového prostoru s různými velikostmi PTE.

1. Datový TLB má dvě různé kopie, které obsahují stejné informace. Dvě kopie umožňují dva přístupy k datům pro každý cyklus pro převod virtuálních adres na fyzické. Stejně jako instrukce TLB je tato TLB rozdělena na dva typy informací.

1. Datová mezipaměť udržuje kopie paměti o 64 bajtech řádků. Je rozdělena do 8 bank (každá ukládá 8 KB dat) a dokáže načíst dvě 8bajtová data za cyklus, pokud jsou tato data v různých bankách. Existují dvě kopie štítků, protože každý 64bajtový řádek je rozložen ve všech 8 bankách. Každá kopie štítku spravuje jeden ze dvou přístupů za cyklus.

K8 má také víceúrovňové ukládání do mezipaměti. Existují instrukční a datové TLB druhé úrovně, které ukládají pouze 4KB PTE mapování. Instrukční a datové mezipaměti a různé TLB mohou být naplněny velkou unifikovanou mezipamětí úrovně 2. Tato mezipaměť je exkluzivní pro data a instrukce L1, což znamená, že jakákoli 8bajtová linka může být umístěna v jedné z mezipaměti instrukce L1, mezipaměť dat L1 nebo mezipaměť L2. Je však možné, že řádek v mezipaměti dat má PTE, který se také nachází v jedné z mezipamětí TLB – operační systém je zodpovědný za udržování konzistentnosti TLB tím, že stahuje jejich části, když se obnovuje tabulka stránek v paměti.

K8 ukládá informace, které se nikdy neukládají do paměti – prediktivní informace. Tyto keše nejsou na předchozím diagramu znázorněny. Jak je pro tuto třídu CPU obvyklé, K8 má poměrně složitou predikci větvení s tabulkami, které pomáhají předpovídat, které cesty se ubírají, a dalšími tabulkami, které předpovídají cestu a cíle skoku. Některé z těchto informací jsou spojeny s instrukcemi v mezipaměti instrukcí L1 i sjednocené L2.

K8 používá zajímavý mechanismus pro ukládání predikčních informací s instrukcemi do sekundární mezipaměti. Řádky v sekundární mezipaměti jsou chráněny před neúmyslným poškozením dat (např . zasažení částice alfa přes ECC nebo paritu , v závislosti na tom, zda byly tyto řádky odstraněny z mezipaměti dat nebo instrukcí. parity zabírá méně bitů než ECC, řádky z mezipaměti instrukcí zbylo několik bitů. Tyto bity se používají k výpočtu předpovědí cesty spojených s pokyny. Konečným výsledkem je, že prediktor cesty má velkou historickou tabulku, takže má lepší přesnost.

Další hierarchie

Jiné procesory mají jiné typy prediktorů. (např. prediktor bypassu mezi úložištěm a načtením v DEC Alpha 21264) a různé další specializované prediktory jsou snadno představitelné pro integraci do budoucích procesorů.

Tyto prediktory jsou mezipaměti v tom smyslu, že ukládají informace, jejichž výpočet je nákladný. Některé terminologie používané v diskuzi o prediktorech jsou stejné jako pro cache (označované jako hity v prediktoru cesty), ale prediktory obecně nejsou váženy jako součást hierarchie cache.

K8 udržuje instrukce a data cache konzistentní v hardwaru, což znamená, že uložení do jedné instrukce těsně po uložení instrukce změní další instrukci. Jiné procesory, jako jsou procesory z rodiny Alpha a MPS, jsou založeny na softwaru, aby byly mezipaměti instrukcí konzistentní. Není zaručeno, že úložiště budou vidět v proudu instrukcí, pokud program nezavolá volbu operačního systému pro zajištění konzistence. Cílem je ušetřit hardwarovou složitost za předpokladu, že samo- modifikační kód je vzácný.

Hierarchie mezipaměti se rozšiřuje, pokud vezmeme v úvahu software i hardware. Registrový soubor v jádře procesoru lze považovat za velmi malou, rychlou mezipaměť, která narazí, selže a zaplní kompilátor předem předpovídá. (Viz zejména optimalizace Loop nest .) Registrové soubory mají také někdy hierarchii: Cray-1 (cca 1976) měl 8 skalárních registrů a 8 adresových registrů, které byly obecně použitelné, měl také 64 skalárních registrů a 64 adres typu "B" registrů. Registry typu "B" mohly být načteny rychleji než ty v hlavní paměti, protože Cray-1 neměl datovou mezipaměť.

Implementace

Protože čtení mezipaměti jsou poměrně běžné operace, které zaberou více než jeden cyklus, opakování od načtení instrukce k samotné instrukci bývá nejkritičtější cestou v dobrém návrhu procesoru, takže data v této cestě jsou ztracena. jak je to možné. V důsledku toho je mezipaměť L1 nejcitlivější komponentou na čipu.

Nejjednodušší cache je virtuálně indexovaná přímo mapovaná cache. Virtuální adresa je vypočítána pomocí sčítačky, nejvýznamnější část adresy je extrahována a použita k indexování paměti SRAM, která vrací uložená data. Data jsou bajtově zarovnána v bajtovém posuvníku a odtud jsou předána do další operace. Není potřeba žádná kontrola štítků ve vnitřní smyčce – štítky ve skutečnosti ani není třeba číst. Později v kanálu, ale před skutečným načtením příkazu, musí být značka pro načtená data načtena a zkontrolována s virtuální adresou, aby se ujistil, že došlo k přístupu do mezipaměti. Pokud se to nezdaří, mezipaměť se aktualizuje o požadovaný řádek a kanál se restartuje.

Asociativní mezipaměť je mnohem komplikovanější, protože některé datové prvky musí být načteny, aby bylo možné určit, který bod mezipaměti vybrat, sada-asociativní mezipaměť N-way úrovně 1 obvykle čte paralelně všech možných N štítků a N dat a poté vybere údaje spojené s odpovídajícím štítkem. Mezipaměti úrovně 2 někdy šetří energii tím, že si nejprve přečtou štítek, takže se z paměti SRAM přečte pouze jeden kus dat.

Cesta ke čtení pro dvoucestnou asociativní mezipaměť

Diagram vpravo slouží k objasnění použití různých adresových polí. Diagram ukazuje SRAM, indexování a multiplexování pro virtuálně označenou a virtuálně indexovanou 4KB, 2cestnou set-asociativní mezipaměť s 64B řádky, 32b široké čtení a 32b virtuální adresa.

Protože mezipaměť je 4KB a má 64B řádků, je v mezipaměti pouze 64 řádků a čteme dva najednou ze štítku SRAM, který má 32 řádků, každý s několika 21bitovými štítky. Ačkoli lze k indexování štítků a dat SRAM použít libovolný bit 31 až 6 funkcí virtuální adresy, je snazší použít nejméně významné bity.

Podobně, protože mezipaměť je 4KB a má čtecí cestu 4B a čte dva režimy pro každou adresu, data SRAM mají 512 řádků o šířce 8 bajtů.

Modernější mezipaměť by mohla být 16KB, 4-cestná set-asociativní, virtuálně indexovaná, virtuálně naznačená a fyzicky značená, s 32B řádky, 32b čteními a 36bitovými fyzickými adresami. Výskyt čtecích cest pro tyto typy keší se hodně podobá výše uvedené cestě. Místo štítků se čtou vhinty a porovnávají se s podmnožinou virtuálních adres. Později v kanálu je virtuální adresa přeložena na fyzickou adresu pomocí TLB a fyzický štítek je přečten (pouze jeden, protože vhint poskytuje způsob čtení mezipaměti). Nakonec je fyzická adresa porovnána s adresou štítku, aby se zjistilo, zda došlo ke shodě.

Některé implementace SPARC zlepšily rychlost svých mezipamětí L1 o několik zpoždění tím, že zhroutily sčítačku virtuální adresy v dekodérech SRAM.

Související položky

• Mezipaměti
• Vyrovnávací paměť
• Konzistence mezipaměti
• procesor

Další projekty

Jiné projekty

• Wikimedia Commons

• Wikimedia Commons obsahuje obrázky nebo jiné soubory v mezipaměti CPU

Externí odkazy

• ( EN ) Evaluating Associativity in CPU Caches - Hill and Smith - 1989 - Představuje kapacitu, konflikt a povinnou klasifikaci.
• ( EN ) Výkon mezipaměti pro SPEC CPU2000 Benchmarks . - Hill and Cantin - 2003 - Tento referenční dokument byl několikrát aktualizován. Má důkladné a přehledné prezentované výsledky simulace pro přiměřeně širokou sadu benchmarků a organizací cache.
• ( EN ) Memory Hierarchy in Cache-Based Systems ( PDF ) (archivováno z originálu 15. září 2009) . , Ruud van der Pas, 2002, Sun Microsystems, je pěkným úvodním článkem k ukládání do mezipaměti CPU.
• ( EN ) A Cache Primer ( PDF ) (z originálu archivováno 25. července 2008) . Paul Genua, PE, 2004, Freescale Semiconductor, další úvodní článek.