|
|
Meeting the challenges of k-nearest neighbor search implementation for GPU accelerators
Hanák, Drahomír ; Kruliš, Martin (advisor) ; Yaghob, Jakub (referee)
Similarity search is a commonly used technique in databases for finding objects si- milar to a query. It finds applications in content-based retrieval of complex objects like images, information retrieval, and statistical learning. Our thesis focuses on the imple- mentation and optimization of the k nearest neighbours (kNN) algorithm on a GPU, a commonly used technique in similarity search. We analyze and evaluate several existing GPU kNN implementations in various configurations and propose the best algorithm for each configuration. We also suggest optimizations of k-selection. In particular, we suggest a small k-selection approach, which achieves up to 80% of peak theoretical throughput on a typical configuration used in many applications of kNN and is faster than the current state-of-the-art. We implemented a fused algorithm, which solves kNN without mate- rializing the distance matrix, and a large k-selection, which outperforms an optimized, parallel sorting of the whole database by a significant margin. 1
|
|
|
Convergent Real-Time Collaborative Document Editor and Repository
Kloda, Vojtěch ; Kruliš, Martin (advisor) ; Zavoral, Filip (referee)
Online document editors are useful tools that allow users to create, edit, and often also store and share documents. Some editors additionally support collaborative real-time editing for multiple users, allowing them to get live feedback from others. Collaborative editors need to face the issue of conflicting user changes. To avoid desynchronization, such editors need to be able to resolve conflicts in a consistent way at the site of each user. To do so, editors use the technology of operational transformation, which proposes a series of complex algorithms aiming to achieve consistency. The goal of this thesis is to develop a collaborative editor and repository prototype which is able to automatically resolve conflicting user changes and support large numbers of active users. To achieve this, a new theory for handling consistency is devised from an existing one by introducing a set of constraints to improve scalability. 1
|
|
|
Extension of web-based interface for protein binding sites prediction
Polák, Lukáš ; Hoksza, David (advisor) ; Kruliš, Martin (referee)
Protein-ligand binding sites are positions on the protein structure where the protein interacts with other molecules. PrankWeb is a web server devel- oped at MFF UK allowing prediction of such places. These predictions are essential in fields such as bioengineering and computational drug discovery. The goal of this thesis was to update this web server, i.e., replace old and unsupported components with new ones. Another goal was to extend the server architecture to enable the simple addition of modules for the postpro- cessing of the predicted binding sites. These modules can be implemented either on the client side in case of simple computations, or on the server side in case of complex computations. As part of the thesis, we have implemented a client module for computing the volume of active sites and a server module allowing the docking of small proteins into predicted binding sites. The the- sis describes not only the interventions in the architecture but also provides a short introduction to the problem of protein-ligand binding sites and their prediction.
|
|
|
Accelerating cross-correlation with GPUs
Maděra, Karel ; Kruliš, Martin (advisor) ; Horáček, Jan (referee)
Cross-correlation is a commonly used tool in the field of signal processing, with ap- plications in pattern recognition, particle physics, electron tomography, and many other areas. For many of these applications, it is often the limiting factor on system perfor- mance due to its computational complexity. In this thesis, we analyze the cross-correlation algorithm and its optimization and parallelization possibilities. We then implement sev- eral optimizations of the definition-based algorithm, mainly focused on parallelization using the Graphical processing unit (GPU). Even though the definition-based algorithm provides many possibilities for parallelization, the implementation needs to solve several problems, such as the algorithm's low arithmetic intensity. Furthermore, the problems differ between computation types, which include cross-correlating a pair of inputs, one in- put with many other inputs, or many inputs with many other inputs. Lastly, we compare the optimizations of the definition-based algorithm with the asymptotically faster and commonly used algorithm based on the Fast Fourier Transform. Depending on the total size of the data, we achieve parity between the two algorithms for matrix sizes ranging from 60x60 to 150x150, allowing performance improvements for systems using matrices smaller...
|
|
|
Number recognition on digital displays using Axis cameras' CPU
Kaifer, Jan ; Šikudová, Elena (advisor) ; Kruliš, Martin (referee)
Práce se zabývá implementací aplikace pro kamery AXIS, která rozpoznává digitální čísla na tabulích ve sportovních halách. Existuje mnoho algoritmů pro rozpoznávání čísel, ale velmi málo z nich je dostatečně efektivních, aby je bylo možné spustit přímo na kameře bez dedikovaného výpočetního akcelerátoru. Aplikace provádí detekci pomoci neuronových sítí a s nimi se nám povedlo dosáhnout velmi dobrých výsledků, díky kterým je možné aplikaci využít v produkčním prostředí. Mimo neuronové sítě práce také popisuje naivní algoritmus postavený na technikách počítačového vidění. 1
|
|
|
Software pro rozvrhování operací a evidence nástrojů pro nemocniční zařízení
Tupec, Pavel ; Šerý, Ondřej (advisor) ; Kruliš, Martin (referee)
Nowadays in most medical facilities is daily schedule of operations mainly created manually or with minimal support of software tools. Result of this is occasional ineffectivity of operation schedule and primarily huge time consumption for surgery chief who could use his time for more important things related to his work. Another reason for creating this application is that information about patients, operations, wards and diagnosis are stored decentralized in different applications and systems, which makes working with them more difficult. Target of this application is implementation application for creating operating schedules in hospital facilities with assurance of necessary instruments, wards and instrument evidence. Where all data about all necessary entities will be stored and managed centralized. Purpose of final program is make schedule creating more effective and partially automatized operation planning.
|
|
|
Routing policies and real paths in the Internet
Hlaváček, Tomáš ; Peterka, Jiří (advisor) ; Kruliš, Martin (referee)
Routing policies are now represented by RPSL and by its evolutionary extension called RPSLng. These languages can be used for describing unique routing policy of each autonomous system. Experience shows that even though there are translation tools from RPSL and RPSLng to configuration formats of commonly used routers, the actual network configuration is rarely generated from RPSL sources and routing policy is then perceived as marginal paperwork, which often does not reflect the real network settings. There will be most likely a need for RPSL format change in order to remedy the discrepancies. To support this I present long-term measurements of inaccuracies in routing policies compared to real paths in the Internet. I also present a list of the most frequent problems, and I offer suggestions, how to reform RPSL to improve situation in the long term. Powered by TCPDF (www.tcpdf.org)
|
|
|
Enhanced Editor of MEF Component Architectures
Vodolán, Miroslav ; Ježek, Pavel (advisor) ; Kruliš, Martin (referee)
Managed Extensibility Framework allows development of component-based .NET applications. However relations between components can be quite complex. Therefore the MEF Editor was implemented in context of author's bachelor thesis, which can visualise the relations according to source code analysis and provide their editing. Although possibilities of the analysis are determined by available user's extensions, in some cases the editor cannot be used. This master thesis provides a solution in form of a new version of the MEF Editor which increases the number of cases it can be used in. As part of this thesis, we implemented the editor with extensions allowing analysis of application projects written in C# language and compiled assemblies. It helps to detect composition errors in these applications and allows visual editing of source code where component architecture of these applications is implemented. Powered by TCPDF (www.tcpdf.org)
|
|
|
Vector editor for creating animations
Kruliš, Martin ; Zavoral, Filip (advisor) ; Parízek, Pavel (referee)
The object of this work is to design and implement a vector editor with animation support. This program is designated for a very specialized group of users that want to create simple animations but find buying complex commercial tools unnecessary. The application will allow user to design basic vector objects, edit them and set them into motion using curved trajectories. Main features of the application are its modularity and flexibility, making it ready for future extending and customization.
|
|
|
Environment for distributed computations
Dědeček, Jan ; Žemlička, Michal (advisor) ; Kruliš, Martin (referee)
In present work are analyzed possibilities of optimization special task. In this task is requested to generate all variants of word equal length n and test them by computation. The first part of work is analyzing possibility of precessing words more efficiently. Number of words is equal to 2n, then even for small lengths is not possible to compute task on one computer in satisfiable time. The advantage of this task is that computation of each word is independent, therefore task could be easily divided. The second part of work is analyzing possibility of dividing computing on multiple computers, so the overall time of computation is maximally decreased. Side way of this work is creation of distributive application.
|
guest ::
