A* Algorithm for Multicore Graphics Processors
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Publicerad
2010
Författare
Rafia, Inam
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Information Technology , Informationsteknik