Parallel Search of GPU for 15-Puzzle Solver with IDA<sup>*</sup> Search

Bibliographic Information

Other Title
  • IDA<sup>*</sup>探索を用いた15パズルSolverのGPUに適した並列探索法について

Search this article

Description

When a 15-puzzle solver with Iterative Deeping A* Search (IDA*Search) was simply introduced into Graphic Processing Unit (GPU), the serious problem sometimes happens: the performance decreases on searches of some maps whose optimal solution has many moves. This is because the thread divergence becomes a serious problem in depth-first search which is used in IDA* Search. This paper proposes the method which solves this problem by introducing breadth-first search instead of depth-first search into IDA* Search and avoids shortage of the work area by soft-cache using the common memory. The results of the experiment of the solver with this method show that the 15-puzzles whose solution is almost the longest (around 80 moves) were solved 30 times as fast as the serial search of GPU using NVIDIA GeForce GTX580 and Intel Core i7 2600 3.4GHz CPU.

Journal

Keywords

Details 詳細情報について

  • CRID
    1574231877573730816
  • NII Article ID
    110009882483
  • NII Book ID
    AA11362144
  • ISSN
    09196072
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top