|
|
Model theory and extremal combinatorics
Konečný, Matěj ; Hubička, Jan (advisor) ; Solecki, Slawomir (referee) ; Macpherson, Dugald (referee)
This thesis is concerned with combinatorial properties of homogeneous structures such as the Ramsey property, big Ramsey degrees, EPPA, and others. What these properties have in common is that, while being finitary problems on classes of finite structures, they are equivalent to various dynamical properties of automorphism groups of the cor- responding homogeneous structures. This thesis consists of an extended introduction to these areas, a list of open problems, and ten papers of which the author is a co-author, seven of which have been published at the time of writing this thesis, the other three have been submitted. The goal is to demonstrate that, at least on the combinatorial side of things, there are many interplays of these properties which can be (and have been) exploited to further each of the areas. 1
|
|
|
The Extension Property for Partial Automorphisms (EPPA) of Reducts of Relational Structures
Beliayeu, Mikhail ; Hubička, Jan (advisor) ; Konečný, Matěj (referee)
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
|
|
|
An alternative SSA construction algorithm for GCC
Kastl, Filip ; Hubička, Jan (advisor) ; Jambor, Martin (referee)
SSA form is a very important concept in compiler internal code representa- tion. Φ-functions are an integral part of SSA form. Braun, Buchwald, Hack, Leißa, Mallon and Zwinkau introduce a new algorithm for SSA construction and another related algorithm for reducing the number of Φ-functions. These algorithms are not yet implemented in the GCC compiler. Firstly, we introduce, implement and test a basic code generation API based on the SSA construction algorithm. We list the possible extensions and usecases of the API. Then we implement the Φ optimization as a standalone pass. We use it to measure the number of redundant Φ-functions produced by other GCC passes. Finally, we conclude that GCC would benefit from including both of these algorithms. 1
|
|
|
Improving loop optimization with histogram profiling
Kubánek, Ondřej ; Hubička, Jan (advisor) ; Jambor, Martin (referee)
Production compilers use numerous techniques to generate performant code. One such technique is Profile-guided optimization (PGO). The princi- ple of this technique is to insert instrumentation during compilation, gather information about program behaviour with training runs and use this infor- mation during recompilation to improve optimization. The thesis aims to improve the precision of Loop optimizations in GNU Compiler Collection (GCC) with PGO. Currently in GCC, only the average iteration count of a loop is known with PGO. This leads to inefficiencies in both the performance and size of the binary. We implement infrastructure for measuring more information about loop iterations and add new counters namely the histogram of iterations and his- togram of iterations modulo its size. With the histogram of iterations, we improve loop peeling and implement a new case of loop versioning optimiza- tion. This significantly improves the performance of the generated code with reasonable overhead.
|
|
|
Incremental link-time optimization in GNU Compiler Collection
Jireš, Michal ; Hubička, Jan (advisor) ; Jambor, Martin (referee)
Modern compilers attempt to optimize programs as much as possible. One such significant effort is Link-Time Optimization (LTO). LTO takes the whole program as accessible to a linker, and performs global optimizations that are impossible in previously local compilations. Because of the global nature, LTO must be performed in full in each compilation, which results in long compile times even in edit-compile cycles. Incremental compilation can reduce compile times of edit-compile cycles by reusing unchanged objects. This thesis aims to implement incremental compilation for Link-Time Optimizations of GNU Compiler Collection, specifically of local transformation phase. We implement incremental compilation by caching files of compilation units of local transformation. For best success of incremental compilation we also aim to minimize number of changed compilation units after small edit. We achieve this in two ways. First, we create better partitioning strategy, that concentrates the changes into fewer compilation units. Second, we analyzed sources of divergence and, if easily possible, removed them. That includes stabilizing values and fixing streaming and inter-procedural optimizations to increase their robustness against small edits. Both without influencing quality of the final binary. 1
|
|
|
Off-diagonal ordered Ramsey numbers
Poljak, Marian ; Balko, Martin (advisor) ; Hubička, Jan (referee)
We study ordered Ramsey numbers, an analogue of the classical Ramsey numbers for graphs with linearly ordered vertex sets. Inspired by a problem posed by Conlon, Fox, Lee and Sudakov, we focus on ordered Ramsey numbers of ordered matchings M< versus triangles. We generalize their lower bound on r<(M< , K< 3 ) for ordered matchings with any fixed interval chromatic number. We also analyze an upper bound on r<(M< , K< 3 ) for almost all ordered matchings M< with interval chromatic number 2 obtained by Rohatgi and improve it from O(n24/13 ) to O(n7/4 ). 1
|
|
|
Pattern matching in compilers
Bílka, Ondřej ; Hubička, Jan (advisor) ; Mareš, Martin (referee)
Title: Pattern matching in compilers Author: Ondřej Bílka Department: Department of Applied Mathematics Supervisor: Jan Hubička, Department of Applied Mathematics Abstract: In this thesis we develop tools for effective and flexible pattern matching. We introduce a new pattern matching system called amethyst. Amethyst is not only a generator of parsers of programming languages, but can also serve as an alternative to tools for matching regular expressions. Our framework also produces dynamic parsers. Its intended use is in the context of IDE (accurate syntax highlighting and error detection on the fly). Amethyst offers pattern matching of general data structures. This makes it a useful tool for implement- ing compiler optimizations such as constant folding, instruction scheduling, and dataflow analysis in general. The parsers produced are essentially top-down parsers. Linear time complexity is obtained by introducing the novel notion of structured grammars and reg- ularized regular expressions. Amethyst uses techniques known from compiler optimizations to produce effective parsers. Keywords: Packrat parsing, dynamic parsing, structured grammars, functional programming 1
|
|
|
Optimizing large applications
Liška, Martin ; Hubička, Jan (advisor) ; Mareš, Martin (referee)
Both uppermost open source compilers, GCC and LLVM, are mature enough to link-time optimize large applications. In case of large applications, we must take into account, except standard speed efficiency and memory consumption, different aspects. We focus on size of the code, cold start-up time, etc. Developers of applications often come up with ad-hoc solutions such as Elfhack utility, start-up of an application via a pre-loading utility and dlopen; prelinking and variety of different tools that reorder functions to fit the order of execution. The goal of the thesis is to analyse all existing techniques of optimization, evaluate their efficiency and design new solutions based on the link-time optimization platform. Powered by TCPDF (www.tcpdf.org)
|
|
|
Optimizations in the GNU Compiler Collection targeted at scientific computing
Jambor, Martin ; Hubička, Jan (advisor) ; Jelínek, Jakub (referee)
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.
|
|
|
Pre-press adjustment of documents
Šnupárek, Aleš ; Mareš, Martin (advisor) ; Hubička, Jan (referee)
In the present work I study printing formats (PDF, PostScript) and abilities of modifying already finished documents before printing. In the other part of my work I focus on commonly used tools for pre-print preparations of documents. Last part of my work is design and implementation of tool for pre-print preparations of documents.
|
guest ::
