|
|
Model theory and extremal combinatorics
Konečný, Matěj ; Hubička, Jan (vedoucí práce) ; Solecki, Slawomir (oponent) ; Macpherson, Dugald (oponent)
Tato disertační práce se zabývá kombinatorickými vlastnostmi homogenních struk- tur, jako je například Ramseyova vlastnost, velké ramseyovské stupně, EPPA a další. Tyto vlastností mají společné, že přestože jsou to vlastnosti tříd konečných struktur, jsou ekvivalentní různým dynamickým vlastnostem grup automorfismů příslušných ho- mogenních struktur. Tato práce sestává z rozšířeného úvodu do těchto oblastí, seznamu otevřených problémů a deseti článků, jejichž je autor spoluautorem. Sedm z nich bylo již v době psaní této disertace publikováno, zbylé tři byly odeslané do časopisů k recen- znímu řízení. Cílem práce je ukázat, že (alespoň na straně konečné kombinatoriky) mezi výše zmíněnými vlastnostmi je mnoho souvislostí, jichž lze využít pro posun příslušných oblastí. 1
|
|
|
The Extension Property for Partial Automorphisms (EPPA) of Reducts of Relational Structures
Beliayeu, Mikhail ; Hubička, Jan (vedoucí práce) ; Konečný, Matěj (oponent)
The Extension Property for Partial Automorphisms (EPPA), also called Hrusovski property, is a crucial concept in the realms of combinatorics, group theory, and model theory, linking the properties of structures and the classes of finitely generated substruc- tures that embed into them. The notion of EPPA, established by Hodges, Hodkinson, Lascar, and Shelah, has spurred significant advancements in understanding graph struc- tures and the automorphism groups associated with them. A milestone was achieved by Hrusovski, who demonstrated EPPA for the class of finite graphs. The research since has centered on categorizing more classes with EPPA, simplifying proof techniques, and understanding the broader implications of EPPA. This thesis contributes to this ongoing pursuit, specifically aiming to demonstrate EPPA for graph classes enriched by comple- mentary automorphisms. It includes an analysis of undirected and directed graphs with loops and extends the exploration to a class of general structures in a finite relational language. 1
|
|
|
Alternativní algoritmus stavby SSA formy pro GCC
Kastl, Filip ; Hubička, Jan (vedoucí práce) ; Jambor, Martin (oponent)
SSA forma je velice důležitý koncept týkající se interní reprezentace kódu v překladačích. Φ-funkce jsou nedílná součást SSA formy. Braun, Buchwald, Hack, Leißa, Mallon a Zwinkau představují nový algoritmus pro stavbu SSA a společně s ním také algoritmus redukující množství Φ-funkcí. V GCC zatím tyto algoritmy nebyly implementovány. V této práci nejprve představíme, naimplementujeme a otestujeme základní API určené pro generování kódu, které je založené na zmíněném algoritmu pro stavbu SSA. Následně předvedeme možnosti využití tohoto API a uvedeme jeho možná rozšíření. Poté naimplementujeme algoritmus pro optimalizaci Φ- funkcí. Pomocí tohoto algoritmu změříme, kolik redundantních Φ-funkcí pro- dukují GCC optimalizační průchody. Na základě získaných poznatků nakonec dojdeme k závěru, že by bylo užitečné tyto algoritmy do GCC přidat. 1
|
|
|
Optimalizace smyček pomocí histogramu
Kubánek, Ondřej ; Hubička, Jan (vedoucí práce) ; Jambor, Martin (oponent)
Produkční překladače používají mnoho různých technik optimalizace kódu. Jedna taková technika je Profile-guided optimization (PGO). Princip této techniky je, že během překládání programu je do něj vložena instrumentace, uživatel změří jeho chování pomocí testovacího běhu a při druhém překladu jsou změřená data použita ke zlepšení optimalizace. Cílem této práce je zlep- šit přesnost optimalizace smyček v GNU Compiler Collection (GCC) s PGO. Během PGO je aktuálně znám ve GCC pouze průměrný počet iterací dané smyčky. To vede k neefektivním optimalizacím, jak co se týče výkonu, tak co se týče velikosti generovaného programu. Tato práce přidává infrastrukturu pro měření dalších vlastností smyček. Implementujeme histogram iterací smyčky a histogram iterací smyčky mo- dulo jeho velikostí. Pomocí histogramu iterací pak zlepšíme optimalizaci loop peeling a přidáme novou verzi optimalizace loop versioning. To podstatně zlepšuje výkon za přiměřenou cenu.
|
|
|
Incremental link-time optimization in GNU Compiler Collection
Jireš, Michal ; Hubička, Jan (vedoucí práce) ; Jambor, Martin (oponent)
Moderní překladače se snaží optimalizovat programy co nejvíc je možné. Jedna z významných snah jsou Link-Time Optimalizace (LTO). LTO vezme celý program jak je dostupný linkeru a provede globální optimalizace které jsou nemožné v předcháze- jících lokálních překladech. Kvůli globální povaze LTO musí být provedeno celé při každém překladu, což vede k dlouhým časům překladu i v případě cyklu změny-překladu. Inkrementální překlad může snížit časy překladu cyklů změny-překladu znovupoužitím nezměněných objektů. Tato práce má za cíl implementovat inkrementální překlad pro LTO v překladači GNU Compiler Collection, specificky pro fázi lokálních transformací. Implementujeme inkre- mentální kompilaci kešováním souborů z překladových jednotek lokální transformace. Pro nejlepší výsledky inkrementální kompilace máme také za cíl minimalizovat počet změněných překladových jednotek po malé změně. Toho dosáhneme dvěma způsoby. Za prvé vytvoříme lepší rozdělovací strategii, která bude koncentrovat změny do menšího počtu překladových jednotek. Za druhé analyzujeme zdroje divergence a, pokud je to jednoduše možné, odstraníme je. To zahrnuje stabilizaci hodnot a opravu streamování a mezi procedurální optimalizace pro zvýšení jejich odolnosti vůči malým změnám. V obou případech se nemění kvalita výsledného spustitelného souboru. 1
|
|
|
Off-diagonal ordered Ramsey numbers
Poljak, Marian ; Balko, Martin (vedoucí práce) ; Hubička, Jan (oponent)
V práci studujeme uspořádaná Ramseyova čísla, která jsou analogií klasických Ram- seyových čísel pro grafy s lineárně uspořádanými vrcholy. Motivováni problémem od autorů Conlon, Fox, Lee a Sudakov se zabýváme uspořádanými Ramseyovými čísly pro uspořádaná párování M< vůči trojúhelníku. Zobecníme jejich dolní odhad čísla r<(M< , K< 3 ) pro uspořádaná párování s libovolným pevně zvoleným intervalovým chro- matickým číslem. Také zlepšíme horní odhad čísla r<(M< , K< 3 ) pro téměř všechna uspořádaná párování s intervalovým chromatickým číslem 2, který dokázal Rohatgi, z O(n24/13 ) na O(n7/4 ). 1
|
|
|
Pattern matching in compilers
Bílka, Ondřej ; Hubička, Jan (vedoucí práce) ; Mareš, Martin (oponent)
Název práce: Pattern matching in compilers Autor: Ondřej Bílka Katedra: Katedra Aplikované Matematiky Vedoucí diplomové práce: Jan Hubička, Katedra Aplikované Matematiky Abstrakt: V této práci vyvineme nástroje na efektivní a flexibilní pattern matching. Představíme specializovaný programovací jazyk amethyst. Jedna z funkcí amethystu je generatování parserů. Také může sloužit jako alterna- tiva k regulárním výrazum. Naš systém umí generovat dynamické parsery. Jejich hlavní uplatnění je tvorba nástroju do IDE jako např. interaktivní zvýrazňovač syntaxe nebo detektor chyb. Amethyst umí zpracovávat i obecné datové struktury. Plánované využití je implementace kompilátorových optimal- izací jako napřiklad propagace konstant či rozvrhování instrukcí a jiné optimal- izace založené na dataflow analyze. Generované parsery jsou víceméně top-down parsery. Představíme nový algo- ritmus pro parsovaní strukturovaných gramatik v linearním čase. Amethyst používá techniky z kompilatorů pro optimalizovaní generovaných parserů. Klíčová slova: packrat parsování, dynamické parsování, strukturované gramatiky, funkcionální programování 1
|
|
|
Optimizing large applications
Liška, Martin ; Hubička, Jan (vedoucí práce) ; Mareš, Martin (oponent)
Oba hlavní open source překladače, GCC a LLVM, dnes dosahují stavu, kdy jsou schopny link-time optimalizovat velké aplikace. U rozsáhlých aplikací si nevystačíme jenom s klasickými měřítky výkonu jako je rychlost nebo paměťová náročnost. Zajímá nás typicky velikost kódu, doba studeného startu aplikace a podobně. Vývojáři těchto balíků tak často sahají k různým ad-hoc řešením, mezi které patří například utilita ElfHack, startování vlastních aplikaci pomocí předzavedené utility a dlopen, prelinking a různé nástroje pro přerovnání výsledného programu podle pořadí provádění funkcí. Práce si klade za cíl zmonitorovat dostupné techniky optimalizace, ocenit jejich účinnost a navrhnout nová řešení, postavená na platformě link-time optimalizací. Powered by TCPDF (www.tcpdf.org)
|
|
|
Optimalizace vědeckých výpočtů pro GNU Compiler Collection
Jambor, Martin ; Hubička, Jan (vedoucí práce) ; Jelínek, Jakub (oponent)
Many members of the scientific community look for alternatives to Fortran to increase maintainability, reusability and interoperability of their projects and component and to achieve rapid development and deployment. C++ appears to be an ever more appealing alternative because evolving compilers and coding techniques continually boost the efficiency of the resultant code. This work describes what C++ scientific code typically looks like, and discuses a number of contemporary optimizing techniques compilers use to remove overhead caused by levels of abstraction. Moreover, it proposes a new Intraprocedural Analysis of Aggregates to expose even more information stored within objects and track object behaviour. It also describes implementation of intraprocedural propagation of constants within aggregates built on top of this analysis. Finally, it discusses its efficiency and potential for future work.
|
|
|
Předtisková příprava dokumentů
Šnupárek, Aleš ; Mareš, Martin (vedoucí práce) ; Hubička, Jan (oponent)
V předložené práci se zabýváme některými tiskovými formáty (PDF, PostScript) a možností úprav hotových dokumentů před samotným tiskem. Dále zkoumám současné nástroje pro dané úpravy. V části se zabývám návrhem a realizací nástroje, který umožňuje provádět některé ze základních předtiskových úprav.
|
host ::
RSS.