Mezipaměti počítače Cache paměť - mezipaměť Hlavní paměť procesoru je typu DRAM a je pomalá. Proto se mezi pomalou hlavní paměť a procesor vkládá menší, ale rychlá vyrovnávací (cache) paměť SRAM. Rychlost cache paměti nespočívá jen v použití rychlejší technologie SRAM, ale také v tom, že je menší (je jednodušší proces dekódování adresy). 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í (zapisování) dat z (do) paměti - tzv. princip lokality Mezipaměť (cache) je vlastně velmi rychlým paměťovým zásobníkem (typ SRAM), určeným k dočasnému ukládání dat, které procesor potřebuje nebo bude potřebovat s velkou pravděpodobností. Díky tomu je procesor schopen načíst data podstatně rychleji než přímo z hlavní paměti. V současnosti se v počítačích používají dvě až tři úrovně mezipamětí: L1 cache – mezipaměť první úrovně L2 cache – mezipaměť druhé úrovně L3 cache – mezipaměť třetí úrovně L1 cache integrována do procesoru velikost 8-64 KB pro ukládání právě využívané či potřebné pracovní sady dat a kódu pracuje stejnou rychlostí jako procesor
L1 procesor
instrukce
L1
cache
L2 cache
L3 cache
data
hlavní paměť HDD
L2 cache, L3 cache součást procesoru nebo základní desky velikost L2:64-512 KB, L3:1-4MB mezistupeň mezi L1 a hlavní pamětí, obsahuje data, která procesor přímo nepoužívá, ale pravděpodobně bude potřebovat pracuje stejnou rychlostí jako procesor nebo základní deska – stále rychlejší než čtení přímo z hlavní paměti
-1-
Druhy cache pamětí Podle způsobu organizace rozlišujeme následující tři druhy cache paměti: Cache s přímým zobrazením Asociativní cache Cache s omezenou asociativitou (cache se stupněm asociativity n)
Procesor Blok
L2 (L3) cache
L1 cache
Operační paměť
Blok
Cache s přímým zobrazením Hlavní paměť 2n bytů, rozdělena do bloků 4B Cache 2p řádků (slotů) Do slotu lze uložit obsah jednoho bloku, tj. 4B dat Tag slouží k identifikaci bloku, který je v slotu uložen Pro přiřazení řádku cache paměti i bloku paměti k se používá funkce i = k modulo M p , kde M = 2 je počet řádků cache tabulky. Počet řádků tabulky se tedy volí tak, aby byl mocninou 2. Do řádky 0 cache paměti budou tedy ukládány bloky: Do řádky 1 budou ukládány bloky: Do řádky j budou ukládány bloky: atd.
0, M , 2M, . . . 1 , M + 1 , 2M + 1 , . . . j , M + j , 2M + j , . . .
Určitý blok je vždy uložen do stejného řádku cache tabulky. Je-li M = 2p , pak p méně významných bitů čísla bloku určuje číslo řádku cache tabulky, ve kterém je blok uložen.
-2-
Číslo bloku má n – 2 bitů. Bloky, které jsou ukládány do stejné řádky, se liší v n – 2 – p nejvyšších bitech čísla bloku. Obsah těchto bitů je ukládán do cache paměti jako tag. Bit platnosti udává, zda je obsah slotu platný Hlavní paměť Adresa 0
Číslo bloku
1 2 3 4 Řádek
0
Cache Bit platnosti
1
Tag
Obsah bloku
Řádek 0 1 2
2p–1
n
2 –1
Adresa Číslo bloku
Byte
n – 2 – p bitů
p bitů
tag
2 bity
Adresa řádky v cache
Adresa
Tag
Data
Dekodér
Tag
Slot
Komparátor Data
-3-
Inf.
Asociativní cache U asociativní cache paměti může být blok uložen do libovolné řádky cache tabulky. Jako tag proto musí sloužit celé číslo bloku. Při hledání konkrétního bloku v cache je nutno porovnat tag ve všech řádcích cache tabulky. To je obtížný úkol a je řešitelný pouze dost složitými obvody, které vyžadují velké množství dalších hradel. Proto se konstruují asociativní paměti jen s menší kapacitou.
Adresa
Tag
Komparátor
Tag
Data
Inf.
Komparátor Komparátor
Data Adresa Tag
Byte
22
2
Při výběru řádku (slotu) pro uložení bloku je možné se řídit jednou z následujících strategií: Výběr nejméně používané řádky (least freaquently used strategy) Výběr nejdéle nepoužívané řádky (least recently used strategy) Výběr řádky, která je obsazena nejdéle (FIFO strategy) Náhodný výběr řádku (random strategy) První tři strategie vyžadují, aby v každé řádce byla položka, do které řídící obvody ukládají informaci o využití řádky. Náhodná strategie to nevyžaduje a nejjednodušeji se proto implementuje. Experimenty ukázaly, že náhodná strategie výběru řádky je jen o málo méně efektivní než ostatní strategie.
-4-
Cache se stupněm associativity n Pokud má cache asociativitu n, skládá se z n tabulek se stejným počtem řádků, umístěných vedle sebe. Řádek výsledné tabulky tvoří skupina řádků původních tabulek (skupina, angl. set). Původní řádky, ze kterých se skupina skládá, nazveme pro odlišení sloty. Každý slot skupiny obsahuje bit platnosti, tag a data (tj. obsah jednoho bloku). Příklad: Cache se stupněm asociativity n = 2:
Bit platn.
Tag
Obsah bloku
Bit platn.
Tag
Obsah bloku
0 1 2
7FFF Adresa Tag
Skupina
7
15
Byte 2
Má-li výsledná tabulka M skupin, ukládá se k-tý blok do jednoho ze slotů skupiny i , kde i = k modulo M. Při hledání bloku v cache paměti, řídící obvody nejdříve podle adresy vyberou skupinu, ve které může být blok uložen. Blok může být uložen jen v jedné skupině a výběr této skupiny je přímý. Hledání bloku v rámci skupiny pak řídící obvody provedou asociativně.
-5-
Adresa
Skupina Tag
Data Inf.
Dekodér
Data Inf.
Dekodér
Tag
Tag
Komparátor
Komparátor Data
Data Data
Cache se stupněm asociativity n je mezistupněm mezi cache pamětí s přímým výběrem a asociativní pamětí. Pokud je asociativita n = 1, jedná se o cache s přímým zobrazením. Pokud je počet skupin M = 1 (tj . výsledná tabulka má jen jeden řádek či skupinu), jedná se o asociativní cache. Příklad Fyzická adresa paměti je n = 24 bitů. Paměťová buňka má velikost 1B. Velikost hlavní paměti je 16 MB. Bloky paměti, které se přenášejí mezi cache pamětí a hlavní pamětí, mají velikost 4B. Paměť je tedy rozdělena na 4M bloků. Kapacita cache paměti je 256 kB. Proto současně v ní může být umístěno 256k/4 bloků, tj. 64k bloků. Cache tabulka má 64k řádek s adresami 0,1 ,2 , . . . FFFF. Po zapnutí procesoru je obsah cache paměti náhodný. Proto se nejdříve nastaví všechny bity platnosti na 0. Předpokládejme nejprve, že pro uložení bloků hlavní paměti do paměti cache se používá přímé zobrazení. Do jednotlivých řádků cache tabulky budou uloženy následující bloky hlavní paměti.
-6-
0
Ukládané bloky (hexadecimálně) 0 , 1 00 00 , . . . , 3F 00 00
1
1 , 1 00 01 , . . . , 3F 00 01
2
2 , 1 00 02 , . . . , 3F 00 02
FFFF
FF FF, 1 FF FF, . . . 3FF FF
Bit platnosti
Obsah bloku
Tag
Adresa Tag
Řádek cache paměti
6
16
Byte 2
Postupně je tabulka zaplňována bloky, které procesor potřebuje ke své činnosti a které proto přepisuje do cache paměti – 17 00 00, 1A 00 02, 1 FF FF
0 1 2
1 0 1
17
Uložený blok (hexadecimálně) 17 00 00
1A
1A 00 02
FFFF
1
1
1 FF FF
Bit platnosti
Tag
Obsah bloku
-7-
Do cache paměti byly dále postupně uloženy následující bloky: 37 00 01 , 27 00 00 , 23 FF FF, B 00 00
1 2
1 1 1
B 37
Uložený blok (hexadecimálně) B 00 00 37 00 01
1A
1A 00 02
FFFF
1
23
23 FF FF
Bit platnosti 0
Tag
Obsah bloku
Nyní předpokládejme plně asociativní cache. Do cache paměti byly uloženy následující bloky: 27 00 00 , 23 FF FF, B 00 00, 1A 00 02
1 2
1 1 1
1A 00 02 23 FF FF
Uložený blok (hexadecimálně) 1A 00 02 23 FF FF
27 00 00
27 00 00
FFFF
1
B 00 00
B 00 00
Bit platnosti 0
Tag
Adresa
Obsah bloku
Tag
Byte
22
2
Pro uložení bloku do cache paměti lze použít libovolný řádek cache tabulky.
-8-
Dále předpokládejme cache se stupněm asociativity n = 2. Do paměti cache opět uložíme bloky: 27 00 00 , 23 FF FF, B 00 00, 1A 00 02 Stanovíme číslo skupiny (15 bitů) a hodnotu tag (7 bitů) pro jednotlivé bloky: 2
7
0
0
0
0
1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4E 00 00 Tag
Skupina
2 3 F F F F 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 47 7F FF Tag
0
B
Skupina
0
0
0
0
0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 00 00 Tag
1
A
Skupina
0
0
0
2
0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 34 00 02 Tag
Skupina
Uložení bloků v tabulce cache bude následující: Bit platn.
Tag
1
4E
0
Obsah bloku
Bit platn.
Tag
Obsah bloku
Uložený blok (hexadecimálně)
1
16
27 00 00, B 00 00
1
34
1A 00 02
1 2
0
7FFF
1
47
23 FF FF
0
Adresa Tag 7
Skupina 15
Výběr slotu v rámci skupiny je libovolný (náhodný).
-9-
Byte 2
Spolupráce procesor-cache paměť Při čtení z hlavní paměti (HP) procesor její obsah zapíše do cache Při zápisu do HP používá tyto základní strategie: Okamžitý zápis (write through strategy) Opožděný zápis (write back strategy) Okamžitý zápis je jednodušší strategie. Procesor zapíše nový obsah paměťového místa do hlavní paměti i do cache paměti. Při každé strojové instrukci zápisu do paměti se tedy provádí i zápis do hlavní paměti. Tento způsob řešení tedy znamená značné zatížení systémové sběrnice. Opožděný zápis - Procesor zapíše nový obsah paměťového místa pouze do cache paměti. V řádce cache tabulky zaznamená do bitu UPDATE, že došlo ke změně obsahu bloku. Nastavení bitu UPDATE znamená, že obsah řádky cache tabulky již nadále není platný. Předtím než řídící obvody cache paměti zapíší do této řádky cache tabulky obsah nového bloku, musí zajistit přepis obsahu původního bloku do hlavní paměti. Výhodou tohoto způsobu zápisu je menší zátěž systémové sběrnice.
Koherence cache pamětí V multiprocesorovém systému, každý procesor má obvykle vlastní cache. Procesory pracují nezávisle na sobě a sdílejí společnou paměť. Musí být zajištěno, že procesory čtou z hlavní paměti stejný obsah - koherence cache pamětí. Adaptéry dnešních počítačů používají přímý přístup do paměti (DMA) a pracují nezávisle na procesoru. Proto se může stát, že adaptér pozmění v hlavní paměti obsah paměťového místa a vnitřní cache procesoru nebude obsahovat platná data.
Řešení koherence podle typu zápisu Okamžitý zápis (write through strategy) Řešení koherence cache pamětí je jednodušší v případě použití této strategie. Spočívá v tom, že řadiče cache pamětí musí sledovat provoz na systémové sběrnici. Pokud zjistí, že do hlavní paměti byl zapsán blok, jehož kopii mají v cache paměti, musí svoji kopii označit jako neplatnou (tj. nastavit bit platnosti v řádku, kde je kopie uložena na 0).
- 10 -
Opožděný zápis (write back strategy) Byla navržena celá řada protokolů, které problém koherence řeší. PENTIUM například používá protokol MESI K realizaci protokolu jsou tedy třeba čtyři bity a sice: – bit modified (M) (bit změny) – bit excluded (E) (bit vyloučení) – bit shared (S) (bit sdílení) – bit invalid (I) (bit platnosti) Název protokolu MESI je složen ze zkratek těchto bitů.
- 11 -
