Hierarchická paměťUpravit

Hierarchická paměť je hardwarová optimalizace, která využívá výhod prostorové a časové lokality a může být použita na několika úrovních paměťové hierarchie. Stránkování samozřejmě těží z časové a prostorové lokality. Jednoduchým příkladem využití časové lokality je mezipaměť, protože se jedná o speciálně navrženou, rychlejší, ale menší oblast paměti, která se obvykle používá k uchovávání nedávno odkazovaných dat a dat v blízkosti nedávno odkazovaných dat, což může vést k potenciálnímu zvýšení výkonu.

Datové prvky v mezipaměti nemusí nutně odpovídat datovým prvkům, které jsou prostorově blízko v hlavní paměti; datové prvky se však do mezipaměti dostávají po jednom řádku. To znamená, že prostorová lokalizace je opět důležitá: pokud je odkazováno na jeden prvek, bude do mezipaměti přeneseno i několik sousedních prvků. A konečně časová lokálnost hraje roli na nejnižší úrovni, protože výsledky, které jsou odkazovány velmi blízko sebe, mohou být uchovávány ve strojových registrech. Některé programovací jazyky (například C) umožňují programátorovi navrhnout, aby určité proměnné byly uchovávány v registrech.

Lokalita dat je typickým rysem odkazování na paměť u běžných programů (i když existuje mnoho nepravidelných vzorů přístupu do paměti). Díky ní je hierarchické uspořádání paměti výhodné. V počítačích je paměť rozdělena do hierarchie za účelem zrychlení přístupu k datům. Nižší úrovně paměťové hierarchie bývají pomalejší, ale větší. Program tedy dosáhne vyššího výkonu, pokud využívá paměť v době, kdy je uložena v mezipaměti na vyšších úrovních paměťové hierarchie, a vyhne se tomu, aby do vyšších úrovní hierarchie vnášel další data, která by vytlačila data, jež budou v budoucnu krátce použita. To je ideální stav, kterého někdy nelze dosáhnout.

Typická hierarchie paměti (přístupové doby a velikosti mezipaměti jsou přibližné typické hodnoty použité od roku 2013 pro účely diskuse; skutečné hodnoty a skutečné počty úrovní v hierarchii se liší):

• Registry procesoru (8-256 registrů) – okamžitý přístup, s rychlostí nejvnitřnějšího jádra procesoru
• L1 cache procesoru (32 KiB až 512 KiB) – rychlý přístup, s rychlostí nejvnitřnější paměťové sběrnice, kterou vlastní výhradně každé jádro
• L2 cache procesoru (128 KiB až 24 MiB) – o něco pomalejší přístup, s rychlostí paměťové sběrnice sdílené mezi dvojicemi jader
• L3 cache CPU (2 MiB až 32 MiB) – ještě pomalejší přístup, s rychlostí paměťové sběrnice sdílené mezi ještě více jader téhož procesoru
• Hlavní fyzická paměť (RAM) (256 MiB až 64 GiB) – pomalý přístup, jehož rychlost je omezena prostorovými vzdálenostmi a obecnými hardwarovými rozhraními mezi procesorem a paměťovými moduly na základní desce
• Disk (virtuální paměť, souborový systém) (1 GiB až 256 TiB) – velmi pomalý, kvůli užšímu (v šířce bitů), fyzicky mnohem delšímu datovému kanálu mezi základní deskou počítače a diskovými zařízeními, a kvůli cizímu softwarovému protokolu potřebnému nad pomalým hardwarovým rozhraním
• Vzdálená paměť (jiné počítače nebo cloud) (prakticky neomezená) – rychlost se pohybuje od velmi pomalé po extrémně pomalou

Moderní počítače mají tendenci číst bloky nižší paměti do další úrovně paměťové hierarchie. Pokud se tím vytlačí použitá paměť, operační systém se snaží předpovědět, ke kterým datům se bude přistupovat nejméně (nebo nejpozději), a přesune je níže v paměťové hierarchii. Algoritmy předvídání bývají jednoduché, aby se snížila hardwarová náročnost, i když se stávají poněkud složitějšími.

Násobení maticUpravit

Běžným příkladem je násobení matic:

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

Přepnutím pořadí smyček pro j a k se zrychlení při násobení velkých matic stává dramatickým, přinejmenším pro jazyky, které umisťují souvislé prvky pole do poslední dimenze. Matematický výsledek se tím nezmění, ale zvýší se efektivita. V tomto případě „velké“ znamená přibližně více než 100 000 prvků v každé matici nebo dostatek adresovatelné paměti, takže se matice nevejdou do L1 a L2 cache.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

Důvodem tohoto zrychlení je, že v prvním případě je čtení A v cache (protože index k je souvislá, poslední dimenze), ale B ne, takže na B je penalizace za chybění cache. C je irelevantní, protože může být vytažen z vnitřní smyčky — proměnná smyčky je tam k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

V druhém případě je čtení i zápis C v cache, čtení B je v cache a čtení A může být vytažen z vnitřní smyčky.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Druhý příklad tedy nemá ve vnitřní smyčce žádný postih za zmeškání mezipaměti, zatímco první příklad má postih za zmeškání mezipaměti.

Na procesoru z roku 2014 je druhý případ přibližně pětkrát rychlejší než první případ, je-li zapsán v jazyce C a zkompilován pomocí gcc -O3. (Pečlivé prozkoumání rozebraného kódu ukazuje, že v prvním případě GCC používá instrukce SIMD a ve druhém případě ne, ale postih za cache je mnohem horší než zisk SIMD)

Temporální lokálnost lze ve výše uvedeném příkladu zlepšit také použitím techniky zvané blokování. Větší matici lze rozdělit na rovnoměrně velké dílčí matice, takže na menší bloky lze odkazovat (násobit je) několikrát, zatímco jsou v paměti.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

Časová lokálnost výše uvedeného řešení je zajištěna tím, že blok lze použít několikrát, než se přesune dál, takže se méně často přesouvá do paměti a z paměti. Prostorová lokálnost se zlepšuje, protože prvky s po sobě jdoucími paměťovými adresami mají tendenci být vytahovány nahoru v paměťové hierarchii společně.