(57)【要約】【課題】分岐予測ミス発生時に分岐予測において用いるデータを短時間で用意する。【解決手段】演算処理装置は、命令アドレスに対応する複数のインデックスそれぞれに対応して重み値を格納する重みテーブルと、命令フェッチアドレスに応じて重みテーブルから読み出された重み値に基づいて第１の演算と第２の演算とを行い、第１の演算により命令フェッチアドレスに対する分岐予測の基になる第１の値を計算するとともに、第２の演算により将来の分岐予測の基になる第２の値を計算する第１の重み演算部と、完了した分岐命令の完了命令アドレスに応じて重みテーブルから読み出された重み値に基づいて第２の演算に相当する第３の演算を第２の演算と並行して行うことにより、分岐予測失敗時に第２の値の代用値又は更新値となる第３の値を計算する第２の重み演算部とを含み、分岐予測失敗時に第１の重み演算部に格納される第２の値を第３の値で置き換える。【選択図】図５
2020027533.tif 000002
【特許請求の範囲】
【請求項１】
命令アドレスに対応する複数のインデックスそれぞれに対応して重み値を格納する重みテーブルと、
命令フェッチアドレスに応じて前記重みテーブルから読み出された前記重み値に基づいて第１の演算と第２の演算とを行い、前記第１の演算により前記命令フェッチアドレスに対する分岐予測の基になる第１の値を計算するとともに、前記第２の演算により将来の分岐予測の基になる第２の値を計算する第１の重み演算部と、
完了した分岐命令の完了命令アドレスに応じて前記重みテーブルから読み出された前記重み値に基づいて前記第２の演算に相当する第３の演算を前記第２の演算と並行して行うことにより、分岐予測失敗時に前記第２の値の代用値又は更新値となる第３の値を計算する第２の重み演算部と、
を含み、分岐予測失敗時に前記第１の重み演算部に格納される前記第２の値を前記第３の値で置き換える演算処理装置。
【請求項２】
前記第１の重み演算部は前記命令フェッチアドレスに応じて前記重みテーブルから読み出された前記重み値と前記第１の値に応じた分岐予測方向とに基づいて前記第２の演算を行うことにより前記第２の値を計算し、
前記第２の重み演算部は前記完了命令アドレスに応じて前記重みテーブルから読み出された前記重み値と前記完了した分岐命令の分岐方向とに基づいて前記第３の演算を行うことにより前記第３の値を計算する
請求項１記載の演算処理装置。
【請求項３】
前記重みテーブルの前記重み値を更新する重みテーブル更新部を更に含み、
前記第２の重み演算部は、前記第３の値から求めた値に基づいて、前記完了命令アドレスに対応する前記重み値の更新の要否を示す第４の値を生成し、
前記重みテーブル更新部は、前記第４の値が前記重み値の更新要を示す場合に前記重みテーブルの前記重み値を更新する
請求項１又は２記載の演算処理装置。
【請求項４】
前記第２の重み演算部は、連続する複数の前記完了命令アドレスにそれぞれ対応する前記第３の値を複数のバッファに格納しておき、前記連続する複数の完了命令アドレス間の間隔に応じて前記複数のバッファのうちの１つのバッファを選択し、前記選択された１つのバッファに格納される前記第３の値に基づいて前記第４の値を生成する、請求項３記載の演算処理装置。
【請求項５】
前記重みテーブルは、前記命令フェッチアドレスを入力する第１のポートと、前記完了命令アドレスを入力する第２のポートとを含む、請求項３又は４記載の演算処理装置。
【請求項６】
前記重みテーブルは、前記重み値の更新のために用いる複数の前記完了命令アドレスを入力する第３のポートを更に含む、請求項５記載の演算処理装置。
【請求項７】
命令アドレスに対応する複数のインデックスそれぞれに対応して重み値を格納する重みテーブルから命令フェッチアドレスに応じて読み出された前記重み値に基づいて第１の演算と第２の演算とを行い、前記第１の演算により前記命令フェッチアドレスに対する分岐予測の基になる第１の値を計算するとともに、前記第２の演算により将来の分岐予測の基になる第２の値を計算し、
完了した分岐命令の完了命令アドレスに応じて前記重みテーブルから読み出された前記重み値に基づいて前記第２の演算に相当する第３の演算を前記第２の演算と並行して行うことにより、分岐予測失敗時に前記第２の値の代用値又は更新値となる第３の値を計算し、
分岐予測失敗時に前記第２の値を前記第３の値で置き換える
各段階を含む演算処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願開示は、演算処理装置及び演算処理装置の制御方法に関する。
【背景技術】
【０００２】
プロセッサの高速化技術のひとつとして、分岐予測技術によるパイプライン最適化技術がある。分岐予測技術では分岐予測機構が、実行される分岐命令に対して、分岐命令の分岐が成立する(TAKEN)又は成立しない(NOT_TAKEN)のいずれかを示す分岐方向と、分岐命令のターゲットアドレス（分岐先アドレス）とを予測する。分岐命令の処理によって実際に分岐したか否かが判定される前に、予測に応じて先行して後続命令の処理を進めていくことが可能となる。
【０００３】
分岐予測が失敗した場合、先行して実行されていた後続命令の処理を全て破棄し、分岐命令の実際の実行結果に応じた正しい後続命令について処理を実行し直さなければならないため、性能ロスとなる。したがってプロセッサの性能向上のためには、分岐予測の精度を高めることが重要となる。
【０００４】
分岐予測方式には、分岐予測対象の命令に対して、それ以前に実行された所定数Ｎ個（Ｎ：正の整数）の分岐命令のそれぞれの分岐方向を示すグローバル履歴を用いる方式がある。ピースワイズ・リニア（Piecewise-Linear）方式では、過去のＮ個の分岐命令に対するグローバル履歴と、予測対象命令の分岐方向と過去のＮ個の分岐命令の分岐方向との相関を示すＮ個の重み値とに基づいて、予測対象命令の分岐方向を予測する。その際、Ｎ個の重み値として、予測対象命令までの命令実行経路を反映した重み値を用いることにより、分岐予測精度が高められている。
【０００５】
ピースワイズ・リニア方式ではＮ個の重みテーブルを用いる。各重みテーブルには、命令アドレスの一部をインデックスとして、複数のインデックスのそれぞれに対応する重み値が格納されている。１つの分岐命令について分岐予測する毎に、当該予測対象命令の命令アドレスの一部をインデックスとして用いてＮ個の重みテーブルの各々を検索することにより、当該予測対象命令に対応するＮ個の重み値Ｗｉ（ｉ＝１〜２０）を得る。これらＮ個の重み値の各々に、予測対象分岐命令に対する予測分岐結果の値Ｘ（分岐成立なら＋１、分岐不成立なら−１）を掛け、掛け算して得られる重み演算結果Ｍｉ（＝Ｗｉ・Ｘ）を得る。Ｎ個の重みテーブルそれぞれに対応してＮ個のフリップフロップＢＷＳＵＭｉ（ｉ＝１〜２０）が用意されており、フリップフロップＢＷＳＵＭｉ＋１に格納されている値に対して上記の重み演算結果Ｍｉを加算し、加算結果をフリップフロップＢＷＳＵＭｉに格納する。但しフリップフロップＢＷＳＵＭＮにはＭＮをそのまま格納する。
【０００６】
上記計算の結果、ある分岐命令を分岐予測した際にフリップフロップＢＷＳＵＭＮに格納されたＭＮに対して、その後順番に分岐予測される１９個の分岐命令について計算されたＭＮ−１〜Ｍ１が順次加算されていく。最終的に、フリップフロップＢＷＳＵＭ１の格納値ＳＵＭは以下の値となる。
【０００７】
ＳＵＭ＝ＭＮ＋ＭＮ−１＋・・・Ｍ２＋Ｍ１
ある任意のタイミングでの格納値ＳＵＭは、過去に分岐予測したＮ個の分岐命令のそれぞれに対応するＮ個の重み値Ｗｉに、Ｎ個の分岐命令のそれぞれの予測分岐結果の値（＋１又は−１）を掛け合わせた値の積和となっている。
【０００８】
上記Ｎ個の重みテーブルと同一構成を有し、別個設けられた１個の重みテーブルに対して、現在の予測対象命令の命令アドレスの一部をインデックスとして用いて検索することにより、当該予測対象命令に対応する重み値Ｗ０を得る。分岐方向の予測においては、ＳＵＭ＋Ｗ０が正であるならば分岐成立と予測し、ＳＵＭ＋Ｗ０が負であるならば分岐不成立と予測する。
【０００９】
各重み値Ｗｉ（ｉ＝１〜２０）は予測対象命令の分岐方向と過去のＮ個の分岐命令の分岐方向との正の相関を示す値に設定されている。つまり予測対象命令の分岐方向と過去の分岐命令の分岐方向とが同一方向である傾向が、逆方向である傾向よりも強い程、重み値はより大きな正の値となる。逆に、予測対象命令の分岐方向と過去の分岐命令の分岐方向とが逆方向である傾向が、同一方向である傾向よりも強い程、重み値はより大きな負の値となる。
【００１０】
Ｍｉを計算する際には、各重み値Ｗｉに対して予測分岐結果の値（分岐成立なら＋１、分岐不成立なら−１）を掛けている。したがって正の相関が高い過去の命令が分岐成立であった場合には、ＳＵＭに対して正の方向に対するバイアスがかかり、正の相関が高い過去の命令が分岐不成立であった場合には、ＳＵＭに対して負の方向に対するバイアスがかかる。また負の相関が高い過去の命令が分岐成立であった場合には、ＳＵＭに対して負の方向に対するバイアスがかかり、負の相関が高い過去の命令が分岐不成立であった場合には、ＳＵＭに対して正の方向に対するバイアスがかかる。また当該予測対象命令に対応する重み値Ｗ０は、当該予測命令の過去の分岐方向を示す値（分岐成立なら＋１、分岐不成立なら−１）と正の相関を有する値に設定されている。したがって、ＳＵＭ＋Ｗ０が正であるならば予測対象命令について分岐成立である可能性が高く、ＳＵＭ＋Ｗ０が負であるならば予測対象命令について分岐不成立である可能性が高くなる。
【００１１】
上記の計算においては、分岐予測するために予測対象命令に対して実行する処理は、重みテーブルから重み値Ｗ０を読み出し、フリップフロップＢＷＳＵＭ１の格納値ＳＵＭに重み値Ｗ０を加算し、加算結果と０との比較を行うのみである。このときの加算処理は２入力の加算を一回実行するだけで済むので、分岐予測のレイテンシを１サイクルとして実現することができる。
【００１２】
分岐予測において予測ミスが発生した場合、先行して実行されていた後続命令の処理を全て破棄し、分岐命令の実際の実行結果に応じた正しい後続命令について処理を実行し直す必要がある。このとき、分岐予測ユニットにおいて上記の中間演算結果を格納するＮ個のフリップフロップの格納値は、誤って先行実行された分岐命令の処理結果により誤った値になってしまっている。したがってＮ個のフリップフロップの格納値を、正しい後続命令及びそれに続く命令の処理において実行する分岐予測のために用いることはできない。
【００１３】
従来のピースワイズ・リニア方式では、完了した過去Ｎ個の分岐命令の履歴を保持しておき、当該履歴を用いて、正しい後続命令及びそれに続く命令の処理において実行する分岐予測のために用いるＮ個のフリップフロップの格納値を改めて計算している。具体的には、過去のＮ個の完了分岐命令に対応するＮ個の重み値ＷｉにＮ個の完了分岐結果の値を掛け合わせて積和を求める演算を、分岐予測ミス発生時に改めて実行している。この場合、分岐予測ミス発生時に２入力の加算をＮ−１回実行することが必要になり、分岐予測のレイテンシが増大してしまう。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開平６−０８９１７３号公報
【特許文献２】特開２０１７−０２７４５１号公報
【非特許文献】
【００１５】
【非特許文献１】S. McFarling: "Combining Branch Predictions", WRL Technical Note TN-6 (1993)
【非特許文献２】E. Sprangle and R. S. Chappell and M. Alsup and Y. N. Patt: "The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference", International Symposium on Computer Architecture - ISCA , pp. 284-291, 1997
【非特許文献３】D. A. Jimenez , Calvin Lin, "Dynamic Branch Prediction with Perceptrons," Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.197, January 20-24, 2001
【非特許文献４】D. A. Jimenez: "Neural methods for dynamic branch prediction", ACM Transactions on Computer Systems (TOCS) Volume 20 Issue 4, November 2002 Pages 369-397
【非特許文献５】D. A. Jimenez, "Fast Path-Based Neural Branch Prediction," Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.243, December 03-05, 2003
【非特許文献６】D. A. Jimenez, "Piecewise Linear Branch Prediction," Proceedings of the 32nd annual international symposium on Computer Architecture, p.382-393, June 04-08, 2005
【非特許文献７】D. A. Jimenez: "Oh-snap: Optimized hybrid scaled neural analog predictor". In Proceedings of the 3rd Championship on Branch Prediction, http://www.jilp.org/jwac-2/, 2011
【発明の概要】
【発明が解決しようとする課題】
【００１６】
以上を鑑みると、分岐予測ミス発生時に後続命令に対する分岐予測において用いるデータを短時間で用意することが望まれる。
【課題を解決するための手段】
【００１７】
演算処理装置は、命令アドレスに対応する複数のインデックスそれぞれに対応して重み値を格納する重みテーブルと、命令フェッチアドレスに応じて前記重みテーブルから読み出された前記重み値に基づいて第１の演算と第２の演算とを行い、前記第１の演算により前記命令フェッチアドレスに対する分岐予測の基になる第１の値を計算するとともに、前記第２の演算により将来の分岐予測の基になる第２の値を計算する第１の重み演算部と、完了した分岐命令の完了命令アドレスに応じて前記重みテーブルから読み出された前記重み値に基づいて前記第２の演算に相当する第３の演算を前記第２の演算と並行して行うことにより、分岐予測失敗時に前記第２の値の代用値又は更新値となる第３の値を計算する第２の重み演算部とを含み、分岐予測失敗時に前記第１の重み演算部に格納される前記第２の値を前記第３の値で置き換える。
【発明の効果】
【００１８】
少なくとも１つの実施例によれば、分岐予測ミス発生時に後続命令に対する分岐予測において用いるデータを短時間で用意することができる。
【図面の簡単な説明】
【００１９】
【図１】図１は、プロセッサの構成の一例を示す図である。
【図２】図２は、命令実行のパイプラインの各ステージを示す図である。
【図３】図３は、分岐予測におけるパイプライン動作を説明する図である。
【図４】図４は、分岐予測結果が分岐成立を示した場合に命令フェッチをキャンセルする様子を示す図である。
【図５】図５は、分岐予測部の構成及びその周辺部との接続の一例を示す図である。
【図６】図６は、重み演算部による計算の進行を模式的に示す図である。
【図７】図７は、重み演算部の構成の一例を示す図である。
【図８】図８は、１つの重みテーブルの構成の一例を示す図である。
【図９】図９は、更新用重み演算部の構成の一例を示す図である。
【図１０】図１０は、重みテーブル更新部による更新演算の進行を模式的に示す図である。
【図１１】図１１は、分岐予測失敗時における重み演算部のデータ更新動作を模式的に示す図である。
【発明を実施するための形態】
【００２０】
以下に、本発明の実施例を添付の図面を用いて詳細に説明する。以下の各図において、同一又は対応する構成要素は同一又は対応する番号で参照し、その説明は適宜省略する。
【００２１】
図１は、プロセッサの構成の一例を示す図である。図１及び以下の同様の図において、各ボックスで示される各回路又は機能ブロックと他の回路又は機能ブロックとの境界は、基本的には機能的な境界を示すものであり、物理的な位置の分離、電気的な信号の分離、制御論理的な分離等に対応するとは限らない。各回路又は機能ブロックは、他のブロックと物理的にある程度分離された１つのハードウェアモジュールであってもよいし、或いは他のブロックと物理的に一体となったハードウェアモジュール中の１つの機能を示したものであってもよい。
【００２２】
図１に示すプロセッサは、分岐予測部１０、命令フェッチアドレス生成部１１、１次命令キャッシュ１２、命令バッファ１３、及び命令デコーダ１４を含む。プロセッサは更に、ＲＳＡ（Reservation Station for Address generate）１５、ＲＳＥ（Reservation Station for Execute）１６、ＲＳＦ（Reservation Station for Floating）１７、及びＲＳＢＲ（Reservation Station for Branch）１８を含む。プロセッサは更に、ＣＳＥ（Commit Stack Entry）１９、オペランドアドレス生成部２０、演算部２１、演算部２２、ネクストプログラムカウンタ（ＰＣ）２３、及びコンディションコードレジスタ（ＣＣ）２４を含む。プロセッサは更に、１次データキャッシュ２５、固定小数点更新バッファ２６、浮動小数点更新バッファ２７、固定小数点レジスタ２８、及び浮動小数点レジスタ２９を含む。
【００２３】
命令フェッチアドレス生成部１１は、命令フェッチアドレスを格納するプログラムカウンタを内蔵し、当該プログラムカウンタの格納値を一定値ずつ増加させることにより、命令フェッチアドレスを順次生成する。１つのフェッチアドレスにより読み出される１つのフェッチラインには１つの命令のみが含まれてもよいし、或いは複数（例えば８個）の命令が含まれてよい。１つのフェッチラインに含まれる命令数は特に限定されるものではない。
【００２４】
分岐予測部１０は、命令フェッチアドレス生成部１１から出力された命令フェッチアドレスを受け取り、命令フェッチと並行して分岐予測を実行する。分岐予測部１０は、受け取った命令フェッチアドレスを基に分岐予測を行い、分岐成立又は分岐不成立を示す分岐方向と分岐先アドレス（ターゲットアドレス）を命令フェッチアドレス生成部１１に返す。予測された分岐方向が分岐成立であった場合、命令フェッチアドレス生成部１１は次の命令フェッチアドレスとして分岐予測部１０によって予測された分岐先アドレスを選択する。分岐予測部１０の構成及び動作については後ほど説明する。
【００２５】
命令フェッチアドレス生成部３９は、命令フェッチアドレスと命令フェッチリクエストとを１次命令キャッシュ１２に発行する。これに応じて、１次命令キャッシュ１２から命令フェッチアドレスに対応するフェッチラインの命令が読み出され、読み出された命令が命令バッファ１３に格納される。
【００２６】
命令バッファ１３は、プログラムの命令順通り即ちインオーダーで格納した命令を命令デコーダ１４に供給する。命令デコーダ１４は、プログラムの命令順通り即ちインオーダーで命令のデコード処理を行い、インオーダーで命令を発行する。この命令発行処理により、命令デコーダ１４は、デコードした命令の種類に従って、それぞれがキュー構造のストレージであるＲＳＡ１５、ＲＳＥ１６、ＲＳＦ１７、又はＲＳＢＲ１８に各命令を示すエントリを作成する。
【００２７】
ＲＳＡ１５は、主記憶オペランドアドレスを生成してロード命令やストア命令を実行するために、作成されたエントリをプログラムの命令順に拘束されず即ちアウトオブオーダーで制御するリザベーションステーションである。ＲＳＡ１５による制御に基づいて、オペランドアドレス生成部２０がアクセス先のアドレスを生成し、１次データキャッシュ２５の当該アドレスに対してロード命令やストア命令が実行される。ロード命令により読み出されたデータは、固定小数点更新バッファ２６又は浮動小数点更新バッファ２７の指定されたレジスタに格納される。
【００２８】
ＲＳＥ１６は、指定されたレジスタのデータに対して指定された固定小数点演算を実行するために、作成されたエントリをアウトオブオーダーで制御するリザベーションステーションである。ＲＳＥ１６は、実行対象の命令が参照するレジスタの依存性をチェックし、依存性のあるレジスタの更新状況や演算部２１のうちの同じ実行資源を用いる命令の実行状況等から、実行資源である演算部２１が命令を実行可能かどうかを判断する。実行可能であるなら、ＲＳＥ１６は、受け取った命令の順序によらずにアウトオブオーダーで各演算部２１に対してレジスタ番号やオペランドアドレス等の命令実行に必要な情報を出力する。ＲＳＥ１６による制御に基づいて、演算部２１が、固定小数点更新バッファ２６及び固定小数点レジスタ２８の指定されたレジスタのデータに対して指定された固定小数点演算を実行し、固定小数点更新バッファ２６の指定されたレジスタに演算結果を格納する。
【００２９】
ＲＳＦ１７は、指定されたレジスタのデータに対して指定された浮動小数点演算を実行するために、作成されたエントリをアウトオブオーダーで制御するリザベーションステーションである。ＲＳＦ１７は、上記説明したＲＳＥ１６と同様の動作により、アウトオブオーダーで各演算部２２に対してレジスタ番号やオペランドアドレス等の命令実行に必要な情報を出力する。ＲＳＦ１７による制御に基づいて、演算部２２が、浮動小数点更新バッファ２７及び浮動小数点レジスタ２９の指定されたレジスタのデータに対して指定された浮動小数点演算を実行し、浮動小数点更新バッファ２７の指定されたレジスタに演算結果を格納する。
【００３０】
ＲＳＢＲ１８は、分岐命令を実行するためのリザベーションステーションである。ＲＳＢＲ１８は、命令デコーダ１４から分岐命令の種別を受け取ると共に、命令アドレスバッファから分岐命令アドレスを受け取り、分岐命令毎にそれぞれの信号を格納する。その後、ＲＳＢＲ１８は、演算部２１から分岐先アドレスや分岐条件となる演算の結果を受け取り、得られた演算結果が分岐条件を満たしていれば分岐成立、満たしていなければ分岐不成立の判断を行い、分岐方向を確定する。
【００３１】
またＲＳＢＲ１８では、上記演算結果が示す実際の分岐アドレス及び分岐方向と分岐予測時の分岐アドレス及び分岐方向とが一致するか否かの判断や、分岐命令の順序関係の制御も行う。ＲＳＢＲ１８は、エントリ作成時に分岐予測時の分岐方向や分岐先アドレスを登録し、演算結果と予測との一致検証を実行後、演算結果によりエントリの置き換えを行う。演算結果と予測とが一致した場合、ＲＳＢＲ１８は、ＣＳＥ１９へ分岐命令の完了報告を出力する。演算結果と予測とが一致しなかった場合、即ち分岐予測失敗の場合、ＲＳＢＲ１８は、ＣＳＥ１９へ分岐命令の完了報告と共に後続命令のキャンセル要求を出力し、命令フェッチアドレス生成部１１へ再命令フェッチ要求と再命令フェッチのアドレスとを出力する。
【００３２】
命令デコーダ１４は更に、全てのデコードされた命令に命令識別子を割り振り、命令識別子を命令の順番通りにＣＳＥ１９に送る。ＣＳＥ１９は、デコードされた命令の命令識別子を命令の実行順番通りに蓄積するキュー構造のストレージと、キューの情報と各処理パイプからの演算完了報告とに基づいてコミット処理を行う完了処理回路とに分けられる。デコーダで解読された命令の命令識別子はＣＳＥ１９のキューに蓄えられ、処理パイプからの完了報告を待つ。各リザベーションステーションがアウトオブオーダーで実行した命令についての完了報告をＣＳＥ１９に送ると、ＣＳＥ１９の完了処理回路が、キューに蓄えられた完了待ちの命令の中から完了報告に対応する命令をインオーダーで開放し、完了を確定させる。
【００３３】
ＣＳＥ１９から開放され完了が確定する命令については、対応する資源の更新を行なう。ロード命令や演算命令等の場合には、固定小数点更新バッファ２６や浮動小数点更新バッファ２７のデータを、固定小数点レジスタ２８や浮動小数点レジスタ２９に転送し、命令実行結果をソフトウェアからアクセス可能なレジスタに反映させる。また同時に、ネクストプログラムカウンタ２３の値を、実行完了して開放される命令の次の命令のアドレスを指し示すように適切な増分だけ変化させる。またコンディションコードレジスタ２４には、分岐命令の実行結果を示すコードが格納される。なおネクストプログラムカウンタ２３は、割り込み発生時等の特殊な場合に用いられるプログラムカウンタであり、プログラムの通常の進行中に用いられることはない。
【００３４】
図２は、命令実行のパイプラインの各ステージを示す図である。図２の上段に示すのは図１に示すプロセッサの命令実行パイプラインの一例であり、下段に示すのは図１に示すプロセッサの分岐予測のパイプラインの一例である。図２に示すように、命令実行と分岐予測とは、並行してそれぞれの処理がパイプラインで処理される。
【００３５】
命令実行におけるパイプラインの各ステージにおける動作は以下の通りである。
ＩＡ：命令フェッチアドレスを決定し一次キャッシュに送る
ＩＴ：キャッシュのＴＬＢにアクセスする
ＩＭ：ＴＬＢのタグのマッチをする
ＩＢ：一次キャッシュから命令を受け取り、命令バッファに送る
Ｒ：命令バッファで命令を受け取り、命令フェッチフェーズでの例外などをチェック
Ｄ：命令を解読する
Ｐ：リザベーションステーションから演算部へ投入する命令を決定する
Ｂ：演算に用いるデータを演算器に投入する
Ｘ１：演算器が演算する
Ｕ：演算の完了報告をＣＳＥへ送る
Ｃ：コミット判定
Ｗ：リソース更新
また分岐予測におけるパイプラインの各ステージにおける動作は以下の通りである。
ＩＡ：命令フェッチアドレスを決定し、分岐予測機構に送る
ＢＴ：重みテーブルから重み値を取り出し、予測対象命令用の重み演算を実行する
ＢＭ：分岐予測
ＢＢ：分岐予測結果転送
ＢＲ：後続する予測対象命令用の重み演算を実行する
ＢＷ１：重みテーブル更新
ＲＩ：分岐予測ミス時の命令復帰
図３は、分岐予測におけるパイプライン動作を説明する図である。ＩＡサイクルにおいて、分岐予測部１０は、命令フェッチアドレスを命令フェッチアドレス生成部１１から受け取る。ＢＴサイクルにおいて、分岐予測部１０は、重みテーブルから重み値を取り出し、予測対象命令用の重み演算を実行する。ＢＭサイクルにおいて、分岐予測部１０は、分岐成立又は分岐不成立の予測を完了する。
【００３６】
パイプライン化された命令フェッチにおいて、命令フェッチアドレスは基本的には命令シーケンス通りに進んでいく。図３において、第１乃至第４の命令フェッチサイクルＩＦＣ１乃至ＩＦＣ４でそれぞれフェッチされた第１乃至第４の命令について実行される各ステージが、同一行内横方向に順番に示されている。図３において、第２の命令フェッチサイクルＩＦＣ２における命令フェッチアドレスは、第１の命令フェッチサイクルＩＦＣ１における命令フェッチアドレス＋フェッチラインサイズとなる。分岐予測結果が得られるＢＭサイクルまでは、命令シーケンス通りに投機的に命令フェッチを実行し続ける。
【００３７】
図４は、分岐予測結果が分岐成立を示した場合に命令フェッチをキャンセルする様子を示す図である。分岐予測部１０がＢＭサイクルにおいて分岐予測結果を分岐成立とした場合、投機実行されていた命令シーケンスに従った命令フェッチはキャンセルされる。図４においては、第１の命令フェッチサイクルＩＦＣ１においてフェッチした第１の命令について、ＢＭサイクルで得られる分岐予測結果が分岐成立となっている。このＢＭサイクル迄に命令シーケンス通りに投機的にフェッチされていた第２及び第３の命令（命令フェッチサイクルＩＦＣ２及びＩＦＣ３においてフェッチされた命令）の実行が、当該ＢＭサイクルにおいてキャンセルされる。第４の命令フェッチサイクルＩＦＣ４における命令フェッチは、第１の命令フェッチサイクルＩＦＣ１でフェッチされた第１の命令に対して予測された分岐先アドレスに対して実行される。
【００３８】
図５は、分岐予測部１０の構成及びその周辺部との接続の一例を示す図である。図５に示す分岐予測部１０は、ターゲットアドレス履歴３０、重みテーブル部３１、完了分岐命令パスヒストリ３２、重み演算部３３、更新用重み演算部３４、重みテーブル更新部３５、及び分岐方向予測部３６を含む。
【００３９】
図５に示されるＲＳＢＲ１８は、前述のように、命令デコーダ１４から分岐命令の種別を受け取ると共に、命令アドレスバッファ１３Ａから分岐命令アドレスを受け取り、分岐命令毎にそれぞれの信号を格納する。ＲＳＢＲ１８は、実際の分岐命令の実行結果と分岐予測結果とが一致した場合、ＣＳＥ１９へ分岐命令の完了報告を出力すると共に、分岐予測部１０に完了した分岐命令の情報を供給する。ＲＳＢＲ１８は、実際の分岐命令の実行結果と分岐予測結果とが一致しなかった場合、ＣＳＥ１９へ分岐命令の完了報告と共に後続命令のキャンセル要求を出力し、命令フェッチアドレス生成部１１へ再命令フェッチ要求と再命令フェッチのアドレスとを出力し、更に、分岐予測部１０に完了した分岐命令の情報を供給する。
【００４０】
命令フェッチアドレス生成部１１から供給された命令フェッチアドレスＦＡＤＲのフェッチラインに含まれる分岐命令に対して、分岐予測部１０が分岐予測を実行する。即ち、命令フェッチアドレスＦＡＤＲのフェッチラインに含まれる分岐命令が、分岐予測対象となる。分岐予測部１０に供給された命令フェッチアドレスＦＡＤＲはターゲットアドレス履歴３０と重みテーブル部３１とに供給される。
【００４１】
ターゲットアドレス履歴３０は、供給される命令フェッチアドレスＦＡＤＲの一部をインデックスとして、複数のインデックスのそれぞれに対応してタグと、ターゲットアドレスと、フラグとが格納されている。命令フェッチアドレスＦＡＤＲがターゲットアドレス履歴３０に供給されると、当該命令フェッチアドレスＦＡＤＲの一部をインデックスとして、当該インデックスに対応するタグと、ターゲットアドレスと、フラグとが得られる。ターゲットアドレス履歴３０では、得られたタグが、命令フェッチアドレスＦＡＤＲのインデックスとして使用しなかったアドレス部分と一致するか否かが判断される。当該判断の結果は分岐方向予測部３６に供給される。
【００４２】
タグが一致した場合、ターゲットアドレス履歴３０は、ターゲットアドレスＴＡＤＲを命令フェッチアドレス生成部１１に供給する。なおターゲットアドレス履歴３０に格納されているターゲットアドレスＴＡＤＲは、実行完了した分岐命令に関する情報がＲＳＢＲ１８から分岐予測部１０に供給されると、当該完了した分岐命令の分岐先アドレスの情報により適宜更新される。
【００４３】
分岐方向予測部３６は、タグ一致の場合、命令フェッチアドレスＦＡＤＲのフェッチラインに分岐命令が含まれると判断し、後述する分岐予測演算により求められた分岐成立又は分岐不成立を示す分岐予測方向ＢＤ＿Ｐを命令フェッチアドレス生成部１１に出力する。タグが一致しない場合、分岐方向予測部３６は、分岐予測方向ＢＤ＿Ｐとして分岐不成立を示す値を命令フェッチアドレス生成部１１に供給する。
【００４４】
なお前述のように、１つの命令フェッチアドレスＦＡＤＲにより読み出される１つのフェッチラインには１つの命令のみが含まれてもよいし、或いは複数（例えば８個）の命令が含まれてよい。複数の命令が含まれる構成とした場合には、命令フェッチアドレスＦＡＤＲに対して、複数個のタグのそれぞれに対してタグ一致を判定してよい。複数個のタグのそれぞれに対してタグ一致を判定した結果に応じて、複数個のターゲットアドレスＴＡＤＲを特定してよい。また後述するように、各重みテーブルには１つのインデックスに対応して複数個の重み値を格納しておき、各重み値について分岐予測等の計算を並行して行ってよい。複数個のタグのそれぞれに対してタグ一致を判定した結果に応じて、タグ一致と判定されたタグに対応する分岐予測結果のみを、命令フェッチアドレス生成部１１に供給してよい。この際、１つの命令フェッチアドレスＦＡＤＲに対応する１つのフェッチラインにおいて、１つでも分岐成立する分岐命令が含まれる場合には、当該１つの命令フェッチアドレスＦＡＤＲに対する分岐予測結果は分岐成立とされる。
【００４５】
以下の説明においては、特に必要がない限りは、１つの命令フェッチアドレスＦＡＤＲの１つのフェッチラインに含まれる１つの命令及びそれに対応する１つの重み値に着目して、分岐予測部１０の動作について説明を行う。
【００４６】
重みテーブル部３１は、命令アドレスに対応する複数のインデックスそれぞれに対応して重み値を格納する重みテーブルである。重みテーブル部３１は、前述のピースワイズ・リニア方式の演算を行うための２１個の重みテーブルＢＷＴ０乃至ＢＷＴ２０を含む。各重みテーブルは同一の構成を有してよい。各重みテーブルには、命令アドレスの一部をインデックスとして、複数のインデックスのそれぞれに対応する重み値が格納されている。命令フェッチアドレスＦＡＤＲが重みテーブル部３１に供給されると、当該命令フェッチアドレスＦＡＤＲの一部をインデックスとして、重みテーブルＢＷＴ０から、当該インデックスに対応する重み値Ｗ０が読み出される。読み出された重み値Ｗ０は、重み演算部３３に供給される。
【００４７】
重み演算部３３は、２０個の重みテーブルＢＷＴ１乃至ＢＷＴ２０のそれぞれに対応して２０個のフリップフロップＢＷＳＵＭｉ（ｉ＝１〜２０）を有する。重み演算部３３は、フリップフロップＢＷＳＵＭ１の格納値ＳＵＭに重み値Ｗ０を加算し、演算結果ＳＵＭ＋Ｗ０を分岐方向予測部３６に供給する。分岐方向予測部３６は、ＳＵＭ＋Ｗ０が正であるならば分岐成立と予測し、ＳＵＭ＋Ｗ０が負であるならば分岐不成立と予測する。
【００４８】
上記の分岐方向を予測するサイクルの後に、重みテーブル部３１では、命令フェッチアドレスＦＡＤＲの一部をインデックスとして用いて、２０個の重みテーブルＢＷＴ１乃至ＢＷＴ２０を並列に検索する。これにより、２０個の重みテーブルＢＷＴ１乃至ＢＷＴ２０から、命令フェッチアドレスＦＡＤＲに対応する２０個の重み値Ｗｉ（ｉ＝１〜２０）を読み出す。読み出された２０個の重み値Ｗｉ（ｉ＝１〜２０）は、重み演算部３３に供給される。
【００４９】
重み演算部３３は、２０個の重み値Ｗｉ（ｉ＝１〜２０）の各々に、命令フェッチアドレスＦＡＤＲに対する予測分岐結果の値Ｘ（分岐成立なら＋１、分岐不成立なら−１）を掛け、掛け算して得られる重み演算結果Ｍｉ（＝Ｗｉ・Ｘ）を得る。重み演算部３３は、フリップフロップＢＷＳＵＭｉ＋１に格納されている値に対して上記の重み演算結果Ｍｉを加算し、加算結果をフリップフロップＢＷＳＵＭｉに格納する。但しフリップフロップＢＷＳＵＭ２０にはＭ２０をそのまま格納する。このフリップフロップへの値の格納は、現在の命令フェッチアドレスＦＡＤＲに対して前述のタグが一致した場合にのみ、実行される。即ち、分岐命令を含むフェッチラインに対してのみ、各フリップフロップＢＷＳＵＭｉの格納値が更新される。
【００５０】
上記計算の結果、分岐命令が含まれるフェッチラインに対してフリップフロップＢＷＳＵＭ２０に格納されたＭ２０に対して、その後順番に分岐予測される分岐命令が含まれる１９個のフェッチラインについて計算されたＭ１９〜Ｍ１が順次加算されていく。最終的に、フリップフロップＢＷＳＵＭ１の格納値ＳＵＭは以下の値となる。
【００５１】
ＳＵＭ＝Ｍ２０＋Ｍ１９＋・・・Ｍ２＋Ｍ１
ある任意のタイミングでの格納値ＳＵＭは、分岐命令が含まれる過去の２０個の命令フェッチアドレスＦＡＤＲのそれぞれに対応する２０個の重み値Ｗｉに、それぞれ対応する２０個の予測分岐結果の値（＋１又は−１）を掛け合わせた値の積和となっている。この値ＳＵＭが、次の命令フェッチアドレスＦＡＤＲに対して分岐予測する際に、ＳＵＭ＋Ｗ０の値を計算するために用いられることになる。
【００５２】
なお以下に説明するように、過去に分岐予測した２０個の命令フェッチアドレスＦＡＤＲは、直近の３つの命令フェッチアドレスＦＡＤＲ（即ち直近の３つのフェッチライン）を除外したものである。これは分岐予測の各ステージの進行タイミングの関係上、直前の３つのフェッチラインを計算対象から除外すれば、フリップフロップＢＷＳＵＭ１に格納するＳＵＭの計算を、この値を用いる分岐予測計算より前に終了させることができるからである。即ち、分岐予測対象のフェッチラインのＢＴステージ（予測対象命令用の重み演算を実行するステージ）の時点で、フリップフロップＢＷＳＵＭ１の格納値が確定しているのは、分岐予測対象のフェッチラインから４つ前のフェッチラインにおける計算値である。
【００５３】
図６は、重み演算部３３による計算の進行を模式的に示す図である。図６において、ＩＡ、ＢＴ、ＢＭ、ＢＢ、ＢＲ等は前述した分岐予測におけるパイプラインの各ステージである。ＦＡＤＲは現在分岐予測対象である命令フェッチアドレスである。ＦＡＤＲ１は現在分岐予測対象である命令フェッチアドレスＦＡＤＲの直前３つの命令フェッチアドレスを除いて、分岐命令を含み分岐予測された最後のフェッチラインの命令フェッチアドレスである。ＦＡＤＲ２は、分岐命令を含みＦＡＤＲ１より前に分岐予測されたフェッチラインのうち、最後のフェッチラインの命令フェッチアドレスである。ＦＡＤＲ２０は、分岐命令を含みＦＡＤＲ１より前に分岐予測されたフェッチラインのうち、最後から１９番目のフェッチラインの命令フェッチアドレスである。
【００５４】
演算器４０は、重みテーブルＢＷＴ２０に対して設けられており、重みテーブルＢＷＴ２０からの重み値Ｗ２０に対して分岐予測方向ＢＤ＿Ｐを掛け算する。掛け算結果はフリップフロップＢＷＳＵＭ２０に格納される。演算器４１は、重みテーブルＢＷＴｉ（ｉ＝１〜１９）の各々に対して設けられており、重みテーブルＢＷＴｉからの重み値Ｗｉに対して分岐予測方向ＢＤ＿Ｐを掛け算し、掛け算結果とフリップフロップＢＷＳＵＭｉ＋１の格納値とを加算する。加算結果はフリップフロップＢＷＳＵＭｉに格納される。
【００５５】
命令フェッチアドレスＦＡＤＲ２０乃至ＦＡＤＲ１に対して順次実行される上記演算の結果、ＦＡＤＲ１に対する分岐予測のＢＲステージの終了時にフリップフロップＢＷＳＵＭ１に格納される値が、次のＦＡＤＲの分岐予測において使用する値ＳＵＭとなる。演算器４２は、重みテーブルＢＷＴ０に対して設けられており、重みテーブルＢＷＴ０からの重み値Ｗ０に対してフリップフロップＢＷＳＵＭ１からの値ＳＵＭを加算する。
【００５６】
図７は、重み演算部３３の構成の一例を示す図である。図７に示される重み演算部３３は、２０個の掛け算器４５、２０個の加算器４６、２０個のフリップフロップＢＷＳＵＭ１乃至ＢＷＳＵＭ２０、及びセレクタ回路４７を含む。セレクタ回路４７は、入力される分岐方向信号ＢＤ＿Ｐに応じて、分岐成立時に＋１となり、分岐不成立時に−１となる出力Ｘを生成する。
【００５７】
掛け算器４５の各々は、対応する重みテーブルＢＷＴｉ（ｉ＝１〜２０）からの重み値Ｗｉと値Ｘとを掛け算する。加算器４６の各々は、重みテーブルＢＷＴｉ（ｉ＝１〜１９）からの重みＷｉと値Ｘとの掛け算の結果と、フリップフロップＢＷＳＵＭｉ＋１の格納値とを加算し、加算結果によりフリップフロップＢＷＳＵＭｉの格納値を更新する。重みテーブルＢＷＴ０からの重み値Ｗ０については、加算器４６（図６の演算器４２）は、重み値Ｗ０とフリップフロップＢＷＳＵＭ１の格納値とを加算する。加算結果は分岐方向予測部３６に供給される。
【００５８】
図８は、１つの重みテーブルの構成の一例を示す図である。図８には、２１個の重みテーブルＢＷＴ０乃至ＢＷＴ２０のうちの代表の１つとして、重みテーブルＢＷＴ１を示してある。重みテーブルＢＷＴ０乃至ＢＷＴ２０の各々は同一の構成を有してよい。
【００５９】
重みテーブルＢＷＴ１には、６４個のインデックスの各々に対して、４個の重み値Ｗ００乃至Ｗ０３が格納されている。インデックスは命令アドレスの一部に対応しており、例えば命令アドレスの一部である６個のアドレスビットに対応してよい。具体的には、命令フェッチアドレスＦＡＤＲが順次インクリメントする際に変化する最下位のビットが、インデックスの最下位のビットに対応してよい。
【００６０】
前述のように１つのフェッチアドレスにより読み出される１つのフェッチラインには複数の命令が含まれてよい。複数の命令が含まれる場合には、１つのフェッチラインに対して複数の分岐予測を実行してよい。図８に示す重みテーブルの例では、４個の重み値を各インデックスに対応付けて格納してある。この場合、命令フェッチアドレスＦＡＤＲが供給されると、当該命令フェッチアドレスに対応するインデックスに対応する４個の重み値が読み出されることになる。４個の重み値それぞれに対して、前述の重み演算が並列に実行され、４個の予測結果が計算されてよい。各フェッチラインに対して複数個の重み値が対応付けられていることは必須ではなく、例えば各フェッチラインに対して１個の重み値が対応付けられている構成であってもよい。
【００６１】
重みテーブルＢＷＴ１は３ポート構成となっている。入力Ａポート５１には、命令フェッチアドレスＦＤＡＲが印加される。この入力Ａポート５１への入力に応答して、出力Ａポート５４から４個の重み値が出力される。これらの重み値は、重み演算部３３に供給されて、予測対象である命令フェッチアドレスＦＤＡＲに対する予測演算に用いられる。
【００６２】
入力Ｂポート５２には、完了した分岐命令を含むフェッチラインのアドレスＢＡＤＲが印加される。この入力Ｂポート５２への入力に応答して、出力Ｂポート５５から４個の重み値が出力される。これらの重み値は、更新用重み演算部３４に供給されて、分岐予測失敗時に重み演算部３３のフリップフロップＢＷＳＵＭｉ（ｉ＝０〜２０）を更新するためのデータの演算に用いられる。
【００６３】
入力Ｃポート５３には、完了分岐命令パスヒストリ３２に格納されている完了した分岐命令を含む一連のフェッチライン（過去の分岐命令実行経路）のアドレスＢＡＤＲ＿ＰＡＴＨが印加される。この入力Ｃポート５３への入力に応答して、出力Ｃポート５６から４個の重み値が出力される。これらの重み値は、重みテーブル更新部３５に供給されて、重み値更新の対象となる。
【００６４】
図９は、更新用重み演算部３４の構成の一例を示す図である。図９に示される更新用重み演算部３４は、２０個の掛け算器６０、２０個の加算器６１、２０個のフリップフロップＢＷＵＰ１乃至ＢＷＵＰ２０、セレクタ回路６３、セレクタ回路６４、及び更新判定部６５を含む。
【００６５】
更新用重み演算部３４は、図７に示される重み演算部３３と類似の構成を有しており、類似の重み演算を実行する。但し、更新用重み演算部３４において演算対象となる重み値は、命令フェッチアドレスＦＡＤＲに対応するものではなく、ＲＳＢＲ１８から報告される完了した分岐命令のフェッチラインアドレスＢＡＤＲに対応するものである。
【００６６】
前述の重み演算部３３におけるフリップフロップＢＷＳＵＭ１乃至ＢＷＳＵＭ２０の格納値は、命令フェッチ時に分岐命令を含む各フェッチラインについて計算した値となっている。一方、更新用重み演算部３４におけるフリップフロップＢＷＵＰ１乃至ＢＷＵＰ２０の格納値は、完了した分岐命令を含む各フェッチラインについて計算した値となっている。即ち、更新用重み演算部３４のフリップフロップＢＷＵＰ１乃至ＢＷＵＰ２０の格納値は、重み演算部３３のフリップフロップＢＷＳＵＭ１乃至ＢＷＳＵＭ２０の格納値と同様に計算されているが、異なるタイミングで計算されたものとなっている。これらフリップフロップＢＷＵＰ１乃至ＢＷＵＰ２０の格納値が、分岐予測失敗時において、重み演算部３３のフリップフロップＢＷＳＵＭ１乃至ＢＷＳＵＭ２０の値に対する代用値又は更新値として用いられることになる。
【００６７】
言葉を換えて言うと、図５に示す分岐予測部１０では、重み演算部３３が、命令フェッチアドレスＦＡＤＲに応じて重みテーブル部３１から読み出された重み値Ｗ０〜Ｗ２１に基づいて第１の演算と第２の演算とを行う。重み演算部３３は、第１の演算により命令フェッチアドレスＦＡＤＲに対する分岐予測の基になる第１の値（例えばＳＵＭ＋Ｗ０）を計算するとともに、第２の演算により将来の分岐予測の基になる第２の値（例えばＢＷＳＵＭ２０〜ＢＷＳＵＭ１の格納値）を計算する。
【００６８】
また更新用重み演算部３４が、完了した分岐命令の完了命令アドレスＢＡＤＲに応じて重みテーブル部３１から読み出された重み値Ｗ０〜Ｗ２１に基づいて上記第２の演算に相当する第３の演算を上記第２の演算と並行して行う。この第３の演算により、分岐予測失敗時に第２の値（例えばＢＷＳＵＭ２０〜ＢＷＳＵＭ１の格納値）の代用値又は更新値となる第３の値（例えばＢＷＵＰ２０〜ＢＷＵＰ１の格納値）を計算する。そして、重み演算部３４のフリップフロップＢＷＵＰｉ（ｉ＝１〜２０）の値を重み演算部３３のフリップフロップＢＷＳＵＭｉ（ｉ＝１〜２０）にそれぞれコピーすることで、分岐予測失敗時に重み演算部３３に格納される上記第２の値を上記第３の値で置き換える。
【００６９】
ここで「第３の演算を第２の演算と並行して行う」とは、命令フェッチアドレスＦＡＤＲが供給される度に第２の演算を実行し、それと並行して、完了した分岐命令の完了命令アドレスＢＡＤＲが供給される度に第３の演算を実行するということである。またそれにより、第２の値と第３の値とが並行して蓄積されていくということである。第２の演算と第３の演算とが同一タイミングに実行されることがあってもよいし、異なるタイミングに実行されることがあってもよい。命令フェッチシーケンスの流れに沿って第２の演算が順次行われ、それと並行して、分岐命令完了シーケンスの流れに沿って第３の演算が順次行われる。即ち、第３の演算は従来技術の場合のように分岐予測失敗が検出された時点で纏めて実行されるのではなく、第２の演算が進行するのと同時に第３の演算が進行していく。これにより、分岐予測ミス発生時に後続命令に対する分岐予測において用いるデータを短時間で用意することが可能となる。
【００７０】
以下に、図９に示す更新用重み演算部３４の構成及び動作について詳細に説明する。
【００７１】
更新用重み演算部３４は、完了した分岐命令の分岐成立又は分岐不成立を示す完了分岐方向ＢＤ＿ＣをＲＳＢＲ１８から受け取る。セレクタ回路６４は、入力される完了分岐方向ＢＤ＿Ｃに応じて、分岐成立時に＋１となり、分岐不成立時に−１となる出力Ｘを生成する。
【００７２】
重みテーブル部３１は、ＲＳＢＲ１８から、完了した分岐命令を含むフェッチラインのアドレスの一部をインデックスとして受け取り、当該インデックスに対応する重み値（Ｗｉ＝０〜２０）を出力する。掛け算器６０の各々は、対応する重みテーブルＢＷＴｉ（ｉ＝１〜２０）からの重み値Ｗｉと値Ｘとを掛け算する。加算器６１の各々は、重みテーブルＢＷＴｉ（ｉ＝１〜１９）からの重みＷｉと値Ｘとの掛け算の結果と、フリップフロップＢＷＵＰｉ＋１の格納値とを加算し、加算結果によりフリップフロップＢＷＵＰｉの格納値を更新する。重みテーブルＢＷＴ０からの重み値Ｗ０については、加算器６１は、重み値Ｗ０とフリップフロップＢＷＵＰ１の格納値とを加算する。加算結果は更新判定部６５に供給される。
【００７３】
前述のように、重み演算部３３は命令フェッチアドレスＦＡＤＲに応じて重みテーブル部３１から読み出された重み値と上記第１の値に応じた分岐予測方向ＢＤ＿Ｐとに基づいて上記第２の演算を行う。それに対して更新用重み演算部３４は、完了命令アドレスＢＡＤＲに応じて重みテーブル部３１から読み出された重み値と完了した分岐命令の分岐方向ＢＤ＿Ｃとに基づいて上記第３の演算を行うことにより上記第３の値を計算する。これにより、重み演算部３３と更新用重み演算部３４とのそれぞれにおいて、異なる適切な分岐方向に対する重み演算を実行することが可能となる。
【００７４】
なお後述するように、フリップフロップＢＷＵＰ１としては５つのフリップフロップが設けられており、タイミングの異なる５個の演算結果を格納する。セレクタ回路６３が、ＲＳＢＲ１８から供給されるシーケンスカウントＳＥＱ＿ＣＮＴに基づいて、５個の演算結果のうちの１つを選択する。選択された演算結果が、重み値Ｗ０と加算される対象となる。
【００７５】
上記の構成により、更新用重み演算部３４は、２０個の重み値Ｗｉ（ｉ＝０〜２０）の各々に、完了分岐結果の値Ｘ（分岐成立なら＋１、分岐不成立なら−１）を掛け、重み演算結果ＭＵＰｉ（＝Ｗｉ・Ｘ）を得る。更新用重み演算部３４は、フリップフロップＢＷＵＰｉ＋１に格納されている値に対して上記の重み演算結果ＭＵＰｉを加算し、加算結果をフリップフロップＢＷＵＰｉに格納する。但しフリップフロップＢＷＵＰ２０にはＭＵＰ２０をそのまま格納する。
【００７６】
これにより、完了分岐命令が含まれるフェッチラインに対してフリップフロップＢＷＵＰ２０に格納されたＭＵＰ２０に対して、その後順番に完了される分岐命令が含まれる１９個の異なるフェッチラインについて計算されたＭＵＰ１９〜ＭＵＰ１が順次加算されていく。最終的に、フリップフロップＢＷＵＰ１の格納値ＳＵＭＵＰは以下の値となる。
【００７７】
ＳＵＭＵＰ＝ＭＵＰ２０＋ＭＵＰ１９＋・・・ＭＵＰ２＋ＭＵＰ１
これらの計算は、ＲＳＢＲ１８から供給される分岐命令情報が、完了した分岐命令が新たなフェッチラインに属すること、即ち今回完了した分岐命令が前回完了した分岐命令とは異なるフェッチラインに属すること、を示す場合に実行される。即ち、上記計算はフェッチライン単位で実行される。
【００７８】
完了した分岐命令が新たなフェッチラインに属するか否かは、シーケンスカウントＳＥＱ＿ＣＮＴに基づいて判断することができる。シーケンスカウントＳＥＱ＿ＣＮＴは命令デコーダ１４からＲＳＢＲ１８に分岐命令が登録される際に各分岐命令に付随する情報であり、各分岐命令が何フェッチラインぶりにＲＳＢＲ１８に登録されたか、を示している。ある分岐命令に付随するシーケンスカウントＳＥＱ＿ＣＮＴがゼロであれば、当該分岐命令は直前の分岐命令と同一のフェッチラインに属していることになる。
【００７９】
シーケンスカウントＳＥＱ＿ＣＮＴを作成するために、命令デコーダ１４にカウンタを設ければよい。命令デコーダ１４は、フェッチライン境界の命令を発行するたびにカウンタをカウントアップする。命令デコーダ１４は、分岐命令を発行する度に、その時点でのカウント値を分岐命令に付随させてＲＳＢＲ１８に送ると共にカウントをゼロにリセットする。また分岐予測ミスが発生した場合、それが確定した時点でのシーケンスカウントＳＥＱ＿ＣＮＴの値は誤った分岐予測による値となるので、カウンタをリセットする。その後再命令フェッチにより正しい命令がフェッチされてくるとき、上記カウンタのカウントアップを再開する。
【００８０】
更新用重み演算部３４においては、重みテーブル更新部３５における重み値更新を実行するか否かを判定する更新判定部６５が設けられている。更新判定部６５における更新判定処理においては、予測時に分岐方向判断のために計算するＳＵＭ＋Ｗ０に相当する値であるＳＵＭＵＰ＋Ｗ０（加算器６１の出力値）が用いられる。具体的には、ＳＵＭＵＰ＋Ｗ０の値が所定の閾値未満であるか、ＳＵＭＵＰ＋Ｗ０の値が分岐予測に用いられたとした場合に示す分岐予測方向と実際の分岐方向とが異なっているとき（即ち分岐予測に失敗した場合）に、更新処理を実行する。
【００８１】
なお所定の閾値未満の時に更新をするのは、過去の履歴による学習が未だ充分に進んでいない状態であると判断できるからである。所定の閾値以上の場合には、充分に学習が進んだ状態であり、過学習によりその後の変化に適応できにくくなることを防ぐために、更新処理を実行しない。
【００８２】
以上のように、更新用重み演算部３４は、上記第３の値（例えばＢＷＵＰ１の格納値）から求めた値（例えばＳＵＭＵＰ＋Ｗ０）に基づいて、完了命令アドレスＢＡＤＲに対応する重み値の更新の要否を示す第４の値（例えば更新判定部６５の出力値）を生成する。重みテーブル更新部３５は、上記第４の値が重み値の更新要を示す場合に重みテーブル部３１の重み値を更新する。これにより、従来のように予測対象命令に対応する上記第１の値（例えばＳＵＭ＋Ｗ０）に応じて重み値更新を行っていた場合と比較して、完了分岐命令に対応する上記第３の値から求めた値に応じて重み値更新を行うので、より精度の高い重み値更新が可能になる。
【００８３】
前述のように、重み演算部３３において予測時にＳＵＭ＋Ｗ０を計算する際には、重み値Ｗ０を取得するフェッチラインに対して、フリップフロップＢＷＳＵＭ１の格納値ＳＵＭを計算するフェッチラインは４つ前のフェッチラインである。従って、更新用重み演算部３４におけるＳＵＭＵＰ＋Ｗ０の計算時にも、４つのフェッチライン差を実現する必要がある。この目的のために、フリップフロップＢＷＵＰ１としては５つのフリップフロップが設けられており、セレクタ回路６３が、シーケンスカウントＳＥＱ＿ＣＮＴに基づいて、５個のフリップフロップの格納値のうちの１つを選択する。
【００８４】
ＲＳＢＲ１８から新たに供給された完了分岐命令を分岐命令Ａとする。フリップフロップＢＷＵＰ１として設けられている第１のフリップフロップ乃至第５のフリップフロップのうち、第１のフリップフロップには分岐命令Ａの直前に完了した分岐命令Ｂに対して計算したＳＵＭＵＰの値が格納される。第２のフリップフロップには、分岐命令Ｂの１つ前のフェッチラインに対して計算したＳＵＭＵＰの値が格納される。第３のフリップフロップには、分岐命令Ｂの２つ前のフェッチラインに対して計算したＳＵＭＵＰの値が格納される。第４のフリップフロップには、分岐命令Ｂの３つ前のフェッチラインに対して計算したＳＵＭＵＰの値が格納される。第５のフリップフロップには、分岐命令Ｂの４つ前のフェッチラインに対して計算したＳＵＭＵＰの値が格納される。
【００８５】
分岐命令Ａに付随するシーケンスカウントＳＥＱ＿ＣＮＴの値が０のとき、分岐命令Ａは分岐命令Ｂと同一フェッチラインに属すので、第５のフリップフロップに格納される分岐命令Ｂの４つ前のフェッチラインに対するＳＵＭＵＰと重み値Ｗ０とを加算する。同様に、シーケンスカウントＳＥＱ＿ＣＮＴの値が１のとき、第４のフリップフロップに格納される分岐命令Ｂの３つ前のフェッチラインに対するＳＵＭＵＰと重み値Ｗ０とを加算する。以下同様であり、シーケンスカウントＳＥＱ＿ＣＮＴの値が４以上のときには、第１のフリップフロップに格納される分岐命令Ｂのフェッチラインに対するＳＵＭＵＰと重み値Ｗ０とを加算する。
【００８６】
なお重み値の更新処理は、１フェッチラインに含まれる複数の分岐命令のそれぞれに対して実行してよい。このとき実行される更新処理は、それら複数の分岐命令のそれぞれに対応して図８に示される重み値Ｗ００乃至Ｗ０４を個別に更新してよい。
【００８７】
以上のように、更新用重み演算部３４は、連続する複数の完了命令アドレスにそれぞれ対応する上記第３の値（例えばＳＵＭＵＰ）を複数のバッファ（５つのフリップフロップＢＷＵＰ１）に格納しておく。そして、上記連続する複数の完了命令アドレス間の間隔に応じて上記複数のバッファのうちの１つのバッファを選択し、選択された１つのバッファに格納される上記第３の値に基づいて上記第４の値（例えば更新判定部６５の出力値）を生成する。これにより、重み値更新の要否の判断をする際に、比較的単純な構成により、フェッチライン間の距離の変動を吸収することが可能となる。
【００８８】
図１０は、重みテーブル更新部３５による更新演算の進行を模式的に示す図である。図１０において、ＢＷ１、ＢＷ２、・・・は更新演算パイプラインの各ステージである。図１０に示す掛け算器６０、加算器６１、フリップフロップＢＷＵＰ１、セレクタ回路６３、及び更新判定部６５は、図９に示す掛け算器６０、加算器６１、フリップフロップＢＷＵＰ１、セレクタ回路６３、及び更新判定部６５である。但し、図１０の構成例における更新判定部６５は、ＲＳＢＲ１８から供給される分岐予測の失敗を示す予測失敗信号ＦＡＩＬ（予測失敗の時に１、予測成功の時に０）に基づいて、分岐予測の失敗に有無を判断している。なお図１０では、掛け算器６０と加算器６１とを纏めて１つのユニットとして図示してある。
【００８９】
更新判定部６５の演算器７５は、ＳＵＭＵＰ＋Ｗ０の値と所定の閾値とを比較し、ＳＵＭＵＰ＋Ｗ０の値が所定の閾値未満である場合に出力を１に設定し、それ以外の場合に出力を０に設定する。ＯＲ回路７６の出力は、ＳＵＭＵＰ＋Ｗ０の値が所定の閾値未満である場合又は分岐予測失敗（即ちＦＡＩＬ＝１）の場合に１となり、それ以外の場合に０となる。更新判定部６５は、このＯＲ回路７６の出力を、判定値として出力する。
【００９０】
図５にも示される完了分岐命令パスヒストリ３２は、ＲＳＢＲ１８から供給される完了した分岐命令に関する情報に基づいて構築される。完了分岐命令パスヒストリ３２には、各フェッチラインのアドレスの一部（この例では６ビット）と当該フェッチラインに含まれる分岐命令の演算結果の分岐方向とが対応付けて、各エントリとして保持されている。図５の構成例において、エントリ数は２１個であり、これら２１個のフェッチラインに対する分岐方向のデータはグローバル履歴と呼ばれる。グローバル履歴の分岐方向は、フェッチライン単位で与えられており、当該フェッチライン内部に１つでも分岐成立する分岐命令が含まれる場合には、当該フェッチラインに対する分岐方向は分岐成立とされる。それ以外の場合に分岐方向は分岐不成立とされる。
【００９１】
完了分岐命令パスヒストリ３２において、０番のエントリは、重みテーブル更新部３５による更新対象となる分岐命令及び重みテーブルＢＷＴ０に対応する。１番のエントリは、更新対象の分岐命令を含むフェッチラインより４つ前のフェッチラインにおける分岐命令及び重みテーブルＢＷＴ１に対応する。２番のエントリは、更新対象の分岐命令を含むフェッチラインより５つ前のフェッチラインにおける分岐命令及び重みテーブルＢＷＴ２に対応する。以下同様であり、最後の２０番のエントリは、更新対象の分岐命令を含むフェッチラインより２３個前のフェッチラインにおける分岐命令及び重みテーブルＢＷＴ２０に対応する。
【００９２】
ＲＳＢＲ１８から供給された前述の分岐命令Ａのアドレスが重みテーブルＢＷＴ０に供給され、対応する重み値Ｗ０が読み出される。また完了分岐命令パスヒストリ３２に格納されている各フェッチラインのアドレスが、対応する重みテーブルＢＷＴｉ（ｉ＝１〜２０）に供給され、対応する重み値Ｗｉ（ｉ＝１〜２０）が読み出される。図１０では、図示の都合上重みテーブルＢＷＴ０及びＢＷＴ１のみが示されているが、残りの重みテーブルについても同様である。
【００９３】
演算器７０は、分岐命令Ａの分岐方向が分岐成立であれば重み値Ｗ０を＋１し、分岐命令Ａの分岐方向が分岐不成立であれば重み値Ｗ０を−１して、計算結果を書き込み制御部７２に供給する。分岐命令Ａの分岐方向は、完了分岐命令パスヒストリ３２のエントリ０から供給される。
【００９４】
演算器７１は、分岐命令Ａの分岐方向と完了分岐命令パスヒストリ３２のｉ番のエントリに保持された分岐方向が同一方向ならば重み値Ｗｉを＋１する。演算器７１は更に、分岐命令Ａの分岐方向と完了分岐命令パスヒストリ３２のｉ番のエントリに保持された分岐方向が逆方向ならば重み値Ｗｉを−１する。計算結果は、対応する書き込み制御部７２に供給される。
【００９５】
書き込み制御部７２は、更新判定部６５から供給される判定値が１の場合に、演算器７０又は７１から供給された計算値を、対応する重みテーブルに書き戻す。これにより、重みテーブルＢＷＴｉ（ｉ＝１〜２０）の重み値が更新される。
【００９６】
図１１は、分岐予測失敗時における重み演算部３３のデータ更新動作を模式的に示す図である。
【００９７】
分岐予測時には、フリップフロップＢＷＳＵＭ１に格納される値ＳＵＭと命令フェッチアドレスの一部をインデックスとして重みテーブルＢＷＴ０から読み出される重み値Ｗ０とを加算する。分岐予測ミスによるパイプラインキャンセル後の命令フェッチ再開の最初のフェッチラインにおいて分岐予測する場合、フリップフロップＢＷＳＵＭ１の値ＳＵＭとして、再命令フェッチアドレスに対して適切な値を復元する必要がある。これは、分岐予測ミス時の再命令フェッチのフェッチラインに対する復元状態を、分岐予測ミスが起こらなかった場合に同一フェッチラインに対して存在したであろう状態と全く同一状態としなければ実現できない。これを実現するために、前述のように、更新用重み演算部３４は、重み演算部３３のフリップフロップＢＷＳＵＭｉ（ｉ＝１〜２０）と同じ演算結果を格納するように、フリップフロップＢＷＵＰｉ（ｉ＝１〜２０）の格納値を計算している。
【００９８】
図１１では、図面上から２番目のフェッチラインＦＬ２において、分岐予測時に分岐不成立と予測したが、分岐演算結果が分岐成立であり、分岐予測ミスが発生した場合を示している。仮に分岐予測が正しく分岐成立と予測されていたら、図４で説明した場合と同様に、命令シーケンス方向の３番目及び４番目のフェッチラインＦＬ３及びＦＬ４はキャンセルされ、５番目のフェッチラインＦＬ５が正しい分岐先として命令フェッチを継続する。
【００９９】
分岐先のフェッチラインＦＬ５の予測時に、重みテーブルＢＷＴ１に対応しているフェッチラインは、フェッチラインＦＬ５の４つ前のフェッチラインである筈なので、図１１における１番目のフェッチラインＦＬ１となる。従って、重み演算部３３のフリップフロップＢＷＳＵＭ１の格納値としては、１番目のフェッチラインＦＬ１迄計算が行われた値ＳＵＭを復元する必要がある。
【０１００】
分岐予測ミスは分岐命令のＵステージで発覚する。ＲＩ１ステージ（分岐予測ミス時の命令復帰の第１のステージ）は再命令フェッチの最初のフェッチラインＦＬ５のＩＡステージと同一タイミングである。この時点では１番目のフェッチラインＦＬ１の分岐に対応する更新用重み演算部３４におけるフリップフロップＢＷＵＰｉ（ｉ＝１〜２０）の更新値を演算中であり、フリップフロップＢＷＵＰ１の格納値ＳＵＭＵＰは未だ確定していない。なお紙面の都合上、フリップフロップＢＷＵＰｉ（ｉ＝１〜２０）のうち、フリップフロップＢＷＵＰ１及びＢＷＵＰ２のみを図１１には示してある。
【０１０１】
次のＲＩ２ステージは再命令フェッチの最初のフェッチラインＦＬ５のＢＴステージと同一タイミングである。この時点では、更新用重み演算部３４のフリップフロップＢＷＵＰ１の格納値ＳＵＭＵＰが確定しているので、この格納値ＳＵＭＵＰをそのまま重み演算部３３にバイパスしてＳＵＭの値の代わりに使用することで、重み演算を実行する。即ち、フェッチラインＦＬ５のＢＴステージにおいて、演算器４２が、重みテーブルＢＷＴ０から読み出された重み値Ｗ０とフェッチラインＦＬ１のＢＷＵＰ１の格納値とを加算する。これにより、再命令フェッチの最初のフェッチラインＦＬ５において、分岐予測が実現できる。
【０１０２】
次のＲＩ３ステージは再命令フェッチ後の２番目のフェッチラインＦＬ６のＢＴステージと同一タイミングである。このフェッチラインＦＬ６における予測時に、重みテーブルＢＷＴ１に対応しているのは、分岐予測ミスを検出した２番目のフェッチラインＦＬ２である。この時点では分岐予測ミスを検出した分岐について、更新用重み演算部３４のフリップフロップＢＷＵＰ１の格納値ＳＵＭＵＰが確定しているので、この格納値ＳＵＭＵＰをそのまま重み演算部３３にバイパスしてＳＵＭの値の代わりに使用することで、重み演算を実行する。即ち、フェッチラインＦＬ６のＢＴステージにおいて、演算器４２が、重みテーブルＢＷＴ０から読み出された重み値Ｗ０とフェッチラインＦＬ２のＢＷＵＰ１の格納値とを加算する。これにより、再命令フェッチ後の２番目のフェッチラインＦＬ６において、分岐予測が実現できる。
【０１０３】
ＲＩ３ステージでは、分岐予測ミスを検出したフェッチラインＦＬ２に対して、更新用重み演算部３４におけるフリップフロップＢＷＵＰｉ（ｉ＝１〜２０）の更新値が確定している。従って、このＲＩ３ステージで重み演算部３４のフリップフロップＢＷＵＰｉ（ｉ＝１〜２０）の値を重み演算部３３のフリップフロップＢＷＳＵＭｉ（ｉ＝１〜２０）にそれぞれコピーすることで、重み演算部３３におけるフリップフロップの演算値の復元が完了する。
【０１０４】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【符号の説明】
【０１０５】
１０  分岐予測部
１１  命令フェッチアドレス生成部
１２  １次命令キャッシュ
１３  命令バッファ
１４  命令デコーダ
１５  ＲＳＡ
１６  ＲＳＥ
１７  ＲＳＦ
１８  ＲＳＢＲ
１９  ＣＳＥ
２０  オペランドアドレス生成部
２１  演算部
２２  演算部
２３  ネクストプログラムカウンタ（ＰＣ）
２４  コンディションコードレジスタ（ＣＣ）
２５  １次データキャッシュ
２６  固定小数点更新バッファ
２７  浮動小数点更新バッファ
２８  固定小数点レジスタ
２９  浮動小数点レジスタ
３０  ターゲットアドレス履歴
３１  重みテーブル部
３２  完了分岐命令パスヒストリ
３３  重み演算部
３４  更新用重み演算部
３５  重みテーブル更新部
３６  分岐方向予測部
【図１】
2020027533.tif 000003
【図２】
2020027533.tif 000004
【図３】
2020027533.tif 000005
【図４】
2020027533.tif 000006
【図５】
2020027533.tif 000007
【図６】
2020027533.tif 000008
【図７】
2020027533.tif 000009
【図８】
2020027533.tif 000010
【図９】
2020027533.tif 000011
【図１０】
2020027533.tif 000012
【図１１】
2020027533.tif 000013