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

書誌事項

タイトル別名
  • Parallel Search of GPU for 15-Puzzle Solver with IDA<sup>*</sup> Search

この論文をさがす

説明

Iterative Deeping A* Search (IDA* 探索) を用いた 15 パズル Solver を Graphic Processing Unit(GPU) に単純移植すると,手数の長い問題の探索において,性能が向上するどころか劣化するという深刻な問題が発生する場合がある.その原因は,IDA* 探索の内部で行っている深さ優先探索でスレッド分散が多発しているためと考えられる.本発表では,IDA* 探索の内部探索処理に幅優先探索法の考えを導入してスレッド分散を解消すると共に,その際発生する作業域不足を共有メモリを用いたソフトキャッシュ機能により回避する方式を提案する.また,提案方式を実現した Solver の作成・評価を行った結果,NVIDIA GeForce GTX580 と Intel Core i7 2600 3.4GHz CPU を使用した場合,15 パズルの最長手数に近い問題 (約 80 手) において,CPU のみの逐次探索の場合と比較して実行時間を 30 分の 1 以下に短縮することができた.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1574231877573730816
  • NII論文ID
    110009882483
  • NII書誌ID
    AA11362144
  • ISSN
    09196072
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ