等式分割を用いた配列データ依存解析手法

スポンサーリンク

概要

論文の詳細を見る
逐次的な手続き型言語のプログラムを自動並列化する際には(多重)ループ中に含まれる配列操作に対してデータ依存解析を行い並列実行可能であるかどうかを判定する。つまり参照の添字が繰返し空間内で同じ値を取り得るかを判定する必要があり, 一般には不等式の制約下で連立方程式を解く問題となる。このデータ依存解析の手法としてはGCDテスト, Banerjeeの不等式の手法, Omegaテスト, V-Pascalの手法などがある。このうち後二者は上下限式や添字式が制御変数の線形式である場合に厳密な解析が可能だが, これらの手法は解析にかかるコストが問題であった。そこで本研究では, それぞれの変数の上限と下限の制約が静的に決定できる時に一つの整等式が複数の整等式からなる連立方程式に分解できる場合があることに着目して, 配列データ依存解析の効率化手法を提案する。
1997-09-24

著者

関連論文

もっと見る

スポンサーリンク