Systémové programování

Závěrečné práce

Diplomové práce

Efficient concurrent memoization system

Autor
Viacheslav Kroilov
Rok
2020
Typ
Diplomová práce
Vedoucí
Ing. Daniel Langr, Ph.D.
Oponenti
Ing. Jiří Kašpar
Anotace
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.

Swift pro Embedded Systémy

Autor
Alan Dragomirecký
Rok
2019
Typ
Diplomová práce
Vedoucí
Ing. Petr Máj
Oponenti
Ing. Tomáš Zahradnický, Ph.D.
Anotace
Po svém zveřejnění v roce 2014 se Swift stal okamžitě jedním z jazyků s nejrychleji rostoucí popularitou. Jeho hlavním zaměřením je vývoj uživatelských aplikací, brzy si ale našel své místo i v serverových aplikacích a nově i v datových vědách. Do této chvíle nebyla nicméně zveřejněná žádná práce zabývající se použitím Swiftu v těch nejmenších počítačích se značně omezenými výpočetními prostředky - ve vestavěných systémech. Tato práce si klade za cíl situaci změnit a být prvním krokem na cestě Swiftu k těmto zařízením. V práci je popsán proces přidání nové bare-metal platformy do kompilátoru Swiftu a nástrojů s ním spojených. V závěru je představen Swift jako možná alternativa k již existujícím řešením na poli vývoje pro vestavěné systémy.

Kompresní metoda PPM využívající de Bruijnovy grafy

Autor
Jakub Kulík
Rok
2019
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
Ing. Petr Procházka, Ph.D.
Anotace
Tato práce pojednavá o odlišném přístupu k PPM kompresnímu algoritmu založeném na succinct de Bruijnových grafech. Využívá dynamické binární vektory a waveletové stromy sloučené do jediného stromu pro vytvoření vysoce výkonné dynamické succinct datové struktury schopné reprezentovat grafy používané kompresorem. Přestože je algorithmus pomalý ve srovnání s ostatními běžně užívanými kompresory, dosahuje dobrých kompresních poměrů při využití výrazně menšího množství paměti.

Spolehlivá charakterizace existence řešení parametrických soustav rovnic

Autor
Libor Vytlačil
Rok
2018
Typ
Diplomová práce
Vedoucí
doc. Dipl.-Ing. Dr. techn. Stefan Ratschan
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Tato práce se zabývá charakterizací množin bodů $p\in P$, pro které exis\-tu\-je reálné řešení $x$ dané parametrické soustavy rovnic $f_P(x,p)=0$, kde ${f_P\colon X\subseteq\Rsetn{n}\to\Rsetn{n}}$ je spojitá funkce zapsaná ve formě aritmetických výrazů a $X$ je box (součin uzavřených reálných intervalů). Je navržen a implementován algoritmus typu branch and bound založený na intervalové aritmetice a testu existence řešení pomocí Brouwerova topologického stupně. Implementace umožňuje několik způsobů manipulace s do\-mé\-nou $X$ a další parametrizace své činnosti. Intervalová aritmetika slouží jednak k výpočtu odhadů obrazů funkcí, jednak k zajištění robustnosti vzhledem k zaokrouhlovacím chybám. Implementace je poskytnuta v podobě samostatné aplikace včetně uživatelského rozhraní (textového i grafického). Na základě výsledků experimentů, které jsou uloženy ve formě skriptů pro snadnou reprodukovatelnost, je naše implementace schopna produkovat kvalitní výsledky a skončit v rozumném čase pro různorodé nelineární soustavy až o třech rovnicích, které mohou obsahovat kombinace elementárních funkcí jako $\exp$, $\log$, $\sin$, $\cos$, $\arcsin$, $\arccos$, $n$-tá odmocnina, $\dots$. Přispíváme také k dosavadní práci týkající se praktického počítání topologického stupně popisem a použitím vlastní spolehlivé metody pro stanovení, zda pro libovolné boxy $X'\subseteq X$, $P'\subseteq P$ je definován stupeň $\tdeg(f_p, X', 0)$ a má pro každý parametr $p\in P'$ stejnou hodnotu.

Zlepšení RIR Bytecode překladače a interpretu

Autor
Jan Ječmen
Rok
2017
Typ
Diplomová práce
Vedoucí
Ing. Petr Máj
Oponenti
Ing. Filip Křikava, Ph.D.
Anotace
R je dynamicý programovací jazyk, navzdory svému stáří dnes stále oblíbený. RIR je alternativní implementace kompilátoru a interpretu R bajtkódu, která umožňuje snadno provádět statickou analýzu a přidávat optimalizace. RIR je ve vývoji a zatím nedosahuje výkonu standardního R. Tato diplomová práce se pokouší přiblížit výkon RIR k výkonu standardního R. V jejím rámci byly přidány nové instrukce do RIR bajtkódu a nová funkcionalita do jeho kompilátoru a došlo k přepracování jeho interpretu. Průměrné zpomalení na sadě benchmarků Shootout proti standardnímu R bylo sníženo o polovinu.

Rozšíření systému NEMEA pro nasazení v distribuovaném prostředí

Autor
Marek Švepeš
Rok
2017
Typ
Diplomová práce
Vedoucí
Ing. Tomáš Čejka, Ph.D.
Anotace
Množství dat, které musí v dnešní době monitorovací systémy zpracovávat, roste kvůli zvyšující se rychlosti počítačových sítí a přibývajícímu počtu připojených zařízení. Kvůli různým typům bezpečnostních hrozeb musí být většinou data zpracována mnoha detekčními algoritmy najednou s omezenými výpočetními prostředky. Pro zpracování velkého množství síťových dat se začíná používat paralelizace a vznikají škálovatelná řešení monitorovacích systémů. V rámci této diplomové práce byl pro účely výzkumu v oblasti paralelizace zpracování použit modulární open-source systém NEMEA. Tato práce se zabývá návrhem, realizací a testováním rozšíření systému NEMEA, které umožní distribuované nasazení systému, což díky paralelnímu zpracování řádově zvýší propustnost celého systému. Zvolený způsob paralelizace spočívá v rozdělování proudu síťových toků mezi výpočetní uzly. Navržené řešení je realizováno v podobě NEMEA modulu. Práce dále popisuje vytvořené testovací prostředí, ve kterém byly provedeny experimenty k ověření vlastností nového modulu. Všechny experimenty byly provedeny s reálnými daty z akademické sítě CESNET2. V závěru práce je představena škálovatelná architektura paralelního zpracování pomocí systému NEMEA.

Paralelní bezeztrátová komprese dat

Autor
Ondřej Fiedler
Rok
2016
Typ
Diplomová práce
Vedoucí
prof. Ing. Jan Holub, Ph.D.
Oponenti
doc. Ing. Ivan Šimeček, Ph.D.
Anotace
Tato práce se zabývá paralelní bezeztrátovou kompresí dat se zaměřením na využití výpočtů na grafické kartě. Uvádí čtenáře do problematiky datové komprese a do problematiky architektur a technologií pro paralelní výpočty. Zkoumá existující řešení pro paralelní bezeztrátovou kompresi včetně algoritmů určených pro grafické karty. Hlavním přínosem této práce je nová implementace PMLZSS, což je slovníková kompresní metoda pro grafické karty založená na LZSS, kterou v roce 2015 navrhli Bin Zhou, Hai Jin a Ran Zheng. Jsou popsána a vyhodnocena navržená technologická a algoritmická vylepšení. Práce experimentálně porovnává vytvořenou implementaci PMLZSS se sekvenční implementací LZSS a existujícími paralelními řešeními pro vícejádrové procesory a grafické karty. PMLZSS byla na testovaných datech 9,4krát až 22krát rychlejší než sekvenční verze. Pro soubory z několika kategorií dosáhla implementace PMLZSS z testovaných řešení nejvyšší rychlosti zpracování.

Konstrukce zásobníkového automatu přijímajícího jazyk daný regulárním stromovým výrazem

Autor
Tomáš Pecka
Rok
2016
Typ
Diplomová práce
Vedoucí
Ing. Jan Trávníček, Ph.D.
Oponenti
Ing. Radomír Polách
Anotace
Tato práce studuje regulárni stromové výrazy, formalismus pro popis regulárnich stromových jazyků. Hlavnim přinosem práce je nový algoritmus pro převod regulárniho stromového výrazu na ekvivalentni zásobnikový automat, který přijimá stromy v lineárnim postfixovém zápisu. Výsledný automat patři do kategorie real-time height-deterministic zásobnikových automatů, což znamená, že je vždy zdeterminizovatelný. Algoritmus vytvářejici tento automat je modifikaci Glushkovova algoritmu pro převod regulárnich výrazů na nedeterministický konečný automat. Implementace převodu je v jazyce C++ jako rozšiřeni Automatové knihovny.

Paralelní vyhledávání repetic v grafech

Autor
Jiří Stránský
Rok
2016
Typ
Diplomová práce
Vedoucí
RNDr. Tomáš Valla, Ph.D.
Oponenti
RNDr. Ondřej Suchý, Ph.D.
Anotace
Tato práce studuje takzvané vzorky v sítích. Vzorky v sítích jsou souvislé podgrafy v dané síti, které se vyskytují ve výrazně vyšších četnostech, než je očekávané v náhodných sítích. Jsou popsány různé přístupy pro hledání vzorků v sítích a na základě jejich analýzy je představen nový, vylepšený, paralelní algoritmus pro hledání vzorků v sítích, nazvaný Efise. Praktické výsledky ukazují, že Efise nabízí výrazně vyšší výkonnost než ostatní nástroje. Díky efektivní metodě paralelizace dosahuje Efise lineárního zrychlení a dokáže hledat vzorky v sítích řádově rychleji než doposud nejrychlejší nástroje.