部分冗長除去に基づく大域命令スケジューリング

• Item type: Trans(1)
• 公開日: 2007-08-15
• タイトル: 部分冗長除去に基づく大域命令スケジューリング
• タイトル / 言語: en
• タイトル: Global Instruction Scheduling Based on Partial Redundancy Elimination
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 株式会社野村総合研究所
• 著者所属: 東京理科大学理工学部情報科学科
• 著者所属(英): en
• 著者所属(英): Nomura Research Institute, Ltd.
• 著者所属(英): en
• 著者所属(英): Department of Information Sciences, Faculty of Science and Technology, Tokyo University of Science
• 著者名: 勝原, 達也; 滝本, 宗宏
• 著者名(英): Tatsuya, KATSUHARA; Munehiro, TAKIMOTO
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 命令レベル並列性を高める有効な手法の 1 つとして、命令スケジューリングがある。特に、投機的実行を許す命令スケジューリングは、さらに並列度を高められる点で効果的であることが知られている。投機的実行は、元のプログラムに存在しなかった冗長性を導入する可能性があるので、1 つの命令をスケジュールするたびに共通部分式の削除を適用することが効果的である。本発表では、共通部分式の削除で取り除くことができない部分冗長性を扱う部分冗長除去に注目し、部分冗長除去に基づく大域命令スケジューリングを提案する。本手法は、あるプログラム点に対して、投機的命令スケジューリングを含むコードの上方移動を行うごとに、部分冗長除去のデータフロー解析を適用する。解析結果から最適化効果が認められる場合、実際にプログラムを変更することで、命令スケジューリングを実現する。部分冗長除去の性質は、プログラムの実行パスを長くしないことを保証し、大域命令スケジューリングで問題となる補償コードを最適なプログラム点に自動的に挿入する。また、本手法は、ループ構造を認識することなく、ループスケジューリング手法の 1 つである、ループシフティングを実現することができる。さらに本論文では、本手法を COINS コンパイラ・インフラストラクチャ上で実装し、最適化効果を検証する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Instruction scheduling is one of the effective techniques to increase Instruction-level parallelism. Especially, the instruction scheduling which allows speculative execution is known as a technique which exposes more parallelism in a program. Since the speculative execution can introduce new redundant expressions as a second order effect, eliminating the redundant expressions using common sub-expression elimination (CSE) opens a way for scheduling other operations. We propose an instruction scheduling approach based on partial redundancy elimination (PRE) which eliminates more redundant expressions than CSE does. PRE can eliminate not only totally redundant expressions which CSE can eliminate but also partially redundant expressions, therefore leads to more opportunities to schedule. In addition to that, we focus on a property such that PRE eliminates redundant expressions based on code motion. This property enables determining whether scheduling to a specific idol resource is effective or not, and automatically inserting any compensation code to optimal points after scheduling. Hence, our scheduling approach guarantees that any execution paths are not lengthened. Our approach can also be applied to any program structures, and achieve a loop scheduling, i.e. loop shifting, without identifying loop structure.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 48, 号 SIG12(PRO34), p. 52-65, 発行日 2007-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会