[dipl] Perustieteiden korkeakoulu / SCI

Permanent URI for this collectionhttps://aaltodoc.aalto.fi/handle/123456789/21

Browse

Browsing [dipl] Perustieteiden korkeakoulu / SCI by Subject "15-palapeli"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Parallel shortest path search on GPU hardware
    (2010) Hätälä, Antti
     School of Science | Master's thesis
    The aim of this thesis is to show that a modern GPU can he leveraged for accelerating the A* heuristic graph search algorithm for solving a single-pair shortest path problem. While a lot of prior research has been done in A* parallelization for supercomputer architectures, to the best knowledge of the authors this is the first reported attempt at speeding up the solving of a single shortest path problem by GPU massive parallel processing. To overcome the large runtime memory requirements and the parallel processing overhead inefficiencies associated with traditional best-first parallel A*, a scheme of iterative-deepening A* with fixed node iteration count based periodic load balancing is chosen. The implementation consists of a compact parallel depth-first search CUDA kernel, CPU control logic for iteration launch and termination detection, a global load balancing routine on the CPU and a parallel per-block load balancing method in the CUDA kernel. The empirical study involves implementing a solver for the 15-puzzle optimal solution problem, analyzing the parallel speedup obtained from GPU massive parallelism and comparing the results against an optimized CPU solver. For a standard test set of a hundred 15-puzzle start configurations a 34-fold performance improvement over the CPU implementation is achieved.