[dipl] Perustieteiden korkeakoulu / SCI

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

Browse

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

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • Cooperative Heuristic Search with Software Agents
    (2014-06-02) Halme, Antti
     Perustieteiden korkeakoulu | Master's thesis
    Parallel algorithms extend the notion of sequential algorithms by permitting the simultaneous execution of independent computational steps. When the independence constraint is lifted and executions can freely interact and intertwine, parallel algorithms become concurrent and may behave in a nondeterministic way. Parallelism has over the years slowly risen to be a standard feature of high-performance computing, but concurrency, being even harder to reason about, is still considered somewhat notorious and undesirable. As such, the implicit randomness available in concurrency is rarely made use of in algorithms. This thesis explores concurrency as a means to facilitate algorithmic cooperation in a heuristic search setting. We use agents, cooperating software entities, to build a single-source shortest path (SSSP) search algorithm based on parallelized A∗, dubbed A!. We show how asynchronous information sharing gives rise to implicit randomness, which cooperating agents use in A! to maintain a collective secondary ranking heuristic and focus search space exploration. We experimentally show that A! consistently outperforms both vanilla A∗ and a noncooperative, explicitly randomized A∗ variant in the standard n-puzzle sliding tile problem context. The results indicate that A! performance increases with the addition of more agents, but that the returns are diminishing. A! is observed to be sensitive to heuristic improvement, but also constrained by search overhead from limited path diversity. A hybrid approach combining both implicit and explicit randomness is also evaluated and found to not be an improvement over A! alone. The studied A! implementation based on vanilla A∗ is not as such competitive against state-of-the-art parallel A∗ algorithms, but rather a first step in applying concurrency to speed up heuristic SSSP search. The empirical results imply that concurrency and nondeterministic cooperation can successfully be harnessed in algorithm design, inviting further inquiry into algorithms of this kind.
  • 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.