An implementation and performance evaluation of parallel algorithms for off-road vehicle routing on the GPU

Sammanfattning

Routing is a problem with diverse applications, multiple problems from several fields can be formulated as general graph problems, one of the most intuitive being vehicle routing, graphs denoting positions (nodes) and their connecting paths, and solved using some type of pathfinding. Implementing pathfinding for general graphs on the parallel architecture of the GPU poses several challenges, including limited memory, work balancing, synchronization, as well as branching. This degree project compares and evaluates several algorithms and methods for computing path isochrones, the complete set of shortest paths to everywhere from a given starting position for large terrain rasters on the GPU. Terrain rasters in this context entails uniform grid data where each grid cell encodes either a traversal cost or the inverse thereof, traversal speed for a specific vehicle. The goal is to find or improve the methods existing for general graphs, optimizing for this specific type of graph. Two implementations are presented, both variations of the commonly used delta-stepping method, one for graphs too large to fit in memory with local pathfinding until convergence, and one for smaller graphs, equivalent to the former, but with the whole graph rather than a subset. The results show that specializing implementations to function on the native format of the grid is more effective than converting to the more commonly used CSR format, due to required data movement, and constant degree of the cells. Synchronization and data movement play a significant role in the possible speedup of pathfinding on these type of graphs. The structure of the graph itself plays the most significant role, larger and more connected graphs allows for a larger speedup. The developed implementations achieve a speedup of around 10 for large connected graphs, around 5 for the average case, and on par with a sequential reference implementation in the worst case.