Original title: Akcelerace heuristických metod diskrétní optimalizace na GPU
Translated title: Acceleration of Discrete Optimization Heuristics Using GPU
Authors: Pecháček, Václav ; Jaroš, Jiří (referee) ; Pospíchal, Petr (advisor)
Document type: Master’s theses
Year: 2012
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Práce se zabývá řešením diskrétních optimalizačních úloh. Zaměřuje se na zkrácení doby výpočtu s využitím heuristických metod a paralelismu. Teoretický základ tvoří kombinace algoritmů ant colony optimization (ACO) a lokálního prohledávání k-optimization. Platformu použitou při implementaci pak představuje technologie Nvidia CUDA umožňující efektivní provádění obecných výpočtů na moderních grafických čipech. Návrh využívá případové studie v podobě známého problému obchodního cestujícího (TSP). Řešení je založeno na rozdělení úlohy na podproblémy s pomocí techniky tour-based partitioning, paralelním zpracování jednotlivých částí a jejich opětovném spojení. Vytvořený paralelní kód dokáže provádět výpočet více než sedmnáctkrát rychleji než jeho sekvenční verze. Thesis deals with discrete optimization problems. It focusses on faster ways to find good solutions by means of heuristics and parallel processing. Based on ant colony optimization (ACO) algorithm coupled with k-optimization local search approach, it aims at massively parallel computing on graphics processors provided by Nvidia CUDA platform. Well-known travelling salesman problem (TSP) is used as a case study. Solution is based on dividing task into subproblems using tour-based partitioning, parallel processing of distinct parts and their consecutive recombination. Provided parallel code can perform computation more than seventeen times faster than the sequential version.
Keywords: acceleration; ACO; ant colony optimization; discrete optimization; GPGPU; GPU; heuristic; k-optimization; local search; Nvidia CUDA; parallel processing; tour-based partitioning; travelling salesman problem; TSP; ACO; akcelerace; ant colony optimization; diskrétní optimalizace; GPGPU; GPU; heuristika; k-optimization; lokální prohledávání; Nvidia CUDA; paralelní zpracování; problém obchodního cestujícího; tour-based partitioning; TSP

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/53693

Permalink: http://www.nusl.cz/ntk/nusl-236550


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses