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

概要

論文の詳細を見る
多数の計算機を長時間用いる大規模分散計算を行うためには,一部の計算機の故障に際しても全体の計算が破綻なく動き続ける,という耐故障性を実現することが特に重要である.このような要件を満たしつつ,組合せ最適化問題などに代表される大規模探索問題を解くための分散計算フレームワークとして,マスタ・ワーカ構成,ワークスティーリングなどの手法が提案され,適用されてきた.探索問題は一般に,親問題の解が多数の子問題の探索結果によって決まる,という再帰的な構造で表現されるが,多数の親問題間で同一の子問題を共有し,ある子問題の結果が多くの親問題に必要とされるような種類の探索問題も多い.ゲーム木探索などがその代表例である.前述のマスタ・ワーカ構成などを用いると,同一の子問題を多数重複して無駄に計算してしまうことになりがちであり,探索効率に悪影響を及ぼしてしまう.このような重複計算をさけるための手法として,ハッシングに基づく分散探索手法が提案されている.我々は,失われた子問題を再実行することでこの手法に耐故障性を付加し,大規模探索に適用することを試みた.本論文では,重複する子問題を持つような探索問題の構造をモデル化し,マスタ・ワーカなどの手法と提案手法との,探索効率および故障発生時の回復に必要となるコストについて,シミュレーションによって比較を行い,提案手法の特質を明らかにする.また,実問題に対して本手法を適用し,実システムでの性能評価を行う.
一般社団法人情報処理学会の論文
2007-03-15

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

スポンサーリンク

概要

著者

関連論文

スポンサーリンク