|
|
Evolutionary Design of Hash Functions
Kidoň, Marek ; Bidlo, Michal (referee) ; Dobai, Roland (advisor)
Hash tables are fast associative array implementations which became part of modern world of information technology and thanks to its simplicity became very popular among computer programmers. The choice of proper hash function is very important. Improperly selected hash function can result in poor hash table performance and its application. Currently there are many exceptional implementations of general hash functions. Such functions are not constrained to a concrete set of inputs, they perform on any input. On the other hand if we know the input domain we can design a specific hash function for desired application thus reaching better levels of performance compare to a general hash function. However hash function design is not trivial. There are no rules, standards, guides nor automated tools that would help us with such a task. In case of manual design the hash function author has to rely on his/her knowledge, experience, inventiveness and intuition. In case of such complicated tasks there is sometimes advantageous to choose a different path and use techniques such as evolution algorithms. Natural computing is an approach of certain problem solutions that are inspired by the process of species reproduction as defined by Charles Darwin. In this thesis we will design hash functions for the domain of IP addresses, that serve as an unique network device interface identifier in internet protocol networks. The chosen subset of natural computing is the genetic programming, a very specific technique that is an adequate approach to our problem thanks to its properties. Evolutionary designed hash functions offer good properties. They outperform state-of-the-art generic, human-created hash functions in terms of speed and collision resistance.
|
|
| |
|
|
Evolutionary Approach to Synthesis and Optimization of Ordinary and Polymorphic Circuits
Gajda, Zbyšek ; Schmidt, Jan (referee) ; Zelinka,, Ivan (referee) ; Sekanina, Lukáš (advisor)
Tato disertační práce se zabývá evolučním návrhem a optimalizací jak běžných, tak polymorfních digitálních obvodů. V práci jsou uvedena a vyhodnocena nová rozšíření kartézského genetického programování (Cartesian Genetic Programming, CGP), která umožňují zkrácení výpočetního času a získávání kompaktnějších obvodů. Další část práce se zaměřuje na nové metody syntézy polymorfních obvodů. Uvedené metody založené na polymorfních binárních rozhodovacích diagramech a polymorfním multiplexovaní rozšiřují běžné reprezentace digitálních obvodů, a to s ohledem na začlenění polymorfních hradel. Z důvodu snížení počtu hradel v obvodech syntetizovaných uvedenými metodami je provedena evoluční optimalizace založená na CGP. Implementované polymorfní obvody, které jsou optimalizovány s využitím CGP, reprezentují nejlepší známá řešení, jestliže je jako cílové kritérium brán počet hradel obvodu.
|
|
|
Cellular Automata Design Optimization
Jílek, Tomáš ; Drábek, Vladimír (referee) ; Bidlo, Michal (advisor)
Focus of this master's thesis is on evolutionary design of cellular automata and it's optimalization. There are described Evolutionary algorithms and Cellular automata in first part. Thereafter, one of the new ways of transition function representation and its possible evolutionary design is presented. Name of this method is Conditionally Matching Rules. This is followed by description of realized experiments with detailed results. Finally, success with optimalization for some tasks is presented in last chapter along with discussion.
|
|
|
Cellular Automaton in Evolutionary Process
Hejč, Michal ; Herrman, Tomáš (referee) ; Bidlo, Michal (advisor)
The aim of this master's theses it to focuse on the usage of genetic algorithms in combination with a technique of biologically inspired development in cellular automata. The principles of the proposed method is described. The main part of this work deals with the design of combinational logic circuits. The genetic algorithm is utilized to design a nonuniform one-dimensional cellular automaton (in particular, the local transition functions) which serves as a circuit generator. Experiments have been conducted to design of basic types of combinational circuits and polymorphic circuits. Finally, the results are presented and compared with the results obtained in the previous work in which a uniform cellular automaton was applied.
|
|
|
Evolutionary Approximation of Image Filters
Foukal, Tomáš ; Bidlo, Michal (referee) ; Sekanina, Lukáš (advisor)
This master's thesis introduces the areas of approximate computing, image filtering in hardware and evolutionary algorithms. It proposes a new design solution to the problem of the evolutionary approximation of median filters, where the objective is to reduce computational and implementation requirements and simultaneously minimize the error of filtering. Based on the gained knowledge and proposals, the necessary programs have been implemented. Experimental evaluation shows that the proposed method can provide good tradeoffs between the quality of filtering and the implementation cost for median filters.
|
|
|
Evolutionary Design of Simulator Based on Cellular Automata
Brigant, Vladimír ; Šperka, Svatopluk (referee) ; Mrnuštík, Michal (advisor)
This work describes concept of a cellular automata (CA) simulator, which is able to predict behaviour of a complex spatial system. This prediction is based on available training data and transition rule acquired from regression analysis powered by evolutionary algorithms. Two regression analysis methods (linear and logistic regression) are suggested, implemented and compared on urban growth prediction of Brno city.
|
|
|
Acceleration Methods for Evolutionary Design of Digital Circuits
Vašíček, Zdeněk ; Miller, Julian (referee) ; Zelinka,, Ivan (referee) ; Sekanina, Lukáš (advisor)
Ačkoliv můžeme v literatuře nalézt řadu příkladů prezentujících evoluční návrh jakožto zajímavou a slibnou alternativu k tradičním návrhovým technikám používaným v oblasti číslicových obvodů, praktické nasazení je často problematické zejména v důsledku tzv. problému škálovatelnosti, který se projevuje např. tak, že evoluční algoritmus je schopen poskytovat uspokojivé výsledky pouze pro malé instance řešeného problému. Vážný problém představuje tzv. problém škálovatelnosti evaluace fitness funkce, který je markantní zejména v oblasti syntézy kombinačních obvodů, kde doba potřebná pro ohodnocení kandidátního řešení typicky roste exponenciálně se zvyšujícím se počtem primárních vstupů. Tato disertační práce se zabývá návrhem několika metod umožňujících redukovat problem škálovatelnosti evaluace v oblasti evolučního návrhu a optimalizace číslicových systémů. Cílem je pomocí několika případových studií ukázat, že s využitím vhodných akceleračních technik jsou evoluční techniky schopny automaticky navrhovat inovativní/kompetitivní řešení praktických problémů. Aby bylo možné redukovat problém škálovatelnosti v oblasti evolučního návrhu číslicových filtrů, byl navržen doménově specifický akcelerátor na bázi FPGA. Tato problematika reprezentuje případ, kdy je nutné ohodnotit velké množství trénovacích dat a současně provést mnoho generací. Pomocí navrženého akcelerátoru se podařilo objevit efektivní implementace různých nelineárních obrazových filtrů. S využitím evolučně navržených filtrů byl vytvořen robustní nelineární filtr implusního šumu, který je chráněn užitným vzorem. Navržený filtr vykazuje v porovnání s konvenčními řešeními vysokou kvalitu filtrace a nízkou implementační cenu. Spojením evolučního návrhu a technik známých z oblasti formální verifikace se podařilo vytvořit systém umožňující výrazně redukovat problém škálovatelnosti evoluční syntézy kombinačních obvodů na úrovni hradel. Navržená metoda dovoluje produkovat komplexní a přesto kvalitní řešení, která jsou schopna konkurovat komerčním nástrojům pro logickou syntézu. Navržený algoritmus byl experimentálně ověřen na sadě několika benchmarkových obvodů včetně tzv. obtížně syntetizovatelných obvodů, kde dosahoval v průměru o 25% lepších výsledků než dostupné akademické i komerční nástroje. Poslední doménou, kterou se práce zabývá, je akcelerace evolučního návrhu lineárních systémů. Na příkladu evolučního návrhu násobiček s vícenásobnými konstantními koeficienty bylo ukázáno, že čas potřebný k evaluaci kandidátního řešení lze výrazně redukovat (defacto na ohodocení jediného testovacího vektoru), je-li brán v potaz charakter řešeného problému (v tomto případě linearita).
|
|
|
Evolutionary Design of Collective Communications Accelerated by GPUs
Tyrala, Radek ; Dvořák, Václav (referee) ; Jaroš, Jiří (advisor)
This thesis provides an analysis of the application for evolutionary scheduling of collective communications. It proposes possible ways to accelerate the application using general purpose computing on graphics processing units (GPU). This work offers a theoretical overview of systems on a chip, collective communications scheduling and more detailed description of evolutionary algorithms. Further, the work provides a description of the GPU architecture and its memory hierarchy using the OpenCL memory model. Based on the profiling, the work defines a concept for parallel execution of the fitness function. Furthermore, an estimation of the possible level of acceleration is presented. The process of implementation is described with a closer insight into the optimization process. Another important point consists in comparison of the original CPU-based solution and the massively parallel GPU version. As the final point, the thesis proposes distribution of the computation among different devices supported by OpenCL standard. In the conclusion are discussed further advantages, constraints and possibilities of acceleration using distribution on heterogenous computing systems.
|
|
|
Polymorphic Image Filters
Salajka, Vojtěch ; Vašíček, Zdeněk (referee) ; Sekanina, Lukáš (advisor)
This thesis deals with the polymorphic image filter design. The study includes polymorphic circuits, their theoretical base and practical applications. It further focuses on the cartesian genetic programming that can be used for an evolutionary design of some types of image filters. The thesis continues with the specification of the evolutionary algorithm to be used for the design of the polymorphic image filters. The implementation of the algorithm is described in two versions -- a standard one running only on a CPU and an accelerated one that partially uses the GPU. Several polymorphic image filters are designed by means of the algorithm.
|
guest ::
