Algoritmus externí paměti

Externí algoritmus paměti (nazývané také mimo jádro algoritmus ) je algoritmus , který je optimalizován pro účinné zpracování množství dat , které překračují kapacitu k dispozici hlavní paměti . Přístup k velkokapacitním paměťovým médiím, jako jsou pevné disky nebo síťová úložiště, je však o několik řádů pomalejší než operace ALU nebo přístup k vyšším úrovním hierarchie úložiště . Proto je počet I / O operací na zařízeních s pomalým velkokapacitním úložištěm rozhodující pro výkon algoritmů externí paměti .

Model paralelního disku, zde s . Interní paměť obsahuje datové prvky, externí paměť je neomezená. Přenos dat mezi nimi probíhá vždy v blocích velikosti .

{\ displaystyle D = P = 1}

{\ displaystyle M}

{\ displaystyle B}

Analýza v modelu paralelního disku (PDM)

Model paralelního disku se často používá k analýze algoritmů externí paměti . Modeluje nejdůležitější vlastnosti magnetických pevných disků a systémů s několika paralelně připojenými pevnými disky a je stále dostatečně jednoduchý pro efektivní analýzu. Uvažujeme zde pouze o dávkových problémech a systémech s jedním procesorem. Pro on-line problémy a systémů s libovolným počtem procesorů, viz Vitter (2006).

definice

Model se skládá z vnitřní paměti, která obsahuje datové prvky, a neomezené vnější paměti, která se skládá z pevných disků. Hlavním indikátorem výkonu je složitost I / O: počet přístupů do externí paměti k vyřešení problému s datovými prvky. Při každém přístupu k externí paměti lze do vnitřní paměti z každého pevného disku načíst blok datových prvků. Analogové lze zapisovat z interní do externí paměti. Dále by mělo platit také . ${\ displaystyle M}$ ${\ displaystyle D}$ ${\ displaystyle N}$ ${\ displaystyle D}$ ${\ displaystyle B}$ ${\ displaystyle M <N}$ ${\ displaystyle 1 \ leq DB \ leq M / 2}$

Dva soubory A a B o velikosti, které jsou distribuovány v procesu prokládání na pevných discích D1 až D3.

{\ displaystyle 4B}

V případě pevných disků musí být vstupní data problému pro efektivní zpracování distribuována mezi disky v pruhovaném ( en ) formátu (pro příklad viz ilustrační obrázek). Výstup algoritmu by měl mít stejný formát. To umožňuje zapisovat nebo číst datové prvky z externí paměti s optimálním počtem I / O. ${\ displaystyle D> 1}$ ${\ displaystyle D}$ ${\ displaystyle N}$ ${\ displaystyle \ Theta (N / DB)}$

Vzorce pro výsledný počet I / O lze často zjednodušit, pokud se místo výše použitých datových prvků použije příslušný počet bloků. To má za následek odvozených proměnných stejně . ${\ displaystyle n = N / B}$ ${\ displaystyle m = M / B}$

Základní operace

Složitost I / O mnoha algoritmů je v zásadě určena výkonem některých základních operací:

Skenování (také streamování nebo dotýkání ) - čtení nebo zápis sekvenčních datových prvků ${\ displaystyle N}$
Uspořádat z datových prvků (srovnání založené) ${\ displaystyle N}$

Omezení složitosti I / O těchto operací najdete v následující tabulce:

Omezení složitosti I / O základních operací
chirurgická operace	I / O bariéra, D = 1	I / O bariéra, D ≥ 1
${\ displaystyle {\ textit {Scan}} (N)}$	${\ displaystyle \ Theta (N / B) = \ Theta (n)}$	${\ displaystyle \ Theta (N / DB) = \ Theta (n / D)}$
${\ displaystyle {\ textit {Třídit}} (N)}$	${\ displaystyle \ Theta (N / B \ log _ {M / B} N / B) = \ Theta (n \ log _ {m} n)}$	${\ displaystyle \ Theta (N / DB \ log _ {M / B} N / B) = \ Theta (n / D \ log _ {m} n)}$

Příklady

Sloučit třídění

Sloučení sloučení externí paměti by mělo sloužit jako jednoduchý příklad algoritmu třídění externí paměti, který je optimální pro I / O. Tento algoritmus pracuje ve dvou fázích. ${\ displaystyle D = 1}$

První fáze, nazývaná tvorba běhu , přijímá netříděnou sekvenci prvků v externí paměti jako vstup a generuje permutaci této sekvence jako výstup, rozdělená do tříděných dílčích sekvencí délky (tzv. Běhy ). Každý z těchto dílčích sekvencí je generován čtením na vstupních bloků do vnitřní paměti, jejich třídění a pak tam psaní je zpět do externí paměti. ${\ displaystyle N / M}$ ${\ displaystyle M}$ ${\ displaystyle m}$ ${\ displaystyle n}$

Ve druhé fázi algoritmu jsou stávající běhy rekurzivně sloučeny, dokud není k dispozici pouze jeden zcela seřazený běh. Za tímto účelem jsou běhy současně streamovány blok po bloku přes vnitřní paměť pro každou úroveň rekurze a sloučeny do tříděného běhu. Všechny prvky jsou čteny a zapisovány jednou za úroveň, což odpovídá I / O. Po sloučení fází zbývá jen jeden seřazený běh, výsledek. ${\ displaystyle m}$ ${\ displaystyle 2n}$ ${\ displaystyle \ Theta (\ log _ {m} n)}$

Celkově algoritmus potřebuje I / O, a je proto optimální. ${\ displaystyle \ Theta (n \ log _ {m} n)}$

motivace

Obvykle se runtime algoritmů analyzuje ve výpočtových modelech bez hierarchie paměti. V těchto modelech je přístup do paměti stálý, stejně jako provádění aritmetických instrukcí. Kromě toho jsou náklady na přístup do paměti nezávislé na adrese, ke které se přistupuje, stejně jako na předchozích přístupech.

Tyto předpoklady jsou zjednodušující a neodpovídají realitě. Na jedné straně se časy přístupu mezi dvěma úrovněmi hierarchie úložiště obvykle liší řádově. Na druhou stranu mezipaměti a způsob práce pevných disků znamenají, že přístup k několika po sobě jdoucím adresám je obecně rychlejší než přístup k náhodným adresám (viz také vlastnost lokality ).

Rozdíl mezi dobami přístupu mezi hlavním a velkokapacitním úložištěm je obzvláště vysoký. Viz také hierarchie úložiště . To platí také pro SSD jako velkokapacitní úložiště.

aplikace

Existují různé knihovny a nástroje pro implementaci algoritmů externí paměti. Komplexní přehled najdete ve Vitteru (2006) na straně 141.

Dějiny

Podle Vittera začaly práce na algoritmech externí paměti ve Stanfordu již v roce 1956 disertační prací HB Demuth Electronic sorting dat . Dokonce i Donald Knuth se ve své monografii z roku 1973, která vyšla The Art of Computer Programming Sorting and Searching: Volume 3, zabýval značně tříděním dat na magnetických páskách a částečně na pevných discích. Zhruba ve stejné době představil Robert Floyd ve svém díle permutací informací v idealizované skladování dvouúrovňové model s velkou podobnost s PDM s parametry , , kde . V roce 1988 Aggarwal a Vitter rozšířili Floydův model v části Vstupně / výstupní složitost třídění a související problémy tak, aby zahrnovala možnost paralelních blokových přenosů. V roce 1994 představili Vitter a Shriver model paralelního disku, což je realističtější verze modelu Aggarwal a Vitters. ${\ displaystyle D = 1}$ ${\ displaystyle P = 1}$ ${\ displaystyle B = M / 2 = \ Theta (N ^ {c})}$ ${\ displaystyle 0 <c <1}$

Viz také

Hierarchie úložiště
Cache-Oblivious Algorithm - alternativní modelování ve kterém algoritmus a jsou k dispozici ${\ displaystyle M}$ ${\ displaystyle B}$

Individuální důkazy

↑ ^a^b^c^d^e^f^g^hⁱ^j^k^l^mⁿ^o Jeffrey Scott Vitter: Algoritmy a datové struktury pro externí paměť . In: Foundations and Trends® in Theoretical Computer Science . páska 2 , č. 4. 2006, ISSN 1551-305X , s. 305-474 , doi : 10.1561 / 0400000014 ( nowpublishers.com [zpřístupněno 26. července 2019]).
↑ Deepak Ajwani, Itay Malinger, Ulrich Meyer, Sivan Toledo: Charakterizace výkonu zařízení pro ukládání paměti Flash a jeho dopad na design algoritmu . In: Experimentální algoritmy . páska 5038 . Springer Berlin Heidelberg, Berlin, Heidelberg 2008, ISBN 978-3-540-68548-7 , str. 208-219 , doi : 10.1007 / 978-3-540-68552-4_16 ( springer.com [přístup 30. července 2019]).
↑ Demuth, Howard B.: Elektronické třídění dat . Katedra elektrotechniky, Stanford University, 1956, OCLC 25124024 .
^ Knuth, Donald Ervin: Umění počítačového programování. Sv. 3, Třídění a vyhledávání . Addison-Wesley, 1973, ISBN 0-201-89685-0 .
↑ Robert W. Floyd: permutující informace v idealizovaném dvouúrovňovém úložišti . In: Složitost počítačových výpočtů . Springer USA, Boston, MA 1972, ISBN 1-4684-2003-8 , str. 105-109 , doi : 10.1007 / 978-1-4684-2001-2_10 .
↑ Alok Aggarwal, Jeffrey, S. Vitter: Vstupní / výstupní složitost třídění a související problémy . In: Komunikace ACM . páska 31 , č. 9 , 1. srpna 1988, str. 1116-1127 , doi : 10,1145 / 48529,48535 .
↑ JS Vitter, EAM Shriver: Algoritmy pro paralelní paměť, I: dvouúrovňové paměti . In: Algorithmica . páska 12 , č. 2-3 , 1994, ISSN 0178-4617 , str. 110–147 , doi : 10.1007 / BF01185207 ( springer.com [přístup 26. července 2019]).

[Vitter_2006-1] ↑ ^a^b^c^d^e^f^g^hⁱ^j^k^l^mⁿ^o Jeffrey Scott Vitter: Algoritmy a datové struktury pro externí paměť . In: Foundations and Trends® in Theoretical Computer Science . páska 2 , č. 4. 2006, ISSN 1551-305X , s. 305-474 , doi : 10.1561 / 0400000014 ( nowpublishers.com [zpřístupněno 26. července 2019]).

[2] Deepak Ajwani, Itay Malinger, Ulrich Meyer, Sivan Toledo: Charakterizace výkonu zařízení pro ukládání paměti Flash a jeho dopad na design algoritmu . In: Experimentální algoritmy . páska 5038 . Springer Berlin Heidelberg, Berlin, Heidelberg 2008, ISBN 978-3-540-68548-7 , str. 208-219 , doi : 10.1007 / 978-3-540-68552-4_16 ( springer.com [přístup 30. července 2019]).

[Demuth_1994-3] Demuth, Howard B.: Elektronické třídění dat . Katedra elektrotechniky, Stanford University, 1956, OCLC 25124024 .

[Knuth_1973-4] Knuth, Donald Ervin: Umění počítačového programování. Sv. 3, Třídění a vyhledávání . Addison-Wesley, 1973, ISBN 0-201-89685-0 .

[Floyd_1972-5] Robert W. Floyd: permutující informace v idealizovaném dvouúrovňovém úložišti . In: Složitost počítačových výpočtů . Springer USA, Boston, MA 1972, ISBN 1-4684-2003-8 , str. 105-109 , doi : 10.1007 / 978-1-4684-2001-2_10 .

[Aggarwal_1988-6] Alok Aggarwal, Jeffrey, S. Vitter: Vstupní / výstupní složitost třídění a související problémy . In: Komunikace ACM . páska 31 , č. 9 , 1. srpna 1988, str. 1116-1127 , doi : 10,1145 / 48529,48535 .

[Vitter_1994-7] JS Vitter, EAM Shriver: Algoritmy pro paralelní paměť, I: dvouúrovňové paměti . In: Algorithmica . páska 12 , č. 2-3 , 1994, ISSN 0178-4617 , str. 110–147 , doi : 10.1007 / BF01185207 ( springer.com [přístup 26. července 2019]).

Languages