割当て・評価スケジューリングアルゴリズムによる並列化コンパイラ

佐谷野 健二  白川 友紀  

誌名
電子情報通信学会論文誌 D   Vol.J81-D1   No.3   pp.221-232
発行日: 1998/03/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 計算機システム
キーワード: 
並列化コンパイラ,  スケジューリング,  発見的手法,  実行時間評価,  

本文: PDF(904.1KB)>>
論文を購入




あらまし: 
本論文では,リストスケジューリングのような発見的手法にプログラムの実行時間評価を組み合わせた,割当て・評価スケジューリングアルゴリズム(AESA)について述べている.AESAによってスケジューリングを行う際に必要となる実行時間の評価方法として,従来のようなプロセッサ間通信時間を式を用いて表す簡易評価の他に,パケットの衝突やバッファのあふれを考慮したプロセッサ間通信モデルを用いて実行時間を評価する詳細評価について検討を行った.更に,このような実行時間評価の際に問題となる処理時間の増大を抑えるために,実行時間の評価範囲を制限する範囲指定評価や,その改良手法である継続範囲指定評価について検討を行った.また本研究では,AESAの技術に基づく並列化コンパイラを開発し,サンプルプログラムを用いて性能評価を行った.この結果,FFT,Gauss消去,N-Bodyの各プログラムで,簡易評価に対する詳細評価の有効性の高さが確認された.継続範囲指定評価では,適切な評価範囲を用いることで,詳細評価より実行時間の評価処理を短縮しながら,詳細評価とほぼ同程度の性能が得られることが確認された.