配列データを共有したループ文の並列実行のための漸進処理手法

概要

論文の詳細を見る
ループ文の並列実行では,イタレーション単位の並列実行が基本となっている.しかし,複雑なループ伝搬依存が存在するループ文では,イタレーション間の並列性を抽出することは困難である.また,計算機クラスタ環境では,タスク間通信オーバヘッドなどによりイタレーション単位の細粒度並列処理は適さない.本稿では,ループ文の並列実行方式である漸進処理を提案する.漸進処理では,同一配列データを操作する複数のループ文をパイプライン的に実行させる.ループ文はそれぞれ並列実行されるが,各ループ文内のイタレーションは逐次的に実行されるので,複雑なループ伝搬依存が存在しても適用可能である.また,イタレーションでなく,ループ文全体がタスク生成の単位となるので,タスク起動のオーバヘッドを削減でき,計算と通信のオーバラップにより通信オーバヘッドを減少させることができる.漸進処理を適用するためには,ループ文における配列データ要素の操作順序を解析する必要がある.我々はループ文での操作順序をアクセス・パターンとして定義し,漸進処理を効率的に行うためにアクセス・パターンの類似性を解析する漸進処理適用判定アルゴリズムを開発した.また,様々なループ文に対して漸進処理適用判定アルゴリズムを適用し,アルゴリズムの有効性についても調査した.
2001-04-15

配列データを共有したループ文の並列実行のための漸進処理手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク