ループレベル並列処理における実行時間を考慮したスケジューリングアルゴリズムとその評価
スポンサーリンク
概要
- 論文の詳細を見る
並列処理の問題の中に,プログラムのどの部分をどのプロセッサにどのような順番で割り当てれば,並列計算機の性能を最大限発揮させることができるのかというスケジューリングの問題がある.ループレベルでのスケジューリングアルゴリズムの代表的なものとして,静的スケジューリング,動的スケジューリング,ガイデッドセルフスケジューリング(以下GSS)がある.このうち,静的スケジューリングはコンパイル時にスケジューリングを行うために,ループ本体の実行時間にばらつきがある場合負荷の分散が不平等になる恐れがあるが,実行時のオーバーヘッドはほとんどない.逆に動的スケジューリングの場合,実行時にスケジューリングを行うために,そのオーバヘッドが問題になるが,ループ本体の実行時間にばらつきがある場合でも負荷が各プロセッサに均等に分散される.このように,実行時のオーバーヘッドと負荷の分散不均一によるオーバーヘッドはトレードオフの関係にあり,両方を同時に改善することは困難である.GSSは静的スケジューリングに比べ,多少実行時のオーバーヘッドを犠牲にすることで,負荷の均一化を図っているが,完全な負荷の均一化はできない.本論文では,負荷分散の均一化の観点から静的動的融合スケジューリングアルゴリズムとif分岐を考慮したGSSの2つのスケジューリングアルゴリズムを提案する.いずれのアルゴリズムもループ本体の実行時間が既知の場合に使用可能であり,これら2つのスケジューリングアルゴリズムを組み合わせて用いることで,従来の動的スケジューリング同様に負荷分散の均一化を図ることができ,しかも従来の動的スケジューリングに比べ大幅に実行時のオーバーへッドを削減することができる.
- 一般社団法人情報処理学会の論文
- 1992-02-24
著者
関連論文
- データベースを用いたデータ解析のための集合操作
- 集合の階層を保持するデータベース
- 実行時エラーのプログラム相談システム『Consult:R』
- コンパイルエラーのプログラム相談システム『Consult:C』の評価
- 並列処理におけるタスクスケジューリングアルゴリズムの性能評価について
- ループレベル並列処理における実行時間を考慮したスケジューリングアルゴリズムとその評価
- 樹木生成におけるブレンドの応用
- 表示的意味論によるC言語の意味記述と処理系作成への応用
- ベクトル計算によるラジオシティ法の高速化
- マルチプロセッサをクラスタ化したときのマルチタスク環境におけるスケジューリング方式とその評価
- 九州大学大型計算機センターを中心とするネットワーク構築の現状と問題点
- メトリックス・統計調査によるベクトル処理用プログラムの特徴の把握
- 4元数の3次元空間フラクタルを用いた樹状パターンの生成
- 分散共有メモリシステム上にソフトウェアによって構築されたキャッシュシステムの静的制御
- 分散環境における共有メモリ型SPMDプログラミングモデル : Split-C/PVMの実装
- 非同期通信によって自動最適化を行なう並列化コンパイラの設計
- 大規模線形計算パッケージLAPACKのベクトル計算機上での最適化と性能評価について
- 並列化コンパイラにおけるプロセッサ間非同期通信命令を用いた通信コストの最適化