| 講演名 | 2006-06-23 部分冗長除去の命令スケジューリングへの応用 滝本 宗宏, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 命令レベル並列性を高める有効な手法の1つとして,命令スケジューリングがある.特に,投機的実行を許す命令スケジューリングは,さらに並列度を高められる点で効果的であることが知られている.投機的実行は,元のプログラムに存在しなかった冗長性を導入する可能性があるので,1つの命令にスケジューリングを適用するたびに,共通部分式除去を適用すると,さらなるスケジューリングが可能になる.本研究では,共通部分式除去では取り除けない部分冗長性を扱う部分冗長除去に注目し,部分冗長除去に基づく命令スケジューリングを提案する.本手法は,命令を移動したいプログラム点に命令を挿入したのち,部分冗長除去を適用することによって,冗長性を増やさないスケジューリングを実現する.本スケジューリング法がもつ部分冗長除去の性質は,どの実行パスも伸ばさないことを保証し,任意のループ構造に対して,ループシフティングを可能にする. |
| 抄録(英) | Instruction scheduling is an effective technique to increase the operations which can be executed in parallel. 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 during the instruction scheduling opens a way for scheduling other operations. We propose an instruction scheduling approach based on partial redundancy elimination which is a technique for eliminating redundant expressions. Since the partial redundancy elimination can deal with not only the totally redundant expressions which common sub-expression elimination can eliminate but also partially redundant expressions, it eliminates more redundant expressions, and therefore, enables more operations to be scheduled. In addition to that, we focus on a property which partial redundancy elimination eliminates redundant expressions based on code motion. This property enables automatically inserting any compensation code after scheduling an operation to a specific idle resource. Hence, our scheduling approach not only guarantees that any execution path is not lengthened, but can also achieve a loop scheduling, i.e. loop shifting. |
| キーワード(和) | 命令スケジューリング / 部分冗長除去 / ループシフティング / データフロー解析 |
| キーワード(英) | Instruction Scheduling / Partial Redundancy Elimination / Loop Shifting / Dataflow Analysis |
| 資料番号 | SS2006-20 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 2006/6/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 部分冗長除去の命令スケジューリングへの応用 |
| サブタイトル（和） | |
| タイトル（英） | Applying Partial Redundancy Elimination to Instruction Scheduling |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 命令スケジューリング / Instruction Scheduling |
| キーワード(2)（和/英） | 部分冗長除去 / Partial Redundancy Elimination |
| キーワード(3)（和/英） | ループシフティング / Loop Shifting |
| キーワード(4)（和/英） | データフロー解析 / Dataflow Analysis |
| 第 1 著者 氏名（和/英） | 滝本 宗宏 / Munehiro TAKIMOTO |
| 第 1 著者 所属（和/英） | 東京理科大学理工学部 Faculty of Science and Technology, Tokyo University of Science |
| 発表年月日 | 2006-06-23 |
| 資料番号 | SS2006-20 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 121 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |