| 講演名 | 2007-10-18 反辞書木を用いた分岐予測手法 西新 幹彦, 森田 啓義, 太田 隆博, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | パイプライン処理によるマイクロプロセッサの高速化を妨げないためには,分岐成立の有無を高い精度で予測することが必要である.計算機資源に制限をおかないという条件の下で,吉瀬と岩田[1]は分岐成立の有無を実行順に並べた2元系列に対してJacquet et al.[2]の手法でパターンマッチングに基づく分岐予測を行い,高い精度を達成した.[2]の手法は定常ミキシング情報源に対して漸近的に最良な予測をすることが理論的に保証されている.一方,Ota and Morita[3]は接尾辞木に逆MFリンクを付け加えた反辞書木と呼ばれる構造を用いて,パターンマッチングに相当する処理を線形の計算時間で行うモデリング手法を提案している.そこで本研究では,現実的な実行速度で同等の結果を得るために,[3]の手法を予測に適用して分岐予測を行った.実験の結果,予測精度は[1]よりわずかに悪くなる傾向があるが,実行時間は50分の1から4600分の1程度に短縮された. |
| 抄録(英) | It is necessary to predict by high accuracy the results of the branch commands so as not to obstruct the speed-up of microprocessors by the pipelining. Under the condition of not putting the limitation on the computer resources Kise and Iwata [1] did the branch prediction with high accuracy by means of the technique of Jacquet et al. [2] which is based on the pattern matching. It is theoretically guaranteed that the technique of [2] is asymptotically optimal for stationary mixing sources. On the other hand, Ota and Morita [3] have proposed a modeling technique for the processing that corresponds to the pattern matching at a linear computing time by using the structure that is called an anti-dictionary tree that consists of a suffix tree and reversed MF links on it. In this research, the technique of [3] is applied to the branch prediction to obtain the same results as with [2] at a practical execution speed. As results of the experiments, the execution times are shortened from 1/50 to 1/4600 with hardly more inferior prediction accuracy than [1]. |
| キーワード(和) | 反辞書 / 分岐予測 / 接尾辞木 / 極小禁止語 / パターンマッチング |
| キーワード(英) | Antidictionary / branch prediction / suffix tree / minimal forbidden word / pattern matching |
| 資料番号 | CAS2007-38,NLP2007-66 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2007/10/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 反辞書木を用いた分岐予測手法 |
| サブタイトル（和） | |
| タイトル（英） | Branch Prediction Based on Antidictionary Tree |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 反辞書 / Antidictionary |
| キーワード(2)（和/英） | 分岐予測 / branch prediction |
| キーワード(3)（和/英） | 接尾辞木 / suffix tree |
| キーワード(4)（和/英） | 極小禁止語 / minimal forbidden word |
| キーワード(5)（和/英） | パターンマッチング / pattern matching |
| 第 1 著者 氏名（和/英） | 西新 幹彦 / Mikihiko NISHIARA |
| 第 1 著者 所属（和/英） | 信州大学工学部 Faculty of Engineering, Shinshu University |
| 第 2 著者 氏名（和/英） | 森田 啓義 / Hiroyoshi MORITA |
| 第 2 著者 所属（和/英） | 電気通信大学情報システム学研究科 Graduate School of Information Systems, The University of Electro-Communications |
| 第 3 著者 氏名（和/英） | 太田 隆博 / Takahiro OTA |
| 第 3 著者 所属（和/英） | 長野県工科短期大学校電子技術科 Department of Electronic Engineering, Nagano Prefectural Institute of Technology |
| 発表年月日 | 2007-10-18 |
| 資料番号 | CAS2007-38,NLP2007-66 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 266 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |