自動並列化のためのElement-Sensitiveポインタ解析

概要

論文の詳細を見る
マルチコアプロセッサの普及にともない,C 言語のような逐次型言語で記述されたプログラムのコンパイラによる自動並列化が期待されている.しかしながら,科学技術計算やメディア処理アプリケーションのアルゴリズムは潜在的に高い並列性を持っていながら,従来のポインタ解析技術では並列性の自動抽出にはしばしば不十分なことがある.たとえば,アルゴリズム上は多次元配列として扱うことが可能なデータ構造を,ポインタへのポインタとメモリ動的確保を行うループの記述により実装する場合がある.このようなデータ構造に対して従来のポインタ解析の適用を考えた場合,配列の各要素の情報が配列全体で単一の情報に縮退されてしまうため,コンパイラによる依存解析ができず,自動並列化が阻害されてしまう.そこで本論文では,ポインタの配列において各要素の指し先のエイリアス関係を識別可能な Element-Sensitive ポインタ解析を提案する.提案する Element-Sensitive ポインタ解析では,既存のポインタ解析手法に対して簡単な追加情報を加えるだけで,自動並列化に有用なポインタ解析精度を得ることができる.ポインタの配列の各要素に指し示されるオブジェクトに重なりがない場合は,そのようなポインタが指し示すデータ構造を多次元配列と同様に並列性抽出の対象とすることが可能となる.また,Element-Sensitive ポインタ解析のアルゴリズムとともに,その解析結果の自動並列化への適用方法についても述べる.自動並列化による速度向上について,8 コア構成のサーバである IBM p5 550Q 上で性能評価を行ったところ,科学技術計算やマルチメディア処理を行う 4 つのアプリケーションプログラムについて,逐次実行時と比較して平均 5.50 倍の速度向上が得られた.
2010-03-16

自動並列化のためのElement-Sensitiveポインタ解析

スポンサーリンク

概要

著者

関連論文

スポンサーリンク