Povzporejanje biološko navdihnjenih algoritmov : diplomsko delo

Prestor, Domen (avtor), Brodnik, Andrej (mentor), Korošec, Peter (komentor)

Diplomska naloga obravnava osnovne ideje in pristope, uporabne pri povzporejanju s strani narave navdihnjenih algoritmov. Njen temelj je poskus pohitritve algoritma, razvitega na Inštitutu Jožef Stefan, ki temelji na stigmergiji mravelj. Kako? Z uporabo grafične kartice in tovrstnemu početju namenjenega ogrodja, OpenCL. Potrebno je bilo torej pripraviti nabor tako imenovanih ščepcev kode, ki bodo delčke algoritma, primerne za vzporedno izvajanje, izvedli na grafični kartici, jih čim bolj optimizirati in opraviti potrebne meritve. Diplomsko delo opiše posamezne korake povzporejanega algoritma, poda nekaj splošnih smernic za povzporejanje biološko navdihnjenih algoritmov in predstavi konkretne rezultate meritev. Le-ti so predstavljeni v različnih kontekstih (primerjava časov izvajanj posameznih korakov algoritma glede na uporabljeno število niti, primerjava časov izvajanj posameznih korakov vzporedne implementacije s časi izvajanj posameznih korakov zaporedne in primerjava celotnega časa izvajanja vzporedne implementacije s celotnim časom izvajanja zaporedne).

• Jezik: Slovenski jezik
• Ključne besede: biološko navdihnjeni algoritmi, diferencialna stigmergija mravelj, grafična procesna enota, standard OpenCL, vmesnik JavaCL, računalništvo, visokošolski strokovni študij, računalništvo in informatika, diplomske naloge
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Založnik: [D. Prestor]
• Leto izida: 2015
• Št. strani: 71 str.
• PID: 20.500.12556/RUL-30656
• COBISS.SI-ID: 1536252867
• Datum objave v RUL: 19.03.2015

Licence

• Licenca: CC BY-SA 2.5 SI, Creative Commons Priznanje avtorstva-Deljenje pod enakimi pogoji 2.5 Slovenija
• Povezava: https://creativecommons.org/licenses/by-sa/2.5/si/deed.sl
• Opis: Dovoljuje kopiranje in razširjanje vsebin v kakršnemkoli mediju in obliki. Dovoljuje remixanje, urejanje, predelava in vključevanje vsebine v lastna dela v vse namene, tudi komercialne. Primerno morate navesti avtorja, povezavo do licence in označiti spremembe, če so kakšne nastale. To lahko storite na kakršenkoli razumen način, vendar ne na način, ki bi namigoval na to, da dajalec licence podpira vas ali vašo uporabo dela. Če vsebino uredite, predelate (remixate) ali gradite na njej, morate svojo različico razširjati pod isto licenco kot izvirnik. Ne smete uporabiti pravnih določil ali tehničnih ukrepov, ki bi pravno omejili ali onemogočilo druge, da bi storili karkoli, kar licenca dovoli.

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Parallelization of biologically inspired algorithms

Izvleček

This thesis addresses the basic ideas and approaches used when parallelizing biologically inspired algorithms. Its foundation is an attempt of speeding up an algorithm developed on the Jožef Stefan Institute, that is based on the stigmergy of ants. How? With the use of graphics processor and the intended framework, OpenCL. What had to be done was to prepare a set of the so called code kernels that will take pieces of the algorithm suited for parallel computing, and execute them on the graphics card; optimize them as much as possible, and perform the required measurements. The thesis describes individual steps of the parallelized algorithm, it provides some general guidelines for the parallelization of biologically inspired algorithm and presents the actual measurement results. The latter are presented in different contexts (comparison of individual algorithm steps execution times with respect to the used number of threads, comparison of individual algorithm steps parallel execution time with the individual steps sequential execution time, and comparison of the total parallel algorithm execution time with the total sequential algorithm execution time).

• Ključne besede: biologically inspired algorithms, differential ant stigmergy, graphics processing unit, JavaCL interface, OpenCL standard, computer science, computer and information science, diploma