例外依存関係を越える部分冗長性除去

• Item type: Trans(1)
• 公開日: 2005-01-15
• タイトル: 例外依存関係を越える部分冗長性除去
• タイトル / 言語: en
• タイトル: Partial Redundancy Elimination beyond Exception Dependency
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学情報理工学系研究科コンピュータ科学専攻
• 著者所属: 東京大学情報理工学系研究科コンピュータ科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo
• 著者名: 大平, 怜; 平木, 敬
• 著者名(英): Rei, Odaira; Kei, Hiraki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 実行時の安全を保証するための例外機構は一方で速度低下の原因となるため，部分冗長性除去（Partial Redundancy Elimination; PRE）で上方移動を用いて不要な例外命令を削除することが有効である．しかし我々はプログラムの意味を保つために例外命令どうしの順序関係である例外依存関係を保つ必要がある．したがって，従来の部分冗長性除去では例外命令の上方移動が阻害されることが多い．本研究で我々はプログラムの意味を保存しつつ例外依存関係を越える部分冗長性除去，Sentinel PRE を提案する．Sentinel PRE は例外依存関係を無視して上方移動を行い，その後で高速な解析により例外順序の入れ替わりを検出する．順序が入れ替わった例外命令で例外が起きた場合，プログラムの意味を保つために上方移動する前の状態に脱最適化でコードを戻す．現実のプログラムで例外が起きることは稀であるため，ほとんどの場合は上方移動により最適化された高速なコードが実行される．Sentinel PRE は特別なハードウェアのサポートには依存せず，動的なコード書き換えにより脱最適化を実現する．我々はSentinel PRE をJava の実行時コンパイラに実装して実験を行い，Java Grande Benchmark 中のheapsort プログラムで8.4%の性能向上を得た．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Exception mechanism guarantees runtime robustness, but results in performance degradation. Thus, it is effective to remove redundant excepting instructions by Partial Redundancy Elimination (PRE), which uses hoisting of instructions. However, we must preserve ordering constraints between excepting instructions, which we call exception dependencies, in order to keep the semantics of the program. Therefore, existing PRE algorithms cannot hoist many excepting instructions. In this work, we propose Sentinel PRE, a PRE algorithm which overcomes exception dependencies and at the same time keeps the semantics. Sentinel PRE first hoists excepting instructions without considering exception dependencies, and then detects exception reordering by fast analysis. If exception occurs at a reordered instruction, it deoptimizes the code into the one before hoisting. Since we rarely encounter exception in real programs, the optimized code is executed in almost all cases. Sentinel PRE does not rely on special hardware support, and performs deoptimization by runtime code patching. We implemented Sentinel PRE in a Java just-in-time compiler and conducted experiments. The results show 8.4% performance improvement in “heapsort” program in Java Grande Benchmark.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 46, 号 SIG1(PRO24), p. 134-148, 発行日 2005-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会