コンパイル時未定義ループ不変値を添字式に持つループの最内ループ並列化の1手法

概要

論文の詳細を見る
データ並列言語の典型的なSPMDコード生成では、ループのインデックス空間をowner computes規則に基づいて分割するコードが生成される。コンパイラによる最適化として、分割された計算に必要なデータを可能な限り外側ループあるいはループの外でプリフェッチさせることで、より多くの計算を同期的通信なしに実行するコードを生成することがあげられる。また同期的通信によって、pipelined computationなどSPMDコードの並列実行様式が決定される。元のプログラムの意味を壊さずにプリフェッチを行なってプログラムをゆるい同期の下に並列に実行するためにはデータのdef-useの関係を調べることが必要である。そのためにコンパイル時のデータ依存解析が重要である。プリフェッチするデータをどのプロセッサが所有し、それら所有プロセッサが定義するどの時点の値を読み込むのかを解析する。しかしデータ依存解析によってある配列参照についてデータ依存が複数の可能性を持つと判明した場合、その配列参照の値を定義するステートメントが1つに決まらない。そのため、データ依存のdef-use関係に基づいた単純なメッセージベクタ化ができない。SPMDプログラムは1つのプログラムが全プロセッサで使用されるため、プロセッサごとの場合分けコードを挿入するとコードが増大し易い。詳細な場合分けによる最適化は、コードサイズを爆発させる可能性が大きい。そのためコードを大幅に増やさずに並列性を引き出す手法が現実的である。本稿では、コードを大幅には増やさずに、複数のデータ依存可能性を伴う最内ループが持つ並列性を引き出す手法を提案する。
1994-09-20

コンパイル時未定義ループ不変値を添字式に持つループの最内ループ並列化の1手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク