@techreport{oai:ipsj.ixsq.nii.ac.jp:00113669,
 author = {萩野谷, 一二 and 古宮, 嘉那子 and Kazuji, Haginoya and Kanako, Komiya},
 issue = {16},
 month = {Feb},
 note = {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 分の １ 以下に短縮することができた．, 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.},
 title = {IDA<sup>*</sup>探索を用いた15パズルSolverのGPUに適した並列探索法について},
 year = {2015}
}