配列アクセス解析

コンピュータサイエンスにおいて、配列アクセス解析は、配列の要素または一部への読み取りおよび書き込みアクセスパターンを決定するために使用されるコンパイラ解析アプローチです。 ^{[ 1 ]}

科学プログラムで操作される主要なデータ型は配列です。配列全体の定義/使用解析だけでは、自動並列化や配列のプライベート化といった積極的なコンパイラ最適化には不十分です。配列アクセス解析は、特定のコードセグメント（基本ブロック、ループ、あるいはプロシージャレベル）が配列のどの部分、あるいはどの要素にアクセスしているかを把握することを目的としています。

配列アクセス解析は、精度と複雑さのトレードオフの違いから、厳密法（または参照リストベース法）と要約法に大きく分類できます。厳密法は精度が高いものの、計算量と記憶容量の点で非常にコストがかかります。一方、要約法は近似値ですが、迅速かつ経済的に計算できます。

典型的な正確な配列アクセス解析には、線形化と原子画像化が含まれます。要約手法はさらに、配列セクション、トリプレット表記法を用いた境界付き正規セクション、データアクセス記述子などの線形制約法、および配列領域解析に分類できます。

参考文献

1. Paek, Yunheung; Hoeflinger, Jay; Padua, David (2002年1月). 「効率的かつ正確な配列アクセス解析」 . ACM Transactions on Programming Languages and Systems . 24 (1): 65– 109. doi : 10.1145/509705.509708 .