| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-10-18 10:30 反辞書木を用いた分岐予測手法 ○西新幹彦（信州大）・森田啓義（電通大）・太田隆博（長野県工科短大）  CAS2007-38 NLP2007-66 |
|
| 抄録 | （和） | パイプライン処理によるマイクロプロセッサの高速化を妨げないためには，分岐成立の有無を高い精度で予測することが必要である．計算機資源に制限をおかないという条件の下で，吉瀬と岩田は分岐成立の有無を実行順に並べた2元系列に対してJacquet et al.の手法でパターンマッチングに基づく分岐予測を行い，高い精度を達成した．Jacquet et al.の手法は定常ミキシング情報源に対して漸近的に最良な予測をすることが理論的に保証されている． 一方，Ota and Moritaは接尾辞木に逆MFリンクを付け加えた反辞書木と呼ばれる構造を用いて，パターンマッチングに相当する処理を線形の計算時間で行うモデリング手法を提案している． そこで本研究では，現実的な実行速度で同等の結果を得るために，Ota and Moritaの手法を予測に適用して分岐予測を行った．実験の結果，予測精度は吉瀬と岩田よりわずかに悪くなる傾向があるが，実行時間は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 did the branch prediction with high accuracy by means of the technique of Jacquet et al. which is based on the pattern matching. It is theoretically guaranteed that the technique of Jacquet et al. is asymptotically optimal for stationary mixing sources. On the other hand, Ota and Morita 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 \cite{OTAMORITA} is applied to the branch prediction to obtain the same results as with Jacquet et al. 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 Kise and Iwata. |
|
| キーワード | （和） | 反辞書 / 分岐予測 / 接尾辞木 / 極小禁止語 / パターンマッチング / / / |
| （英） | antidictionary / branch prediction / suffix tree / minimal forbidden word / pattern matching / / / | |
| 文献情報 | 信学技報, vol. 107, no. 264, CAS2007-38, pp. 21-24, 2007年10月. | |
| 資料番号 | CAS2007-38 | |
| 発行日 | 2007-10-11 (CAS, NLP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CAS2007-38 NLP2007-66 |
|
| 研究会情報 | |
| 研究会 | CAS NLP |
| 開催期間 | 2007-10-18 - 2007-10-19 |
| 開催地（和） | 武蔵工業大学 |
| 開催地（英） | Musashi Institute of Technology |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | CAS |
| 会議コード | 2007-10-CAS-NLP |
| 本文の言語 | 日本語 |
| タイトル（和） | 反辞書木を用いた分岐予測手法 |
| サブタイトル（和） | |
| タイトル（英） | Branch Prediction Based on Antidictionary Tree |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 反辞書 / antidictionary |
| キーワード(2)（和/英） | 分岐予測 / branch prediction |
| キーワード(3)（和/英） | 接尾辞木 / suffix tree |
| キーワード(4)（和/英） | 極小禁止語 / minimal forbidden word |
| キーワード(5)（和/英） | パターンマッチング / pattern matching |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 西新 幹彦 / Mikihiko Nishiara / ニシアラ ミキヒコ |
| 第1著者 所属（和/英） | 信州大学 (略称： 信州大) Shinshu University (略称： Shinshu Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 森田 啓義 / Hiroyoshi Morita / モリタ ヒロヨシ |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) University of Electro-Communications (略称： UEC) |
| 第3著者 氏名（和/英/ヨミ） | 太田 隆博 / Takahiro Ota / オオタ タカヒロ |
| 第3著者 所属（和/英） | 長野県工科短期大学校 (略称： 長野県工科短大) Nagano Prefectural Institute of Technology (略称： PIT-Nagano) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-10-18 10:30:00 |
| 発表時間 | 20分 |
| 申込先研究会 | CAS |
| 資料番号 | CAS2007-38, NLP2007-66 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.264(CAS), no.266(NLP) |
| ページ範囲 | pp.21-24 |
| ページ数 | 4 |
| 発行日 | 2007-10-11 (CAS, NLP) |
[研究会発表申込システムのトップページに戻る]