Závěrečné práce

Ryan Michael Culpepper

doc. Ing. Filip Křikava, Ph.D.

Katedra teoretické informatiky

Tato práce se věnuje implementaci funkcionálního, staticky typovaného programovacího jazyka inspirovaného jazykem Haskell. Hlavním bodem zájmu práce je implementace typového systému pro tento jazyk. Implementace vychází z několika zdrojů zabývajících se implementací konkrétních aspektů typového systému. Tato práce se také zabývá dalšími aspekty implementace programovacího jazyka--lexikální a syntaktickou analýzou, překladem do menšího funkcionálního jazyka a tzv. non-strict evaluací.

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. Petr Máj, Ph.D.

Ing. Tomáš Pecka

Katedra teoretické informatiky

Tato práce prezentuje tiny x86 architekturu a virtuální stroj, určené jako pomocný nástroj studentům k porozumění technikám kompilování a jejich dopad na výkon programu. V porovnání s již existujícími instrukčními sadami je tiny x86 jednodušší na použití, protože oproti binárnímu kódování nabízí aplikační rozhraní v jazyce C++ a nelimituje se na jeden návrh (jsou podporovány prvky CISC i RISC architektury). Prezentovaný virtuální stroj nabízí rozsáhle možnosti konfigurace, dovolující z(ne)výraznit různé návrhové prvky (počet registrů, odezvu paměti, trvání instrukcí atd.). Virtuální stroj je již nasazen v předmětu NI-GEN (generování kódu) na FIT ČVUT, kde jeho jednoduchost dovoluje studentům během semestru psát kompletní kompilátor.

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

prof. Ing. Jan Holub, Ph.D.

Ing. Petr Procházka, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

Ing. Petr Máj

Ing. Tomáš Zahradnický, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

doc. Dipl.-Ing. Dr. techn. Stefan Ratschan

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

Katedra teoretické informatiky

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.

Ing. Tomáš Čejka, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

Ing. Petr Máj

Ing. Filip Křikava, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace

Ing. Jan Trávníček, Ph.D.

Ing. Radomír Polách

Katedra teoretické informatiky

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.

Práce na DSpace

prof. Ing. Jan Holub, Ph.D.

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

Katedra teoretické informatiky

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í.

RNDr. Tomáš Valla, Ph.D.

RNDr. Ondřej Suchý, Ph.D.

Katedra teoretické informatiky

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.

Práce na DSpace