2024-03-29T07:34:42Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000119852022-10-21T05:24:51Z00581:00677:00685
並列ゲーム木探索のための分散共有ハッシュ法の評価Some Experiments on the Distributed Shared-Hashing Method for Searching Game - Trees in Paralleljpn論文http://id.nii.ac.jp/1001/00011985/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=11985&item_no=1&attribute_id=1&file_no=1Copyright (c) 2001 by the Information Processing Society of Japanアルゴリズム理論電気通信大学電気通信学部情報工学科/現在,株式会社アイザック電気通信大学電気通信学部情報工学科/現在,サン・マイクロシステムズ株式会社電気通信大学電気通信学部情報工学科電気通信大学電気通信学部情報工学科佐藤, 信弘新藤, 雅也野下浩平中山, 泰一ゲーム木探索における局面表(トランスポジション表)は,局面の探索結果を表に登録し,同一局面の探索を表の参照ですませる技法である.本論文では,並列的なゲーム木探索のために計算機間で共有する局面表を実現し,その有効性を実験的に評価する.実験対象として並列選択の比較回数を決定する探索問題をとりあげる.通信速度の遅いネットワークで結合された並列計算環境において,分散的に共有するハッシュ法による共有局面表の実現方法を2種類比較する.代表的な並列アルゴリズムを2つ選び,実行時間や各種オーバヘッドを測定し,共有局面表の効果を調べる.著しい結果として8台の計算機により逐次計算の7倍以上の速度向上を得た.また逐次計算では時間がかかりすぎ解けなかった問題が共有局面表による並列計算で解くことができた.本論文の分散共有ハッシュ法により,並列計算の性能向上の目標である十分良い台数効果が実現できることを実証した.In game-tree searching,transposition tables are used for eliminating repetitions of the identical computation for reappeared positions.For parallel searching on a distributed parallel computer-cluster,two types of the shared-hashing method are presented for implementing the global transposition table.For evaluating our method in terms of various overheads as well as the computation time,a certain selection problem is used and two parallel algorithms are implemented to solve it.As one of our experimental results,more than seven-fold speedups have been achieved on eight processors.By our method, several instances of the problem have been solved,which could not be solved on a single computer.The experiments have proved that our distributed shared-hashing method is efficient enough to show a good performance near the maximum on a distributed parallel environment with slow interprocessor communication.AN00116647情報処理学会論文誌425119812062001-05-151882-77642009-06-29