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

• Item type: Trans(1)
• 公開日: 2010-03-16
• タイトル: 自動並列化のためのElement-Sensitiveポインタ解析
• タイトル / 言語: en
• タイトル: Element-Sensitive Pointer Analysis for Automatic Parallelization
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 早稲田大学基幹理工学部情報理工学科
• 著者所属: 早稲田大学基幹理工学部情報理工学科
• 著者所属: 早稲田大学基幹理工学部情報理工学科
• 著者所属: 早稲田大学基幹理工学部情報理工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science and Engineering, Waseda University
• 著者名: 間瀬, 正啓; 村田, 雄太; 木村, 啓二; 笠原, 博徳
• 著者名(英): Masayoshi, Mase; Yuta, Murata; Keiji, Kimura; Hironori, Kasahara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: マルチコアプロセッサの普及にともない，C 言語のような逐次型言語で記述されたプログラムのコンパイラによる自動並列化が期待されている．しかしながら，科学技術計算やメディア処理アプリケーションのアルゴリズムは潜在的に高い並列性を持っていながら，従来のポインタ解析技術では並列性の自動抽出にはしばしば不十分なことがある．たとえば，アルゴリズム上は多次元配列として扱うことが可能なデータ構造を，ポインタへのポインタとメモリ動的確保を行うループの記述により実装する場合がある．このようなデータ構造に対して従来のポインタ解析の適用を考えた場合，配列の各要素の情報が配列全体で単一の情報に縮退されてしまうため，コンパイラによる依存解析ができず，自動並列化が阻害されてしまう．そこで本論文では，ポインタの配列において各要素の指し先のエイリアス関係を識別可能な Element-Sensitive ポインタ解析を提案する．提案する Element-Sensitive ポインタ解析では，既存のポインタ解析手法に対して簡単な追加情報を加えるだけで，自動並列化に有用なポインタ解析精度を得ることができる．ポインタの配列の各要素に指し示されるオブジェクトに重なりがない場合は，そのようなポインタが指し示すデータ構造を多次元配列と同様に並列性抽出の対象とすることが可能となる．また，Element-Sensitive ポインタ解析のアルゴリズムとともに，その解析結果の自動並列化への適用方法についても述べる．自動並列化による速度向上について，8 コア構成のサーバである IBM p5 550Q 上で性能評価を行ったところ，科学技術計算やマルチメディア処理を行う 4 つのアプリケーションプログラムについて，逐次実行時と比較して平均 5.50 倍の速度向上が得られた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: As multicore processors become widely used, there is an increasing need to achieve automatic parallelization of sequential programs written in C language by a compiler. However, traditional pointer analysis techniques are often insufficient in automatically extracting parallelism even when target scientific and media applications have large amount of inherent parallelism in their algorithms. For example, a compiler cannot analyze data dependencies for a data structure implemented by a pointer to pointer variable and memory allocation loops, even though the data structure can be essentially realized by a multiple dimensional array in an algorithm. For these data structures, traditional pointer analysis techniques aggregate information for each element in an array of pointer into information for the whole array, hamper automatic parallelization. This paper proposes element-sensitive pointer analysis, which can distinguish the alias relation among elements in an array of pointer. The proposed element-sensitive pointer analysis can acqire a sensitivity beneficial for automatic parallelization through just adding simple information to conventional pointer analyses. When there is no overlap among objects pointed-to by different array elements of the array of pointers, the pointed data structure can be treated as same as multiple dimensional array in parallelism extraction. The element-sensitive pointer analysis algorithm is described as well as its application method for automatic parallelization is shown. As the result, on IBM p5 550Q 8 cores server, automatic parallelization achieves 5.50x speedup against sequential execution on average for 4 application programs with element-sensitive pointer analysis.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 3, 号 2, p. 36-47, 発行日 2010-03-16
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会