反辞書木を用いた分岐予測手法

西新 幹彦  森田 啓義  太田 隆博  

誌名
電子情報通信学会論文誌 A   Vol.J93-A   No.3   pp.204-206
発行日: 2010/03/01
Online ISSN: 1881-0195
Print ISSN: 0913-5707
論文種別: レター
専門分野: 
キーワード: 
反辞書,  分岐予測,  接尾辞木,  極小禁止語,  パターンマッチング,  

本文: PDF(85.4KB)
>>論文を購入


あらまし: 
パイプライン処理によるマイクロプロセッサの高速化の効果を十分に生かすためには,分岐成立の有無を高い精度で予測することが必要である.計算機資源に制限をおかないという条件のもとで,吉瀬と岩田は分岐成立の有無を実行順に並べた二元系列に対してJacquetらの手法でパターンマッチングに基づく分岐予測を行い,高い精度を達成した.の手法は定常ミクシング情報源に対して漸近的に最良な予測をすることが理論的に保証されている.一方,Ota and Moritaは接尾辞木を拡張した反辞書木と呼ばれる構造を用いて,パターンマッチングに相当する処理を線形の計算時間で行うモデリング手法を提案している.そこで本論文では,線形時間で同等の結果を得るために,の手法を分岐予測に適用することを提案する.実験の結果,とほぼ同等の予測精度を達成しつつ,実行時間は50分の1から5400分の1程度に短縮された.