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
Full metadata record
DC FieldValueLanguage
dc.contributor.authorRafia, Inam
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)sv
dc.contributor.departmentChalmers University of Technology / Department of Computer Science and Engineering (Chalmers)en
dc.date.accessioned2019-07-03T12:27:59Z-
dc.date.available2019-07-03T12:27:59Z-
dc.date.issued2010
dc.identifier.urihttps://hdl.handle.net/20.500.12380/129175-
dc.description.abstractGraphics 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.
dc.language.isoeng
dc.setspec.uppsokTechnology
dc.subjectInformation Technology
dc.subjectInformationsteknik
dc.titleA* Algorithm for Multicore Graphics Processors
dc.type.degreeExamensarbete för masterexamensv
dc.type.degreeMaster Thesisen
dc.type.uppsokH
Collection:Examensarbeten för masterexamen // Master Theses



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