|
Analysis and Testing of Concurrent Programs
Letko, Zdeněk ; Lourenco, Joao (oponent) ; Sekanina, Lukáš (oponent) ; Vojnar, Tomáš (vedoucí práce)
The thesis starts by providing a taxonomy of concurrency-related errors and an overview of their dynamic detection. Then, concurrency coverage metrics which measure how well the synchronisation and concurrency-related behaviour of tested programs has been examined are proposed together with a~methodology for deriving such metrics. The proposed metrics are especially suitable for saturation-based and search-based testing. Next, a novel coverage-based noise injection techniques that maximise the number of interleavings witnessed during testing are proposed. A comparison of various existing noise injection heuristics and the newly proposed heuristics on a set of benchmarks is provided, showing that the proposed techniques win over the existing ones in some cases. Finally, a novel use of stochastic optimisation algorithms in the area of concurrency testing is proposed in the form of their application for finding suitable combinations of values of the many parameters of tests and the noise injection techniques. The approach has been implemented in a prototype way and tested on a set of benchmark programs, showing its potential to significantly improve the testing process.
|
|
Relational Verification of Programs with Integer Data
Konečný, Filip ; Bouajjani, Ahmed (oponent) ; Jančar, Petr (oponent) ; Vojnar, Tomáš (vedoucí práce)
This work presents novel methods for verification of reachability and termination properties of programs that manipulate unbounded integer data. Most of these methods are based on acceleration techniques which compute transitive closures of program loops. We first present an algorithm that accelerates several classes of integer relations and show that the new method performs up to four orders of magnitude better than the previous ones. On the theoretical side, our framework provides a common solution to the acceleration problem by proving that the considered classes of relations are periodic. Subsequently, we introduce a semi-algorithmic reachability analysis technique that tracks relations between variables of integer programs and applies the proposed acceleration algorithm to compute summaries of procedures in a modular way. Next, we present an alternative approach to reachability analysis that integrates predicate abstraction with our acceleration techniques to increase the likelihood of convergence of the algorithm. We evaluate these algorithms and show that they can handle a number of complex integer programs where previous approaches failed. Finally, we study the termination problem for several classes of program loops and show that it is decidable. Moreover, for some of these classes, we design a polynomial time algorithm that computes the exact set of program configurations from which nonterminating runs exist. We further integrate this algorithm into a semi-algorithmic method that analyzes termination of integer programs, and show that the resulting technique can verify termination properties of several non-trivial integer programs.
|
|
Důvěra a reputace v distribuovaných systémech
Samek, Jan ; Návrat,, Pavol (oponent) ; Šafařík,, Jiří (oponent) ; Hanáček, Petr (vedoucí práce)
Tato disertační práce se zabývá problematikou modelování důvěry v distribuovaných systémech, konkrétně pak více-kontextové důvěry v distribuovaných multi-agentních systémech. V současné době existuje velké množství modelů důvěry či reputace, nicméně více-kontextová vlastnost důvěry či reputace v nich není často zohledněna. Z tohoto důvodu se práce zaměřuje především na analýzu více-kontextových modelů založených na důvěře a na jejím základě stanovuje předpoklady pro nový, vlastnost více-kontextovost plně podporující, model důvěry. Stěžejní částí práce je formální návrh nového více-kontextového modelu důvěry, který je schopen vytvářet, aktualizovat a uchovávat důvěru pro různé aspekty (kontexty) jedné entity multi-agentního systému. Důvěru lze v navrženém modelu budovat jak na základě přímých zkušeností, tak i na základě doporučení a reputace. Dalším aspektem navrženého modelu je schopnost odvozovat důvěru v různé kontexty na základě znalosti důvěry v kontexty jiné, což je zajištěno vytvořením hierarchické struktury jednotlivých kontextů jedné entity. Přínosem nového modelu je především zvýšení efektivity rozhodování agentů v rámci multi-agentního systému ve smyslu schopnosti výběru optimálního partnera pro provedení transakce. Návrh modelu byl ověřen implementací prototypu multi-agentního systému, ve kterém se agenti rozhodují a jednají na základě důvěry.
|
|
Acceleration Methods for Evolutionary Design of Digital Circuits
Vašíček, Zdeněk ; Miller, Julian (oponent) ; Zelinka,, Ivan (oponent) ; Sekanina, Lukáš (vedoucí práce)
Although many examples showing the merits of evolutionary design over conventional design techniques utilized in the field of digital circuits design have been published, the evolutionary approaches are usually hardly applicable in practice due to the various so-called scalability problems. The scalability problem represents a general problem that refers to a situation in which the evolutionary algorithm is able to provide a solution to a small problem instances only. For example, the scalability of evaluation of a candidate digital circuit represents a serious issue because the time needed to evaluate a candidate solution grows exponentially with the increasing number of primary inputs. In this thesis, the scalability problem of evaluation of a candidate digital circuit is addressed. Three different approaches to overcoming this problem are proposed. Our goal is to demonstrate that the evolutionary design approach can produce interesting and human competitive solutions when the problem of scalability is reduced and thus a sufficient number of generations can be utilized. In order to increase the performance of the evolutionary design of image filters, a domain specific FPGA-based accelerator has been designed. The evolutionary design of image filters is a kind of regression problem which requires to evaluate a large number of training vectors as well as generations in order to find a satisfactory solution. By means of the proposed FPGA accelerator, very efficient nonlinear image filters have been discovered. One of the discovered implementations of an impulse noise filter consisting of four evolutionary designed filters is protected by the Czech utility model. A different approach has been introduced in the area of logic synthesis. A method combining formal verification techniques with evolutionary design that allows a significant acceleration of the fitness evaluation procedure was proposed. The proposed system can produce complex and simultaneously innovative designs, overcoming thus the major bottleneck of the evolutionary synthesis at gate level. The proposed method has been evaluated using a set of benchmark circuits and compared with conventional academia as well as commercial synthesis tools. In comparison with the conventional synthesis tools, the average improvement in terms of the number of gates provided by our system is approximately 25%. Finally, the problem of the multiple constant multiplier design, which belongs to the class of problems where a candidate solution can be perfectly evaluated in a short time, has been investigated. We have demonstrated that there exists a class of circuits that can be evaluated efficiently if a domain knowledge is utilized (in this case the linearity of components).
|
|
Point to Line Mappings and Other Line Parameterizations not only for Hough Transform
Havel, Jiří ; Kälviäinen, Heikki (oponent) ; Lefevre, Sebastien (oponent) ; Herout, Adam (vedoucí práce)
This works focuses on the Hough transform (HT). The HT is mostly used for the detection of lines or curves, but was also generalized for detection of arbitrary shapes. The main theme of this work are line parameterizations, especially the Point-to-Line mappings. These parameterizations share the property, that a point in the image maps onto a line in the parameter space. This work presents proofs of some properties of PTLMs, notably the existence of a practical pair of PTLMs for line detection and the effect of a convolution in the image space on the contents of the parameter space. Two realtime implementations of HT are presented in this work. Both accelerate HT using graphical hardware. One uses GPGPU API CUDA and the other the rendering API OpenGL. As an application of the line detection, this work describes part of the detection of checkerboard marker usable for the augmented reality.
|
| |
|
Sharing Local Information for Faster Scanning-Window Object Detection
Hradiš, Michal ; Kälviäinen, Heikki (oponent) ; Matas, Jiří (oponent) ; Zemčík, Pavel (vedoucí práce)
This thesis aims to improve existing scanning-window object detectors by exploiting information shared among neighboring image windows. This goal is realized by two novel methods which are build on the ideas of Wald's Sequential Probability Ratio Test and WaldBoost. Early non-Maxima Suppression moves non-maxima suppression decisions from a post-processing step to an early classification phase in order to make the decisions as soon as possible and thus avoid normally wasted computations. Neighborhood suppression enhances existing detectors with an ability to suppress evaluation at overlapping positions. The proposed methods are applicable to a wide range of detectors. Experiments show that both methods provide significantly better speed-precision trade-off compared to state-of-the-art WaldBoost detectors which process image windows independently. Additionally, the thesis presents results of extensive experiments which evaluate commonly used image features in several detection tasks and scenarios.
|
|
Multimedia Data Processing in Heterogeneous Distributed Environment
Kajan, Rudolf ; Ferko,, Andrej (oponent) ; Míkovec, Zdeněk (oponent) ; Herout, Adam (vedoucí práce)
Ubiquitous computing, a paradigm in which the processing of information is linked with each activity or object as encountered, was proposed by Mark Weiser as the next era for interacting with computers. Its goal is to enable people to interact with devices more naturally and casually in ways that suit whatever location or context they find themselves in. Ubiquitous computing focuses on learning by removing the complexity of computing and increases efficiency while using computing for different daily activities. But after more than 15 years since Weiser formulated these goals, several aspects of ubiquitous computing are still not a part of user experience with today’s technology. Seamless integration with environment leading to technological invisibility or user interaction spanning across multiple devices pose still a great challenge. The main goal of our work is to make a step towards making the idea of ubiquitous computing a reality by addressing the question about intuitive information sharing between a personal device and a situated display. We have developed three interaction techniques which support unobtrusive content exchange between touch-enabled personal device and a large display - whether it is shared-private or public. These techniques are based on video streams, augmented reality, and analysis of gaze data. Besides the interaction techniques, we also present a framework for real-time application state acquisition and reconstruction on target platform. We report on user studies focused on the usability of our prototypes and a system performance evaluations. Our experiments were formed around real-life scenarios which are commonly experienced throughout the day. For interactions based on video streams, the results indicate that our techniques outperform the existing solutions: the localization and task migration is done in real time on a midlevel cellphone; the localization is reliable even for different observation angles and for cluttered screen content. Our technique based on gaze analysis goes even further by allowing for modeling of implicit user preferences through gaze data, while being accurate and unobtrusive.
|
|
Metodologie pro návrh číslicových obvodů se zvýšenou spolehlivostí
Straka, Martin ; Gramatová, Elena (oponent) ; Racek, Stanislav (oponent) ; Kotásek, Zdeněk (vedoucí práce)
Práce představuje alternativní metodiku k již existujícím technikám pro návrh číslicových systémů se zvýšenou spolehlivostí implementovaných do obvodů FPGA a doplňuje některé nové vlastnosti při realizaci a testování těchto systémů. Práce se opírá o využití částečné dynamické rekonfigurace obvodu FPGA při návrhu systémů odolných proti poruchám, kde může být částečná rekonfigurace využita jako mechanizmus pro opravu a zotavení systému po výskytu poruchy. Práce nejprve představuje obecné principy diagnostiky, testování a spolehlivosti číslicových systémů včetně stručného popisu programovatelných obvodů FPGA a jejich architektury. Dále pokračuje přehledem současných metod a technik při návrhu a implementaci systémů odolných proti poruchám do obvodů FPGA, kde jsou popsány zejména techniky z oblasti detekce a lokalizace poruch, opravy a posuzování kvality návrhu. Nejdůležitější částí práce je popis metodiky pro návrh, implementaci a testování systémů odolných proti poruchám, která byla vytvořena pro obvody FPGA, jejichž konfigurační paměť je založena na pamětech typu SRAM. Nejprve je prezentována technika pro vytváření a automatizované generování hlídacích obvodů pro číslicové systémy a komunikační protokoly v FPGA, následně je prezentovaná referenční architektura spolehlivého systému implementovaného do FPGA včetně několika odolných architektur využívajících principu částečné dynamické rekonfigurace jako mechanizmu opravy a zotavení po výskytu poruchy. Dále je popsán způsob řízení rekonfiguračního procesu a testovací platforma pro snadné testovaní a ověření kvality systémů odolných proti poruchám implementovaných dle navržené metodiky. V závěru jsou diskutovány experimentální výsledky a přínos práce.
|
|
Metodologie pro návrh číslicových obvodů se zvýšenou spolehlivostí
Straka, Martin ; Kotásek, Zdeněk (vedoucí práce)
Práce představuje alternativní metodiku k již existujícím technikám pro návrh číslicových systémů se zvýšenou spolehlivostí implementovaných do obvodů FPGA a doplňuje některé nové vlastnosti při realizaci a testování těchto systémů. Práce se opírá o využití částečné dynamické rekonfigurace obvodu FPGA při návrhu systémů odolných proti poruchám, kde může být částečná rekonfigurace využita jako mechanizmus pro opravu a zotavení systému po výskytu poruchy. Práce nejprve představuje obecné principy diagnostiky, testování a spolehlivosti číslicových systémů včetně stručného popisu programovatelných obvodů FPGA a jejich architektury. Dále pokračuje přehledem současných metod a technik při návrhu a implementaci systémů odolných proti poruchám do obvodů FPGA, kde jsou popsány zejména techniky z oblasti detekce a lokalizace poruch, opravy a posuzování kvality návrhu. Nejdůležitější částí práce je popis metodiky pro návrh, implementaci a testování systémů odolných proti poruchám, která byla vytvořena pro obvody FPGA, jejichž konfigurační paměť je založena na pamětech typu SRAM. Nejprve je prezentována technika pro vytváření a automatizované generování hlídacích obvodů pro číslicové systémy a komunikační protokoly v FPGA, následně je prezentovaná referenční architektura spolehlivého systému implementovaného do FPGA včetně několika odolných architektur využívajících principu částečné dynamické rekonfigurace jako mechanizmu opravy a zotavení po výskytu poruchy. Dále je popsán způsob řízení rekonfiguračního procesu a testovací platforma pro snadné testovaní a ověření kvality systémů odolných proti poruchám implementovaných dle navržené metodiky. V závěru jsou diskutovány experimentální výsledky a přínos práce.
|
host ::
