(57)【特許請求の範囲】
【請求項１】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、
前記グローバル履歴の履歴数よりも少ない最近のｎ回の分岐命令に対応したｎ個の重みテーブルであって、それぞれの重みテーブルは、
最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、
前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルと、
前記最近のｎ回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、
前記グローバル履歴に含まれる前記最近のｎ回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、
前記重み付き分岐結果値算出手段により最近のｎ回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、
少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段と
を備える情報処理装置。
【請求項２】
少なくとも、前記重み選択手段による前記重みの選択、および、前記重み付き分岐結果値算出手段による重み付き分岐結果値の算出をステージ１とし、
少なくとも、前記予測値算出手段による予測値の算出をステージ０とし、
ステージ毎に順次処理を行う
請求項１に記載の情報処理装置。
【請求項３】
前記ステージ１における処理の処理結果を保持する保持手段をさらに備え、
前記分岐命令の分岐方向の予測の度に、前記ステージ０の処理、および、前記ステージ１の処理を行い、
前記ステージ１の処理の処理結果を前記保持手段に保持させるとともに、前記ステージ０の処理を、前記保持手段に保持されている前回の予測において行われた前記ステージ１の処理の処理結果を用いて行う
請求項２に記載の情報処理装置。
【請求項４】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ１とし、
前記ステージ１において前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値の累算結果を前記保持手段に保持させ、
前記ステージ０において、前記予測値算出手段により、前記保持手段に保持されている前記累算結果を用いて前記予測値を算出させる
請求項３に記載の情報処理装置。
【請求項５】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算の一部を前記ステージ１とし、残りの一部を前記ステージ０とし、
前記ステージ１において、前記重み付き分岐結果値累算手段により、前記重み付き分岐結果値の累算を途中まで行わせ、
得られた累算途中結果を前記保持手段に保持させ、
前記ステージ０において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記累算途中結果をさらに累算させる
請求項３に記載の情報処理装置。
【請求項６】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ０とし、
前記ステージ１において前記重み付き分岐結果値算出手段により算出された重み付き分岐結果を前記保持手段に保持させ、
前記ステージ０において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記重み付き分岐結果を累算させる
請求項３に記載の情報処理装置。
【請求項７】
前記重みテーブルのインデックスに含まれる複数の多重化アドレスに対応する過去の複数の分岐命令は、前記各重みテーブル間で重複が少なくなるように決定されたものである
請求項１から６のいずれか１項に記載の情報処理装置。
【請求項８】
複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令における前記多重化アドレスからインデックスが生成されたものであり、
複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令における前記多重化アドレスからインデックスが生成されたものである
請求項７に記載の情報処理装置。
【請求項９】
前記予測値算出手段により算出された前記予測値と実際の分岐結果の一致不一致に基づいて、前記重みテーブルの重みの値を更新する学習処理を行う学習手段をさらに備える
請求項１から８のいずれか１項に記載の情報処理装置。
【請求項１０】
前記学習手段は、さらに、前記多重化アドレスに反映されたローカル履歴を、前記実際の分岐結果に置換する
請求項９に記載の情報処理装置。
【請求項１１】
予測対象分岐命令のターゲットアドレスの多重化アドレスに対応づけられ閾値を保持した第２の重みテーブルと、
前記ターゲットアドレスの多重化アドレスで前記第２の重みテーブルを索引することによって閾値を算出する閾値算出手段を備え、
前記予測値算出手段は、前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値に、前記閾値算出手段により算出された前記閾値を加算することにより、前記予測値を算出する
請求項１から１０のいずれか１項に記載の情報処理装置。
【請求項１２】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のｎ回の分岐命令に対応したｎ個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備える情報処理装置の情報処理方法において、
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成し、
前記最近のｎ回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択し、
前記グローバル履歴に含まれる前記最近のｎ回の分岐命令毎に、選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出し、
最近のｎ回の分岐命令に対して算出された前記重み付き分岐結果値を累算し、
少なくとも累算された前記重み付き分岐結果値を用いて、予測値を算出する
情報処理方法。
【請求項１３】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のｎ回の分岐命令に対応したｎ個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備えるコンピュータを、
前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、
前記最近のｎ回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、
前記グローバル履歴に含まれる前記最近のｎ回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、
前記重み付き分岐結果値算出手段により最近のｎ回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、
少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段と
して機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置および方法、並びにプログラムに関し、特に、実装コストの低減、および、分岐予測の予測精度向上を実現させることができるようにした情報処理装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
近年、プロセッサのパイプラインはさらなる深化の傾向を見せており、パイプラインが深くなるにつれ制御ハザードに起因する性能低下はより深刻なものとなってきている。制御ハザードはプログラム内に存在するif文やWhile文に代表される分岐命令によって引き起こされる。これを回避する１つの手段として用いられるのが分岐命令の分岐方向（分岐成立（Taken）、若しくは、分岐不成立（Not Taken））を予測する分岐予測である。１９９０年代に入りgshare分岐予測器が考えられたが、わずかな予測精度向上でプロセッサのパフォーマンスは大幅に向上するため、分岐予測器には、さらなる予測精度の向上が要求された。
【０００３】
分岐予測器はCPUの性能向上に大きな役割を果たしており、近年において活発に研究が行われている。中でも学習理論の一種であるパーセプトロンを応用したパーセプトロン分岐予測器は、単体で高い予測精度を示すことで注目されている。
【０００４】
パーセプトロン分岐予測器は、予測すべき分岐命令であるbranch Bのアドレスの他に過去に実行した分岐命令のアドレスを時系列に並べた実行パス履歴、過去の分岐結果の履歴を時系列順に並べたグローバル履歴、および、この分岐履歴を対の情報である分岐命令のアドレスを用いて並び替えたローカル履歴などを用いて予測を行う（例えば、特許文献１参照）。
【０００５】
パーセプトロン分岐予測器は、branch Bのアドレスや実行パス履歴をインデックスとして重みテーブルと呼ばれる多数のテーブルからそれぞれ重みと呼ばれる整数値を読み出す。これらの重みはそれぞれグローバル履歴の特定の場所と１対１に対応している。グローバル履歴の各要素は、１ならば分岐成立、−１ならば分岐不成立を表わす。パーセプトロン分岐予測器は、読み出された重みをWiとし、対応するグローバル履歴の要素をXiとし、さらに、１≦ｉ≦ｎとし、次式を計算する。
【０００６】
【数１】
0005283054.tif 000002
【０００７】
式（１）において、W0はバイアスであり、重みと同様に読み出される。パーセプトロン分岐予測器は、求められたyの値が正ならば分岐成立として値「１」を出力し、yの値が負ならば分岐不成立として値「−１」を出力する。重みWiの更新規則は、分岐結果をｔ∈{１，−１}とすると次式によって表される。通常の場合、α＝１とする。
【０００８】
【数２】
0005283054.tif 000003
【０００９】
以上の様なパーセプトロン分岐予測器として、これまでに、基本的な構造によるGlobal/Local Perceptron Branch Predictor、予測処理のパイプライン化を可能としたPath-based Neural Predictor、重み読み出しのインデックスを工夫したPiecewise Linear Branch Predictor、重み読み出しの並列化を行ったPTBP、およびAdvanced Anti-Aliasing Perceptron Branch Predictor (A3PBP)などのパーセプトロン分岐予測器等が知られている。
【００１０】
例えば、A3PBPは、実行パス履歴の情報をより効率的に利用する構造を持ち、ローカル履歴を重み読み出しのインデックスに利用することにより、重みの負の衝突を削減し予測精度を向上させた（例えば非特許文献１および非特許文献２参照）。
【００１１】
A3PBPでは、ステージｎにおけるｍ番目の重みテーブルTableｉ＝（ｎ−１）Ｍ＋ｍ（１≦ｎ≦ｈ，１≦ｍ≦Ｍ）のインデックスindex[ｉ]を、Ａ［ｓ］を用いて生成する。Ａ［ｓ］は、branch Bよりｓ個前の分岐命令のアドレス、すなわち、実行パス履歴を表す。Ａ［０］は、そのステージで得られうる最新のアドレスを示す。A3PBPは、この実行パス履歴を構成するアドレスの一部分をローカル履歴ビットに置換した多重化アドレスを用いて、以下の式（３）のように、最新のアドレスＡ［０］と多重化アドレスの排他的論理和によりindex［ｉ］を生成し、そのインデックスを用いて重みを選択する。
【００１２】
【数３】
0005283054.tif 000004
【００１３】
【特許文献１】特開平１０−１７１６５３号公報
【非特許文献１】二ノ宮康之、阿部公輝「実行パスとローカル履歴を重み選択に利用したパーセプトロン分岐予測器」情報処理学会研究報告(IPSJ SIG Technical Report),2006-ARC-169(6),2006年8月1日,p.31-36
【非特許文献２】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.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、パーセプトロン分岐予測器は複雑な構造を持つためその回路量が大きい。さらに、パーセプトロン分岐予測器において、重みテーブルの数（予測計算に使う重みの数と等しい）が増加すると累算に要するハードウェアコストや計算レイテンシが増大する。
【００１５】
仮に、ハードウェアコストを増大させないようにするために、テーブルを記憶する記憶容量を一定とすると、テーブル数が多い程、１つあたりのテーブルのエントリ数は相対的に小さくなる。しかしながら、エントリ数の不足は使用する重みの衝突を引き起こし、予測精度低下の主因となる恐れがある。
【００１６】
以上の点を、換言すれば、テーブル数を削減することにより、実装コストや計算レイテンシを低減させ、さらに、重みの負の衝突の発生を抑制させることができる。
【００１７】
しかしながら、テーブル数を削減するには、使用するグローバル履歴長も短くする必要があるが、単純に予測に反映させる履歴情報の長さを短くすると、その分、予測精度が低減する恐れがある。
【００１８】
マルチコア化の進むCPU（Central Processing Unit）に実装するためには精度の向上とともに実装コストの削減が求められる。
【００１９】
本発明は、このような従来の実情に鑑みて提案されたものであり、実装コストの低減、および、分岐予測の予測精度向上を実現させることができるようにするものである。
【課題を解決するための手段】
【００２０】
本発明の第１の側面は、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、前記グローバル履歴の履歴数よりも少ない最近のｎ回の分岐命令に対応したｎ個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルと、前記最近のｎ回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、前記グローバル履歴に含まれる前記最近のｎ回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、前記重み付き分岐結果値算出手段により最近のｎ回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段とを備える情報処理装置である。
【００２１】
少なくとも、前記重み選択手段による前記重みの選択、および、前記重み付き分岐結果値算出手段による重み付き分岐結果値の算出をステージ１とし、少なくとも、前記予測値算出手段による予測値の算出をステージ０とし、ステージ毎に順次処理を行うことができる。
【００２２】
前記ステージ１における処理の処理結果を保持する保持手段をさらに備え、前記分岐命令の分岐方向の予測の度に、前記ステージ０の処理、および、前記ステージ１の処理を行い、前記ステージ１の処理の処理結果を前記保持手段に保持させるとともに、前記ステージ０の処理を、前記保持手段に保持されている前回の予測において行われた前記ステージ１の処理の処理結果を用いて行うことができる。
【００２３】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ１とし、前記ステージ１において前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値の累算結果を前記保持手段に保持させ、前記ステージ０において、前記予測値算出手段により、前記保持手段に保持されている前記累算結果を用いて前記予測値を算出させることができる。
【００２４】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算の一部を前記ステージ１とし、残りの一部を前記ステージ０とし、前記ステージ１において、前記重み付き分岐結果値累算手段により、前記重み付き分岐結果値の累算を途中まで行わせ、得られた累算途中結果を前記保持手段に保持させ、前記ステージ０において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記累算途中結果をさらに累算させることができる。
【００２５】
前記重み付き分岐結果値累算手段による重み付き分岐結果値の累算を前記ステージ０とし、前記ステージ１において前記重み付き分岐結果値算出手段により算出された重み付き分岐結果を前記保持手段に保持させ、前記ステージ０において、前記重み付き分岐結果値累算手段により、前記保持手段に保持されている前記重み付き分岐結果を累算させることができる。
【００２６】
前記重みテーブルのインデックスに含まれる複数の多重化アドレスに対応する過去の複数の分岐命令は、前記各重みテーブル間で重複が少なくなるように決定されたものであるようにすることができる。
【００２７】
複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的近い分岐命令における前記多重化アドレスからインデックスが生成されたものであり、複数の前記重みテーブルのうち、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令に対応する重みテーブルは、前記グローバル履歴上での命令間距離が予測すべき分岐命令に比較的遠い分岐命令における前記多重化アドレスからインデックスが生成されたものであるようにすることができる。
【００２８】
前記予測値算出手段により算出された前記予測値と実際の分岐結果の一致不一致に基づいて、前記重みテーブルの重みの値を更新する学習処理を行う学習手段をさらに備えることができる。
【００２９】
前記学習手段は、さらに、前記多重化アドレスに反映されたローカル履歴を、前記実際の分岐結果に置換することができる。
【００３０】
予測対象分岐命令のターゲットアドレスの多重化アドレスに対応づけられ閾値を保持した第２の重みテーブルと、前記ターゲットアドレスの多重化アドレスで前記第２の重みテーブルを索引することによって閾値を算出する閾値算出手段を備え、前記予測値算出手段は、前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値に、前記閾値算出手段により算出された前記閾値を加算することにより、前記予測値を算出することができる。
【００３１】
本発明の第１の側面は、また、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のｎ回の分岐命令に対応したｎ個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備える情報処理装置の情報処理方法において、前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成し、前記最近のｎ回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択し、前記グローバル履歴に含まれる前記最近のｎ回の分岐命令毎に、選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出し、最近のｎ回の分岐命令に対して算出された前記重み付き分岐結果値を累算し、少なくとも累算された前記重み付き分岐結果値を用いて、予測値を算出する情報処理方法である。
【００３２】
本発明の第１の側面は、さらに、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、前記グローバル履歴の履歴数よりも少ない最近のｎ回の分岐命令に対応したｎ個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、前記最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、前記過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルを備えるコンピュータを、前記分岐命令のアドレスに対して、前記分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスを生成する多重化アドレス生成手段と、前記最近のｎ回の分岐命令毎に前記インデックスにより各重みテーブルから重みを選択する重み選択手段と、前記グローバル履歴に含まれる前記最近のｎ回の分岐命令毎に、前記重み選択手段により選択された前記各重みと前記分岐命令の分岐成立若しくは不成立に対応した値との積を重み付き分岐結果値として算出する重み付き分岐結果値算出手段と、前記重み付き分岐結果値算出手段により最近のｎ回の分岐命令に対して算出された前記重み付き分岐結果値を累算する重み付き分岐結果値累算手段と、少なくとも前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値を用いて、予測値を算出する予測値算出手段として機能させるプログラムである。
【００３３】
本発明の第１の側面においては、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する、グローバル履歴の履歴数よりも少ない最近のｎ回の分岐命令に対応したｎ個の重みテーブルであって、それぞれの重みテーブルは、最新の分岐命令のアドレスと、最新の分岐命令よりも重みテーブル毎に定められた数だけ過去の複数の分岐命令における多重アドレスとから生成されたインデックスによって重みを選択されるものであって、過去の複数の分岐命令に対して事前になされた分岐予測の正否に応じて付与された重みを保持するものである、該重みテーブルが備えられ、分岐命令のアドレスに対して、分岐命令における分岐結果が並べられたローカル履歴で分岐命令アドレスの下位ビットの一部を置き換えた多重化アドレスが生成され、最近のｎ回の分岐命令毎にインデックスにより各重みテーブルから重みが選択され、グローバル履歴に含まれる最近のｎ回の分岐命令毎に、選択された各重みと分岐命令の分岐成立若しくは不成立に対応した値との積が重み付き分岐結果値として算出され、最近のｎ回の分岐命令に対して算出された重み付き分岐結果値が累算され、少なくとも累算された重み付き分岐結果値を用いて、予測値が算出される。
【発明の効果】
【００３４】
本発明によれば、分岐命令の予測を行うことができる。特に、実装コストを低減させ、さらに、分岐予測の予測精度を向上させることができる。
【発明を実施するための最良の形態】
【００４９】
以下、本発明の実施の形態について説明する。
【００５０】
図１は、本発明を適用した情報処理装置の構成例を示すブロック図である。
【００５１】
図１の情報処理装置に搭載されるCPU（Central Processing Unit）１１は、命令実行を並列化し、前の命令の実行終了を待たずに次の命令を実行するパイプライン処理を行うプロセッサである。CPU１１は、メモリ１２に記憶されている命令を読み出して実行し、必要に応じて処理結果をメモリ１２に返す。
【００５２】
CPU１１は、分岐予測部２１、フェッチ部２２、デコード部２３、演算部２４、ライトバック部２５、命令キャッシュ３１、およびデータキャッシュ３２を有している。
【００５３】
１つの命令に対する実行処理は複数のステージ（工程）により構成される。つまり、命令キャッシュ３１に保持された命令を読み出すフェッチ（IF）、フェッチされた命令をデコードし、制御信号を生成したり、レジスタ・ファイルをレジスタ指定子で参照したり、必要に応じてデータキャッシュ３２よりデータを読み出したりするデコード（ID）、数値の計算やロード・ストアのデータやアドレス・分岐先の計算を行う命令実行（EX）、並びに、演算結果を、データキャッシュを介してメモリ１２に戻すライトバック（WB）などのステージがある。
【００５４】
命令キャッシュ３１は、メモリ１２より順次命令を読み出し保持する。フェッチ部２２は、IFステージにおいて、命令キャッシュ３１より命令をフェッチし、それをデコード部２３に供給する。デコード部２３は、IDステージにおいて、フェッチ部２２より供給された命令をデコードし、必要に応じてデータキャッシュ３２よりデータを取得し、それらを演算部２４に供給する。
【００５５】
演算部２４は、EXステージにおいて、デコード部２３より供給される情報に基づいて演算を行う。その演算結果はライトバック部２５に供給される。また、演算部２４は、演算結果によって次の命令（ジャンプ先のアドレス）が異なる分岐命令のライトバック部２５は、WBステージにおいて、演算部２４より供給された演算結果をデータキャッシュ３２に保持させる。データキャッシュ３２は、必要に応じて、その演算結果をデコード部２３に供給したり、メモリ１２に書き込ませたりする。
【００５６】
分岐予測部２１は、IFステージにおいて、演算部２４により実行される分岐命令について、そのの実行結果、すなわち分岐先（アドレス）を、演算部２４より供給される過去の演算結果等に基づいて予測する（分岐命令に対して分岐予測を行う）。つまり、分岐予測部２１は、この予測処理を、過去に実行された分岐命令の予測結果（分岐予測の正否）に応じて付与された重みによって重み付けされた、グローバル履歴の分岐結果を用いて行う。詳細については後述する。
【００５７】
フェッチ部２２は、その分岐予測部２１の予測に従って次の命令をフェッチする。
【００５８】
このとき、フェッチ部２２、デコード部２３、演算部２４、およびライトバック部２５は、パイプライン処理を行い、複数の命令を並列に実行する。すなわち、フェッチ部２２は、演算部２４の演算結果を待たずに、分岐予測部２１の予測結果に従って、命令キャッシュ３１より命令を次々とフェッチする。従って、分岐予測部２１の予測精度を向上させることにより、CPU１１において行われるパイプライン処理において制御ハザードの発生が減少するので、CPU１１の処理性能を向上させることができる。
【００５９】
次に、その分岐予測部２１の構成について説明する。図２は、図１の分岐予測部２１の詳細な構成例を示すブロック図である。
【００６０】
図２において、分岐予測部２１は、上述したパイプラインを用いて分岐予測を行う予測処理部４１、分岐命令のアドレスに分岐命令ごとの分岐結果の履歴であるローカル履歴を反映させた多重化アドレスを生成する多重化アドレス生成部７４、分岐予測に使用される重みテーブルの各重みについて、分岐命令の演算結果に基づいて学習を行う学習処理部４２、分岐予測に使用される各パラメータの更新を行う更新処理部４３、および分岐予測に使用される各パラメータやデータを保持するレジスタ４４を有している。
【００６１】
レジスタ４４は、予測処理部４１の分岐予測に使用されるパラメータやデータ等を必要に応じて保持する。レジスタ４４には、例えば、重み付き分岐結果累算値８１、重みテーブル８２、多重化アドレス８３、グローバル履歴８４、実行パス履歴８５、ローカル履歴８６、通常間隔インデックス８７、および長間隔インデックス８８が保持される。
【００６２】
グローバル履歴８４は、プログラム全体における分岐結果を時系列に並べた分岐結果の履歴（分岐履歴）である。GHR［ｐ］は、グローバル履歴８４における最新の分岐結果から（ｐ＋１）番目の分岐結果を示す（０≦ｐ≦n−１）。各分岐結果は、分岐成立（Taken）を示す値「１」、若しくは、分岐不成立（Not Taken）を示す値「−１」により構成される。つまり、各分岐結果は分岐方向を示す。ただし、「−１」は実際には「０」で表現されている。
【００６３】
実行パス履歴８５は、グローバル履歴８４の各分岐結果に対応する分岐命令のアドレスの履歴、すなわち、実行された各分岐命令のアドレスである。Ａ［ｐ］は、実行パス履歴８５における最新のアドレスから（ｐ＋１）番目のアドレスを示す。つまり、グローバル履歴８４の分岐結果GHR［ｐ］は、実行パス履歴８５のアドレスＡ［ｐ］で示される分岐命令の分岐結果を示す。また、Ａ［０］は、その時点での最新の分岐命令アドレスを示す。なお、最新の分岐結果GHR［０］によりジャンプする先のアドレス、つまり、これかから実行される分岐命令のアドレスをターゲットアドレス（TA）とも称する。つまり、換言すると、古い（最新でない）ターゲットアドレス（TA）が実行パス履歴８５に時系列順に蓄積される。
【００６４】
ローカル履歴（LHT（Local History Table））８６は、グローバル履歴８４の各分岐結果を、分岐命令ごとにまとめたものである。例えば、LHT［ｑ］は、ある分岐命令の、最新の分岐結果からｑ（０≦ｑ＜ｐ）番目の分岐結果を示す。つまり、ローカル履歴８６においても、グローバル履歴８４と同様に、各分岐結果は分岐方向を示し、その値は、分岐成立（Taken）を示す値「１」、若しくは、分岐不成立（Not Taken）を示す値「−１」により構成される。
【００６５】
図３を参照して、グローバル履歴８４乃至ローカル履歴８６についてさらに詳細に説明する。
【００６６】
図３の左に示されるプログラム（sample.c）９１は、グローバル履歴８４乃至ローカル履歴８６の説明のための、分岐命令を含むプログラムの例である。プログラム９１においては、分岐命令として、２００行目にfor文が記述され、２０８行目、２１６行目、および２２４行目にif文が記述されている。
【００６７】
図３の右側には、このプログラム９１について、グローバル履歴８４、実行パス履歴８５、およびローカル履歴８６の例が示されている。各履歴は、図３において、左から右に向かって時系列順に並んでいる。つまり、最も左側の履歴が一番古く、最も右側の履歴が一番新しい。実行パス履歴８５の、最も古い（一番左の）アドレスは「２００」であり、２００行目のfor文が実行されたことが示されている。
【００６８】
このアドレスに対応するグローバル履歴８４の分岐結果（GH）は「０」であり、２００行目のfor文の条件（i<2）が真であったことが示されている。従って、このときのターゲットアドレス、すなわち次（実行パス履歴８５の左から２番目）のアドレスは、for文のループ内の次の分岐命令が記述された「２０８」となる。このアドレスに対応するグローバル履歴８４の分岐結果（GH）は「０」であり（すなわち、if文の条件（a==b）が偽であり）、変数ｘのインクリメント（x++）は行われずに、次の分岐処理の２１６行目に処理が移行する。従って、このときのターゲットアドレス、すなわち次（実行パス履歴８５の左から３番目）のアドレスは、次の分岐命令が記述された「２１６」である。このアドレスに対応するグローバル履歴８４の分岐結果（GH）は「１」であり（すなわち、if文の条件（a==b）が真であり）、変数ｙがインクリメント（ｙ++）される。その後、処理は２００行目に戻る（実行パス履歴８５においては左から４番目に進む）。
【００６９】
以降も同様にして各命令が実行され、２００行目のfor文の条件（i<2）が偽となるまでfor文のループ内の命令（２０８行目および２１６行目の分岐命令）が繰り返し実行される。
【００７０】
そして、実行パス履歴８５の最新の（一番右の）アドレスで指定された２００行目のfor文の予測において、分岐結果が「１」（グローバル履歴８４の一番右の分岐結果（GH））であること、すなわち、２００行目のfor文のループが終了されたと予測されたことが示されている。この場合、２２４行目のif文にジャンプすることになるので、このときのターゲットアドレス（TA）の値は、図３に示されるように「２２４」となる。
【００７１】
なお、ローカル履歴８６の各分岐結果（LH）は、グローバル履歴に示される分岐結果が、分岐命令毎に（行番号毎に）整理されている。
【００７２】
図２に戻り、多重化アドレス（MA（Multiprex Address）（ｐ））８３は、実行パス履歴８５のアドレス（Ａ［ｐ］）の下位ビットをそのビット長分のローカル履歴８６（分岐結果LHT［ｑ］）に差し替えたものである。MA［ｐ］は、実行パス履歴８５における最新のアドレスから（ｐ＋１）番目のアドレスＡ［ｐ］の下位ビットをローカル履歴８６の分岐結果LHT［ｑ］に差し替えたものを示す。なお、本実施形態においては、多重化アドレス８３のアドレス（MA［ｐ］）は、実行パス履歴８５のアドレス（Ａ［ｐ］）の下位ビットをそのビット長さ分のローカル履歴８６（LHT［ｑ］）に差し替えて生成されるようにしたが、アドレス（Ａ［ｐ］）の下位ビットを削除することなく、アドレス（Ａ［ｐ］）にローカル履歴８６の分岐結果（LHT［ｑ］）を付加させることにより、アドレス（Ａ［ｐ］）にローカル履歴８６の分岐結果（LHT［ｑ］）を反映させるようにしてもよい。
【００７３】
本実施形態において多重化アドレス生成部７４は、例えば図４に示されるように、実行パス履歴８５のアドレス９２の下位２ビットを削除してアドレス（ショート）９３を生成し、そのアドレス（ショート）９３にローカル履歴８６（LHT）から読み出された２ビットの分岐結果（LH）９４を付加したものを多重化アドレス（MA）８３とする。レジスタ４４は、この多重化アドレス８３を記憶しておき、ステージ１における重みテーブル８２からの重みの読み出しや、ステージ０における閾値の読み出しに利用するインデックスの生成に利用している。
【００７４】
このように、本実施形態においては、ローカル履歴８６の分岐結果は直接的に予測演算に使用されることはないが、インデックス生成に利用することで１つのアドレスからローカル履歴長のべき乗通りのインデックスが生成可能になる。一般的に１つの分岐命令が、その時々に応じて分岐方向を変える（分岐方向の両方に分岐する）ことは多いが、実行パス履歴８５のアドレスのみをインデックスとして重みを選択する従来の手法の場合、その分岐命令がいずれの方向に分岐する場合であっても同じ重みが選択されることになっていた（重みの負の衝突が発生した）。
【００７５】
これに対し、図５に示されるように、ローカル履歴８６の分岐結果を実行パス履歴８５のアドレスの下位ビットと差し替えた多重化アドレス（MA）８３を用いて生成したインデックスを使用することにより、重みテーブル８２より選択する重みを、その分岐方向によって変更することができ、重みの負の衝突を回避することができる。これにより、ハードウェアコストの増加を最小限に抑えつつ予測精度の向上を期待することができる。
【００７６】
図２に戻り、重みテーブル８２は、各分岐命令について、過去に当該分岐命令まで辿ったグローバル履歴８４の各分岐結果に対して、事前になされた分岐予測の正否を反映した重み（重み群）が、当該分岐命令のアドレスの下位ビットをローカル履歴に差し替えた多重化アドレス８３を用いて生成されたインデックスと対応付けられて、保持されたものである。WT［ｊ］（１≦ｊ≦ｎ，ｊは整数）は、グローバル履歴８４のｊ番目の分岐結果GHR［ｊ−１］に割り当てられた重み群を、複数の多重化アドレス８３を用いて生成されるインデックスに対応付けるテーブル情報である。つまり、GHR［ｊ−１］には、WT［ｊ］より選択された重みが付加される。
【００７７】
重み付き分岐結果累算値８１は、グローバル履歴の各分岐結果に重み付けを行った重み付き分岐結果値を、各ステージにおいて鎖毎に順次累算した値である。REG［ｒ］は、ｒ（１≦ｒ≦ｎ，ｒは整数）個の重み付き分岐結果値の累算値であり、レジスタ４４に保持される時点での値である。詳細については後述するが、重み付き分岐結果の累算は、ステージ１において行うようにしてもよいし、ステージ０において行うようにしてもよいし、ステージ１およびステージ０の両方で行うようにしてもよい。ここでは、ステージ１においてｒ個の重み付き分岐結果値を累算する（残りの累算はステージ０において行う）ものとする。
【００７８】
通常間隔インデックス８７は、複数の多重化アドレス８３を用いて生成された、重みテーブル８２に対して使用される、重み選択用のインデックスである。通常間隔インデックス８７は、互いの分岐命令の距離が比較的短い複数の多重化アドレス８３と最新のアドレスＡ［０］の排他的論理和により生成される。
【００７９】
長間隔インデックス８８も同様に、複数の多重化アドレス８３を用いて生成された、重みテーブル８２に対して使用される、重み選択用のインデックスである。ただし、長間隔インデックス８８は、互いの分岐命令の距離が比較的長い複数の多重化アドレス８３と最新のアドレスＡ［０］の排他的論理和により生成される。
【００８０】
ここでこれらのインデックスについて図６乃至図９を参照して説明する。
【００８１】
グローバル履歴８４の分岐結果は、予測すべき分岐命令であるbranch Bに近いほどbranch Bとの関連が高いことは明らかであるので、グローバル履歴８４の、branch Bと近いものから順に所定の数の分岐結果に対して重み付けが行われる。パーセプトロン分岐予測器において、重み付けを行うグローバル履歴８４の長さ（履歴長）は、基本的に長いほど予測精度が向上する。つまり、使用する重みテーブル８２の数が多いほど、予測計算に使用される重みの数が増えるので予測精度は向上する。
【００８２】
しかしながら、使用する重みテーブルの数が増加すると、ハードウェアコストや計算レイテンシが上昇する。また、仮に、全体の記憶容量を一定とすれば、重みテーブル８２の数が増大することにより、各テーブルのエントリ数は相対的に少なくなる。エントリ数の不足は使用する重みの衝突を引き起こし予測精度低下の主因となりうるので、テーブル数を削減することは、実装コストと計算レイテンシの低減を実現するだけでなく、重みの負の衝突の回避にも寄与する。
【００８３】
しかしながら、テーブル数を削減するためには、使用するグローバル履歴８４の履歴長も短くする必要があるが、単純に履歴長を短くすると、その分、予測精度が低下してしまう。予測精度の向上を実現するためには、従来法と同程度の履歴情報を予測に反映させる必要がある。つまり、従来とは別の形で履歴情報を予測に反映させる必要がある。
【００８４】
そこで、本実施の形態においては、予測結果の履歴情報を、重み付けを行うグローバル履歴８４としてではなく、重み選択に使用するインデックスに反映させるようにする。つまり、例えば、従来のA3PBPにおいては、実行パス履歴８５を、重み読み出しのインデックス生成に使用していたが、本実施の形態においては、テーブル数を削減して１テーブルあたりのエントリ数を増やすために、インデックス生成に複数の多重化アドレスを用いることにより、A3PBPで使用した実行パス履歴情報よりも詳細な情報を重み読み出しのインデックスに反映させるようにする。
【００８５】
図６は、ｉ番目のテーブルであるTableiが使用するインデックス生成関数index［ｉ］の例を、そのインデックス生成に使用されるアドレスの種類数毎に示す表である。図６に示される表において、index［ｉ］は、テーブルによって使用する多重化アドレス８３（MA）の組み合わせを変えるために、実行パス履歴上のｐ個（ｐ＝１，・・・，５）の多重化アドレス（MA［c1i−ｎ］，・・・，MA［cpi−ｎ］）を用いて生成されるようになされている。
【００８６】
実行パス履歴情報を予測に反映させるためにp個の多重化アドレス８３（MA）は、テーブル間で極力重複しないように選択する必要がある。そのため、係数c1＝１，１＜c2＜・・・＜cpは素数とされている。なお、p＝１の場合、A3PBPのインデックス生成関数と同等となる。
【００８７】
また、これらの素数を調整し、branch Bから遠くなるにつれて使用する多重化アドレス８３（MA）の間隔が徐々に開くようにすることで、branch Bと強い相関を持つ近距離の分岐履歴に重点を置きつつ、予測が遠距離の特定の区間の履歴に強く依存することを極力避けるようにすることができる。
【００８８】
このように、実行パス履歴８５のより詳細な情報を重み読み出しのインデックスに反映させることにより、１テーブルあたりのエントリ数を増やすことができるため、予測精度を向上させることができるが、過剰に詳細なパス情報の利用は重みの負の衝突を誘発し、予測精度が低下する恐れがある。すなわち、インデックス生成に使用するアドレスの種類数には最適値が存在することが予想される。
【００８９】
そこで、この最適値を実験により求めた。実験はSPEC INT2000の12種類のベンチマークをSimCoreシミュレータで１億命令程度実行した際にトレースしたデータを用いた。このデータを８本鎖２段パイプラインのA3PBPをシミュレートしたプログラムで処理し、重み読み出しのインデックス生成に使用する多重化アドレスの数と予測精度の関係を測定した。ステージ０のテーブルを除いたテーブルの個数は８個である．記憶容量は総計32Kバイトとした。
【００９０】
その実験結果のグラフを図７に示す。図７に示されるグラフは、インデックス生成に使用した多重化アドレス８３の種類数と、そのインデックスを用いて選択した重みによりグローバル履歴８４に対して重み付けを行い、分岐予測を行ったときの予測ミス率との関係を示しており、横軸は使用した多重化アドレス８３の種類を示し、縦軸はそのときの予測ミス率（％）を示している。曲線１５１は、重み選択に用いられる重みテーブル８２のエントリ数が２Ｋであるときの関係を示しており、曲線１５２は、その重みテーブル８２のエントリ数が４Ｋであるときの関係を示しており、曲線１５３は、その重みテーブル８２のエントリ数が８Ｋであるときの関係を示しており、曲線１５４は、その重みテーブル８２のエントリ数が１６Ｋであるときの関係を示している。
【００９１】
このグラフにおいて、曲線１５１乃至曲線１５４の各曲線の形状から、エントリ数に関わらず、使用する多重化アドレス８３の種類が少ないと予測ミス率が下がらない、つまり効率的に重みテーブル８２を使用することができないことが分かる。逆に過剰に多重化アドレス８３の種類を増やすと予測ミス率が上昇してしまうことも分かる。さらに、曲線１５１乃至曲線１５４の互いの関係から、インデックス生成に使用する最適な多重化アドレス８３の種類数は重みテーブル８２のエントリ数と関係がある、つまりエントリ数が多いほど予測ミス率を低減させることができることが分かる。また、エントリ数が増えるに従って、より詳細なパス情報を使用することによって予測精度が向上することもわかる。例えば、エントリ数が２Ｋ乃至８Ｋの場合、最も予測ミス率が低くなる、最適な多重化アドレス８３の種類が４であるのに対し、エントリ数が１６Ｋの場合には、最適な多重化アドレス８３の種類は５となっている。
【００９２】
以上のように、効率的なインデックス生成に必要な多重化アドレス８３の種類数はエントリ数に応じて４種類から５種類程度であるということが分かる。しかしながら、図６に示される方法でインデックスを生成する場合、従来法よりも短い履歴しか使用することができない。
【００９３】
例えば４種類の多重化アドレス８３を用いてインデックス生成を行う場合、使用される多重化アドレス８３のうち、予測すべき分岐命令branch Bから最も遠い分岐命令の多重化アドレスは、MA［５i−１］である。ｉ＝８とすると、このアドレスはMA[39]（branch Bよりも40個前に処理された分岐命令の多重化アドレス）となり、従来法で使用する履歴長の半分程度となる。
【００９４】
O-GEHL branch predictorで知られているように、予測精度の向上のためには長いグローバル履歴を用いることが必要であるが、従来法ではグローバル履歴中の１つの分岐結果は１つの重みテーブルに対応するので、テーブル数を削減すると利用できるグローバル履歴８４の履歴数も削減することになる。つまり、図６に示される方法でインデックスを作成することにより、予測精度が低下してしまう恐れがある。そこで、少ないテーブル数の下で長い実行パス履歴８５と長いグローバル履歴８４を利用することができるようにすることが求められる。
【００９５】
より長い実行パス履歴８５を利用するために、図６に示される重みテーブルのインデックス生成法に加え、より過去の多重化アドレス８３を用いるインデックス生成法も併用するようにする。一般に、予測すべき分岐命令branch Bに近い履歴ほど分岐結果と強い相関を持っている。そこで、予測精度を向上させるために、予測すべき分岐命令branch Bに近い、近距離の履歴に重点を置くとともに、履歴長が短くならないように、予測すべき分岐命令branch Bから遠い、遠距離の履歴も満遍なく利用する。例えば、ｉの係数c1，・・・，cpは、予測器全体で使用する多重化アドレス８３の間隔が、branch Bから遠くなるにしたがい徐々に開くように値を選択する。
【００９６】
例えば、４種類のアドレスを使用する場合(p＝３)、図６に示される以下の式（４）を用いて生成されるインデックスを用いて重み選択を行う重みテーブル１乃至重みテーブル４と、以下の式（５）を用いて生成されるインデックスを用いて重み選択を行う重みテーブル５乃至重みテーブル７を用意する。
【００９７】
【数４】
0005283054.tif 000005
【数５】
0005283054.tif 000006
【００９８】
式（４）と式（５）を比較して分かるように、使用される多重化アドレス８３の、互いの距離（命令間距離）は、式（５）の方法の場合よりも式（４）の方法の場合の方が長い。図２に示される通常間隔インデックス８７は、式（４）の方法により生成されるインデックス（NDI：NomalDistance Index）であり、図２に示される長間隔インデックス８８は、式（５）の方法により生成されるインデックス（LDI：Long Distance Index）である。
【００９９】
このときの、インデックス生成に使用される多重化アドレス８３の分布の例を図８に示す。図８に示される表は、各重みテーブル（重みテーブル１乃至重みテーブル７）のインデックス生成に使用される多重化アドレス８３の分布を示すものであり、一番上の行の数字は、予測すべき分岐命令branch Bからの命令間距離を示しており、２行目以降のアスタリスク（＊）は、その行のテーブルに対するインデックスの生成に、その列の分岐命令の多重化アドレスを用いることを示している。例えば、上から２行目の重みテーブル１のインデックス生成には、予測すべき分岐命令branch Bからの命令間距離が「１」、「３」、および「５」の３つの多重化アドレス８３が使用される。
【０１００】
なお、表の一番下の行（ALL）は、各テーブル（重みテーブル１乃至重みテーブル７）のインデックス生成に用いられる全ての多重化アドレスの分布を示している。また、図８において下の表は、上の表に続く表である。上の表では、命令間距離が「１」乃至「２５」の範囲における多重化アドレス８３の分布を示しており、下の表では、命令間距離が「２６」乃至「５０」の範囲における多重化アドレス８３の分布を示している。
【０１０１】
図８の表に示されるように、ｉの値が小さい重みテーブル８２、つまり、グローバル履歴８４の分岐結果のうち、予測すべき分岐命令branch Bに近い方から順に所定の数の分岐結果のそれぞれに割り当てられた重みテーブル８２については、NDIをインデックスとして用いるようにし、branch Bから遠い、残りの分岐結果にそれぞれ割り当てられた重みテーブル８２については、LDIをインデックスとして用いるようにしている。図８の例の場合、重みテーブル１乃至重みテーブル４では、式（４）を用いて生成されたインデックスNDIにより重み選択が行われ、重みテーブル５乃至重みテーブル７では、式（５）を用いて生成されたインデックスLDIにより重み選択が行われる。
【０１０２】
従って、重みテーブル１乃至重みテーブル４のインデックス生成には、branch Bからの命令間距離が「２０」よりも近い多重化アドレスのみが使用されているが、重みテーブル５乃至重みテーブル７のインデックス生成には、それ以上の命令間距離の多重化アドレスも使用されている。例えば、重みテーブル７のインデックス生成には、branch Bからの命令間距離が「４９」の多重化アドレスも使用されている。
【０１０３】
このように、グローバル履歴８４の各分岐結果に割り当てられる重みテーブルによって、そのインデックス生成に用いられる多重化アドレスの、予測すべき分岐命令branch Bからの命令間距離を変えるようにしている。より具体的には、グローバル履歴８４の、branch Bからの命令間距離が近い分岐結果に割り当てられる重みテーブルほど、branch Bからの命令間距離がより短い多重化アドレスを用いてインデックスが生成されるようにしている。
【０１０４】
また、グローバル履歴８４の、branch Bからの命令間距離が所定の距離より遠い分岐結果に割り当てられる重みテーブルは、互いの命令間距離が比較的長い多重化アドレスの組みを用いて生成されるLDIをインデックスとし、branch Bからの命令間距離が比較的遠い多重化アドレスもインデックス生成に使用するようにしている。
【０１０５】
さらに、重みテーブル全体においては、branch Bに近い多重化アドレス程多くインデックス生成に使用するようになされている。
【０１０６】
このようにインデックス生成に使用する多重化アドレスを選択することにより、予測精度を低減させずに、より長い実行パス履歴を使用することができるようにし、実行パス履歴を長くすることによる予測精度向上を実現することができる。
【０１０７】
また、多重化アドレス８３へ分岐結果を付加することにより多重化アドレスの列（すなわち実行パス履歴）にグローバル履歴情報を付加するようにする。具体的には、予測すべき分岐命令であるbranch Bから生成された多重化アドレス８３に含まれるローカル履歴８６の部分のうち、最も過去の履歴ビットをbranch Bの分岐方向が確定した際にその分岐結果で置換することにより多重化アドレス８３を更新するようにする。これは分岐方向が確定し更新が完了したローカル履歴８６で多重化アドレス８３を生成するのと等価である。
【０１０８】
図９は、ローカル履歴が１ビットの場合、（A3PBPのように）更新を行わない場合と、更新を行う場合の多重化アドレスを比較する図である。図９Ａに示される表の上の行は、実行パス履歴を示しており、「Ａ」、「Ｂ」、「Ｃ」、および「Ｄ」は、分岐命令のアドレスを模式的に示したものである。同じ文字は同じアドレス（つまり同一の分岐命令）を示している。また、図９Ａに示される表において、下の行は、各分岐命令における分岐結果、すなわちグローバル履歴を示しており、「Ｘ1」、「Ｘ2」、「Ｘ3」、「Ｘ4」、「Ｘ5」、「Ｘ6」、「Ｘ7」、および「Ｘ8」は、それぞれの分岐方向を示している。つまり、これらの値は、「１」か「−１」のいずれか一方である。なお、図９Ａに示される表において、横方向は、branch Bからの命令間距離を示しており、左に行くほどbranch Bに近く、右に行くほどbranch Bより遠くなる。
【０１０９】
図９Ｂは、図９Ａに示される実行パス履歴およびグローバル履歴より生成された多重化アドレスの、分岐方向確定後に更新を行わない場合の例を示している。各行は生成された多重化アドレスの構成（使用された実行パス履歴およびグローバル履歴）を示している。また、縦方向は、branch Bからの命令間距離を示しており、上に行くほどbranch Bに近く、下に行くほどbranch Bより遠くなる。
【０１１０】
図９Ｂの場合、「Ａ」乃至「Ｄ」の各実行パス履歴には、その時点で確定している前回の分岐結果が付加される。従って、ｉ＝４における実行パス履歴「Ａ」に対しては、その１つ前の「Ａ」の分岐結果、すなわち、ｉ＝８における分岐結果「Ｘ8」が付加されている。同様に、ｉ＝３における実行パス履歴「Ｄ」に対しては、ｉ＝６における分岐結果「Ｘ6」が付加され、ｉ＝２における実行パス履歴「Ｂ」に対しては、ｉ＝５における分岐結果「Ｘ5」が付加され、ｉ＝１における実行パス履歴「Ｃ」に対しては、ｉ＝７における分岐結果「Ｘ7」が付加されている。
【０１１１】
これに対して、図９Ｃは、図９Ａに示される実行パス履歴およびグローバル履歴より生成された多重化アドレスの、分岐方向確定後に更新を行う場合の例を示している。図９Ｃの見方は、図９Ｂと基本的に同様である。
【０１１２】
図９Ｃに示されるように、更新の結果、「Ａ」乃至「Ｄ」の各実行パス履歴には、最新の分岐結果が付加される。従って、ｉ＝４における実行パス履歴「Ａ」に対しては、ｉ＝４における分岐結果「Ｘ4」が付加され、ｉ＝３における実行パス履歴「Ｄ」に対しては、ｉ＝３における分岐結果「Ｘ3」が付加され、ｉ＝２における実行パス履歴「Ｂ」に対しては、ｉ＝２における分岐結果「Ｘ2」が付加され、ｉ＝１における実行パス履歴「Ｃ」に対しては、ｉ＝１における分岐結果「Ｘ1」が付加されている。つまり、更新を行う場合、多重化アドレス８３には、その多重化アドレス８３に含まれる実行パス履歴８５のアドレスに対応するグローバル履歴８４の分岐結果が含まれる。
【０１１３】
なお、実際の回路において、このような更新処理は信号線を繋ぎ替えるだけで容易に実現することができ、また、予測処理とは独立した他の処理として行うことができるので、予測に必要なレイテンシに変化はない。
【０１１４】
以上のように、多重化アドレスにグローバル履歴情報を含めるようにし、テーブルのインデックスとして使用される多重化アドレスの命令間間隔はbranch Bから遠くなるにつれて徐々に開くように設定する。このようにすることにより多重化アドレスに含まれているグローバル履歴の分岐結果もまたbranch Bから遠くなるにつれて間隔が徐々に開いていくことになるので、使用する履歴に偏りが生じない。このようにして長いグローバル履歴を利用する。
【０１１５】
図２に戻り、レジスタ４４には、以上のような各種のパラメータが必要に応じて保持される。
【０１１６】
図２の予測処理部４１は、このようなレジスタ４４に保持されるデータやパラメータ等を用いて、分岐命令の予測処理を行う。予測処理部４１は、グローバル履歴の分岐結果に重み付けを行うステージ１の処理を行うステージ１処理部５１、および、重み付けされた分岐結果と閾値から、branch Bの予測を行うステージ０の処理を行うステージ０処理部５２を有している。
【０１１７】
ステージ１処理部５１は、ステージ１において、重みテーブル８２（WT［ｊ］）から重みを選択する重み選択部６１、その選択された重みをグローバル履歴８４の分岐結果に乗算することにより、重み付き分岐結果値を算出する重み付き分岐結果値算出部６２、および、重み付けされた重み付き分岐結果値を累算する重み付き分岐結果値累算部６３を有する。
【０１１８】
重み選択部６１は、ステージ１において、グローバル履歴８４の各分岐結果に割り当てられた重みテーブル８２（WT［ｊ］）から、通常間隔インデックス８７（NDI［ｊ］）または長間隔インデックス８８（LDI［ｊ］）に対応する重みをそれぞれ選択して読み出す。重み付き分岐結果値算出部６２は、ステージ１において、重み選択部６１に選択された各重みを、それぞれに対応するグローバル履歴８４の分岐結果に乗算することにより、分岐結果の重み付けを行い、重み付き分岐結果値を算出する。グローバル履歴８４の分岐結果の値は「１」または「−１」であるので、より具体的には、重み付き分岐結果値算出部６２は、グローバル履歴８４の分岐結果の値に応じて、重み選択部６１に選択された各重みの符号を決定する。例えば、重み選択部６１に選択された重みが「W」とすると、重み付き分岐結果値算出部６２は、グローバル履歴８４の分岐結果が「１」である場合、「W」を重み付き分岐結果値とし、グローバル履歴８４の分岐結果が「−１」である場合、「−W」を重み付き分岐結果値とする。
【０１１９】
重み付き分岐結果値累算部６３は、重み付き分岐結果値算出部６２により算出された各重み付き分岐結果値を累算する。上述したように、ステージ１においては、重み付き分岐結果値累算部６３は、重み付き分岐結果値の累算をｒ個まで行う。残りの累算はステージ０において行う。重み付き分岐結果値累算部６３は、算出した重み付き分岐結果累算値８１をレジスタ４４に保持させる。このレジスタ４４に保持された重み付き分岐結果累算値８１は、次の分岐命令に対して実行されるステージ０の処理に利用される。
【０１２０】
ステージ０処理部５２は、ステージ０において、重み付き分岐結果値累算部６３が行う重み付き分岐結果値の累算の続きを行う重み付き分岐結果値累算部７１、分岐成立または不成立を識別するための閾値を算出する閾値算出部７２、および、重み付き分岐結果値累算部７１により算出された重み付き分岐結果累算値と、閾値算出部７２により算出された閾値とに基づいて、予測すべき分岐命令branch Bの分岐結果の予測値を算出する予測値算出部７３を有する。
【０１２１】
重み付き分岐結果値累算部７１は、基本的に重み付き分岐結果値累算部６３と同様の処理を行う。つまり、重み付き分岐結果値累算部６３と重み付き分岐結果値累算部７１の両方の処理により、重み付き分岐結果値算出部６２により算出された重み付き分岐結果値が所定の数まで累算される。
【０１２２】
なお、この重み付き分岐結果値累算部６３と重み付き分岐結果値累算部７１との間の処理の分配方法は任意である。例えば、重み付き分岐結果値累算部６３が、重み付き分岐結果値Ａ乃至Ｃを累算してＡ＋Ｂ＋Ｃを算出し、重み付き分岐結果値累算部７１が、その累算値Ａ＋Ｂ＋Ｃに対して、他の重み付き分岐結果値ＤやＥをそれぞれ累算するようにしてもよいし、重み付き分岐結果値累算部６３がＡ＋Ｂを算出し、重み付き分岐結果値累算部７１が、その累算値Ａ＋Ｂに対して、他の重み付き分岐結果値ＣやＤやＥをそれぞれ累算するようにしてもよい。
【０１２３】
また、例えば、重み付き分岐結果値累算部６３が、重み付き分岐結果値Ａ乃至Ｆを累算して累算値Ａ＋Ｂ，Ｃ＋Ｄ、およびＥ＋Ｆを算出し、重み付き分岐結果値累算部７１が、その累算値Ａ＋Ｂと累算値Ｃ＋Ｄを累算して累算値Ａ＋Ｂ＋Ｃ＋Ｄを算出するようにしてもよいし、重み付き分岐結果値累算部６３が累算値Ａ＋Ｂ＋Ｃと累算値Ｄ＋Ｅを算出し、重み付き分岐結果値累算部７１が、その累算値Ｄ＋Ｅに重み付き分岐結果値Ｆを累算するようにしてもよい。
【０１２４】
もちろん、このような重み付き分岐結果値の累算を全て重み付き分岐結果値累算部６３により（ステージ１において）行うようにしてもよい。その場合、重み付き分岐結果値累算部７１は省略可能である。逆に、重み付き分岐結果値の累算を全て重み付き分岐結果値累算部７１により（ステージ０において）行うようにし、重み付き分岐結果値累算部６３を省略するようにしてもよい。
【０１２５】
閾値算出部７２は、上述した重み付き分岐結果値累算部７１による累算と並行して、ステージ０に割り当てられた重みテーブル８２から、最新のアドレスＡ［０］（ステージ０においてはターゲットアドレス）における多重化アドレスを生成する際にローカル履歴に差し替えらる下位ビットを除く上位ビットをインデックスとして、特定される複数の閾値を候補として全て選定する。閾値の候補数は、多重化アドレスを生成する際にローカル履歴に差し替えらる下位ビットの数のべき乗であり、例えば、ローカル履歴に差し替えらるビット数が２である場合は、閾値の候補数は４となる。また、閾値算出部７２は、最新のアドレスＡ［０］をインデックスとしてローカル履歴８６のテーブルより分岐結果を読み出して、複数の閾値候補の重みの中から１つを選択することにより、閾値を算出する。なお、このように最新のアドレスＡ〔０〕の上位ビットで特定した閾値の候補からローカル履歴で１つを選択することによって、結果として多重化アドレスを用いて閾値を算出したことになる。
【０１２６】
予測値算出部７３は、重み付き分岐結果値累算部７１により算出された重み付き分岐結果累算値と、閾値算出部７２により算出された閾値とを加算することによって予測値を算出する。
【０１２７】
多重化アドレス生成部７４は、例えば、実行パス履歴８５のアドレス（処理時はターゲットアドレス）の下位４ビットを、ローカル履歴８６に含まれる最新から４つ分の分岐結果に差し替えて多重化アドレス（MA）を生成する。
【０１２８】
学習処理部４２は、予測値算出部７３において算出された予測値と、演算部２４における実際の演算結果（分岐結果）に基づいて、重みテーブル８２の各重みについての学習処理を行う。
【０１２９】
更新処理部４３は、新たなターゲットアドレス、演算結果（分岐結果）が確定した後、実行パス履歴８５、グローバル履歴８４、ローカル履歴８６を随時更新する処理を行う。なお、更新処理部４３は、予測値が算出される毎にグローバル履歴８４を暫定的に更新し、演算結果が算出された後に、予測値を演算結果が異なる場合は、演算結果に書き換えるようになっている。また、更新処理部４３は、新たなターゲットアドレスとローカル履歴８６とにより多重化アドレス８３が生成された後、予測すべき分岐命令の分岐結果が確定すると、その確定した分岐結果を用いて多重化アドレスを更新する。
【０１３０】
図１０は、予測処理部４１により実行される予測処理のパイプライン構造の構成例を模式的に示す図である。上述したように、予測処理はステージ０とステージ１の２つのステージにより構成される。従って、従来のパーセプトロン分岐予測器と比べてパイプラインの段数は少ない。
【０１３１】
グローバル履歴８４の各分岐結果に対して重み付けが行われるステージ１においては、各分岐結果に乗算する重みを選択する重みテーブル８２が設けられている。図１０においては、ｎ個（ｎは自然数）の分岐結果（分岐結果８４−０（GHR［０］）乃至分岐結果８４−（ｎ−１）（GHR［ｎ−１］））に対して重み付けを行うものとし、重みテーブル８２もｎ個用意されている（重みテーブル８２−１乃至重みテーブル８２−ｎ）。
【０１３２】
これらの重みテーブル８２のうち、予測すべき分岐命令branch Bに近い方からI個分の分岐結果に対応する重みテーブル８２−１乃至重みテーブル８２−Iは、NDI［ｊ］がインデックスとされ、残りの重みテーブル８２−（I＋１）乃至重みテーブル８２−ｎは、LDI［ｊ］がインデックスとされる。
【０１３３】
まず、予測すべき分岐命令branch Bから１つ目のグローバル履歴８４の分岐結果８４−０（GHR［０］）に対応する部分について説明する。この分岐結果８４−０に対しては重みテーブル８２−１、インバータ１０１−１、およびセレクタ１０２−１が設けられている。NDI［１］をインデックスとして重みテーブル８２−１より読み出された重みは、インバータ１０１−１およびセレクタ１０２−１の一方の入力端子に供給される。インバータ１０１−１は、重みテーブル８２−１より読み出された重みの符号を反転させてセレクタ１０２−１の他方の入力端子に供給する。セレクタ１０２−１は、GHR［０］の値に基づいて、GHR［０］の値の符号が正であるなら、重みテーブル８２−１より読み出された重みを重み付き分岐結果値としてCSA（Carry Save Adder） tree１０３に供給し、GHR［０］の値の符号が負であるなら、インバータ１０１−１より供給された重みを重み付き分岐結果値としてCSA tree１０３に供給する。
【０１３４】
他の分岐結果についても基本的に同様の構成が設けられ、同様の処理が行われる。すなわち、CSA tree１０３には、ｎ個の重み付き分岐結果値が供給される。ただし、branch BからＩ個目までの分岐結果に対応する重みテーブル８２においては、NDIをインデックスとして使用し、（Ｉ＋１）個目より後の分岐結果に対応する重みテーブル８２においては、LDIをインデックスとして使用する。
【０１３５】
CSAは桁上げ保存加算器である。CSA tree１０３は、その桁上げ保存加算器の木構造、すなわち累算器であり、入力されたｎ個の重み付き分岐結果値を所定の数（ｒ個）に減らすまで累算し、得られた重み付き分岐結果累算値８１（REG［ｒ］）をレジスタ４４に保持させる。
【０１３６】
以上がステージ１の処理の構成である。
【０１３７】
分岐の予測が行われるステージ０においては、桁上げ保存加算器の木構造（すなわち累算器）であり、レジスタ４４に蓄積された重み付き分岐結果累算値８１をさらに累算するCSA tree１１１、重みテーブル８２−０より選択された重み群の中から、LHT８６より選択された分岐結果に基づいて閾値を選択するセレクタ１１２、重み付き分岐結果値の累算値の途中結果とセレクタ１１２により選択された閾値とを加算する桁上げ保存加算器であるCSA１１３、および、CSA１１３の出力を全て加算する桁上げ伝播加算器であるCPA（carry propagation adder）１１４が設けられている。
【０１３８】
重みテーブル８２−０からは、branch B のアドレスＡ［０］を用いて重みの候補が読み出される。セレクタ１１２は、この中からローカル履歴８６の分岐結果の値によって予測に使用する重みを選択する。そのローカル履歴８６の分岐結果はbranch BのアドレスＡ［０］を用いてLHT８６から読み出される。この処理と並行して、CSA tree１１１は、ステージ１において行われた重み付き分岐結果値の累算の続きを行う。CSA１１３およびCPA１１４により、重み付き分岐結果値の累算の途中結果と、セレクタ１１２に選択されたバイアスの重み（閾値）が加算され、その結果が正であれば分岐成立と予測され、負であれば分岐不成立と予測される。学習は従来のパーセプトロン分岐予測器と同様の方法で行われる。
【０１３９】
次に、分岐予測処理の全体の流れについて、図１１のフローチャートを参照して説明する。
【０１４０】
予測処理部４１のステージ１処理部５１（図２）は、ステップＳ１において、分岐命令が命令キャッシュ３１（図１）に入力されたか否かを判定し、入力されていないと判定した場合、ステップＳ２に処理を進め、分岐予測パイプラインとしての処理をストール（破棄）させ、処理をステップＳ１に戻す。すなわち、ステージ１処理部５１は、ステップＳ１において、分岐命令が入力されたと判定するまで、ステップＳ２の処理を繰り返しながら待機する。
【０１４１】
ステップＳ１において、分岐命令が入力されたと判定した場合、ステージ１処理部５１は、処理をステップＳ３に進める。ステップＳ３において、ステージ１処理部５１は、図１０に示されるステージ１について、重み付き分岐結果累算値８１（REG［ｒ］）を求めるステージ１処理を実行する。ステップＳ３の処理を終了すると、ステージ１処理部５１は、処理をステップＳ４に進める。
【０１４２】
ステップＳ４において、ステージ０処理部５２は、予測すべき分岐命令が命令キャッシュ３１に入力されたか否かを判定し、入力されたと判定するまで、ステップＳ５において分岐予測パイプラインとしての処理をストールさせながら待機する。
【０１４３】
ステップＳ４において、予測すべき分岐命令が入力されたと判定した場合、ステージ０処理部５２は、処理をステップＳ６に進め、図１０に示されるステージ０について、予測を行うステージ０処理を実行する。また、そのステップＳ６と並行して、ステップ７において、多重化アドレス生成部７４は、入力された分岐命令のアドレスすなわちターゲットアドレスとローカル履歴とにより新たな多重化アドレスを生成する。ステップＳ６およびステップＳ７の処理が終了されると、処理はステップＳ８に進む。
【０１４４】
ステップＳ８において、更新処理部４３は、レジスタの各値を更新する。ステップＳ８の処理が終了されると、処理が終了される。なお、この分岐予測処理とは独立して、別途演算部２４により実際に演算された分岐結果に基づいて、グローバル履歴８４、ローカル履歴８６、および多重化アドレス８３が更新される。また、分岐結果に基づいて学習処理部４２により学習処理がなされた重みにより重みテーブル８２が更新される。
【０１４５】
このように、本実施の形態の分岐予測処理においては、ステージ１において重み付き分岐結果累算値が算出され、ステージ０においてその重み付き分岐結果累算値を用いて予測処理が行われる。ただし、実際には、各分岐命令に対して予測値を出力する必要があるので、上述した各ステージの処理は並行して行われる。つまり、ステージ０の処理は、前回分岐命令が入力された際に行われたステージ１の処理結果を利用して行われる。換言すれば、ステージ１の処理は、次に入力される分岐命令に対する予測のために実行される。
【０１４６】
次に、ステージ０処理の流れの例を図１２のフローチャートを参照して説明する。
【０１４７】
ステージ０処理が開始されると、重み付き分岐結果値累算部７１は、ステップＳ２１において、レジスタ４４に保持されている重み付き分岐結果累算値８１（REG［ｊ］）を全て読み出し、CSA tree１１１を用いて累算の続きを行い、それらの総和を途中まで算出する。この処理と並行して、閾値算出部７２は、ステップＳ２２において、実行パス履歴８５の最新のアドレスＡ［０］をインデックスとしてローカル履歴８６より分岐結果（LHT（Ａ［０］））を読み出す。また、閾値算出部７２は、そのステップＳ２２の処理と並行して、さらに、ステップＳ２３の処理を行い、実行パス履歴８５の最新のアドレスＡ［０］の所定ビット数の上位ビットをインデックスとして、閾値用の重みテーブル８２−０より、そのインデックスに対応する閾値の候補（WT［０］（Ａ［０］））を全て取得する。
【０１４８】
ステップＳ２２およびステップＳ２３の処理を終了すると、閾値算出部７２は、ステップＳ２４において、セレクタ１１２により、ローカル履歴８６より読み出した分岐結果に基づいて、重みテーブル８２−０より選択された閾値の候補の中から閾値として採用するものを選択する。
【０１４９】
ステップＳ２１およびステップＳ２４の処理が終了すると、予測値算出部７３は、ステップＳ２５において、CSA１１３およびCPA１１４を用いて重み付き分岐結果累算値の総和と閾値を加算し、ステップＳ２６において、加算結果の最上位ビットの値を反転させ、ステップＳ２７において、その反転結果（最上位ビット）を予測値として出力する。
【０１５０】
次に、図１３のフローチャートを参照して、ステージ１処理の流れの例を説明する。
【０１５１】
ステージ１処理部５１の重み選択部６１は、ステップＳ４１において、予測すべき分岐命令branch Bからの命令間距離を示す変数ｊの値を「１」に設定する。ステップＳ４２において、重み選択部６１は、その変数ｊの値が「Ｉ」以下であるか否かを判定する。つまり、重み選択部６１は、今回重み付けを行うグローバル履歴８４の分岐結果の、branch Bからの命令間距離がＩよりも短いか否か（つまり、branch Bに比較的近い分岐命令の分岐結果であるか否か）を判定する。
【０１５２】
変数ｊの値が「Ｉ」以下であると判定された場合、重み選択部６１は、処理をステップＳ４３に進め、重み付き分岐結果値算出部６２とともに、NDIをインデックスとして使用して重みを選択し、選択した重みを分岐結果に乗算するNDI使用重み読み出し処理を行う。NDI使用重み読み出し処理の詳細については後述する。NDI使用重み読み出し処理が終了すると、重み選択部６１は、処理をステップＳ４５に進める。
【０１５３】
また、ステップＳ４２において、変数ｊの値が「Ｉ」より大きいと判定された場合、重み選択部６１は、処理をステップＳ４４に進め、重み付き分岐結果値算出部６２とともに、LDIをインデックスとして使用して重みを選択し、選択した重みを分岐結果に乗算するLDI使用重み読み出し処理を行う。LDI使用重み読み出し処理の詳細については後述する。LDI使用重み読み出し処理が終了すると、重み選択部６１は、処理をステップＳ４５に進める。
【０１５４】
ステップＳ４５において、重み選択部６１は、変数ｊの値を「１」インクリメントし、重み付けの処理対象を次の分岐結果に切り返る。ステップＳ４６において、重み選択部６１は、変数ｊの値が任意の自然数ｎより大きいか否かを判定し、変数ｊの値がｎより大きくなく、ｊ番目の重みテーブル８２（WT［ｊ］）が存在すると判定した場合、処理をステップＳ４２に戻し、それ以降の処理を繰り返す。つまり、重み選択部６１は、ステップＳ４２乃至ステップＳ４６の処理を繰り返し実行することにより、予測処理に利用されるグローバル履歴８４の全ての分岐結果に対して重み付けを行う。そして、ステップＳ４６において変数ｊの値がｎより大きく、処理対象とする全ての分岐結果に対して重み付けを行ったと判定した場合、重み選択部６１は、処理をステップＳ４７に進める。
【０１５５】
重み付き分岐結果値累算部６３は、ステップＳ４７において、以上のようにして算出された各重み付き分岐結果値を累算し、ステップＳ４８において、算出された重み付き分岐結果累算値の途中結果であるREG［ｒ］をレジスタ４４に保持させる。
【０１５６】
ステップＳ４８の処理が終了されるとステージ１処理は終了される。
【０１５７】
次に、図１３のステップＳ４３において実行されるNDI使用重み読み出し処理の詳細な流れの例を、図１４のフローチャートを参照して説明する。
【０１５８】
ステップＳ６１において、重み選択部６１は、入力された最新のアドレスＡ［０］および多重化アドレスを用いてNDI［ｊ］を生成する。ステップＳ６２において、重み選択部６１は、そのNDI［ｊ］をインデックスとしてWT［ｊ］（WT［ｊ］（NDI［ｊ］）より重みを取得する。ステップＳ６３において、重み付き分岐結果値算出部６２は、グローバル履歴８４の分岐結果GHR［ｊ−１］の値が「１」であるか否かを判定し、「１」であると判定した場合、WT［ｊ］より読み出した重みを重み付き分岐結果値とし、NDI使用重み読み出し処理を終了する。つまり、重み付き分岐結果値算出部６２は、この場合、セレクタ１０２−ｊを制御して、WT［ｊ］より選択された重みがそのままCSA tree１０３に出力されるようにする。
【０１５９】
また、ステップＳ６３において、グローバル履歴８４の分岐結果GHR［ｊ−１］の値が「−１」であると判定した場合、重み付き分岐結果値算出部６２は、処理をステップＳ６４に進め、WT［ｊ］より読み出した重みの符号を反転させ、その値を重み付き分岐結果値とし、NDI使用重み読み出し処理を終了する。つまり、重み付き分岐結果値算出部６２は、この場合、セレクタ１０２−ｊを制御して、WT［ｊ］より選択された重みがインバータ１０１を介してCSA tree１０３に出力されるようにする。
【０１６０】
NDI使用重み読み出し処理が終了されると、処理は、図１３のステップＳ４３に戻り、ステップＳ４５以降の処理が実行される。
【０１６１】
次に、図１３のステップＳ４４において実行されるLDI使用重み読み出し処理の詳細な流れの例を、図１５のフローチャートを参照して説明する。
【０１６２】
ステップＳ８１において、重み選択部６１は、入力された最新のアドレスＡ［０］および多重化アドレスを用いてLDI［ｊ］を生成する。ステップＳ８２において、重み選択部６１は、そのLDI［ｊ］をインデックスとしてWT［ｊ］（WT［ｊ］（LDI［ｊ］）より重みを取得する。ステップＳ８３において、重み付き分岐結果値算出部６２は、グローバル履歴８４の分岐結果GHR［ｊ−１］の値が「１」であるか否かを判定し、「１」であると判定した場合、WT［ｊ］より読み出した重みを重み付き分岐結果値とし、LDI使用重み読み出し処理を終了する。つまり、重み付き分岐結果値算出部６２は、この場合、セレクタ１０２−ｊを制御して、WT［ｊ］より選択された重みがそのままCSA tree１０３に出力されるようにする。
【０１６３】
また、ステップＳ８３において、グローバル履歴８４の分岐結果GHR［ｊ−１］の値が「−１」であると判定した場合、重み付き分岐結果値算出部６２は、処理をステップＳ８４に進め、WT［ｊ］より読み出した重みの符号を反転させ、その値を重み付き分岐結果値とし、LDI使用重み読み出し処理を終了する。つまり、重み付き分岐結果値算出部６２は、この場合、セレクタ１０２−ｊを制御して、WT［ｊ］より選択された重みがインバータ１０１を介してCSA tree１０３に出力されるようにする。
【０１６４】
LDI使用重み読み出し処理が終了されると、処理は、図１３のステップＳ４４に戻り、ステップＳ４５以降の処理が実行される。
【０１６５】
以上のように、各ステージの処理が実行される。
【０１６６】
次に、図１６のフローチャートを参照して、図２の学習処理部４２により実行される学習処理の流れの例を説明する。
【０１６７】
学習処理は、演算部２４において行われた実際の命令実行結果を、重みテーブル８２の内容に反映させるように、それらの学習を行う処理である。この学習処理は、学習処理部４２によって、上述した分岐予測処理とは独立して、パイプライン処理が行われている間実行される。
【０１６８】
例えば、学習処理が開始されると、学習処理部４２は、ステップＳ１０１において、演算部２４より取得した情報に基づいて、分岐方向が確定したか否か、すなわち、演算部２４において分岐命令が実行されその実行結果が得られたか否かを判定し、得られたと判定するまで待機する。分岐命令の実行結果は、演算部２４より分岐予測部２１に供給される。分岐命令の実行が終了し、分岐方向が確定したと判定した場合、学習処理部４２は、ステップＳ１０２において、ステージ０において算出された予測値と演算部２４より取得した分岐命令の実行結果である分岐結果とが等しいか否か（予測が当たったか否か）を判定する。予測値と分岐結果とが等しい（予測が当たった）と判定した場合、学習処理部４２は、処理をステップＳ１０３に進め、予測値を算出する際の重み付き分岐結果累算値の総和と閾値との加算結果の絶対値が、予め定められた所定の値である偏向値θより小さいか否かを判定する。すなわち、その予測が十分に確信を持ってなされたものであるか否か（予測値の信頼性が高いか否か）を判定する。
【０１６９】
ステップＳ１０３において、予測時の計算値の絶対値が偏向値θより小さい、つまり、予測値の信頼性が低いと判定された場合、学習処理部４２は、処理をステップＳ１０４に進める。また、ステップＳ１０３において、予測値と分岐結果とが等しくない（予測が外れた）と判定した場合、学習処理部４２は、処理をステップＳ１０６に進める。
【０１７０】
ステップＳ１０４において、学習処理部４２は、今回の分岐方向と値が一致するグローバル履歴８４の分岐結果（GHR［ｐ］）に対応する重みの値に「１」を加算するように、レジスタ４４に保持されている重みテーブル８２を更新する。
【０１７１】
ステップＳ１０４の処理を終了すると、学習処理部４２は、ステップＳ１０５に処理を進め、各重みテーブルの、今回の分岐方向と値が一致しないグローバル履歴８４の分岐結果（GHR［ｐ］）に対応する重みの値に「１」を減算するように、レジスタ４４に保持されている重みテーブル８２を更新する。
【０１７２】
換言すると、学習処理部４２は、ステップＳ１０４およびステップＳ１０５の処理により、図１０に示される各重みテーブル８２の、今回の分岐予測処理において読み出される値に「１」を加算または減算することにより、分岐方向と値が一致するグローバル履歴の重みを増し、分岐方向と一致しないグローバル履歴の重みを低減させるように、グローバル履歴８４の各分岐結果（GHR［ｐ］）の重みを再調整する（更新する）。
【０１７３】
ステップＳ１０５の処理を終了すると、学習処理部４２は、処理をステップＳ１０６に進める。
【０１７４】
ステップＳ１０６において、更新処理部４３は、分岐方向が確定すると、最新の多重化アドレス８３内の最も過去のローカル履歴ビットを分岐結果と置換する。つまり、更新処理部４３は、多重化アドレス８３の更新を行う。
【０１７５】
ステップＳ１０６の処理が終了されると、学習処理が終了される。
【０１７６】
以上より、本実施形態によれば、分岐予測部２１は、予測に用いる重みテーブルの数を低減させて実装コストを低減させるとともに、より詳細な実行パス履歴情報を重み読み出しのインデックスに反映させることにより、テーブル当たりのエントリ数を増大させ、分岐予測の予測精度向上を実現させることができる。
【０１７７】
以上のような分岐予測部２１による分岐予測処理の予測精度をシミュレーション結果について説明する。
【０１７８】
まず、最適な重みのビット長を求めるためのシミュレーションについて説明する。最適な重みのビット長を求めるためにNDIの数Ｉと、LDIの数（ｎ−Ｉ）を変えて予測精度を求めた。図１７にそのシミュレーション結果を示す。図１７に示されるグラフは、重みのビット長と予測ミス率の関係を、テーブル数（NDIをインデックスとするテーブルとLDIをインデックスとするテーブルのそれぞれの数）毎に示している。
【０１７９】
図１７に示されるシミュレーションにおいては、NDIをインデックスとするテーブルの数Ｉと、LDIをインデックスとするテーブルの数（ｎ−１）の組み合わせが、（３，１）の場合、（５，３）の場合、および（７，５）の３つの場合について、重みのビット長と予測ミス率の関係を比較した。
【０１８０】
図１７に示されるグラフより、どのテーブル数の場合においても、重みのビット長は、長くなるほど予測精度が高くなることがわかる。ただし、６ビット以上ではほとんど変化していない。不要に重みのビット長を増大させると負荷の増大に繋がる恐れがある。そこで、以下のシミュレーションにおいては、重みのビット長は６とする。従来のパーセプトロン分岐予測器においては、一般的に、重みのビット長は８ビットとされていた。つまり、従来の一般的なパーセプトロン分岐予測器の場合よりも重みのビット長が短く設定される。
【０１８１】
次に、本実施の形態において説明した手法と、従来法の予測精度を比較する。比較対象としてPipelined PTBPとO-GEHL branch predictorを用いた。いずれも、本実施の形態において説明した手法と略同程度の複数の重みテーブルと加算器を備える分岐予測器である。なお、本実施の形態において説明した手法については、分岐命令の分岐方向が確定した後に多重化アドレスを更新する場合と更新しない場合の両方についてシミュレーションを行った。また、各分岐予測器の記憶容量が、８Ｋバイト、１６Ｋバイト、３２Ｋバイト、６４Ｋバイト、および１２８Ｋバイトの５つの場合についてそれぞれシミュレーションを行った。
【０１８２】
図１８に示される表は、シミュレーションにおいて各分岐予測器に割り当てたパラメータの例を示している。例えば、記憶容量が８Ｋバイトの場合、Pipelined PTBPのテーブル数は２２とし、重みビット長は８ビットとし、O-GEHL branch predictorのテーブル数は８とし、本実施の形態において説明した分岐予測器（Proposed）のテーブル数は、NDIをインデックスとするテーブルの数、LDIをインデックスとするテーブルの数、および、ステージ０に割り当てられる閾値設定用のテーブル（バイアステーブル）の数をそれぞれ、３／２／１とし、重みビット長を６ビットとし、閾値シフトを１ビットとする。
【０１８３】
また、Proposedのバイアステーブルは、他のテーブルの２倍の容量とし、多重化アドレスで使用するローカル履歴長は２bitとした．閾値シフトはバイアステーブルから読みだされた閾値に対する右シフトの桁数である。また、更新閾値は、テーブルの総数をＴとし、閾値シフトをｑ桁とした時、２．１×（Ｔ＋２ｑ）とした。
【０１８４】
図１９は、以上のような条件下で、各予測器の記憶容量と予測ミス率の関係を示すグラフである。曲線２０１がPipelined PTBPの記憶容量と予測ミス率の関係を示しており、曲線２０２がO-GEHL branch predictorの記憶容量と予測ミス率の関係を示しており、曲線２０３が、予測すべき分岐命令の分岐方向が確定した後に多重化アドレスの更新を行わない場合の、Proposedの記憶容量と予測ミス率の関係を示しており、曲線２０４が、予測すべき分岐命令の分岐方向が確定した後に多重化アドレスの更新を行う場合の、Proposedの記憶容量と予測ミス率の関係を示している。
【０１８５】
図１９に示されるように、Proposedの分岐予測器は、全ての記憶容量において、他の分岐予測器よりも予測ミス率が低い（曲線２０３および曲線２０４）。特に、多重化アドレスの更新を行う場合（曲線２０４）の方が、多重化アドレスの更新を行わない場合（曲線２０３）よりも予測ミス率が低い。
【０１８６】
Proposedの分岐予測器のハードウェアコストを従来の分岐予測器と比較すると、同じ記憶容量で比較した場合、主なハードウェア量の違いは、重みの読み出し、加減算、更新に関する回路である。パーセプトロン分岐予測器は、１つの重みに対してそれぞれ１つの読み出しおよび更新回路が必要となる。さらに、重みの累算回路の回路面積も累算する重みの数に比例する。図１８の表に示されているように、Proposedの分岐予測器のテーブル数は、Pipelined PTBPのテーブル数と比べて４分の１程度である。つまり、本実施の形態において説明したProposedの分岐予測器では、これらの回路の数がPipelined PTBPの４分の１程度で済むことになる。また、重みのビット長も短くなっているため、加減算や更新に関する回路の１単位当たりの面積コストも低減される。
【０１８７】
次にレイテンシを従来法と比較する。Proposedの分岐予測器の場合、累算する重みの数が少なく、重みのビット長も短いためCPA回路が縮小される。この結果、CPAのレイテンシは従来の分岐予測器よりも軽減される。反対にテーブルのエントリ数の違いによりテーブル読み出しのレイテンシは増加する。ただし、その増加量はエントリ数の対数値に比例する。Proposedの分岐予測器と従来の分岐予測器とのエントリ数の比は最大で４倍程度であり、この分のレイテンシの増加は小さいことが分かる。以上から本実施の形態において説明した分岐予測器のレイテンシは従来の分岐予測器と同等であると言える。さらに、累算する重みの数が減少しているため累算のレイテンシも大幅に減少するので、ステージ１で読み出した複数の重みをバイアスと加算する前にCPAを用いて累算しておくことも可能である。このようにすることで、Proposedの分岐予測器の場合、従来の分岐予測器と比べてCSA１個のレイテンシを軽減させることができる。
【０１８８】
以上のように、本実施の形態において説明したProposedの分岐予測器は、従来の予測精度のみでなく実装コストやレイテンシの面でも優れていることが分かる。つまり、Proposedの分岐予測器は、実装コストの低減、および、分岐予測の予測精度向上を実現させることができる。
【０１８９】
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、図２０に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。
【０１９０】
図２０において、パーソナルコンピュータ３００のCPU３０１は、ROM（Read Only Memory）３０２に記憶されているプログラム、または記憶部３１３からRAM（Random Access Memory）３０３にロードされたプログラムに従って各種の処理を実行する。RAM３０３にはまた、CPU３０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１９１】
CPU３０１、ROM３０２、およびRAM３０３は、バス３０４を介して相互に接続されている。このバス３０４にはまた、入出力インタフェース３１０も接続されている。
【０１９２】
入出力インタフェース３１０には、キーボード、マウスなどよりなる入力部３１１、CRTやLCDなどよりなるディスプレイ、並びにスピーカなどよりなる出力部３１２、ハードディスクなどより構成される記憶部３１３、モデムなどより構成される通信部３１４が接続されている。通信部３１４は、インターネットを含むネットワークを介しての通信処理を行う。
【０１９３】
入出力インタフェース３１０にはまた、必要に応じてドライブ３１５が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア３２１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部３１３にインストールされる。
【０１９４】
上述した一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
【０１９５】
この記録媒体は、例えば、図２０に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM（Compact Disc - Read Only Memory）,DVD（Digital Versatile Disc）を含む）、光磁気ディスク（MD（Mini Disc）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア３２１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM３０２や、記憶部３１３に含まれるハードディスクなどで構成される。
【０１９６】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１９７】
また、本明細書において、システムとは、複数のデバイス（装置）により構成される装置全体を表すものである。
【０１９８】
なお、以上において、１つの装置として説明した構成を分割し、複数の装置として構成するようにしてもよい。逆に、以上において複数の装置として説明した構成をまとめて１つの装置として構成されるようにしてもよい。また、各装置の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置の構成の一部を他の装置の構成に含めるようにしてもよい。つまり、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【産業上の利用可能性】
【０１９９】
本発明は、分岐予測器に適用することが可能である。
【図面の簡単な説明】
【０２００】
【図１】本発明を適用した情報処理システムの構成例を示すブロック図である。
【図２】図１の分岐予測部の詳細な構成例を示すブロック図である。
【図３】パラメータの例を説明する図である。
【図４】多重化アドレスの生成手順を説明する模式図である。
【図５】多重化アドレスを用いた重み読み出しの例を説明する図である。
【図６】アドレスの種類数に応じたインデックスの生成方法を説明する表である。
【図７】多重化アドレスの種類数と予測ミス率との関係を示すグラフである。
【図８】使用される多重化アドレスの分布の例を示すグラフである。
【図９】更新を行わない場合と、更新を行う場合の多重化アドレスを比較する図である。
【図１０】予測処理部により実行される予測処理のパイプライン構造の構成例を模式的に示す図である。
【図１１】パイプライン処理の流れの例を説明する図である。
【図１２】ステージ０処理の流れの例を説明するフローチャートである。
【図１３】ステージ１処理の流れの例を説明するフローチャートである。
【図１４】NDI使用重み読み出し処理の流れの例を説明するフローチャートである。
【図１５】LDI使用重み読み出し処理の流れの例を説明するフローチャートである。
【図１６】学習処理の流れの例を説明するフローチャートである。
【図１７】テーブル数と予測ミス率の関係を説明するグラフである。
【図１８】分岐予測器毎のパラメータの例を示す表である。
【図１９】分岐予測器毎の記憶容量と予測ミス率との関係を示すグラフである。
【図２０】本発明を適用したパーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
【０２０１】
１１  CPU，  ２１  分岐予測部，  ４１  予測処理部，  ４２  学習処理部，  ４３  更新処理部，  ４４  レジスタ，  ５１  ステージ１処理部，  ５２  ステージ０処理部，  ６１  重み選択部，  ６２  重み付き分岐結果値算出部，  ６３  重み付き分岐結果値累算部，  ７１  重み付き分岐結果値累算部，  ７２  閾値算出部，  ７３  予測値算出部，  ７４  多重化アドレス生成部，  ８１  重み付き分岐結果累算値，  ８２  重みテーブル，  ８３  多重化アドレス，  ８４  グローバル履歴，  ８５  実行パス履歴，  ８６  ローカル履歴，  ８７  通常間隔インデックス，  ８８  長間隔インデックス，  １０１  インバータ，  １０２  セレクタ，  １０３  CSA tree，  １１１  CSA tree，  １１２  セレクタ，  １１３  CSA，  １１４  CPA
【図１】
0005283054.tif 000007
【図２】
0005283054.tif 000008
【図３】
0005283054.tif 000009
【図４】
0005283054.tif 000010
【図５】
0005283054.tif 000011
【図６】
0005283054.tif 000012
【図７】
0005283054.tif 000013
【図８】
0005283054.tif 000014
【図９】
0005283054.tif 000015
【図１０】
0005283054.tif 000016
【図１１】
0005283054.tif 000017
【図１２】
0005283054.tif 000018
【図１３】
0005283054.tif 000019
【図１４】
0005283054.tif 000020
【図１５】
0005283054.tif 000021
【図１６】
0005283054.tif 000022
【図１７】
0005283054.tif 000023
【図１８】
0005283054.tif 000024
【図１９】
0005283054.tif 000025
【図２０】
0005283054.tif 000026