Theses

Ryan Michael Culpepper

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

Department of Theoretical Computer Science

This thesis presents an implementation of a functional, statically typed programming language inspired by Haskell. It mainly focuses on the challenges of implementing the type system for such an language. The implementation is based on multiple resources covering implementations of different type system features. The thesis also covers other aspects of the language implementation--lexical and syntactic analysis, translation into a smaller functional core language, and non-strict evaluation.

Thesis on DSpace

Ing. Daniel Langr, Ph.D.

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

Department of Theoretical Computer Science

Frequent heap allocations can have a significant impact on the overall performance of a program. The problem becomes even more critical in multithreaded applications, where too many interactions with heap can grow into the main bottleneck and effectively diminish scalability. Profiling such applications with existing heap profilers is almost impossible due to the enormous runtime overhead they add. This thesis describes the typical memory layout of a Linux process, briefly shows the internals of the GNU C memory allocator, analyzes available heap profiling tools, and guides the reader through the process of constructing a~custom heap profiler. Further, the thesis proposes a concept of low-latency heap profiling. Based on that, a new profiler Heaprof has been developed and compared with other heap profiling tools. Experimental results revealed that Heaprof was the only tool capable of profiling without further compromising the program's scalability. For 8-threaded benchmarks, Heaprof achieved up to 8 times profiling speedup.

Thesis on DSpace

Ing. Petr Máj, Ph.D.

Ing. Tomáš Pecka

Department of Theoretical Computer Science

This thesis presents tiny x86 architecture and virtual machine designed to help students understand various compiler techniques and their effect on the program performance. Compared to existing instruction set architectures, tiny x86 is simpler, easier to use as it comes with a C++ API as opposed to binary encodings and does not limit itself to single design principles (both CISC and RISC features are supported). The VM also offers extensive configuration options, allowing it to (de-)emphasize various architecture features (register pressure, memory latency, instruction timings, etc.). The VM is already used in the NI-GEN (Code Generation) course at FIT CTU, where its simplicity allows the students to write full compiler pipeline during the term.

Thesis on DSpace

Ing. Daniel Langr, Ph.D.

Ing. Jiří Kašpar

Department of Theoretical Computer Science

An automatic memoization system - also known as a software cache - stores a limited number of recently accessed elements and speeds up consequent accesses to them. Least-Recently-Used (LRU) is a popular replacement policy for hardware and software caches. However, its concurrent implementation suffers from high contention due to the list reordering performed both on lookup and insertion. A novel LRU-inspired concurrent software cache, called DeferredLRU, is presented in this thesis. The main goal of the design was to make it scalable and suitable for many-core systems. These properties were achieved by using a different approach to tracking item access order. This approach substantially decreases the number of list reinsertions --- the main factor of the contention in a regular LRU cache. DeferredLRU throughput and hit-rate are sensitive to the meta-parameter setting. By fine-tuning meta parameters for specific inputs, it was possible to achieve higher hit-rate than of a regular LRU cache for every tested input. The relative difference was up to 7.8%. DeferredLRU performance was compared to existing alternatives, including corresponding caches from Intel TBB and Facebook HHVM projects. Tested caches were evaluated with up to 32 threads (on a 16 HW cores CPU). In 32 threads evaluation, DeferredLRU was faster in all 16 tests. When accesses were distributed among multiple smaller caches for better parallelism (this approach is called binning), DeferredLRU was faster in 11 of 16 tests and was close to best-performing caches in 5 other tests. DeferredLRU with binning was up to 28.8 times faster on 32 threads compared to single-threaded performance.

Thesis on DSpace

prof. Ing. Jan Holub, Ph.D.

Ing. Petr Procházka, Ph.D.

Department of Theoretical Computer Science

This thesis presents a slightly different approach to the PPM compression algorithm based on the succinct de Bruijn graphs. It uses dynamic bit vectors, and wavelet trees merged into a single tree to create a high performance dynamic succinct data structure capable of representing graphs used by the compressor. Even though the compressor is slow compared to other widely used compressors, it achieves good compression ratios while using much less memory.

Thesis on DSpace

Ing. Petr Máj

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

Department of Theoretical Computer Science

Released in 2014, Swift quickly become one of the fastest growing programming languages, and, in addition to its original field of use in application development, is finding its place on servers and recently also in data science. However, no work has been published regarding the use of Swift on the smallest computers with highly-constrained resources - embedded systems. This thesis aims to be the first step in extending Swift's possibilities towards this segment. It describes the process of adding support for a new bare-metal platform to the Swift compiler and its related tools. As a result, Swift is presented as a viable alternative to existing embedded platforms.

Thesis on DSpace

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

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

Department of Theoretical Computer Science

This thesis deals with the problem of characterizing the sets of points ${p\in P}$, for which there exists a real-valued solution $x$ to a given parametric system of equations $f_P(x,p)=0$, where $f_P\colon X\subseteq\Rsetn{n}\to\Rsetn{n}$ is a continuous function formed by arithmetical expressions and $X$ is a box (product of closed real intervals). A branch and bound like algorithm based on interval arithmetics and a solution existence test using Brouwer's topological degree is designed and implemented. It allows several ways of manipulating the domain $X$ and further parametrization of its operation. Interval arithmetics is used for computing estimates of function images, as well as for providing robustness with respect to rounding errors. The implementation is provided in a form of self-contained application including a user interface (both text-based and graphical). Based on results of the experiments, that are stored in scripts for an easy reproducibility, our implementation is capable of producing quality results and terminate in reasonable time for various non-linear systems up to three equations, possibly containing combinations of elementary functions like $\exp$, $\log$, $\sin$, $\cos$, $\arcsin$, $\arccos$, $n$-th root, $\dots$. We also enhance previous work related to the practical computation of the topological degree by describing and using a custom sound method of determining, if for arbitrary boxes $X'\subseteq X$, $P'\subseteq P$, the degree $\tdeg(f_p, X', 0)$ is defined and has the same value for every $p\in P'$.

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

Department of Theoretical Computer Science

As the speed and the size of computer networks grow, monitoring systems have to process increasing volume of data. Moreover, because of various kinds of security threats, all data must be processed by many detection methods at the same time with limited computational resources. Therefore, it is necessary to develop scalable solutions of monitoring systems allowing for parallel processing huge volume of data. This thesis uses modular and open-source system NEMEA for research in the field of parallel processing. The thesis deals with design, implementation and testing of NEMEA system extension, that allows for deployment in distributed environment. The extension increases throughput of the system using parallel processing. The paralelization is done by splitting a stream of flow records among computational nodes. Working prototype is implemented as a NEMEA module. The thesis further describes a testing environment used for experiments verifying the characteristics of the working prototype. All experiments were performed using real data traces from NREN CESNET2. The thesis is concluded by introducing a scalable architecture of parallel processing using NEMEA system.

Thesis on DSpace

Ing. Petr Máj

Ing. Filip Křikava, Ph.D.

Department of Theoretical Computer Science

R is a dynamic programming language that, despite being over 20 years old, is still widely used. RIR is an alternative to its bytecode compiler and interpreter that aims to facilitate adding static analyses and optimization passes easily. RIR is under development and does not currently match the performance of standard R. This thesis attempts to amend the situation. It extends the RIR internal representation, adds new features to its compiler and refactors its interpreter. The average slowdown versus standard R is brought down by about one half in the Shootout benchmarks.

Thesis on DSpace

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

Ing. Radomír Polách

Department of Theoretical Computer Science

This thesis studies regular tree expressions, a formalism for describing regular tree languages. Main topic of this thesis is a new algorithm for converting a regular tree expression to a pushdown automaton recognizing trees in their linear postfix notation. Resulting pushdown automaton is real-time height-deterministic, i.e., it can always be determinised. The algorithm for conversion is an adaptation of Glushkov's algorithm for converting a regular expression to a nondeterministic finite automaton. C++ implementation of the algorithm is attached as an extension of Automata Library.

Thesis on DSpace

prof. Ing. Jan Holub, Ph.D.

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

Department of Theoretical Computer Science

This thesis deals with the parallel lossless data compression, focusing on the usage of a graphics processing unit (GPU). It gives an introduction to data compression and parallel architectures and technologies. It contains a survey of parallel lossless data compressors for multiple platforms, including GPUs. The main contribution of the thesis is an improved implementation of PMLZSS, which is a dictionary data compression method for GPUs based on LZSS by Bin Zhou, Hai Jin and Ran Zheng from 2015. All the technological and algorithmic improvements are described and evaluated. Experiments are performed to compare the implementation with a sequential implementation of LZSS and with existing parallel solutions for multi-core processors and GPUs. The implementation is 9.4 to 22 times faster than the sequential solution while achieving comparable quality of compression. It is the fastest method for compressing binaries, documents or spreadsheets among measured solutions.

RNDr. Tomáš Valla, Ph.D.

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

Department of Theoretical Computer Science

This thesis studies so-called network motifs. Network motifs are connected subgraphs of a given network that occur in significantly higher frequencies than would be expected in random networks. Different approaches to finding network motifs are described and based on their analysis a new improved parallel algorithm for finding network motifs called Efise was introduced. Practical results show, that Efise offers significantly better performance than other tools and thanks to efficient parallelization method, it also achieves linear speedups, which makes it an order of magnitude faster than previous state-of-the-art tools for finding network motifs.

Thesis on DSpace