(57)【特許請求の範囲】
【請求項１】
複数ステージのパイプライン処理構造をもつプロセッサの分岐予測装置であって、
複数の命令の中から次に実行すべき命令のアドレスを指定する命令フェッチアドレス部と、
前記命令フェッチアドレス部に接続されて、指定された命令のアドレスの履歴から次に実行すべき命令の第１の予測アドレスを出力する第１の分岐予測手段と、
前記命令フェッチアドレス部に接続されて、指定された命令のアドレスの履歴から次に実行すべき命令の第２の予測アドレスを前記第１の予測アドレスの出力から所定時間遅れて出力する前記第１の分岐予測手段よりも予測精度が高い第２の分岐予測手段と、
前記命令フェッチアドレス部に接続されて、指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを前記第２の分岐予測手段よりも低応答速度と高い予測精度で出力する第３の分岐予測手段と、
前記第１乃至第３の分岐予測手段の出力が全て同じであるとき、前記第１の分岐予測手段の出力をフェッチすべき命令アドレスとして前記命令フェッチアドレス部に指定し、前記第２及び第３の分岐予測手段の出力が異なるとき、前記第３の分岐予測手段の出力をフェッチすべき命令アドレスとして前記命令フェッチアドレス部に指定し、前記第１及び第２の分岐予測手段の出力が異なるとき、前記第２の分岐予測手段の出力をフェッチすべき命令アドレスとして前記命令フェッチアドレス部に指定する、予測結果選択手段と、
を備えるプロセッサの分岐予測装置。
【請求項２】
請求項１に記載の分岐予測装置を備えるパイプライン処理構造をもつプロセッサ。
【請求項３】
複数ステージのパイプライン処理構造をもつプロセッサの分岐予測方法であって、
指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを所定の応答速度と所定の予測精度で出力する第１の分岐予測ステップと、
前記指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを前記第１の分岐予測ステップよりも低応答速度と高い予測精度で出力する第２の分岐予測ステップと、
前記指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを前記第２の分岐予測ステップよりも低応答速度と高い予測精度で出力する第３の分岐予測ステップと、を備え、
前記第１乃至第３の分岐予測ステップの出力が同じであるとき、前記第１の分岐予測ステップの出力をフェッチすべき命令アドレスとして指定し、
前記第２及び第３の分岐予測ステップの出力が異なるとき、前記第３の分岐予測ステップの出力をフェッチすべき命令アドレスとして指定すると共にパイプラインの後段で前記第１及び第２の分岐予測ステップの各出力の命令アドレスに基づくフェッチによる処理を破棄し、
前記第１及び第２の分岐予測ステップの出力が異なるとき、前記第２の分岐予測ステップの出力をフェッチすべき命令アドレスとして指定する共にパイプラインの後段で前記第１の分岐予測ステップの出力の命令アドレスに基づくフェッチによる処理を破棄する、
プロセッサの分岐予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータアーキテクチャにおける分岐予測、パイプライン動作を行うプロセッサの分岐予測装置、分岐予測方法に関する。
【背景技術】
【０００２】
プロセッサにおけるスループットを向上するためにプロセッサにはパイプライン処理機構が設けられているものがある。パイプライン動作を行うプロセッサにおいては複数段のパイプラインで連続的に命令を実行するのでスループットが向上する。しかし、パイプラインで条件分岐命令などのある処理結果を基にした判断が必要な状態が発生すると、パイプラインで連続的に命令を実行することができない状態（制御ハザード）が生じる。このようなハザードを軽減するために分岐予測と命令の投機実行が用いられている。例えば、特開２００１−２４３０６９号公報には、一つの分岐予測手段に対して過去に実施した分岐予測結果をフィードバックして最新の分岐予測状態として分岐予測精度を高めるようにした分岐予測装置が紹介されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００１−２４３０６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
分岐予測と命令の投機実行は高速動作を実現するパイプライン動作のプロセッサにとって重要な技術である。しかしながら、(a)分岐の予測結果の精度が高い分岐予測方式は入力から予測結果を得るまでの時間が長い。分岐予測結果が得られるまで後続のフェッチが実施できず、パイプライン中にいわゆるバブルが発生する。(b)入力から予測結果を得るまでの時間が短い分岐予測方式は予測結果の精度が低い。分岐予測結果の精度が低いため、多くの投機実行が失敗し、高い性能が得られない。
【０００５】
よって、本発明は分岐予測の入力から分岐予測の結果出力までの時間（予測レイテンシ）が短く、高精度の分岐予測が可能な分岐予測装置及び分岐予測方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を達成するため参考例の分岐予測装置の一態様は、命令フェッチの履歴から次に実行するフェッチラインを決める複数の分岐予測手段と矛盾検出手段とを備え、複数の分岐予測手段のうち高速な分岐予測手段が出力した予測アドレスで暫定的に命令フェッチアドレスを決め、複数の分岐予測手段のうち高精度で低速な分岐予測手段が出力した予測アドレスと高速な分岐予測手段が出力した予測アドレスとが同じ場合には当該暫定的な命令フェッチアドレスの命令はパイプラインで実行され、異なる場合には低速な分岐予測手段の予測アドレスを命令フェッチアドレスとし、時間軸上において先行する暫定的な命令フェッチアドレスの命令はパイプラインで実行されない（破棄される）。
【０００７】
かかる構成とすることによって、分岐予測時間が短く（低予測レイテンシ）、予測精度の高い分岐予測装置を得ることが可能となる。
【０００８】
また、本発明の分岐予測装置の一態様は、複数ステージのパイプライン処理構造をもつプロセッサの分岐予測装置であって、複数の命令の中から次に実行すべき命令のアドレスを指定する命令フェッチアドレス部と、上記命令フェッチアドレス部に接続されて、指定された命令のアドレスの履歴から次に実行すべき命令の第１の予測アドレスを出力する第１の分岐予測手段と、上記命令フェッチアドレス部に接続されて、指定された命令のアドレスの履歴から次に実行すべき命令の第２の予測アドレスを上記第１の予測アドレスの出力から所定時間遅れて出力する上記第１の分岐予測手段よりも予測精度が高い第２の分岐予測手段と、上記命令フェッチアドレス部に接続されて、指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを上記第２の分岐予測手段よりも低応答速度と高い予測精度で出力する第３の分岐予測手段と、上記第１乃至第３の分岐予測手段の出力が全て同じであるとき、上記第１の分岐予測手段の出力をフェッチすべき命令アドレスとして上記命令フェッチアドレス部に指定し、上記第２及び第３の分岐予測手段の出力が異なるとき、上記第３の分岐予測手段の出力をフェッチすべき命令アドレスとして上記命令フェッチアドレス部に指定し、上記第１及び第２の分岐予測手段の出力が異なるとき、上記第２の分岐予測手段の出力をフェッチすべき命令アドレスとして上記命令フェッチアドレス部に指定する、予測結果選択手段と、を備える。
また、参考例の分岐予測装置の一態様は、複数ステージのパイプライン処理構造をもつプロセッサの分岐予測装置において、複数の命令をアドレスに対応づけて記憶する記憶手段と、上記複数の命令の中から次に実行すべき命令のアドレスを指定する命令フェッチアドレス部と、指定された命令を実行する実行ユニットと、指定された命令のアドレスの履歴から次に実行すべき命令の第１の予測アドレスを出力する第１の分岐予測手段と、指定された命令のアドレスの履歴から次に実行すべき命令の第２の予測アドレスを上記第１の予測アドレスの出力から所定時間遅れて出力する上記第１の分岐予測手段よりも予測精度が高い第２の分岐予測手段と、上記第２の予測アドレスに先行する上記第１の予測アドレスを上記命令フェッチ部に与えると共に、上記第１の予測アドレスと上記第１の予測アドレスに後続する上記第２の予測アドレスが異なるとき上記第２の予測アドレスを上記命令フェッチ部に与える予測結果選択手段と、上記第２の予測アドレスが上記命令フェッチアドレス部に与えられるとき上記第１の予測アドレスの命令の実行の破棄を上記実行ユニットに指示する矛盾検出手段と、を備える。
【０００９】
かかる構成とすることによって、分岐予測時間が短く、予測精度の高い分岐予測装置を得ることが可能となる。
【００１０】
また、本発明の分岐予測装置の一態様は、複数ステージのパイプライン処理構造をもつプロセッサの分岐予測装置において、複数の命令をアドレスに対応づけて記憶する記憶手段と、上記複数の命令の中から次に実行すべき命令のアドレスを指定する命令フェッチアドレス部と、指定された命令を実行する実行ユニットと、指定された命令のアドレスの履歴から次に実行すべき命令の第１の予測アドレスの列を出力する第１の分岐予測手段と、指定された命令のアドレスの履歴から次に実行すべき命令の第２の予測アドレスの列を上記第１の予測アドレスの出力から所定時間遅れて出力する上記第１の分岐予測手段よりも予測精度が高い第２の分岐予測手段と、上記第１の予測アドレスの列を上記命令フェッチアドレス部に与えると共に、上記第１の予測アドレスの列と上記第２の予測アドレスの列とを比較して対応する予測アドレスに相違があるとき、上記第２の予測アドレスの列のアドレスで上記第１の予測アドレスの列を修正する予測結果選択手段と、上記第２の予測アドレスの列のアドレスが上記命令フェッチアドレス部に与えられるとき上記第１の予測アドレスの列の修正されたアドレスの命令の実行の破棄を上記実行ユニットに指示する矛盾検出手段と、を備える。
【００１１】
かかる構成とすることによって、分岐予測時間が短く、予測精度の高い分岐予測装置を得ることが可能となる。
【００１２】
好ましくは、上記第１の分岐予測手段の出力と上記第２の分岐予測手段の出力との相互間には、上記パイプライン構造における１ステージ又は複数ステージに対応する時間差がある。
【００１３】
また、参考例の分岐予測装置の一態様は、複数ステージのパイプライン処理構造をもつプロセッサの分岐予測装置において、複数の命令をアドレスに対応づけて記憶する記憶手段と、上記複数の命令の中から次に実行すべき命令のアドレスを指定する命令フェッチアドレス部と、指定された命令を実行する実行ユニットと、指定された命令のアドレスの履歴から次に実行すべき命令の第１の予測アドレスの列を出力する第１の分岐予測手段と、指定された命令のアドレスの履歴から次に実行すべき命令の第２の予測アドレスの列を上記第１の予測アドレスの出力から所定時間遅れて出力する上記第１の分岐予測手段よりも予測精度が高い第２の分岐予測手段と、上記第１の予測アドレスの列を上記命令フェッチアドレス部に与えると共に、上記第１の予測アドレスの列と上記第２の予測アドレスの列とを比較して対応する予測アドレスに相違があるとき、上記第２の予測アドレスの列のアドレスで上記第１の予測アドレスの列を修正する予測結果選択手段と、上記第２の予測アドレスの列のアドレスが上記命令フェッチアドレス部に与えられるとき上記第１の予測アドレスの列の修正されたアドレスの命令の実行の破棄を上記実行ユニットに指示する矛盾検出手段と、を備える。
【００１４】
かかる構成とすることによって、分岐予測時間が短く、予測精度の高い分岐予測装置を得ることが可能となる。
【００１５】
また、参考例の分岐予測方式の一態様は、複数ステージのパイプライン処理構造をもつプロセッサの分岐予測方式において、高速で低精度の分岐予測手段と低速で高精度の分岐予測手段を並行して動作させ、先に得られる低精度の予測アドレスを暫定アドレスとして命令フェッチを実行し、上記暫定アドレスと後に得られる高精度の予測アドレスとを比較して予測結果が異なるとき、後に得られる高精度の予測アドレスで命令フェッチを実行すると共に上記暫定アドレスでフェッチされた命令の破棄又は上記暫定アドレスでフェッチされた命令の実行結果を破棄する。
【００１６】
かかる構成とすることによって、分岐予測時間が短く、予測精度の高い分岐予測装置を得ることが可能となる。
【００１７】
また、本発明の分岐予測方法の一態様は、複数ステージのパイプライン処理構造をもつプロセッサの分岐予測方法であって、指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを所定の応答速度と所定の予測精度で出力する第１の分岐予測ステップと、上記指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを上記第１の分岐予測ステップよりも低応答速度と高い予測精度で出力する第２の分岐予測ステップと、上記指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを上記第２の岐予測ステップよりも低応答速度と高い予測精度で出力する第３の分岐予測ステップと、を備え、上記第１乃至第３の分岐予測ステップの出力が同じであるとき、上記第１の分岐予測ステップの出力をフェッチすべき命令アドレスとして指定し、上記第２及び第３の分岐予測ステップの出力が異なるとき、上記第３の分岐予測ステップの出力をフェッチすべき命令アドレスとして指定すると共にパイプラインの後段で上記第１及び第２の分岐予測ステップの各出力の命令アドレスに基づくフェッチよる処理を破棄し、上記第１及び第２の分岐予測ステップの出力が異なるとき、上記第２の分岐予測ステップの出力をフェッチすべき命令アドレスとして指定する共にパイプラインの後段で上記第１の分岐予測ステップの出力の命令アドレスに基づくフェッチによる処理を破棄する。
また、参考例の分岐予測方式の一態様は、複数ステージのパイプライン処理構造をもつプロセッサの分岐予測方式において、指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを所定の応答速度と所定の予測精度で出力する第１の分岐予測手段と、指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを上記第１の分岐予測手段よりも低応答速度と高い予測精度で出力する第２の分岐予測手段と、指定された命令のアドレスの履歴から次に実行すべき命令の予測アドレスを上記第２の岐予測手段よりも低応答速度と高い予測精度で出力する第３の分岐予測手段と、を備え、上記第１乃至第３の分岐予測手段の出力が同じであるとき、上記第１の分岐予測手段の出力をフェッチすべき命令アドレスとして指定し、上記第２及び第３の分岐予測手段の出力が異なるとき、上記第３の分岐予測手段の出力をフェッチすべき命令アドレスとして指定すると共にパイプラインの後段で上記第１及び第２の分岐予測手段の各出力をフェッチした命令アドレスによる処理を破棄し、上記第１及び第２の分岐予測手段の出力が異なるとき、上記第２の分岐予測手段の出力をフェッチすべき命令アドレスとして指定する共にパイプラインの後段で上記第１の分岐予測手段の出力をフェッチした命令アドレスによる処理を破棄する。
【００１８】
かかる構成とすることによって、分岐予測時間が短く、予測精度の高い分岐予測装置を得ることが可能となる。
【発明の効果】
【００１９】
本発明によれば、分岐予測の入力から分岐予測の結果出力までの時間が短く、高精度の分岐予測が可能な分岐予測装や分岐予測方式を得ることが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明の分岐予測装置を説明する説明図である。
【図２】分岐予測装置内の動作のアルゴリズムの例を説明するフローチャートである。
【図３】分岐予測装置の動作（予測が一致する場合）を説明するタイミング図である。
【図４】分岐予測装置の動作（予測が一致しない場合）を説明するタイミング図である。
【図５】本発明の分岐予測装置による予測レイテンシ（実行時間）の低減を説明する図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照しつつ本発明の実施形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲に係る発明を限定するものではなく、また、実施形態の中で説明されている特徴の組み合わせのすべてが発明の解決手段に必須であるとは限らない。
【００２２】
（装置の構成）
本発明によるプロセッサに内蔵される分岐予測装置は、相対的に低速で高精度な分岐予測装置と相対的に高速で低精度な分岐予測装置を命令フェッチパイプライン中で協調的に動作させることで高速で高精度な分岐予測を実現する。
【００２３】
本実施例では、プロセッサが三段のパイプラインステージを持ち、分岐予測装置が分岐予測手段としての三つ（複数）の分岐予測部を用いて予測を行い、予測結果に基づいて命令フェッチ機構とパイプラインを制御する場合を例として説明する。第一の分岐予測部１００が最も高速で低精度な動作を実現する分岐予測手段であり、第二の分岐予測部１０１は第一の分岐予測部よりも低速でより精度が高い動作を実現する分岐予測手段である。第三の分岐予測部１０２は最も低速で最も高精度な動作を実現する分岐予測手段である。
【００２４】
分岐予測部には、例えば、単純予測、静的予測、次ライン予測、２レベル分岐予測、局所分岐予測、高域分岐予測、統合分岐予測、合意予測、分岐予測部の上書き、ニューラル分岐予測、Ｌ−Ｔａｇｅ分岐予測、その他の分岐予測のアルゴリズムを持つ予測機構が適宜に構成される。
【００２５】
図１に示すように、本発明の分岐予測装置は、予測結果選択部１２０と、命令フェッチアドレス部１３０と、命令キャッシュ部１４０と、命令デコード部１５０と、命令フェッチライン有効ビット部１６０、１６１と、命令実行ユニット部１７０と、三つ（複数）の分岐予測部１００、１０１及び１０２と、予測情報の結果を参照して後続のフェッチ情報の破棄を行うかを決定する矛盾検出部１１０及び１１１、論理ゲートなどを含んで構成されている。
【００２６】
ここで、命令フェッチ部１３０（ステージ０）、命令キャッシュ部１４０（ステージ１）、命令デコード部１５０、命令実行ユニット部１７０（ステージ２）がパイプラインを構成している。また、図１の縦方向にパイプラインの三つのステージ（ステージ０、ステージ１、ステージ２）が示されている。各ステージ間のデータ移動はレジスタやデータラッチによって同期される。
【００２７】
命令フェッチアドレス部１３０は予測結果選択部１２０から出力される次に実行すべき命令アドレスを保持し、命令キャッシュ部１４０に対して命令フェッチ指示を与える。また、命令フェッチアドレス部１３０は同時に分岐予測部１００、１０１、及び１０２に対して分岐予測要求を与える。
【００２８】
命令フェッチライン有効ビット部１６０、１６１は各ステージの命令フェッチデータが有効であるか否かを示す。例えば、ステージ０において命令フェッチ指示で“１”が命令フェッチ有効ビット部１６０にセットされる。クロックと同期して後段の命令フェッチライン有効ビット部１６１（複数のパイプライン）に伝搬する。途中で分岐予測部の出力相互に不一致が生じた場合には命令フェッチライン有効ビット部はリセットされる。
【００２９】
命令キャッシュ部１４０は命令フェッチアドレス部１３０から与えられた命令フェッチ指示に従って該当アドレスの命令フェッチ処理を行い、命令部デコード部１５０に対して命令情報を与える。
【００３０】
命令デコード部１５０は、命令キャッシュ部１４０から出力された命令フェッチライン情報をデコードして命令実行ユニット部１７０を動作させる制御信号群を形成し、命令実行ユニット部１７０に与える。同一パイプラインステージの命令フェッチライン有効ビット部１６１が“１”（セット）の場合に命令実行ユニット部１７０に命令の実行の指示が与えられ、“０”（リセット）の場合には命令実行ユニット部１７０に命令の実行の指示が与えらず（命令実行ユニット部１７０は命令を動作しない）、命令は破棄される。
【００３１】
複数の分岐予測部１００〜１０２はそれぞれ予測結果を分岐予測結果選択部１２０と後続フェッチライン破棄判定を行う矛盾検出部１１０及び１１１に出力する。
【００３２】
予測結果選択部１２０は得られた複数の分岐予測結果のうち適切なものを判定し、命令フェッチアドレス部１３０に出力する。予測結果選択部１２０の動作は図２を参照して後述される。
命令フェッチアドレス部１３０に指定された値に従って命令フェッチパイプラインは次サイクル以降のフェッチ処理を継続する。
【００３３】
後続フェッチライン破棄判定を行う矛盾検出手段（１１０及び１１１）は分岐予測部間での不整合を検出し、矛盾を検出すると命令破棄指示を命令フェッチライン有効ビット部（１６０及び１６１）に対して出力する（後述の図２参照）。すなわち、矛盾検出部１１０は分岐予測部１００及び１０１間での不整合を検出し、矛盾を検出すると命令破棄指示を命令フェッチライン有効ビット部１６０に対して出力する。また、矛盾検出手段１１１は分岐予測部１０１及び１０２間での不整合を検出し、矛盾を検出すると命令破棄指示を命令フェッチライン有効ビット部１６０及び１６１に対して出力する。命令破棄指示は後続のフェッチラインの命令フェッチライン有効ビット部１６０、１６１を“０”にリセットする。命令フェッチライン有効ビット部１６１を“０”にリセットすると破棄された命令は実行されない。なお、命令フェッチライン有効ビット部１６０、１６１は初期値が“１”にセットされる。
【００３４】
（装置の動作の説明）
次に、上述した分岐予測装置を備えるプロセッサの動作について説明する。
まず、命令フェッチアドレス部１３０はパイプライン動作の各サイクルで命令キャッシュ１４０に対して命令フェッチ要求を出力する。また、命令フェッチアドレス部１３０は分岐予測要求を出力する。命令フェッチ要求、分岐予測要求が出力されると、以下の（ア）、（イ）の処理が並行して実行される。
【００３５】
（ア）命令キャッシュ部１４０は命令フェッチ要求に対応して命令フェッチアドレス部１３０の値に基づいて命令フェッチを行い、得られた命令情報を命令デコード部１５０に出力する。命令キャッシュ部１４０の動作は、命令キャッシュメモリの動作として周知の技術が使用されているのでその説明を省略する。
【００３６】
（イ）分岐予測部１００、１０１、及び１０２は分岐予測要求を受け取ると、異なるタイミングで予測結果を出力する。予測結果選択部１２０は分岐予測部１００、１０１、及び１０２が出力した予測結果を適宜選択して命令フェッチアドレス部１３０に反映する。矛盾検出部１１０、１１１は選択結果に応じて不要な命令フェッチ結果を破棄するように予測結果選択部１２０に指示をする。
【００３７】
更に、図２のフローチャートを参照して、上記動作(イ)の命令フェッチアドレスの決定と命令フェッチ結果の破棄の判定の動作（矛盾検出の動作）について説明する。
同図に示すように、パイプライン動作が開始されると、矛盾検出部１１０及び１１１等からなる矛盾検出手段は分岐予測部１００〜１０２の各出力を監視する（ステップＳ１０）。
【００３８】
矛盾検出手段は、(1) 矛盾検出部１１１において分岐予測部１０１と１０２の各出力が一致し（ステップＳ１２；Ｙｅｓ）、矛盾検出部１１０において分岐予測部１００と１０１の各出力が一致している場合（ステップＳ１４；Ｙｅｓ）、予測結果選択部１２０に第一の分岐予測部１００の出力を選択させ、命令アドレス部１３０に設定する（ステップＳ１６）。
【００３９】
矛盾検出手段は、(2) 矛盾検出部１１１において分岐予測部１０１と１０２の各出力が一致し（ステップＳ１２；Ｙｅｓ）、矛盾検出部１１０において分岐予測部１００と１０１の各出力が一致しない場合（ステップＳ１４；Ｎｏ）、予測結果選択部１２０に第二の分岐予測部１０１の出力を選択させ、命令アドレス部１３０に設定する。同時に後続のフェッチした命令を破棄すべく、命令フェチライン有効ビット部１６０及び１６１を“０”に設定する（ステップＳ２０）。
【００４０】
また、矛盾検出手段は、(3) 矛盾検出部１１１において分岐予測部１０１と１０２の各出力が一致しない場合（ステップＳ１２；Ｎｏ）、予測結果選択部１２０に第三の分岐予測部１０２の出力を選択させ、命令アドレス部１３０に設定する。同時に後続のフェッチした命令を破棄すべく、命令フェチライン有効ビット部１６０を“０”に設定する（ステップＳ１８）。
分岐予測装置は、このような分岐予測の処理（ステップＳ１０〜Ｓ２０）を繰り返す。
【００４１】
（具体例）
次に、図３及び図４に示すタイミングチャートを参照して、本発明の分岐予測装置の命令フェッチ動作により選択される命令アドレスの例について説明する。図３は分岐予測部１００乃至１０２の各予測アドレスが一致する場合の例を示している。図４は、分岐予測部１００と１０１との間、分岐予測部１０１と１０２との間で予測アドレスの不一致が生じる場合（分岐予測部間で予測アドレスの不一致が発生する場合）の例を示している。両図の横軸は時間軸であり、クロック信号Ｔ０乃至Ｔ１０に従って処理のステージが進む。
【００４２】
（命令フェッチ動作の概略）
まず、命令フェッチ処理は命令フェッチアドレスを用いて開始される。時刻Ｔ０では所定の命令フェッチアドレスを用いて命令キャッシュに対して命令フェッチ指示を出力する。時刻Ｔ０では平行して、第一、第二、第三の分岐予測手段に対して命令フェッチアドレスを出力する。
【００４３】
第一の分岐予測手段は時刻Ｔ０から時刻Ｔ１の間に次の命令フェッチアドレスを計算し出力する。命令フェッチアドレス部ではこの結果を時刻Ｔ１の命令フェッチアドレスとして反映する。
【００４４】
第二の分岐予測手段は、時刻Ｔ１から時刻Ｔ２の間で、時刻Ｔ０に開始した分岐予測結果を出力する。この結果は時刻Ｔ１の第一の分岐予測手段の出力と一致していると仮定する。この場合、後続の命令のフェッチは継続される。時刻Ｔ１では並行して、第一、第二、第三の分岐予測手段に対して命令フェッチアドレスを出力する。
【００４５】
時刻Ｔ１から時刻Ｔ２の間では、第一の分岐予測手段が時刻Ｔ２のための命令フェッチアドレスを出力する。この場合、図２のフローチャートに従って第一の分岐予測手段の結果が時刻Ｔ２のための命令フェッチアドレスとして反映される。
【００４６】
第三の分岐予測手段は、時刻Ｔ２から時刻Ｔ３の間で、時刻Ｔ０に開始した分岐予測結果を出力する。この結果は時刻Ｔ１から時刻Ｔ２に出力された第二の分岐予測手段の出力と一致していると仮定する。この場合、後続の命令フェッチは継続される。
【００４７】
時刻Ｔ２から時刻Ｔ３の間では、第二の分岐予測手段が時刻Ｔ１に開始した分岐予測結果を出力する。この結果が時刻Ｔ２で得られた第一の分岐予測手段と異なるため（図４の例）、後続の命令フェッチ有効ビットがリセットされる。
時刻Ｔ３の命令フェッチアドレスには、第二の分岐予測手段の出力結果が反映される。
【００４８】
時刻Ｔ３から時刻Ｔ４では第三の分岐予測手段が時刻Ｔ１に開始した分岐予測結果を出力する。この結果が時刻Ｔ２に得られた第二の分岐予測結果と一致していないため、後続の命令フェッチは破棄される。
【００４９】
時刻Ｔ７は第二の分岐予測手段の出力と第三の分岐予測手段の矛盾した例（図４の例）である。アドレスＣ５が次のフェッチアドレスとして選択され、命令フェッチアドレスとして利用される。
【００５０】
（予測アドレスが一致する場合の例）
まず、予測アドレスが一致する場合について説明すると、図３に示すように、時刻Ｔ０において、命令フェッチアドレス部１３０は命令フェッチアドレスＡ０を用いて命令キャッシュ部１４０に対して命令フェッチ指示を出力する。また、同時に、第一の分岐予測部１００、第二の分岐予測部１０１、第三の分岐予測部１０２に対して命令フェッチアドレスＡ０を出力する。なお、命令フェッチライン有効ビット部１６０、１６１の初期値は“１”である。
【００５１】
時刻Ｔ０から時刻Ｔ１の間において、分岐予測部１００は次の命令フェッチアドレスＡ１を計算し出力する。分岐予測部１０１及び１０２はまだ予測アドレスを出力しない。予測結果選択部１２０は分岐予測部１００が出力したアドレスＡ１を選択をする。
【００５２】
時刻Ｔ１において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ１を反映する。
【００５３】
時刻Ｔ１から時刻Ｔ２の間において、命令フェッチアドレス部１３０はアドレスＡ１を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ２を出力する。分岐予測部１０１は時刻Ｔ０に開始した分岐予測結果（アドレスＡ１）を出力する。分岐予測部１０２はまだ予測アドレスの出力を発生しない。矛盾検出部１１０は分岐予測部１０１の予測アドレスＡ1と分岐予測部１００の前回の予測アドレスＡ１が一致したことを判別する。予測結果選択部１２０は分岐予測部１００が出力したアドレスＡ２を選択する。
【００５４】
時刻Ｔ２において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ２を反映する。また、矛盾検出部１１０の一致判別出力により命令フェッチライン有効ビット部１６０は“１”が維持され、アドレスＡ１は破棄されない（維持される）。
【００５５】
時刻Ｔ２から時刻Ｔ３の間において、命令フェッチアドレス部１３０はアドレスＡ２を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ３を出力する。分岐予測部１０１は分岐予測結果（アドレスＡ２）を出力する。分岐予測部１０２は予測アドレスＡ１を出力する。矛盾検出部１１０は分岐予測部１０１の予測アドレスＡ２と分岐予測部１００の前回の予測アドレスＡ２との一致を判別する。また、矛盾検出部１１１は分岐予測部１０２の予測アドレスＡ１と分岐予測部１０１の前回の予測アドレスＡ１との一致を判別する。予測結果選択部１２０は分岐予測部１００が出力したアドレスＡ３を選択をする。
【００５６】
時刻Ｔ３において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ３を反映する。また、矛盾検出部１１０の一致判別出力により命令フェッチライン有効ビット部１６０は“１”となり、アドレスＡ２は破棄されない（維持される）。また、矛盾検出部１１１の一致判別出力により命令フェッチライン有効ビット部１６０、１６１は“１”が維持され、アドレスＡ０、アドレスＡ１は破棄されない（維持される）。それにより、命令アドレスＡ０、Ａ１の実行結果は破棄されない。
【００５７】
時刻Ｔ３から時刻Ｔ４の間において、命令フェッチアドレス部１３０はアドレスＡ３を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ４を出力する。分岐予測部１０１はアドレスＡ３を出力する。分岐予測部１０２は予測アドレスＡ２を出力する。矛盾検出部１１０は分岐予測部１０１の予測アドレスＡ３と分岐予測部１００の前回の予測アドレスＡ３との一致を判別する。また、矛盾検出部１１１は分岐予測部１０２の予測アドレスＡ２と分岐予測部１０１の前回の予測アドレスＡ２との一致を判別する。予測結果選択部１２０は分岐予測部１００が出力したアドレスＡ４を選択をする。
【００５８】
時刻Ｔ４において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ４を反映する。また、矛盾検出部１１０の一致判別出力により命令フェッチライン有効ビット部１６０は“１”が維持され、アドレスＡ３は破棄されない（維持される）。また、矛盾検出部１１１の一致判別出力により命令フェッチライン有効ビット部１６０、１６１は“１”が維持され、アドレスＡ１、アドレスＡ２は破棄されない（維持される）。それにより、命令アドレスＡ１、Ａ２の実行結果は破棄されない。
【００５９】
同様の処理が繰り返されて、図３に示すように命令アドレスＡ０〜Ａ９、…がフェッチされる。
このように、出力が遅延する第三の分岐予測部１０２の予測結果を待たずに処理を行うので演算時間が短縮される。
【００６０】
（予測アドレスが一致しない場合の例）
次に、図４を参照して分岐予測部間で予測アドレスの不一致が生じる場合について説明する。前述したように、予測時間の短い分岐予測部よりも予測時間の長い分岐予測部の方が予測精度が高いものである。
【００６１】
まず、時刻Ｔ０において、命令フェッチアドレス部１３０は命令フェッチアドレスＡ０を用いて命令キャッシュ部１４０に対して命令フェッチ指示を出力する。また、同時に第一の分岐予測部１００、第二の分岐予測部１０１、第三の分岐予測部１０２に対して命令フェッチアドレスＡ０を出力する。
【００６２】
時刻Ｔ０から時刻Ｔ１の間において、分岐予測部１００は次の命令フェッチアドレスＡ１を計算し出力する。分岐予測部１０１及び１０２はまだ出力を発生しない。予測結果選択部１２０は分岐予測部１００が出力したアドレスＡ１を選択する。なお、命令フェッチライン有効ビット部１６０、１６１は“１”が初期設定されている。
【００６３】
時刻Ｔ１において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ１を反映する。
【００６４】
時刻Ｔ１から時刻Ｔ２の間において、命令フェッチアドレス部１３０はアドレスＡ１を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は予測アドレスＡ２を出力する。分岐予測部１０１は時刻Ｔ０に開始した分岐予測結果（アドレスＡ１）を出力する。分岐予測部１０２はまだ予測アドレスの出力を発生しない。矛盾検出部１１０は分岐予測部１０１の予測アドレスＡ１と分岐予測部１００の前回の予測アドレスＡ１との一致を判別する。予測結果選択部１２０は分岐予測部１００が出力したアドレスＡ２を選択する。
【００６５】
時刻Ｔ２において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ２を反映する。また、矛盾検出部１１０の一致判別出力により命令フェッチライン有効ビット部１６０は“１”が維持され、アドレスＡ１は破棄されない（維持される）。
【００６６】
時刻Ｔ２から時刻Ｔ３の間において、命令フェッチアドレス部１３０はアドレスＡ２を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ３を出力する。ここで、分岐予測部１０１は分岐予測結果としてアドレスＢ２を出力すると仮定する。分岐予測部１０２は予測アドレスＡ１を出力する。矛盾検出部１１０は、分岐予測部１０１の予測アドレスＢ２と分岐予測部１００の前回の予測アドレスＡ２とが一致しないので不一致を判別する。また、矛盾検出部１１１は、分岐予測部１０２の予測アドレスＡ１と分岐予測部１０１の前回の予測アドレスＡ１との一致を判別する。予測結果選択部１２０は分岐予測部１０１が出力したアドレスＢ２を選択する。
【００６７】
時刻Ｔ３において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＢ２を反映する。また、矛盾検出部１１０は、分岐予測部１００の出力（アドレスＡ２）と分岐予測部１０１の出力（アドレスＢ２）が一致しないので命令フェッチライン有効ビット部１６０に“０”を設定する。アドレスＡ２の処理は破棄される。また、矛盾検出部１１１は、分岐予測部１０２の予測アドレスＡ１と分岐予測部１０１の前回の予測アドレスＡ１とが一致したので命令フェッチライン有効ビット部１６１の“１”を維持する。アドレスＡ１は破棄されない（維持される）。それにより、命令アドレスＡ１の内容の実行結果は破棄されない。
【００６８】
時刻Ｔ３から時刻Ｔ４の間において、命令フェッチアドレス部１３０はアドレスＢ２を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ４を出力する。分岐予測部１０１はまだアドレスを出力しない。ここで、分岐予測部１０２が予測アドレスＣ２を出力すると仮定する。矛盾検出部１１１は、分岐予測部１０２の予測アドレスＣ２と分岐予測部１０１の前回の予測アドレスＢ２との不一致を判別する。予測結果選択部１２０は分岐予測部１０２が出力したアドレスＣ２を選択する。
【００６９】
時刻Ｔ４において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＣ２を反映する。また、矛盾検出部１１１は、分岐予測部１０２の出力（予測アドレスＣ２）と分岐予測部１０１の出力（Ｂ２）が一致しないので命令フェッチライン有効ビット部１６０及び１６１を共に“０”にリセットする。それにより、命令アドレスＡ２、Ｂ２の内容の実行結果は破棄される。
【００７０】
時刻Ｔ４から時刻Ｔ５の間において、命令フェッチアドレス部１３０はアドレスＣ２を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ５を出力する。分岐予測部１０１はまだ予測アドレスを出力しない。分岐予測部１０２も予測アドレスを出力しない。
【００７１】
時刻Ｔ５において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ５を反映する。命令フェッチライン有効ビット部１６０は“１”にセットされ、命令フェッチライン有効ビット部１６１は命令フェッチライン有効ビット部１６０の前回の“０”出力を取り込んで“０”を維持する。
【００７２】
時刻Ｔ５から時刻Ｔ６の間において、命令フェッチアドレス部１３０はアドレスＡ５を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ６を出力する。分岐予測部１０１は予測アドレスＡ５を出力する。分岐予測部１０２は予測アドレスをまだ出力しない。矛盾検出部１１０は、分岐予測部１０１の出力（アドレスＡ５）と分岐予測部１００の前回の出力（アドレスＡ５）との一致を判別する。
【００７３】
時刻Ｔ６において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ６を反映する。また、矛盾検出部１１０は、分岐予測部１００の出力（アドレスＡ５）と分岐予測部１０１の出力（アドレスＡ５）が一致するので命令フェッチライン有効ビット部１６０の“１”を維持する。命令フェッチライン有効ビット部１６１は命令フェッチライン有効ビット部１６０の前回の“１”出力を取り込んで“１”に設定される。
【００７４】
時刻Ｔ６からＴ７の間において、命令フェッチアドレス部１３０はアドレスＡ６を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ７を出力する。分岐予測部１０１はアドレスＡ６を出力する。ここで、分岐予測部１０２が予測アドレスＣ５を出力すると仮定する。矛盾検出部１１１は、分岐予測部１０２の予測アドレスＣ５と分岐予測部１０１の前回の予測アドレスＡ５との不一致を判別する。予測結果選択部１２０は分岐予測部１０２が出力したアドレスＣ５を選択する。
【００７５】
時刻Ｔ７において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＣ５を反映する。また、矛盾検出部１１１の不一致出力は、命令フェッチライン有効ビット部１６０及び１６１を共に“０”にリセットする。それにより、命令アドレスＡ５、Ａ６の内容の実行結果は破棄される。
【００７６】
時刻Ｔ７から時刻Ｔ８の間において、命令フェッチアドレス部１３０はアドレスＣ５を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ８を出力する。分岐予測部１０１はまだ予測アドレスを出力しない。分岐予測部１０２も予測アドレスを出力しない。
【００７７】
時刻Ｔ８において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ８を反映する。命令フェッチライン有効ビット部１６０は“１”にセットされ、命令フェッチライン有効ビット部１６１は命令フェッチライン有効ビット部１６０の前回の“０”出力を取り込んで“０”を維持する。
【００７８】
時刻Ｔ８から時刻Ｔ９の間において、命令フェッチアドレス部１３０はアドレスＡ８を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ９を出力する。分岐予測部１０１は予測アドレスＡ８を出力する。分岐予測部１０２は予測アドレスをまだ出力しない。矛盾検出部１１０は、分岐予測部１０１の出力（アドレスＡ８）と分岐予測部１００の前回の出力（アドレスＡ８）との一致を判別する。
【００７９】
時刻Ｔ９において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ９を反映する。また、矛盾検出部１１０は、分岐予測部１００の前回出力（アドレスＡ８）と分岐予測部１０１の出力（アドレスＡ８）が一致するので命令フェッチライン有効ビット部１６０の“１”を維持する。命令フェッチライン有効ビット部１６１は命令フェッチライン有効ビット部１６０の前回の“１”出力を取り込んで“１”に設定される。
【００８０】
時刻Ｔ９からＴ１０の間において、命令フェッチアドレス部１３０はアドレスＡ９を命令キャッシュ部１４０、分岐予測部１００〜１０２に出力する。分岐予測部１００は次の予測アドレスＡ１０を出力する。分岐予測部１０１はアドレスＡ９を出力する。分岐予測部１０２が予測アドレスＡ８を出力する。矛盾検出部１１１は、分岐予測部１０２の予測アドレスＡ８と分岐予測部１０１の前回の予測アドレスＡ８との一致を判別する。予測結果選択部１２０は分岐予測部１０２が出力したアドレスＡ８を選択する。
【００８１】
時刻Ｔ１０において、命令フェッチアドレス部１３０は命令フェッチアドレスとしてアドレスＡ１０を反映する。
【００８２】
以下、同様の処理が繰り返されて、図４に示すように命令アドレスＡ０、Ａ１、Ｃ２、Ｃ５、Ａ８、Ａ９、Ａ１０、…がフェッチされる。
このように、出力が遅延する第三の分岐予測部１０２の予測結果を待たずに処理を行うので演算時間（予測レイテンシ）が短縮される。
【００８３】
（実施例の効果）
図５を参照して実施例の構成による予測例について説明する。例えば、図１に示す例において、第一の分岐予測手段が７０％の精度、第二の分岐予測手段が９０％の精度、第三の分岐予測手段が９５％の精度であった場合、平均のレイテンシは図５の結果から１．５４となる。第三の分岐予測手段のレイテンは３サイクルであるため、予測精度を維持しながら約２倍の高速化が実現できる。
【００８４】
以上説明しように本発明の実施形態によれば、高精度の分岐予測手段を採用した場合に問題となるパイプラインバブルの発生を抑制することができる。
例えば、単純に第三の分岐予測手段のみを採用すると、時刻Ｔ１で得られた分岐予測結果（アドレスＡ１への分岐)が時刻Ｔ３まで得られない。逆に、第一の分岐予測手段のみを採用すると、時刻Ｔ２で得られた分岐予測結果の予測成功率は８０％程度なので高い確率で命令の実行が失敗する。
【００８５】
本発明を採用することにより高い予測精度を実質的に短いレイテンシで計算でき、命令フェッチパイプラインの効率化が実現できる。
【００８６】
なお、上記発明の実施の形態を通じて説明された実施例や応用例は、用途に応じて適宜に組み合わせて、又は変更若しくは改良を加えて用いることができ、本発明は上述した実施形態の記載に限定されるものではない。そのような組み合わせ又は変更若しくは改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００８７】
（産業上の利用の可能性）
本発明は高性能なプロセッサに適用できる。特に、深いパイプラインを持つプロセッサに有効である。
【符号の説明】
【００８８】
１００  第一の分岐予測部（手段）、１０１  第二の分岐予測部（手段）、１０２  第三の分岐予測部（手段）、１１０，１１１  矛盾検出部、１２０  予測結果選択部、１３０命令フェッチアドレス部、１４０  命令キャッシュ部、１６０，１６１  命令フェッチライン有効ビット部、１７０  命令実行ユニット部
【図１】
0005656074.tif 000002
【図２】
0005656074.tif 000003
【図３】
0005656074.tif 000004
【図４】
0005656074.tif 000005
【図５】
0005656074.tif 000006