|
|
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.
|
|
|
Evolutionary Design of Neural Networks
Beluský, Tomáš ; Vašíček, Zdeněk (referee) ; Minařík, Miloš (advisor)
The work deals with the development of the genetic algorithm, which designs the structure and learning of the neural networks. The fitness function also includes the number of hidden neurons, and thus we obtain the most optimal structure, which is reachable. The own versions of the operators are presented, which manage the entire process of evolution. The result of the work is a library for evolutionary design of neural networks. Moreover, graphical interface for setting parameters and displaying the results was created. In the experimental part the design is compared with other systems and algorithms. Finally, results are reviewed and the process for the following development of the system is outlined.
|
|
|
Advanced Evolutionary Image Filtering
Saranová, Ivana ; Drábek, Vladimír (referee) ; Bidlo, Michal (advisor)
This work aims to use cellular automata with a transition function of conditionally matching rules designed by the evolution strategy for the removal of noises of different types and intensities from digital images. The proposed method improves the original concept of conditionally matching rules by modifying the right side of the rule, extending it from a single value to a selection of functions. Furthermore, various evolution strategy setups were explored, including usage of different noise models for evolution, training on partially damaged images, and other setups, resulting in high-quality filters for each noise model. Comparing these filters to the existing methods shows great improvement from the original approach and the ability to evolutionarily design filters that are placed among the top methods quality-wise.
|
|
|
Concurrent evolutionary design of hardware and software
Minařík, Miloš ; Sekaj, Ivan (referee) ; Squillero, Giovanni (referee) ; Sekanina, Lukáš (advisor)
Genetické programování (GP) je v určitém rozsahu schopno automaticky generovat požadované programy, aniž by uživatel musel určit, jakým způsobem má program postupovat. GP bylo s úspěchem použito k řešení široké škály praktických problémů z různých oblastí, přičemž výsledky byly často srovnatelné s řešeními vytvořenými člověkem. Doposud však nebyla zodpovězena otázka, zda GP dokáže generovat vysoce optimalizovaný výpočetní model (platformu) spolu s programem spustitelným na této platformě, který by řešil daný problém při dodržení všech omezení (například na plochu na čipu a zpoždění). V případě scénářů, kdy je optimalizováno více kritérií, by uživatelským výstupem měla být množina nedominovaných řešení s různými kombinacemi úrovně využití zdrojů (plocha, příkon) a výkonu (rychlosti provádění). Tento problém může být chápán jako souběžný návrh hardwaru a softwaru, zkráceně HW/SW codesign. Tato práce zkoumá způsoby, jakými lze souběžně evolučně vyvíjet platformu a programy v případě, že je problém zadán množinou vektorů vstupů a jim odpovídajících výstupů. Nejprve byl vytvořen model architektury a evoluční platforma zajišťující zpracování a evoluční vývoj těchto architektur. Kandidátní mikroprogramové architektury byly evolvovány spolu s programy pomocí lineárního genetického programování. Následně byla provedena série jednodušších experimentů. Navržená platforma dosahovala výsledků srovnatelných s nejnovějšími metodami. Na základě slabých míst objevených během počátečních experimentů byla platforma rozšířena. Rozšířená platforma byla poté ověřena na několika složitějších experimentech. Jeden z nich byla zaměřen na efektivní implementaci aproximace sigmoidální funkce. Platforma v tomto případě našla řadu různých řešení implementujících aproximaci sigmoidy, z nichž některá byla sekvenční a jiná čistě kombinační. V rámci experimentu byly evolučně nalezeny i známé algoritmy, přičemž některé z nich byly evolucí dokonce optimalizovány pro podmnožinu definičního oboru zvolenou pro daný experiment. Poslední sada experimentů byla zaměřena na evoluční návrh obrazových filtrů pro redukci šumu typu sůl a pepř. Platforma v tomto případě znovuobjevila koncept přepínaných filtrů a naezla variantu přepínaného mediánového filtru, která byla z hlediska výsledků filtrace srovnatelná s běžně používanými metodami. Tato práce prokázala, že pomocí genetického programování lze navrhovat a optimalizovat malé HW/SW systémy. Automatizovaný evoluční návrh složitějších HW/SW systémů zůstává otevřeným problémem vhodným k dalšímu výzkumu.
|
|
|
Automated Multi-Objective Parallel Evolutionary Circuit Design and Approximation
Hrbáček, Radek ; Fišer, Petr (referee) ; Trefzer,, Martin (referee) ; Sekanina, Lukáš (advisor)
Spotřeba a energetická efektivita se stává jedním z nejdůležitějších parametrů při návrhu počítačových systémů, zejména kvůli omezené kapacitě napájení u zařízení napájených bateriemi a velmi vysoké spotřebě energie rostoucích datacenter a cloudové infrastruktury. Současně jsou uživatelé ochotni do určité míry tolerovat nepřesné nebo chybné výpočty v roustoucím počtu aplikací díky nedokonalostem lidských smyslů, statistické povaze výpočtů, šumu ve vstupních datech apod. Přibližné počítání, nová oblast výzkumu v počítačovém inženýrství, využívá rozvolnění požadavků na funkčnost za účelem zvýšení efektivity počítačových systémů, pokud jde o spotřebu energie, výpočetní výkon či složitost. Aplikace tolerující chyby mohou být implementovány efektivněji a stále sloužit svému účelu se stejnou nebo mírně sníženou kvalitou. Ačkoli se objevují nové metody pro návrh přibližně počítajících výpočetních systémů, je stále nedostatek automatických návrhových metod, které by nabízely velké množství kompromisních řešení dané úlohy. Konvenční metody navíc často produkují řešení, která jsou daleko od optima. Evoluční algoritmy sice přinášejí inovativní řešení složitých optimalizačních a návrhových problémů, nicméně trpí několika nedostatky, např. nízkou škálovatelností či vysokým počtem generací nutných k dosažení konkurenceschopných výsledků. Pro přibližné počítání je vhodný zejména multikriteriální návrh, což existující metody většinou nepodporují. V této práci je představen nový automatický multikriteriální paralelní evoluční algoritmus pro návrh a aproximaci digitálních obvodů. Metoda je založena na kartézském genetickém programování, pro zvýšení škálovatelnosti byla navržena nová vysoce paralelizovaná implementace. Multikriteriální návrh byl založen na principech algoritmu NSGA-II. Výkonnost implementace byla vyhodnocena na několika různých úlohách, konkrétně při návrhu (přibližně počítajících) aritmetických obvodů, Booleovských funkcích s vysokou nelinearitou či přibližných logických obvodů pro tří-modulovou redundanci. V těchto úlohách bylo dosaženo význammých zlepšení ve srovnání se současnými metodami.
|
|
|
Coevolution of Fitness Predicotrs in Cartesian Genetic Programming
Drahošová, Michaela ; Pošík, Petr (referee) ; Šenkeřík, Roman (referee) ; Sekanina, Lukáš (advisor)
Kartézské genetické programován (CGP) je evoluc inspirovaná metoda strojového učen, která je primárně určená pro automatizovaný návrh programů a čslicových obvodů. CGP je úspěšné v řešen mnoha úloh z reálného světa. Avšak k nalezen inovativnch řešen obvykle potřebuje značný výpočetn výkon. Každý kandidátn program navržený pomoc CGP mus být spuštěn, aby se zjistilo, do jaké mry tento program řeš zadaný problém, a mohla mu být přiřazena fitness hodnota. Právě vyhodnocen fitness bývá výpočetně nejnáročnějš část návrhu pomoc CGP. Tato práce se zabývá využitm koevoluce prediktorů fitness v CGP za účelem zrychlen procesu evolučnho návrhu prováděného pomoc CGP. Prediktor fitness je malá podmnožina trénovacch dat použvaná pro rychlý odhad fitness hodnoty namsto náročného vyhodnocen objektivn fitness hodnoty. Koevoluce prediktorů fitness je optimalizačn metoda modelován fitness, která snižuje náročnost a frekvenci výpočtu fitness. V této práci je koevolučn algoritmus přizpůsoben pro CGP a jsou představeny a zkoumány tři přstupy k zakódován prediktorů fitness. Představená metoda je experimentálně vyhodnocena v pěti úlohách symbolické regrese a v úloze návrhu obrazových filtrů. Výsledky experimentů ukazuj, že pomoc této metody lze významně snžit výpočetn čas, který CGP potřebuje pro řešen zkoumané třdy úloh.
|
guest ::
