Název: Akcelerace heuristických metod diskrétní optimalizace na GPU
Překlad názvu: Acceleration of Discrete Optimization Heuristics Using GPU
Autoři: Pecháček, Václav ; Jaroš, Jiří (oponent) ; Pospíchal, Petr (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2012
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [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.
Klíčová slova: 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; 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

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/53693

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-236550


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce