Ing. Daniel Langr, Ph.D.

Ing. Daniel Langr, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra softwarového inženýrství

Ing. Daniel Langr, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

V této práci je představen C++11Sort, nová paralelni verze in-place algoritmu quicksort. C++11Sort je implementován pouze na základě C++11 vláken a přislušných synchronizačnich technik, tedy bez použiti nadstandardnich roz- šiřeni jazyka C++ a externich knihoven. V rešeršni části jsou popsány exis- tujici implementace paralelni verze algoritmu quicksort. Tyto existujici im- plementace jsou následně experimentálně porovnány s vytvořeným algorit- mem C++11Sort. C++11Sort dosahuje v experimentech výborných výsledků, napřiklad při řazeni dvou miliard celých čisel je o 28 % rychlejši než nejrych- lejši existujici implementace.

Práce na DSpace

Ing. Daniel Langr, Ph.D.

Ing. Jiří Kašpar

Katedra teoretické informatiky

Automaticky memoizační systém - také softwarová cache - ukládá omezený počet prvků v paměti, které byly nedávno zpřístupněny a zrychluje tak následný přístup k nim. Least-Recently-Used (LRU) je populární strategie nahrazování prvků pro hardwarovou a softwarovou cache. Nicméně, její paralelní implementace má nízkou škálovatelnost v důsledku přeskupování seznamu, které je prováděno jak při vyhledávání tak při vkládání. V této práci je představena nová paralelní softwarová cache DeferredLRU, která vychází z LRU strategie. Hlavním cílem návrhu byla škálovatelnost a efektivní využití na mnoha-jádrových sýstémech. Toho bylo dosaženo použitím jiného řešení ke sledování pořadí přístupu k prvkům. Toto řešení podstatně snižuje počet opětovných vložení prvků do seznamu, což je hlavním faktorem zpomalení u běžné LRU cache. Výkonnost a hit-rate DeferredLRU jsou citlivé na nastavení konfiguračních parametrů. Díky vyladělnému nastavení parametrů pro specifické vstupy byl dosažen vyšší hit-rate než u běžné LRU cache ve všech testovaných případech. Relativní rozdíl byl až 7,8%. Výkon DererredLRU byl porovnán s existujícími alternativami, včetně souvisejícíh implementací cache z projektů Intel TBB a Facebook HHVM. Testované implementace cache byly hodnoceny až do 32 vláken (na 16 HW CPU jádrech). Při 32 vláknech, DeferredLRU bylo rychlejší ve všech 16 testech. Pokud byly přístupy distribuovány mezi více malých cache z důvodu lepšího paralelizmu (tzv. binning), DeferredLRU bylo rychlejší v 11 z 16 případů a ve zbylých 5 byl výkon blízko nejlepšímu pozorovanému výsledku. DeferredLRU s binning přístupem bylo až 28,8 krát rychlejší na 32 vláknech ve srovnání s jedno-vláknovým výkonem.

Práce na DSpace

Ing. Daniel Langr, Ph.D.

Ing. Jiří Kašpar

Katedra teoretické informatiky

Ab initio přístup ke zkoumání struktury atomových jader je na popředí součas- ného vývoje nukleární fyziky. LSU3shell je implementací ab initio metody zvané symmetry-adapted no-core shell model (SA-NCSM) pro vysoce paralelní výpočetní systémy. Cílem této práce bylo zanalyzovat výkonnové charakteristiky programu LSU3shell se zaměřením převážně na dynamickou alokaci paměti, provést rešerši metod a řešení která by mohla vést ke zlepšení výkonu a využití paměti, a provést následnou implementaci. Tento přístup se ukázal být správný, a bylo možné provést mnoho optimalizací vztahujících se k dynamické alokaci paměti. Výsledkem této práce je průměrné zrychlení LSU3shell o 41 %, což nám ušetří až 1,4 milionu core-hodin z naší alokace na superpočítači BlueWaters.

Práce na DSpace

Ing. Daniel Langr, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra teoretické informatiky

Četné dynamické alokace z haldy mohou mít zásadní dopad na celkovou dobu běhu programu. Problém se stává ještě více kritickým ve vícevláknových aplikacích, kde přílišná interakce s haldou může přerůst v hlavní zdroj neefektivity programu a negativně se podepsat na jeho škálovatelnosti. Existující profilery haldy přidávají k běhu programu tak velkou režii, že se profilování paměťově náročných vícevláknových aplikací stává téměř nemožné. Tato práce popisuje obvyklé rozložení paměti Linuxového procesu, nastiňuje interní části paměťového manažeru GNU C, analyzuje existující nástroje pro profilování haldy a provádí čtenáře procesem konstrukce vlastního profileru haldy. Práce dále navrhuje koncept profilování haldy s nízkou latencí, na jehož základě byl vytvořen nový profiler s názvem Heaprof. Ten byl následně porovnán s existujícími profilery. Experimentální vyhodnocení odhalilo, že Heaprof jako jediný ze zkoumaných nástrojů dokázal provádět profilování bez dalšího dopadu na škálovatelnost programu. V osmivláknových benchmarcích došlo až k osminásobnému urychlení celého profilování.

Práce na DSpace

Ing. Daniel Langr, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Katedra počítačových systémů

Cilem teto prace je poskytnout uceleny prehled dosud publikovanych formatu pro ulozeni ridke matice v pameti pocitace. Prace obsahuje popis jejich principu a pripadne vyuziti pri nasobeni ridke matice s vektorem na modernich paralelnich systemech.

Práce na DSpace