Algoritmus bez paměti cache - Cache-oblivious algorithm
Při práci na počítači je algoritmus bez paměti mezipaměti (nebo algoritmus transcendentní mezipaměti) algoritmus navržený tak, aby využíval výhody mezipaměti procesoru, aniž by měl velikost mezipaměti (nebo délku řádků mezipaměti atd.) Jako explicitní parametr. Optimální cache-zapomíná algoritmus je cache-zapomíná algoritmus, který používá mezipaměti optimálně (v asymptotické smyslu, ignoruje konstantní faktory). Algoritmus bez paměti cache je tedy navržen tak, aby dobře fungoval bez úprav na více počítačích s různými velikostmi mezipaměti nebo v hierarchii paměti s různými úrovněmi mezipaměti s různými velikostmi. Algoritmy, které zapomínají na mezipaměť, jsou v kontrastu s explicitním blokováním , jako v případě optimalizace smyčky , která problém explicitně rozdělí na bloky, které jsou pro danou mezipaměť optimálně dimenzovány.
Optimální cache-zapomíná algoritmy jsou známé pro násobení matic , maticové provedení , třídění , a několik dalších problémů. Některé obecnější algoritmy, například Cooley – Tukey FFT , při určitých volbách parametrů optimálně zapomínají na mezipaměť. Protože jsou tyto algoritmy optimální pouze v asymptotickém smyslu (ignorujíc konstantní faktory), může být nutné další ladění specifické pro stroj, aby se dosáhlo téměř optimálního výkonu v absolutním smyslu. Cílem algoritmů bez paměti cache je snížit množství takového ladění, které je vyžadováno.
Algoritmus bez paměti cache obvykle pracuje s rekurzivním algoritmem rozděl a panuj , kde je problém rozdělen na menší a menší podproblémy. Nakonec jeden dosáhne podproblémové velikosti, která se vejde do mezipaměti, bez ohledu na velikost mezipaměti. Například optimální násobení matice zapomenuté z mezipaměti se získá rekurzivním rozdělením každé matice na čtyři dílčí matice, které mají být vynásobeny, vynásobením dílčích matic způsobem první hloubky . Při ladění pro konkrétní počítač lze použít hybridní algoritmus, který používá blokování vyladěné pro konkrétní velikosti mezipaměti na nejnižší úrovni, ale jinak používá algoritmus bez paměti mezipaměti.
Dějiny
Myšlenku (a název) na algoritmy zapomínající na mezipaměť vytvořil Charles E. Leiserson již v roce 1996 a poprvé publikoval Harald Prokop ve své diplomové práci na Massachusettském technologickém institutu v roce 1999. Předchůdců bylo mnoho, typicky analyzovali konkrétní problémy ; tyto jsou podrobně diskutovány ve Frigo et al. 1999. Mezi rané příklady patří Singleton 1969 pro rekurzivní Fast Fourierovu transformaci, podobné myšlenky v Aggarwal et al. 1987, Frigo 1996 pro maticové násobení a dekompozici LU a Todd Veldhuizen 1996 pro maticové algoritmy v knihovně Blitz ++ .
Idealizovaný model mezipaměti
Algoritmy zapomínající na mezipaměť se obvykle analyzují pomocí idealizovaného modelu mezipaměti, někdy nazývaného model zapomínající na mezipaměť . Tento model je mnohem snazší analyzovat než vlastnosti skutečné mezipaměti (které mají komplikovanou asociativitu, zásady nahrazování atd.), Ale v mnoha případech je prokazatelně v rámci konstantního faktoru realističtějšího výkonu mezipaměti. Liší se od modelu externí paměti, protože algoritmy zapomínající na mezipaměť neznají velikost bloku ani velikost mezipaměti .
Zejména model bez paměti cache je abstraktní stroj (tj. Teoretický model výpočtu ). Je podobný modelu stroje RAM, který nahrazuje nekonečnou pásku Turingova stroje nekonečným polem. Ke každému umístění v poli lze přistupovat v čase, podobně jako v paměti s náhodným přístupem na skutečném počítači. Na rozdíl od modelu stroje RAM také zavádí mezipaměť: druhou úroveň úložiště mezi RAM a CPU. Další rozdíly mezi těmito dvěma modely jsou uvedeny níže. V modelu bez paměti cache:
- Paměť je rozdělena na bloky objektů.
- Z mezipaměti lze nyní obsluhovat zátěž nebo úložiště mezi hlavní pamětí a registrem CPU.
- Pokud nelze z mezipaměti obsluhovat zatížení nebo úložiště, nazývá se to vynechání mezipaměti .
- Při vynechání mezipaměti dojde k načtení jednoho bloku z hlavní paměti do mezipaměti. Totiž, pokud se CPU pokusí přistupovat ke slovu a je to řádek obsahující , pak je načten do mezipaměti. Pokud byla mezipaměť dříve plná, bude také vypuzen řádek (viz zásady pro výměnu níže).
- Cache obsahuje objekty, kde . Toto je také známé jako předpoklad vysoké mezipaměti .
- Mezipaměť je plně asociativní: každý řádek lze načíst do libovolného umístění v mezipaměti.
- Zásady nahrazování jsou optimální. Jinými slovy se předpokládá, že mezipaměti je během provádění algoritmu přidělena celá sekvence přístupů do paměti. Pokud potřebuje vystěhovat linku v čase , prozkoumá její posloupnost budoucích požadavků a vystěhuje linku, ke které se v budoucnosti přistupuje nejdále. To lze v praxi napodobit pomocí zásady Nejméně nedávno použité , která se ukazuje být v rámci malého konstantního faktoru optimální strategie nahrazování offline
Abychom změřili složitost algoritmu, který se spouští v rámci modelu bez paměti cache, měříme počet chyb mezipaměti, které algoritmus zaznamenal. Protože model zachycuje skutečnost, že přístup k prvkům v mezipaměti je mnohem rychlejší než přístup k věcem v hlavní paměti , doba běhu algoritmu je definována pouze počtem přenosů paměti mezi mezipamětí a hlavní pamětí. Je to podobné jako u modelu externí paměti , který má všechny výše uvedené funkce, ale algoritmy bez paměti cache jsou nezávislé na parametrech mezipaměti ( a ). Výhodou takového algoritmu je, že to, co je efektivní na stroji, který zapomíná na mezipaměť, bude pravděpodobně účinný na mnoha skutečných strojích, aniž by doladil konkrétní parametry konkrétního stroje. U mnoha problémů bude optimální algoritmus zapomínající na mezipaměť také optimální pro počítač s více než dvěma úrovněmi hierarchie paměti .
Příklady
Nejjednodušší algoritmus zapomínající na mezipaměť představený ve Frigo et al. je operace transpozice matice mimo místo ( pro transpozici byly také navrženy algoritmy na místě , ale pro non-square matice jsou mnohem komplikovanější). Vzhledem k tomu, m × n matice a n x m matice B , bychom chtěli uložit přemístit A do B . Naivní řešení prochází jedním polem v pořadí hlavních řádků a druhým v hlavním sloupci. Výsledkem je, že když jsou matice velké, dostaneme chybu mezipaměti na každém kroku procházení sloupců. Celkový počet chyb v mezipaměti je .
Algoritmus bez paměti cache má optimální pracovní složitost a optimální složitost mezipaměti . Základní myšlenkou je redukovat transpozici dvou velkých matic na transpozici malých (sub) matic. Děláme to tak, že rozdělíme matice na polovinu podél jejich větší dimenze, dokud nebudeme muset provést transpozici matice, která se vejde do mezipaměti. Protože velikost mezipaměti není algoritmu známa, budou matice i nadále rekurzivně děleny i po tomto bodě, ale tyto další pododdělení budou v mezipaměti. Jakmile jsou rozměry m a n dostatečně malé, takže vstupní pole velikosti a výstupní pole velikosti se vejde do mezipaměti, průchody hlavní i hlavní hlavní způsobí vynechání práce a mezipaměti. Použitím tohoto přístupu rozděl a panuj můžeme dosáhnout stejné úrovně složitosti pro celkovou matici.
(V zásadě by se dalo pokračovat v dělení matic, dokud není dosaženo základního případu velikosti 1 × 1, ale v praxi se používá větší základní případ (např. 16 × 16), aby se amortizovala režie rekurzivních volání podprogramů.)
Většina algoritmů bez paměti cache spoléhá na přístup typu rozděl a panuj. Snižují problém, takže se nakonec vejde do mezipaměti, bez ohledu na to, jak malá je mezipaměť, a ukončí rekurzi v nějaké malé velikosti určené režií volání funkcí a podobnými optimalizacemi nesouvisejícími s mezipamětí a poté použijí nějaký přístup efektivní z mezipaměti sloučit výsledky těchto malých, vyřešených problémů.
Stejně jako externí třídění v modelu externí paměti je třídění bez paměti cache možné ve dvou variantách: funnelsort , které se podobá mergesort , a cache-livestious distribution sort , které se podobá quicksortu . Stejně jako jejich externích paměťových protějšky, jak dosáhnout dobu provozu z , který se shoduje se spodní hranici , a je tedy asymptoticky optimální .
