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.

Ruttning är ett problem med breda tillämpningsområden. Flera problem kan formuleras som generella grafproblem, fordonsruttning en av de mest självklara, rafer då bestående av positioner (noder) och deras anslutningar (kanter), och kan då lösas med någon form av ruttning. Att implementera ruttning på GPU:n har flera utmaningar, begränsat minne, arbetsbalans, synkronisering, samt branching. Detta examensarbete undersöker och evaluerar ett flertal algoritmer och metoder för att beräkna vägisokroner, den kompletta samlingen av kortaste vägar till alla destinationer från en given startposition, för stora terrängraster på GPU:n. Terrängraster betyder i detta fallet uniform rasterdata där varje cell innehåller en traverseringskostnad eller dess invers, traverseringshastighet för något specifikt fordon. Målet är att hitta eller förbättra de existerande GPU-ruttningsmetoderna för denna specifika graftyp. Två implementationer presenteras, båda en variation på den vanligt användna deltasteppningsmetoden, en för grafer för stora för att få plats i minnet, som använder sig av en lokal ruttningsmetod till konvergens uppnås, samt en för mindre grafer som är ekvivalent till den föregående, men med hela grafen istället för en delmängd av den. Resultaten visar att det är värt att specialisera implementationer för att använda sig av det naturliga rasterformatet är mer effektivt än att konvertera till det mer vanligt användna CSR-formatet, på grund av nödvändig dataförflyttning, samt nära konstant grad på noderna. Synkronisering och dataförflyttning spelar en stor roll i att avgöra den möjliga uppsnabbningskapaciteten för denna typen av graf. Strukturen av själv grafen är den största faktorn, och mängden traverserbara celler avgör den möjliga uppsnabbningsmöjligheten, även om de har en hög traverseringskostnad. De presenterade implementationerna når runt 10 gånger snabbare prestanda för stora, väl anslutna grafer, runt 5 gånger snabbare prestanda i medelfallet och detsamma som referensimplementationen i de värsta fallen.