Vyrovnávací paměti (cache)

Obsah

1. Vyrovnávací paměti (cache)
2. Hierarchie pamětí
3. Systémy bez vyrovnávacích pamětí
4. Vyrovnávací paměti na platformě x86
5. Princip práce vyrovnávacích pamětí
6. Kritéria vyrovnávací paměti a jejich vliv na efektivitu
7. Literatura a odkazy na Internetu

1. Vyrovnávací paměti (cache)

V předchozích částech tohoto seriálu jsme si popsali činnost mikroprocesorů při zpracovávání programu rozloženého do jednotlivých strojových instrukcí i funkci operační paměti vytvořené většinou pomocí technologie DRAM, tj. mřížky paměťových jednobitových buněk založených na jednom tranzistoru s připojeným kondenzátorem. Vzhledem k tomu, že rychlost mikroprocesorů roste rychleji než rychlost dynamických pamětí (především při náhodném přístupu), bylo nutné do původně jednoduchého systému mikroprocesor–operační paměť (základ von Neumannovy architektury) zavést takzvané vyrovnávací paměti (cache memory). Ty na jednu stranu statisticky zvyšují pravděpodobnost, že mikroprocesor bude pracovat na své maximální rychlosti v případě, že jsou data přítomna ve vyrovnávací paměti, na stranu druhou umožňují, aby se data mezi operační pamětí a vyrovnávací pamětí přenášela v blocích, což je na současných technologiích operačních pamětí (SDRAM, DDR, DDR2 atd.) mnohem rychlejší než náhodný přístup.

Obrázek 1: Postupný růst rychlostí dynamických pamětí pro tři různé technologie (SDRAM, DDR, DDR2, RDRAM a XDR)

Způsob uspořádání pamětí, především operační paměti, do značné míry ovlivňuje celou architekturu počítače, která v mnoha případech z různých důvodů odporuje původní von Neumannově architektuře. Idea hierarchického uspořádání pamětí je poměrně jednoduchá a vychází z cenových a výkonnostních kritérií (v neposlední řadě se také musí dbát na požadovaný elektrický příkon počítače, protože prakticky všechna dodaná energie se v něm přeměňuje na teplo, které je zapotřebí rozptýlit do okolí). V počítači je umístěno více technologických typů paměťových součástek, od těch nejrychlejších (a také v přepočtu na cenu jednoho bitu nejdražších) pamětí s velmi malou kapacitou až po velkokapacitní média, například pevné disky tvořící část virtuální paměti, u nichž je cena za bit sice nejnižší, ale také tomu odpovídá jejich rychlost, která je o několik řádů nižší, než je tomu u pamětí, které stojí v celé hierarchii o jeden či více stupňů výše.

Obrázek 2: Von Neumannova architektura ve své klasické podobě

2. Hierarchie pamětí

Typická hierarchie současných osobních počítačů i serverů může být následující:

1. Na vrcholku celé hierarchické struktury pamětí se nachází velmi rychlá paměť tvořená pracovními registry umístěnými přímo na mikroprocesoru. Tato paměť má v porovnání s dalšími paměťmi poměrně malou kapacitu (například se u typických RISC procesorů jedná o 32 registrů po 32 bitech = 32×32 = 1024 bitů = 128 bytů), ovšem na druhou stranu jsou pracovní registry přímo zapojeny do ostatních struktur mikroprocesoru a čtení i zápis je nejrychlejší – většinou odpovídá jednomu taktu, který je v případě použití zřetězeného zpracování instrukcí využit i nějakou další operací. Přílišné zvyšování počtu pracovních registrů není vhodné, například z důvodu rychlé reakce na přerušení (obsahy registrů se musí uschovat a posléze zase obnovit) či rychlého přepínání úloh. Jednou z metod pro částečné obejití tohoto omezení je využití stínových registrů (shadow registers). Pro adresování registrů se využívají k tomu určené adresní části instrukcí, které jsou mnohdy velmi krátké (například pro jednoznačný výběr jednoho z 32 registrů postačí pouhých pět bitů).
2. Na druhém místě hierarchie se nachází vyrovnávací paměť (cache) první úrovně, označovaná jako Level 1 cache. U některých starších architektur mikroprocesorů se tato paměť nacházela na samostatném čipu, tj. odděleně od mikroprocesoru, dnes se však (i díky mnohem vyšší integraci) tato paměť téměř vždy nachází přímo na čipu obsahujícím samotný mikroprocesor. Jedním z důvodů je snaha o co nejrychlejší přístupy do vyrovnávací paměti první úrovně. Zajímavé je, že z programátorského hlediska je tato paměť téměř neviditelná (většinou až na několik speciálních instrukcí, které však běží v takzvaném ringu 0 a jsou tedy dostupné pouze z jádra operačního systému), programátor tedy nemůže určit, která data mají být umístěna ve vyrovnávací paměti a která v paměti operační. Tato úroveň vyrovnávací paměti bývá velmi často rozdělena na samostatně pracující paměť určenou pro program (I-cache) a data (D-cache), čímž se do jisté míry čistě von Neumannovská architektura stává architekturou Harvardskou.
3. Na třetím místě hierarchie bývá umístěna vyrovnávací paměť druhé úrovně, označovaná názvem Level 2 cache či Second level cache. Tato paměť má vyšší kapacitu než vyrovnávací paměť první úrovně, ovšem její rychlost může být nižší (například může být taktována externí frekvencí paměťové sběrnice a nikoli interní frekvencí mikroprocesoru, což snižuje cenu celého systému). Podobně jako Level 1 cache, i Level 2 cache může být rozdělena na část určenou pro data a část určenou pro operační kódy instrukcí, ovšem na mnoha architekturách je tato paměť unifikovaná. Vzhledem ke své větší kapacitě (a také kvůli zvýšení výtěžnosti) může být vyrovnávací paměť druhé úrovně umístěna v samostatném čipu/čipech, mnohdy na malém zásuvném modulu spolu s mikroprocesorem a dalšími podpůrnými obvody. Co se týče výrobní technologie, bývá Level 2 cache založena buď na MOS SRAM (statické paměti se šestitranzisto­rovými paměťovými buňkami) nebo na bipolární technologii (při extrémních požadavcích na rychlost se používaly i bistabilní klopné obvody ECL).
4. Vlastní operační paměť se nachází až na čtvrtém místě v hierarchii. Na rozdíl od obou úrovní vyrovnávacích pamětí je operační paměť přímo či (dnes častěji) nepřímo adresovatelná a tedy plně přístupná programátorům. Operační paměť je z pohledu mikroprocesoru velmi pomalá, především při náhodném přístupu, což je také jeden z hlavních důvodů použití vyrovnávacích pamětí. Typickou technologií operačních pamětí je mřížka paměťových buněk tvořených tranzistorem a kondenzátorem (resp. prvkem s určitou kapacitou), tj. jedná se o dynamickou paměť, která se musí v pravidelných obnovovat, většinou pomocí takzvaného skrytého obnovení (hidden refresh), jenž je prováděno bez zásahu mikroprocesoru i programátora.
5. Vzhledem k tomu, že všechny mikroprocesory určené pro desktopy a servery podporují takzvanou virtuální paměť, pokračuje hierarchie pamětí ještě níže, protože se operační paměť rozšiřuje o několik řádů pomalejší a současně o několik řádů objemnější pevné disky. Z hlediska programátora tvořícího běžné aplikace (přesněji řečeno programy neběžící s privilegii jádra operačního systému) je viditelná takzvaná virtuální paměť tvořená jak operační pamětí, tak i částí kapacity pevného disku (či Flash disku atd.). V praxi může existence virtuální paměti znamenat, že některé bloky paměti nejsou přítomny přímo v operační paměti, ale jsou po určitý čas uloženy na pevném disku. Při pokusu o přístupu k tomuto bloku (ať již pro čtení či zápis) je daný blok načten do volného místa operační paměti a zpřístupněn programu (popř. se volné místo vytvoří odložením jiného bloku na pevný disk). Aplikační programátor se o tyto činnosti nemusí starat, jsou to pro něj transparentní operace – z jeho pohledu je paměť lineární sekvencí adres, která může být maximálně rozdělena na několika částí (část určená pro program, část pro data, část pro zásobník).

Obrázek 3: PA RISC firmy Hewlett-Packard (mikroprocesor spolu s podpůrnými obvody a vyrovnávacími pamětmi druhé úrovně)

3. Systémy bez vyrovnávacích pamětí

Na starších architekturách, například osmibitových domácích počítačích, byla celá hierarchie paměti zredukována na pouhé dvě úrovně. První úroveň opět tvořily pracovní registry mikroprocesoru, těch však bývalo z dnešního pohledu relativně málo, například v případě mikroprocesoru 6502 se jednalo o tři osmibitové registry a u Intel 8080 o osm registrů. Druhou úroveň tvořila dynamická operační paměť, která však bývala obnovována za asistence mikroprocesoru a většinou i speciálního podprogramu (neexistovala zde tedy možnost provádění skrytých obnovení). Mikroprocesor 6502 je typickým zástupcem procesorů vytvořených v době, kdy býval přístup do dynamické paměti rychlejší než doba provedení typické instrukce a současně se větší počet pracovních registrů negativně podílel na ceně mikroprocesoru (nehledě na další komplikace, například při vyvolání přerušení). Z tohoto důvodu 6502 obsahuje, jak již bylo řečeno, pouhé tři pracovní registry (akumulátor a dva index registry), zato však má instrukce (přesněji řečeno, adresní režimy) pro rychlou práci s prvními 256 byty operační paměti, nazvané zero page. U šestnáctibitových mikroprocesorů se však úloha obrátila, protože provádění instrukcí začalo být rychlejší než přístup do dynamické paměti (DRAM) a právě zde se (z pohledu osobních počítačů poprvé) objevují vyrovnávací paměti.

Obrázek 4: Ve slavném počítači ZX-81 vyrovnávací paměti nenajdeme

4. Vyrovnávací paměti na platformě x86

Už počítače s mikroprocesory 386 podporovaly vyrovnávací paměti; jednalo se ovšem o paměti umístěné mimo procesor, které používaly strategii write-through a byly společné pro data i programový kód. Na platformě x86 došlo poprvé k rozdělení vyrovnávací paměti na část určenou pro program a část určenou pro data až u prvních mikroprocesorů Intel Pentium, které měly tuto vyrovnávací paměť (první úrovně) umístěnou přímo na čipu. Předchůdce Pentií, tj. mikroprocesor 486 měl na čipu také vyrovnávací paměť, ovšem s poměrně malou kapacitou, která u původních mikroprocesorů firmy Intel dosahovala kapacity pouhých osmi kilobytů (pomalejší strategie write-through) a u nejnovějších modelů pak šestnácti kilobytů (ovšem s využitím strategie write-back). Externí vyrovnávací paměť (druhé úrovně) bylo možné nainstalovat do základní desky, kde se nacházely příslušné patice DIL – u mnoha základních desek se však místo skutečných vyrovnávacích pamětí v těchto paticích nacházely „prázdné“ čipy, které neprováděly žádnou činnost.

Obrázek 5: Vícejádrový systém s vyrovnávacími paměťmi úrovně 1 rozdělenými pro jednotlivá jádra a společnou vyrovnávací pamětí druhé úrovně

5. Princip práce vyrovnávacích pamětí

Vyrovnávací paměť je fyzicky umístěna na datové sběrnici mezi mikroprocesorem a operační pamětí. Paměť je rozdělena do bloků o konstantní velikosti, které bývají nazývané cache line. Velikosti těchto bloků jsou různé, v praxi se pohybují od osmi bytů do jednoho kilobytu. Například vyrovnávací paměť o kapacitě 512 kB a velikosti bloku 32 bytů obsahuje celkem 16384 bloků. Operační paměť je taktéž logicky rozdělena na bloky o stejné velikosti, těchto bloků je však mnohem více, než bloků ve vyrovnávací paměti (pro operační paměť o kapacitě 64 MB se jedná o 2097152 bloků). Z tohoto poměru také vyplývá, že zdaleka ne všechny bloky operační paměti mohou být „kešovány“ ve vyrovnávací paměti (poměr bloků je 1:128). Právě na strategii výběru bloků (a také na tom, jakým způsobem mohou být bloky do vyrovnávací paměti mapovány) je závislá efektivita vyrovnávací paměti. Ke každému bloku umístěnému ve vyrovnávací paměti jsou přidány ještě další důležité informace, především takzvaný tag, což je index odpovídajícího bloku v operační paměti (v podstatě se jedná o hodnotu ukazatele/adresy podělenou délkou bloku).

Ve chvíli, kdy mikroprocesor potřebuje přečíst nějaká data (tj. obsah paměťové buňky na nějaké adrese, může se jednat jak o operační kód strojové instrukce, tak i o skutečná zpracovávaná data), provede se kontrola, zda se tato data nachází ve vyrovnávací paměti, tj. zda nějaký blok obsahuje požadovanou adresu. Pokud ano (nastane takzvaný cache hit), jsou data z vyrovnávací paměti přečtena a předána mikroprocesoru a to mnohem rychleji, než v případě čtení dat z operační paměti. Ovšem ve chvíli, kdy potřebná data nejsou nalezena ve vyrovnávací paměti (tzv. cache miss), musí do ní být přenesena. Na základě alokační strategie (popsané v následující části tohoto seriálu) se uvolní blok ve vyrovnávací paměti a data jsou do tohoto bloku načtena (přenáší se vždy celý blok, na což je dobré myslet při návrhu datových struktur i způsobu zpracování) a dále se pokračuje v přenosu do mikroprocesoru.

Zápis dat (většinou) probíhá poněkud složitějším způsobem. V případě, že je blok, ve kterém se nachází zapisovaná adresa, uložen ve vyrovnávací paměti, jsou data do vyrovnávací paměti skutečně zapsána a celý blok se označí bitem dirty (špinavý). Takový blok nemůže být zahozen, ale musí být v případě potřeby jeho uvolnění nejdříve uložen zpět do operační paměti, aby byla zajištěna koherence dat. Tato strategie se označuje write-back. Dříve se používala jednodušší metoda řízení vyrovnávací paměti, která je nazvaná write-through. Při použití této metody se data zapisují jak do vyrovnávací paměti (předpokládá se, že se data budou opětovně číst) tak současně „propisují“ i do hlavní paměti, což je sice pomalejší, ale řízení je naopak jednodušší (nemusí se testovat příznak dirty apod.). U některých počítačů, například u PC s procesorem 486 bylo možné mezi oběma strategiemi řízení vyrovnávací paměti volit (v BIOSu), přičemž rychlejší strategie write-back mohla vést k nestabilitě systému.

6. Kritéria vyrovnávací paměti a jejich vliv na efektivitu

Při návrhu struktury, především informační kapacity, rychlosti a strategie řízení vyrovnávacích pamětí v počítači i při jejich použití v praxi (například při nastavování parametrů jádra operačního systému) je nutné sledovat kritérium, kterým se vyjadřuje efektivnost použití vyrovnávacích pamětí. Jedná se o takzvaný součinitel výpadků bloků, který se vypočte z podílu neuspokojivých přístupů do vyrovnávací paměti (tj. přístupů, které ve svém důsledku vedou k nutnosti čtení či zápisu bloku z operační paměti či do operační paměti) a celkového počtu přístupů. Na začátku práce počítače je vyrovnávací paměť prázdná a proto se součinitel výpadků bloku rovná jedné – každý pokus o přístup do vyrovnávací paměti vede k nutnosti načtení celého bloku z operační paměti či označení daného bloku příznakem dirty (tímto bitovým příznakem je označený blok určený pro zápis do operační paměti, příznak značí nesoulad mezi obsahem bloku ve vyrovnávací paměti a korespondujícího bloku v hlavní paměti).

S rostoucím počtem přístupů do paměti, zejména při opakovaném volání stejných programů či práci se stále stejnými daty (v obou případech se uplatňuje známé pravidlo 80–20), hodnota součinitele výpadků bloků postupně klesá. Rychlost poklesu a konkrétní průměrná hodnota součinitele výpadků bloků po ustálení závisí na poměru kapacit vyrovnávací a operační paměti i na tom, jakým způsobem je implementováno řízení vyrovnávací paměti (strategie), na struktuře zpracovávaných dat i na tom, jakým způsobem jsou aplikace i vlastní operační systém naprogramovány (například nevhodně napsaná programová smyčka může program zpomalit až o několik řádů). V praxi lze dosáhnout hodnot součinitele výpadků bloků menších než 0,05, tj. jen v pěti procentech případů dochází k výpadku bloku a v devadesáti pěti procentech vyrovnávací paměť skutečně poslouží ke svému účelu.

Další důležitou hodnotou při návrhu či práci s vyrovnávacími paměťmi je takzvaná efektivnost vyrovnávací paměti. Tu lze vypočítat pomocí vzorce (jedná se o poněkud zjednodušený vztah, ovšem pro prvotní orientaci v problému dostačuje):

T_ef = (1-SVB)×T_V + (1+x)×SVB×T_H

kde:

• T_ef je efektivní (zdánlivá) vybavovací doba paměti, jak se jeví programátorům i uživatelům
• T_V je vybavovací doba vyrovnávací paměti
• T_H je vybavovací doba operační paměti
• SVB je hodnota součinitele výpadku bloků
• x je podíl bloků změněných ve vyrovnávací paměti

Pokud bude například vyrovnávací paměť vytvořena pomocí technologie desetkrát rychlejší, než je rychlost operační paměti, hodnota SVB bude 0,05 (pět procent) a hodnota x 0,25 (jedna čtvrtina), zkrátí se průměrná vybavovací doba dat na šestinu původní hodnoty, což může být uspokojivý výsledek. Dále uvažme, že kapacita vyrovnávací paměti je rovna jedné tisícině kapacity operační paměti (to zhruba odpovídá dnešnímu stavu) a cena za bit rychlé vyrovnávací paměti je desetinásobná oproti běžné DRAM. Zavedením vyrovnávací paměti se cena paměťového subsystému jako celku zvýšila o pouhé jedno procento (10×1/1000×100), zatímco rychlost je šestkrát vyšší. Právě zde tkví důvod velké popularity vyrovnávacích pamětí – zvýšení výkonu za relativně malé náklady.

Obrázek 6: Datová a instrukční vyrovnávací paměť první úrovně u systému s jádrem MIPS

7. Literatura a odkazy na Internetu

1. Pavel Valášek, Roman Loskot: Polovodičové paměti,
   BEN – Technická literatura, Praha 1998, ISBN-80–86056–18-X
2. Budínský J.: Polovodičové paměti a jejich použití,
   SNTL, Praha 1977
3. Budínský J.: Polovodičové paměti – Názvosloví a definice,
   TESLA VÚST, Praha 1980
4. Janů K.: Paměti a řadiče – část I.,
   ČSVTS, Knižnice mikroprocesorová technika, Praha 1982
5. Great Microprocessors of the Past and Present (V 13.0.0)
6. Cache Mapping and Associativity
7. CPU cache
8. Cache algorithms