=Paper=
{{Paper
|id=None
|storemode=property
|title=Revize metod externího třídění pro moderní hardware
|pdfUrl=https://ceur-ws.org/Vol-1003/65.pdf
|volume=Vol-1003
|dblpUrl=https://dblp.org/rec/conf/itat/KrulisCFY13
}}
==Revize metod externího třídění pro moderní hardware==
https://ceur-ws.org/Vol-1003/65.pdf
ITAT 2013 Proceedings, CEUR Workshop Proceedings Vol. 1003, pp. 65–68
http://ceur-ws.org/Vol-1003, Series ISSN 1613-0073, c 2013 M. Kruliš, M. Čermák, Z. Falt, J. Yaghob
Revize metod externího třídění pro moderní hardware
Martin Kruliš, Miroslav Čermák, Zbyněk Falt a Jakub Yaghob ∗
Katedra softwarového inženýrství, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze, Malostranské nám 25., Praha 1
{krulis,cermak,falt,yaghob}@ksi.mff.cuni.cz
Abstrakt: Metody externího třídění, tedy třídění využíva- • Externí pamět’ je o mnoho řádů pomalejší než interní
jícího vnější pamět’, jsou velmi dobře známy již mnoho pamět’, takže dominantní složkou vyjadřující časo-
desetiletí. Tyto metody byly původně navrženy pro sys- vou složitost je počet operací s externí pamětí.
témy s malým množstvím interní paměti a magnetickými
V tomto článku bychom rádi vyvrátili tyto předpoklady
páskami coby vnější pamětí. Magnetické pásky jsou spe-
pomocí empirických experimentů, jejichž cílem je identifi-
cifické čistě sekvenčním přístupem k datům, který také
kovat vlastnosti soudobých pevných disků s magnetickými
ovlivnil návrh metod externího třídění. Pásky byly nahra-
plotnami a SSD pevných disků. Na základě opravených
zeny pevnými disky s magnetickými plotnami, které při-
předpokladů pak navrhujeme změny pro algoritmy vněj-
nesly možnost náhodného přístupu k datům, avšak sek-
šího třídění, které by měly značně vylepšit jejich výkon.
venční přístup zůstal nadále výrazně výkonnější. Vět-
Tento článek je organizován následovně. Sekce 2 shr-
šina hardwarových předpokladů, na kterých je externí tří-
nuje přehled souvisejících prací zaměřených na externího
dění postaveno se za poslední desetiletí výrazně změ-
třídění. Popis současných algoritmů se nachází v sekci 3.
nila, zejména s příchodem SSD disků a vývojem non-
Sekce 4 definuje nové předpoklady o současném hardware
volatilních pamětí. V tomto článku představujeme nový
a na jejich základě navrhuje změny v metodách externího
přístup k externímu třídění, který reflektuje parametry sou-
třídění. Výsledky experimentů, které podporují naše zá-
časného hardware. Dále předkládáme empirické srovnání
věry, se nachází v sekci 5 a sekce 6 uzavírá článek.
s již existujícími metodami, které se hojně používají v sou-
dobých systémech.
Klíčová slova: třídění, vnější pamět’, algoritmus, optima- 2 Související výzkum
lizace, moderní hardware
Problém externího třídění, tedy třídění za použité vnější
paměti, je jedním z hlavních problémů v oblasti algoritmů
1 Úvod pro externí pamět’. Částečně je tomu tak proto, že třídicí
operace tvoří signifikantní část počítačových operací [6], a
Třídění patří k základním stavebním kamenům řady algo- částečně proto, že třídění je důležitým paradigma v návrhu
ritmů a aplikací. V databázových systémech patří společně efektivních algoritmů nejen pro externí pamět’. Studium
s operací JOIN k nejpoužívanějším operacím vůbec. I přes těchto problémů a analýza algoritmů používajících vnější
rostoucí kapacity a klesající ceny operačních pamětí není pamět’ mají své počátky před více než 50ti lety v Demu-
vždy možné řešit tuto úlohu čistě v rámci vnitřní paměti thově doktorské tezi [3], která se zaměřovala zejména na
počítače. Pro tyto situace máme k dispozici algoritmy ex- třídění. V 70tých letech provedl Knuth [6] rozsáhlou studii
terního třídění, které využívají diskové úložiště k odklá- třídění v rámci svých knih pojednávajících o umění mo-
dání mezivýsledků. derního programování. V knize o třídění a vyhledávání se
Algoritmy vnějšího třídění byly navrženy a zmapovány zabývá mimo jiné strategiemi výběru a nahrazení a meto-
již v dobách, kdy se jako externí pamět’ používaly mag- dami polyfázového slévání za použití magnetických pásek
netické pásky. I přes jejich původní cíle se tyto algoritmy a magnetických disků. Od té doby vzniklo mnoho nových
s drobnými úpravami používají dodnes. Jejich hlavní ne- a upravených algoritmů pro třídění za pomoci externí pa-
výhodou je, že předpoklady, ze kterých tyto algoritmy vy- měti [11], avšak všechny tyto metody sdílí společné před-
chází dnes již neplatí. Nejvýznamnější předpoklady mů- poklady definované Knuthem.
žeme shrnout takto: Datová komunikace mezi rychlou interní pamětí a po-
malejší externí pamětí je považována za úzké hrdlo při
• Externí pamět’ je organizována sekvenčně, nebo je zpracování velikých dát [2, 7, 11]. Většina algoritmů se
sekvenční přístup výrazně výkonnější. snaží dosáhnout odbourání tohoto úzkého hrdla minima-
lizací počtu vstupně výstupních operací, optimální prací
• Máme k dispozici pouze malé množství externích pá- s vyrovnávací pamětí [7], nebo asynchronním načítáním
sek, resp. můžeme rozumně pracovat pouze s malým dat [2]. Další metodou je nasazení více pevných disků,
množstvím otevřených souborů. které se využívají bud’ nezávisle, nebo pomocí prokládání
∗ Článek byl podporován Grantovou agenturou Univerzity Karlovy, (stripingu), který bývá často efektivnější než kompliko-
projekty č. 472313 a 277911, Grantovou agenturou ČR (GAČR) vané algoritmy pro nezávislé využití disků [10]. Nejno-
P103/13/08195S a grantem SVV-2013-267312. vějším přístupem je využití distribuovaného prostředí při
66 M. Kruliš, M. Čermák, Z. Falt, J. Yaghob
vhodném rozdělení dat a výpočtů [8]. Pokroku ve výkonu
disků (především SSD) si všimli také autoři energeticky
efektivních algoritmů [1, 9], jejichž hlavním cílem je opět
minimalizace počtu diskových operací a tedy i minimali-
zace cyklů slévání.
Obrázek 1: Princip dvoufázového třídění
3 Existující metody vnějšího třídění
pásek. Nejjednodušší implementace slévání běhů potom
Většina algoritmů externího třídění má dvě části. V první využívá N − 1 souborů jako vstup a jeden soubor pro ucho-
části se generují takzvané běhy, tedy sekvence setříděných vání výstupu. Na počátku jsou při generování běhy rozdis-
dat. Druhá část pak provádí postupné slévání těchto běhů, tribuovány rovnoměrně mezi vstupní soubory. Proces slé-
dokud nevznikne běh jediný, který reprezentuje setříděná vání pak pracuje iterativně a každá iterace má dvě fáze. V
data. Algoritmy se však liší tím, jakým způsobem běhy první fázi slévá současně běhy z N − 1 souborů a výsledné
generují a jak je slévají. běhy zapisuje do výstupního souboru. V druhé fázi je pře-
čten celý výstupní soubor a běhy z něj jsou rovnoměrně
rozdistribuovány mezi vstupní soubory. Algoritmus končí,
3.1 Generování běhů
když ve výstupním souboru zůstane pouze jeden běh.
Nejjednodušší metodou je přímočaré generování běhů po- Proces slévání je znázorněn na obrázku 1. Samotné slé-
mocí jednoho bufferu1, jehož velikost je zvolena tak, aby vání probíhá ve vnitřní paměti a je možné jej implemento-
využíval veškerou dostupnou interní pamět’. Buffer je poté vat například pomocí prioritní fronty (tzn. haldy), která si
naplněn vstupními daty a setříděn vhodnou metodou in- udržuje první dosud nezpracovaný prvek z každého běhu.
terního třídění, například Quicksortem [5]. Data z bufferu Hlavní nevýhodou tohoto postupu je nutnost provádět
jsou následně přesunuta do vnější paměti, čímž je vytvo- opětovnou redistribuci běhů ve druhé fázi každé iterace.
řen jeden běh. Tento postup je opakován, dokud se nachází Jedním z možných řešení, je použít pouze N/2 souborů
nezpracovaná data ve vstupním souboru. jako vstupních a generované běhy distribuovat rovnou
Na první pohled by se mohlo zdát, že není možné ge- mezi N/2 výstupních souborů. Tento postup má ale ne-
nerovat běhy delší, než je velikost vnitřní paměti. Existuje výhodu v tom, že slévá vždy pouze N/2 běhů místo N − 1
drobné vylepšení, které zajišt’uje generování běhů větších běhů, díky čemuž může potřebovat větší množství iterací.
délek, pokud jsou vstupní data vhodně koncipována. Tato
metoda používá dvě prioritní fronty (typicky reprezento-
3.3 Polyfázové třídění
vané 2-regulárními haldami), které se dělí o veškerou do-
stupnou pamět’. Hlavní nevýhodu dvoufázového třídění do jisté míry řeší
Na počátku zabírá první halda veškerou pamět’ a je polyfázové třídění. Jeho idea spočívá v nerovnoměrné dis-
zcela naplněna daty ze vstupního souboru. V každém tribuci běhů, která je chytře navržena tak, aby bylo možné
kroku je z haldy odebráno minimum a zapsáno do právě běhy neustále slévat bez jejich opětovného rozhazování.
generovaného běhu na disku. Jako náhrada za toto mini- Přitom je vždy N − 1 souborů používáno jako vstupních a
mum je ze vstupního souboru načten další prvek. Pokud výsledné běhy se ukládají do jednoho souboru.
je tento prvek větší nebo roven prvku právě zapsanému Cílem je, aby při posledním slévání byl v každém z
do výstupního běhu, může být nový prvek začleněn do N − 1 vstupních souborů právě jeden běh. V takovém pří-
první haldy. Pokud je větší, první halda zmenší svou ve- padě proběhne poslední krok slévání optimálním způso-
likost o jedna a prvek je vložen do haldy druhé, která se bem. Počáteční rozložení běhů lze dopočítat reverzním
tím zároveň zvětší. Generování běhu končí v okamžiku, naplánováním všech iterací slévání od optimální koncové
kdy je první halda vyčerpána a druhá zabírá celou pamět’. konfigurace. Situace pro N = 3 a 21 počátečních běhů je
V tomto okamžiku se prohodí význam obou hald a může znázorněna v následující tabulce.
začít generování dalšího běhu.
Experimenty na náhodně uspořádaných datech s uni-
soubor zač. #1 #2 #3 #4 #5 #6
formním rozložením ukazují, že běhy generované pomocí
dvou hald mají v průměru dvojnásobnou délku, než je ve- #1 13 5 0 3 1 0 1
likost dostupné paměti. #2 8 0 5 2 0 1 0
#3 0 8 3 0 2 1 0
3.2 N-cestné dvoufázové třídění
Tabulka 1: Optimální slévání 21 běhů pro N = 3
Předpokládejme, že daný systém je schopen otevřít nej-
výše N souborů, resp. může současně používat nejvýše N Na počátku je v prvním souboru 13 běhů a ve druhém
1 Z důvodu nedostatku vhodné terminologie budeme v tomto článku 8. V každém kroku se vezme nejvyšší možný počet běhů,
používat anglický termín buffer v jeho počeštěné podobě. který je možný slít přímo (např. v prvním kroku 8), čímž se
Revize metod externího třídění pro moderní hadware 67
vždy právě jeden soubor uvolní. V případě dvou vstupních haldy navíc není možné (na rozdíl od ostatních třídicích
a jednoho výstupního souboru je rozložení běhů založeno algoritmů) jednoduše paralelizovat. V tomto okamžiku se
na Fibonacciho číslech. jako nejvíce vhodný algoritmus jeví rozdělení paměti na
dva (případně tři) stejně velké úseky, přičemž data v jed-
nom úseku jsou tříděna zatím co data ve druhém (a pří-
4 Moderní přístup k vnějšímu třídění padně třetím) úseku jsou přenášena z disku nebo na disk.
Jako algoritmus vnitřního třídění poslouží nejlépe para-
V této sekci nastíníme nové předpoklady o hardware, lelní verze Quicksortu.
zejména o pevných discích, a na jejich základě opravíme
Jak jsme již naznačili, samotný proces slévání je za běž-
existující algoritmy vnějšího třídění.
ných okolností možné provést v jediném kroku. Pokud je
vnitřní pamět’ řádově přibližně tisíckrát menší než největší
4.1 Vlastnosti hardware možná data ve vnější paměti, pak první část třídění vyge-
neruje nejvýše tisíc běhů, které můžeme mít uloženy v ti-
Na základě empirických pozorování, jejichž nejdůležitější síci nezávislých souborech. K samotnému slévání potom
výsledky jsou shrnuty v sekci 5, můžeme postulovat násle- můžeme použít bud’ prioritní frontu, jak navrhuje Knuth
dující předpoklady: [6], nebo upravenou techniku paralelního proudového slé-
vání, kterou představil ve své práci Falt [4].
• Soudobé magnetické disky sice stále preferují sek-
venční přístup, avšak pokud je k datům přistupováno
po dostatečně velkých blocích (řádově jednotky až
5 Experimenty
desítky MB), je možné aplikovat nad těmito bloky ná-
hodný přístup bez výrazného poklesu výkonu. U SSD
disků je možné používat i bloky menší. Experimenty byly prováděny na běžném PC s proceso-
rem Core i7 (4 fyzická, 8 logických jader) vybaveném
• Průměrná rychlost čtení a zápisu výrazně převyšuje 16 GB RAM. Data byla uložena na samostatném disku
rychlost vnitřního sériového třídění a je srovnatelná (1 TB, 7200 otáček) a druhý (identický) disk byl použit
s rychlostí paralelního vnitřního třídění (na běžně do- pro dočasné soubory s vygenerovanými běhy. Testovací
stupném hardware). data reprezentoval soubor 32 bitových celočíselných hod-
not, které byly náhodně vygenerovány s uniformním roz-
• Použití prioritní fronty (resp. haldy) k vnitřnímu tří- dělením.
dění je výrazně pomalejší než použití Quicksortu.
První sada experimentů zkoumá poměr časů potřebných
• Soudobé operační systémy zvládají bez problémů k setřídění bloku dat pomocí interního třídění a časy po-
pracovat i s tisíci otevřenými soubory současně. třebné k přečtení resp. zapsaní těchto dat na disk. Obrázek
2 prezentuje naměřené časy pro různě velké bloky dat a
• Poměr velikosti vnitřní a vnější paměti je na běžných srovnává jednovláknové třídění Quicksortem s jeho para-
hardwarových konfiguracích menší než 1 : 1000. lelní verzí. Z výsledků je patrné, že časy diskových ope-
rací jsou výrazně nižší, než doba potřebná k setřídění dat
Z výše uvedených předpokladů vyplývají dvě věci. Ex- pomocí jednoho jádra a přibližně srovnatelné s tříděním,
terní třídění již není potřeba optimalizovat na počet disko- které využívá všech 8 logických jader procesoru.
vých operací, nebot’ za běžných podmínek je možné pro-
vést slévání všech vygenerovaných běhů najednou. Díky
tomu je každý prvek právě dvakrát čten z disku a právě
200.0
read
dvakrát na disk zapsán. Za druhé, možnost paralelního serial sort
parallel sort
zpracování tříděných dat ve vnitřní paměti je výrazně dů-
50.0
write
time [s] (log. scale)
ležitější pro budoucí škálovatelnost, protože rychlost pev-
ných disků již přesáhla propustnost třídicích algoritmů pro
10.0
vnitřní pamět’.
2.0
4.2 Změny v algoritmech
0.5
Základní koncept externího třídění zůstává nadále nezmě-
něn. Každý algoritmus má tedy dvě části – generování 16M 64M 256M 1G
běhů a jejich následné slévání. Tyto části jsou do jisté míry block size (objects)
nezávislé, a proto se jim můžeme věnovat samostatně.
Při generování běhů jsme empiricky ověřili, že použití Obrázek 2: Porovnání časů třídění a diskových operací
dvou hald sice vede k vytvoření menšího počtu delších
běhů, avšak tento proces je výrazně pomalejší než pou- Další experimenty se týkají generování běhů. V těchto
žití optimalizovaných algoritmů. Hledání minima pomocí experimentech byl použit vstupní soubor o velikosti 64
68 M. Kruliš, M. Čermák, Z. Falt, J. Yaghob
GB (16 miliard čísel) a buffer pro vnitřní třídění o veli- 6 Závěr
kosti 1 GB (tedy pro 256 milionů čísel). Tyto experimenty
srovnávají sériový přístup, který realizuje všechny diskové V tomto článku jsme aktualizovali některé zažité předpo-
operace i třídění v jediném vlákně, paralelní přístup, který klady týkající se vnějších pamětí a na jejich základě jsme
provádí diskové operace sériově, ale ke třídění dat vyu- navrhli změny třídicích algoritmů, které měly pozitivní do-
žívá všechna dostupná vlákna, přístup založený na pipe- pad na výkon a budoucí škálovatelnost. Prokázali jsme,
line, který provádí diskové operace asynchronně a zároveň že počet diskových operací již není hlavním kritériem op-
třídí paralelně, a konečně generování běhů pomocí dvou timalizace těchto algoritmů, ale vývoj je třeba směřovat
hald. do paralelních implementací. V pokračování této práce se
chceme zaměřit na vylepšení vícecestného slévání pro pa-
ralelní systémy a provést rozsáhlejší testy zejména za po-
užití diskových polí a SSD disků.
20000
19738.6
Reference
15000
time [s]
[1] Andreas Beckmann, Ulrich Meyer, Peter Sanders, and Jo-
10000
hannes Singler. Energy-efficient sorting using solid state
disks. Sustainable Computing: Informatics and Systems,
5243.34
1(2):151–163, 2011.
5000
3194.01
2119.51 [2] Paolo Bertasi, Marco Bressan, and Enoch Peserico. psort,
1250
yet another fast stable sorting software. Journal of Experi-
0
serial I/O serial parallel pipeline 2−heap
mental Algorithmics (JEA), 16:2–4, 2011.
[3] Howard B Demuth. Electronic data sorting. Dept. of Elect-
rical Engineering, 1956.
Obrázek 3: Časy potřebné pro generování běhů [4] Zbyněk Falt, Martin Kruliš, and Jakub Yaghob. Optimali-
zace třídicích algoritmů pro systémy proudového zpraco-
vání dat. Informačné Technológie - Aplikácie a Teória,
Metoda generování běhů pomocí dvou hald má sice po- pages 69–74, 2011.
zitivní dopad na délku (a tedy i počet) běhů [6], avšak z [5] C.A.R. Hoare. Quicksort. The Computer Journal, 5(1):10,
grafu na obrázku 3 je patrné, že tento postup je výrazně 1962.
pomalejší z důvodu značného nárůstu výpočetních operací [6] Donald Ervin Knuth, Donald Ervin Knuth, and Donald Er-
a náhodnému přístupu do vnitřní paměti, který špatně vy- vin Knuth. Sorting and Searching. Addison-Wesley, 2003.
užívá vyrovnávací paměti procesoru. [7] Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray,
and Dave Lomet. Alphasort: A cache-sensitive parallel ex-
ternal sort. The VLDB Journal – The International Journal
on Very Large Data Bases, 4(4):603–628, 1995.
25000
generate [8] Alexander Rasmussen, George Porter, Michael Conley,
merge
Harsha V Madhyastha, Radhika Niranjan Mysore, Alexan-
time [s] (log. scale)
der Pucher, and Amin Vahdat. Tritonsort: A balanced large-
15000
scale sorting system. In Proceedings of the 8th USENIX
conference on Networked systems design and implemen-
tation, pages 3–3. USENIX Association, 2011.
[9] Vijay Vasudevan, Lawrence Tan, Michael Kaminsky, Mi-
5000
chael A Kozuch, David Andersen, and Padmanabhan Pillai.
Fawnsort: Energy-efficient sorting of 10gb. Sort Ben-
0
serial parallel pipeline 2−heap chmark final, 2010.
[10] Darren Erik Vengroff and J Scott Vitter. Supporting i/o-
efficient scientific computation in tpie. In Parallel and
Obrázek 4: Celkové časy externího třídění Distributed Processing, 1995. Proceedings. Seventh IEEE
Symposium on, pages 74–77. IEEE, 1995.
[11] Jeffrey Scott Vitter. External memory algorithms and data
Celkové časy třídění potom prezentuje obrázek 4. Ke structures: Dealing with massive data. ACM Computing
slévání běhů byl použit mechanismus vícecestného slévání surveys (CsUR), 33(2):209–271, 2001.
pomocí 2-regulární haldy. Slévání 128 běhů, které vygene-
rovaly první tři metody trvalo přibližně 2400 sekund, za-
tímco slévání 64 běhů vygenerovaných pomocí dvou hald
trvalo 3100 sekund. Tento překvapivý výsledek se nám za-
tím nepodařilo uspokojivě vysvětlit.