2024-03-29T11:37:20Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000289882023-04-27T10:00:04Z01164:02240:02258:02260
並列分枝限定法における耐故障アルゴリズムの評価Evaluation of Fault-Tolerant Parallel Branch and Bound Algorithmsjpnhttp://id.nii.ac.jp/1001/00028988/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=28988&item_no=1&attribute_id=1&file_no=1Copyright (c) 2005 by the Information Processing Society of Japan東京工業大学東京工業大学川上, 健太合田, 憲人計算機クラスタやグリッドで大規模な処理を行った場合,計算ノードで障害が発生すると計算全体が停止してしまう恐れがあり,並列計算における耐故障性は非常に重要なテーマである.本稿では,マスタ・ワーカモデルを用いた並列分枝限定法における耐故障性を実現するための手法であるタスクの多重化による手法とワーカの監視による手法の性能評価について述べる.タスクの多重化による手法には,実行時間を削減するために新たに不要な処理の中断機構を実装した.本性能評価の結果,中断機構により,実行時間が大幅に短縮されることが確認された.また,両手法ともに高い耐高負荷及び耐障害性を有することが確認された.Fault-tolerance is one of crucial issues for large-scale computing environments, such as a PC cluster or the Grid, where a fault on one computer might stop the whole computation. This paper evaluates two fault-tolerant algorithms, the task replication algorithm and the worker monitoring algorithm, for a parallel branch and bound method parallelized by the masterworker paradigm. For the task replication algorithm, the performance of the mechanism to avoid redundant computation is also evaluated. The results showed that this mechanism significantly reduced computation time and that both fault-tolerant algorithms effectively work to improve fault-tolerance and load-tolerance.AN10463942情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC)200581(2005-HPC-103)49542005-08-032009-06-30