CUDA Powered A* Search Algorithm

Import 26/06/2013Tato práce se zabývá porovnáním rychlosti dobře známého vyhledávacího algoritmu A* na procesoru a grafické kartě. Hledá se ideální rozdělení vláken, kde každé prohledává obecný graf, který byl vytvořený pomocí triangulace. Práce srovná několik způsobů jak náhodně položené body v rovině spojit a ukáže, proč je nejvhodnější Delaunayho triangulace. Výsledné řešení je kontrolováno grafickým znázorněním díky knihovnám OpenCV. Očekává se, že výsledné programy pro počítání algoritmů, ať už na procesoru nebo technologii CUDA, budou velmi podobné. Každé vyhledávání počítá jen čistě A* algoritmus a nebere v úvahu žádné jiné pomocné postupy.This thesis presents a speed comparison of the well know A* Search algorithm implemented on processor and graphics card. The goal is to find the ideal thread division where each thread searches through a common graph created by a triangulation. The work compares several ways of connecting randomly generated points on a plane together and shows why it is best to use Delaunay triangulation. The results are evaluated by graphical representation generated by OpenCV libraries. It is presumed that the final programs for computing algorithms, either on the processor or CUDA, are very similar. Every search only computes the A* algorithm and does not take into account any other auxiliary procedures.460 - Katedra informatikydobř