単一ノード故障時におけるマルチコアプロセッサシステムの回復時間を最小化するタスクスケジューリング

機関リポジトリ 情報処理学会 HANDLE オープンアクセス

書誌事項

タイトル別名
  • Task Scheduling Algorithm to Minimize Recovery Time in Case of Single Node Fault in Multicore Processor System

この論文をさがす

抄録

本論文では，各計算ノードがマルチコアプロセッサであるような並列処理システムにおいて，ネットワークの輻輳を考慮しつつ，マルチコアプロセッサの単一停止故障時の回復時間を最小化するタスクスケジューリングアルゴリズムを提案する．最近開発されたプロセッサのほとんどはマルチコアであり，マルチコアプロセッサが故障した場合は，その上で実行されているタスクをすべてやり直す必要が発生する．ここでは，リカバリのために，各計算ノードで従来手法に基づくチェックポインティングを行うとを仮定する．1つのノードで互いに依存した計算を長時間行うと，そのプロセッサが故障したときに，最近保存したチェックポイントが失われるため，かなり前のタスクから計算をやり直す必要が生じる．提案手法ではこのようなケースが生じないようなタスクスケジュールを生成する．本手法は並列アルゴリズムとして設計されており，入力サイズが十分大きければ，プロセッサ数が$n$のときに，$O(n)$のスケジュール作成時間のスピードアップが達成できる．シミュレーションと実機4台を使用した実験により提案手法の評価を行い，故障発生時にタスク処理時間を既存手法より最大で約30%程度短縮できる一方，故障が発生していないときのオーバヘッドが実験で用いたいくつかの設定において3%程度に収まることを確認した．

In this paper, we propose a task scheduling algorithm for a multicore processor system which reduces the recovery time in case of a single fail-stop failure of a multicore processor. Many of recently developed processors have multiple cores on a single die, and one failure of a computing node causes failure of many processors. In case of a failure of a multicore processor, all tasks which have been executed on the failed multicore processor have to be recovered at once. The proposed algorithm is based on an existing checkpointing technique, and we assume that checkpoints are taken when a node sends a result to the next node. If a series of computation that depends on former results is executed on a single multicore processor, we need to execute all part of the series of computation again in case of failure of the processor. The proposed scheduling algorithm tries to avoid generating a schedule that takes long recovery time. We designed our algorithm as a parallel algorithm that achieves O(n) speedup if the input size is sufficiently large where n is the number of processors. We evaluated our method using simulations and experiments with four PCs. By comparing our method with existing scheduling method, we confirmed that the execution time including recovery time in case of a node failure is reduced by 20 to 30% with a few percent of overhead in the execution time in case of no failure.

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ