文献

J-GLOBAL ID：201002256411276896   整理番号：10A0440784

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

Element-Sensitive Pointer Analysis for Automatic Parallelization

著者 (4件)： 間瀬正啓 (早稲田大 基幹理工) ,  村田雄太 (早稲田大 基幹理工) ,  木村啓二 (早稲田大 基幹理工) ,  笠原博徳 (早稲田大 基幹理工)
資料名： 情報処理学会論文誌トランザクション(CD-ROM)  (情報処理学会論文誌 Computer Vision and Applications(CD-ROM))
巻： 2009  号： 2  ページ： PUROGURAMINGU.VOL.3,NO.2,36-47  発行年： 2010年04月15日 
JST資料番号： L7379A  ISSN： 1882-7772  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *並列化 ,  マイクロプロセッサ ,  *コンパイラ ,  アルゴリズム ,  データ構造 ,  *プログラム解析 ,  高速化 ,  性能評価 ,  マルチメディア
準シソーラス用語： *ポインタ解析 ,  マルチコアプロセッサ ,  科学技術計算 ,  *自動並列化

分類 (2件)： ディジタル計算機方式一般  (JC02010O) ,  言語プロセッサ  (JD03040F)

引用文献 (24件)：

• Eigenmann, R., Hoeflinger, J. and Padua, D.: On the Automatic Parallelization of the Perfect Benchmarks, IEEE Trans. parallel and distributed systems, Vol.9, No.1(1998).
• Hall, M. W., Anderson, J. M., Amarasinghe, S. P., Murphy, B. R., Liao, S., Bugnion, E. and Lam, M. S.: Maximizing Multiprocessor Performance with the SUIF Compiler, IEEE Computer (1996).
• 笠原博徳: 最先端の自動並列化コンパイラ技術, 情報処理, Vol.44, No.4 (通巻458号), pp. 384-392(2003).
• ISO/IEC 9899: 1999 — Programming Language C (1999).
• Hind, M.: Pointer Analysis: Haven’t We Solved This Problem Yet?, PASTE’01(2001).

タイトルに関連する用語 (2件)： 自動並列化 ,  ポインタ解析