|
||||||
|
||||||
| Undergraduate Honours Projects | ||||||
|
Carleton University - School of Computer Science Undergraduate Honours Project Fall 2009 Parallel Pathfinding on the NVIDIA Tesla Architecture Matthew Peyrard 
ABSTRACT In this project we present the implementation of a parallel pathfinding algorithm in CUDA, NVIDIA's extension of C++ for programming general-purpose applications using its GPUs. The solution we discovered works very efficiently on mesh shaped graphs, and scaled to graph sizes exceeding 10 million vertices, which was only a limitation due to a lack of on chip memory. The algorithm was also a success in the sense that the approach we used can be extended to any algorithm that requires dynamic distribution of work to a fixed number of threads on a single-instruction multiple-thread programming model. We found our implementation of the algorithm to be superior to its single-threaded sequential counterpart, by as much as a factor of 17 for very large graphs. |
||||||
|
