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

IPSJ Web Site 1 Citations 16 References

Bibliographic Information

Other Title
  • ハッシング ニ モトズク ダイキボ タンサク モンダイ ノ タイコショウ ブンサン ショリ シュホウ
  • A Hash-based Fault-tolerant Distributed Processing for Large-scale Search Problems

Search this article

Abstract

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

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.

Journal

Citations (1)*help

See more

References(16)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top