並列化可能性判定のための配列データ依存解析問題のモデル化とシンプレックス法を基とする解法の提案

• Item type: SIG Technical Reports(1)
• 公開日: 2004-09-13
• タイトル: 並列化可能性判定のための配列データ依存解析問題のモデル化とシンプレックス法を基とする解法の提案
• タイトル / 言語: en
• タイトル: Modeling of Array Data Dependence Analysis Problem for Parallelization and Proposal of Its Solving Algorithm based on Simplex Method
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 和歌山大学大学院システム工学研究科
• 著者所属: 京都大学工学研究科附属情報センター
• 著者所属: 和歌山大学システム工学部
• 著者所属: 立命館大学情報理工学部情報システム学科
• 著者所属(英): 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テストより，高速に厳密な解析を行う新たな手法を提案する．本手法は，線形計画法と全探索を組みあわせ，さらに，GCDテスト，Banerjeeテスト，分離テストの機能をも取り込んだ新しい独自の総合的アルゴリズムである．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Data dependence analysis is essential for automatic parallelizing compilers. Several dependence analysis tests on array data have already been proposed. Each test cannot avoid the trade-off between its speed and exactness. Among conventional tests, Omega test is well known as an exact test. 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 linear programming and exhaustive solution search method. This algorithm also includes the features of GCD test, Banerjee test, and Separability test.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 2004, 号 92(2004-MPS-051), p. 9-12, 発行日 2004-09-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会