マルチプロセッサシステムのためのプログラム構造を考慮したフォールトトレラントスケジューリング

• 橋本 幸司

  大阪大学 大学院基礎工学研究科 情報数理系専攻

• 土屋 達弘

  大阪大学 大学院基礎工学研究科 情報数理系専攻

• 菊野 亨

  大阪大学 大学院基礎工学研究科 情報数理系専攻

書誌事項

タイトル別名

• A Scheduling Algorithm Using Height-Based Partitioning for Fault-Tolerance in Multiprocessor Systems

抄録

本稿では, マルチプロセッサシステムにおいてフォールトトレランスを実現するためのタスクスケジューリング法を提案する.提案法では, まず並列プログラムを表現するタスクグラフの構造を陽に考慮して, 全体のタスク集合を部分集合に分割する.その分割に当たっては, 各部分集合に属するタスク間で実行依存関係を持たないようにする.次に, 分割された各部分集合毎にそこに属するタスクの多重化を行なってタスクスケジュールを求める.最後に, 代表的数値演算処理プログラムであるガウス消去法, ラプラス方程式解法, LU分解法を対象に, 提案法の評価のための適用実験を行った.その結果, 従来法に比べ提案アルゴリズムの実行時間が大幅に短縮できることがわかった.更に, 従来法に比べプロセッサの故障が存在する場合のプログラムの終了時間が大幅に改善できることも明らかになった.
In this paper, we propose a new scheduling algorithm for achieving fault-tolerance in multiprocessor systems. The proposed algorithm partitions a set of tasks associated with a given task graph into subsets such that all tasks in each subset have no data dependencies among them. Then based on the partition, the algorithm duplicates and schedules its tasks for each subset successively. Finally, using three kinds of practical task graphs (Gaussian elimination, Laplace equation solver and LU-decomposition), we conducted simulation studies. Experimental results show that fault-tolerance can be achieved at the cost of small degree of time redundancy, and that performance in the case of a processor failure is improved compared to a previous algorithm.

収録刊行物

• 電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス

  電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス 98 (294), 15-22, 1998-09-21

  一般社団法人電子情報通信学会

キーワード

• マルチプロセッサシステム
• フォールトトレランス
• スケジューリング
• タスクグラフ

詳細情報

• CRID: 1570854177462354432
• NII論文ID: 110003276992
• NII書誌ID: AN10013287
• 本文言語コード: en
• データソース種別:
  • CiNii Articles