| Item type |
SIG Technical Reports(1) |
| 公開日 |
2015-02-26 |
| タイトル |
|
|
タイトル |
IDA<sup>*</sup>探索を用いた15パズルSolverのGPUに適した並列探索法について |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Parallel Search of GPU for 15-Puzzle Solver with IDA<sup>*</sup> Search |
| 言語 |
|
|
言語 |
jpn |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
ゲーム、パズルの解析 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
茨城大学工学部 |
| 著者所属 |
|
|
|
茨城大学工学部 |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Computer and Information Sciences, Ibaraki University |
| 著者所属(英) |
|
|
|
en |
|
|
Department of Computer and Information Sciences, Ibaraki University |
| 著者名 |
萩野谷, 一二
古宮, 嘉那子
|
| 著者名(英) |
Kazuji, Haginoya
Kanako, Komiya
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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 分の １ 以下に短縮することができた． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
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. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA11362144 |
| 書誌情報 |
研究報告ゲーム情報学（GI）
巻 2015-GI-33,
号 16,
p. 1-8,
発行日 2015-02-26
|
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-GI15033016.pdf (1.1 MB)
