Algoritmus externí paměti - External memory algorithm

v výpočetní, algoritmy externí paměti nebo out-of-core algoritmy jsou algoritmy které jsou určeny ke zpracování dat, která jsou příliš velká na to, aby se vešla do počítače hlavní paměť najednou. Takové algoritmy je třeba optimalizovat, aby bylo možné efektivně načítat a přistupovat k datům uloženým v pomalé hromadné paměti (pomocná paměť ) jako pevné disky nebo páskové jednotky, nebo když je paměť zapnutá počítačová síť.^[1][2] Algoritmy externí paměti jsou analyzovány v model externí paměti.

Modelka

Mezipaměť nalevo drží ${ displaystyle { tfrac {M} {B}}}$ bloky velikosti ${ displaystyle B}$ každý, celkem M předměty. Externí paměť vpravo je neomezená.

Algoritmy externí paměti jsou analyzovány v idealizovaném stavu model výpočtu nazývá se model externí paměti (nebo I / O modelnebo model přístupu na disk). Model externí paměti je abstraktní stroj podobně jako Model stroje RAM, ale s mezipaměti navíc hlavní paměť. Model zachycuje skutečnost, že operace čtení a zápisu jsou v a mnohem rychlejší mezipaměti než v hlavní paměť, a to čtení dlouhé souvislé bloky je rychlejší než čtení náhodně pomocí a hlava pro čtení a zápis na disk. The provozní doba z algoritmus v modelu externí paměti je definován požadovaným počtem čtení a zápisů do paměti.^[3] Model představili Alok Aggarwal a Jeffrey Vitter v roce 1988.^[4] Model externí paměti souvisí s mezipaměťový model, ale algoritmy v modelu externí paměti mohou znát obě velikost bloku a mezipaměti velikost. Z tohoto důvodu se model někdy označuje jako model s vědomím mezipaměti.^[5]

Model se skládá z a procesor s vnitřní pamětí nebo mezipaměti velikosti M, připojený k neomezený externí paměť. Interní i externí paměť se dělí na bloky velikosti B. Jedna operace vstupu / výstupu nebo přenosu paměti spočívá v přesunutí bloku B souvislé prvky z vnější do vnitřní paměti a provozní doba algoritmu je určen počtem těchto operací vstupu / výstupu.^[4]

Algoritmy

Algoritmy v modelu externí paměti využívají skutečnosti, že načtením jednoho objektu z externí paměti se načte celý blok velikosti ${ displaystyle B}$. Tato vlastnost se někdy označuje jako lokalita.

Hledání prvku mezi ${ displaystyle N}$ objektů je možné v modelu externí paměti pomocí a B-strom s větvícím faktorem ${ displaystyle B}$. Pomocí B-stromu lze v prohlížeči dosáhnout vyhledávání, vkládání a mazání ${ displaystyle O ( log _ {B} N)}$ čas (v Velká O notace ). Informace teoreticky, to je minimum provozní doba pro tyto operace možné, takže použití B-stromu je asymptoticky optimální.^[4]

Externí třídění třídí v nastavení externí paměti. Externí třídění lze provést pomocí distribučního řazení, které je podobné quicksort, nebo prostřednictvím a ${ displaystyle { tfrac {M} {B}}}$-druh sloučení. Obě varianty dosahují asymptoticky optimální doba běhu ${ displaystyle O ({ tfrac {N} {B}} log _ { tfrac {M} {B}} { tfrac {N} {B}})}$ seřadit N předměty. Tato vazba platí také pro rychlá Fourierova transformace v modelu externí paměti.^[2]

Problém permutace je přeskupit ${ displaystyle N}$ prvky do konkrétního permutace. To lze provést buď tříděním, které vyžaduje výše uvedený běh třídění, nebo vložením každého prvku v pořadí a ignorováním výhody lokality. Permutaci lze tedy provést v ${ displaystyle O ( min (N, { tfrac {N} {B}} log _ { tfrac {M} {B}} { tfrac {N} {B}}))}$ čas.

Aplikace

Model externí paměti zachycuje hierarchie paměti, který není modelován v jiných běžných modelech používaných při analýze datové struktury, tak jako stroj s náhodným přístupem a je užitečné k prokázání dolní hranice pro datové struktury. Tento model je také užitečný pro analýzu algoritmů, které fungují na datových sadách příliš velkých, aby se vešly do interní paměti.^[4]

Typickým příkladem je geografické informační systémy, zvláště digitální výškové modely, kde celá sada dat snadno přesahuje několik gigabajty nebo dokonce terabajtů dat.

Tato metodika přesahuje rámec univerzální CPU a také zahrnuje GPU výpočetní i klasická zpracování digitálních signálů. v univerzální výpočet na grafických jednotkách (GPGPU), výkonné grafické karty (GPU) s malou pamětí (ve srovnání se známější systémovou pamětí, která se nejčastěji označuje jednoduše jako RAM ) jsou využívány s relativně pomalým přenosem paměti CPU na GPU (ve srovnání s výpočtovou šířkou pásma).

Dějiny

Časné použití termínu „out-of-core“ jako adjektiva je v roce 1962 v odkazu na zařízení které jsou jiné než základní paměť z IBM 360.^[6] Časné použití výrazu „out-of-core“ ve vztahu k algoritmy se objeví v roce 1971.^[7]

Viz také

• Externí třídění
• Online algoritmus
• Streamovací algoritmus
• Algoritmus zapomínající na mezipaměť
• Paralelní externí paměť
• Procházení grafu externí paměti

Reference

externí odkazy

• Out of Core SVD a QR
• Mimo základní grafiku
• Scalapack design