TOP > 国内特許検索 > 情報処理装置および方法、並びにプログラム > 明細書

明細書 :情報処理装置および方法、並びにプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5283054号 (P5283054)
公開番号 特開2009-037305 (P2009-037305A)
登録日 平成25年6月7日(2013.6.7)
発行日 平成25年9月4日(2013.9.4)
公開日 平成21年2月19日(2009.2.19)
発明の名称または考案の名称 情報処理装置および方法、並びにプログラム
国際特許分類 G06F   9/38        (2006.01)
FI G06F 9/38 330B
請求項の数または発明の数 13
全頁数 33
出願番号 特願2007-199159 (P2007-199159)
出願日 平成19年7月31日(2007.7.31)
審査請求日 平成22年7月15日(2010.7.15)
特許権者または実用新案権者 【識別番号】504133110
【氏名又は名称】国立大学法人電気通信大学
発明者または考案者 【氏名】二ノ宮 康之
【氏名】阿部 公輝
個別代理人の代理人 【識別番号】100082131、【弁理士】、【氏名又は名称】稲本 義雄
【識別番号】100121131、【弁理士】、【氏名又は名称】西川 孝
審査官 【審査官】三坂 敏夫
参考文献・文献 国際公開第2008/012957(WO,A1)
C. Y. Ho et al.,"Combining Local and Global History Hashing in Perceptron Branch Prediction",IEEE/ACIS International Conference on Computer and Information Science, 2007. ICIS 2007. 6th ,米国,IEEE,2007年 7月13日,Pages:54-59
石井 康雄 他,「実行パス履歴情報を利用した分岐予測手法」,情報処理学会論文誌,日本,社団法人情報処理学会,第47巻 No.SIG3(ACS13),58頁~72頁
澁川 誠 他,「パーセプトロン分岐予測器への冗長入力付加の効果とその最適化」,先進的計算基盤システムシンポジウム SACSIS2006 論文集,日本,社団法人情報処理学会,2006年 5月22日,第2006巻 第5号,307頁~314頁
二ノ宮 康之 他,「実行パスとローカル履歴を重み選択に利用したパーセプトロン分岐予測器」,情報処理学会研究報告,日本,社団法人情報処理学会,2006年 8月 1日,2006-ARC-169(6),31頁~36頁
調査した分野 G06F 9/38
特許請求の範囲 【請求項1】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、
前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、
最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、
前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルと、
前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、
前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、
前記重み付き分岐結果値算出手段により最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、
少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段と
を備える情報処理装置。
【請求項2】
少なくとも、前記重み選択手段による前記重みの選択、および、前記重み付き分岐結果値算出手段による重み付き分岐結果の算出をステージ1とし、
少なくとも、前記予測値算出手段による予測値の算出をステージ0とし、
ステージ毎に順次処理を行う
請求項1に記載の情報処理装置。
【請求項3】
前記ステージ1における処理の処理結果を保持する保持手段をさらに備え、
前記分岐命令の分岐方向の予測の度に、前記ステージ0の処理、および、前記ステージ1の処理を行い、
前記ステージ1の処理の処理結果を前記保持手段に保持させるとともに、前記ステージ0の処理を、前記保持手段に保持されている前回の予測において行われた前記ステージ1の処理の処理結果を用いて行う
請求項2に記載の情報処理装置。
【請求項4】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ1とし、
前記ステージ1において前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値の累算結果を前記保持手段に保持させ、
前記ステージ0において、前記予測値算出手段により、前記保持手段に保持されている前記累算結果を用いて前記予測値を算出させる
請求項3に記載の情報処理装置。
【請求項5】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算の一部を前記ステージ1とし、残りの一部を前記ステージ0とし、
前記ステージ1において、前記重み付き分岐結果値累算手段により、前記重み付き分岐結果値の累算を途中まで行わせ、
得られた累算途中結果を前記保持手段に保持させ、
前記ステージ0において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記累算途中結果をさらに累算させる
請求項3に記載の情報処理装置。
【請求項6】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ0とし、
前記ステージ1において前記重み付き分岐結果値算出手段により算出された重み付き分岐結果を前記保持手段に保持させ、
前記ステージ0において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記重み付き分岐結果を累算させる
請求項3に記載の情報処理装置。
【請求項7】
前記重みテーブルのインデックスに含まれる複数の多重化アドレスに対応する過去の複数の分岐命令は、前記各重みテーブル間で重複が少なくなるように決定されたものである
請求項1から6のいずれか1項に記載の情報処理装置。
【請求項8】
複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令における前記多重化アドレスからインデックスが生成されたものであり、
複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令における前記多重化アドレスからインデックスが生成されたものである
請求項7に記載の情報処理装置。
【請求項9】
前記予測値算出手段により算出された前記予測値と実際の分岐結果の一致不一致に基づいて、前記重みテーブルの重みの値を更新する学習処理を行う学習手段をさらに備える
請求項1から8のいずれか1項に記載の情報処理装置。
【請求項10】
前記学習手段は、さらに、前記多重化アドレスに反映されたローカル履歴を、前記実際の分岐結果に置換する
請求項9に記載の情報処理装置。
【請求項11】
予測対象分岐命令のターゲットアドレスの多重化アドレスに対応づけられ閾値を保持した第2の重みテーブルと、
前記ターゲットアドレスの多重化アドレスで前記第2の重みテーブルを索引することによって閾値を算出する閾値算出手段を備え、
前記予測値算出手段は、前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値に、前記閾値算出手段により算出された前記閾値を加算することにより、前記予測値を算出する
請求項1から10のいずれか1項に記載の情報処理装置。
【請求項12】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備える情報処理装置の情報処理方法において、
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成し、
前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択し、
前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出し、
最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算し、
少なくとも累算された前記重み付き分岐結果値を用いて、予測値を算出する
情報処理方法。
【請求項13】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備えるコンピュータ
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、
前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、
前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、
前記重み付き分岐結果値算出手段により最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、
少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段と
して機能させるプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、情報処理装置および方法、並びにプログラムに関し、特に、実装コストの低減、および、分岐予測の予測精度向上を実現させることができるようにした情報処理装置および方法、並びにプログラムに関する。
【背景技術】
【0002】
近年、プロセッサのパイプラインはさらなる深化の傾向を見せており、パイプラインが深くなるにつれ制御ハザードに起因する性能低下はより深刻なものとなってきている。制御ハザードはプログラム内に存在するif文やWhile文に代表される分岐命令によって引き起こされる。これを回避する1つの手段として用いられるのが分岐命令の分岐方向(分岐成立(Taken)、若しくは、分岐不成立(Not Taken))を予測する分岐予測である。1990年代に入りgshare分岐予測器が考えられたが、わずかな予測精度向上でプロセッサのパフォーマンスは大幅に向上するため、分岐予測器には、さらなる予測精度の向上が要求された。
【0003】
分岐予測器はCPUの性能向上に大きな役割を果たしており、近年において活発に研究が行われている。中でも学習理論の一種であるパーセプトロンを応用したパーセプトロン分岐予測器は、単体で高い予測精度を示すことで注目されている。
【0004】
パーセプトロン分岐予測器は、予測すべき分岐命令であるbranch Bのアドレスの他に過去に実行した分岐命令のアドレスを時系列に並べた実行パス履歴、過去の分岐結果の履歴を時系列順に並べたグローバル履歴、および、この分岐履歴を対の情報である分岐命令のアドレスを用いて並び替えたローカル履歴などを用いて予測を行う(例えば、特許文献1参照)。
【0005】
パーセプトロン分岐予測器は、branch Bのアドレスや実行パス履歴をインデックスとして重みテーブルと呼ばれる多数のテーブルからそれぞれ重みと呼ばれる整数値を読み出す。これらの重みはそれぞれグローバル履歴の特定の場所と1対1に対応している。グローバル履歴の各要素は、1ならば分岐成立、-1ならば分岐不成立を表わす。パーセプトロン分岐予測器は、読み出された重みをWiとし、対応するグローバル履歴の要素をXiとし、さらに、1≦i≦nとし、次式を計算する。
【0006】
【数1】
JP0005283054B2_000002t.gif

【0007】

式(1)において、W0はバイアスであり、重みと同様に読み出される。パーセプトロン分岐予測器は、求められたyの値が正ならば分岐成立として値「1」を出力し、yの値が負ならば分岐不成立として値「-1」を出力する。重みWiの更新規則は、分岐結果をt∈{1,-1}とすると次式によって表される。通常の場合、α=1とする。
【0008】
【数2】
JP0005283054B2_000003t.gif

【0009】
以上の様なパーセプトロン分岐予測器として、これまでに、基本的な構造によるGlobal/Local Perceptron Branch Predictor、予測処理のパイプライン化を可能としたPath-based Neural Predictor、重み読み出しのインデックスを工夫したPiecewise Linear Branch Predictor、重み読み出しの並列化を行ったPTBP、およびAdvanced Anti-Aliasing Perceptron Branch Predictor (A3PBP)などのパーセプトロン分岐予測器等が知られている。
【0010】
例えば、A3PBPは、実行パス履歴の情報をより効率的に利用する構造を持ち、ローカル履歴を重み読み出しのインデックスに利用することにより、重みの負の衝突を削減し予測精度を向上させた(例えば非特許文献1および非特許文献2参照)。
【0011】
A3PBPでは、ステージnにおけるm番目の重みテーブルTablei=(n-1)M+m(1≦n≦h,1≦m≦M)のインデックスindex[i]を、A[s]を用いて生成する。A[s]は、branch Bよりs個前の分岐命令のアドレス、すなわち、実行パス履歴を表す。A[0]は、そのステージで得られうる最新のアドレスを示す。A3PBPは、この実行パス履歴を構成するアドレスの一部分をローカル履歴ビットに置換した多重化アドレスを用いて、以下の式(3)のように、最新のアドレスA[0]と多重化アドレスの排他的論理和によりindex[i]を生成し、そのインデックスを用いて重みを選択する。
【0012】
【数3】
JP0005283054B2_000004t.gif

【0013】

【特許文献1】特開平10-171653号公報
【非特許文献1】二ノ宮康之、阿部公輝「実行パスとローカル履歴を重み選択に利用したパーセプトロン分岐予測器」情報処理学会研究報告(IPSJ SIG Technical Report),2006-ARC-169(6),2006年8月1日,p.31-36
【非特許文献2】Y. Ninomiya and K. Abe, "A3PBP: A Path Traced Perceptron Branch Predictor Using Local History for Weight Selection," The Journal of Instruction-Level Parallelism, Vol.9, pp.1-18, May 2007.
【発明の開示】
【発明が解決しようとする課題】
【0014】
しかしながら、パーセプトロン分岐予測器は複雑な構造を持つためその回路量が大きい。さらに、パーセプトロン分岐予測器において、重みテーブルの数(予測計算に使う重みの数と等しい)が増加すると累算に要するハードウェアコストや計算レイテンシが増大する。
【0015】
仮に、ハードウェアコストを増大させないようにするために、テーブルを記憶する記憶容量を一定とすると、テーブル数が多い程、1つあたりのテーブルのエントリ数は相対的に小さくなる。しかしながら、エントリ数の不足は使用する重みの衝突を引き起こし、予測精度低下の主因となる恐れがある。
【0016】
以上の点を、換言すれば、テーブル数を削減することにより、実装コストや計算レイテンシを低減させ、さらに、重みの負の衝突の発生を抑制させることができる。
【0017】
しかしながら、テーブル数を削減するには、使用するグローバル履歴長も短くする必要があるが、単純に予測に反映させる履歴情報の長さを短くすると、その分、予測精度が低減する恐れがある。
【0018】
マルチコア化の進むCPU(Central Processing Unit)に実装するためには精度の向上とともに実装コストの削減が求められる。
【0019】
本発明は、このような従来の実情に鑑みて提案されたものであり、実装コストの低減、および、分岐予測の予測精度向上を実現させることができるようにするものである。
【課題を解決するための手段】
【0020】
本発明の第1の側面は、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルと、前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、前記重み付き分岐結果値算出手段により最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段とを備える情報処理装置である。
【0021】
少なくとも、前記重み選択手段による前記重みの選択、および、前記重み付き分岐結果値算出手段による重み付き分岐結果の算出をステージ1とし、少なくとも、前記予測値算出手段による予測値の算出をステージ0とし、ステージ毎に順次処理を行うことができる。
【0022】
前記ステージ1における処理の処理結果を保持する保持手段をさらに備え、前記分岐命令の分岐方向の予測の度に、前記ステージ0の処理、および、前記ステージ1の処理を行い、前記ステージ1の処理の処理結果を前記保持手段に保持させるとともに、前記ステージ0の処理を、前記保持手段に保持されている前回の予測において行われた前記ステージ1の処理の処理結果を用いて行うことができる。
【0023】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ1とし、前記ステージ1において前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値の累算結果を前記保持手段に保持させ、前記ステージ0において、前記予測値算出手段により、前記保持手段に保持されている前記累算結果を用いて前記予測値を算出させることができる。
【0024】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算の一部を前記ステージ1とし、残りの一部を前記ステージ0とし、前記ステージ1において、前記重み付き分岐結果値累算手段により、前記重み付き分岐結果値の累算を途中まで行わせ、得られた累算途中結果を前記保持手段に保持させ、前記ステージ0において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記累算途中結果をさらに累算させることができる。
【0025】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ0とし、前記ステージ1において前記重み付き分岐結果値算出手段により算出された重み付き分岐結果を前記保持手段に保持させ、前記ステージ0において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記重み付き分岐結果を累算させることができる。
【0026】
前記重みテーブルのインデックスに含まれる複数の多重化アドレスに対応する過去の複数の分岐命令は、前記各重みテーブル間で重複が少なくなるように決定されたものであるようにすることができる。
【0027】
複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令における前記多重化アドレスからインデックスが生成されたものであり、複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令における前記多重化アドレスからインデックスが生成されたものであるようにすることができる。
【0028】
前記予測値算出手段により算出された前記予測値と実際の分岐結果の一致不一致に基づいて、前記重みテーブルの重みの値を更新する学習処理を行う学習手段をさらに備えることができる。
【0029】
前記学習手段は、さらに、前記多重化アドレスに反映されたローカル履歴を、前記実際の分岐結果に置換することができる。
【0030】
予測対象分岐命令のターゲットアドレスの多重化アドレスに対応づけられ閾値を保持した第2の重みテーブルと、前記ターゲットアドレスの多重化アドレスで前記第2の重みテーブルを索引することによって閾値を算出する閾値算出手段を備え、前記予測値算出手段は、前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値に、前記閾値算出手段により算出された前記閾値を加算することにより、前記予測値を算出することができる。
【0031】
本発明の第1の側面は、また、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備える情報処理装置の情報処理方法において、前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成し、前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択し、前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出し、最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算し、少なくとも累算された前記重み付き分岐結果値を用いて、予測値を算出する情報処理方法である。
【0032】
本発明の第1の側面は、さらに、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備えるコンピュータ前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、前記最近のn回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、前記グローバル履歴に含まれる前記最近のn回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、前記重み付き分岐結果値算出手段により最近のn回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段として機能させるプログラムである。
【0033】
本発明の第1の側面においては、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、グローバル履歴の履歴数よりも少ない最近のn回の分岐命令に対応したn個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルが備えられ、分岐命令のアドレスに対して、分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスが生成され、最近のn回の分岐命令毎にインデックスにより各重みテーブルから重みが選択され、グローバル履歴に含まれる最近のn回の分岐命令毎に、選択された各重みと分岐命令の分岐成立若しくは不成立に対応した値との積が重み付き分岐結果値として算出され、最近のn回の分岐命令に対して算出された重み付き分岐結果値が累算され、少なくとも累算された重み付き分岐結果値を用いて、予測値が算出される。
【発明の効果】
【0034】
本発明によれば、分岐命令の予測を行うことができる。特に、実装コストを低減させ、さらに、分岐予測の予測精度を向上させることができる。
【発明を実施するための最良の形態】
【0049】
以下、本発明の実施の形態について説明する。
【0050】
図1は、本発明を適用した情報処理装置の構成例を示すブロック図である。
【0051】
図1の情報処理装置に搭載されるCPU(Central Processing Unit)11は、命令実行を並列化し、前の命令の実行終了を待たずに次の命令を実行するパイプライン処理を行うプロセッサである。CPU11は、メモリ12に記憶されている命令を読み出して実行し、必要に応じて処理結果をメモリ12に返す。
【0052】
CPU11は、分岐予測部21、フェッチ部22、デコード部23、演算部24、ライトバック部25、命令キャッシュ31、およびデータキャッシュ32を有している。
【0053】
1つの命令に対する実行処理は複数のステージ(工程)により構成される。つまり、命令キャッシュ31に保持された命令を読み出すフェッチ(IF)、フェッチされた命令をデコードし、制御信号を生成したり、レジスタ・ファイルをレジスタ指定子で参照したり、必要に応じてデータキャッシュ32よりデータを読み出したりするデコード(ID)、数値の計算やロード・ストアのデータやアドレス・分岐先の計算を行う命令実行(EX)、並びに、演算結果を、データキャッシュを介してメモリ12に戻すライトバック(WB)などのステージがある。
【0054】
命令キャッシュ31は、メモリ12より順次命令を読み出し保持する。フェッチ部22は、IFステージにおいて、命令キャッシュ31より命令をフェッチし、それをデコード部23に供給する。デコード部23は、IDステージにおいて、フェッチ部22より供給された命令をデコードし、必要に応じてデータキャッシュ32よりデータを取得し、それらを演算部24に供給する。
【0055】
演算部24は、EXステージにおいて、デコード部23より供給される情報に基づいて演算を行う。その演算結果はライトバック部25に供給される。また、演算部24は、演算結果によって次の命令(ジャンプ先のアドレス)が異なる分岐命令のライトバック部25は、WBステージにおいて、演算部24より供給された演算結果をデータキャッシュ32に保持させる。データキャッシュ32は、必要に応じて、その演算結果をデコード部23に供給したり、メモリ12に書き込ませたりする。
【0056】
分岐予測部21は、IFステージにおいて、演算部24により実行される分岐命令について、そのの実行結果、すなわち分岐先(アドレス)を、演算部24より供給される過去の演算結果等に基づいて予測する(分岐命令に対して分岐予測を行う)。つまり、分岐予測部21は、この予測処理を、過去に実行された分岐命令の予測結果(分岐予測の正否)に応じて付与された重みによって重み付けされた、グローバル履歴の分岐結果を用いて行う。詳細については後述する。
【0057】
フェッチ部22は、その分岐予測部21の予測に従って次の命令をフェッチする。
【0058】
このとき、フェッチ部22、デコード部23、演算部24、およびライトバック部25は、パイプライン処理を行い、複数の命令を並列に実行する。すなわち、フェッチ部22は、演算部24の演算結果を待たずに、分岐予測部21の予測結果に従って、命令キャッシュ31より命令を次々とフェッチする。従って、分岐予測部21の予測精度を向上させることにより、CPU11において行われるパイプライン処理において制御ハザードの発生が減少するので、CPU11の処理性能を向上させることができる。
【0059】
次に、その分岐予測部21の構成について説明する。図2は、図1の分岐予測部21の詳細な構成例を示すブロック図である。
【0060】
図2において、分岐予測部21は、上述したパイプラインを用いて分岐予測を行う予測処理部41、分岐命令のアドレスに分岐命令ごとの分岐結果の履歴であるローカル履歴を反映させた多重化アドレスを生成する多重化アドレス生成部74、分岐予測に使用される重みテーブルの各重みについて、分岐命令の演算結果に基づいて学習を行う学習処理部42、分岐予測に使用される各パラメータの更新を行う更新処理部43、および分岐予測に使用される各パラメータやデータを保持するレジスタ44を有している。
【0061】
レジスタ44は、予測処理部41の分岐予測に使用されるパラメータやデータ等を必要に応じて保持する。レジスタ44には、例えば、重み付き分岐結果累算値81、重みテーブル82、多重化アドレス83、グローバル履歴84、実行パス履歴85、ローカル履歴86、通常間隔インデックス87、および長間隔インデックス88が保持される。
【0062】
グローバル履歴84は、プログラム全体における分岐結果を時系列に並べた分岐結果の履歴(分岐履歴)である。GHR[p]は、グローバル履歴84における最新の分岐結果から(p+1)番目の分岐結果を示す(0≦p≦n-1)。各分岐結果は、分岐成立(Taken)を示す値「1」、若しくは、分岐不成立(Not Taken)を示す値「-1」により構成される。つまり、各分岐結果は分岐方向を示す。ただし、「-1」は実際には「0」で表現されている。
【0063】
実行パス履歴85は、グローバル履歴84の各分岐結果に対応する分岐命令のアドレスの履歴、すなわち、実行された各分岐命令のアドレスである。A[p]は、実行パス履歴85における最新のアドレスから(p+1)番目のアドレスを示す。つまり、グローバル履歴84の分岐結果GHR[p]は、実行パス履歴85のアドレスA[p]で示される分岐命令の分岐結果を示す。また、A[0]は、その時点での最新の分岐命令アドレスを示す。なお、最新の分岐結果GHR[0]によりジャンプする先のアドレス、つまり、これかから実行される分岐命令のアドレスをターゲットアドレス(TA)とも称する。つまり、換言すると、古い(最新でない)ターゲットアドレス(TA)が実行パス履歴85に時系列順に蓄積される。
【0064】
ローカル履歴(LHT(Local History Table))86は、グローバル履歴84の各分岐結果を、分岐命令ごとにまとめたものである。例えば、LHT[q]は、ある分岐命令の、最新の分岐結果からq(0≦q<p)番目の分岐結果を示す。つまり、ローカル履歴86においても、グローバル履歴84と同様に、各分岐結果は分岐方向を示し、その値は、分岐成立(Taken)を示す値「1」、若しくは、分岐不成立(Not Taken)を示す値「-1」により構成される。
【0065】
図3を参照して、グローバル履歴84乃至ローカル履歴86についてさらに詳細に説明する。
【0066】
図3の左に示されるプログラム(sample.c)91は、グローバル履歴84乃至ローカル履歴86の説明のための、分岐命令を含むプログラムの例である。プログラム91においては、分岐命令として、200行目にfor文が記述され、208行目、216行目、および224行目にif文が記述されている。
【0067】
図3の右側には、このプログラム91について、グローバル履歴84、実行パス履歴85、およびローカル履歴86の例が示されている。各履歴は、図3において、左から右に向かって時系列順に並んでいる。つまり、最も左側の履歴が一番古く、最も右側の履歴が一番新しい。実行パス履歴85の、最も古い(一番左の)アドレスは「200」であり、200行目のfor文が実行されたことが示されている。
【0068】
このアドレスに対応するグローバル履歴84の分岐結果(GH)は「0」であり、200行目のfor文の条件(i<2)が真であったことが示されている。従って、このときのターゲットアドレス、すなわち次(実行パス履歴85の左から2番目)のアドレスは、for文のループ内の次の分岐命令が記述された「208」となる。このアドレスに対応するグローバル履歴84の分岐結果(GH)は「0」であり(すなわち、if文の条件(a==b)が偽であり)、変数xのインクリメント(x++)は行われずに、次の分岐処理の216行目に処理が移行する。従って、このときのターゲットアドレス、すなわち次(実行パス履歴85の左から3番目)のアドレスは、次の分岐命令が記述された「216」である。このアドレスに対応するグローバル履歴84の分岐結果(GH)は「1」であり(すなわち、if文の条件(a==b)が真であり)、変数yがインクリメント(y++)される。その後、処理は200行目に戻る(実行パス履歴85においては左から4番目に進む)。以降も同様にして各命令が実行され、200行目のfor文の条件(i<2)が偽となるまでfor文のループ内の命令(208行目および216行目の分岐命令)が繰り返し実行される。そして、実行パス履歴85の最新の(一番右の)アドレスで指定された200行目のfor文の予測において、分岐結果が「1」(グローバル履歴84の一番右の分岐結果(GH))であること、すなわち、200行目のfor文のループが終了されたと予測されたことが示されている。この場合、224行目のif文にジャンプすることになるので、このときのターゲットアドレス(TA)の値は、図3に示されるように「224」となる。
【0071】
なお、ローカル履歴86の各分岐結果(LH)は、グローバル履歴に示される分岐結果が、分岐命令毎に(行番号毎に)整理されている。
【0072】
図2に戻り、多重化アドレス(MA(Multiprex Address)(p))83は、実行パス履歴85のアドレス(A[p])の下位ビットをそのビット長分のローカル履歴86(分岐結果LHT[q])に差し替えたものである。MA[p]は、実行パス履歴85における最新のアドレスから(p+1)番目のアドレスA[p]の下位ビットをローカル履歴86の分岐結果LHT[q]に差し替えたものを示す。なお、本実施形態においては、多重化アドレス83のアドレス(MA[p])は、実行パス履歴85のアドレス(A[p])の下位ビットをそのビット長さ分のローカル履歴86(LHT[q])に差し替えて生成されるようにしたが、アドレス(A[p])の下位ビットを削除することなく、アドレス(A[p])にローカル履歴86の分岐結果(LHT[q])を付加させることにより、アドレス(A[p])にローカル履歴86の分岐結果(LHT[q])を反映させるようにしてもよい。
【0073】
本実施形態において多重化アドレス生成部74は、例えば図4に示されるように、実行パス履歴85のアドレス92の下位2ビットを削除してアドレス(ショート)93を生成し、そのアドレス(ショート)93にローカル履歴86(LHT)から読み出された2ビットの分岐結果(LH)94を付加したものを多重化アドレス(MA)83とする。レジスタ44は、この多重化アドレス83を記憶しておき、ステージ1における重みテーブル82からの重みの読み出しや、ステージ0における閾値の読み出しに利用するインデックスの生成に利用している。
【0074】
このように、本実施形態においては、ローカル履歴86の分岐結果は直接的に予測演算に使用されることはないが、インデックス生成に利用することで1つのアドレスからローカル履歴長のべき乗通りのインデックスが生成可能になる。一般的に1つの分岐命令が、その時々に応じて分岐方向を変える(分岐方向の両方に分岐する)ことは多いが、実行パス履歴85のアドレスのみをインデックスとして重みを選択する従来の手法の場合、その分岐命令がいずれの方向に分岐する場合であっても同じ重みが選択されることになっていた(重みの負の衝突が発生した)。
【0075】
これに対し、図5に示されるように、ローカル履歴86の分岐結果を実行パス履歴85のアドレスの下位ビットと差し替えた多重化アドレス(MA)83を用いて生成したインデックスを使用することにより、重みテーブル82より選択する重みを、その分岐方向によって変更することができ、重みの負の衝突を回避することができる。これにより、ハードウェアコストの増加を最小限に抑えつつ予測精度の向上を期待することができる。
【0076】
図2に戻り、重みテーブル82は、各分岐命令について、過去に当該分岐命令まで辿ったグローバル履歴84の各分岐結果に対して、事前になされた分岐予測の正否を反映した重み(重み群)が、当該分岐命令のアドレスの下位ビットをローカル履歴に差し替えた多重化アドレス83を用いて生成されたインデックスと対応付けられて、保持されたものである。WT[j](1≦j≦n,jは整数)は、グローバル履歴84のj番目の分岐結果GHR[j-1]に割り当てられた重み群を、複数の多重化アドレス83を用いて生成されるインデックスに対応付けるテーブル情報である。つまり、GHR[j-1]には、WT[j]より選択された重みが付加される。
【0077】
重み付き分岐結果累算値81は、グローバル履歴の各分岐結果に重み付けを行った重み付き分岐結果値を、各ステージにおいて鎖毎に順次累算した値である。REG[r]は、r(1≦r≦n,rは整数)個の重み付き分岐結果値の累算値であり、レジスタ44に保持される時点での値である。詳細については後述するが、重み付き分岐結果の累算は、ステージ1において行うようにしてもよいし、ステージ0において行うようにしてもよいし、ステージ1およびステージ0の両方で行うようにしてもよい。ここでは、ステージ1においてr個の重み付き分岐結果値を累算する(残りの累算はステージ0において行う)ものとする。
【0078】
通常間隔インデックス87は、複数の多重化アドレス83を用いて生成された、重みテーブル82に対して使用される、重み選択用のインデックスである。通常間隔インデックス87は、互いの分岐命令の距離が比較的短い複数の多重化アドレス83と最新のアドレスA[0]の排他的論理和により生成される。
【0079】
長間隔インデックス88も同様に、複数の多重化アドレス83を用いて生成された、重みテーブル82に対して使用される、重み選択用のインデックスである。ただし、長間隔インデックス88は、互いの分岐命令の距離が比較的長い複数の多重化アドレス83と最新のアドレスA[0]の排他的論理和により生成される。
【0080】
ここでこれらのインデックスについて図6乃至図9を参照して説明する。
【0081】
グローバル履歴84の分岐結果は、予測すべき分岐命令であるbranch Bに近いほどbranch Bとの関連が高いことは明らかであるので、グローバル履歴84の、branch Bと近いものから順に所定の数の分岐結果に対して重み付けが行われる。パーセプトロン分岐予測器において、重み付けを行うグローバル履歴84の長さ(履歴長)は、基本的に長いほど予測精度が向上する。つまり、使用する重みテーブル82の数が多いほど、予測計算に使用される重みの数が増えるので予測精度は向上する。
【0082】
しかしながら、使用する重みテーブルの数が増加すると、ハードウェアコストや計算レイテンシが上昇する。また、仮に、全体の記憶容量を一定とすれば、重みテーブル82の数が増大することにより、各テーブルのエントリ数は相対的に少なくなる。エントリ数の不足は使用する重みの衝突を引き起こし予測精度低下の主因となりうるので、テーブル数を削減することは、実装コストと計算レイテンシの低減を実現するだけでなく、重みの負の衝突の回避にも寄与する。
【0083】
しかしながら、テーブル数を削減するためには、使用するグローバル履歴84の履歴長も短くする必要があるが、単純に履歴長を短くすると、その分、予測精度が低下してしまう。予測精度の向上を実現するためには、従来法と同程度の履歴情報を予測に反映させる必要がある。つまり、従来とは別の形で履歴情報を予測に反映させる必要がある。
【0084】
そこで、本実施の形態においては、予測結果の履歴情報を、重み付けを行うグローバル履歴84としてではなく、重み選択に使用するインデックスに反映させるようにする。つまり、例えば、従来のA3PBPにおいては、実行パス履歴85を、重み読み出しのインデックス生成に使用していたが、本実施の形態においては、テーブル数を削減して1テーブルあたりのエントリ数を増やすために、インデックス生成に複数の多重化アドレスを用いることにより、A3PBPで使用した実行パス履歴情報よりも詳細な情報を重み読み出しのインデックスに反映させるようにする。
【0085】
図6は、i番目のテーブルであるTableiが使用するインデックス生成関数index[i]の例を、そのインデックス生成に使用されるアドレスの種類数毎に示す表である。図6に示される表において、index[i]は、テーブルによって使用する多重化アドレス83(MA)の組み合わせを変えるために、実行パス履歴上のp個(p=1,・・・,5)の多重化アドレス(MA[c1i-n],・・・,MA[cpi-n])を用いて生成されるようになされている。
【0086】
実行パス履歴情報を予測に反映させるためにp個の多重化アドレス83(MA)は、テーブル間で極力重複しないように選択する必要がある。そのため、係数c1=1,1<c2<・・・<cpは素数とされている。なお、p=1の場合、A3PBPのインデックス生成関数と同等となる。
【0087】
また、これらの素数を調整し、branch Bから遠くなるにつれて使用する多重化アドレス83(MA)の間隔が徐々に開くようにすることで、branch Bと強い相関を持つ近距離の分岐履歴に重点を置きつつ、予測が遠距離の特定の区間の履歴に強く依存することを極力避けるようにすることができる。
【0088】
このように、実行パス履歴85のより詳細な情報を重み読み出しのインデックスに反映させることにより、1テーブルあたりのエントリ数を増やすことができるため、予測精度を向上させることができるが、過剰に詳細なパス情報の利用は重みの負の衝突を誘発し、予測精度が低下する恐れがある。すなわち、インデックス生成に使用するアドレスの種類数には最適値が存在することが予想される。
【0089】
そこで、この最適値を実験により求めた。実験はSPEC INT2000の12種類のベンチマークをSimCoreシミュレータで1億命令程度実行した際にトレースしたデータを用いた。このデータを8本鎖2段パイプラインのA3PBPをシミュレートしたプログラムで処理し、重み読み出しのインデックス生成に使用する多重化アドレスの数と予測精度の関係を測定した。ステージ0のテーブルを除いたテーブルの個数は8個である.記憶容量は総計32Kバイトとした。
【0090】
その実験結果のグラフを図7に示す。図7に示されるグラフは、インデックス生成に使用した多重化アドレス83の種類数と、そのインデックスを用いて選択した重みによりグローバル履歴84に対して重み付けを行い、分岐予測を行ったときの予測ミス率との関係を示しており、横軸は使用した多重化アドレス83の種類を示し、縦軸はそのときの予測ミス率(%)を示している。曲線151は、重み選択に用いられる重みテーブル82のエントリ数が2Kであるときの関係を示しており、曲線152は、その重みテーブル82のエントリ数が4Kであるときの関係を示しており、曲線153は、その重みテーブル82のエントリ数が8Kであるときの関係を示しており、曲線154は、その重みテーブル82のエントリ数が16Kであるときの関係を示している。
【0091】
このグラフにおいて、曲線151乃至曲線154の各曲線の形状から、エントリ数に関わらず、使用する多重化アドレス83の種類が少ないと予測ミス率が下がらない、つまり効率的に重みテーブル82を使用することができないことが分かる。逆に過剰に多重化アドレス83の種類を増やすと予測ミス率が上昇してしまうことも分かる。さらに、曲線151乃至曲線154の互いの関係から、インデックス生成に使用する最適な多重化アドレス83の種類数は重みテーブル82のエントリ数と関係がある、つまりエントリ数が多いほど予測ミス率を低減させることができることが分かる。また、エントリ数が増えるに従って、より詳細なパス情報を使用することによって予測精度が向上することもわかる。例えば、エントリ数が2K乃至8Kの場合、最も予測ミス率が低くなる、最適な多重化アドレス83の種類が4であるのに対し、エントリ数が16Kの場合には、最適な多重化アドレス83の種類は5となっている。
【0092】
以上のように、効率的なインデックス生成に必要な多重化アドレス83の種類数はエントリ数に応じて4種類から5種類程度であるということが分かる。しかしながら、図6に示される方法でインデックスを生成する場合、従来法よりも短い履歴しか使用することができない。
【0093】
例えば4種類の多重化アドレス83を用いてインデックス生成を行う場合、使用される多重化アドレス83のうち、予測すべき分岐命令branch Bから最も遠い分岐命令の多重化アドレスは、MA[5i-1]である。i=8とすると、このアドレスはMA[39](branch Bよりも40個前に処理された分岐命令の多重化アドレス)となり、従来法で使用する履歴長の半分程度となる。
【0094】
O-GEHL branch predictorで知られているように、予測精度の向上のためには長いグローバル履歴を用いることが必要であるが、従来法ではグローバル履歴中の1つの分岐結果は1つの重みテーブルに対応するので、テーブル数を削減すると利用できるグローバル履歴84の履歴数も削減することになる。つまり、図6に示される方法でインデックスを作成することにより、予測精度が低下してしまう恐れがある。そこで、少ないテーブル数の下で長い実行パス履歴85と長いグローバル履歴84を利用することができるようにすることが求められる。
【0095】
より長い実行パス履歴85を利用するために、図6に示される重みテーブルのインデックス生成法に加え、より過去の多重化アドレス83を用いるインデックス生成法も併用するようにする。一般に、予測すべき分岐命令branch Bに近い履歴ほど分岐結果と強い相関を持っている。そこで、予測精度を向上させるために、予測すべき分岐命令branch Bに近い、近距離の履歴に重点を置くとともに、履歴長が短くならないように、予測すべき分岐命令branch Bから遠い、遠距離の履歴も満遍なく利用する。例えば、iの係数c1,・・・,cpは、予測器全体で使用する多重化アドレス83の間隔が、branch Bから遠くなるにしたがい徐々に開くように値を選択する。
【0096】
例えば、4種類のアドレスを使用する場合(p=3)、図6に示される以下の式(4)を用いて生成されるインデックスを用いて重み選択を行う重みテーブル1乃至重みテーブル4と、以下の式(5)を用いて生成されるインデックスを用いて重み選択を行う重みテーブル5乃至重みテーブル7を用意する。
【0097】
【数4】
JP0005283054B2_000005t.gif
【数5】
JP0005283054B2_000006t.gif

【0098】
式(4)と式(5)を比較して分かるように、使用される多重化アドレス83の、互いの距離(命令間距離)は、式(5)の方法の場合よりも式(4)の方法の場合の方が長い。図2に示される通常間隔インデックス87は、式(4)の方法により生成されるインデックス(NDI:NomalDistance Index)であり、図2に示される長間隔インデックス88は、式(5)の方法により生成されるインデックス(LDI:Long Distance Index)である。
【0099】
このときの、インデックス生成に使用される多重化アドレス83の分布の例を図8に示す。図8に示される表は、各重みテーブル(重みテーブル1乃至重みテーブル7)のインデックス生成に使用される多重化アドレス83の分布を示すものであり、一番上の行の数字は、予測すべき分岐命令branch Bからの命令間距離を示しており、2行目以降のアスタリスク(*)は、その行のテーブルに対するインデックスの生成に、その列の分岐命令の多重化アドレスを用いることを示している。例えば、上から2行目の重みテーブル1のインデックス生成には、予測すべき分岐命令branch Bからの命令間距離が「1」、「3」、および「5」の3つの多重化アドレス83が使用される。
【0100】
なお、表の一番下の行(ALL)は、各テーブル(重みテーブル1乃至重みテーブル7)のインデックス生成に用いられる全ての多重化アドレスの分布を示している。また、図8において下の表は、上の表に続く表である。上の表では、命令間距離が「1」乃至「25」の範囲における多重化アドレス83の分布を示しており、下の表では、命令間距離が「26」乃至「50」の範囲における多重化アドレス83の分布を示している。
【0101】
図8の表に示されるように、iの値が小さい重みテーブル82、つまり、グローバル履歴84の分岐結果のうち、予測すべき分岐命令branch Bに近い方から順に所定の数の分岐結果のそれぞれに割り当てられた重みテーブル82については、NDIをインデックスとして用いるようにし、branch Bから遠い、残りの分岐結果にそれぞれ割り当てられた重みテーブル82については、LDIをインデックスとして用いるようにしている。図8の例の場合、重みテーブル1乃至重みテーブル4では、式(4)を用いて生成されたインデックスNDIにより重み選択が行われ、重みテーブル5乃至重みテーブル7では、式(5)を用いて生成されたインデックスLDIにより重み選択が行われる。
【0102】
従って、重みテーブル1乃至重みテーブル4のインデックス生成には、branch Bからの命令間距離が「20」よりも近い多重化アドレスのみが使用されているが、重みテーブル5乃至重みテーブル7のインデックス生成には、それ以上の命令間距離の多重化アドレスも使用されている。例えば、重みテーブル7のインデックス生成には、branch Bからの命令間距離が「49」の多重化アドレスも使用されている。
【0103】
このように、グローバル履歴84の各分岐結果に割り当てられる重みテーブルによって、そのインデックス生成に用いられる多重化アドレスの、予測すべき分岐命令branch Bからの命令間距離を変えるようにしている。より具体的には、グローバル履歴84の、branch Bからの命令間距離が近い分岐結果に割り当てられる重みテーブルほど、branch Bからの命令間距離がより短い多重化アドレスを用いてインデックスが生成されるようにしている。
【0104】
また、グローバル履歴84の、branch Bからの命令間距離が所定の距離より遠い分岐結果に割り当てられる重みテーブルは、互いの命令間距離が比較的長い多重化アドレスの組みを用いて生成されるLDIをインデックスとし、branch Bからの命令間距離が比較的遠い多重化アドレスもインデックス生成に使用するようにしている。
【0105】
さらに、重みテーブル全体においては、branch Bに近い多重化アドレス程多くインデックス生成に使用するようになされている。
【0106】
このようにインデックス生成に使用する多重化アドレスを選択することにより、予測精度を低減させずに、より長い実行パス履歴を使用することができるようにし、実行パス履歴を長くすることによる予測精度向上を実現することができる。
【0107】
また、多重化アドレス83へ分岐結果を付加することにより多重化アドレスの列(すなわち実行パス履歴)にグローバル履歴情報を付加するようにする。具体的には、予測すべき分岐命令であるbranch Bから生成された多重化アドレス83に含まれるローカル履歴86の部分のうち、最も過去の履歴ビットをbranch Bの分岐方向が確定した際にその分岐結果で置換することにより多重化アドレス83を更新するようにする。これは分岐方向が確定し更新が完了したローカル履歴86で多重化アドレス83を生成するのと等価である。
【0108】
図9は、ローカル履歴が1ビットの場合、(A3PBPのように)更新を行わない場合と、更新を行う場合の多重化アドレスを比較する図である。図9Aに示される表の上の行は、実行パス履歴を示しており、「A」、「B」、「C」、および「D」は、分岐命令のアドレスを模式的に示したものである。同じ文字は同じアドレス(つまり同一の分岐命令)を示している。また、図9Aに示される表において、下の行は、各分岐命令における分岐結果、すなわちグローバル履歴を示しており、「X1」、「X2」、「X3」、「X4」、「X5」、「X6」、「X7」、および「X8」は、それぞれの分岐方向を示している。つまり、これらの値は、「1」か「-1」のいずれか一方である。なお、図9Aに示される表において、横方向は、branch Bからの命令間距離を示しており、左に行くほどbranch Bに近く、右に行くほどbranch Bより遠くなる。
【0109】
図9Bは、図9Aに示される実行パス履歴およびグローバル履歴より生成された多重化アドレスの、分岐方向確定後に更新を行わない場合の例を示している。各行は生成された多重化アドレスの構成(使用された実行パス履歴およびグローバル履歴)を示している。また、縦方向は、branch Bからの命令間距離を示しており、上に行くほどbranch Bに近く、下に行くほどbranch Bより遠くなる。
【0110】
図9Bの場合、「A」乃至「D」の各実行パス履歴には、その時点で確定している前回の分岐結果が付加される。従って、i=4における実行パス履歴「A」に対しては、その1つ前の「A」の分岐結果、すなわち、i=8における分岐結果「X8」が付加されている。同様に、i=3における実行パス履歴「D」に対しては、i=6における分岐結果「X6」が付加され、i=2における実行パス履歴「B」に対しては、i=5における分岐結果「X5」が付加され、i=1における実行パス履歴「C」に対しては、i=7における分岐結果「X7」が付加されている。
【0111】
これに対して、図9Cは、図9Aに示される実行パス履歴およびグローバル履歴より生成された多重化アドレスの、分岐方向確定後に更新を行う場合の例を示している。図9Cの見方は、図9Bと基本的に同様である。
【0112】
図9Cに示されるように、更新の結果、「A」乃至「D」の各実行パス履歴には、最新の分岐結果が付加される。従って、i=4における実行パス履歴「A」に対しては、i=4における分岐結果「X4」が付加され、i=3における実行パス履歴「D」に対しては、i=3における分岐結果「X3」が付加され、i=2における実行パス履歴「B」に対しては、i=2における分岐結果「X2」が付加され、i=1における実行パス履歴「C」に対しては、i=1における分岐結果「X1」が付加されている。つまり、更新を行う場合、多重化アドレス83には、その多重化アドレス83に含まれる実行パス履歴85のアドレスに対応するグローバル履歴84の分岐結果が含まれる。
【0113】
なお、実際の回路において、このような更新処理は信号線を繋ぎ替えるだけで容易に実現することができ、また、予測処理とは独立した他の処理として行うことができるので、予測に必要なレイテンシに変化はない。
【0114】
以上のように、多重化アドレスにグローバル履歴情報を含めるようにし、テーブルのインデックスとして使用される多重化アドレスの命令間間隔はbranch Bから遠くなるにつれて徐々に開くように設定する。このようにすることにより多重化アドレスに含まれているグローバル履歴の分岐結果もまたbranch Bから遠くなるにつれて間隔が徐々に開いていくことになるので、使用する履歴に偏りが生じない。このようにして長いグローバル履歴を利用する。
【0115】
図2に戻り、レジスタ44には、以上のような各種のパラメータが必要に応じて保持される。
【0116】
図2の予測処理部41は、このようなレジスタ44に保持されるデータやパラメータ等を用いて、分岐命令の予測処理を行う。予測処理部41は、グローバル履歴の分岐結果に重み付けを行うステージ1の処理を行うステージ1処理部51、および、重み付けされた分岐結果と閾値から、branch Bの予測を行うステージ0の処理を行うステージ0処理部52を有している。
【0117】
ステージ1処理部51は、ステージ1において、重みテーブル82(WT[j])から重みを選択する重み選択部61、その選択された重みをグローバル履歴84の分岐結果に乗算することにより、重み付き分岐結果値を算出する重み付き分岐結果値算出部62、および、重み付けされた重み付き分岐結果値を累算する重み付き分岐結果値累算部63を有する。
【0118】
重み選択部61は、ステージ1において、グローバル履歴84の各分岐結果に割り当てられた重みテーブル82(WT[j])から、通常間隔インデックス87(NDI[j])または長間隔インデックス88(LDI[j])に対応する重みをそれぞれ選択して読み出す。重み付き分岐結果値算出部62は、ステージ1において、重み選択部61に選択された各重みを、それぞれに対応するグローバル履歴84の分岐結果に乗算することにより、分岐結果の重み付けを行い、重み付き分岐結果値を算出する。グローバル履歴84の分岐結果の値は「1」または「-1」であるので、より具体的には、重み付き分岐結果値算出部62は、グローバル履歴84の分岐結果の値に応じて、重み選択部61に選択された各重みの符号を決定する。例えば、重み選択部61に選択された重みが「W」とすると、重み付き分岐結果値算出部62は、グローバル履歴84の分岐結果が「1」である場合、「W」を重み付き分岐結果値とし、グローバル履歴84の分岐結果が「-1」である場合、「-W」を重み付き分岐結果値とする。
【0119】
重み付き分岐結果値累算部63は、重み付き分岐結果値算出部62により算出された各重み付き分岐結果値を累算する。上述したように、ステージ1においては、重み付き分岐結果値累算部63は、重み付き分岐結果値の累算をr個まで行う。残りの累算はステージ0において行う。重み付き分岐結果値累算部63は、算出した重み付き分岐結果累算値81をレジスタ44に保持させる。このレジスタ44に保持された重み付き分岐結果累算値81は、次の分岐命令に対して実行されるステージ0の処理に利用される。
【0120】
ステージ0処理部52は、ステージ0において、重み付き分岐結果値累算部63が行う重み付き分岐結果値の累算の続きを行う重み付き分岐結果値累算部71、分岐成立または不成立を識別するための閾値を算出する閾値算出部72、および、重み付き分岐結果値累算部71により算出された重み付き分岐結果累算値と、閾値算出部72により算出された閾値とに基づいて、予測すべき分岐命令branch Bの分岐結果の予測値を算出する予測値算出部73を有する。
【0121】
重み付き分岐結果値累算部71は、基本的に重み付き分岐結果値累算部63と同様の処理を行う。つまり、重み付き分岐結果値累算部63と重み付き分岐結果値累算部71の両方の処理により、重み付き分岐結果値算出部62により算出された重み付き分岐結果値が所定の数まで累算される。
【0122】
なお、この重み付き分岐結果値累算部63と重み付き分岐結果値累算部71との間の処理の分配方法は任意である。例えば、重み付き分岐結果値累算部63が、重み付き分岐結果値A乃至Cを累算してA+B+Cを算出し、重み付き分岐結果値累算部71が、その累算値A+B+Cに対して、他の重み付き分岐結果値DやEをそれぞれ累算するようにしてもよいし、重み付き分岐結果値累算部63がA+Bを算出し、重み付き分岐結果値累算部71が、その累算値A+Bに対して、他の重み付き分岐結果値CやDやEをそれぞれ累算するようにしてもよい。
【0123】
また、例えば、重み付き分岐結果値累算部63が、重み付き分岐結果値A乃至Fを累算して累算値A+B,C+D、およびE+Fを算出し、重み付き分岐結果値累算部71が、その累算値A+Bと累算値C+Dを累算して累算値A+B+C+Dを算出するようにしてもよいし、重み付き分岐結果値累算部63が累算値A+B+Cと累算値D+Eを算出し、重み付き分岐結果値累算部71が、その累算値D+Eに重み付き分岐結果値Fを累算するようにしてもよい。
【0124】
もちろん、このような重み付き分岐結果値の累算を全て重み付き分岐結果値累算部63により(ステージ1において)行うようにしてもよい。その場合、重み付き分岐結果値累算部71は省略可能である。逆に、重み付き分岐結果値の累算を全て重み付き分岐結果値累算部71により(ステージ0において)行うようにし、重み付き分岐結果値累算部63を省略するようにしてもよい。
【0125】
閾値算出部72は、上述した重み付き分岐結果値累算部71による累算と並行して、ステージ0に割り当てられた重みテーブル82から、最新のアドレスA[0](ステージ0においてはターゲットアドレス)における多重化アドレスを生成する際にローカル履歴に差し替えらる下位ビットを除く上位ビットをインデックスとして、特定される複数の閾値を候補として全て選定する。閾値の候補数は、多重化アドレスを生成する際にローカル履歴に差し替えらる下位ビットの数のべき乗であり、例えば、ローカル履歴に差し替えらるビット数が2である場合は、閾値の候補数は4となる。また、閾値算出部72は、最新のアドレスA[0]をインデックスとしてローカル履歴86のテーブルより分岐結果を読み出して、複数の閾値候補の重みの中から1つを選択することにより、閾値を算出する。なお、このように最新のアドレスA〔0〕の上位ビットで特定した閾値の候補からローカル履歴で1つを選択することによって、結果として多重化アドレスを用いて閾値を算出したことになる。
【0126】
予測値算出部73は、重み付き分岐結果値累算部71により算出された重み付き分岐結果累算値と、閾値算出部72により算出された閾値とを加算することによって予測値を算出する。
【0127】
多重化アドレス生成部74は、例えば、実行パス履歴85のアドレス(処理時はターゲットアドレス)の下位4ビットを、ローカル履歴86に含まれる最新から4つ分の分岐結果に差し替えて多重化アドレス(MA)を生成する。
【0128】
学習処理部42は、予測値算出部73において算出された予測値と、演算部24における実際の演算結果(分岐結果)に基づいて、重みテーブル82の各重みについての学習処理を行う。
【0129】
更新処理部43は、新たなターゲットアドレス、演算結果(分岐結果)が確定した後、実行パス履歴85、グローバル履歴84、ローカル履歴86を随時更新する処理を行う。なお、更新処理部43は、予測値が算出される毎にグローバル履歴84を暫定的に更新し、演算結果が算出された後に、予測値を演算結果が異なる場合は、演算結果に書き換えるようになっている。また、更新処理部43は、新たなターゲットアドレスとローカル履歴86とにより多重化アドレス83が生成された後、予測すべき分岐命令の分岐結果が確定すると、その確定した分岐結果を用いて多重化アドレスを更新する。
【0130】
図10は、予測処理部41により実行される予測処理のパイプライン構造の構成例を模式的に示す図である。上述したように、予測処理はステージ0とステージ1の2つのステージにより構成される。従って、従来のパーセプトロン分岐予測器と比べてパイプラインの段数は少ない。
【0131】
グローバル履歴84の各分岐結果に対して重み付けが行われるステージ1においては、各分岐結果に乗算する重みを選択する重みテーブル82が設けられている。図10においては、n個(nは自然数)の分岐結果(分岐結果84-0(GHR[0])乃至分岐結果84-(n-1)(GHR[n-1]))に対して重み付けを行うものとし、重みテーブル82もn個用意されている(重みテーブル82-1乃至重みテーブル82-n)。
【0132】
これらの重みテーブル82のうち、予測すべき分岐命令branch Bに近い方からI個分の分岐結果に対応する重みテーブル82-1乃至重みテーブル82-Iは、NDI[j]がインデックスとされ、残りの重みテーブル82-(I+1)乃至重みテーブル82-nは、LDI[j]がインデックスとされる。
【0133】
まず、予測すべき分岐命令branch Bから1つ目のグローバル履歴84の分岐結果84-0(GHR[0])に対応する部分について説明する。この分岐結果84-0に対しては重みテーブル82-1、インバータ101-1、およびセレクタ102-1が設けられている。NDI[1]をインデックスとして重みテーブル82-1より読み出された重みは、インバータ101-1およびセレクタ102-1の一方の入力端子に供給される。インバータ101-1は、重みテーブル82-1より読み出された重みの符号を反転させてセレクタ102-1の他方の入力端子に供給する。セレクタ102-1は、GHR[0]の値に基づいて、GHR[0]の値の符号が正であるなら、重みテーブル82-1より読み出された重みを重み付き分岐結果値としてCSA(Carry Save Adder) tree103に供給し、GHR[0]の値の符号が負であるなら、インバータ101-1より供給された重みを重み付き分岐結果値としてCSA tree103に供給する。
【0134】
他の分岐結果についても基本的に同様の構成が設けられ、同様の処理が行われる。すなわち、CSA tree103には、n個の重み付き分岐結果値が供給される。ただし、branch BからI個目までの分岐結果に対応する重みテーブル82においては、NDIをインデックスとして使用し、(I+1)個目より後の分岐結果に対応する重みテーブル82においては、LDIをインデックスとして使用する。
【0135】
CSAは桁上げ保存加算器である。CSA tree103は、その桁上げ保存加算器の木構造、すなわち累算器であり、入力されたn個の重み付き分岐結果値を所定の数(r個)に減らすまで累算し、得られた重み付き分岐結果累算値81(REG[r])をレジスタ44に保持させる。
【0136】
以上がステージ1の処理の構成である。
【0137】
分岐の予測が行われるステージ0においては、桁上げ保存加算器の木構造(すなわち累算器)であり、レジスタ44に蓄積された重み付き分岐結果累算値81をさらに累算するCSA tree111、重みテーブル82-0より選択された重み群の中から、LHT86より選択された分岐結果に基づいて閾値を選択するセレクタ112、重み付き分岐結果値の累算値の途中結果とセレクタ112により選択された閾値とを加算する桁上げ保存加算器であるCSA113、および、CSA113の出力を全て加算する桁上げ伝播加算器であるCPA(carry propagation adder)114が設けられている。
【0138】
重みテーブル82-0からは、branch B のアドレスA[0]を用いて重みの候補が読み出される。セレクタ112は、この中からローカル履歴86の分岐結果の値によって予測に使用する重みを選択する。そのローカル履歴86の分岐結果はbranch BのアドレスA[0]を用いてLHT86から読み出される。この処理と並行して、CSA tree111は、ステージ1において行われた重み付き分岐結果値の累算の続きを行う。CSA113およびCPA114により、重み付き分岐結果値の累算の途中結果と、セレクタ112に選択されたバイアスの重み(閾値)が加算され、その結果が正であれば分岐成立と予測され、負であれば分岐不成立と予測される。学習は従来のパーセプトロン分岐予測器と同様の方法で行われる。
【0139】
次に、分岐予測処理の全体の流れについて、図11のフローチャートを参照して説明する。
【0140】
予測処理部41のステージ1処理部51(図2)は、ステップS1において、分岐命令が命令キャッシュ31(図1)に入力されたか否かを判定し、入力されていないと判定した場合、ステップS2に処理を進め、分岐予測パイプラインとしての処理をストール(破棄)させ、処理をステップS1に戻す。すなわち、ステージ1処理部51は、ステップS1において、分岐命令が入力されたと判定するまで、ステップS2の処理を繰り返しながら待機する。
【0141】
ステップS1において、分岐命令が入力されたと判定した場合、ステージ1処理部51は、処理をステップS3に進める。ステップS3において、ステージ1処理部51は、図10に示されるステージ1について、重み付き分岐結果累算値81(REG[r])を求めるステージ1処理を実行する。ステップS3の処理を終了すると、ステージ1処理部51は、処理をステップS4に進める。
【0142】
ステップS4において、ステージ0処理部52は、予測すべき分岐命令が命令キャッシュ31に入力されたか否かを判定し、入力されたと判定するまで、ステップS5において分岐予測パイプラインとしての処理をストールさせながら待機する。
【0143】
ステップS4において、予測すべき分岐命令が入力されたと判定した場合、ステージ0処理部52は、処理をステップS6に進め、図10に示されるステージ0について、予測を行うステージ0処理を実行する。また、そのステップS6と並行して、ステップ7において、多重化アドレス生成部74は、入力された分岐命令のアドレスすなわちターゲットアドレスとローカル履歴とにより新たな多重化アドレスを生成する。ステップS6およびステップS7の処理が終了されると、処理はステップS8に進む。
【0144】
ステップS8において、更新処理部43は、レジスタの各値を更新する。ステップS8の処理が終了されると、処理が終了される。なお、この分岐予測処理とは独立して、別途演算部24により実際に演算された分岐結果に基づいて、グローバル履歴84、ローカル履歴86、および多重化アドレス83が更新される。また、分岐結果に基づいて学習処理部42により学習処理がなされた重みにより重みテーブル82が更新される。
【0145】
このように、本実施の形態の分岐予測処理においては、ステージ1において重み付き分岐結果累算値が算出され、ステージ0においてその重み付き分岐結果累算値を用いて予測処理が行われる。ただし、実際には、各分岐命令に対して予測値を出力する必要があるので、上述した各ステージの処理は並行して行われる。つまり、ステージ0の処理は、前回分岐命令が入力された際に行われたステージ1の処理結果を利用して行われる。換言すれば、ステージ1の処理は、次に入力される分岐命令に対する予測のために実行される。
【0146】
次に、ステージ0処理の流れの例を図12のフローチャートを参照して説明する。
【0147】
ステージ0処理が開始されると、重み付き分岐結果値累算部71は、ステップS21において、レジスタ44に保持されている重み付き分岐結果累算値81(REG[j])を全て読み出し、CSA tree111を用いて累算の続きを行い、それらの総和を途中まで算出する。この処理と並行して、閾値算出部72は、ステップS22において、実行パス履歴85の最新のアドレスA[0]をインデックスとしてローカル履歴86より分岐結果(LHT(A[0]))を読み出す。また、閾値算出部72は、そのステップS22の処理と並行して、さらに、ステップS23の処理を行い、実行パス履歴85の最新のアドレスA[0]の所定ビット数の上位ビットをインデックスとして、閾値用の重みテーブル82-0より、そのインデックスに対応する閾値の候補(WT[0](A[0]))を全て取得する。
【0148】
ステップS22およびステップS23の処理を終了すると、閾値算出部72は、ステップS24において、セレクタ112により、ローカル履歴86より読み出した分岐結果に基づいて、重みテーブル82-0より選択された閾値の候補の中から閾値として採用するものを選択する。
【0149】
ステップS21およびステップS24の処理が終了すると、予測値算出部73は、ステップS25において、CSA113およびCPA114を用いて重み付き分岐結果累算値の総和と閾値を加算し、ステップS26において、加算結果の最上位ビットの値を反転させ、ステップS27において、その反転結果(最上位ビット)を予測値として出力する。
【0150】
次に、図13のフローチャートを参照して、ステージ1処理の流れの例を説明する。
【0151】
ステージ1処理部51の重み選択部61は、ステップS41において、予測すべき分岐命令branch Bからの命令間距離を示す変数jの値を「1」に設定する。ステップS42において、重み選択部61は、その変数jの値が「I」以下であるか否かを判定する。つまり、重み選択部61は、今回重み付けを行うグローバル履歴84の分岐結果の、branch Bからの命令間距離がIよりも短いか否か(つまり、branch Bに比較的近い分岐命令の分岐結果であるか否か)を判定する。
【0152】
変数jの値が「I」以下であると判定された場合、重み選択部61は、処理をステップS43に進め、重み付き分岐結果値算出部62とともに、NDIをインデックスとして使用して重みを選択し、選択した重みを分岐結果に乗算するNDI使用重み読み出し処理を行う。NDI使用重み読み出し処理の詳細については後述する。NDI使用重み読み出し処理が終了すると、重み選択部61は、処理をステップS45に進める。
【0153】
また、ステップS42において、変数jの値が「I」より大きいと判定された場合、重み選択部61は、処理をステップS44に進め、重み付き分岐結果値算出部62とともに、LDIをインデックスとして使用して重みを選択し、選択した重みを分岐結果に乗算するLDI使用重み読み出し処理を行う。LDI使用重み読み出し処理の詳細については後述する。LDI使用重み読み出し処理が終了すると、重み選択部61は、処理をステップS45に進める。
【0154】
ステップS45において、重み選択部61は、変数jの値を「1」インクリメントし、重み付けの処理対象を次の分岐結果に切り返る。ステップS46において、重み選択部61は、変数jの値が任意の自然数nより大きいか否かを判定し、変数jの値がnより大きくなく、j番目の重みテーブル82(WT[j])が存在すると判定した場合、処理をステップS42に戻し、それ以降の処理を繰り返す。つまり、重み選択部61は、ステップS42乃至ステップS46の処理を繰り返し実行することにより、予測処理に利用されるグローバル履歴84の全ての分岐結果に対して重み付けを行う。そして、ステップS46において変数jの値がnより大きく、処理対象とする全ての分岐結果に対して重み付けを行ったと判定した場合、重み選択部61は、処理をステップS47に進める。
【0155】
重み付き分岐結果値累算部63は、ステップS47において、以上のようにして算出された各重み付き分岐結果値を累算し、ステップS48において、算出された重み付き分岐結果累算値の途中結果であるREG[r]をレジスタ44に保持させる。
【0156】
ステップS48の処理が終了されるとステージ1処理は終了される。
【0157】
次に、図13のステップS43において実行されるNDI使用重み読み出し処理の詳細な流れの例を、図14のフローチャートを参照して説明する。
【0158】
ステップS61において、重み選択部61は、入力された最新のアドレスA[0]および多重化アドレスを用いてNDI[j]を生成する。ステップS62において、重み選択部61は、そのNDI[j]をインデックスとしてWT[j](WT[j](NDI[j])より重みを取得する。ステップS63において、重み付き分岐結果値算出部62は、グローバル履歴84の分岐結果GHR[j-1]の値が「1」であるか否かを判定し、「1」であると判定した場合、WT[j]より読み出した重みを重み付き分岐結果値とし、NDI使用重み読み出し処理を終了する。つまり、重み付き分岐結果値算出部62は、この場合、セレクタ102-jを制御して、WT[j]より選択された重みがそのままCSA tree103に出力されるようにする。
【0159】
また、ステップS63において、グローバル履歴84の分岐結果GHR[j-1]の値が「-1」であると判定した場合、重み付き分岐結果値算出部62は、処理をステップS64に進め、WT[j]より読み出した重みの符号を反転させ、その値を重み付き分岐結果値とし、NDI使用重み読み出し処理を終了する。つまり、重み付き分岐結果値算出部62は、この場合、セレクタ102-jを制御して、WT[j]より選択された重みがインバータ101を介してCSA tree103に出力されるようにする。
【0160】
NDI使用重み読み出し処理が終了されると、処理は、図13のステップS43に戻り、ステップS45以降の処理が実行される。
【0161】
次に、図13のステップS44において実行されるLDI使用重み読み出し処理の詳細な流れの例を、図15のフローチャートを参照して説明する。
【0162】
ステップS81において、重み選択部61は、入力された最新のアドレスA[0]および多重化アドレスを用いてLDI[j]を生成する。ステップS82において、重み選択部61は、そのLDI[j]をインデックスとしてWT[j](WT[j](LDI[j])より重みを取得する。ステップS83において、重み付き分岐結果値算出部62は、グローバル履歴84の分岐結果GHR[j-1]の値が「1」であるか否かを判定し、「1」であると判定した場合、WT[j]より読み出した重みを重み付き分岐結果値とし、LDI使用重み読み出し処理を終了する。つまり、重み付き分岐結果値算出部62は、この場合、セレクタ102-jを制御して、WT[j]より選択された重みがそのままCSA tree103に出力されるようにする。
【0163】
また、ステップS83において、グローバル履歴84の分岐結果GHR[j-1]の値が「-1」であると判定した場合、重み付き分岐結果値算出部62は、処理をステップS84に進め、WT[j]より読み出した重みの符号を反転させ、その値を重み付き分岐結果値とし、LDI使用重み読み出し処理を終了する。つまり、重み付き分岐結果値算出部62は、この場合、セレクタ102-jを制御して、WT[j]より選択された重みがインバータ101を介してCSA tree103に出力されるようにする。
【0164】
LDI使用重み読み出し処理が終了されると、処理は、図13のステップS44に戻り、ステップS45以降の処理が実行される。
【0165】
以上のように、各ステージの処理が実行される。
【0166】
次に、図16のフローチャートを参照して、図2の学習処理部42により実行される学習処理の流れの例を説明する。
【0167】
学習処理は、演算部24において行われた実際の命令実行結果を、重みテーブル82の内容に反映させるように、それらの学習を行う処理である。この学習処理は、学習処理部42によって、上述した分岐予測処理とは独立して、パイプライン処理が行われている間実行される。
【0168】
例えば、学習処理が開始されると、学習処理部42は、ステップS101において、演算部24より取得した情報に基づいて、分岐方向が確定したか否か、すなわち、演算部24において分岐命令が実行されその実行結果が得られたか否かを判定し、得られたと判定するまで待機する。分岐命令の実行結果は、演算部24より分岐予測部21に供給される。分岐命令の実行が終了し、分岐方向が確定したと判定した場合、学習処理部42は、ステップS102において、ステージ0において算出された予測値と演算部24より取得した分岐命令の実行結果である分岐結果とが等しいか否か(予測が当たったか否か)を判定する。予測値と分岐結果とが等しい(予測が当たった)と判定した場合、学習処理部42は、処理をステップS103に進め、予測値を算出する際の重み付き分岐結果累算値の総和と閾値との加算結果の絶対値が、予め定められた所定の値である偏向値θより小さいか否かを判定する。すなわち、その予測が十分に確信を持ってなされたものであるか否か(予測値の信頼性が高いか否か)を判定する。
【0169】
ステップS103において、予測時の計算値の絶対値が偏向値θより小さい、つまり、予測値の信頼性が低いと判定された場合、学習処理部42は、処理をステップS104に進める。また、ステップS103において、予測値と分岐結果とが等しくない(予測が外れた)と判定した場合、学習処理部42は、処理をステップS106に進める。
【0170】
ステップS104において、学習処理部42は、今回の分岐方向と値が一致するグローバル履歴84の分岐結果(GHR[p])に対応する重みの値に「1」を加算するように、レジスタ44に保持されている重みテーブル82を更新する。
【0171】
ステップS104の処理を終了すると、学習処理部42は、ステップS105に処理を進め、各重みテーブルの、今回の分岐方向と値が一致しないグローバル履歴84の分岐結果(GHR[p])に対応する重みの値に「1」を減算するように、レジスタ44に保持されている重みテーブル82を更新する。
【0172】
換言すると、学習処理部42は、ステップS104およびステップS105の処理により、図10に示される各重みテーブル82の、今回の分岐予測処理において読み出される値に「1」を加算または減算することにより、分岐方向と値が一致するグローバル履歴の重みを増し、分岐方向と一致しないグローバル履歴の重みを低減させるように、グローバル履歴84の各分岐結果(GHR[p])の重みを再調整する(更新する)。
【0173】
ステップS105の処理を終了すると、学習処理部42は、処理をステップS106に進める。
【0174】
ステップS106において、更新処理部43は、分岐方向が確定すると、最新の多重化アドレス83内の最も過去のローカル履歴ビットを分岐結果と置換する。つまり、更新処理部43は、多重化アドレス83の更新を行う。
【0175】
ステップS106の処理が終了されると、学習処理が終了される。
【0176】
以上より、本実施形態によれば、分岐予測部21は、予測に用いる重みテーブルの数を低減させて実装コストを低減させるとともに、より詳細な実行パス履歴情報を重み読み出しのインデックスに反映させることにより、テーブル当たりのエントリ数を増大させ、分岐予測の予測精度向上を実現させることができる。
【0177】
以上のような分岐予測部21による分岐予測処理の予測精度をシミュレーション結果について説明する。
【0178】
まず、最適な重みのビット長を求めるためのシミュレーションについて説明する。最適な重みのビット長を求めるためにNDIの数Iと、LDIの数(n-I)を変えて予測精度を求めた。図17にそのシミュレーション結果を示す。図17に示されるグラフは、重みのビット長と予測ミス率の関係を、テーブル数(NDIをインデックスとするテーブルとLDIをインデックスとするテーブルのそれぞれの数)毎に示している。
【0179】
図17に示されるシミュレーションにおいては、NDIをインデックスとするテーブルの数Iと、LDIをインデックスとするテーブルの数(n-1)の組み合わせが、(3,1)の場合、(5,3)の場合、および(7,5)の3つの場合について、重みのビット長と予測ミス率の関係を比較した。
【0180】
図17に示されるグラフより、どのテーブル数の場合においても、重みのビット長は、長くなるほど予測精度が高くなることがわかる。ただし、6ビット以上ではほとんど変化していない。不要に重みのビット長を増大させると負荷の増大に繋がる恐れがある。そこで、以下のシミュレーションにおいては、重みのビット長は6とする。従来のパーセプトロン分岐予測器においては、一般的に、重みのビット長は8ビットとされていた。つまり、従来の一般的なパーセプトロン分岐予測器の場合よりも重みのビット長が短く設定される。
【0181】
次に、本実施の形態において説明した手法と、従来法の予測精度を比較する。比較対象としてPipelined PTBPとO-GEHL branch predictorを用いた。いずれも、本実施の形態において説明した手法と略同程度の複数の重みテーブルと加算器を備える分岐予測器である。なお、本実施の形態において説明した手法については、分岐命令の分岐方向が確定した後に多重化アドレスを更新する場合と更新しない場合の両方についてシミュレーションを行った。また、各分岐予測器の記憶容量が、8Kバイト、16Kバイト、32Kバイト、64Kバイト、および128Kバイトの5つの場合についてそれぞれシミュレーションを行った。
【0182】
図18に示される表は、シミュレーションにおいて各分岐予測器に割り当てたパラメータの例を示している。例えば、記憶容量が8Kバイトの場合、Pipelined PTBPのテーブル数は22とし、重みビット長は8ビットとし、O-GEHL branch predictorのテーブル数は8とし、本実施の形態において説明した分岐予測器(Proposed)のテーブル数は、NDIをインデックスとするテーブルの数、LDIをインデックスとするテーブルの数、および、ステージ0に割り当てられる閾値設定用のテーブル(バイアステーブル)の数をそれぞれ、3/2/1とし、重みビット長を6ビットとし、閾値シフトを1ビットとする。
【0183】
また、Proposedのバイアステーブルは、他のテーブルの2倍の容量とし、多重化アドレスで使用するローカル履歴長は2bitとした.閾値シフトはバイアステーブルから読みだされた閾値に対する右シフトの桁数である。また、更新閾値は、テーブルの総数をTとし、閾値シフトをq桁とした時、2.1×(T+2q)とした。
【0184】
図19は、以上のような条件下で、各予測器の記憶容量と予測ミス率の関係を示すグラフである。曲線201がPipelined PTBPの記憶容量と予測ミス率の関係を示しており、曲線202がO-GEHL branch predictorの記憶容量と予測ミス率の関係を示しており、曲線203が、予測すべき分岐命令の分岐方向が確定した後に多重化アドレスの更新を行わない場合の、Proposedの記憶容量と予測ミス率の関係を示しており、曲線204が、予測すべき分岐命令の分岐方向が確定した後に多重化アドレスの更新を行う場合の、Proposedの記憶容量と予測ミス率の関係を示している。
【0185】
図19に示されるように、Proposedの分岐予測器は、全ての記憶容量において、他の分岐予測器よりも予測ミス率が低い(曲線203および曲線204)。特に、多重化アドレスの更新を行う場合(曲線204)の方が、多重化アドレスの更新を行わない場合(曲線203)よりも予測ミス率が低い。
【0186】
Proposedの分岐予測器のハードウェアコストを従来の分岐予測器と比較すると、同じ記憶容量で比較した場合、主なハードウェア量の違いは、重みの読み出し、加減算、更新に関する回路である。パーセプトロン分岐予測器は、1つの重みに対してそれぞれ1つの読み出しおよび更新回路が必要となる。さらに、重みの累算回路の回路面積も累算する重みの数に比例する。図18の表に示されているように、Proposedの分岐予測器のテーブル数は、Pipelined PTBPのテーブル数と比べて4分の1程度である。つまり、本実施の形態において説明したProposedの分岐予測器では、これらの回路の数がPipelined PTBPの4分の1程度で済むことになる。また、重みのビット長も短くなっているため、加減算や更新に関する回路の1単位当たりの面積コストも低減される。
【0187】
次にレイテンシを従来法と比較する。Proposedの分岐予測器の場合、累算する重みの数が少なく、重みのビット長も短いためCPA回路が縮小される。この結果、CPAのレイテンシは従来の分岐予測器よりも軽減される。反対にテーブルのエントリ数の違いによりテーブル読み出しのレイテンシは増加する。ただし、その増加量はエントリ数の対数値に比例する。Proposedの分岐予測器と従来の分岐予測器とのエントリ数の比は最大で4倍程度であり、この分のレイテンシの増加は小さいことが分かる。以上から本実施の形態において説明した分岐予測器のレイテンシは従来の分岐予測器と同等であると言える。さらに、累算する重みの数が減少しているため累算のレイテンシも大幅に減少するので、ステージ1で読み出した複数の重みをバイアスと加算する前にCPAを用いて累算しておくことも可能である。このようにすることで、Proposedの分岐予測器の場合、従来の分岐予測器と比べてCSA1個のレイテンシを軽減させることができる。
【0188】
以上のように、本実施の形態において説明したProposedの分岐予測器は、従来の予測精度のみでなく実装コストやレイテンシの面でも優れていることが分かる。つまり、Proposedの分岐予測器は、実装コストの低減、および、分岐予測の予測精度向上を実現させることができる。
【0189】
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、図20に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。
【0190】
図20において、パーソナルコンピュータ300のCPU301は、ROM(Read Only Memory)302に記憶されているプログラム、または記憶部313からRAM(Random Access Memory)303にロードされたプログラムに従って各種の処理を実行する。RAM303にはまた、CPU301が各種の処理を実行する上において必要なデータなども適宜記憶される。
【0191】
CPU301、ROM302、およびRAM303は、バス304を介して相互に接続されている。このバス304にはまた、入出力インタフェース310も接続されている。
【0192】
入出力インタフェース310には、キーボード、マウスなどよりなる入力部311、CRTやLCDなどよりなるディスプレイ、並びにスピーカなどよりなる出力部312、ハードディスクなどより構成される記憶部313、モデムなどより構成される通信部314が接続されている。通信部314は、インターネットを含むネットワークを介しての通信処理を行う。
【0193】
入出力インタフェース310にはまた、必要に応じてドライブ315が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア321が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部313にインストールされる。
【0194】
上述した一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
【0195】
この記録媒体は、例えば、図20に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク(フレキシブルディスクを含む)、光ディスク(CD-ROM(Compact Disc - Read Only Memory),DVD(Digital Versatile Disc)を含む)、光磁気ディスク(MD(Mini Disc)を含む)、もしくは半導体メモリなどよりなるリムーバブルメディア321により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM302や、記憶部313に含まれるハードディスクなどで構成される。
【0196】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【0197】
また、本明細書において、システムとは、複数のデバイス(装置)により構成される装置全体を表すものである。
【0198】
なお、以上において、1つの装置として説明した構成を分割し、複数の装置として構成するようにしてもよい。逆に、以上において複数の装置として説明した構成をまとめて1つの装置として構成されるようにしてもよい。また、各装置の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置の構成の一部を他の装置の構成に含めるようにしてもよい。つまり、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【産業上の利用可能性】
【0199】
本発明は、分岐予測器に適用することが可能である。
【図面の簡単な説明】
【0200】
【図1】本発明を適用した情報処理システムの構成例を示すブロック図である。
【図2】図1の分岐予測部の詳細な構成例を示すブロック図である。
【図3】パラメータの例を説明する図である。
【図4】多重化アドレスの生成手順を説明する模式図である。
【図5】多重化アドレスを用いた重み読み出しの例を説明する図である。
【図6】アドレスの種類数に応じたインデックスの生成方法を説明する表である。
【図7】多重化アドレスの種類数と予測ミス率との関係を示すグラフである。
【図8】使用される多重化アドレスの分布の例を示すグラフである。
【図9】更新を行わない場合と、更新を行う場合の多重化アドレスを比較する図である。
【図10】予測処理部により実行される予測処理のパイプライン構造の構成例を模式的に示す図である。
【図11】パイプライン処理の流れの例を説明する図である。
【図12】ステージ0処理の流れの例を説明するフローチャートである。
【図13】ステージ1処理の流れの例を説明するフローチャートである。
【図14】NDI使用重み読み出し処理の流れの例を説明するフローチャートである。
【図15】LDI使用重み読み出し処理の流れの例を説明するフローチャートである。
【図16】学習処理の流れの例を説明するフローチャートである。
【図17】テーブル数と予測ミス率の関係を説明するグラフである。
【図18】分岐予測器毎のパラメータの例を示す表である。
【図19】分岐予測器毎の記憶容量と予測ミス率との関係を示すグラフである。
【図20】本発明を適用したパーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
【0201】
11 CPU, 21 分岐予測部, 41 予測処理部, 42 学習処理部, 43 更新処理部, 44 レジスタ, 51 ステージ1処理部, 52 ステージ0処理部, 61 重み選択部, 62 重み付き分岐結果値算出部, 63 重み付き分岐結果値累算部, 71 重み付き分岐結果値累算部, 72 閾値算出部, 73 予測値算出部, 74 多重化アドレス生成部, 81 重み付き分岐結果累算値, 82 重みテーブル, 83 多重化アドレス, 84 グローバル履歴, 85 実行パス履歴, 86 ローカル履歴, 87 通常間隔インデックス, 88 長間隔インデックス, 101 インバータ, 102 セレクタ, 103 CSA tree, 111 CSA tree, 112 セレクタ, 113 CSA, 114 CPA
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19