A* Algorithm for Multicore Graphics Processors

Examensarbete för masterexamen

Använd denna länk för att citera eller länka till detta dokument: https://hdl.handle.net/20.500.12380/129175
Ladda ner:
Fil Beskrivning StorlekFormat 
129175.pdfFulltext1.23 MBAdobe PDFVisa
Typ: Examensarbete för masterexamen
Master Thesis
Titel: A* Algorithm for Multicore Graphics Processors
Författare: Rafia, Inam
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.
Nyckelord: Information Technology;Informationsteknik
Utgivningsdatum: 2010
Utgivare: 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
Samling:Examensarbeten för masterexamen // Master Theses



Materialet i Chalmers öppna arkiv är upphovsrättsligt skyddat och får ej användas i kommersiellt syfte!