|
|
Acceleration of Burrows-Wheeler Transform Using GPU
Zahradníček, Tomáš ; Drábek, Vladimír (referee) ; Šimek, Václav (advisor)
This thesis deals with Burrows-Wheeler transform (BWT) and possibilities of acceleration of this transform on graphics processing unit (GPU). Methods of compression based on BWT are introduced, as well as software libraries CUDA and OpenCL for writing programs for GPU. Parallel variants of BWT are implemented, as well as following steps necessary for compression, using CUDA library. Amount of compression of used approaches are tested and parallel versions are compared to their sequential counterparts.
|
|
|
Towards Efficient Parallel Data Processing on Modern Hardware
Falt, Zbyněk ; Yaghob, Jakub (advisor) ; Smrž, Pavel (referee) ; Benkner, Siegfried (referee)
Parallel data processing is a very hot topic in current research, since the amount of data and the complexity of the operations performed on them has been increasing significantly in the past few years. In this thesis, we focus on a specific domain of this research -- the design and implementation of parallel algorithms used mainly in database systems. First, we introduce important enhancements in the Bobox system, which is a framework for the development of parallel data processing applications. Then, we introduce a new domain specific language called Bobolang which makes the implementation of those applications easier. Next, we propose parallel and scalable algorithms used in the domain of databases, namely sort and merge join, and introduce their efficient implementation using the combination of Bobox and Bobolang. Finally, we introduce parallel runtime for SPARQL engine as an example of a parallel data processing application which demonstrates the main contributions of this thesis in complex and real-life situations. Powered by TCPDF (www.tcpdf.org)
|
|
|
Acceleration of Burrows-Wheeler Transform Using GPU
Zahradníček, Tomáš ; Drábek, Vladimír (referee) ; Šimek, Václav (advisor)
This thesis deals with Burrows-Wheeler transform (BWT) and possibilities of acceleration of this transform on graphics processing unit (GPU). Methods of compression based on BWT are introduced, as well as software libraries CUDA and OpenCL for writing programs for GPU. Parallel variants of BWT are implemented, as well as following steps necessary for compression, using CUDA library. Amount of compression of used approaches are tested and parallel versions are compared to their sequential counterparts.
|
|
|
Interactive Processing of Volumetric Data
Kolomazník, Jan ; Pelikán, Josef (advisor) ; Czanner, Silvester (referee) ; Dokládal, Petr (referee)
Title: Interactive Processing of Volumetric Data Author: Jan Kolomazník Department: Department of Software and Computer Science Education Supervisor: RNDr. Josef Pelikán, Department of Software and Computer Science Education Abstract: Interactive visualization and segmentation of volumetric data are quite lim- ited due to the increased complexity of the task and size of the input data in comparison to two-dimensional processing. A special interactive segmentation workflow is presented, based on minimal graph-cut search. The overall execution time was lowered by implementing all the computational steps on GPU, which required a design of massively parallel algorithms (using thousands of threads). To lower the computational burden even further the graph is constructed over the image subregions com- puted by parallel watershed transformation. As a suitable formalism for a range of massively parallel algorithms was chosen cellular automata. A set of cellular automata extensions was defined, which allows efficient mapping and computation on GPU. Several variants of parallel watershed transformation are then defined in the form of cellular automaton. A novel form of 2D transfer function was presented, to improve direct volume visualization of the input data, suited for discriminating image features by their shape and...
|
|
|
Towards Efficient Parallel Data Processing on Modern Hardware
Falt, Zbyněk ; Yaghob, Jakub (advisor) ; Smrž, Pavel (referee) ; Benkner, Siegfried (referee)
Parallel data processing is a very hot topic in current research, since the amount of data and the complexity of the operations performed on them has been increasing significantly in the past few years. In this thesis, we focus on a specific domain of this research -- the design and implementation of parallel algorithms used mainly in database systems. First, we introduce important enhancements in the Bobox system, which is a framework for the development of parallel data processing applications. Then, we introduce a new domain specific language called Bobolang which makes the implementation of those applications easier. Next, we propose parallel and scalable algorithms used in the domain of databases, namely sort and merge join, and introduce their efficient implementation using the combination of Bobox and Bobolang. Finally, we introduce parallel runtime for SPARQL engine as an example of a parallel data processing application which demonstrates the main contributions of this thesis in complex and real-life situations. Powered by TCPDF (www.tcpdf.org)
|
|
|
A parallel finite element solver for unsteady incompressible Navier-Stokes equations
Šístek, Jakub
A parallel solver for unsteady incompressible Navier-Stokes equations is presented. It is based on the finite element method combined with the pressure-correction approach. Semi-implicit treatment of the convective term is considered, leading to five systems of linear algebraic equations to be solved in each time step. Krylov subspace iterative methods are employed for the solution of these systems with a particular emphasis on efficient parallel preconditioners. A simulation of a benchmark problem of incompressible viscous flow around a sphere at Reynolds number 300 is presented and compared with literature.
|
|
| |
|
|
Solving the combinatorial optimization problems with the Ant Colony Optimization metaheuristic method
Chu, Andrej ; Jablonský, Josef (advisor) ; Janáček, Jaroslav (referee) ; Linda, Bohdan (referee)
The Ant Colony Optimization belongs into the metaheuristic methods category and it has been developing quite recently. So far it has shown its capabalities to over-perform other metaheuristic methods in quality of the solutions. This work brings analysis of the possible applications of the method on the classical optimization combinatorial problems -- traveling salesman problem, vehicle routing problem, knapsack problem, generalized assignment problem and maximal clique problem. It also deals with the practical experiments with application on several optimization problems and analysis of the time and memory complexity of such algorithms. The last part of the work is dedicated to the possibility of parallelization of the algorithm, which was result of the application of the ACO method on the traveling salesman problem. It brings analysis of the crucial operations and data synchronization issues, as well as practical example and demonstration of the parallelized version of the algorithm.
|
|
| |
|
| |
guest ::
