A* Algorithm for Multicore Graphics Processors

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/129175
Download file(s):
File Description SizeFormat 
129175.pdfFulltext1.23 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: A* Algorithm for Multicore Graphics Processors
Authors: Rafia, Inam
Abstract: Graphics processors are becoming more and more popular among many application developers as commodity data-parallel coprocessors. As a consequence, general purpose programming for graphics processors research is growing. A* is a well known best-first shortest path finding algorithm, commonly used in computer games and robotics, to quickly find a good path in real time. We have implemented A* in CUDA, NVIDIA’s programming platform for graphics processors. Our graphics processor A* implementation is faster and more efficient than a similar CPU version of the same algorithm. We have provided three improvements to the parallel A* algorithm to allow it to work faster and on larger maps. The first improvement is the use of pre-calculated paths for commonly used paths. Secondly, we allow multiple threads to work on the same path and thirdly we have implemented a scheme for Hierarchical Breakdown. Instead of computing the complete path as a whole, the path is calculated in many segments. This makes it possible to calculate more paths concurrently on big maps than was possible before. Very large maps are broken down into many clusters and paths are computed at a higher level of abstraction using path abstraction. All the segments of a path are then joined together to make a complete path using path refinements.
Keywords: Information Technology;Informationsteknik
Issue Date: 2010
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/129175
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.