Task Scheduling Algorithm to Minimize Recovery Time in Case of Single Node Fault in Multicore Processor System

摘要

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