(57)【特許請求の範囲】
【請求項１】
命令を実行する命令実行部と、
分岐予測対象の命令の命令フェッチよりも前に行われた所定の回数の命令フェッチ毎に、前記命令フェッチにおいて分岐成立と予測した命令が含まれたか否かを示す履歴情報と、前記命令フェッチのアドレスに基づくインデックスにより検索される前記命令に対する重みを格納した重みテーブルとを有し、
前記分岐予測対象の命令の命令フェッチを行う前に、前記所定の回数の命令フェッチに係る前記履歴情報及び前記重みを取得し、取得した前記履歴情報及び前記重みを用いて重み積和演算を行い、前記分岐予測対象の命令の命令フェッチの際に前記重み積和演算により得られた結果と前記分岐予測対象の命令の重みとの演算を行い前記分岐予測対象の命令が分岐成立であるか分岐不成立であるかを予測する分岐予測機構とを有し、
前記分岐予測機構は、前記分岐予測対象の命令の命令フェッチよりも、前記所定の回数の命令フェッチに係る前記履歴情報及び前記重みを用いた重み積和演算にかかるサイクル数前に行われた命令フェッチから前記所定の回数前の命令フェッチまでの間の前記履歴情報及び前記重みを取得して前記重み積和演算を行うことを特徴とする演算処理装置。
【請求項２】
前記分岐予測機構は、前記分岐予測対象の命令の命令フェッチを行うよりも、前記所定の回数の命令フェッチに係る前記履歴情報及び前記重みを用いた重み積和演算にかかるサイクル数分前に、前記履歴情報及び前記重みを取得して前記重み積和演算を開始することを特徴とする請求項１記載の演算処理装置。
【請求項３】
前記分岐予測機構は、前記分岐予測対象の命令の命令フェッチよりも、前記所定の回数の命令フェッチに係る前記履歴情報及び前記重みを用いた重み積和演算にかかるサイクル数前に行われた命令フェッチから前記所定の回数前の命令フェッチまでの間の前記命令フェッチのアドレスをパス履歴として保持することを特徴とする請求項２記載の演算処理装置。
【請求項４】
前記分岐予測機構は、ある命令が分岐成立と予測された場合、当該ある命令が分岐不成立であることを前提として投機的に行っていた命令フェッチのアドレスであって、前記パス履歴に登録されている命令フェッチのアドレスを、前記パス履歴から除くものであり、
前記分岐予測機構は、前記ある命令が分岐成立と予測された場合、前記パス履歴から除かれる命令フェッチのアドレスの個数分だけ、前記パス履歴から追い出されていた命令フェッチのアドレスを前記パス履歴に戻すものであり、
前記分岐予測機構は、前記パス履歴に命令フェッチのアドレスを保持するとともに、分岐成立が予測される場合に備えて、前記個数分の命令フェッチのアドレスを保持するものであることを特徴とする請求項３記載の演算処理装置。
【請求項５】
前記分岐予測機構はさらに、
完了した命令のアドレスに基づく命令パス履歴又は完了した分岐命令のアドレスに基づく分岐命令パス履歴を生成して保持し、分岐命令の予測ミスによる新たな命令フェッチが必要となった場合、前記命令フェッチのアドレスに関するパス履歴を、保持した前記命令パス履歴又は前記分岐命令パス履歴のいずれかに置き換え、前記新たな命令フェッチの実行後は、置き換えた前記命令パス履歴又は前記分岐命令パス履歴のいずれかを用いて分岐予測を行うことを特徴とする請求項１記載の演算処理装置。
【請求項６】
前記演算処理装置はさらに、
分岐命令を登録する分岐リザベーションステーションを有し、
前記分岐予測機構は、
分岐命令が何フェッチライン毎に分岐リザベーションステーションに登録されるかを示す情報に基づき、前記分岐命令パス履歴を生成することを特徴とする請求項５記載の演算処理装置。
【請求項７】
命令を実行する命令実行部と、分岐予測対象の命令の命令フェッチよりも前に行われた所定の回数の命令フェッチ毎に、前記命令フェッチにおいて分岐成立と予測した命令が含まれたか否かを示す履歴情報と、前記命令フェッチのアドレスに基づくインデックスにより検索される前記命令に対する重みを格納した重みテーブルとを有し、分岐予測対象の命令が分岐成立であるか分岐不成立であるかを予測する分岐予測機構とを有する演算処理装置の制御方法であって、
前記分岐予測機構が、前記分岐予測対象の命令の命令フェッチを行う前に、前記所定の回数の命令フェッチに係る前記履歴情報及び前記重みを取得して、取得した前記履歴情報及び前記重みを用いて重み積和演算を行い、
前記分岐予測機構が、前記分岐予測対象の命令の命令フェッチの際に前記重み積和演算により得られた結果と前記分岐予測対象の命令の重みとの演算を行い前記分岐予測対象の命令の分岐予測を行い、
前記重み積和演算は、前記分岐予測機構が、前記分岐予測対象の命令の命令フェッチよりも、前記所定の回数の命令フェッチに係る前記履歴情報及び前記重みを用いた重み積和演算にかかるサイクル数前に行われた命令フェッチから前記所定の回数前の命令フェッチまでの間の前記履歴情報及び前記重みを取得して行うことを特徴とする演算処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置及び演算処理装置の制御方法に関する。
【背景技術】
【０００２】
パイプライン機能を有するプロセッサは、実行する命令が分岐命令である場合、分岐命令が分岐するか否かを分岐予測機構により予測して処理を先に進めるようにしている。分岐予測が失敗すると、分岐予測の結果を基に先行して実行していた処理をすべて破棄して別の処理を実行し直さなければならないために性能ロスとなる。そのため、分岐予測精度の向上は、プロセッサの性能向上を図る上で重要である。
【０００３】
分岐予測機構の第１の形態として、過去に分岐成立した分岐命令の分岐先アドレス（ターゲットアドレス）を分岐履歴として保持し、命令フェッチ（命令の読み出し）と並行して、命令フェッチアドレスをインデックスとして分岐履歴を検索することにより、分岐の成否（分岐成立又は分岐不成立）及び分岐先アドレスを予測する分岐予測方式がある（例えば、特許文献１）。この方式では、分岐先の予測確定までの時間が短いために分岐成立時の無駄な命令フェッチをほぼなくすことが可能であるが、分岐予測に命令列の流れに相当する情報がないので分岐予測精度が低かった。
【０００４】
また、分岐予測機構の第２の形態としてＧ−Ｓｈａｒｅと呼ばれる分岐予測方式がある（例えば、非特許文献１）。この方式では、分岐命令の分岐成立確度と分岐先アドレスを分岐履歴として保持し、フェッチした命令が条件分岐命令であると判断した場合、最近の分岐の成否を時系列に示したグローバル履歴と命令フェッチアドレスとの排他的論理和をインデックスとして分岐成立確度の履歴を検索することにより、分岐の成否を判断して分岐先アドレスを予測する。この方式により、単に分岐先の履歴を検索する第１の形態よりも高い分岐予測精度を得ることが可能である。
【０００５】
第２の形態では、分岐の成否を時系列に示したグローバル履歴の長さが長くなるほど、分岐予測性能を向上させることができる。しかし、グローバル履歴の長さは分岐成立確度の履歴のサイズに依存するため、グローバル履歴の長さを１ビット増やすには分岐成立確度の履歴のサイズを２倍にする必要がある。そのため、グローバル履歴の長さを増やしにくく、分岐履歴の拡張による分岐予測精度の向上の実装面積コストが大きい。
【０００６】
また、分岐予測機構の第３の形態としてＰｅｒｃｅｐｔｒｏｎと呼ばれる分岐予測方式がある（例えば、非特許文献２）。この方式では、分岐予測対象の命令の分岐の成否と分岐予測対象の命令の前にフェッチした命令の分岐の成否との関連性に基づいて分岐予測を行う。分岐予測対象の命令との関連性を重み値として重みテーブルに記憶し、分岐予測時には分岐予測対象の命令のフェッチアドレスをインデックスとして重みテーブルを検索して得られる重み値とグローバル履歴とを対応付けて積和演算した結果を基に分岐予測を行う。
【０００７】
具体的には、分岐予測対象の命令に対してｉ個前（ｉは１≦ｉ≦ｎの自然数）の命令の重みＷ（ｉ）と、ｉ個前の命令が分岐成立ならば“＋１”、分岐不成立ならば“−１”の値を示すグローバル履歴Ｘ（ｉ）とを乗算した結果を積和演算する（Ｗ（０）＋Ｗ（１）×Ｘ（１）＋Ｗ（２）×Ｘ（２）＋・・・＋Ｗ（ｎ）×Ｘ（ｎ））。そして、積和演算した結果が正であれば分岐成立と予測し、積和演算した結果が負であれば分岐不成立と予測する。
【０００８】
第３の形態では、グローバル履歴の長さは重みテーブルの個数に依存しており、グローバル履歴の長さを１ビット増やすには重みテーブルを１個増やせば良い。重みテーブルのサイズが十分に小さい場合、グローバル履歴を増やすことによる実装面積コストは第２の形態と比較して小さくすることができる。しかし、第３の形態においては、分岐予測したい命令のアドレスで重みテーブルを参照して重みを得て、それらの重みを足し合わせた結果を分岐予測結果として使用する。この処理には時間がかかるため、分岐予測のレイテンシを伸ばしたり動作周波数を下げたりする必要が生じる。
【０００９】
また、分岐予測機構の第４の形態としてＰｉｅｃｅｗｉｓｅ−Ｌｉｎｅａｒと呼ばれる分岐予測方式がある（例えば、非特許文献３，４）。この方式は、第３の形態を基にして、分岐予測対象の命令までの命令実行経路を分岐予測に用いることにより、分岐予測精度を向上させることが可能である。具体的には、分岐予測対象の命令のｉ個前の重みテーブルのインデックスを、分岐予測対象の命令に対してｉ個前の命令のフェッチアドレスで検索することにより命令実行経路を分岐予測に反映する。
【００１０】
また、重みテーブルから選択された重みによりグローバル履歴の各分岐結果に対して重み付けを行いグローバル履歴と重みを積和演算することによって重み付き分岐結果の積和演算値を算出するステージ１と、その重み付き分岐結果の積和演算値を用いて予測値を算出するステージ０との２つのステージのパイプラインにより予測処理を構成し、ステージ０の処理を、前回分岐命令が入力された際に行われたステージ１の処理結果を利用して行う分岐予測技術が提案されている（例えば、特許文献２）。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開平６−８９１７３号公報
【特許文献２】特開２００９−３７３０５号公報
【非特許文献】
【００１２】
【非特許文献１】S. McFarling: "Combining Branch Predictors", Western Research Laboratory Technical Note TN-36, June 1993.
【非特許文献２】D. A. Jimenez and C. Lin: "Dynamic branch prediction with perceptrons", In Proceedings of the 7th International Symposium on High Performance Computer Architecture (HPCA-7), p.197-206, January 2001.
【非特許文献３】D. A. Jimenez: "Piecewise linear branch prediction", In Proceedings of the 32nd Annual International Symposium on Computer Architecture (ISCA-32), June 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.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
前述したＰｉｅｃｅｗｉｓｅ−Ｌｉｎｅａｒ分岐予測方式による分岐予測では高い予測精度が得られるものの、後述するように分岐予測機構の回路量が膨大になってしまったり、分岐予測のレイテンシが増大してしまったりする。１つの側面では、本発明の目的は、回路量及び分岐予測のレイテンシが増大することを抑制し、分岐予測の予測精度の高い分岐予測機構を実現することにある。
【課題を解決するための手段】
【００１４】
演算処理装置の一態様は、命令を実行する命令実行部と、分岐予測対象の命令が分岐成立であるか分岐不成立であるかを予測する分岐予測機構とを有する。分岐予測機構は、分岐予測対象の命令の命令フェッチよりも前に行われた所定の回数の命令フェッチ毎に、命令フェッチにおいて分岐成立と予測した命令が含まれたか否かを示す履歴情報と、命令フェッチのアドレスに基づくインデックスにより検索される命令に対する重みを格納した重みテーブルとを有する。分岐予測機構は、分岐予測対象の命令の命令フェッチを行う前に、所定の回数の命令フェッチに係る履歴情報及び重みを取得して重み積和演算を行い、分岐予測対象の命令の命令フェッチの際に重み積和演算により得られた結果と分岐予測対象の命令の重みとの演算を行い分岐予測対象の命令の分岐予測を行う。また、分岐予測機構は、分岐予測対象の命令の命令フェッチよりも、所定の回数の命令フェッチに係る履歴情報及び重みを用いた重み積和演算にかかるサイクル数前に行われた命令フェッチから所定の回数前の命令フェッチまでの間の履歴情報及び重みを取得して重み積和演算を行う。
【発明の効果】
【００１５】
発明の一態様においては、分岐予測対象の命令の命令フェッチから分岐予測の結果を得るまでの分岐予測のレイテンシを低減でき、また、重み積和演算の中間結果を伝搬するための記憶回路を削減することができる。したがって、回路量及び分岐予測のレイテンシが増大することを抑制し、分岐予測の予測精度の高い分岐予測機構を実現することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】情報処理システムの構成例を示す図である。
【図２】第１の実施形態におけるプロセッサの構成例を示す図である。
【図３】第１の実施形態におけるプロセッサでの条件分岐命令の処理例を示す図である。
【図４】第１の実施形態における分岐予測機構の構成例を示す図である。
【図５】第１の実施形態における分岐予測処理を説明するための図である。
【図６】第１の実施形態における分岐予測に係る各ブロックの相関を示す図である。
【図７】第２の実施形態におけるプロセッサの構成例を示す図である。
【図８】第２の実施形態における分岐予測に係る各ブロックの相関を示す図である。
【図９】本実施形態における命令フェッチ及び分岐予測機構のパイプラインを説明するための図である。
【図１０】Ｐｉｅｃｅｗｉｓｅ−Ｌｉｎｅａｒ分岐予測方式による分岐予測処理の例を示す図である。
【図１１】Ｐｉｅｃｅｗｉｓｅ−Ｌｉｎｅａｒ分岐予測方式による分岐予測処理の他の例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態を図面に基づいて説明する。本発明の実施形態では、分岐予測機構は、Ｐｉｅｃｅｗｉｓｅ−Ｌｉｎｅａｒ（ピースワイズリニア）分岐予測方式により分岐命令の分岐予測を行う。
【００１８】
まず、本発明の実施形態における命令フェッチ及び分岐予測機構のパイプラインについて説明する。図９（Ａ）及び図９（Ｂ）は、本実施形態における命令フェッチ及び分岐予測機構のパイプラインを説明するための図である。本実施形態において、命令フェッチは、図９（Ａ）及び図９（Ｂ）に示すように、ＩＡサイクル、ＩＴサイクル、ＩＸサイクル、ＩＭサイクル、ＩＢサイクル、及びＩＲサイクルとパイプライン化されている。
【００１９】
ＩＡサイクルは、命令フェッチアドレスを決定して一次キャッシュメモリに送るサイクルである。また、ＩＡサイクルは、命令フェッチアドレスを分岐予測機構に送るサイクルでもある。ＩＴサイクルは、ＴＬＢ（Translation Lookaside Buffer）にアクセスするサイクルである。ＩＸサイクルは、ＴＬＢを引くための１サイクルである。ＩＭサイクルは、ＴＬＢのタグのマッチサイクルである。ＩＢサイクルは、バッファサイクルであり、一次キャッシュメモリから命令制御部に命令を送るためのサイクルである。ＩＲサイクルは、命令制御部で命令を受け取り、命令に付随する命令フェッチフェーズでの例外などをチェックするサイクルである。
【００２０】
命令フェッチがパイプライン化されて順々に実行されるのと並行に、分岐予測機構もパイプライン化されて分岐予測を実行する。分岐予測機構は、ＩＡサイクルで命令フェッチアドレスを受け取る。それを受けて、分岐予測機構は、ＢＴサイクル及びＢＸサイクルで分岐予測機構のメモリ（ＲＡＭ）を引き、ＢＭサイクルで分岐命令の予測された分岐先を出力する。また、分岐予測機構は、ＢＴサイクルで重みテーブルを引き、ＢＸサイクルで重み演算を行い、ＢＭサイクルで分岐成立（ＴＡＫＥＮ）又は分岐不成立（ＮＯＴ＿ＴＡＫＥＮ）の予測を完了する。分岐予測機構での分岐予測が完了するＢＭサイクルと命令フェッチのＩＭサイクルとがタイミングとしては一致することとなる。
【００２１】
パイプライン化された命令フェッチにおいて、命令フェッチアドレスは、基本的には所定のサイズ分ずつシーケンシャルに増加される。例えば、図９（Ａ）に示すようなシーケンシャルな命令フェッチＩＦＣ１、ＩＦＣ２、ＩＦＣ３、ＩＦＣ４のそれぞれの命令フェッチアドレスは、１つ前の命令フェッチの命令フェッチアドレスにフェッチラインサイズを加えたものとなる。分岐予測の結果が確定するＢＭサイクルまでは、シーケンシャル方向に命令フェッチアドレスを増加させて投機的な命令フェッチが行われる。
【００２２】
分岐予測機構がＢＭサイクルで分岐成立と予測した場合、投機実行されていたシーケンシャルな命令フェッチはキャンセルされる。例えば、図９（Ｂ）に示すように、命令フェッチＩＦＣ１でフェッチされる命令について分岐成立と予測した場合、分岐予測の結果が確定するＢＭサイクル９０１まで命令フェッチＩＦＣ２、ＩＦＣ３は投機実行されており、命令フェッチＩＦＣ１のＢＭサイクル９０１にキャンセルされる。命令フェッチＩＦＣ４のＩＡサイクル９０２では、命令フェッチＩＦＣ１の際に予測された分岐先アドレスを命令フェッチアドレスに決定する。すなわち、命令フェッチＩＦＣ４は、命令フェッチＩＦＣ１の際に予測された分岐先アドレスを用いて行われる。
【００２３】
ここで、Ｐｉｅｃｅｗｉｓｅ−Ｌｉｎｅａｒ分岐予測方式による分岐予測を実現する方法として、次のような方法が考えられる。
【００２４】
・第１の方法
分岐予測対象の命令のｉ個前の命令の重みと（ｉ＋１）個前までの命令の重みの積和演算結果との演算をｉ個前の命令の命令フェッチ時に行い、その結果を次のサイクルに伝搬する。さらに、（ｉ−１）個前の命令の命令フェッチ時には、（ｉ−１）個前の命令の重みと前サイクルから伝搬したｉ個前までの命令の重みの積和演算結果との演算を行い、その結果を次のサイクルに伝搬する。これを繰り返すことで、分岐予測対象の命令の重み積和演算を実現する。
【００２５】
第１の方法では、分岐予測対象の命令の命令フェッチ時には、１個前までの命令の重みの積和演算結果と分岐予測対象の命令の重みとの２入力の加算を行うだけで分岐予測に用いる重みの積和演算結果が得られる。そのため、重み積和演算にかかるレイテンシを隠すことができ、分岐予測のレイテンシを１サイクルとして実現できるため命令フェッチの性能を劣化させることなく、分岐予測の予測精度向上によるプロセッサの性能向上を実現できる。また、１サイクルに実行する演算量が軽減できプロセッサの高周波数化にも適している。
【００２６】
しかし、第１の方法では、次のサイクルに重み積和演算の中間結果を伝搬するためのフリップフロップ等の記憶回路が重みテーブル毎に必要となる。この重み積和演算の中間結果を伝搬するための記憶回路の回路量は、グローバル履歴の長さを伸長したり、重み演算の並列度を上げたり、さらに毎サイクル異なるスレッドの命令フェッチを行うＳＭＴ（Simultaneous Multi Thread）方式のプロセッサ上で実装する場合などには、実装コストとしても消費電力においても無視できない量となる。
【００２７】
第１の方法による分岐予測処理の例を図１０に示す。図１０に示す例では、命令フェッチは、ＩＡサイクル、ＩＴサイクル、ＩＸサイクル、ＩＭサイクル、ＩＢサイクル、及びＩＲサイクルとパイプライン化しており、分岐予測処理も、ＩＡサイクルで確定する命令フェッチアドレスを受け取り、ＢＴサイクル、ＢＸサイクル、及びＢＭサイクルとパイプライン化しており、ＢＭサイクルで分岐予測の結果が確定している。
【００２８】
また、参照する分岐履歴のグローバル履歴（ＧＨＲ：Global History Register）の長さを２０としている。ある命令フェッチにおいて分岐予測を行うとき、その命令フェッチよりも前に行われた２０回分の命令フェッチにおいて分岐成立と予測した命令が含まれたかをグローバル履歴として用いる。グローバル履歴は、１回の命令フェッチに対して１ビットの要素が割り当てられ、分岐成立と予測した命令が含まれていれば“１”とする。
【００２９】
図１０に示す第１の方法による分岐予測処理では、分岐予測対象の命令の命令フェッチに対して２０回前の命令フェッチ時に、そのときの命令フェッチアドレス（ＦＡＤ＜２０＞）で２０回前のフェッチライン用の重みテーブル（Branch Weight Table：ＢＷＴ）の２０番（ＢＷＴ２０）を引く。そして、重みテーブル（ＢＷＴ２０）から得られた重みをフリップフロップ等の記憶回路（ＦＦ＜２０＞）に保存する。
【００３０】
その後、１９回前の命令フェッチ時にも、同様にそのときの命令フェッチアドレス（ＦＡＤ＜１９＞）で重みテーブルの１９番（ＢＷＴ１９）を引く。そして、重みテーブル（ＢＷＴ１９）から得られた重みに記憶回路（ＦＦ＜２０＞）に保存してある重みテーブル（ＢＷＴ２０）から得た重みを足し合わせ中間結果を記憶回路（ＦＦ＜１９＞）に保存する。
【００３１】
その後、１８回前の命令フェッチ時にも、同様にそのときの命令フェッチアドレス（ＦＡＤ＜１８＞）で重みテーブルの１８番（ＢＷＴ１８）を引く。そして、重みテーブル（ＢＷＴ１８）から得られた重みに、記憶回路（ＦＦ＜１９＞）に保存してある重みテーブル（ＢＷＴ２０）から得た重みと重みテーブル（ＢＷＴ１９）から得た重みとを足し合わせた中間結果を足し合わせ中間結果を記憶回路（ＦＦ＜１８＞）に保存する。
【００３２】
これを繰り返していき、２回前の命令フェッチ時に、そのときの命令フェッチアドレス（ＦＡＤ＜２＞）で重みテーブルの２番（ＢＷＴ２）を引く。そして、重みテーブル（ＢＷＴ２）から得られた重みに、記憶回路（ＦＦ＜３＞）に保存してある重みテーブル（ＢＷＴ２０）〜重みテーブル（ＢＷＴ３）からそれぞれ得た重みの積和演算結果を足し合わせ中間結果を記憶回路（ＦＦ＜２＞）に保存する。
【００３３】
その後、１回前の命令フェッチ時に、そのときの命令フェッチアドレス（ＦＡＤ＜１＞）で重みテーブルの１番（ＢＷＴ１）を引く。そして、重みテーブル（ＢＷＴ１）から得られた重みに、記憶回路（ＦＦ＜２＞）に保存してある重みテーブル（ＢＷＴ２０）〜重みテーブル（ＢＷＴ２）からそれぞれ得た重みの積和演算結果を足し合わせ中間結果を記憶回路（ＦＦ＜１＞）に保存する。
【００３４】
これにより、分岐予測対象の命令の命令フェッチを行う際には、重みテーブル（ＢＷＴ２０）〜重みテーブル（ＢＷＴ１）からそれぞれ得た重みの積和演算結果を記憶回路（ＦＦ＜１＞）から得ることができる。したがって、分岐予測対象の命令の分岐予測を行う際は、記憶回路（ＦＦ＜１＞）に保存してある値と、命令フェッチアドレス（ＦＡＤ＜０＞）で重みテーブルの０番（ＢＷＴ０）を引いて得られた分岐予測対象の命令の重みとを足すだけでよいので、分岐予測結果（ＷＲ）が得られるので分岐予測のレイテンシが短くなる。一方で、重み積和演算の中間結果を伝搬するための記憶回路を重みテーブル分設けるため、回路量が増大し実装コストが増大する。
【００３５】
・第２の方法
分岐予測における重み積和演算を分岐予測対象の命令の命令フェッチから数サイクルかけて実行する。第２の方法では、重み積和演算の中間結果を伝搬するための記憶回路の量が第１の方法と比較して大幅に削減可能であり、プロセッサコアの小型化やプロセッサの省電力化には適している。しかし、第２の方法では、分岐予測における重み積和演算の演算時間がそのまま分岐予測のレイテンシに反映されるため、分岐予測のレイテンシが増大してしまう。
【００３６】
第２の方法による分岐予測処理の例を図１１に示す。図１１に示す例では、命令フェッチは、ＩＡサイクル、ＩＴサイクル、ＩＸサイクル、ＩＭサイクル、ＩＢサイクル、及びＩＲサイクルとパイプライン化しており、分岐予測処理は、ＩＡサイクルで確定する命令フェッチアドレスを受けて行われる。
【００３７】
また、参照する分岐履歴のグローバル履歴の長さを２０としている。ある命令フェッチにおいて分岐予測を行うとき、その命令フェッチよりも前に行われた２０回分の命令フェッチにおいて分岐成立と予測した命令が含まれたかをグローバル履歴として用いる。グローバル履歴は、１回の命令フェッチに対して１ビットの要素が割り当てられ、分岐成立と予測した命令が含まれていれば“１”とする。
【００３８】
図１１に示す第２の方法による分岐予測処理では、分岐予測対象の命令の命令フェッチよりも前に行われた２０回分の命令フェッチの命令フェッチアドレス（ＦＡＤ＜２０＞〜ＦＡＤ＜１＞）を記憶しておく。そして、分岐予測対象の命令の命令フェッチの際に、同時にすべての重みテーブル（ＢＷＴ２０〜ＢＷＴ０）をそれぞれ対応する命令フェッチアドレス（ＦＡＤ＜２０＞〜ＦＡＤ＜０＞）で引き、各重みテーブル（ＢＷＴ２０〜ＢＷＴ０）から得られた重みを足し合わせ分岐予測結果（ＷＲ）とする。
【００３９】
第２の方法では、同時にすべての重みテーブルを引いて計算を行うので、重み積和演算の中間結果を保存する記憶回路として、グローバル履歴の長さ分の大量の記憶回路を持つ必要がなく、回路量の増大を抑えて実装コストの増大を抑制することができる。一方で、グローバル履歴の長さ分の重みを足し合わせるには多くの時間を要するので、プロセッサの高周波数化を実現するには重み積和演算の演算を数サイクルに分ける必要がある。図１１に示す例では、３サイクル（ＢＸ１、ＢＸ２、ＢＸ３）かけて重み積和演算の演算を行っている。このように第２の方法では、分岐予測のレイテンシが増大する。
【００４０】
以下に説明する本発明の実施形態では、前述した第２の方法を基にして、分岐予測のレイテンシの増大を抑制する。前述した第２の方法では、分岐予測対象の命令の命令フェッチ時に分岐予測に用いるすべての重みテーブルを参照し、それぞれの重みテーブルから得られた重みの積和演算を行うために、重み積和演算の演算時間がそのまま分岐予測のレイテンシに反映されている。
【００４１】
そこで、本実施形態では、分岐予測に用いる重みテーブルの内、分岐予測対象の命令の命令フェッチアドレスをインデックスとして検索する重みテーブルを除いた残りのすべての重みテーブルを分岐予測対象の命令の命令フェッチを行う前に先読みして、重み積和演算を実行する。この重みテーブルの先読みを、それぞれの重みテーブルから得られた重みの足し合わせに要するサイクル数分前の命令フェッチのタイミングから行うことで、分岐予測対象の命令の命令フェッチアドレスで重みテーブルを引いたときには、過去の命令の重みの積和演算結果は計算済みとなっている。そして、分岐予測対象の命令の命令フェッチ時には、先読みによって得られた重みの積和演算結果と、分岐予測対象の命令の重みとの２入力の加算を行うだけで分岐予測に用いる重みの積和演算結果を得る。
【００４２】
これにより、重み積和演算にかかるレイテンシを隠すことができ、分岐予測対象の命令の命令フェッチから分岐予測結果を得るまでの分岐予測のレイテンシを１サイクルとして実現できるため、命令フェッチの性能を劣化させることなく、分岐予測の予測精度向上によるプロセッサの性能向上を実現できる。また、重み積和演算の中間結果を伝搬するための記憶回路として、グローバル履歴の長さ分の記憶回路を持つ必要がないので、回路量の増大を抑えて実装コストの増大を抑制することができる。
【００４３】
（第１の実施形態）
本発明の第１の実施形態について説明する。
図１は、本実施形態における演算処理装置としてのプロセッサ（ＣＰＵ：Central Processing Unit）を含む情報処理システムの構成例を示す図である。図１に示す情報処理システムは、例えば複数のプロセッサ（ＣＰＵ）１１Ａ、１１Ｂ及びメモリ１２Ａ、１２Ｂと、外部装置との入出力制御を行うインターコネクト制御部１３とを有する。
【００４４】
図２は、第１の実施形態におけるプロセッサの構成例を示す図である。図２には、一例としてスーパースカラプロセッサの構成例を示すが、本実施形態におけるプロセッサは、図２に示したプロセッサに限定されるものではない。命令フェッチアドレス生成部２０１が生成する命令フェッチアドレスに従って一次命令キャッシュメモリ２０２からフェッチされた命令は、順番通りに命令デコーダ２０３によって解読され、リザベーションステーションと呼ばれるキュー構造のストレージに蓄積されていく。
【００４５】
リザベーションステーションは、ロード命令やストア命令のアドレス生成用リザベーションステーション（ＲＳＡ：Reservation Station for Address generation）２０４、固定小数点演算用リザベーションステーション（ＲＳＥ：Reservation Station for Execution）２０５、浮動小数点演算用リザベーションステーション（ＲＳＦ：Reservation Station for Floating point）２０６、及び分岐命令用リザベーションステーション（ＲＳＢＲ：Reservation Station for BRanch）２０７のように命令の種類毎に用意されている。リザベーションステーション２０４〜２０７に格納された各々の命令は、それぞれ命令実行の準備が整ったものからアウトオブオーダー（Out of Order）で実行されていく。
【００４６】
ＲＳＡ２０４から投入されるロード命令又はストア命令に応じて、オペランドアドレス生成部２０９によりアドレスが生成されて一次データキャッシュメモリ２１０に対するアクセスが実行される。ＲＳＥ２０５から投入される固定小数点演算命令に応じて、演算部２１１、固定小数点更新バッファ２１２、及び固定小数点レジスタ２１３により固定小数点演算が実行される。ＲＳＦ２０６から投入される浮動小数点演算命令に応じて、演算部２１４、浮動小数点更新バッファ２１５、及び浮動小数点レジスタ２１６により浮動小数点演算が実行される。ＲＳＢＲ２０７は、分岐の確定を待って各種制御を行う。
【００４７】
一方で、命令デコーダ２０３によって解読された命令は、その順番通りに命令識別子（ＩＩＤ：Instruction Identification）が割り振られ、順番通りにコミット処理を行うコミットスタックエントリ（ＣＳＥ：Commit Stack Entry）２０８に送られる。コミットスタックエントリ２０８は、命令デコーダ２０３によってデコードされた命令を命令の実行順番通りにためておくキュー構造のストレージと、キューの情報と各処理パイプラインからの完了報告を基にコミット処理を行う完了処理回路とに分けられる。
【００４８】
命令デコーダ２０３で解読された命令は、コミットスタックエントリ２０８のキューに貯められ、命令処理完了の報告を待つ。各々のリザベーションステーション２０４〜２０７においてアウトオブオーダーで実行された命令は終了報告がコミットスタックエントリ２０８に送られ、コミットスタックエントリ２０８の完了処理回路でプログラム本来の実行順序に従って、キューに貯められた完了報告待ちの命令の中から終了報告に対応する命令が終了（コミット）され、資源の更新が行われる。コミットスタックエントリ２０８によりプログラムカウンタ２１７及びコンディションコードレジスタ２１８が更新される。
【００４９】
分岐予測機構２１９は、命令フェッチアドレス生成部２０１から出力された命令フェッチアドレスを受け取り、命令フェッチと並行して分岐予測を実行する。分岐予測機構２１９は、受け取った命令フェッチアドレスを基に分岐予測を行い、分岐成立又は分岐不成立を示す分岐方向と分岐先アドレスの予測結果を命令フェッチアドレス生成部２０１に返す。予測された分岐方向が分岐成立であった場合、命令フェッチアドレス生成部２０１は次の命令フェッチアドレスとして分岐予測機構２１９によって予測された分岐先アドレスを選択する。
【００５０】
第１の実施形態におけるプロセッサでの条件分岐命令の処理例を図３に示す。一次命令キャッシュメモリ２０２からフェッチされ命令デコーダ２０３によって分岐命令であると解読された命令は、ＲＳＢＲ２０７に格納され、分岐が判断できる状態になるのを待つ。
【００５１】
条件分岐命令ではコンディションコード（ＣＣ：Condition Code）と呼ばれるレジスタの値によって分岐成立であるか分岐不成立であるかを確定する。そのため、直前のコンディションコード変更命令の処理が演算部２１１で完了しなければ、後続の条件分岐命令は分岐の確定をすることができない。なお、コンディションコードレジスタ２１８はコンディションコード変更命令がコミットされたときに更新されるが、コンディションコードレジスタ２１８が更新されてからＲＳＢＲ２０７で分岐の判断を行うと時間がかかる。そこで、本実施形態では、演算部２１１で計算されたコンディションコードをＲＳＢＲ２０７へ直接送りＲＳＢＲ２０７で分岐の判断を行う。無条件分岐命令については、コンディションコードを待つ必要がないためＲＳＢＲ２０７が単独で分岐を判断する。
【００５２】
分岐が判断できる状態になるとＲＳＢＲ２０７で分岐の判断を行って終了報告及び資源の更新に必要な情報ＣＭＭ（ＣＭＡ）をコミットスタックエントリ２０８−２へ送る。また、完了処理待ち命令のキューを蓄積する回路であるコミットスタックエントリ２０８−１からキュー情報ＱＩＦがコミットスタックエントリ２０８−２へ送られる。コミットスタックエントリ２０８−２は、ＲＳＢＲ２０７及びコミットスタックエントリ２０８−１からの報告を受けて完了処理を行い、資源の更新を行う。
【００５３】
分岐予測が外れた場合、投機実行されていた分岐命令以降の処理をパイプラインからすべて消し、正しい分岐先アドレスで新たに命令フェッチを行う必要がある。第１の実施形態では、コミットスタックエントリ２０８で分岐予測に失敗した命令が完了処理待ち命令のキューの先頭（ＴＯＱ：Top of Queue）となった場合、その命令を完了させてプログラムカウンタ等の資源を更新する。また、同時にそのときにパイプライン上にいるすべての演算は誤った分岐予測による投機実行であるので、それらをすべてキャンセルして更新されたプログラムカウンタ（正しい分岐先アドレス）から新たに命令フェッチを行う。分岐予測機構２１９の情報の更新は、完了した命令の情報ＣＭＢをコミットスタックエントリ２０８から受け取り、それを基に行う。
【００５４】
図４は、第１の実施形態における分岐予測機構２１９の構成例を示す図である。分岐予測機構２１９は、ターゲットアドレス部４０１、タグ部４０２、フラグ部４０３、条件分岐予測部４０４、及び分岐予測判断部４０５を有する。ターゲットアドレス部４０１は、分岐先アドレスを記憶する。タグ部４０２は、タグを記憶する。フラグ部４０３は、分岐命令のフラグ（条件分岐である等）を記憶する。
【００５５】
条件分岐予測部４０４は、条件分岐命令の分岐成立又は分岐不成立を判別する。条件分岐予測部４０４は、例えばＰｉｅｃｅｗｉｓｅ＿Ｌｉｎｅａｒ（ピースワイズリニア）分岐予測器である。分岐予測判断部４０５は、それぞれの情報から最終的な分岐予測判断を行い命令フェッチアドレス生成部２０１に分岐予測結果を送る。本実施形態では条件分岐予測部をPIECEWISE_LINEAR分岐予測器で実現する。
【００５６】
分岐予測を行う際は、命令フェッチアドレス生成部２０１から分岐予測対象の命令の命令フェッチアドレスＦＡＤが分岐予測機構２１９に供給される。分岐予測機構２１９は、それを受けて分岐予測対象の命令の命令フェッチアドレスＦＡＤの一部をインデックスとして、分岐先アドレスを保存してあるターゲットアドレス部４０１を引き、分岐予測対象の命令が分岐成立と予測されたときの分岐先アドレスＴＧＡを出力する。
【００５７】
同時に同一のインデックスでタグを保存してあるタグ部４０２を引き、タグＴＡＧを得る。タグＴＡＧは、例えば命令フェッチアドレスＦＡＤのインデックスとして使用しないビットとし、引いてきたタグＴＡＧと分岐予測対象の命令のインデックスとして使用しなかったアドレス部分とのマッチをとることでタグマッチとする。同時に同一のインデックスでフラグを保存してあるフラグ部４０３を引き、フラグＦＬＧを得る。フラグＦＬＧは、例えばその命令が条件分岐命令であるか否か等の情報である。
【００５８】
同時に命令フェッチアドレスＦＡＤの一部を条件分岐予測部４０４に渡し、条件分岐予測部４０４は、そのアドレスを受けて分岐予測対象の命令の分岐成立又は分岐不成立を予測する。条件分岐予測部４０４は、ＩＦＣＨ（命令フェッチ）ベースのパスヒストリ４１１、ＣＯＭＭＩＴ（コミット）ベースのパスヒストリ４１２、重みテーブル４１３、及び重み演算部４１４を有する。条件分岐予測部４０４の各ブロックの動き及び信号の流れの詳細については後述する。
【００５９】
分岐予測機構２１９での分岐予測結果の出力は、例えば次のように行われる。以下の判断は各部からの情報を基に分岐予測判断部４０５が行う。まず、分岐予測判断部４０５は、タグ部４０２で引いたタグＴＡＧがマッチしているかを見る。タグＴＡＧがマッチしていない場合、条件分岐予測部４０４では分岐予測を行わず、分岐予測機構２１９の分岐予測の結果として分岐不成立を出力する。
【００６０】
タグＴＡＧがマッチした場合、分岐予測判断部４０５は、フラグ部４０３から得たフラグＦＬＧによって処理を変える。フラグ部４０３から得たフラグＦＬＧによって、その命令が無条件分岐命令であることが分かった場合、条件分岐予測部４０４からの情報は見ずに、分岐予測の結果を分岐成立としてターゲットアドレス部４０１より得た分岐先アドレスＴＧＡを命令フェッチアドレス生成部２０１に戻す。命令フェッチアドレス生成部２０１は、それを受けてその分岐先アドレスから再び命令フェッチを始める。
【００６１】
タグＴＡＧがマッチし、かつフラグ部４０３から得たフラグＦＬＧにより、命令が条件分岐命令であることが分かった場合、条件分岐予測部４０４からの分岐成立又は分岐不成立の情報を基に分岐するかどうかを判断する。条件分岐予測部４０４から分岐成立の予測が出た場合、ターゲットアドレス部４０１より得た分岐先アドレスＴＧＡを命令フェッチアドレス生成部２０１に戻す。命令フェッチアドレス生成部２０１は、それを受けてその分岐先アドレスから再び命令フェッチを始める。
【００６２】
図５は、第１の実施形態における条件分岐予測部４０４による分岐予測処理を説明するための図である。図５に示す例では、命令フェッチは、ＩＡサイクル、ＩＴサイクル、ＩＸサイクル、ＩＭサイクル、ＩＢサイクル、及びＩＲサイクルとパイプライン化しており、分岐予測処理は、ＩＡサイクルで確定する命令フェッチアドレスを受けて行われる。
【００６３】
また、分岐予測の際に参照する分岐履歴のグローバル履歴（ＧＨＲ：Global History Register）の長さを２０としている。ある命令フェッチにおいて分岐予測を行うとき、その命令フェッチよりも前に行われた２０回分の命令フェッチにおいて分岐成立と予測した命令が含まれたかをグローバル履歴として用いる。グローバル履歴は、１回の命令フェッチに対して１ビットの要素が割り当てられ、分岐成立と予測した命令が含まれていれば“１”とする。
【００６４】
また、以下に説明する本実施形態での２０個の命令の重みの足し合わせには３サイクルかかるものとする。この場合、本実施形態では分岐予測対象の３回以上前の命令フェッチを分岐予測に反映させる。そこで、分岐予測対象の命令の命令フェッチの２３回前の命令フェッチから３回前の命令フェッチまでの命令フェッチアドレスを記憶しておき、分岐予測対象の命令の命令フェッチを行う３サイクル前から、それぞれのアドレスで重みテーブル（ＢＷＴ２０〜ＢＷＴ１）を引いて重みを得て、３サイクルかけて足し合わせる。分岐予測対象の命令の命令フェッチアドレスでも重みテーブル（ＢＷＴ０）を引き、重みテーブル（ＢＷＴ２０〜ＢＷＴ１）から得た重みを足し合わせた結果（ＷＲＡ）と重みテーブル（ＢＷＴ０）から得た重みを足すことで分岐予測結果（ＷＲＢ）を得る。
【００６５】
なお、本実施形態では、分岐予測対象の命令の命令フェッチの直前の命令フェッチの命令フェッチアドレスを分岐予測に用いることができない。図５に示す例では、分岐予測対象の命令の命令フェッチの直前の２回の命令フェッチのアドレスを分岐予測に用いることができない。しかし、もし３回前の命令フェッチの分岐予測結果が分岐成立であった場合、直後の２回の命令フェッチはキャンセルされることになる。なぜなら、分岐予測が分岐成立であると確定するのは、命令フェッチアドレスが確定するＩＡサイクルより複数サイクル後であり（図５に示す例では３サイクル）、分岐成立と予測されるまではシーケンシャルな命令フェッチが行われるためである。もし、分岐成立と予測された場合、その後に投機的に出されたシーケンシャルな命令フェッチは無効である。
【００６６】
同様に、もし分岐予測対象の命令の命令フェッチの１回前の命令フェッチの分岐予測結果が分岐成立である場合、分岐予測対象の命令の命令フェッチは直後に行われるシーケンシャルな命令フェッチであるため分岐成立と予測した時点で無効である。図５に示す例においては、ＩＡサイクルから３サイクル後に分岐予測結果が確定するため分岐予測対象の命令の命令フェッチの１回前、２回前の命令フェッチのアドレスの分岐予測が分岐成立であった場合、分岐予測対象の命令の命令フェッチはその後キャンセルされることとなる。
【００６７】
すなわち、本実施形態において、重みテーブルから得た重みを足し合わせるのに必要なサイクル分前の命令フェッチのアドレスを分岐予測に用いなくても、過去に分岐成立となった分岐予測はすべて分岐予測対象の命令の命令フェッチに反映される。過去の分岐不成立の分岐予測に比べて過去の分岐成立の予測結果の方が分岐予測対象の命令の分岐予測確度への影響度は大きいため、重みテーブルから得た重みを足し合わせるのに必要なサイクル分前の命令フェッチのアドレスを分岐予測に用いなくても、分岐予測確度への影響度を抑えることができる。
【００６８】
第１の実施形態における分岐予測処理では、図５に示すようにＩＦＣＨ（命令フェッチ）ベースのパスヒストリ４１１を導入し、分岐予測対象の命令の命令フェッチより前のグローバル履歴の長さ分の命令フェッチアドレス及び分岐予測結果を記憶しておく。ＩＦＣＨベースのパスヒストリ４１１は、命令フェッチアドレス（の一部）を保存しておくアドレス部４１１−１と分岐成立又は分岐不成立の情報を保存しておくＴＡＫＥＮ保存部４１１−２を有する。
【００６９】
アドレス部４１１−１では、ＩＡサイクルに命令フェッチが出るたびに、その命令フェッチアドレスを登録し、古いものから追い出していく構成となっている。ＴＡＫＥＮ保存部４１１−２では、ＢＭサイクルに分岐予測結果が確定するたびに、その結果を登録し、古いものから追い出していく構成となっている。それらの命令フェッチアドレス（ＦＡＤ＜２０＞〜ＦＡＤ＜２＞）を基にサイクルＴ１で重みテーブル（ＢＷＴ２０〜ＢＷＴ２）を引き、命令の重みを得る。重みテーブル（ＢＷＴ１）は、分岐予測対象の命令の３回前の命令フェッチの際に、そのときの命令フェッチアドレス（ＦＡＤ＜１＞）で引けばよいので、パスヒストリ４１１−１の命令フェッチアドレスを用いる必要はない。
【００７０】
また、重み演算には過去の命令フェッチによって得られた命令のそれぞれが分岐成立と予測された命令を含むか否かの情報が必要となる。それらの情報はＩＦＣＨベースのパスヒストリのＴＡＫＥＮ保存部４１１−２より読み出されて演算に使われる。図５に示すように、パスヒストリからアドレス部４１１−２を読み出すサイクルとＴＡＫＥＮ保存部４１１−２を読み出すサイクルとが異なる。重みテーブル（ＢＷＴ２０〜ＢＷＴ３）から得られる重みに対する分岐成立又は分岐不成立の分岐予測の情報は、重み演算を開始させる前のサイクルには確定しており、パスヒストリのＴＡＫＥＮ保存部４１１−２に保存されている。
【００７１】
したがって、重みテーブル（ＢＷＴ２０〜ＢＷＴ３）から得られる重みに対する分岐成立又は分岐不成立の分岐予測の情報は、サイクルＴ３のタイミングでそれぞれパスヒストリ４１１−２から読み出されて足し合わされていく。重みテーブル（ＢＷＴ２）から得られる重みに対する分岐成立又は分岐不成立の分岐予測の情報は、サイクルＴ３のタイミングで確定するので、確定した分岐予測の情報を用いて重み演算を行う。重みテーブル（ＢＷＴ１）から得られる重みに対する分岐成立又は分岐不成立の分岐予測の情報は、重みテーブル（ＢＷＴ２０〜ＢＷＴ２）から得られる重みの重み演算を開始させるサイクルの次サイクルＴ４に確定する。ゆえに、重みテーブル（ＢＷＴ１）から得られる重みの足し合わせだけは１サイクルだけ遅れて実行される。
【００７２】
ここで、ＩＦＣＨベースのパスヒストリ４１１は、重みテーブル（ＢＷＴ２０〜ＢＷＴ２）を引くための命令フェッチアドレスを保存するエントリ２０〜２番を有する。分岐成立と予測された場合には分岐成立であると確定するまでに誤ったシーケンシャルな命令フェッチを行っており、パスヒストリ４１１にも誤った命令フェッチの情報が登録されてしまっている。
【００７３】
そこで、分岐成立であると確定したときに、それまでに出された誤った投機命令フェッチに対応するパスヒストリを消して追い出されたエントリを戻す必要があるため、パスヒストリ４１１−１のエントリ２０番〜２番から追い出されたエントリを保存しておくエントリが必要となる。図５に示した例の場合、命令フェッチから分岐予測が確定するまでに３サイクルかかるため、分岐予測結果とは異なるシーケンシャルな命令フェッチを最大２回出している。図５に示した構成のパスヒストリ４１１−１では、エントリ２０番〜２番から追い出されたエントリを保存しておくためのエントリを２つ備えている（エントリＲ１番及びＲ２番）。
【００７４】
続いて、分岐予測ミスした場合の動作について述べる。分岐予測をミスした場合には前述したように分岐予測ミスした命令がコミットしたら、プログラムカウンタを正しい分岐先アドレスに更新して、その値で命令フェッチから再びやり直す必要がある。また、その時点でパイプラインを流れている演算は誤った分岐予測によるものであるのでクリアされる。
【００７５】
正しい分岐先から再び命令フェッチを行う場合、ＩＦＣＨベースのパスヒストリ４１１を正しいものに更新しなければならない。なぜなら、再命令フェッチの段階で構成されたパスヒストリ４１１は誤った分岐予測に対するものであり、かつ分岐予測ミスした命令がコミットするときと命令フェッチではステージが大きくずれているためである。再命令フェッチを行う前に分岐ミスした命令の命令フェッチの２０回前の命令フェッチ分の情報にＩＦＣＨベースのパスヒストリ４１１を更新し、その後再命令フェッチを行う必要がある。
【００７６】
そのため、分岐予測機構２１９では、コミットスタックエントリ２０８からの全命令のコミットに係る情報を受けて、ＣＯＭＭＩＴ（コミット）ベースのパスヒストリ４１２も作成している。分岐予測のミスが起きると、ＩＦＣＨベースのパスヒストリ４１１をＣＯＭＭＩＴベースのパスヒストリ４１２で置き換え、再命令フェッチの実行後は、置き換えたパスヒストリを用いて分岐予測を行う。再命令フェッチの２０回前の命令フェッチラインの情報がパスヒストリに載ることとなるので、再命令フェッチの後も再び正しいパスヒストリで分岐予測を行うことができる。ＣＯＭＭＩＴベースのパスヒストリ４１２は、ＩＦＣＨベースのパスヒストリ４１１と同じ構成にする必要がある。すなわち、１つのエントリには１つのフェッチライン毎のコミットしたアドレス及びそのフェッチラインに分岐成立と予測された命令があったか否かの確定情報が入る。
【００７７】
具体的なＣＯＭＭＩＴベースのパスヒストリ４１２の実現方法について説明する。コミットスタックエントリ２０８に命令を登録する際、フェッチラインの境界が自身であるという情報を保存しておく。その命令がコミットする際、ＣＯＭＭＩＴベースのパスヒストリ４１２にエントリを追加し、最も古いエントリを追い出す。エントリには完了した命令の命令フェッチアドレス（の一部）をアドレス部として保存する。また、コミットスタックエントリ２０８にはＲＳＢＲ２０７からの完了報告とともに分岐命令の分岐成立又は分岐不成立の情報も入ってくる。その情報を基にＣＯＭＭＩＴベースのパスヒストリ４１２のエントリに該当する１つのフェッチライン分の命令の中に分岐成立と予測された命令があったかを判断し、その情報もＣＯＭＭＩＴベースのパスヒストリ４１２に登録する。
【００７８】
Ｐｉｅｃｅｗｉｓｅ＿Ｌｉｎｅａｒ分岐予測方式において、重みテーブルは条件分岐命令がコミットするたびに更新させる必要がある。例えば、分岐成立であれば＋１とし分岐不成立でれば−１とする。本実施形態において、グローバル履歴は、各フェッチラインに付くため、重みテーブルはフェッチラインを超えるたびに更新させる必要がある。第１の実施形態におけるテーブル更新の仕組みを、以下に説明する。
【００７９】
フェッチラインを超える命令がコミットされると、ＣＯＭＭＩＴベースのパスヒストリ４１２を更新するととともに、そのフェッチライン上に条件分岐命令があった場合には更新する前のパスヒストリを用いて各重みを更新する。フェッチラインを超える命令がコミットされるとき、コミットされる自身の命令を含むフェッチラインのアドレスを用いて重みテーブル（ＢＷＴ０）を更新する。
【００８０】
フェッチラインに条件分岐命令が含まれ分岐成立と予測された場合には１を加算し、条件分岐命令が含まれ分岐不成立と予測された場合には１を減算する。フェッチラインに条件分岐命令が含まれなければ重みは更新しない。重みテーブル（ＢＷＴ１）は、その１つ前のフェッチラインに対応する重みである。ゆえに、重みテーブル（ＢＷＴ１）の更新は、ＣＯＭＭＩＴベースのパスヒストリ４１２の１番のアドレスと分岐予測の情報を用いる。同様に、重みテーブル（ＢＷＴ２０）は、ＣＯＭＭＩＴベースのパスヒストリ４１２の２０番のアドレスと分岐予測の情報を用いる。
【００８１】
図６に、第１の実施形態における分岐予測に係る各ブロックの相関性を示す。命令フェッチアドレス生成部２０１は、ＩＡサイクルに命令フェッチアドレスを確定させて分岐予測機構２１９に送る（Ｐ１０１）。分岐予測機構２１９では、その命令フェッチアドレスに対する分岐予測を行うため重みテーブル４１３を引く。それと同時に３つ後の命令フェッチアドレスに対する分岐予測を行うために重みテーブル（ＢＷＴ１）を引いておく。また、それ以降の命令フェッチアドレスに対する分岐予測を行うためにＩＦＣＨベースのパスヒストリ４１１のエントリの２番に命令フェッチアドレスの一部を登録する。その後、命令フェッチが行われるたびにＩＦＣＨベースのパスヒストリ４１１のアドレス部は更新され、古いものが追い出されていく。
【００８２】
命令フェッチの際に、そのフェッチラインに対する分岐予測を行うために数サイクル前に重みテーブル４１３から重みを引く（Ｐ１０２）。重みテーブル４１３を引くためのアドレスは、それぞれ過去のフェッチラインのアドレスで、ＩＦＣＨベースのパスヒストリ４１１のアドレス部より持ってくる。引かれた各重みテーブルの重みは、対応する過去の各フェッチラインの分岐予測情報（Ｐ１０３）と合わせて重み演算部４１４で計算され、分岐予測結果（Ｐ１０４）となる。
【００８３】
分岐予測結果は、命令フェッチアドレス生成部２０１に送られ、分岐成立と予測されたならば分岐先アドレスが命令フェッチアドレスとして採用される。一方で、分岐予測結果は、３つ後のフェッチラインの分岐予測のための計算に再び使用され、またその更に後の分岐予測のためにＩＦＣＨベースのパスヒストリ４１１のＴＡＫＥＮ保存部に登録される。
【００８４】
一方、命令フェッチアドレスは、命令フェッチに使用され（Ｐ１０５）、一次命令キャッシュメモリ２０２からフェッチされた命令は命令デコーダ２０３でデコードされ命令種類毎に各リザベーションステーション６０１に登録される。一方で、命令デコーダ２０３でデコードされた命令は、コミットスタックエントリ２０８に登録され命令の完了（Ｐ１０６）を待つ。
【００８５】
コミットした命令の情報は、ＣＯＭＭＩＴベースのパスヒストリ４１２の更新に使用される（Ｐ１０７）。ＣＯＭＭＩＴベースのパスヒストリ４１２及びコミットした命令の情報は重みテーブルの更新に用いられる（Ｐ１０９）。また、分岐予測ミスの際にＩＦＣＨベースのパスヒストリ４１１は、ＣＯＭＭＩＴベースのパスヒストリ４１２の情報で置換され（Ｐ１０８）、置換された後で再びコミットスタックエントリ２０８の指示で更新されたプログラムカウンタの値を用いて正しい分岐先アドレスからフェッチされる（Ｐ１１０）。
【００８６】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。
図７は、第２の実施形態におけるプロセッサの構成例を示す図である。図７において、図２に示した構成要素と同一の機能を有する構成要素には同一の符号を付し、重複する説明は省略する。
【００８７】
第１の実施形態では、分岐予測ミスした命令がコミットスタックエントリ２０８での完了処理待ち命令のキューの先頭となりコミットされるまでは再命令フェッチを実行できない。その場合、もし分岐命令の前に非常に処理に時間がかかり、かつ分岐予測の判断に影響しない命令があった場合、分岐予測ミスが確定しているのに再命令フェッチを出せないケースが考えられる。分岐予測ミスの確定はＲＳＢＲ２０７からコミットスタックエントリ２０８に分岐命令の完了報告を出す段階ではすでにわかっており、コミットスタックエントリ２０８に完了報告を出すと同時に再命令フェッチの指示を出せればストールを小さくすることができる。
【００８８】
図７に示す第２の実施形態におけるプロセッサは、図２に示した第１の実施形態におけるプロセッサと比べると、ＲＳＢＲ２０７から命令フェッチアドレス生成部２０１への再命令フェッチアドレスのパスが追加されている。ただし、トラップ等が発生した場合にはプログラムカウンタを基に再命令フェッチをかけるため、プログラムカウンタから命令フェッチアドレス生成部２０１へのパスも残っている。また、分岐予測機構２１９の更新は、分岐命令のＣＯＭＰＬＥＴＥ（コンプリート）ベースで行うため、コミットスタックエントリ２０８からではなくＲＳＢＲ２０７からの情報ＣＭＤを用いて分岐予測機構２１９を更新している。
【００８９】
命令フェッチに係る構成は、第１の実施形態と同様に構成することができる。第２の実施形態でも、第１の実施形態と同様に、分岐予測ミスした際にはＩＦＣＨベースのパスヒストリ４１１を置き換える必要がある。ただし、第２の実施形態では、第１の実施形態と比較して、パスヒストリの置き換えのためのテーブルを用意しておくことが難しい。
【００９０】
第２の実施形態では、シーケンシャルカウンタ（ＳＥＱ＿ＣＴＲ：SEAQUENTIAL_COUNTER）と呼ぶ情報を導入する。この情報は命令デコーダ２０３からＲＳＢＲ２０７に登録される際、各分岐命令に付随して、各分岐命令が何フェッチラインぶりにＲＳＢＲ２０７に入ってきたかを示している。分岐命令による処理以外は、命令フェッチアドレスはシーケンシャルに進むためシーケンシャルカウンタの値があれば、分岐命令と分岐命令との間に行われたフェッチライン分についても分岐命令のＣＯＭＰＬＥＴＥベースでパスヒストリを作ることができる。
【００９１】
具体的にシーケンシャルカウンタの実現方法について説明する。命令デコーダ２０３にシーケンシャルカウンタ本体を用意し、フェッチライン境界の命令を発行するたびにカウンタをカウントアップする。また、分岐命令を発行するたびに、その時点でのシーケンシャルカウンタの値を分岐命令に付随させてＲＳＢＲ２０７に送り、ＲＳＢＲ２０７のエントリに登録させ、シーケンシャルカウンタのカウント値を０にする。また、分岐予測ミスが発生した場合、それが確定した時点でのシーケンシャルカウンタの値は誤った分岐予測による値となるのでクリアする。その後、再命令フェッチにより正しい命令がフェッチされてくるとき、シーケンシャルカウンタはカウント動作を再開する。
【００９２】
ＲＳＢＲ２０７からコミットスタックエントリ２０８へ分岐命令の完了報告を出す際、分岐予測機構２１９にもコンプリートした命令の情報を送る。分岐予測機構２１９は、それを受けてＣＯＭＰＬＥＴＥベースのパスヒストリを作成する。その際、終了した分岐命令に付随していたシーケンシャルカウンタの値の分のエントリをＣＯＭＰＬＥＴＥベースのパスヒストリに作り、その分古いエントリを追い出す。このようにすることで、フェッチライン毎のパスヒストリを、第１の実施形態でＣＯＭＭＩＴベースで作成していたように作成することができる。
【００９３】
図８に、第２の実施形態における分岐予測に係る各ブロックの相関性を示す。命令フェッチアドレス生成部２０１は、ＩＡサイクルに命令フェッチアドレスを確定させて分岐予測機構２１９に送る（Ｐ２０１）。分岐予測機構２１９では、その命令フェッチアドレスに対する分岐予測を行うため重みテーブル４１３を引く。それと同時に３つ後の命令フェッチアドレスに対する分岐予測を行うために重みテーブル（ＢＷＴ１）を引いておく。また、それ以降の命令フェッチアドレスに対する分岐予測を行うためにＩＦＣＨベースのパスヒストリ４１１のエントリの２番に命令フェッチアドレスの一部を登録する。その後、命令フェッチが行われるたびにＩＦＣＨベースのパスヒストリ４１１のアドレス部は更新され、古いものは追い出されていく。
【００９４】
命令フェッチの際に、そのフェッチラインに対する分岐予測を行うために数サイクル前に重みテーブル４１３から重みを引く（Ｐ２０２）。重みテーブル４１３を引くためのアドレスは、それぞれ過去のフェッチラインのアドレスで、ＩＦＣＨベースのパスヒストリ４１１のアドレス部より持ってくる。引かれた各重みテーブルの重みは、対応する過去の各フェッチラインの分岐予測情報（Ｐ２０３）と合わせて重み演算部４１４で計算され、分岐予測結果（Ｐ２０４）となる。
【００９５】
分岐予測結果は、命令フェッチアドレス生成部２０１に送られ、分岐成立と予測されたならば分岐先アドレスが命令フェッチアドレスとして採用される。一方で、分岐予測結果は、３つ後のフェッチラインの分岐予測のための計算に再び使用され、またその更に後の分岐予測のためにＩＦＣＨベースのパスヒストリ４１１のＴＡＫＥＮ保存部に登録される。
【００９６】
一方、命令フェッチアドレスは、命令フェッチに使用され（Ｐ２０５）、一次命令キャッシュメモリ２０２からフェッチされた命令は命令デコーダ２０３でデコードされ命令種類毎に各リザベーションステーション８０１に登録される。一方で、命令デコーダ２０３でデコードされた命令は、コミットスタックエントリ２０８に登録され命令の完了（Ｐ２０６、Ｐ２０７）を待つ。また、分岐命令はＲＳＢＲ２０７に登録される。それと同時にシーケンシャルカウンタの値も分岐命令に付随してＲＳＢＲ２０７に登録される（Ｐ２０８）。
【００９７】
シーケンシャルカウンタの値を含むコンプリートした分岐命令の情報は、ＣＯＭＰＬＥＴＥベースのパスヒストリ８０２の更新に使用される（Ｐ２０９）。ＣＯＭＰＬＥＴＥベースのパスヒストリ８０２及びコンプリートした分岐命令の情報は重みテーブルの更新に用いられる（Ｐ２１１）。また、分岐予測ミスの際にＩＦＣＨベースのパスヒストリ４１１は、ＣＯＭＰＬＥＴＥベースのパスヒストリ８０２の情報で置換され（Ｐ２１０）、置換された後で再びＲＳＢＲ２０７の指示で正しい分岐先アドレスからフェッチされる（Ｐ２１２）。
【００９８】
なお、前記実施形態は、何れも本発明を実施するにあたっての具体化のほんの一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００９９】
２０１  命令フェッチアドレス生成部
２０２  一次命令キャッシュメモリ
２０３  命令デコーダ
２０４〜２０７  リザベーションステーション
２０８  コミットスタックエントリ
２１９  分岐予測機構
４０１  ターゲットアドレス部
４０２  タグ部
４０３  フラグ部
４０４  条件分岐予測部
４０５  分岐予測判断部
４１１  パスヒストリ（ＩＦＣＨベース）
４１２  パスヒストリ（ＣＯＭＭＩＴベース）
４１３  重みテーブル
４１４  重み演算部
８０２  パスヒストリ（ＣＯＭＰＬＥＴＥベース）
【図１】
0006683918.tif 000002
【図２】
0006683918.tif 000003
【図３】
0006683918.tif 000004
【図４】
0006683918.tif 000005
【図５】
0006683918.tif 000006
【図６】
0006683918.tif 000007
【図７】
0006683918.tif 000008
【図８】
0006683918.tif 000009
【図９】
0006683918.tif 000010
【図１０】
0006683918.tif 000011
【図１１】
0006683918.tif 000012