Jak jste na tom s pamětí? (6)

Na první pohled je jasné, že zatímco význam cash (v podobě hotových peněz) obecně neustále klesá, s pamětí cache je to úplně naopak. I z tohoto důvodu si tento druh paměti zaslouží pozornost v našem seriálu o technologiích. Zároveň je to již poslední část

Je libo Cache nebo Cash?

Na první pohled je jasné, že zatímco význam cash (v podobě hotových peněz) obecně neustále klesá, s pamětí cache je to úplně naopak. I z tohoto důvodu si tento druh paměti zaslouží pozornost v našem seriálu o technologiích. Zároveň je to již poslední část povídání o pamětech.

Dělení cache pamětí:

Pokud si vzpomínáte, o cache paměti jsme mluvili již v souvislosti s procesory. Je to v podstatě rychlá vyrovnávací paměť mezi nějakým rychlým zařízením (např. procesorem) a pomalejším zařízením (např. operační pamětí, harddiskem apod.). V dnešních počítačích se běžně můžeme setkat se dvěma druhy cache pamětí:

  • externí (sekundární, L2) cache:

Externí cache paměť je paměť, která je umístěna mezi pomalejší operační pamětí a rychlým procesorem. Tato paměť je vyrobena jako rychlá paměť SRAM (viz minulé části) a slouží jako vyrovnávací paměť u počítačů s výkonným procesorem, které by byly bez ní operační pamětí velmi zpomalovány. První externí cache paměti se objevují u počítačů s procesorem 80386. Jejich kapacita je 32 kB popř. 64 kB. S výkonnějšími procesory se postupně zvyšuje i kapacita externích cache pamětí na 128 kB, 256 kB, 512 kB a v současné době existují i paměti L2 s kapacitou 1MB. Externí cache paměť je zpravidla osazena přímo na základní desce počítače (výjimku tvoří procesory Pentium Pro a Pentium II, které mají externí cache paměť integrovánu v pouzdře procesoru - na jednom křemíku). Její činnost je řízena řadičem cache paměti.

  • interní (primární, L1) cache:

Interní cache paměť je paměť, která slouží k vyrovnání rychlosti velmi výkonných procesorů a pomalejších pamětí. Tento typ cache paměti je integrován přímo na čipu procesoru a je také realizován pomocí paměti typu SRAM. Interní cache paměť se objevuje poprvé u procesoru 80486 s kapacitou 8 kB. Takovýto procesor ale musí mít v sobě integrován také řadič interní cache paměti pro řízení její činnosti. Obecně jsou cache paměti poměrně drahé, ale u L1 to platí dvojnásob, proto nebývá větší než 64kB.

Práce cache paměti vychází ze skutečnosti, že program má tendenci se při své práci určitou dobu zdržovat na určitém místě paměti, a to jak při zpracování instrukcí, tak při načítání (resp. zapisování) dat z (resp. do) paměti. Je-li požadována nějaká informace z paměti, je nejdříve hledána v cache paměti (interní, pokud existuje, a následně v externí). Pokud požadovaná informace není přítomna v žádné z cache pamětí, je zavedena přímo z operační paměti. Kromě momentálně požadované informace se však do cache paměti zavede celý blok paměti, takže je velká pravděpodobnost, že následně požadované informace již budou v cache paměti přítomny. Pokud dojde k zaplnění cache paměti a je potřeba zavést další blok, je nutné, aby některý z bloků cache paměť opustil. Nejčastěji se k tomuto používá tzv. LRU (Least Recently Used) algoritmu, tj. algoritmu, který vyřadí nejdéle nepoužívaný blok.

Cache paměti bývají organizovány jako tzv. asociativní paměti. Asociativní paměti jsou tvořeny tabulkou (tabulkami), která obsahuje vždy sloupec, v němž jsou umístěny tzv. tagy (klíče), podle kterých se v asociativní paměti vyhledává. Dále jsou v tabulce umístěna data, která paměť uchovává, a popř. další informace nutné k zajištění správné funkce paměti. Např.:

  • informace o platnosti (neplatnosti) uložených dat
  • informace pro realizaci LRU algoritmu
  • informace protokolu MESI (Modified Exclusive Shared Invalid), který zajišťuje synchronizaci dat v cache pamětech v případě, že cache pamětí je v počítači více (u interních cache pamětí v okamžiku, kdy počítač obsahuje více procesorů).

Při přístupu do cache paměti je nutné zadat adresu, na které jsou uložena požadovaná data. Tato adresa je buď celá, nebo jí může část považovaná za tag, který se porovnává s tagy v cache paměti.

Konstrukce cache paměti

Cache paměti jsou konstruovány jedním ze tří způsobů:

  • plně asociativní:

U plně asociativní cache paměti je celá adresa, ze které se budou číst data (popř. na kterou se budou data zapisovat), brána jako tag. Tento tag je přiveden na vstup komparátorů (zařízení realizující porovnání dvou hodnot) společně s tagem v daném řádku tabulky. Pokud je některý z tagů v tabulce shodný se zadaným tagem na vstupu, ohlásí odpovídající komparátor shodu a to znamená, že požadovaná informace je v cache paměti přítomna a je možné ji použít. Pokud všechny komparátory signalizují neshodu, je to známka toho, že požadovaná informace v cache paměti není a je nutné ji zavést odjinud (externí cache paměť, operační paměť).

Tento způsob cache paměti má ale své nevýhody:

    1. Vždy je potřeba velké množství komparátorů.
    2. Vzhledem k tomu, že se musí v každém řádku tabulky uchovávat celý tag, musí mít cache paměť velkou kapacitu, do které se tyto tagy ukládají a kterou není možné využít k uchovávání dat.

Z těchto důvodů se plně asociativní paměti prakticky nepoužívají. :-)

  • n-cestně asociativní:

N-cestně asociativní paměti pracují tak, že je zadaná adresa nejprve rozdělena na dvě části viz obrázek, pro n = 2):

    • tag

    • adresa třídy

Poté je adresa třídy přivedena na n dekodérů (zařízení, které na základě vstupní hodnoty vybere jeden ze svých výstupů, na který umístí hodnotu logická 1, a na ostatní výstupy umístí hodnotu logická 0), které v každé tabulce vyberou jeden řádek. Z těchto řádků se potom vezmou příslušné tagy a komparátorem se porovnají se zadaným tagem. Podobně jako u plně asociativních cache pamětí pokud jeden z komparátorů signalizuje shodu, je informace v cache paměti přítomna. V opačném případě je nezbytné informaci hledat jinde.

N-cestně asociativní paměti částečně eliminují nevýhody plně asociativních cache pamětí a v současnosti jsou nejpoužívanějším typem cache pamětí.

  • přímo mapovaná:

Přímo mapovaná cache paměť je speciální případ n-cestně asociativní cache paměti pro n = 1. Zadaná adresa je opět rozdělena na tag a adresu třídy. Adresa třídy je přivedena na vstup dekodéru, který podle ní vybere jeden řádek v tabulce. Tag na tomto řádku je následně porovnán se zadaným tagem, čímž se rozhodne o přítomnosti resp. nepřítomnosti informace v cache paměti. Přímo mapovaná cache ve srovnání s n-cestně asociativní cache pamětí vykazuje nižší výkon, a proto její použití není dnes příliš časté.

Konkrétním příkladem cache paměti může být například interní cache paměť procesoru 80486, která je realizována jako 4-cestně asociativní cache paměť.

Adresa je rozdělena na tři části:

  • Tag - horních 21 bitů
  • Adresa třídy - 7 bitů => 128 řádků tabulky
  • Slabika - dolní 4 bity

Adresa třídy je přivedena na dekodér, který vybere jeden řádek. Zadaný tag je dále komparátorem porovnán proti 4 tagům ve vybraném řádku. Pokud jeden z komparátorů ohlásí shodu, provede se výběr dat v datové části paměti. Datová část obsahuje v každém sloupci 16B, ze kterých je pomocí dolních 4 bitů zadané adresy vybrán jeden požadovaný byte.

Každý řádek cache paměti ještě obsahuje jeden bit, který říká, zda informace v daném sloupci jsou platné, a 3 bity pro realizaci tzv. pseudo-LRU algoritmu. Zde myslím vystačíme pouze s tím, že tento algoritmus je poněkud zdokonalenou verzí LRU algoritmu. Pomocí tří bitů totiž nelze vždy určit nejdéle nepoužívaný blok cache paměti. Tento algoritmus je však jednoduchý a rychlý. Díky tomu poskytuje dostatečný výkon.

Nakonec si ještě povíme, podle jakého kritéria se dají paměti cache také dělit. Existují totiž dva způsoby zápisu dat do cache paměti:

  • write-through: cache paměti, u kterých v případě zápisu procesoru do cache paměti dochází okamžitě i k zápisu do operační paměti. Procesor tak obsluhuje jen zápis a o další osud dat se stará cache paměť.
  • write-back: cache paměti, u nichž jsou data zapisována do operační paměti až ve chvíli, kdy je to třeba, a nikoliv okamžitě při jejich změně. K zápisu dat do operační paměti tedy dochází např. v okamžiku, kdy je cache zcela zaplněna a je třeba do ní umístit nová data. Tento způsob práce cache paměti vykazuje oproti předešlému způsobu vyšší výkon.

Tímto bychom ukončili kapitolu věnovanou pamětem. Z původně krátkého tématu se nakonec stalo jedno z nejobsáhlejších, a tak vám raději nebudu slibovat, jak dlouhé budou příští díly. Pouze vás navnadím na další téma seriálu o technologiích - bude o DVDčku.