Array subscript bit vector表示による依存解析手法

概要

論文の詳細を見る
自動並列化コンパイラにおいて、ソースコード中の並列性を最大限に引き出すためには強力なデータ依存解析が必要である。特にループにおいてループキャリィドディペンデンス解析を行う場合には、制御変数の値域を考慮しつつ配列変数の添字式を解析しなければならない。データ依存解析の従来手法としてはGCD testが最も簡単な手法の一つとして知られているが、ネストしたループにおいて解析対象となる配列変数の添字式Subが式(1)のような複数の制御変数による線形一次式で表現される場合に適用できない。このような場合にはOmega testなどが使用されるが、最悪の条件下では解析時間のオーダー関数が指数関数となることが知られている。Sub=a_0+a_1・I_1+a_2・I_2+……a_k・I_k+……a_n・I_n(1)(ただしI_kは制御変数、a_kは定数係数)本稿ではこのようなネストループの問題に対して、各々の配列要素にビットを対応させたビットベクトルであるArray Subscript Bit vectorを用いたデータ依存解析手法を提案する。本手法は単純な論理演算によるネストループにおける複数制御変数線形一次式で表現される依存解析を短い時間で行なうことを可能とする。
一般社団法人情報処理学会の論文
1995-03-15