ハッシングに基づく大規模探索問題の耐故障分散処理手法

• Item type: Trans(1)
• 公開日: 2007-03-15
• タイトル: ハッシングに基づく大規模探索問題の耐故障分散処理手法
• タイトル / 言語: en
• タイトル: A Hash-based Fault-tolerant Distributed Processing for Large-scale Search Problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院新領域創成科学研究科
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: 東京大学大学院新領域創成科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Frontier Sciences, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Frontier Sciences, The University of Tokyo
• 著者名: 横山, 大作; 田浦, 健次朗; 近山, 隆
• 著者名(英): Daisaku, Yokoyama; Kenjiro, Taura; Takashi, Chikayama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多数の計算機を長時間用いる大規模分散計算を行うためには，一部の計算機の故障に際しても全体の計算が破綻なく動き続ける，という耐故障性を実現することが特に重要である．このような要件を満たしつつ，組合せ最適化問題などに代表される大規模探索問題を解くための分散計算フレームワークとして，マスタ・ワーカ構成，ワークスティーリングなどの手法が提案され，適用されてきた．探索問題は一般に，親問題の解が多数の子問題の探索結果によって決まる，という再帰的な構造で表現されるが，多数の親問題間で同一の子問題を共有し，ある子問題の結果が多くの親問題に必要とされるような種類の探索問題も多い．ゲーム木探索などがその代表例である．前述のマスタ・ワーカ構成などを用いると，同一の子問題を多数重複して無駄に計算してしまうことになりがちであり，探索効率に悪影響を及ぼしてしまう．このような重複計算をさけるための手法として，ハッシングに基づく分散探索手法が提案されている．我々は，失われた子問題を再実行することでこの手法に耐故障性を付加し，大規模探索に適用することを試みた．本論文では，重複する子問題を持つような探索問題の構造をモデル化し，マスタ・ワーカなどの手法と提案手法との，探索効率および故障発生時の回復に必要となるコストについて，シミュレーションによって比較を行い，提案手法の特質を明らかにする．また，実問題に対して本手法を適用し，実システムでの性能評価を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For large-scale distributed processing of time-consuming computation with many computers, failures of some of the nodes should not cause failure of the whole computation. For this purpose, several fault-tolerant computation frameworks, such as master-worker and work-stealing methods, have been proposed and actually used. Search problems are generally defined recursively: A subproblem is solved using the results of its own child subproblems. Most practical search problems have subproblems shared as children of two or more subproblems. Game tree search is a typical example. With the master-worker framework, many subproblems are likely to be solved repeatedly leading to inefficiency. A search algorithm based on distributed hash table has been developed to eliminate such duplicated computation. Our proposal adds fault-tolerance to the algorithm through recomputation of subproblem results lost with faults. In this paper, a model of search problems with shared subproblems is formalized, and the proposed framework are compared with other methods such as one based on the master-worker framework in search efficiencies of cases with and without faults. The performance on real computers for some practical search problems is also shown.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 48, 号 SIG4(PRO32), p. 1-13, 発行日 2007-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会