(57)【特許請求の範囲】
【請求項１】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、
前記グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプライン構造を有し、
前記分岐命令のアドレスに前記分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成する多重化アドレス生成手段と、
前記各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが前記多重化アドレス生成手段により生成された前記多重化アドレスと対応付けられ前記ステージ毎に割り当てられた重みテーブルより、重みを選択する重み選択手段と、
前記重み選択手段により選択された前記各重みにより、前記ステージ毎に割り当てられた前記グローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出する重み付き分岐結果値累算手段と、
前記多重化アドレス生成手段により生成された前記多重化アドレスをインデックスとして最終段のステージに割り当てられた前記重みテーブルより閾値を選択する閾値算出手段と、
前記最終段のステージにおいて、前記重み付き分岐結果値累算手段により累算された前記重み付き分岐結果値に、前記閾値算出手段により算出された前記閾値を加算することにより、予測値を算出する予測値算出手段と
を備える情報処理装置。
【請求項２】
前記最終段のステージを除いて、前記グローバル履歴に含まれる各分岐結果を履歴順に所定長を有する複数の鎖に分割し、前記各鎖を前記ステージ毎に順次処理することにより、前記鎖の本数分の処理を同時並列的に行うパイプライン構造を有し、
前記重み選択手段は、いずれかの前記鎖のいずれかの前記ステージにおいては、前記多重化アドレスを用いて、割り当てられた前記重みテーブルより重みを選択し、
前記重み付き分岐結果値累算手段は、前記鎖の前記ステージ毎に前記重み付き分岐結果値を取得し、前記鎖毎に前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、
前記予測値算出手段は、前記重み付き分岐結果値累算手段により前記鎖毎に累算された重み付き分岐結果累算値の総和を算出し、算出した重み付き分岐結果累算値の総和を用いて予測値を算出する
請求項１に記載の情報処理装置。
【請求項３】
前記最終段のステージを除いて、前記グローバル履歴に含まれる各分岐結果を履歴順に同一ステージで同時並列的に処理する複数のグループに分割することにより、前記グループの数分の長さを有し前記ステージ毎に順次処理を行う鎖が複数本形成されるパイプライン構造を有し、
前記重み選択手段は、いずれかの前記鎖のいずれかの前記ステージにおいては、前記多重化アドレスを用いて、割り当てられた前記重みテーブルより重みを選択し、
前記重み付き分岐結果値累算手段は、前記鎖の前記ステージ毎に前記重み付き分岐結果値を取得し、前記鎖毎に前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、
前記予測値算出手段は、前記重み付き分岐結果値累算手段により前記鎖毎に累算された重み付き分岐結果累算値の総和を算出し、算出した重み付き分岐結果累算値の総和を用いて予測値を算出する
請求項１に記載の情報処理装置。
【請求項４】
前記重み選択手段は、
予測を行う分岐命令のアドレスであるターゲットアドレスに最も近い分岐命令のアドレスに対する分岐結果が割り当てられた前記鎖の前記ステージにおいては、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスのみをインデックスとして前記重みテーブルより前記重みを選択し、
前記ターゲットアドレスに最も近い分岐命令のアドレスに対する分岐結果以外の分岐結果が割り当てられた前記鎖の前記ステージにおいては、前記最新のアドレスと前記多重化アドレスとの排他的論理和をインデックスとして前記重みテーブルより前記重みを選択する
請求項２または３に記載の情報処理装置。
【請求項５】
前記閾値算出手段は、前記多重化アドレス生成手段により生成された前記多重化アドレスをインデックスとして最終段のステージに割り当てられた前記重みテーブルより閾値を選択する代わりに、前記最終段のステージに割り当てられた前記重みテーブルから、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスに対応する重みを閾値の候補として全て特定し、前記ローカル履歴を用いて全候補の中から前記閾値を選択し、
前記重み付き分岐結果値累算手段は、最終段の１つ前のステージの１本目の鎖において、前記重み選択手段により選択された前記重みにより、１つ前の分岐命令に対する予測値に対して重み付けを行うことによって重み付き分岐結果値を取得する
請求項１乃至４のいずれかに記載の情報処理装置。
【請求項６】
前記閾値算出手段は、前記多重化アドレス生成手段により生成された前記多重化アドレスをインデックスとして最終段のステージに割り当てられた前記重みテーブルより閾値を選択する代わりに、前記最終段のステージに割り当てられた前記重みテーブルから、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスに対応する重みを閾値の候補として全て特定し、前記候補の特定と並行して前記最新のアドレスに対応する前記ローカル履歴を特定し、前記ローカル履歴を用いて全候補の中から前記閾値を選択する
請求項１乃至５のいずれかに記載の情報処理装置。
【請求項７】
前記予測値算出手段により算出された前記予測値が分岐命令の実行結果と一致するか否か、並びに、前記予測値の信頼性に応じて、前記重みテーブルを更新する学習処理を行う学習処理部をさらに備える
請求項１乃至６のいずれかに記載の情報処理装置。
【請求項８】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理方法であって、
前記グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次パイプライン処理を行い、
前記分岐命令のアドレスに前記分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成し、
前記各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが前記多重化アドレスと対応付けられ前記ステージ毎に割り当てられた重みテーブルより、重みを選択し、
選択された前記各重みにより、前記ステージ毎に割り当てられた前記グローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、
前記多重化アドレスをインデックスとして最終段のステージに割り当てられた前記重みテーブルより閾値を選択し、
前記最終段のステージにおいて、累算された前記重み付き分岐結果値に、算出された前記閾値を加算することにより、予測値を算出する
ステップを含む情報処理方法。
【請求項９】
過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する処理を行うプログラムであって、
前記グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次パイプライン処理を行い、
前記分岐命令のアドレスに前記分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成し、
前記各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが前記多重化アドレスと対応付けられ前記ステージ毎に割り当てられた重みテーブルより、重みを選択し、
選択された前記各重みにより、前記ステージ毎に割り当てられた前記グローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、前記重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、
前記多重化アドレスをインデックスとして最終段のステージに割り当てられた前記重みテーブルより閾値を選択し、
前記最終段のステージにおいて、累算された前記重み付き分岐結果値に、前記閾値算出手段により算出された前記閾値を加算することにより、予測値を算出する
ステップをコンピュータに実行させるプログラム。
【請求項１０】
請求項９に記載のプログラムが記録されている記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置および方法、プログラム、並びに記録媒体に関し、特に、予測に必要な時間を抑制するとともに分岐予測の精度を向上させ、プロセッサのプログラム実行速度を向上させることができるようにした情報処理装置および方法、プログラム、並びに記録媒体に関する。
【背景技術】
【０００２】
近年、プロセッサのパイプラインはさらなる深化の傾向を見せており、パイプラインが深くなるにつれ制御ハザードに起因する性能低下はより深刻なものとなってきている。制御ハザードはプログラム内に存在するif文やWhile文に代表される分岐命令によって引き起こされる。これを回避する1つの手段として用いられるのが分岐命令の分岐方向を予測する分岐予測である。1990年代に入りgshare分岐予測器が考えられたが、わずかな予測精度向上でプロセッサのパフォーマンスは大幅に向上するため、分岐予測器には、さらなる予測精度の向上が要求された。
【０００３】
そこで、ニューラルネットワークの一種であるパーセプトロンを応用したパーセプトロン分岐予測器が注目された。
【０００４】
例えば、図1に示されるように、予測すべき分岐命令のアドレスであるターゲットアドレスとプログラムの分岐結果を時系列に並べたグローバル履歴(GH)を入力として用いるグローバルパーセプトロン分岐予測器(Global Perceptron)があった(例えば、特許文献1参照)。
【０００５】
この分岐予測器の場合、図1に示されるように、まず、ターゲットアドレス(TA)の下位ビットをインデックスとして重みテーブルより重みベクトルを読み出す。この重みベクトルは、分岐結果に対して事前になされた分岐予測の正否に応じて付与され、各要素がグローバル履歴(GH)の特定の場所と1対1に対応付けされている。グローバル履歴(GH)の各要素は、その値が「1」であれば分岐成立であり、値が「−1」であれば分岐不成立であることを表している。読み出された重みベクトル(重み群)の各要素とグローバル履歴(GH)を1つずつ乗算することにより重み付き分岐結果値を求め、この重み付き分岐結果値の総和の値が正であれば分岐成立(Taken)と予測され、値が負であれば分岐不成立(Not Taken)と予測される。このグローバルパーセプトロン分岐予測器を式で表すと、式(1)のように表すことができる。
【０００６】
【数１】
0005167489.tif 000002
【０００７】
なお、式(1)において、Ｗiは読み出された重みを示し、Ｘi(1≦i≦ｎ)は、各重みの要素に対応するグローバル履歴(GH)の要素を示す。また、ＷOは、分岐成立、不成立を区別するための閾値であり、重みベクトルとともに重みテーブルより読み出される。
【０００８】
求められたｙの値が正ならば分岐成立として値「1」が出力され、ｙの値が負ならば分岐不成立として値「−1(または0)」が出力される。
【０００９】
この重みＷiの更新規則は分岐結果をｔ∈｛1，−1｝とすると基本的に次の式(2)によって表される。
【００１０】
【数２】
0005167489.tif 000003
【００１１】
なお、式(2)において、係数αの値は通常の場合「1」である。
【００１２】
このようなグローバルパーセプトロン分岐予測器は、gshare分岐予測器などの予測器と比べて予測精度は高いが、予測に必要となる計算量が多いため、ターゲットアドレスが入力されてから分岐予測結果が得られるまでのレイテンシが非常に大きく、CPU(Central Processing Unit)等への実装は事実上不可能であった。
【００１３】
また、図1に示されるグローバルパーセプトロン分岐予測器では、グローバル履歴(GH)を用いるように説明したが、グローバル履歴の代わりに分岐命令毎の分岐結果を並べたローカル履歴を用いたものも知られている。図4は、その場合のローカルパーセプトロン分岐予測器の例を示す図である。このようにローカル履歴(LHT(Local History Table))より読み出した分岐結果(LH)を用いることにより、ローカルパーセプトロン分岐予測器は、グローバルパーセプトロン分岐予測器よりも予測精度を向上させることができる。ただし、このローカルパーセプトロン分岐予測器の場合も、グローバルパーセプトロン分岐予測器の場合と同様に、予測に必要となる計算量が多いため、ターゲットアドレスが入力されてから分岐予測結果が得られるまでのレイテンシが非常に大きく、CPU等への実装は事実上不可能であった。
【００１４】
レイテンシを隠蔽する工夫がなされたパーセプトロン分岐予測器としては、グローバル履歴を履歴順に分割して履歴が古い方から順次処理を行うパイプライン構造を有するパスベースドパーセプトロン分岐予測器(Path-Based Perceptron)があった。パスベースドパーセプトロン分岐予測器では、図2に示されるように、パイプラインの最終段ステージ以外に割り当てられた重みテーブル(テーブル1乃至テーブルＮ)より重みを読み出すためのインデックスにターゲットアドレスではなく、過去に実行された分岐命令のアドレスを用い、最終段ステージにおいて重みテーブル(テーブル0)より閾値を読み出すためにのみターゲットアドレスを用いるようになされている。つまり、インデックスに使用するターゲットアドレスを必要最低限に抑えることで、ターゲットアドレスが入力されるより前から、パイプライン化による複数の予測計算を同時に行うことが可能である。
【００１５】
しかしながら、この場合、過去のアドレスを用いて予測を行うため、プログラムが辿るアドレスが変化した場合には、無関係な値によって予測計算がなされてしまうことになる。このため、履歴長を伸ばしても予測精度の向上度はグローバルパーセプトロン分岐予測器に及ばない恐れがあった。
【００１６】
また、パーセプトロン分岐予測器として他に、パイプライン化されたパストレース分岐予測器(Pipelined PTBP(Path Trace Branch Predictor))が考えられた。パイプラインドPTBP(Pipelined PTBP)は、前記最終段のステージを除いて、前記パイプラインを履歴順に所定長を有する複数の鎖に分割し、前記各鎖を前記ステージ毎に順次処理することにより、前記鎖の本数分の処理を同時並列的に行うパイプライン構造を有しており、鎖の長さ(図3において横方向の段数)をＮとすると1鎖目(図3中、上の鎖)のｎ(ｎ≦Ｎ)番目のグローバル履歴に対応する重みは、過去に実行された分岐命令のアドレスを並べた実行パス履歴のｎ番目のアドレス(読み出し時はその時点で取得可能な最新のアドレス(Ａ［0］))を重み選択のインデックスとし、2鎖目のｎ＋Ｎ番目のグローバル履歴に対応する重みはｎ番目のアドレス(Ａ［0］)とｎ＋Ｎ番目のアドレス(Ａ［Ｎ］)をローテートして排他的論理和を取った値をインデックスとし、3鎖目のｎ＋2Ｎ番目のグローバル履歴に対応する重みはｎ番目のアドレス(Ａ［0］)とｎ＋Ｎ番目のアドレス(Ａ［Ｎ］)とｎ＋2Ｎ番目のアドレス(Ａ［2Ｎ］)をローテートして排他的論理和を取った値をインデックスとして重みを読み出す。ここで、ターゲットアドレスに代えて最新のアドレスＡ〔0〕を用いているのは、プログラムは局所的なループ構造を持つことが多いため、ターゲットアドレスの数個程度前に処理された分岐命令アドレスであればターゲットアドレスの情報を含んでいる可能性が高いためである。パイプラインドPTBPは、このようにＮ個毎にアドレス履歴の排他的論理和を取り、それをインデックスとして読み出した重みにより、各鎖のステージ毎に割り当てられた各分岐結果に対して重み付けをした重み付き分岐結果値を鎖毎に各ステージにおいて順次累算する。そして、最終段ステージにおいて、鎖毎に累算された重み付き分岐結果値の総和を算出し、その総和とターゲットアドレスをインデックスとしてテーブル0より読み出された閾値としての重みとを加算して分岐予測を行う。このようにすることにより、パイプラインドPTBPは、ターゲットの分岐命令までに辿ったパス情報を予測に反映することができ、予測精度を向上させることができた。
【００１７】
しかしながら、プログラム中にはグローバルな分岐履歴の一部が異なっても同じふるまいをする分岐命令が多数存在する。このような場合、パイプラインドPTBPのパイプライン構造では、予測に関係の無いアドレス履歴によってテーブルの読み出し位置の一部が変化し予測に悪影響を与える恐れがあった。パーセプトロン分岐予測器では、この予測に関係の無いアドレス履歴によって生成されるインデックスで読み出される重みは予測に相関のある重みと異なるものとなってしまう。PTBPはその構造上、1つのアドレス履歴が従来のパーセプトロンに比べて多くの重みのインデックスに関わることになり、この問題が及ぼすPTBPへの影響は他の分岐予測器に比較して大きくなってしまう。その結果として予測精度の向上を妨げてしまう恐れがあった。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】
特開平10−171653号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
以上のように、パーセプトロン分岐予測器において、様々な工夫がなされるものの、レイテンシを増大させずに予測精度を向上させることができないという課題があった。また、CPUの性能向上のために、分岐予測器の更なる予測精度の向上が求められているという課題もあった。
【００２０】
本発明は、このような状況に鑑みてなされたものであり、予測に必要な時間を抑制するとともに分岐予測の精度を向上させることができるようにするものである。
【課題を解決するための手段】
【００２１】
本発明の一側面は、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理装置であって、グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプライン構造を有し、分岐命令のアドレスに分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成する多重化アドレス生成手段と、各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが多重化アドレス生成手段により生成された多重化アドレスと対応付けられステージ毎に割り当てられた重みテーブルより、重みを選択する重み選択手段と、重み選択手段により選択された各重みにより、ステージ毎に割り当てられたグローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出する重み付き分岐結果値累算手段と、多重化アドレス生成手段により生成された多重化アドレスをインデックスとして最終段のステージに割り当てられた重みテーブルより閾値を選択する閾値算出手段と、最終段のステージにおいて、重み付き分岐結果値累算手段により累算された重み付き分岐結果値に、閾値算出手段により算出された閾値を加算することにより、予測値を算出する予測値算出手段とを備える情報処理装置である。
【００２２】
前記最終段のステージを除いて、グローバル履歴に含まれる各分岐結果を履歴順に所定長を有する複数の鎖に分割し、各鎖をステージ毎に順次処理することにより、鎖の本数分の処理を同時並列的に行うパイプライン構造を有し、重み選択手段は、いずれかの鎖のいずれかのステージにおいては、多重化アドレスを用いて、割り当てられた重みテーブルより重みを選択し、重み付き分岐結果値累算手段は、鎖のステージ毎に重み付き分岐結果値を取得し、鎖毎に重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、予測値算出手段は、重み付き分岐結果値累算手段により鎖毎に累算された重み付き分岐結果累算値の総和を算出し、算出した重み付き分岐結果累算値の総和を用いて予測値を算出することができる。
【００２３】
前記最終段のステージを除いて、グローバル履歴に含まれる各分岐結果を履歴順に同一ステージで同時並列的に処理する複数のグループに分割することにより、グループの数分の長さを有しステージ毎に順次処理を行う鎖が複数本形成されるパイプライン構造を有し、重み選択手段は、いずれかの鎖のいずれかのステージにおいては、多重化アドレスを用いて、割り当てられた重みテーブルより重みを選択し、重み付き分岐結果値累算手段は、鎖のステージ毎に重み付き分岐結果値を取得し、鎖毎に重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、予測値算出手段は、重み付き分岐結果値累算手段により鎖毎に累算された重み付き分岐結果累算値の総和を算出し、算出した重み付き分岐結果累算値の総和を用いて予測値を算出することができる。
【００２４】
前記重み選択手段は、予測を行う分岐命令のアドレスであるターゲットアドレスに最も近い分岐命令のアドレスに対する分岐結果が割り当てられた鎖のステージにおいては、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスのみをインデックスとして重みテーブルより重みを選択し、ターゲットアドレスに最も近い分岐命令のアドレスに対する分岐結果以外の分岐結果が割り当てられた鎖のステージにおいては、最新のアドレスと多重化アドレスとの排他的論理和をインデックスとして重みテーブルより重みを選択することができる。
【００２５】
前記閾値算出手段は、多重化アドレス生成手段により生成された多重化アドレスをインデックスとして最終段のステージに割り当てられた重みテーブルより閾値を選択する代わりに、最終段のステージに割り当てられた重みテーブルから、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスに対応する重みを閾値の候補として全て特定し、ローカル履歴を用いて全候補の中から閾値を選択し、重み付き分岐結果値累算手段は、最終段の１つ前のステージの１本目の鎖において、重み選択手段により選択された重みにより、１つ前の分岐命令に対する予測値に対して重み付けを行うことによって重み付き分岐結果値を取得することができる。
前記閾値算出手段は、多重化アドレス生成手段により生成された多重化アドレスをインデックスとして最終段のステージに割り当てられた重みテーブルより閾値を選択する代わりに、最終段のステージに割り当てられた重みテーブルから、その時点で取得可能な最新の分岐結果に対応する分岐命令のアドレスである最新のアドレスに対応する重みを閾値の候補として全て特定し、候補の特定と並行して最新のアドレスに対応するローカル履歴を特定し、ローカル履歴を用いて全候補の中から閾値を選択することができる。
前記予測値算出手段により算出された前記予測値が分岐命令の実行結果と一致するか否か、並びに、前記予測値の信頼性に応じて、前記重みテーブルを更新する学習処理を行う学習処理部をさらに備えることができる。
【００２６】
本発明の一側面は、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する情報処理方法であって、グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次パイプライン処理を行い、分岐命令のアドレスに分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成し、各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが多重化アドレスと対応付けられステージ毎に割り当てられた重みテーブルより、重みを選択し、選択された各重みにより、ステージ毎に割り当てられたグローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、多重化アドレスをインデックスとして最終段のステージに割り当てられた重みテーブルより閾値を選択し、最終段のステージにおいて、累算された重み付き分岐結果値に、算出された閾値を加算することにより、予測値を算出するステップを実行する情報処理方法である。
【００２７】
本発明の一側面は、過去における分岐命令の分岐結果が時系列に並べられたグローバル履歴を用いて分岐命令の分岐方向を予測する処理を行うプログラムであって、グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次パイプライン処理を行い、分岐命令のアドレスに分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスを生成し、各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが多重化アドレスと対応付けられステージ毎に割り当てられた重みテーブルより、重みを選択し、選択された各重みにより、ステージ毎に割り当てられたグローバル履歴の各分岐結果に対して重み付けを行うことによって重み付き分岐結果値を取得し、重み付き分岐結果値を順次累算して重み付き分岐結果累算値を算出し、多重化アドレスをインデックスとして最終段のステージに割り当てられた重みテーブルより閾値を選択し、最終段のステージにおいて、累算された重み付き分岐結果値に、算出された閾値を加算することにより、予測値を算出するステップをコンピュータに実行させることができる。
【００２８】
請求項9に記載のプログラムが記録されている記録媒体とすることができる。
【００２９】
本発明の一側面においては、グローバル履歴に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプライン構造が有され、分岐命令のアドレスに分岐命令毎の分岐結果を並べたローカル履歴を反映させた多重化アドレスが生成され、各分岐結果に対して事前になされた分岐予測の正否に応じて付与された重みが多重化アドレスと対応付けられステージ毎に割り当てられた重みテーブルより、重みが選択され、その選択された各重みにより、ステージ毎に割り当てられたグローバル履歴の各分岐結果に対して重み付けが行われることによって重み付き分岐結果値が取得され、重み付き分岐結果値が順次累算されて重み付き分岐結果累算値が算出され、多重化アドレスをインデックスとして最終段のステージに割り当てられた重みテーブルより閾値が選択され、最終段のステージにおいて、累算された重み付き分岐結果値に、算出された閾値が加算されることにより、予測値が算出される。
【発明の効果】
【００３４】
本発明の側面によれば、分岐命令の予測を行うことができる。特に、分岐予測に必要な時間を抑制するとともに分岐予測の精度を向上させることができる。
【図面の簡単な説明】
【００３５】
【図１】従来の分岐予測器の例を説明する図である。
【図２】従来の分岐予測器の他の例を説明する図である。
【図３】従来の分岐予測器の、さらに例を説明する図である。
【図４】従来の分岐予測器の、さらに例を説明する図である。
【図５】本発明を適用した情報処理システムの構成例を示すブロック図である。
【図６】図5の分岐予測部の詳細な構成例を示すブロック図である。
【図７】パラメータの例を説明する図である。
【図８】分岐予測パイプラインの構成例を模式的に示す図である。
【図９】グローバル履歴長およびパイプライン段数と、予測ミス率との関係を示すグラフである。
【図１０】多重化アドレスの生成手順を説明する模式図である。
【図１１】多重化アドレスを用いた重み読み出しの例を説明する図である。
【図１２】アドレスに付加するローカル履歴の分岐結果の長さと予測ミス率との関係を示すグラフである。
【図１３】重み付き分岐結果累算値の算出の例を説明するフローチャートである。
【図１４】パイプライン処理の流れの例を説明する図である。
【図１５】ステージ0処理の流れの例を説明するフローチャートである。
【図１６】ステージｎからステージ1の処理の流れの例を説明するフローチャートである。
【図１７】第1重み付き分岐結果累算処理の流れの例を説明するフローチャートである。
【図１８】第2重み付き分岐結果累算処理の流れの例を説明するフローチャートである。
【図１９】第3重み付き分岐結果累算処理の流れの例を説明するフローチャートである。
【図２０】学習処理の流れの例を説明するフローチャートである。
【図２１】シミュレーションに用いた履歴長の例を示す表である。
【図２２】予測器毎の記憶容量と予測ミス率の関係を示すグラフである。
【図２３】分岐予測パイプラインの他の構成例を模式的に示す図である。
【図２４】分岐予測パイプラインの、さらに他の構成例を模式的に示す図である。
【図２５】予測器毎の記憶容量と予測ミス率の関係を示すグラフである。
【図２６】ステージ0の閾値を読み出す部分の、他の構成例を示す図である。
【図２７】ステージ0処理の流れの、他の例を説明するフローチャートである。
【図２８】分岐予測パイプラインの、さらに他の構成例を模式的に示す図である。
【図２９】本発明を適用したパーソナルコンピュータの構成例を示すブロック図である。
【発明を実施するための形態】
【００３６】
次に、本発明を適用した実施の形態について、図面を参照して説明する。
【００３７】
図5は、本発明を適用した情報処理装置の構成例を示すブロック図である。
【００３８】
図5の情報処理装置に搭載されるCPU(Central Processing Unit)11は、命令実行を並列化し、前の命令の実行終了を待たずに次の命令を実行するパイプライン処理を行うプロセッサである。CPU11は、メモリ12に記憶されている命令を読み出して実行し、必要に応じて処理結果をメモリ12に返す。
【００３９】
CPU11は、分岐予測部21、フェッチ部22、デコード部23、演算部24、ライトバック部25、命令キャッシュ31、およびデータキャッシュ32を有している。
【００４０】
1つの命令に対する実行処理は複数のステージ(工程)により構成される。つまり、命令キャッシュ31に保持された命令を読み出すフェッチ(IF)、フェッチされた命令をデコードし、制御信号を生成したり、レジスタ・ファイルをレジスタ指定子で参照したり、必要に応じてデータキャッシュ32よりデータを読み出したりするデコード(ID)、数値の計算やロード・ストアのデータやアドレス・分岐先の計算を行う命令実行(EX)、並びに、演算結果を、データキャッシュを介してメモリ12に戻すライトバック(WB)などのステージがある。
【００４１】
命令キャッシュ31は、メモリ12より順次命令を読み出し保持する。フェッチ部22は、IFステージにおいて、命令キャッシュ31より命令をフェッチし、それをデコード部23に供給する。デコード部23は、IDステージにおいて、フェッチ部22より供給された命令をデコードし、必要に応じてデータキャッシュ32よりデータを取得し、それらを演算部24に供給する。
【００４２】
演算部24は、EXステージにおいて、デコード部23より供給される情報に基づいて演算を行う。その演算結果はライトバック部25に供給される。また、演算部24は、演算結果によって次の命令(ジャンプ先のアドレス)が異なる分岐命令のライトバック部25は、WBステージにおいて、演算部24より供給された演算結果をデータキャッシュ32に保持させる。データキャッシュ32は、必要に応じて、その演算結果をデコード部23に供給したり、メモリ12に書き込ませたりする。
【００４３】
分岐予測部21は、IFステージにおいて、演算部24より供給される演算結果等に基づいて、過去に実行された分岐命令の予測結果応じて付与された重みによって重み付けされたグローバル履歴の分岐結果を用いて、複数の鎖および複数のステージを有するパイプライン構造の予測処理を行い、分岐命令の実行結果、すなわち分岐先(アドレス)を予測する(分岐命令に対して分岐予測を行う)。フェッチ部22は、その分岐予測部21の予測に従って次の命令をフェッチする。
【００４４】
このとき、フェッチ部22、デコード部23、演算部24、およびライトバック部25は、パイプライン処理を行い、複数の命令を並列に実行する。すなわち、フェッチ部22は、演算部24の演算結果を待たずに、分岐予測部21の予測結果に従って、命令キャッシュ31より命令を次々とフェッチする。従って、分岐予測部21の予測精度を向上させることにより、CPU11において行われるパイプライン処理において制御ハザードの発生が減少するので、CPU11の処理性能を向上させることができる。
【００４５】
ここで、上述のIFステージにおけるパイプライン構造についてより詳細に説明する。本パイプライン構造は、グローバル履歴84に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプラインを、ステージの最終段を除いて、Ｍ個ずつ最新の履歴から順に同一ステージで同時並列的に処理するｎ個のグループに分割することにより、ｎ個の長さを有しステージ毎に順次処理を行う鎖がＭ本形成されてなる(図8参照)。各鎖の各ステージにおいては、割り当てられたグローバル履歴84の分岐結果に重み付けをした重み付き分岐結果値を順次算出して鎖毎に累算していく処理が行われるようになっている。そして、最終段ステージ(ステージ0)では、各鎖において累算された重み付き分岐結果値の総和を求め、閾値を用いて予測値を算出する処理が行われるようになっている(図8参照)。
【００４６】
次に、その分岐予測部21の構成について説明する。図6は、図5の分岐予測部21の詳細な構成例を示すブロック図である。
【００４７】
図6において、分岐予測部21は、上述したパイプラインを用いて分岐予測を行う予測処理部41、分岐命令のアドレスに分岐命令ごとの分岐結果の履歴であるローカル履歴を反映させた多重化アドレスを生成する多重化アドレス生成部74、分岐予測に使用される重みテーブルの各重みについて演算結果に基づいて学習を行う学習処理部42、分岐予測に使用される各パラメータの更新を行う更新処理部43、および分岐予測に使用される各パラメータやデータを保持するレジスタ44を有している。
【００４８】
レジスタ44は、予測処理部41の分岐予測に使用されるパラメータやデータ等を必要に応じて保持する。レジスタ44には、例えば、重み付き分岐結果累算値81、重みテーブル82、多重化アドレス83、グローバル履歴84、実行パス履歴85、およびローカル履歴86が保持される。
【００４９】
グローバル履歴(GHR(ｐ))84は、プログラム全体における分岐結果を時系列に並べた分岐結果の履歴(分岐履歴)である。GHR(ｐ)は、グローバル履歴84における最新の分岐結果から(ｐ＋1)番目の分岐結果を示す(0≦ｐ≦n(Ｍ−1))。各分岐結果は、分岐成立(Taken)を示す値「1」、若しくは、分岐不成立(Not Taken)を示す値「−1」により構成される。つまり、各分岐結果は分岐方向を示す。ただし、「−1」は実際には「0」で表現されている。
【００５０】
実行パス履歴(Ａ［ｐ］)85は、そのグローバル履歴84の各分岐結果に対応する分岐命令のアドレスの履歴である。Ａ［ｐ］は、実行パス履歴85における最新のアドレスから(ｐ＋1)番目のアドレスを示す。つまり、グローバル履歴84の分岐結果GHR(ｐ)は、実行パス履歴85のアドレスＡ［ｐ］で示される分岐命令の分岐結果を示す。また、Ａ［0］は、その時点での最新の分岐命令アドレスを示す。なお、最新の分岐結果GHR(0)によりジャンプする先のアドレスをターゲットアドレス(TA)とも称する。つまり、換言すると、古い(最新でない)ターゲットアドレス(TA)が実行パス履歴85に時系列順に蓄積される。
【００５１】
ローカル履歴(LHT(Local History Table)(ｑ))86は、グローバル履歴84の各分岐結果を、分岐命令ごとにまとめたものである。例えば、LHT(ｑ)は、ある分岐命令の、最新の分岐結果からｑ(0≦ｑ＜ｐ)番目の分岐結果を示す。つまり、ローカル履歴86においても、各分岐結果は分岐方向を示し、その値は、分岐成立(Taken)を示す値「1」、若しくは、分岐不成立(Not Taken)を示す値「−1」により構成される。
【００５２】
図7を参照して、グローバル履歴84乃至ローカル履歴86についてさらに詳細に説明する。
【００５３】
図7の左に示されるプログラム(sample.c)91は、グローバル履歴84乃至ローカル履歴86の説明のための、分岐命令を含むプログラムの例である。プログラム91においては、分岐命令として、200行目にfor文が記述され、208行目、216行目、および224行目にif文が記述されている。
【００５４】
図7の右側には、このプログラム91について、グローバル履歴84、実行パス履歴85、およびローカル履歴86の例が示されている。各履歴は、図7において、左から右に向かって時系列順に並んでいる。つまり、最も左側の履歴が一番古く、最も右側の履歴が一番新しい。実行パス履歴85の、最も古い(一番左の)アドレスは「200」であり、200行目のfor文が実行されたことが示されている。
【００５５】
このアドレスに対応するグローバル履歴84の分岐結果(GH)は「0」であり、200行目のfor文の条件(i<2)が真であったことが示されている。従って、このときのターゲットアドレス、すなわち次(実行パス履歴85の左から2番目)のアドレスは、for文のループ内の次の分岐命令が記述された「208」となる。このアドレスに対応するグローバル履歴84の分岐結果(GH)は「0」であり(すなわち、if文の条件(a==b)が偽であり)、変数ｘのインクリメント(x++)は行われずに、次の分岐処理の216行目に処理が移行する。従って、このときのターゲットアドレス、すなわち次(実行パス履歴85の左から3番目)のアドレスは、次の分岐命令が記述された「216」である。このアドレスに対応するグローバル履歴84の分岐結果(GH)は「1」であり(すなわち、if文の条件(a==b)が真であり)、変数ｙがインクリメント(ｙ++)される。その後、処理は200行目に戻る(実行パス履歴85においては左から4番目に進む)。
【００５６】
以降も同様にして各命令が実行され、200行目のfor文の条件(i<2)が偽となるまでfor文のループ内の命令(208行目および216行目の分岐命令)が繰り返し実行される。
【００５７】
そして、実行パス履歴85の最新の(一番右の)アドレスで指定された200行目のfor文の予測において、分岐結果が「1」(グローバル履歴84の一番右の分岐結果(GH))であること、すなわち、200行目のfor文のループが終了されたと予測されたことが示されている。この場合、224行目のif文にジャンプすることになるので、このときのターゲットアドレス(TA)87の値は、図7に示されるように「224」となる。
【００５８】
なお、ローカル履歴86の各分岐結果(LH)は、グローバル履歴に示される分岐結果が、分岐命令毎に(行番号毎に)整理されている。
【００５９】
図6及び図10を参照して、多重化アドレス(MA(Multiprex Address)(ｐ))83は、実行パス履歴85のアドレス(Ａ［ｐ］)の下位ビットをそのビット長さ分のローカル履歴86(LHT(ｑ))に差し替えて生成される。MA［ｐ］は、実行パス履歴85における最新のアドレスから(ｐ＋1)番目のアドレスＡ［ｐ］の下位ビットをローカル履歴86LHT(ｑ)に差し替えたものを示す。なお、本実施形態においては、多重化アドレス(MA(ｐ))83は、実行パス履歴85のアドレス(Ａ［ｐ］)の下位ビットをそのビット長さ分のローカル履歴86(LHT(ｑ))に差し替えて生成されるようにしたが、アドレス(Ａ［ｐ］)の下位ビットを削除することなく、アドレス(Ａ［ｐ］)にローカル履歴86(LHT(ｑ))を付加させることにより、アドレス(Ａ［ｐ］)にローカル履歴86(LHT(ｑ))を反映させるようにしてもよい。
【００６０】
ここで、予測精度の向上のために、ローカル履歴を利用することについて説明する。ローカル履歴は、例えば、図4を参照して説明したようなグローバル／ローカルパーセプトロン分岐予測器等で使用されており、このローカル履歴の分岐結果を利用することにより、グローバル履歴の分岐結果のみを用いた場合よりも予測精度が向上している。
【００６１】
しかしながら、ローカル履歴の分岐結果に重み付けを行って分岐予測をする場合、ターゲットアドレス以外を用いて重みを読み出すとすると、分岐結果と無関係な重み付けがなされてしまうため、重みはターゲットアドレスを用いて読み出さなくてはならず、パイプライン化ができなくなる。
【００６２】
そこで、本実施形態においては、図10に示すように、実行パス履歴85のアドレス131の下位2ビットを削除してアドレス(ショート)132を生成し、そのアドレス(ショート)132にローカル履歴86(LHT)から読み出された2ビットの分岐結果(LH)133を付加したものを多重化アドレス(MA)83とし、この多重化アドレス83をレジスタ44に記憶しておき、ステージｎからステージ1における重みテーブル82からの重みの読み出し及びステージ0における閾値の読み出しに利用している。
【００６３】
このように、本実施形態においては、ローカル履歴86の分岐結果は直接的に予測演算に使用されることはないが、インデックスに加えることで1つのアドレスからローカル履歴長のべき乗通りのインデックスが作成可能になる。一般的に1つの分岐命令が、その時々に応じて分岐方向を変える(分岐方向の両方に分岐する)ことは多いが、実行パス履歴85のアドレスのみをインデックスとして重みを選択する従来の手法の場合、その分岐命令がいずれの方向に分岐する場合であっても同じ重みが選択されることになっていた(重みの負の衝突が発生した)。
【００６４】
これに対し、図11に示されるように、ローカル履歴86の分岐結果を実行パス履歴85のアドレスの下位ビットと差し替えた多重化アドレス(MA)をインデックスとして使用することにより、選択する重みを、その分岐方向によって変更することができ、重みの負の衝突を回避することができる。これにより、ハードウェアコストの増加を最小限に抑えつつ予測精度の向上を期待することができる。
【００６５】
図6を参照して、重みテーブル(WT(ｉ，ｊ))82は、各分岐命令について、過去に当該分岐命令まで辿ったグローバル履歴の各分岐結果に対して、事前になされた分岐予測の正否を反映した重み(重み群)が、当該分岐命令のアドレスの下位ビットをローカル履歴に差し替えた多重化アドレスと対応付けられて、保持されたものである。多重化アドレス毎に重みが対応付けられているため、1つの分岐命令の両分岐方向について、それぞれ分岐予測の正否に応じて付与された重みが保持されている。重みテーブル82は、多重化アドレス毎に、その分岐命令までのグローバル履歴に含まれる各分岐結果に対する重みの全てが重み群として保持されたものであるが、WT(ｉ，ｊ)は、ｊ(1≦ｊ≦Ｍ)番目の鎖のｉ(1≦ｉ≦ｎ)番目のステージに割り当てられたグローバル履歴がGHR(ｐ)とすると、全多重化アドレスについて最新の分岐結果から(ｐ＋1)番目の分岐結果に対応する重みが保持された部分を重みテーブルとして示すものである(i，ｊは整数)。
【００６６】
重み付き分岐結果累算値(REG(ｉ，ｊ))81は、各鎖の各ステージに割り当てられたグローバル履歴の各分岐結果に重み付けを行った重み付き分岐結果値を、各ステージにおいて鎖毎に順次累算した値である。REG(ｉ，ｊ)は、ｊ(1≦ｊ≦Ｍ)番目の鎖のｉ(1≦ｉ≦ｎ)番目のステージにおいて算出される累算値であり、その鎖のステージｎからステージｉ(1≦ｉ≦ｎ)までの各ステージにおいて算出された、重み付き分岐結果値の累算値を示す(i，ｊは整数)。この累算値は、各ステージで算出される度にレジスタ44に一旦保持された後、次のステージにおいて読み出され、新たな累算値の算出に利用される。
【００６７】
図6のレジスタ44には、このような各種のパラメータが必要に応じて保持される。
【００６８】
図6の予測処理部41は、レジスタ44に保持される、このようなデータやパラメータ等を用いて、複数(ｎ＋1段)のステージおよび複数(Ｍ個)の鎖を有するパイプライン構造の予測処理を行う。なお、ステージ0は、各鎖共通である。予測処理部41は、このようなパイプライン構造の予測処理のうち、ステージｎからステージ1の処理を行うステージ1−ｎ処理部51、および、ステージ0の処理を行うステージ0処理部52を有している。
【００６９】
ステージ1−ｎ処理部51は、各鎖のステージｎ乃至ステージ1の各ステージにおいて、割り当てられた重みテーブル82(WT(ｉ，ｊ))から重みを選択する重み選択部61、及び、その選択された重みによりグローバル履歴の分岐結果に重み付けをした重み付き分岐結果値を算出し、鎖毎に累算処理を行う重み付き分岐結果値累算部62を有する。
【００７０】
重み選択部61は、1本目の鎖(図8において一番上の段の鎖)のステージ1においては、割り当てられた重みテーブル82(WT(1，1))より、実行パス履歴85の最新のアドレスＡ［0］をインデックスとして重みを読み出す。1本目の鎖のステージ1以外のステージ(ｎ〜2)及び他の鎖(2〜Ｍ本目の鎖)の各ステージ(ｎ〜1)においては、それぞれ割り当てられた重みテーブル82より、実行パス履歴85の最新のアドレスＡ［0］と、割り当てられたグローバル履歴84に対応する多重化アドレス(MA)との排他的論理和をインデックスとして、それぞれ重みを選択して読み出す。
【００７１】
重み付き分岐結果値累算部62は、各鎖の各ステージにおいて、割り当てられたグローバル履歴84の分岐結果に重み付けをした重み付き分岐結果値を算出するようになっている。実際には、分岐不成立(Not Taken)を示す値「−1」が「0」で表現されており、「0」に重みを掛け合わせると「0」になってしまうため、分岐結果が「0」である場合は重みの符号を反転させた値を、分岐結果が「1」である場合には重みそのままの値を出力させることにより、重み付き分岐結果値を求めるようになっている。そのため、重み付き分岐結果値累算部62は、例えば、重みの値(ビットパターン)を反転させるための論理否定回路(図示しない)と、分岐結果の値を反転させるための論理否定回路(図示しない)と、読み出した重みの値とこれを論理否定回路により反転させた値とを入力して分岐結果の反転値を用いてどちらかを選択して出力するセレクタ(図示しない)と、セレクタから出力された値と分岐結果の反転値とを加算する加算器を備え、セレクタに分岐結果「0」を反転した「1」が入力されたときは、重みを反転した値(重みの値の1の補数)を選択して出力し、重みを反転した値と分岐結果の反転値「1」とを加算して2の補数(負の表現)として出力し、セレクタに分岐結果「1」を反転した「0」が入力されたときは、重みそのままの値を選択して出力し、その値と分岐結果の反転値「0」とを加算して重みそのままの値を出力するようになっている。
【００７２】
また、重み付き分岐結果値累算部62は、加算器102(図8参照)を有しており、各ステージにおいて、求めた重み付き分岐結果値に、レジスタ44に保持されている直前のステージまでの重み付き分岐結果累算値81を読み出して加算することによって、そのステージまでの重み付き分岐結果累算値81を算出し、算出した新たな重み付き分岐結果累算値81をレジスタ44に保持させるようになっている。なお、加算器102は、上記セレクタ出力値と分岐結果の反転値とを加算する加算器としても用いるようにしても良い。
【００７３】
ステージ0処理部52は、ステージ0において、分岐成立または不成立を識別するための閾値を算出する閾値算出部72と、各鎖の重み付き分岐結果累算値の総和を算出し、算出した総和と閾値とに基づいて予測値を算出する予測値算出部73とを有する。
【００７４】
閾値算出部72は、ステージ0に割り当てられた重みテーブル82から、最新のアドレスＡ［0］(ステージ0においてはターゲットアドレス)における多重化アドレスを生成する際にローカル履歴に差し替えらる下位ビットを除く上位ビットをインデックスとして、特定される複数の閾値を候補として全て選定する。閾値の候補数は、多重化アドレスを生成する際にローカル履歴に差し替えらる下位ビットの数のべき乗であり、例えば、ローカル履歴に差し替えらるビット数が2である場合は、閾値の候補数は4となる。また、閾値算出部72は、セレクタ112を有しており(図8参照)、ローカル履歴86のテーブルより分岐結果を読み出して、複数の閾値候補の重みの中から1つを選択することにより、閾値を算出する。なお、このように最新のアドレスＡ〔0〕の上位ビットで特定した閾値の候補からローカル履歴で1つを選択することによって、結果として多重化アドレスを用いて閾値を算出したことになる。
【００７５】
予測値算出部73は、加算器111を有しており(図8参照)、予測処理がパイプライン構造のステージｎからステージ1まで進む間に各鎖において累算された重み付き分岐結果累算値81をそれぞれレジスタ44より取得し、それらの総和を算出する。また、予測値算出部73は、加算器113を有しており(図8参照)、重み付き分岐結果累算値の総和と閾値算出部72により算出された閾値とを加算することによって予測値を算出する。例えば、予測値算出部73は、重み付き分岐結果累算値の総和と閾値の加算結果の最上位ビット(符号ビット)の値が「1(−を意味)」の場合は、過去において分岐不成立の傾向が強いことを示しているため、分岐不成立を予測して予測値「0」を出力し、最上位ビットの値が「0(＋を意味)」の場合は、過去において分岐成立の傾向が強いことを示しているため、分岐成立を予測して予測値「1」を出力する。この場合、予測値算出部73は、論理否定回路(図示しない)を備え、重み付き分岐結果累算値の総和と閾値の加算結果の最上位ビットを反転させ、その値を予測値として出力するようになっている。なお、重み付き分岐結果累算値の総和と閾値の加算結果の絶対値は、その予測値の確かさ(信頼度)とみなすことができる。
【００７６】
多重化アドレス生成部74は、実行パス履歴85のアドレス(処理時はターゲットアドレス)の下位2ビットを、ローカル履歴86に含まれる最新の分岐結果(ターゲットアドレスの1つ前の分岐命令に対する分岐結果)及びその前の分岐結果に差し替えて多重化アドレス(MA)を生成する。
【００７７】
学習処理部42は、予測値算出部73において算出された予測値と、演算部24における実際の演算結果(分岐結果)に基づいて、重みテーブル82の各重みについての学習処理を行う。更新処理部43は、新たなターゲットアドレス、演算結果(分岐結果)が確定した後、実行パス履歴85、グローバル履歴84、ローカル履歴86を随時更新する処理を行う。なお、更新処理部43は、予測値が算出される毎にグローバル履歴84を暫定的に更新し、演算結果が算出された後に、予測値を演算結果が異なる場合は、演算結果に書き換えるようになっている。また、更新処理部43は、新たなターゲットアドレスとローカル履歴86とによりアドレス83が生成された後、多重化アドレス83を随時更新する処理を行う。
【００７８】
図8は、予測処理部41により実行される予測処理のパイプライン構造(Advanced Anti-Aliasing Perceptron Branch Predictor(A3PBPまたはAAAPBP)と称するパーセプトロン分岐予測器の実行する予測処理の構造)の構成例を模式的に示す図である。
【００７９】
本パイプライン構造は、図8に示すように、ｎＭ−ｎ＋1の長さを有するグローバル履歴84に含まれる各分岐結果を履歴順に分割してステージ毎に順次処理を行うパイプラインを、ステージの最終段(ステージ0)を除いて、ＧＨＲ〔0〕〜ＧＨＲ〔Ｍ−1〕のＭ個の分岐結果に関する処理を、同時並列的にステージ1で行う1つのグループとし、同様にＧＨＲ〔Ｍ−1〕〜ＧＨＲ〔2Ｍ−2〕のＭ個の分岐結果に関する処理を、同時並列的にステージ2で行う1つのグループとするというように、Ｍ個ずつ分割されたグループがｎ個あり、ｎ個の長さを有しステージｎからステージ1に向かって順次処理を行う鎖がＭ本形成されてなる。
【００８０】
また、各鎖の各ステージには、割り当てられたグローバル履歴に対応する重みテーブル82が割り当てられている。具体的には、1本目の鎖のステージ1には、最新の分岐結果から0番目のグローバル履歴ＧＨＲ〔0〕と、グローバル履歴ＧＨＲ〔0〕の分岐結果に対する重みが保持された重みテーブルとが割り当てられており、2本目の鎖のステージ1には、最新の分岐結果から1個前のグローバル履歴ＧＨＲ〔1〕と、グローバル履歴ＧＨＲ〔1〕の分岐結果に対する重みが保持された重みテーブル82とが割り当てられ、Ｍ本目の鎖のステージ1には、最新の分岐結果からＭ−1個前のグローバル履歴ＧＨＲ〔Ｍ−1〕と、グローバル履歴ＧＨＲ〔Ｍ−1〕の分岐結果に対する重みが保持された重みテーブル82とが割り当てられている。同様に他のステージにおいても1本目の鎖から履歴が新しい順に1つずつグローバル履歴〔ｐ〕とグローバル履歴ＧＨＲ〔ｐ〕の分岐結果に対する重みが保持された重みテーブル82とが割り当てられている。
【００８１】
このように本実施形態においては、最新の分岐結果に近いグローバル履歴84ＧＨＲ〔ｐ〕及びターゲットアドレスに近い実行パス履歴85のアドレスほど後のステージで使用されるパイプライン構造としたため、それぞれのステージにおいて処理を行う際に、演算結果に基づいて更新されたグローバル履歴84ＧＨＲ〔ｐ〕及びよりターゲットアドレスに近いアドレスの更新された実行パス履歴85Ａ〔0〕を用いることができるため、予測精度が向上する。すなわち、図3に示すように、パイプラインを履歴順に所定長を有する複数の鎖に分割したパイプライン構造では、最上流のステージにおいては次の段の鎖の最下流のステージよりも最新の分岐結果に近いグローバル履歴84ＧＨＲ〔ｐ〕及びターゲットアドレスに近い実行パス履歴85のアドレスが割り当てられていることから、上方段の鎖の上流側のステージでは、その処理時に、割り当てられたグローバル履歴84ＧＨＲ〔ｐ〕の演算結果(分岐結果)が算出されていない場合があり、演算結果に書き換えられる前に暫定的に格納されている分岐予測結果を用いて投機的に予測を行うことになるため予測精度が低下するが、本実施形態によるパイプライン構造では、分岐予測結果を用いて投機的に予測を行わずにすむため予測精度が向上する。
【００８２】
そして、本パイプライン構造による処理は、次のように行われる。すなわち、ステージｎの上から1本目の鎖において、重み選択部61により、実行パス履歴85のこのステージｎの処理時に取得可能な最新のアドレス(Ａ［0］)と多重化アドレス(MA［(Ｍ−1)(ｎ−1)］)とが読み出され、両者の排他的論理和をインデックスとして、重みテーブル82−｛(ｎ−1)Ｍ＋1｝より重みが選択される。そして、重み付き分岐結果値累算部62により、選択された重みを用いて、グローバル履歴84GHR［(Ｍ−1)(ｎ−1)］に重み付けがなされ、その結果が重み付き分岐結果累算値81としてレジスタ44−ｎに一時的に保持される。
【００８３】
また、ステージｎの上から2本目の鎖において、重み選択部61により、実行パス履歴85のこのステージｎの処理時に取得可能な最新のアドレス(Ａ［0］)と多重化アドレス(MA［ｎＭ−ｎ−Ｍ＋2］)とが読み出され、両者の排他的論理和をインデックスとして、重みテーブル82−｛(ｎ−1)Ｍ＋2｝より重みが選択されされる。そして、重み付き分岐結果値累算部62により、選択された重みを用いて、グローバル履歴84GHR［ｎＭ−ｎ−Ｍ＋2］に重み付けがなされ、その重み付き分岐結果値が重み付き分岐結果累算値81としてレジスタ44−ｎに一時的に保持される。
【００８４】
同様にステージｎの各鎖において、実行パス履歴85の最新のアドレス(Ａ［0］)と多重化アドレス(MA［ｐ］)の排他的論理和に基づいて重みテーブル82より重みが選択され、グローバル履歴84に重み付けがなされ、その重み付き分岐結果値が重み付き分岐結果累算値81としてレジスタ44−ｎに一時的に保持される。このステージｎのＭ個の各鎖における処理は、同時並列的に行われる。
【００８５】
ステージｎ−1乃至ステージ1の各鎖においては、重み付き分岐結果値累算部62により、図8において左隣(時系列的に上流側)の、1段前のステージ(例えば、ステージ(ｎ−1)の1段前のステージはステージｎ、ステージ1の1段前のステージはステージ2)においてレジスタ44(レジスタ44−ｎ乃至レジスタ44−2)に保持された重み付き分岐結果累算値81が読み出され、ステージｎの場合と同様に算出した重み付き分岐結果値に加算され、新たな重み付き分岐結果累算値81としてレジスタ44(レジスタ44−(ｎ−1)乃至レジスタ44−1)に一時的に保持される。
【００８６】
例えば、ステージ2の上から1本目の鎖において、重み選択部61により、実行パス履歴85のこのステージ2の処理時に取得可能な最新のアドレス(Ａ［0］)と多重化アドレス(MA［Ｍ−1］)とが読み出され、両者の排他的論理和をインデックスとして、重みテーブル82−(Ｍ＋1)より重みが選択される。そして、重み付き分岐結果値累算部62により、選択された重みを用いて、グローバル履歴84GHR［Ｍ−1］に重み付けがなされ、その重み付き分岐結果値が、レジスタ44より読み出され、同じ鎖のステージ3までの重み付き分岐結果累算値81(REG(3，1))と加算される。そして、重み付き分岐結果値累算部62により、その加算結果が新たな重み付き分岐結果累算値81として、レジスタ44−2に一時的に保持される(REG(2，1))。ステージ2の他の鎖においても、同様の処理が同時並列的に行われる。
【００８７】
ステージ1においても同様の処理がなされるが、ステージ1の上から1本目の鎖の場合、実行パス履歴85の最新のアドレス(Ａ［0］)のみによって重みが選択される。これは、1本目の鎖において多重化アドレス(MA[0])を用いようとすると、この多重化アドレス(MA[0])は最新のアドレス(Ａ［0］)が確定した後に生成されるため、最新のアドレス(Ａ［0］)が取得可能であるにもかかわらず、多重化アドレス(MA[0])の生成を待って両者の排他的論理和を算出しなければならなくなり、不要にレイテンシを増やすことになるためである。
【００８８】
本パイプライン処理においては、ｘを任意の自然数とし、あるステージのある鎖に割り当てられたグローバル履歴がGHR[ｘ]とすると、GHR[ｘ]の分岐結果に対応する実行パス履歴のアドレスをＡ[ｘ]として、重み選択に用いるインデックスを生成するための多重化アドレス(MA[ｐ])は、Ａ[ｘ]から生成されたものを用いるようにしたが、任意の多重化アドレスを用いるようにしてもよい。例えば、GHR[0]が割り当てられたステージ1の1本目の鎖ではMA[1]を用い、GHR[1]が割り当てられたステージ1の2本目の鎖ではMA[2]を用いるというように、順次対応付けるようにしてもよい。ただし、この対応関係は予測処理の開始前に予め決められている。
【００８９】
このように、本実施形態では、予測に関係のない分岐命令のアドレスの悪影響を最小限に抑えるために、パイプラインドPTBP(図3参照)のように、鎖の長さＮ毎に連鎖的にアドレス履歴の排他的論理和を取って重み読み出しのインデックスにすることはせず、最新のアドレス(Ａ［0］)のみ、あるいは最新のアドレス(Ａ［0］)と多重化アドレス(MA[ｐ])とのみの排他的論理和をインデックスとするようにしている。
【００９０】
本パイプライン処理においては、新たな分岐命令が命令キャッシュ31に入力される毎に、ステージが1つずつ進行するようになっている。
【００９１】
なお、以上において、レジスタ44−1乃至レジスタ44−ｎは、いずれも図6のレジスタ44の記憶領域の一部を示しており、それぞれ、各ステージにおいて算出される重み付き分岐結果累算値を一時的に保持する領域である。
【００９２】
ここで、図8に示されるA3PBPの各ステージでレジスタ44から読み出すことのできる重み付き分岐結果累算値の最大数すなわち鎖の本数について説明する。
【００９３】
A3PBPのレイテンシは、閾値が読み出されるレイテンシと、ステージ1までの鎖毎の重み付き分岐結果累算値と閾値の加算に必要となるレイテンシを足した値である。実装するプロセッサのアーキテクチャに依存することではあるが、閾値の読み出し時間で隠蔽することが十分可能である加算器の段数を3段とすれば、重み付き分岐結果累算値の総和を求めるのを4段の加算器で行うのであれば、閾値の読み出し時間と同等で処理できる。つまり、同時に読み出し可能な重み付き分岐結果累算値の最大数は16となる。
【００９４】
このことを踏まえて、このパーセプトロン分岐予測器のパイプライン段数の最適化実験を行った。実験はSPEC CINT2000の12種類のベンチマークをSimCoreシミュレータで1億命令程度実行した際にトレースしたデータを、この予測器が実装された場合の動作をシミュレートしたプログラムで処理し、その予測精度を求めた。
【００９５】
図9はステージ数(ｈ＋1)による予測ミス率の変化を示している。グローバル履歴(bit数)が短い場合にはｈ＝1(ステージ数最小)が最も良い結果を出しているのに対し、グローバル履歴が長くなるにつれてステージ数(つまりｈ)の深さによる予測ミス率の差は小さくなっている。例えば、グローバル履歴長が64ビットの場合、ｈ＝1の予測ミス率よりも、ｈ＝2の予測ミス率の方が低くなっている。
【００９６】
これは、グローバル履歴が長くなるにしたがい、PTBPのようなパスの詳細な把握による予測精度の向上効果が、ステージの深化によるターゲットアドレスに関する情報の劣化による予測精度低下の影響を上回るためだと思われる。
【００９７】
図9に示されるように、予測ミス率は、グローバル履歴長が16ビットの場合、ｈ＝1(すなわち同時重み付き分岐結果累算値読み出し数が16)のときが一番低く、ｈ＝2(すなわち同時重み付き分岐結果累算値読み出し数が8)のときがその次に低い。また、グローバル履歴長が32ビットの場合、予測ミス率は、ｈ＝1(すなわち同時重み付き分岐結果累算値読み出し数が32)のときとｈ＝2(すなわち同時重み付き分岐結果累算値読み出し数が16)のときが略同程度で最も低く、ｈ＝3(すなわち同時重み付き分岐結果累算値読み出し数が8)のときがその次に低い。さらに、グローバル履歴長が48ビットの場合、予測ミス率は、ｈ＝1(すなわち同時重み付き分岐結果累算値読み出し数が48)のときとｈ＝2(すなわち同時重み付き分岐結果累算値読み出し数が24)のときが略同程度で最も低く、ｈ＝3(すなわち同時重み付き分岐結果累算値読み出し数が12)のときがその次に低い。また、グローバル履歴長が64ビットの場合、予測ミス率は、ｈ＝2(すなわち同時重み付き分岐結果累算値読み出し数が32)のときが最も低く、ｈ＝1(すなわち同時重み付き分岐結果累算値読み出し数が64)のときとｈ＝3(すなわち同時重み付き分岐結果累算値読み出し数が16)のときが略同程度でその次に低い。
【００９８】
以上の結果より、最適な同時重み付き分岐結果累算値読み出し数は16乃至32とすることができる。上述したように、重み付き分岐結果累算値の許容最大数は16であるので、最大の予測精度を得るためには、同時に読み出す重み付き分岐結果累算値の数すなわち鎖の本数を16とするのが最適であるといえる。
【００９９】
次に、ステージ0について説明する。ステージ0では、閾値算出部72により、重みテーブル82から、最新のアドレスＡ［0］の上位ビットをインデックスとして、特定される複数の重みが閾値候補として全て選定されるとともに、最新のアドレスＡ［0］をインデックスとしてローカル履歴86のテーブルより最新の分岐結果とその1つ前の分岐結果とが読み出され、読み出した分岐結果を用いて、閾値算出部72を構成するセレクタ112により、閾値候補の中から1つが選択されることにより閾値が算出される。なお、重みの選択とローカル履歴からの分岐結果の読み出しとは並行して行われる。また、予測値算出部73により、ステージｎからステージ1において鎖ごとに算出されたＭ個の重み付き分岐結果累算値81(REG(1，1)乃至REG(1，Ｍ))がそれぞれレジスタ44より読み出され、予測値算出部73を構成する加算器111により、それらの総和が算出される。そして、予測値算出部73を構成する加算器113により、重み付き分岐結果累算値の総和と閾値とを加算することによって予測値が算出される。
【０１００】
なお、ステージ0ではＭ個の重み付き分岐結果累算値81の総和を算出する必要があるが、閾値の算出と同時並列的に計算させることにより、その計算時間を隠蔽することができる。
【０１０１】
ここで、多重化アドレスを生成する際に差し替えられるローカル履歴86の分岐結果のビット長を示すローカル履歴長と予測精度の関係について説明する。SPEG CINT2000の12種類のベンチマークをSimCoreシミュレータで1億命令程度実行した際にトレースしたデータを、この予測器が実装された場合の動作をシミュレートしたプログラムで処理し、その予測精度を求めた。
【０１０２】
図12は、その実験結果を示す、実行パス履歴85のアドレスに付加する分岐結果の長さ(LHビット長(bit))と予測ミス率(％)の関係を示すグラフである。図12のグラフにおいて、曲線141は、グローバル履歴の長さが32ビットの場合の、LHビット長と予測ミス率との関係を示しており、曲線142は、グローバル履歴の長さが48ビットの場合の、LHビット長と予測ミス率との関係を示している。図12のグラフより、ローカル履歴長が3ビットの場合に最も予測ミス率が低いことが分かる。ただし、2ビットの場合とほとんど差はなく、逆に、ビット長が増えるとステージ0において閾値候補として一括読み出しが必要な重みの数が増え、処理の負荷が大きくなるデメリットが大きくなる。2ビットの場合、一括読み出しの必要がある閾値の個数は4個であり、実装上特に障害とはならない。なお、もちろん、この分岐結果の長さは任意であり、処理の負荷が、実装上問題ない程度であれば、例えば3ビット以上にすることも可能である。
【０１０３】
次に、分岐予測処理の全体の流れについて、図13のフローチャートを参照して説明する。
【０１０４】
予測処理部41のステージ1−ｎ処理部51(図6)は、ステップＳ1において、分岐命令が命令キャッシュ31(図5)に入力されたか否かを判定し、入力されていないと判定した場合、ステップＳ2に処理を進め、分岐予測パイプラインとしての処理をストールさせ、処理をステップＳ1に戻す。すなわち、ステージ1−ｎ処理部51は、ステップＳ1において、分岐命令が入力されたと判定するまで、ステップＳ2の処理を繰り返しながら待機する。
【０１０５】
ステップＳ1において、分岐命令が入力されたと判定した場合、ステージ1−ｎ処理部51は、処理をステップＳ3に進める。ステップＳ3において、ステージ1−ｎ処理部51は、図8に示されるA3PBPのパイプラインのステージｎについて重み付き分岐結果累算処理を行い、算出した重み付き分岐結果累算値81(REG(ｎ，ｊ))をレジスタ44−ｎに保持させる。ステップＳ3の処理を終了すると、ステージ1−ｎ処理部51は、処理をステップＳ4に進める。
【０１０６】
ステップＳ4において、ステージ1−ｎ処理部51は、次の分岐命令が命令キャッシュ31に入力されたか否かを判定し、次の分岐命令が入力されたと判定するまで、ステップＳ5において分岐予測パイプラインとしての処理をストールさせながら待機する。
【０１０７】
ステップＳ4において、次の分岐命令が入力されたと判定した場合、ステージ1−ｎ処理部51は、処理をステップＳ6に進め、図8に示されるA3PBPのパイプラインのステージ(ｎ−1)について重み付き分岐結果累算処理を行い、算出した重み付き分岐結果累算値81(REG((ｎ−1)，ｊ))をレジスタ44−(ｎ−1)に保持させる。ステップＳ6の処理を終了すると、ステージ1−ｎ処理部51は、処理を次のステップに進める。
【０１０８】
以上のように、ステージ1−ｎ処理部51は、分岐命令が命令キャッシュ31に入力される度に、各ステージについて重み付き分岐結果累算処理を繰り返し、ステージ1まで重み付き分岐結果累算値を算出する。
【０１０９】
そしてステージ1について、ステップＳ(3ｎ−2)において、ステージ1−ｎ処理部51は、分岐命令が命令キャッシュ31に入力されたか否かを判定し、次の分岐命令が入力されたと判定するまで、ステップＳ(3ｎ−1)において分岐予測パイプラインとしての処理をストールさせながら待機する。
【０１１０】
ステップＳ(3ｎ−2)において、次の分岐命令が入力されたと判定した場合、ステージ1−ｎ処理部51は、処理をステップＳ3ｎに進め、図8に示されるA3PBPのパイプラインのステージ1について重み付き分岐結果累算処理を行い、算出した重み付き分岐結果累算値81(REG(1，ｊ))をレジスタ44−1に保持させる。ステップＳ3ｎの処理を終了すると、ステージ1−ｎ処理部51は、処理をステップＳ(3ｎ＋1)に進める。
【０１１１】
ステージ0処理部52は、ステップＳ(3ｎ＋1)乃至ステップＳ(3ｎ＋3)において、図8に示されるA3PBPのパイプラインのステージ0についての処理を行う。つまり、ステップＳ(3ｎ＋1)において、ステージ0処理部52は、新たな分岐命令が命令キャッシュ31に入力されたか否かを判定し、次の分岐命令が入力されたと判定するまで、ステップＳ(3ｎ＋2)において分岐予測パイプラインとしての処理をストールさせながら待機する。
【０１１２】
ステップＳ(3ｎ＋1)において、新たな分岐命令が入力されたと判定した場合、ステージ0処理部52は、処理をステップＳ(3ｎ＋3)に進め、図8に示されるA3PBPのパイプラインのステージ0についてステージ0処理を行い、重み付き分岐結果累算値の総和を算出し、閾値を選択し、その総和と閾値を加算し、予測値を算出して出力する。また、ステップＳ(3ｎ＋3)と並行して、ステップ(3ｎ＋5)において、多重化アドレス生成部74が、ステップＳ(3ｎ＋1)において入力された分岐命令のアドレスすなわちターゲットアドレスとローカル履歴とにより多重化アドレスを生成する。
【０１１３】
その後、ステップＳ(3ｎ＋4)において、レジスタの各値が更新されて、処理が終了される。具体的には、ステージ0におけるターゲットアドレスで実行パス履歴が更新され、ステップＳ(3ｎ＋4)において算出された予測値でグローバル履歴84が暫定的に更新される。また、ステップＳ(3ｎ＋5)において生成された多重化アドレス83による更新がされる。なお、その後、この分岐予測処理とは独立して、別途演算部24により実際に演算された分岐結果に基づいて、グローバル履歴84及びローカル履歴が更新される。また、分岐結果に基づいて学習処理部42により学習処理がなされた重みにより重みテーブル82が更新される。
【０１１４】
このように、A3PBPを用いた分岐予測処理においては、ステージｎにおいて初期値が生成され、分岐命令が入力される度にステージを1つずつ進み、重み付き分岐結果累算値が算出される。ただし、実際には、各分岐命令に対して予測値を出力する必要があるので、各ステージの処理は並行して行われる。つまり、図14に示すように、複数のパイプラインが並行して実行され、その結果、ｎ組の重み付き分岐結果累算値が並行して処理され、分岐命令が入力される度に予測値が出力される。
【０１１５】
次に、ステージ0処理の流れの例を図15のフローチャートを参照して説明する。
【０１１６】
ステージ0処理が開始されると、予測値算出部73は、ステップＳ121において、レジスタ44−1に保持されている重み付き分岐結果累算値81(REG(1，ｊ))を全て読み出し、加算器111を用いて、それらの総和を算出する。この処理と並行して、閾値算出部72は、ステップＳ122において、実行パス履歴85の最新のアドレスＡ［0］をインデックスとしてローカル履歴86より分岐結果(LHT(Ａ［0］))を読み出す。
また、閾値算出部72は、さらにステップＳ122の処理と並行して、ステップＳ123において、実行パス履歴85の最新のアドレスＡ［0］の上位ビット(下位2ビットを削除したもの)をインデックスとして閾値用の重みテーブル82−0より閾値の候補(WT［0，Ａ［0］］)を全て(4個)取得する。
【０１１７】
ステップＳ124において、閾値算出部72は、ローカル履歴86より読み出した分岐結果に基づいて、セレクタ112により候補の中から閾値を選択する。予測値算出部73は、ステップＳ125において、加算器113を用いて重み付き分岐結果累算値の総和と閾値を加算し、ステップＳ126において、加算結果の最上位ビットの値を反転させ、ステップＳ127において、その反転結果(最上位ビット)を予測値として出力する。
【０１１８】
次に、図16のフローチャートを参照して、ステージｎからステージ1における処理の詳細な流れの例を説明する。
【０１１９】
ステージ1−ｎ処理部51は、ステップＳ151において、図8におけるパイプラインの鎖の上からの番号を示す変数ｊの値を「1」に設定し、ステップＳ152において、ステージ数を示す変数ｋの値が「1」であるか否かを判定する。つまり、ステージ1−ｎ処理部51は、今回のステージｋ処理がステージ1に対する処理であるか否かを判定する。
変数ｋの値が「1」であると判定した場合、ステージ1−ｎ処理部51は、処理をステップＳ153に進め、変数ｊの値が「1」であるか否かを判定し、「1」であると判定した場合、処理をステップＳ154に進め、図8においてステージ1の上から1本目の鎖において重みを累算する第1重み付き分岐結果累算処理を行う。第1重み付き分岐結果累算処理が終了すると、ステージ1−ｎ処理部51は、処理をステップＳ156に進める。また、ステップＳ153において、変数ｊの値が「1」でないと判定した場合、ステージ1−ｎ処理部51は、処理をステップＳ155に進め、図8において上から2乃至ｎ本目の鎖のステージ1において重みを累算するために、ステージ1の上から1本目の鎖、並びに、ステージｎの各鎖以外において重みを累算する第3重み付き分岐結果累算処理を行う。第3重み付き分岐結果累算処理が終了すると、ステージ1−ｎ処理部51は、処理をステップＳ156に進める。
【０１２０】
ステップＳ156において、ステージ1−n処理部51は、変数ｊの値を「1」インクリメントし、処理対象を次の鎖に切り返る。ステップＳ157において、ステージ1−ｎ処理部51は、変数ｊの値が任意の正の整数Ｍより大きいか否かを判定し、変数ｊの値がＭより大きくなく、変数ｊが示す鎖は存在すると判定した場合、処理をステップＳ153に戻し、それ以降の処理を繰り返す。つまり、ステージ1−ｎ処理部51は、ステージ1の鎖のそれぞれについて、ステップＳ153乃至ステップＳ157の処理を実行する。そして、ステップＳ157において変数ｊの値がＭより大きいと判定した場合、ステージ1−ｎ処理部51は、処理を終了する。
【０１２１】
また、図16のステップＳ152において、変数ｋの値が「1」でないと判定した場合、すなわち、処理対象のステージがステージ2乃至ステージｎのいずれかである場合、ステージ1−ｎ処理部51は、処理をステップＳ158に進める。
【０１２２】
ステップＳ158において、ステージ1−ｎ処理部51は、変数ｋの値が「ｎ」であるか否かを判定し、変数ｋの値が「ｎ」であり、処理対象のステージが最前段のステージｎであると判定した場合、処理をステップＳ159に進め、ステージｎの各鎖において重みを累算する第2重み付き分岐結果累算処理を実行する。ステップＳ159の処理を終了すると、ステージ1−ｎ処理部51は、処理をステップＳ160に進め、変数ｊの値を「1」インクリメントし、ステップＳ161において、変数ｊの値が任意の正の整数Ｍより大きいか否かを判定する。変数ｊの値がＭより大きくなく、変数ｊが示す鎖は存在すると判定した場合、ステージ1−ｎ処理部51は、処理をステップＳ159に戻し、それ以降の処理を繰り返す。つまり、ステージ1−ｎ処理部51は、ステージｎの鎖のそれぞれについて、ステップＳ159乃至ステップＳ161の処理を実行する。そして、ステップＳ161において変数ｊの値がＭより大きいと判定した場合、ステージ1−ｎ処理部51は処理を終了する。
【０１２３】
また、図16のステップＳ158において、変数ｋの値が「1」でないと判定した場合、すなわち、処理対象のステージがステージ2乃至ステージ(ｎ−1)のいずれかである場合、ステージ1−ｎ処理部51は、処理をステップＳ162に進め、第3重み付き分岐結果累算処理を実行する。ステップＳ162の処理が終了すると、ステージ1−ｎ処理部51は、処理をステップS163に進め、変数jの値を「1」インクリメントし、ステップＳ164において、変数ｊの値が任意の正の整数Ｍより大きいか否かを判定する。変数ｊの値がＭより大きくなく、変数ｊが示す鎖は存在すると判定した場合、ステージ1−ｎ処理部51は、処理をステップＳ162に戻し、それ以降の処理を繰り返す。つまり、ステージ1−ｎ処理部51は、ステージ2乃至ステージ(ｎ−1)の鎖のそれぞれについて、ステップＳ162乃至ステップＳ164の処理を実行する。そして、ステップＳ164において変数ｊの値がＭより大きいと判定した場合、ステージ1−ｎ処理部51は処理を終了する。
【０１２４】
次に、図17のフローチャートを参照して、図8のステージ1の一番上の鎖における重み付き分岐結果累算処理である第1重み付き分岐結果累算処理の流れの例を説明する。
【０１２５】
第1重み付き分岐結果累算処理が開始されると、ステップＳ181において、1本目の鎖について、重み付き分岐結果値累算部62は、レジスタ44−2より重み付き分岐結果累算値81(REG(2，1))を読み出して取得する。ステップＳ182において、重み選択部61は、実行パス履歴85の最新のアドレスＡ［0］をインデックスとして、重みテーブル82−1より重みを取得する(すなわちWT(1，Ａ［0］)より重みを取得する)。
【０１２６】
重み付き分岐結果値累算部62は、ステップＳ183において、レジスタ44より、グローバル履歴84の最新の分岐結果84−1(GHR［0］)を取得し、ステップＳ184において、その分岐結果を反転させ、ステップＳ185において、加算器102−1を用いて、重み付き分岐結果累算値81(REG(2，1))を被加数とし、重みテーブルWT(1，Ａ［0］)より取得した重みを加数とし、反転された分岐結果を補数信号として加算処理を行う。すなわち、重みの値そのままと反転したもの(1の補数)を用意しておき、分岐結果84−1＝0の場合は、これを反転した「1」の補数信号が送られくるので、そのときは、重みを反転した値(1の補数)をセレクトして、重みを反転した値(1の補数)と分岐結果84−1＝0を反転した「1」とを加算して2の補数(負の表現)として、重み付き分岐結果累算値81(REG(2，1))と加算し、分岐結果84−1＝1の場合は、これを反転した「0」が補数信号として送られくるので、そのときは、重みそのままの値をセレクトして、その値と分岐結果84−1＝1を反転した「0」とを加算して(結局重みそのままの値)、重み付き分岐結果累算値81(REG(2，1))と加算する。
【０１２７】
重み付き分岐結果値累算部62は、ステップＳ186において、加算結果を新たな重み付き分岐結果累算値81(REG(1，1))としてレジスタ44−1に保持させる。
【０１２８】
次に、図18のフローチャートを参照して、ステージｎにおける重み付き分岐結果の累算処理である第2重み付き分岐結果累算処理の流れの例を説明する。
【０１２９】
第2重み付き分岐結果累算処理が開始されると、ステップＳ201において、重み選択部61は、多重化アドレス83と実行パス履歴85の最新のアドレスの排他的論理和をインデックスとして重みテーブルWT((n-1)×M+j，MA［(n-1)×M-n+j XOR A[0]］)より重みを取得する。ステップＳ202において、重み付き分岐結果値累算部62は、グローバル履歴84より分岐結果84−｛(n-1)×M-n+j｝(GHR［(n-1)×M-n+j］)を取得する。ステップＳ203において、重み付き分岐結果値累算部62は、グローバル履歴84より取得した分岐結果84−｛(n-1)×M-n+j｝の値が「1」であるか否かを判定し、「1」であると判定した場合、そのまま処理をステップＳ205に進め、「1」でないと判定した場合、処理をステップＳ204に進め、取得した重みの符号を反転させた後、ステップＳ205に処理を進める。なお、ステップＳ204における重みの符号を反転は、重みの値(ビットパターン)を反転させた値(重みの値の1の補数)と分岐結果84−｛(n-1)×M-n+j｝(GHR［(n-1)×M-n+j］)を反転させた値(＝1)を加算して2の補数とすることにより行う。
【０１３０】
次に、図19のフローチャートを参照して、図8のステージ1の上から2本目乃至Ｍ本目の各鎖、並びに、ステージ2乃至ステージ(ｎ−1)の全ての鎖における重み付き分岐結果累算処理である第3重み付き分岐結果累算処理の流れの例を説明する。
【０１３１】
第3重み付き分岐結果累算処理が開始されると、ステップＳ221において、重み付き分岐結果値累算部62は、レジスタ44−(ｋ＋1)に保持されている重み付き分岐結果累算値81(REG(ｋ＋1，ｊ))を読み出して取得する。ステップＳ222において、重み選択部61は、実行パス履歴85の最新のアドレス(Ａ［0］)と多重化アドレス83の排他的論理和をインデックスとして、重みテーブル82−((k-1)×M+j)(すなわちWT((k-1)×M+j，MA[(k-1)×M-k+j] XOR A[0]))より重みを取得する。
【０１３２】
重み付き分岐結果値累算部62は、ステップＳ223において、レジスタ44よりグローバル履歴84の分岐結果84−｛(k-1)×M-k+j｝(GHR［(k-1)×M-k+j］)を取得し、ステップＳ224において、重み付き分岐結果累算値81(REG(k+1，1))を被加数とし、重みテーブルWT((k-1)×M+j，MA[(k-1)×M-k+j] XOR A[0])より取得した重みを加数とし、グローバル履歴84より取得した分岐結果84−｛(k-1)×M-k+j｝(GHR[(k-1)×M-k+j])を反転させて補数信号として加算処理を行う。
【０１３３】
重み付き分岐結果値累算部62は、ステップＳ225において、加算結果を新たな重み付き分岐結果累算値81(REG(ｋ，ｊ))としてレジスタ44−ｋに保持させる。
【０１３４】
次に、図20のフローチャートを参照して、図6の学習処理部42により実行される学習処理の流れの例を説明する。
【０１３５】
学習処理は、演算部24において行われた実際の命令実行結果を、重みテーブル82の内容に反映させるように、それらの学習を行う処理である。この学習処理は、学習処理部42によって、上述した分岐予測処理とは独立して、パイプライン処理が行われている間実行される。
【０１３６】
例えば、学習処理が開始されると、学習処理部42は、ステップＳ241において、演算部24より取得した情報に基づいて、分岐方向が確定したか否か、すなわち、演算部24において分岐命令が実行されその実行結果が得られたか否かを判定し、得られたと判定するまで待機する。分岐命令の実行結果は、演算部24より分岐予測部21に供給される。分岐命令の実行が終了し、分岐方向が確定したと判定した場合、学習処理部42は、ステップＳ243において、A3PBPのステージ0において算出された予測値と演算部24より取得した分岐命令の実行結果である分岐結果とが等しいか否か(予測が当たったか否か)を判定する。予測値と分岐結果とが等しい(予測が当たった)と判定した場合、学習処理部42は、処理をステップＳ244に進め、学習処理部42は、予測値を算出する際の重み付き分岐結果累算値の総和と閾値との加算結果の絶対値が、予め定められた所定の値である偏向値θより小さいか否かを判定する。すなわち、その予測が十分に確信を持ってなされたものであるか否か(予測値の信頼性が高いか否か)を判定する。
【０１３７】
ステップＳ244において、予測時の計算値の絶対値が偏向値θより小さい、つまり、予測値の信頼性が低いと判定した場合、学習処理部42は、処理をステップＳ245に進める。また、ステップＳ243において、予測値と分岐結果とが等しくない(予測が外れた)と判定した場合、学習処理部42は、処理をステップＳ245に進める。
【０１３８】
ステップＳ245において、学習処理部42は、今回の分岐方向と値が一致するグローバル履歴84の分岐結果(GHR［ｐ］)に対応する重みの値に「1」を加算するように、レジスタ44に保持されている重みテーブル82を更新する。
【０１３９】
ステップＳ245の処理を終了すると、学習処理部42は、ステップＳ246に処理を進め、各重みテーブルの、今回の分岐方向と値が一致しないグローバル履歴84の分岐結果(GHR［ｐ］)に対応する重みの値に「1」を減算するように、レジスタ44に保持されている重みテーブル82を更新する。
【０１４０】
換言すると、学習処理部42は、ステップＳ245およびステップＳ246の処理により、図8に示されるA3PBPの各重みテーブル82の、今回の分岐予測処理において読み出される値に「1」を加算または減算することにより、分岐方向と値が一致するグローバル履歴の重みを増し、分岐方向と一致しないグローバル履歴の重みを低減させるように、グローバル履歴84の各分岐結果(GHR［ｐ］)の重みを再調整する(更新する)。
【０１４１】
ステップＳ246の処理を終了すると、学習処理部42は、学習処理を終了する。また、ステップＳ244において、予測時の計算値の絶対値が偏向値θ以上である、つまり、予測値の信頼性が高いと判定した場合、学習処理部42は、学習処理を終了する。
【０１４２】
以上より、本実施形態によれば、分岐予測部21は、重みの読み出しに、実行パス履歴85の最新のアドレスＡ［0］に加えてローカル履歴を反映させた多重化アドレス(MA)を利用することにより、重みの負の衝突を回避し、予測精度を向上させることができる。さらに、閾値の選択にもローカル履歴を反映させた多重化アドレス(MA)を利用するので、分岐予測部21は、閾値においても同様に重みの負の衝突を回避し、予測精度をさらに向上させることができる。また、分岐予測部21は、閾値の算出において、閾値の候補の読み出しと並行して、ローカル履歴86の分岐結果の読み出しを行うので、閾値の算出の処理時間(レイテンシ)を低減させることができる。また、最新の分岐結果に近いグローバル履歴84ＧＨＲ〔ｐ〕及びターゲットアドレスに近い実行パス履歴85のアドレスほど後のステージで使用されるパイプライン構造としたため、それぞれのステージにおいて処理を行う際に、演算結果に基づいて更新されたグローバル履歴84ＧＨＲ〔ｐ〕及びよりターゲットアドレスに近いアドレスに更新された実行パス履歴85Ａ〔0〕を用いることができるため、予測精度が向上する。さらに、分岐予測部21は、パイプライン処理により重みの読み出しにかかるレイテンシを隠蔽することができる。また、分岐予測部21は、ターゲットアドレスの変わりにターゲットアドレスと相関の強い実行パス履歴85の最新のアドレスＡ［0］を用いて重みテーブル82より重みを読み出すことにより、事前計算を可能にし、パイプライン処理を実現することができる。さらに、分岐予測部21は、連鎖的に同じインデックスを使用して重み読み出しを行わないようなパイプライン構造(図8)を実現するので、PTBPのように予測に関係の無い実行パス履歴が及ぼす悪影響を最小限に抑えることができる。
【０１４３】
以上のように、分岐予測部21は、予測に必要な時間を抑制するとともに分岐予測の精度を向上させることができる。
【０１４４】
以上のような分岐予測部21(A3PBP)による分岐予測処理の予測精度をシミュレーション結果について説明する。
【０１４５】
A3PBPとの評価対象としてgshare分岐予測器、グローバル／ローカルパーセプトロン分岐予測器(Global/Local Perceptron)、パスベースドパーセプトロン分岐予測器(Path-Based Paerceptron)、アヘッドパイプラインドピースワイズリニア分岐予測器(Ahead Pipelined Piecewise Linear)、並びに、PTBPの8本鎖(PTBP Eight Chain)を用いた。
【０１４６】
シミュレーションは、SPECCINT2000の12種類のベンチマークをSimCoreシミュレータで1億命令程度実行した際にトレースしたデータを、各分岐予測器をシミュレートしたプログラムで処理し、その予測ミス率を測定することにより行った。評価する分岐予測器の記憶容量は、8KBから256KBまでの6段階で制限し、各容量での予測ミス率の違いを評価した。図21の表は、各分岐予測器が各記憶容量で使用するグローバル履歴長の値(バジェットサイズ)の一覧を示している。このシミュレーションにおいて、重みは原則8ビットを使用したが、A3PBPの8KB，16KB，32KBに関しては7ビットを使用した。また、パーセプトロン分岐予測器の学習閾値は全て2.1×(GHR＋1)とした。
【０１４７】
以上のような条件において行ったシミュレーション結果をグラフ化したものを図22に示す。図22のグラフは、各予測器の記憶容量別の予測ミス率の関係を示すグラフである。図22に示されるように、黒丸の点と実線の曲線で示されるA3PBP(AAAPBP)の予測ミス率は全ての記憶容量において、他の、どの分岐予測器の予測ミス率よりも低い。例えば、A3PBP(AAAPBP)の予測ミス率は、8本鎖のPTBP(PTBP Eight Chain)のそれと比較すると、平均で5．7％，最高で6．4％(16KB構成時)も低減されている。以上のようにA3PBPは他の分岐予測器よりもテーブルの使用効率が高い。つまり、分岐予測部21は、分岐予測の精度を向上させることができる。
【０１４８】
なお、以上においては、分岐予測部21は、図8に示されるようなA3PBPによる分岐予測パイプライン処理を実現するように説明したが、例えば、図23に示されるように、ローカル履歴86(ローカル履歴86の分岐結果を反映させた多重化アドレス83)を用いないようにしてもよい。
【０１４９】
図23の例の場合、ステージ0に設けられた、閾値を選択するための重みテーブル182−0と、グローバル履歴84の最新の分岐結果84−1(GHR［0］)の重みを選択するための重みテーブル182−1は、ローカル履歴86(多重化アドレス83)を用いずに、実行パス履歴85の最新のアドレスＡ［0］のみをインデックスとして閾値を選択するテーブルである。また、それら以外の、ステージｎからステージ1(図23の例の場合、ｎ＝2)の各重みテーブル182−2乃至182−ｎＭは、それぞれ、ローカル履歴86の分岐結果(多重化アドレス83)の代わりに、重み付けの相手となるグローバル履歴84の分岐結果84−(ｉ×ｊ−ｉ)と履歴順が等しい、実行パス履歴85のアドレスＡ[ｉ×ｊ−ｉ]を用い、そのアドレスＡ[ｉ×ｊ−ｉ]と最新のアドレスＡ[0]との排他的論理和をインデックスとしてグローバル履歴84の分岐結果84−(ｉ×ｊ−ｉ)の重みを選択するテーブルである。
【０１５０】
つまり、図23の例の場合、重み選択部61は、ステージｎからステージ1の各グローバル履歴84の分岐結果(GHR［ｐ］)について、実行パス履歴85の最新のアドレスＡ［0］と、グローバル履歴84の分岐結果84−ｐ(GHR［ｐ］)と履歴順ｐが等しい実行パス履歴85のアドレス(Ａ［ｐ］)の排他的論理和、または実行パス履歴85の最新のアドレスＡ［0］のみ、のいずれかをインデックス(少なくとも実行パス履歴85の最新のアドレスＡ［0］を反映したインデックス)として、分岐結果84−ｐに対応する重みテーブル182より重みを選択して読み出す。
【０１５１】
ｘを任意の自然数とすると、上述のステージｎからステージ1においては、分岐結果GHR[ｘ]に対応するアドレスとして、このアドレスＡ[ｘ]を用いている。もちろん、Ａ[ｘ]以外の任意のアドレスを分岐結果GHR［ｘ］に対応させるようにしてもよい。ただし、この対応関係は、予測処理の開始前に予め決められている。
【０１５２】
この場合、図8を参照して説明したA3PBPによる予測処理よりも、予測精度は低下するが、最新の分岐結果に近いグローバル履歴84ＧＨＲ〔ｐ〕及びターゲットアドレスに近い実行パス履歴85のアドレスほど後のステージで使用されるパイプライン構造であるため、それぞれのステージにおいて処理を行う際に、演算結果に基づいて更新されたグローバル履歴84ＧＨＲ〔ｐ〕及びよりターゲットアドレスに近いアドレスに更新された実行パス履歴85Ａ〔0〕を用いることによって予測精度の向上を実現することができる。
【０１５３】
また、図24に示されるように、ローカル履歴86(ローカル履歴86の分岐結果を反映させた多重化アドレス83)を用いて閾値を選択する方法を、従来のPTBPに適用することも可能である。
【０１５４】
図24の例の場合、ステージ0の構成は、図8に示されるA3PBPのステージ0の構成と同様である。ステージｎからステージ1の構成は、図3を参照して説明したパイプラインドPTBPの構成と同様であり、重みテーブル201−1乃至重みテーブル201−2Ｎは、それぞれ、実行パス履歴85の最新のアドレスＡ［0］と実行パス履歴85のアドレスＡ［ｊ］の排他的論理和をインデックスとして重みが読み出される。各テーブルより読み出された重みは、それぞれ、乗算器202−1乃至乗算器202−2Ｎにおいて、グローバル履歴84の最新の分岐結果GHR［0］と乗算され、累算される。この重み付き分岐結果値は、ステージ0において総和が求められ、その総和が閾値と加算され予測値が求められる。
【０１５５】
このようにすることによっても、分岐予測部21は、予測精度を向上させることができる。ただし、この場合、図8を参照して説明したA3PBPによる予測処理よりも、予測精度は低下する。
【０１５６】
以上のような各構成において行ったシミュレーション結果をグラフ化したものを図25に示す。図25のグラフは、各予測器の記憶容量別の予測ミス率の関係を示すグラフである。シミュレーション方法および各条件は、図22の場合と同様である。ここでは、図25に示されるように、図8に示されるA3PBP、図23に示される、ローカル履歴86を用いない新パイプライン分岐予測器(New Pipeline)、PTBPの8本鎖(PTBP8x)、並びに、図24に示される、PTBPの閾値選択にローカル履歴86(多重化アドレス83)を用いるようにした分岐予測器(PTBP+MA)を比較した。
【０１５７】
図25に示されるように、予測ミス率は、黒のひし形の点と実線の曲線で示されるA3PBP，PTBP＋MA，New Pipeline，PTBP8xの順で低い。すなわち、図8に示されるA3PBPの構成の内、ローカル履歴86(多重化アドレス83)を用いて重み読み出しや閾値読み出しを行う構成と、ステージｎからステージ1のパイプライン構成のいずれも、従来のPTBP8xの場合よりも予測ミス率を低減させることができる。従って、分岐予測部21は、それらのうち、少なくともいずれか一方を適用することにより、分岐予測の精度を向上させることができ、さらに、それらを図8に示されるように併用するようにすることにより、予測ミス率をさらに低減させ、分岐予測の精度をさらに向上させることができる。
【０１５８】
なお、以上において、閾値の選択において、閾値の候補の読み出しとローカル履歴86からの分岐結果の読み出しを並行して行うように説明したが、これに限らず、例えば、図26に示されるように、最初にローカル履歴86より分岐結果を読み出して多重化アドレス83を生成し、その多重化アドレス83をインデックスとして閾値選択用の重みテーブル82−0より重み(閾値)を読み出すようにしてもよい。
【０１５９】
図26は、図8のステージ0の構成例を示すブロック図である。
【０１６０】
図26の例の場合、実行パス履歴85の最新のアドレスＡ［0］は、ローカル履歴86(LHT)のインデックスとして使用され、分岐結果の選択に用いられる。ローカル履歴86(LHT)より読み出された分岐結果(LH)は多重化アドレス生成部221に供給される。多重化アドレス生成部221には、また、実行パス履歴85の最新のアドレスＡ［0］も供給される。多重化アドレス生成部221は、実行パス履歴85の最新のアドレスＡ［0］の下位ビットを削除して分岐結果を挿入することにより、多重化アドレス83(MA)を生成する。生成された多重化アドレス83は、重みテーブル82−0のインデックスとして使用され、閾値の読み出しに使用される。この場合、多重化アドレス生成部221はステージ0処理部52を構成する。
【０１６１】
このように閾値を選択する前に多重化アドレス83を生成しても、分岐予測部21は、図9の場合と同様の結果(閾値)を得ることができる。ただし、この場合、ローカル履歴86からの分岐結果の読み出しと重みの読み出しを並行して行わないため、図8の構成の場合と比較して閾値の算出のレイテンシが増大する。その代わり、ステージ0において多重化アドレス生成部221で生成された閾値選択用の多重化アドレス83は、現在ステージ0で分岐予測を行っている分岐命令の次以降の分岐命令についてのステージｎからステージ1における重み読み出しのための多重化アドレス83に流用することができるので、別途多重化アドレス生成部74を設けて、現在のステージ0処理と並行して多重化アドレスを生成する必要がない。
【０１６２】
図27のフローチャートを参照して、A3PBPのステージ0における閾値選択のための構成が図26に示される構成である場合の、ステージ0処理の流れの例を説明する。このフローチャートは、図15のフローチャートに対応する。
【０１６３】
ステージ0処理が開始されると、予測値算出部73は、ステップＳ261において、レジスタ44−1に保持されている重み付き分岐結果累算値81(REG(1，ｊ))を全て読み出し、加算器111を用いて、それらの総和を算出する。この処理と並行して、閾値算出部72は、ステップＳ262において、実行パス履歴85の最新のアドレスＡ［0］をインデックスとしてローカル履歴86(LHT［Ａ［0］］)より分岐結果(LHT(Ａ［0］))を読み出す。読み出された分岐結果は、実行パス履歴85の最新のアドレスＡ［0］とともに、多重化アドレス生成部221に供給される。多重化アドレス生成部221は、ステップＳ263において、供給された実行パス履歴85の最新のアドレスＡ［0］の下位2ビットを削除し、ステップＳ264において、削除されたその2ビットに分岐結果を挿入し、多重化アドレス83(MA［0］)を生成する。
【０１６４】
ステップＳ265において、閾値算出部72は、多重化アドレス生成部221において生成した多重化アドレス83(MA［0］)をインデックスとして閾値用の重みテーブル82−0(WT［0，MA［0］］)より閾値を取得する。
【０１６５】
ステップＳ266において、予測値算出部73は、加算器113を用いて重み付き分岐結果累算値の総和と閾値を加算し、ステップＳ267において、加算結果の最上位ビットの値を反転させ、ステップＳ268において、その反転結果(最上位ビット)を予測値として出力する。
【０１６６】
多重化アドレス生成部74は、ステップＳ269において、ステップＳ264において生成した多重化アドレス83(MA［0］)を更新処理部43に出力し、更新処理部43によりレジスタの多重化アドレス83が更新される。
【０１６７】
以上のように、ステージ0処理部52は、多重化アドレス83を閾値選択の前に算出するようにすることもできる。
【０１６８】
また、以上においては、図8のステージ1の上から1本目の鎖において、グローバル履歴84の最新の分岐結果GHR［0］を用いるように説明したが、これに限らず、例えば、ステージ0において1回前の処理において得られた予測値を用いるようにしてもよい。つまり、グローバル履歴84の分岐結果を用いる代わりに予測値を用いることにより、予測処理部41は、演算部24(図5)において分岐結果が確定する前に重み付き分岐結果の累算を行うことができる。
【０１６９】
図28は、この場合のA3PBPの構成の例を示す模式図である。
【０１７０】
この図28の例の場合、ステージ1の重みテーブル82−1からは、実行パス履歴85の最新のアドレスＡ［0］をインデックスとして重みが読み出され、予測値が分岐成立(「1」)、不成立(「−1」)の両方向を想定して、それぞれの値に対して読み出した重みで重み付けされる。そして、それぞれに重み付けされた値が加算器241と加算器242に供給され、加算器241および加算器242は、それぞれに重み付けされた値と、レジスタ44−2より読み出した重み付き分岐結果累算値81(REG(2，1))とを加算し、加算結果がセレクタ243に供給される。
【０１７１】
セレクタ243は、予測値(前の分岐命令に対する分岐予測におけるステージ0処理により得られた予測値)に基づいて、加算器241および加算器242において算出された2つの重み付き分岐結果累算値81のいずれか一方を選択してレジスタ44−1に保持させる(REG1，1)。
【０１７２】
以上のようにすることにより、演算部24(図5)において分岐結果が確定する前に重みの累算を行うことができる。
【０１７３】
なお、以上においては、セレクタ243をステージ1に設けるように説明したが、このセレクタ243をステージ0に設け、加算器241および加算器242の両方の加算結果をレジスタ44−1に保持させるようにしてもよい。その場合、セレクタ243は、ステージ0処理において、前回算出された予測値を用いて、このレジスタ44−1に保持されている2つの重み付き分岐結果累算値81、すなわち、加算器241において算出された加算結果と、加算器242において算出された加算結果のうち、いずれか一方を選択し、その選択した値を、上から1本目の鎖の重み付き分岐結果累算値81として加算器111に供給する。
【０１７４】
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、図29に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。
【０１７５】
図29において、パーソナルコンピュータ300のCPU301は、ROM(Read Only Memory)302に記憶されているプログラム、または記憶部313からRAM(Random Access Memory)303にロードされたプログラムに従って各種の処理を実行する。RAM303にはまた、CPU301が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１７６】
CPU301、ROM302、およびRAM303は、バス304を介して相互に接続されている。このバス304にはまた、入出力インタフェース310も接続されている。
【０１７７】
入出力インタフェース310には、キーボード、マウスなどよりなる入力部311、CRTやLCDなどよりなるディスプレイ、並びにスピーカなどよりなる出力部312、ハードディスクなどより構成される記憶部313、モデムなどより構成される通信部314が接続されている。通信部314は、インターネットを含むネットワークを介しての通信処理を行う。
【０１７８】
入出力インタフェース310にはまた、必要に応じてドライブ315が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア321が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部313にインストールされる。
【０１７９】
上述した一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
【０１８０】
この記録媒体は、例えば、図29に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク(フレキシブルディスクを含む)、光ディスク(CD-ROM,DVDを含む)、光磁気ディスク(MDを含む)、もしくは半導体メモリなどよりなるリムーバブルメディア321により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM302や、記憶部313に含まれるハードディスクなどで構成される。
【０１８１】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並的あるいは個別に実行される処理をも含むものである。
【０１８２】
また、本明細書において、システムとは、複数のデバイス(装置)により構成される装置全体を表すものである。
【０１８３】
なお、以上において、一つの装置として説明した構成を分割し、複数の装置として構成するようにしてもよい。逆に、以上において複数の装置として説明した構成をまとめて一つの装置として構成されるようにしてもよい。また、各装置の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置の構成の一部を他の装置の構成に含めるようにしてもよい。つまり、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
産業上の利用可能性
【０１８４】
本発明は、分岐予測器に適用することが可能である。
【符号の説明】
【０１８５】
11  CPU，  21  分岐予測部，  41  予測処理部，  42  学習処理部，  43  更新処理部，  51  ステージ1−ｎ処理部，  52  ステージ0処理部，  61  重み選択部，  62  重み付き分岐結果値累算部，  72  閾値算出部，  73  予測値算出部，  74  多重化アドレス生成部，  81  重み付き分岐結果累算値，  82  重みテーブル，  83  多重化アドレス，  84  グローバル履歴，  85  実行パス履歴，  86  ローカル履歴，  87  ターゲットアドレス，  101  反転部，  102  加算器，  111  加算器，  112  セレクタ，  113  加算器，  221  多重化アドレス生成部，  241  加算器，  242  加算器，  243  セレクタ
【図１】
0005167489.tif 000004
【図２】
0005167489.tif 000005
【図３】
0005167489.tif 000006
【図４】
0005167489.tif 000007
【図５】
0005167489.tif 000008
【図６】
0005167489.tif 000009
【図７】
0005167489.tif 000010
【図８】
0005167489.tif 000011
【図９】
0005167489.tif 000012
【図１０】
0005167489.tif 000013
【図１１】
0005167489.tif 000014
【図１２】
0005167489.tif 000015
【図１３】
0005167489.tif 000016
【図１４】
0005167489.tif 000017
【図１５】
0005167489.tif 000018
【図１６】
0005167489.tif 000019
【図１７】
0005167489.tif 000020
【図１８】
0005167489.tif 000021
【図１９】
0005167489.tif 000022
【図２０】
0005167489.tif 000023
【図２１】
0005167489.tif 000024
【図２２】
0005167489.tif 000025
【図２３】
0005167489.tif 000026
【図２４】
0005167489.tif 000027
【図２５】
0005167489.tif 000028
【図２６】
0005167489.tif 000029
【図２７】
0005167489.tif 000030
【図２８】
0005167489.tif 000031
【図２９】
0005167489.tif 000032