シンプレックス法に基づく実用的な配列データ依存解析

• Item type: Trans(1)
• 公開日: 2005-01-15
• タイトル: シンプレックス法に基づく実用的な配列データ依存解析
• タイトル / 言語: en
• タイトル: A Practical Test for Array Data Dependence Analysis Based on Simplex Method
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: システムソフトウェア
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 和歌山大学大学院システム工学研究科
• 著者所属: 京都大学工学研究科附属情報センター
• 著者所属: 和歌山大学システム工学部
• 著者所属: 立命館大学情報理工学部情報システム学科
• 著者所属(英): en
• 著者所属(英): Graduate School of Systems Engineering, Wakayama University
• 著者所属(英): en
• 著者所属(英): Center for Information Technology, Faculty of Engineering,Kyoto University
• 著者所属(英): en
• 著者所属(英): Faculty of Systems Engineering, Wakayama University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, College of Information Science and Engineering, Ritsumeikan University
• 著者名: 峰尾, 昌明; 上原, 哲太郎; 齋藤, 彰一; 國枝, 義敏
• 著者名(英): Masaaki, Mineo; Tetsutaro, Uehara; Shoichi, Saito; Yoshitoshi, Kunieda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 自動並列化コンパイラにとって，並列実行可能性を判別するためにデータ依存解析モジュールは必須である．配列要素間のデータ依存解析手法は種々提案されており，各手法には解析の速度と厳密性との間にトレードオフがある．厳密性を重視した依存解析手法としてOmega テストが有名である．しかし，Omega テストは，解析にかかる時間が長く，また実装が困難である．本論文では，実装が容易かつ，Omega テストとほぼ同程度の厳密性を持ち，多くの場合Omega テストより，高速に解析を行う新たな手法を提案する．本手法は，線形計画法と全探索を組み合わせ，さらに，GCD テスト，Banerjee テスト，分離テストの機能をも取り込んだ新しい独自の統合的アルゴリズムとなっている．本論文では，この統合的アルゴリズムの詳細，実装および，性能評価について報告する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Data dependence analysis is essential for automatic parallelizing compilers. Compilers determine the possibility of parallelization on given source programs by using the result from data dependence analysis. Several dependence analysis tests on array data have already been proposed. Each test cannot avoid the trade-off between its analysis speed and exactness of analysis. Among conventional tests, Omega test is well known as an exact test for the broader class of index expressions ever. However, the algorithm of Omega test is so complicated that its analysis is very time consuming and it is difficult to implement Omega test. Therefore, in this paper a new original analysis method is proposed, whose algorithm is based and combined both Simplex method for linear programming and exhaustive solution search method. This algorithm also includes the features of GCD test, Banerjee test, and Separability test. The algorithm, implementation details of prototype and its evaluation applying to the concrete test programs are also described.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 46, 号 SIG3(ACS8), p. 11-24, 発行日 2005-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会