探索の重複領域削減による階層的挟み撃ち探索の高速化

• Item type: Symposium(1)
• 公開日: 2011-05-18
• タイトル: 探索の重複領域削減による階層的挟み撃ち探索の高速化
• タイトル / 言語: en
• タイトル: A Reduction Algorithm of Overlapping Search Space for Hierarchical Pincers Attack Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 並列アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 千葉工業大学情報工学科
• 著者所属: 千葉工業大学情報工学科
• 著者所属: 千葉工業大学情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者名: 中村, あすか; 富永, 浩文; 前川, 仁孝
• 著者名(英): Asuka, Nakamura; Hirobumi, Tominaga; Yoshitaka, Maekawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文は，分枝限定法に有効な並列探索手法のひとつである階層的挟み撃ち探索を，複数のプロセッサが探索する領域を削減することで高速化する手法を提案する．分枝限定法における階層的挟み撃ち探索は，複数のプロセッサが左右から挟み撃つように探索するため，複数のプロセッサが同一のノードを探索する探索の重複領域が生じる．スレーブプロセッサの割当領域に対する探索の重複領域の割合は，各ノードの分枝数が少ない探索木ほど大きくなる．そこで，本論文では，探索の重複領域を削減することで，階層的挟み撃ち探索の求解時間を短縮する．本削減手法は，スレーブプロセッサの探索済領域をリーダプロセッサが探索しないように，スレーブプロセッサだけでなくリーダプロセッサも探索の重複を検出する．また，複数のスレーブプロセッサが同じノードを探索しないように，スレーブプロセッサの探索経路を反映した再割当を行う．評価の結果，提案手法は階層的挟み撃ち探索に対して相乗平均で約 1.2 倍，最大約 2.1 倍高速に求解できることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a reduction algorithm of search space assigned some processors for the hierarchical pincers attack search which is one of the efficient parallel algorithm for the branch and bound method. In hierarchical pincers attack search, some processors search from right and left sides of each subtree in a whole tree. Hence, some of processors search the same search space. In a search tree consisting of a node connecting a few branches, overlapping search space occupies large search area in search area allocated of a slave processor. Therefore, the proposed method speeds up hierarchical pincers attack search by reducing overlapping search space. In this method, the leader processor detects overlapping search area so that it does not search a node which searched slave processors, and allocates a node so that some slave processors do not search the same node. As a results of evaluation, the speedup ratio of the proposal method compared with the hierarchical pincers attack search is about 1.2 times on the average of geometric mean, and about 2.1 times on the maximum.
• 書誌情報: 先進的計算基盤システムシンポジウム論文集; 巻 2011, p. 348-355, 発行日 2011-05-18
• 出版者 / 言語: ja
• 出版者: 情報処理学会