(57)【要約】  演算処理装置としてのＣＰＵは、演算完了時の分岐の成立又は不成立が確定した結果を時系列に示した第２ＧＨＲに加え、命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示した第１ＧＨＲを実装する。ＣＰＵ内の分岐予測部は、命令フェッチ時に、分岐履歴（ＢＲＨＩＳ）だけでなく、命令フェッチアドレス及び第１ＧＨＲに基づいて決定される、期待通りの分岐方向であるか否かを示す分岐成立確度を使って、分岐予測を行う。分岐演算の結果に基づいて分岐予測が失敗であると確定した場合に、ＣＰＵ内の分岐履歴更新部が第２ＧＨＲの値を第１ＧＨＲにコピーする。その後、命令フェッチ制御部が命令フェッチを再実行する。
2012127666.tif 000002
【特許請求の範囲】
【請求項１】
命令フェッチアドレスを確定し、命令フェッチを実行する実行手段と、
命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す情報を保持する第１グローバル履歴レジスタ、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスをエントリとして保持する分岐履歴テーブル、前記命令フェッチアドレスに対応する命令が期待通りの分岐方向であるか否かを示す分岐成立確度をエントリとして保持するパターン履歴テーブル、及び前記命令フェッチアドレスをインデックスとして前記分岐履歴テーブルから検索される分類情報と、前記命令フェッチアドレス並びに前記第１グローバル履歴レジスタの情報をインデックスとして前記パターン履歴テーブルから検索される分岐成立確度とに基づいて、前記命令フェッチアドレスに対応する命令の分岐予測を行う予測部を備える分岐予測手段と、
分岐演算完了時の分岐の成立又は不成立が確定した結果を時系列に示す情報を保持する第２グローバル履歴レジスタを備え、分岐演算の結果に基づいて前記予測部による分岐予測が失敗であると確定した場合に、前記第１グローバル履歴レジスタを前記第２グローバル履歴レジスタの情報で更新する更新手段とを備え、
前記第１グローバル履歴レジスタの更新後に、前記実行手段は、前記命令フェッチを再実行することを特徴とする演算処理装置。
【請求項２】
前記第２グローバル履歴レジスタは、前記実行手段が一度にフェッチした複数の命令を一単位として、条件分岐命令の分岐演算が完了したときに更新されることを特徴とする請求項１に記載の演算処理装置。
【請求項３】
前記第２グローバル履歴レジスタは、前記条件分岐命令の分岐演算が完了したときに、分岐命令のアドレスが前記実行手段が一度にフェッチするデータサイズの境界を跨ぐか否かを示す情報と、分岐の成立又は不成立が確定したことを示す情報とに基づいて更新されることを特徴とする請求項２に記載の演算処理装置。
【請求項４】
命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す情報を保持する第１グローバル履歴レジスタ、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスをエントリとして保持する分岐履歴テーブル、命令フェッチアドレスに対応する命令が期待通りの分岐方向であるか否かを示す分岐成立確度をエントリとして保持するパターン履歴テーブル、及び分岐演算完了時の分岐の成立又は不成立が確定した結果を時系列に示す情報を保持する第２グローバル履歴レジスタを備える演算処理装置の演算処理方法であって、
前記命令フェッチアドレスを確定し、命令フェッチを実行する第１手順と、
前記命令フェッチアドレスをインデックスとして前記分岐履歴テーブルから検索される分類情報と、前記命令フェッチアドレス並びに前記第１グローバル履歴レジスタの情報をインデックスとして前記パターン履歴テーブルから検索される分岐成立確度とに基づいて、前記命令フェッチアドレスに対応する命令の分岐予測を行う第２手順と、
分岐演算の結果に基づいて前記第２手順による分岐予測が失敗であると確定した場合に、前記第１グローバル履歴レジスタを前記第２グローバル履歴レジスタの情報で更新する第３手順と、
前記第１グローバル履歴レジスタの更新後に、前記命令フェッチを再実行する第４手順とを含むことを特徴とする演算処理方法。
【請求項５】
演算処理装置と、当該演算処理装置に接続されるメモリとを備える情報処理装置であって、
前記メモリは、前記演算処理装置でフェッチされた命令フェッチアドレスに対応するデータを格納し、
前記演算処理装置は、
前記命令フェッチアドレスを確定し、命令フェッチを実行する実行手段と、
命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す情報を保持する第１グローバル履歴レジスタ、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスをエントリとして保持する分岐履歴テーブル、前記命令フェッチアドレスに対応する命令が期待通りの分岐方向であるか否かを示す分岐成立確度をエントリとして保持するパターン履歴テーブル、及び前記命令フェッチアドレスをインデックスとして前記分岐履歴テーブルから検索される分類情報と、前記命令フェッチアドレス並びに前記第１グローバル履歴レジスタの情報をインデックスとして前記パターン履歴テーブルから検索される分岐成立確度とに基づいて、前記命令フェッチアドレスに対応する命令の分岐予測を行う予測部を備える分岐予測手段と、
前記メモリから前記データを読み出し、分岐演算を実行する分岐演算手段と、
分岐演算完了時の分岐の成立又は不成立が確定した結果を時系列に示す情報を保持する第２グローバル履歴レジスタを備え、前記演算手段による分岐演算の結果に基づいて前記予測部による分岐予測が失敗であると確定した場合に、前記第１グローバル履歴レジスタを前記第２グローバル履歴レジスタの情報で更新する更新手段とを備え、
前記第１グローバル履歴レジスタの更新後に、前記実行手段は、前記命令フェッチを再実行することを特徴とする情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置、情報処理装置及び演算処理方法に関する。
【背景技術】
【０００２】
パイプライン機能を有するプロセッサは、分岐ターゲット（分岐先命令）の投機的実行を可能にし、性能を最大限に発揮するために、分岐予測部を備えている。分岐予測部は、投機的実行による命令処理を先に進めるために、分岐命令について分岐が成立するか否かを予測する。ここで、分岐予測が失敗すると、分岐予測結果を基に先行して投機的に実行していたパイプラインの処理を全て破棄して正しい分岐ターゲットの処理を実行し直すため、分岐予測の失敗はプロセッサの性能を低下させる。このため、分岐予測精度の向上は、プロセッサの性能向上を図る上で特に重要である。【０００３】
分岐予測の一形態として、過去に分岐成立した分岐命令のターゲットアドレスを分岐履歴として保持し、命令フェッチに用いるアドレスをインデックスとして分岐履歴を命令フェッチと並行して検索することで、フェッチを行なう分岐命令の分岐の成立又は不成立と分岐ターゲットアドレスとを予測する方式が知られている。【０００４】
また、分岐予測の他の一形態として、予測対象の分岐命令より以前に実行された分岐命令の成立又は不成立のパターンを分岐予測に利用する第２の方式が知られている。この第２の方式では、分岐命令の成立確度を最近の分岐命令の成立又は不成立のパターン毎に保持することで、状況に応じた分岐予測が可能となるため、高い分岐予測精度を得ることが可能である。例えば、第２の方式では、プログラムのあるルーチンから別のルーチンに移った直後の分岐命令は分岐不成立になりやすい、又は同じ分岐命令でも同一ルーチン内で再度実行される場合は分岐成立になりやすいなどのように、分岐命令の成立確度が分岐予測に反映される。【０００５】
また、第２の方式の一例として、直近の分岐命令の成立又は不成立を時系列で示したグローバル履歴と命令フェッチアドレスとの排他的論理和をインデックスとして分岐履歴を検索することで、分岐命令の成立又は不成立を判断し、分岐ターゲットアドレスを予測するGshare方式が知られている。この方式では、分岐履歴として分岐成立確度及び分岐命令のターゲットアドレスが保持されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平６−０８９１７３号公報
【非特許文献】
【０００７】
【非特許文献１】Scott McFarling  著、「Combining Branch Predictors」、WRL Technical Note TN-36、June 1993
【非特許文献２】E. Sprangle, R. Chappell, M. Alsup & Y. Patt，"The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference,", Jun. 1997, pp. 284-291.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ところで、上記第１の方式では、分岐ターゲットの予測確定までの時間が短くなるため、分岐成立時の無駄な命令フェッチを無くすことが可能である。しかしながら、予測対象の分岐命令より以前に実行された分岐命令の成立又は不成立のパターンに関する情報が分岐予測に使用されておらず、分岐予測の精度が不十分であった。【０００９】
一方、上記Gshare方式では、比較的高い分岐予測精度を得ることが可能である。しかしながら、上記Gshare方式では、最近の分岐命令の成立又は不成立が確定するのは分岐演算を実行した後であり、直前の分岐命令の結果が確定してから分岐予測を行った場合には、分岐ターゲットの予測確定までの時間が長くなる。このため、分岐予測が外れた場合に不要となる命令フェッチが多くなり、キャッシュ上の必要な情報が上書きされることにより、キャッシュミスが発生する確率が高くなるという欠点があった。【００１０】
上記課題に鑑み、開示された演算処理装置、情報処理装置及び演算処理方法は、命令フェッチ時に分岐予測を高精度で実行できることを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、開示された演算処理装置は、命令フェッチアドレスを確定し、命令フェッチを実行する実行手段と、命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す情報を保持する第１グローバル履歴レジスタ、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスをエントリとして保持する分岐履歴テーブル、前記命令フェッチアドレスに対応する命令が期待通りの分岐方向であるか否かを示す分岐成立確度をエントリとして保持するパターン履歴テーブル、及び前記命令フェッチアドレスをインデックスとして前記分岐履歴テーブルから検索される分類情報と、前記命令フェッチアドレス並びに前記第１グローバル履歴レジスタの情報をインデックスとして前記パターン履歴テーブルから検索される分岐成立確度とに基づいて、前記命令フェッチアドレスに対応する命令の分岐予測を行う予測部を備える分岐予測手段と、分岐演算完了時の分岐の成立又は不成立が確定した結果を時系列に示す情報を保持する第２グローバル履歴レジスタを備え、分岐演算の結果に基づいて前記予測部による分岐予測が失敗であると確定した場合に、前記第１グローバル履歴レジスタを前記第２グローバル履歴レジスタの情報で更新する更新手段とを備え、前記第１グローバル履歴レジスタの更新後に、前記実行手段は、前記命令フェッチを再実行する。【００１２】
上記目的を達成するため、開示された演算処理方法は、命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す情報を保持する第１グローバル履歴レジスタ、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスをエントリとして保持する分岐履歴テーブル、命令フェッチアドレスに対応する命令が期待通りの分岐方向であるか否かを示す分岐成立確度をエントリとして保持するパターン履歴テーブル、及び分岐演算完了時の分岐の成立又は不成立が確定した結果を時系列に示す情報を保持する第２グローバル履歴レジスタを備える演算処理装置の演算処理方法であって、前記命令フェッチアドレスを確定し、命令フェッチを実行する第１手順と、前記命令フェッチアドレスをインデックスとして前記分岐履歴テーブルから検索される分類情報と、前記命令フェッチアドレス並びに前記第１グローバル履歴レジスタの情報をインデックスとして前記パターン履歴テーブルから検索される分岐成立確度とに基づいて、前記命令フェッチアドレスに対応する命令の分岐予測を行う第２手順と、分岐演算の結果に基づいて前記第２手順による分岐予測が失敗であると確定した場合に、前記第１グローバル履歴レジスタを前記第２グローバル履歴レジスタの情報で更新する第３手順と、前記第１グローバル履歴レジスタの更新後に、前記命令フェッチを再実行する第４手順とを含む。【００１３】
上記目的を達成するため、開示された情報処理装置は、演算処理装置と、当該演算処理装置に接続されるメモリとを備える情報処理装置であって、前記メモリは、前記演算処理装置でフェッチされた命令フェッチアドレスに対応するデータを格納し、前記演算処理装置は、前記命令フェッチアドレスを確定し、命令フェッチを実行する実行手段と、命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す情報を保持する第１グローバル履歴レジスタ、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスをエントリとして保持する分岐履歴テーブル、前記命令フェッチアドレスに対応する命令が期待通りの分岐方向であるか否かを示す分岐成立確度をエントリとして保持するパターン履歴テーブル、及び前記命令フェッチアドレスをインデックスとして前記分岐履歴テーブルから検索される分類情報と、前記命令フェッチアドレス並びに前記第１グローバル履歴レジスタの情報をインデックスとして前記パターン履歴テーブルから検索される分岐成立確度とに基づいて、前記命令フェッチアドレスに対応する命令の分岐予測を行う予測部を備える分岐予測手段と、前記メモリから前記データを読み出し、分岐演算を実行する分岐演算手段と、分岐演算完了時の分岐の成立又は不成立が確定した結果を時系列に示す情報を保持する第２グローバル履歴レジスタを備え、前記演算手段による分岐演算の結果に基づいて前記予測部による分岐予測が失敗であると確定した場合に、前記第１グローバル履歴レジスタを前記第２グローバル履歴レジスタの情報で更新する更新手段とを備え、前記第１グローバル履歴レジスタの更新後に、前記実行手段は、前記命令フェッチを再実行する。
【発明の効果】
【００１４】
開示された演算処理装置、情報処理装置及び演算処理方法によれば、命令フェッチ時の分岐予測を高精度で実行できる。従って、分岐予測が外れ、無駄な命令フェッチによるキャッシュミスの発生を抑えることができ、プロセッサの性能を向上させることができる。
【図面の簡単な説明】
【００１５】
【図１】本実施の形態に係る情報処理装置の概略構成図である。
【図２】ＣＰＵ２Ａの概略構成図である。
【図３】分岐予測部１２の概略構成図である。
【図４】ＢＲＨＩＳ１０２のエントリのデータ構造の一例を示す図である。
【図５】ＰＨＴ１０３のエントリのデータ構造の一例を示す図である。
【図６】分岐予測部１２の動作を示すフローチャートである。
【図７】分岐履歴更新部２４の概略構成図である。
【図８】分岐履歴更新部２４の動作を示すフローチャートである。
【図９】２ビットのＢＰ（Branch Pattern）情報で表される分岐成立確度の遷移パターンを示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について、図面を参照して説明する。
【００１７】
図１は、本実施の形態に係る情報処理装置の概略構成図である。図１において、情報処理装置１は、例えば、情報処理装置としてのサーバであり、演算処理装置としてのＣＰＵ２Ａ，２Ｂ、記憶装置としてのメインメモリ３Ａ，３Ｂ、及びインターコネクト制御部４を備えている。ＣＰＵ２Ａ，２Ｂはそれぞれメインメモリ３Ａ，３Ｂに接続されており、メインメモリ３Ａ，３Ｂに格納された命令コードやデータなどを読み出す。インターコネクト制御部４は、ＣＰＵ２Ａ，２Ｂと外部装置５との間でデータの入出力制御を行う。尚、ＣＰＵやメインメモリの個数は２つに限定されるものではない。
【００１８】
図２は、ＣＰＵ２Ａの概略構成図である。ＣＰＵ２Ｂの構成は、ＣＰＵ２Ａの構成と同一であるので、その説明は省略する。
【００１９】
ＣＰＵ２Ａは、アウトオブオーダー実行（即ち、依存関係にない複数の命令を、プログラム中での出現順序に関係なく実行が可能な順序で実行すること）の機能及びパイプライン機能を有する汎用プロセッサである。ＣＰＵ２Ａは、例えば、命令フェッチステージ、命令発行ステージ、命令実行ステージ、命令完了ステージの計４つのステージでそれぞれ動作するハードウェアを備えている。具体的には、ＣＰＵ２Ａは、命令フェッチ制御部１１（実行手段）、分岐予測部１２（分岐予測手段）、一次命令キャッシュ１３、二次キャッシュ１４、メモリコントローラ１５、命令バッファ１６、命令デコーダ１７、命令発行制御部１８、及び一次オペランドキャッシュ（一次データキャッシュ）１９を備えている。さらに、ＣＰＵ２Ａは、演算器２０（分岐演算手段）、分岐制御部２１、レジスタ２２、命令完了制御部２３、及び分岐履歴更新部２４（更新手段）を備えている。
【００２０】
命令フェッチステージでは、命令フェッチ制御部１１、分岐予測部１２、一次命令キャッシュ１３、二次キャッシュ１４及び命令バッファ１６などが動作する。
【００２１】
命令フェッチ制御部１１は、分岐予測部１２からフェッチする命令の予測分岐先アドレス及び分岐制御部２１から分岐演算により確定した分岐先アドレスを受信する（図２のＤ１、Ｄ２）。命令フェッチ制御部１１は、予測分岐先アドレス及び確定した分岐先アドレスと、分岐しない場合においてフェッチ対象命令に連続する次命令アドレスなどから、次の命令フェッチアドレスを決定する。命令フェッチ制御部１１は、決定した命令フェッチアドレスを一次命令キャッシュ１３に出力し（図２のＤ３）、該当するアドレスから命令コードをフェッチする。命令フェッチ制御部１１は、一次命令キャッシュ１３に該当するアドレスの命令コードが存在しない場合（一次キャッシュミスが発生した場合）は二次キャッシュ１４から該当するアドレスの命令コードをフェッチする（図２のＤ４）。また、二次キャッシュ１４に該当するアドレスの命令コードが存在しない場合（二次キャッシュミスが発生した場合）はメインメモリ３Ａから該当するアドレスの命令コードをフェッチする（図２のＤ５）。尚、一次命令キャッシュ１３は二次キャッシュ１４の一部の命令コードを格納し、二次キャッシュ１４はメインメモリ３Ａの一部のデータや命令コードを格納している。本実施の形態では、メインメモリ３ＡはＣＰＵ２Ａの外部に配置しているため、メインメモリ３Ａとの入出力制御はメモリコントローラ１５を介して行われる。一次命令キャッシュ１３、二次キャッシュ１４又はメインメモリ３Ａの該当するアドレスからフェッチされた命令コードは、命令バッファ１６に格納される（図２のＤ６）。
【００２２】
分岐予測部１２は、命令フェッチと並行して分岐予測を実行する。分岐予測部１２は、命令フェッチ制御部１１から受け取った命令フェッチアドレスを基に分岐予測を行い、分岐の成立又は分岐の不成立を示す分岐方向と分岐先アドレスとを命令フェッチ制御部１１へ返す（図２のＤ１）。命令フェッチ制御部１１は、予測された分岐方向が成立であった場合に、次の命令フェッチアドレスとして予測された分岐先アドレスを選択する。
【００２３】
命令発行ステージでは、命令デコーダ１７、及び命令発行制御部１８が動作する。命令デコーダ１７は、命令バッファ１６から命令コードを受け取り（図２のＤ７）、命令の種別や必要な実行資源などを解析し、その解析結果を命令発行制御部１８に出力する（図２のＤ８）。
【００２４】
命令発行制御部１８は、アウトオブオーダー機能を実現するため、命令デコーダ１７で解釈された命令を一旦保持して、実行が可能な命令から実行資源に発行するリザベーションステーションの構造を持つ。このため、命令発行制御部１８は、命令が実行資源により実行可能となるまでその命令を保持しておくバッファの役割も担う。尚、ここでの実行資源は、一次オペランドキャッシュ１９、演算器２０、及び分岐制御部２１などである。命令発行制御部１８は、命令で参照するレジスタなどの依存性を参照し、依存性のあるレジスタの更新状況や同じ実行資源を用いる命令の実行状況などから実行資源が、保持された命令を実行可能であるかどうかを判断する。命令発行制御部１８は、保持された命令を実行資源が実行可能であると判断した場合には、レジスタ番号やオペランドアドレス等のような命令実行に必要な情報を実行資源に出力する（図２のＤ９）。
【００２５】
命令実行ステージでは、一次オペランドキャッシュ１９、演算器２０、及び分岐制御部２１などが動作する。演算器２０は、必要に応じてレジスタ２２や一次オペランドキャッシュ１９からデータを受け取り（図２のＤ１０）、四則演算、論理演算、三角関数演算、及びアドレス計算等のような命令に対応した演算を実行し、その演算結果をレジスタ２２や一次オペランドキャッシュ１９に出力する（図２のＤ１１）。演算器２０は、命令実行の完了通知を命令完了制御部２３へ出力する（図２のＤ１２）。
【００２６】
一次オペランドキャッシュ１９は、二次キャッシュ１４の一部のデータを格納している。また、一次オペランドキャッシュ１９は、命令発行制御部１８からのロード命令に従ってメインメモリ３Ａから演算器２０又はレジスタ２２へ送られるデータをロードしたり、命令発行制御部１８からのストア命令に従って演算器２０又はレジスタ２２からメインメモリ３Ａへ送られるデータをストアする（図２のＤ１３）。
【００２７】
分岐制御部２１は、命令デコーダ１７から分岐命令の種別情報を受け取り、演算器２０から分岐先アドレスや演算結果を受け取る（図２のＤ1４）。そして、分岐制御部２１は、演算器２０から受け取った演算結果が分岐条件を満たしているか否かを判断し、分岐方向を確定する。分岐制御部２１は、演算器２０から受け取った演算結果が分岐条件を満たしていれば分岐成立と判断し、当該演算結果が分岐条件を満たしていなければ分岐不成立と判断する。また、分岐制御部２１は、演算器２０から受け取った演算結果と分岐予測時の分岐アドレス及び分岐方向とが一致するかどうかの判断や、分岐命令同士の順序関係の制御を行う。演算器２０から受け取った演算結果に基づく分岐アドレス及び分岐方向と分岐予測時の分岐アドレス及び分岐方向とが一致する場合は、分岐制御部２１は、命令完了制御部２３へ分岐命令の完了通知を出力する（図２のＤ１５）。演算器２０から受け取った演算結果に基づく分岐アドレス及び分岐方向と分岐予測時の分岐アドレス及び分岐方向とが一致しない場合は、分岐予測が失敗しているので、分岐制御部２１は、命令完了制御部２３へ分岐命令の完了通知を出力する（図２のＤ１５）と共に、既にフェッチし投機実行を行った後続命令のキャンセル要求及び演算器２０から受け取った演算結果に基づく分岐アドレスへの再度の命令フェッチ要求を出力する（図２のＤ１６）。
【００２８】
命令完了ステージでは、レジスタ２２、命令完了制御部２３、及び分岐履歴更新部２４が動作する。命令完了制御部２３は、演算器２０及び分岐制御部２１から受け取った完了通知を基に、不図示のコミットスタックエントリに格納された命令コード順に命令完了処理を行い、レジスタ２２の更新指示を出力する（図２のＤ１７）。コミットスタックエントリは、命令完了制御部２３内に設けられ、命令ごとに１エントリが割り当てられ、実行中の命令の進捗状況の監視に用いられるバッファである。
【００２９】
レジスタ２２は、命令完了制御部２３からレジスタ更新指示を受け取ると、演算器２０や一次オペランドキャッシュ１９から受け取る演算結果のデータを基にレジスタ２２に保持したデータの更新を実行する。分岐履歴更新部２４は、分岐制御部２１から受け取る分岐演算の結果を基に、分岐予測部１２の履歴更新データを作成する。分岐履歴更新部２４は、作成した履歴更新データを分岐予測部１２に出力し（図２のＤ１８）、分岐予測部１２に含まれる後述する分岐履歴保持部の更新を実行する。
【００３０】
図３は、分岐予測部１２の概略構成図である。図３において、垂直方向の破線は、タイミングが異なる実行ステージを示す。また、図３では、一例として、命令フェッチ制御部１１から分岐予測部１２が受け取る命令フェッチアドレスＦＡＩＲ(Fetched Instruction AddRess)１００は、３２ビットで構成されている。図３において、命令フェッチアドレスＦＡＩＲ１００は、ＦＡＩＲ［31：0］と記載されており、［31：0］は第０〜第３１ビットの計３２ビットであることを示す。
【００３１】
分岐予測部１２は、命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す分岐成立情報保持部である第１ＧＨＲ（Global History Register）１０１と、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスなどを格納する分岐履歴保持部であるＢＲＨＩＳ（BRanch HIStory table）１０２と、第１ＧＨＲ１０１と命令フェッチアドレス１００との排他的論理和に対応する命令の分岐成立確度情報を格納する分岐確度情報保持部であるＰＨＴ(Patten History Table)１０３と、分岐予測回路部１０６（予測部）とを備えている。図３では、第１ＧＨＲ１０１は、６ビットで構成されている。
【００３２】
図４は、ＢＲＨＩＳ１０２の各エントリのデータ構造の一例を示す図である。
【００３３】
ＢＲＨＩＳ１０２の各エントリは、図４に示すように、分岐ターゲットアドレスＰＴＩＡＲ(Predicted Target Instruction AddRess)５１及び過去に分岐成立した分岐命令の分類情報５２を備えている。分類情報５２は、命令フェッチアドレスに対応する命令が過去に分岐成立したことを１で示すと共に分岐不成立だったことを０で示すＶＡＬＩＤフィールドと、命令フェッチアドレスに対応する命令が条件分岐であったことを１で示すと共に無条件分岐であったことを０で示すＰ−ＣＯＮＤ−ＢＩＴフィールドと、命令フェッチアドレスに対応する命令が分岐成立を期待する分岐命令であったことを１で示すと共に分岐不成立を期待する分岐命令であったことを０で示すＰ−ＥＸＰＥＣＴ−ＢＩＴフィールドとを含む。ＶＡＬＩＤ、Ｐ−ＣＯＮＤ−ＢＩＴ及びＰ−ＥＸＰＥＣＴ−ＢＩＴの各フィールドは、例えば、０又は１の１ビットを有する。
【００３４】
図３に戻り、ＢＲＨＩＳ１０２は、命令フェッチと並行して、命令フェッチアドレスＦＩＡＲ１００により検索され、該当するエントリの情報（即ち、分岐ターゲットアドレスＰＴＩＡＲ、ＶＡＬＩＤ、Ｐ−ＣＯＮＤ−ＢＩＴ及びＰ−ＥＸＰＥＣＴ−ＢＩＴ）を図３のレジスタ１０４に出力する。レジスタ１０４は、ＢＲＨＩＳ１０２のマッチしたエントリの情報を分岐予測回路部１０６に出力する。
【００３５】
ＰＨＴ１０３に格納される分岐成立確度を示す指標として、Agree-predictionという方式が知られている。このAgree-prediction方式は、分岐成立確度を期待通りの分岐方向であるかどうかで示すものである。分岐成立を期待する命令の一例として、コンパイラなどによって、予め、分岐成立の確度が高いと判定された分岐命令に、分岐成立を期待する情報を付加することが考えられる。
【００３６】
本実施の形態では、期待通りの分岐方向であるか否かを示す分岐成立確度は、「００」、「０１」、「１０」及び「１１」のいずれかの値をとる２ビットのＢＰ（Branch Pattern）情報として表される。ＰＨＴ１０３は、図５に示すように、２ビットのＢＰ［1：0］で表される分岐成立確度７２をエントリとして保持する。分岐予測時、ＰＨＴ１０３は、命令フェッチと並行して、命令フェッチアドレスＦＩＡＲ［5：0］及び第１ＧＨＲ［5：0］の排他的論理和と、命令フェッチアドレスＦＩＡＲ［31：6］とを連結した連結アドレスをインデックスとして検索され、該当するエントリのＢＰ［1：0］（即ち、分岐成立確度７２）をレジスタ１０５に出力する。レジスタ１０５は、ＰＨＴ１０３のマッチしたエントリのＢＰ［1：0］を分岐予測回路部１０６に出力する。ここで、命令フェッチアドレスＦＩＡＲ［5：0］及び第１ＧＨＲ［5：0］の排他的論理和を採る理由は、ＰＨＴ１０３のサイズが有限であり、履歴の利用効率を上げるためである。例えば、命令フェッチアドレス＝１１１１１１且つ第１ＧＨＲ＝００００００（共に２進数表記）の分岐と、命令フェッチアドレス＝１１１１１０且つ第１ＧＨＲ＝０００００１の分岐とは、共に排他的論理和は「１１１１１１」であるので、ＰＨＴ１０３のエントリをシェアして使うことができる。
【００３７】
図９は、２ビットのＢＰ情報で表される分岐成立確度ＢＰ［1：0］の遷移パターンを示す図である。ＰＨＴ１０３からのＢＰ［1：0］の値が「１０」未満の「００」又は「０１」である場合は、分岐の成立又は不成立が期待通りである可能性があることを示す。特に、ＢＰ［1：0］の値が「００」である場合は、分岐の成立又は不成立が期待通りである可能性が高い状態であることを示し、ＢＰ［1：0］の値が「０１」である場合は、分岐の成立又は不成立が期待通りである可能性が低い状態であることを示す。一方、ＰＨＴ１０３からのＢＰ［1：0］の値が「１０」以上の「１０」又は「１１」である場合は、分岐の成立又は不成立が期待通りでない可能性があることを示す。特に、ＢＰ［1：0］の値が「１１」である場合は、分岐の成立又は不成立が期待通りでない可能性が高い状態であることを示し、ＢＰ［1：0］の値が「１０」である場合は、分岐の成立又は不成立が期待通りでない可能性が低い状態であることを示す。
【００３８】
ＰＨＴ１０３のエントリに含まれる２ビットのＢＰ［1：0］は、後述するように、条件分岐の分岐演算が完了する度に更新される。分岐演算で期待通りの結果が確定した場合には、ＢＰ［1：0］の値が１だけ減算されて、対応するエントリが更新される。分岐演算で期待通りの結果が確定し且つＢＰ［1：0］の値が「００」である場合は、これ以上の減算ができないので、対応するエントリは更新されない。一方、分岐演算で期待と異なる結果が確定した場合には、ＢＰ［1：0］の値が１だけ加算されて、対応するエントリが更新される。分岐演算で期待と異なる結果が確定し且つＢＰ［1：0］の値が「１１」である場合は、これ以上の加算ができないので、対応するエントリは更新されない。
【００３９】
図３に戻り、分岐予測回路部１０６は、比較回路１０７、バッファ１０８、論理積回路（ＡＮＤ）１０９〜１１２、論理和回路（ＯＲ）１１３，１１４を備えている。比較回路１０７は、入力したＢＰ［1：0］が「１０」未満の「００」又は「０１」である場合に、論理積回路１１１及び１１２に「０」を出力し、入力したＢＰ［1：0］が「１０」以上の「１０」又は「１１」である場合に、論理積回路１１１及び１１２に「１」を出力する。
【００４０】
バッファ１０８は、レジスタ１０４からＶＡＬＩＤを入力し、ＶＡＬＩＤ＝０であれば「０」を、ＶＡＬＩＤ＝１であれば「１」をＢＲＨＩＳ−ＨＩＴとして出力する。ＢＲＨＩＳ−ＨＩＴは、フェッチした命令が分岐命令であることを示す。つまり、ＶＡＬＩＤはＢＲＨＩＳ−ＨＩＴと同一の値をとり、ＶＡＬＩＤ＝０である場合は、フェッチした命令が分岐命令でないことを示し、分岐予測回路部１０６は、分岐不成立と予測する。即ち、論理和回路１１３から出力される、分岐成立と予測したことを「１」で示すＰＲＥＤＩＣＴ−ＴＡＫＥＮ（１ビット）が「０」になる。ＶＡＬＩＤ＝１である場合は、フェッチした命令が分岐命令であることを示す。
【００４１】
論理積回路１０９は、ＢＲＨＩＳ−ＨＩＴ＝１且つＰ−ＣＯＮＤ−ＢＩＴ＝１である場合に、第１ＧＨＲ１０１に更新指示を出力する。このとき、第１ＧＨＲ１０１は、論理和回路１１４の出力値に応じて更新される。尚、ＢＲＨＩＳ−ＨＩＴ＝１且つＰ−ＣＯＮＤ−ＢＩＴ＝１である場合は、フェッチした命令が条件分岐であることを示す。論理積回路１１０は、ＢＲＨＩＳ−ＨＩＴ＝１且つＰ−ＣＯＮＤ−ＢＩＴ＝０である場合に、論理和回路１１３に「１」を出力し、それ以外の場合に、論理和回路１１３に「０」を出力する。尚、ＢＲＨＩＳ−ＨＩＴ＝１且つＰ−ＣＯＮＤ−ＢＩＴ＝０である場合は、フェッチした命令が無条件分岐であることを示す。
【００４２】
論理積回路１１１は、ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］＝「００」又は「０１」である場合に、論理和回路１１３及び１１４に「１」を出力し、それ以外の場合に、論理和回路１１３及び１１４に「０」を出力する。尚、ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］＝「００」又は「０１」である場合は、フェッチした命令が条件分岐であり、且つ命令の期待通り分岐成立であることを示す。ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］＝「００」又は「０１」である場合は、フェッチした命令が条件分岐であり、且つ命令の期待通り分岐不成立であることを示す。
【００４３】
論理積回路１１２は、ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］＝「１０」又は「１１」である場合に、論理和回路１１３及び１１４に「１」を出力し、それ以外の場合に、論理和回路１１３及び１１４に「０」を出力する。尚、ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］＝「１０」又は「１１」である場合は、フェッチした命令が条件分岐であり、且つ命令の期待と異なる分岐成立であることを示す。ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］＝「１０」又は「１１」である場合は、フェッチした命令が条件分岐であり、且つ命令の期待と異なる分岐不成立であることを示す。
【００４４】
論理和回路１１３は、論理積回路１１０〜１１２の出力のいずれかが「１」である場合には、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして「１」を出力する。即ち、論理積回路１１０〜１１２の出力のいずれかが「１」である場合には、論理和回路１１３は、分岐成立と予想する。また、論理和回路１１３は、論理積回路１１０〜１１２の出力の全てが「０」である場合には、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして「０」を出力する。即ち、論理積回路１１０〜１１２の出力の全てが「０」である場合には、論理和回路１１３は、分岐不成立と予想する。
【００４５】
論理和回路１１４は、論理積回路１１１及び１１２の出力のいずれかが「１」である場合には、第１ＧＨＲ１０１に「１」を出力する。この場合、第１ＧＨＲ１０１の更新値が「１」になる。論理和回路１１４は、論理積回路１１１及び１１２の出力の全てが「０」である場合には、第１ＧＨＲ１０１に「０」を出力する。この場合、第１ＧＨＲ１０１の更新値が「０」になる。
【００４６】
分岐予測部１２は、分岐成立を示すＰＲＥＤＩＣＴ−ＴＡＫＥＮ信号と、レジスタ１０４に保持された分岐ターゲットアドレスＰＴＩＡＲ[31:0]を命令フェッチ制御部１１に出力する。選択回路１１６は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ＝１である場合に、分岐予測部１１から出力された分岐ターゲットアドレスＰＴＩＡＲ［31:0］を次の命令フェッチアドレス（ＮＥＸＴ−ＦＩＡＲ［31:0］）として選択する。一方、選択回路１１６は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ＝０である場合に、次の命令フェッチアドレスとして命令フェッチアドレスＦＩＡＲ［31:0］と連続したアドレスを選択する。ここで、命令フェッチアドレスＦＩＡＲ［31:0］と連続したアドレスとは、アドレス加算回路１１５により命令フェッチアドレスＦＩＡＲ[31:0]を加算したアドレスである。例えば、一度にフェッチするデータの単位が３２バイトである場合、アドレス加算回路１１５は、命令フェッチアドレスＦＩＡＲ［31:0］に３２バイトを加える。
【００４７】
第１ＧＨＲ１０１は、分岐成立を１、分岐不成立を０の１ビットで表した分岐予測結果を時系列に６回分記憶したものであり、分岐予測結果に基づいて条件分岐命令がフェッチされたと予測したときのみ更新される。具体的には、ＢＲＨＩＳ−ＨＩＴ＝０又はＰ−ＣＯＮＤ−ＢＩＴ＝０である場合は条件分岐でないことを示すので、第１ＧＨＲ１０１は更新されない。ＢＲＨＩＳ−ＨＩＴ＝１且つＰ−ＣＯＮＤ−ＢＩＴ＝１である場合は条件分岐命令がフェッチされたことを示すので、第１ＧＨＲ１０１は更新される。ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、且つＰＲＥＤＩＣＴ−ＴＡＫＥＮ＝０である場合は、第１ＧＨＲ１０１の最古の情報が削除され、第１ＧＨＲ１０１に０のエントリが追加される。ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、且つＰＲＥＤＩＣＴ−ＴＡＫＥＮ＝１である場合は、フェッチした条件分岐命令が成立すると予測されていることを表すので、第１ＧＨＲ１０１の最古の情報が削除され、第１ＧＨＲ１０１に１のエントリが追加される。例えば、更新前の第１ＧＨＲ１０１が「ａｂｃｄｅｆ」であるとする。ここで、ａ〜ｆは、０又は１の値を取り得る１ビットの変数を示し、一番右のビット「ｆ」が最古の情報で、左方向に、順番に新しい情報が並んでいるものとする。この前提で、ＢＲＨＩＳ−ＨＩＴ＝０又はＰ−ＣＯＮＤ−ＢＩＴ＝０である場合は、フェッチした条件分岐命令が成立しないと予測されていることを表すので、第１ＧＨＲ１０１は「ａｂｃｄｅｆ」を維持する。ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、且つＰＲＥＤＩＣＴ−ＴＡＫＥＮ＝０である場合は、第１ＧＨＲ１０１は「０ａｂｃｄｅ」に更新される。ＢＲＨＩＳ−ＨＩＴ＝１、Ｐ−ＣＯＮＤ−ＢＩＴ＝１、且つＰＲＥＤＩＣＴ−ＴＡＫＥＮ＝１である場合は、第１ＧＨＲ１０１は「１ａｂｃｄｅ」に更新される。
【００４８】
図６は、分岐予測部１２の動作を示すフローチャートである。ここでは、上述したように、更新前の第１ＧＨＲ１０１が「ａｂｃｄｅｆ」であるとする。
【００４９】
まず、分岐予測部１２は、ＢＲＨＩＳ−ＨＩＴが１であるか否かを判別する（ステップＳ１１）。ステップＳ１１でＢＲＨＩＳ−ＨＩＴが０である場合には（ＮＯ）、フェッチした命令が分岐命令でないと予測し（ステップＳ１２）、即ち、分岐予測部１２の結果として、分岐不成立と予測する（ステップＳ１３）。ステップＳ１２とステップＳ１３のは図３において、論理積回路１０９〜１１２の出力が全て０となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして０を出力する。分岐不成立と予測された場合、命令フェッチ制御部１１では、選択回路１１６で、次の命令フェッチアドレスとして命令フェッチアドレスＦＩＡＲ［31:0］と連続する次命令アドレスを選択する（ステップＳ１４）。
【００５０】
ステップＳ１１でＢＲＨＩＳ−ＨＩＴが１である場合には（ＹＥＳ）、Ｐ−ＣＯＮＤ−ＢＩＴが１であるか否かを判別する（ステップＳ１５）。ステップＳ１５でＰ−ＣＯＮＤ−ＢＩＴが０である場合には（ＮＯ）、フェッチした命令が無条件分岐命令であると予測し（ステップＳ１６）、即ち、分岐予測部１２の結果として分岐成立と予測する（ステップＳ１７）。ステップＳ１６とステップＳ１７は図３において、論理積回路１１０の出力が１となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして１を出力する。分岐不成立と予測された場合、命令フェッチ制御部１１では、選択回路１１６において、次の命令フェッチアドレスとして分岐ターゲットアドレスＰＴＩＡＲ［31:0］を選択する（ステップＳ１８）。
【００５１】
ステップＳ１５でＰ−ＣＯＮＤ−ＢＩＴが１である場合には（ＹＥＳ）、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］≧２（ＢＰ［1：0］＝「１０」又は「１１」）であるか又はＰ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］＜２（ＢＰ［1：0］＝「１０」又は「１１」）であるか否かを判別する（ステップＳ１９）。ステップＳ１９でＰ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］≧２である場合には、分岐予測部１２の結果として分岐不成立と予測し（ステップＳ２０）、第１ＧＨＲ１０１は「０ａｂｃｄｅ」に更新される（ステップＳ２１）。その後、上記ステップＳ１４が実行される。ステップＳ２０及びステップＳ２１は図３において論理積回路１０９の出力が１、論理積回路１１０〜１１２の出力が全て０となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして０を出力し、論理和回路１１４は、第１ＧＨＲ１０１の更新値として０を出力する。
【００５２】
ステップＳ１９でＰ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］＜２である場合には、分岐予測部１２の結果として分岐成立と予測し（ステップＳ２２）、第１ＧＨＲ１０１は「１ａｂｃｄｅ」に更新される（ステップＳ２３）。その後、上記ステップＳ１８の工程が実行される。ステップＳ２２及びステップＳ２３は図３において論理積回路１０９の出力が１、論理積回路１１１の出力が１となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして１を出力し、論理和回路１１４は、第１ＧＨＲ１０１の更新値として１を出力する。
【００５３】
さらに、ステップＳ１５でＰ−ＣＯＮＤ−ＢＩＴが１である場合には（ＹＥＳ）、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］≧２（ＢＰ［1：0］＝「１０」又は「１１」）であるか又はＰ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］＜２（ＢＰ［1：0］＝「１０」又は「１１」）であるか否かを判別する（ステップＳ２４）。ステップＳ２４でＰ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］≧２（ＢＰ［1：0］＝「１０」又は「１１」）である場合には、分岐予測部１２の結果として分岐成立と予測し（ステップＳ２５）、第１ＧＨＲ１０１は「１ａｂｃｄｅ」に更新される（ステップＳ２６）。その後、上記ステップＳ１８の工程が実行される。ステップＳ２５及びステップＳ２６は図３において論理積回路１０９の出力が１、論理積回路１１２の出力が１となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして１を出力、論理和回路１１４は、第１ＧＨＲ１０１の更新値として１を出力する。
【００５４】
ステップＳ２４でＰ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］＜２（ＢＰ［1：0］＝「１０」又は「１１」）である場合には、分岐予測部１２の結果として分岐不成立と予測し（ステップＳ２７）、第１ＧＨＲ１０１は「０ａｂｃｄｅ」に更新される（ステップＳ２８）。その後、上記ステップＳ１４の工程が実行される。ステップＳ２７及びステップＳ２８は図３において論理積回路１０９の出力が１、論理積回路１１０〜１１２の出力が全て０となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして０を出力、論理和回路１１４は、第１ＧＨＲ１０１の更新値として０を出力する。
【００５５】
以上のように、分岐予測部１２は、命令フェッチ時に、分岐履歴だけでなく、第１ＧＨＲ１０１及び命令フェッチアドレスに基づいて決定される分岐成立確度を使って、分岐予測を行う。
【００５６】
図７は、分岐履歴更新部２４の概略構成図である。図７において、垂直方向の破線は、タイミングが異なる実行ステージを示す。
【００５７】
分岐履歴更新部２４は、分岐演算の結果を基にして、ＢＲＨＩＳ１０２、ＰＨＴ１０３、第１ＧＨＲ１０１、及び後述する第２ＧＨＲ２０２の更新を行う。分岐履歴更新部２４は、分岐演算の結果として、図１の分岐制御部２１から、演算の結果確定した命令の分岐ターゲットアドレスＲＴＩＡＲ［31：0］と、分岐命令アドレスＢＩＡＲ［31：0］(Branch Instruction AddRess)とを受信する。分岐ターゲットアドレスＲＴＩＡＲ［31：0］及び分岐命令アドレスＢＩＡＲ［31：0］は、共に３２ビットで構成されている。[31:0]は第０〜第３１ビットの計３２ビットであることを示す。
【００５８】
分岐履歴更新部２４は、レジスタ２０１を備えている。レジスタ２０１は、分岐制御部２１から、ＣＯＭＰＬＥＴＥ、ＲＥＳＵＬＴ−ＴＡＫＥＮ、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ、Ｄ−ＣＯＮＤ−ＢＩＴ、Ｄ−ＥＸＰＥＣＴ−ＢＩＴの計５ビットの情報を受け取る。ＣＯＭＰＬＥＴＥは、分岐演算が完了したことを「１」で、分岐演算が完了していないことを「０」で示す。ＲＥＳＵＬＴ−ＴＡＫＥＮは、分岐成立が確定したことを「１」で、分岐不成立が確定したことを「０」で示す。ＰＲＥＤＩＣＴ−ＴＡＫＥＮは、命令フェッチ時に分岐成立と予測したことを「１」で、分岐不成立と予測したことを「０」で示す。Ｄ−ＣＯＮＤ−ＢＩＴは、命令をデコードした結果、命令が条件分岐命令であることを「１」で、命令が条件分岐命令でないことを「０」で示す。Ｄ−ＥＸＰＥＣＴ−ＢＩＴは、命令をデコードした結果、命令が分岐成立を期待することを「１」で、命令が分岐不成立を期待することを「０」で示す。
【００５９】
分岐履歴更新部２４は、さらに、第２ＧＨＲ２０２、判別回路２０３、論理積回路２０４，２０６，２０７、比較回路２０５，２０８、レジスタ２０９〜２１５、加算器２１６、減算器２１７及び選択回路２１８を備えている。加算器２１６、減算器２１７及び選択回路２１８は演算手段として機能する。
【００６０】
第２ＧＨＲ２０２は、分岐成立を１、分岐不成立を０の１ビットで表した分岐演算結果を時系列に６ビット記憶したものである。第２ＧＨＲ２０２は、一度に命令フェッチした命令列の固まり（例えば命令フェッチの単位を３２Ｂｙｔｅ，１命令を３２ビットで表した場合は8命令分）を単位として、条件分岐命令の分岐演算が完了したときに更新される。即ち、分岐演算自体は１命令毎に行われるが、例えば、命令フェッチの中に２つ以上の分岐命令が入っている場合には、２つ以上の分岐命令を１単位として、第２ＧＨＲ２０２は更新される。従って、図７の論理積回路２０４の出力、ＲＥＳＵＬＴ−ＴＡＫＥＮ、及び論理積回路２１１の出力は、命令フェッチに含まれる分岐命令の数だけそれぞれレジスタ２０９〜２１１に一時保存され、条件分岐命令の分岐演算が完了したときに一括で出力される。第２ＧＨＲ２０２を命令フェッチの単位ごとに更新することは、第１ＧＨＲ１０１と同等の履歴を作成する上で必要である。
【００６１】
判別回路２０３は、分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでいるか否か、即ち直前に実行した分岐命令の命令アドレスとの差分が３２Ｂｙｔｅを超えているかを判別する。分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでいる場合には、判別回路２０３は、論理積回路２０４に１を出力する。分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでいない場合には、判別回路２０３は、論理積回路２０４に０を出力する。
【００６２】
論理積回路２０４は、ＣＯＭＰＬＥＴＥ＝１且つＤ−ＣＯＮＤ−ＢＩＴ＝１である場合には、レジスタ２０９を介して第２ＧＨＲ２０２に更新指示を出力する。例えば、分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでおり、ＣＯＭＰＬＥＴＥ＝１、Ｄ−ＣＯＮＤ−ＢＩＴ＝１、且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝０である場合には、第２ＧＨＲ２０２の最古の情報が削除され、第２ＧＨＲ２０２に０のエントリが追加される。分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでおり、ＣＯＭＰＬＥＴＥ＝１、Ｄ−ＣＯＮＤ−ＢＩＴ＝１、且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝１である場合には、第２ＧＨＲ２０２の最古の情報が削除され、第２ＧＨＲ２０２に１のエントリが追加される。分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨がず、ＣＯＭＰＬＥＴＥ＝１、且つＤ−ＣＯＮＤ−ＢＩＴ＝１である場合には、第２ＧＨＲ２０２は、第２ＧＨＲ２０２の最新の情報とＲＥＳＵＬＴ−ＴＡＫＥＮとの論理和に更新される。
【００６３】
例えば、更新前の第２ＧＨＲ２０２が「ａｂｃｄｅｆ」であるとする。ここで、ａ〜ｆは、０又は１の値を取り得る１ビットの変数を示し、一番右のビット「ｆ」が最古の情報で、左方向に、順番に新しい情報が並んでいるものとする。この前提で、分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでおり、ＣＯＭＰＬＥＴＥ＝１、Ｄ−ＣＯＮＤ−ＢＩＴ＝１、且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝０である場合には、第２ＧＨＲ２０２は「０ａｂｃｄｅ」に更新される。分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでおり、ＣＯＭＰＬＥＴＥ＝１、Ｄ−ＣＯＮＤ−ＢＩＴ＝１、且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝１である場合には、第２ＧＨＲ２０２は「１ａｂｃｄｅ」に更新される。分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨がず、ＣＯＭＰＬＥＴＥ＝１、Ｄ−ＣＯＮＤ−ＢＩＴ＝１、且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝１である場合には、第２ＧＨＲ２０２は「１ｂｃｄｅｆ」に更新される。分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨がず、ＣＯＭＰＬＥＴＥ＝１、Ｄ−ＣＯＮＤ−ＢＩＴ＝１、且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝０である場合には、第２ＧＨＲ２０２は「ａｂｃｄｅｆ」を維持する。
【００６４】
比較回路２０５は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮがＲＥＳＵＬＴ−ＴＡＫＥＮと不一致であるか否かを判別する。ＰＲＥＤＩＣＴ−ＴＡＫＥＮがＲＥＳＵＬＴ−ＴＡＫＥＮと不一致である場合は、比較回路２０５は、論理積回路２０６に１を出力する。一方、ＰＲＥＤＩＣＴ−ＴＡＫＥＮがＲＥＳＵＬＴ−ＴＡＫＥＮと一致する場合は、比較回路２０５は、論理積回路２０６に０を出力する。論理積回路２０６は、ＣＯＭＰＬＥＴＥ＝１且つ比較回路２０５の出力＝１（即ち、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ≠ＲＥＳＵＬＴ−ＴＡＫＥＮ）である場合に、分岐予測が失敗したとして、第１ＧＨＲ１０１及びＢＲＨＩＳ１０２の更新指示をレジスタ２１１を介して第１ＧＨＲ１０１及びＢＲＨＩＳ１０２に出力する。第１ＧＨＲ１０１及びＢＲＨＩＳ１０２の更新については後述する。
【００６５】
論理積回路２０７は、ＣＯＭＰＬＥＴＥ＝１且つＤ−ＣＯＮＤ−ＢＩＴ＝１である場合に、レジスタ２１４を介してＰＨＴ１０３に更新指示を出力する。比較回路２０８は、Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと不一致であるか否かを判別する。Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと不一致である場合は、比較回路２０８は、レジスタ２１５を介して加算器２１６の選択を示す「１」を選択回路２１８に出力する。尚、Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと不一致である場合は、分岐の演算結果が期待通りでなかったことを示す。Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと一致する場合は、比較回路２０８は、バッファ２１５を介して減算器２１７の選択を示す「０」を選択回路２１８に出力する。尚、Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと一致する場合は、分岐の演算結果が期待通りであることを示す。
【００６６】
ＰＨＴ１０３の更新は、条件分岐の分岐演算が完了するたびに実行される。ＰＨＴ１０３の更新アドレス［31：0］は、演算が完了した分岐命令のアドレスＢＩＡＲ［31：6］とアドレスＢＩＡＲ［5：0］及び第２ＧＨＲ２０２（［5：0））の排他的論理和との連結したものである。ここで、更新するエントリは、後で同じ命令に関する分岐予測をする時にＰＨＴ１０３を検索するために利用されるので、必要となるのはフェッチした命令より前の演算結果である。そのため、更新アドレスには、対象となる命令自体の演算結果は反映しない、即ち、対象となる分岐命令の演算結果によって更新される前の第２ＧＨＲ２０２が用いられる。
【００６７】
ここで、更新時のＰＨＴ１０３の出力（即ち、分岐成立確度）は、分岐予測時と異なるインデックスによる出力であることを示すため、ＢＰ２［1：0］として定義する。ＰＨＴ１０３の更新では、一度ＰＨＴ１０３から更新アドレスに対応するエントリのＢＰ２［1：0］が読み出され、分岐の演算結果が期待通りである場合（ＲＥＳＵＬＴ−ＴＡＫＥＮ＝Ｄ−ＥＸＰＥＣＴ−ＢＩＴである場合）には、ＢＰ２［1：0］が減算器２１７によって１だけ減算される。一方、分岐の演算結果が期待通りでない場合ＲＥＳＵＬＴ−ＴＡＫＥＮ≠Ｄ−ＥＸＰＥＣＴ−ＢＩＴである場合）には、ＢＰ２［1：0］が加算器２１６によって１だけ加算される。加算又は減算されたＢＰ２［1：0］は、選択回路２１８を介して更新データＢＰ２’［1：0］として、読み出した時の更新アドレスと同一の更新アドレスに対応するエントリへ書き込まれる。より具体的には、ＣＯＭＰＬＥＴＥ＝１、Ｄ−ＣＯＮＤ−ＢＩＴ＝１、且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝Ｄ−ＥＸＰＥＣＴ−ＢＩＴである場合には、ＰＨＴ１０３の更新対象のエントリのＢＰ２’［1：0］は、減算器２１７及び選択回路２１８を介して、ＢＰ２’＝ＢＰ２［1：0］−１として更新される。このとき、ＢＰ２［1：0］＝００である場合には、さらなる減算ができないので、ＢＰ２’［1：0］の値は更新されない。ＣＯＭＰＬＥＴＥ＝１、Ｄ−ＣＯＮＤ−ＢＩＴ＝１、且つＲＥＳＵＬＴ−ＴＡＫＥＮ≠Ｄ−ＥＸＰＥＣＴ−ＢＩＴである場合には、ＰＨＴ１０３の更新対象のエントリのＢＰ２’［1：0］は、加算器２１６及び選択回路２１８を介して、ＢＰ２’＝ＢＰ２［1：0］＋１として更新される。このとき、ＢＰ２［1：0］＝１１である場合には、さらなる加算ができないので、ＢＰ２’［1：0］の値は更新されない。このように、加算器２１６、減算器２１７及び選択回路２１８は、分岐の演算結果に応じて、ＰＨＴ１０３のエントリに含まれる分岐成立確度を更新することができる。
【００６８】
次に、第１ＧＨＲ１０１及びＢＲＨＩＳ１０２の更新について説明する。
【００６９】
論理積回路２０６において、ＣＯＭＰＬＥＴＥ＝１且つＲＥＳＵＬＴ−ＴＡＫＥＮ≠ＰＲＥＤＩＣＴ−ＴＡＫＥＮである場合、これは分岐予測が失敗したことを示す。分岐予測が失敗した場合、既にフェッチし投機実行を行った後続命令の処理は全てキャンセルされ、正しい分岐演算の結果に基づき予測失敗した命令の次の命令のフェッチから処理はやり直される。このとき、第１ＧＨＲ１０１及びＢＲＨＩＳ１０２は、正しい分岐演算の結果に基づいて更新される。
【００７０】
具体的には、ＢＲＨＩＳ１０２の更新アドレスは、分岐予測が失敗した命令のアドレスＢＩＡＲ［31：0］である。分岐予測が失敗した場合には、ＢＲＨＩＳ１０２の更新対象のエントリに、分岐命令の確定情報であるＲＴＩＡＲ［31：0］、Ｄ−ＣＯＮＤ−ＢＩＴ、及びＤ−ＥＸＰＥＣＴ−ＢＩＴがそれぞれＰＴＩＡＲ［31：0］、Ｐ−ＣＯＮＤ−ＢＩＴ、Ｐ−ＥＸＰＥＣＴ−ＢＩＴとして登録される。さらに、ＢＲＨＩＳ１０２の更新対象のエントリのＶＡＬＩＤは１にセットされる。
【００７１】
分岐予測が失敗した場合、第１ＧＨＲ１０１には、分岐予測が失敗した分岐命令の演算結果を反映した第２ＧＨＲ２０２の値がセットされる。これにより、第１ＧＨＲ１０１には分岐演算が確定した値が反映されることとなり、この値を基に以後の分岐予測が実行される。
【００７２】
このように、再度の命令フェッチ時には、第１ＧＨＲ１０１及びＢＲＨＩＳ１０２が分岐確定後の値に更新されるため、常に分岐確定時とのズレがない状態で分岐予測が可能となる。
【００７３】
図８は、分岐履歴更新部２４の動作を示すフローチャートである。ここでは、上述したように、更新前の第２ＧＨＲ１０１が「ａｂｃｄｅｆ」であるとする。
【００７４】
まず、分岐履歴更新部２４は、ＣＯＭＰＬＥＴＥ＝１であるか、即ち、分岐演算が完了しているか否かを判別する（ステップＳ３１）。ステップＳ３１で分岐演算が完了していない場合には（ＮＯ）、第１ＧＨＲ１０１、ＢＲＨＩＳ１０２、ＰＨＴ１０３及び第２ＧＨＲ２０２は更新されない（ステップＳ３２）。ステップＳ３１とステップＳ３２は図７において論理積回路２０４，２０６，２０７の出力が全て０となることで実現される。
【００７５】
次に、ステップＳ３１で分岐演算が完了してる場合には（ＹＥＳ）、Ｄ−ＣＯＮＤ−ＢＩＴ＝１であるか、即ち、命令が条件分岐であるかを判別する（ステップＳ３３）。
【００７６】
ステップＳ３３で命令が条件分岐でない場合には（ＮＯ）、ＰＨＴ１０３及び第２ＧＨＲ２０２は更新されない（ステップＳ３４）。次に、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ≠ＲＥＳＵＬＴ−ＴＡＫＥＮであるか、即ち、確定した分岐の成立又は不成立の結果が予測と異なるか否かを判別する（ステップＳ３５）。ステップＳ３５で確定した分岐の成立又は不成立の結果が予測と異なる場合には（ＹＥＳ）、第１ＧＨＲ１０１は、更新前の第２ＧＨＲ２０２の値「ａｂｃｄｅｆ」で更新される（ステップＳ３６）。その後、ＢＲＨＩＳ１０２の更新対象のエントリが更新され（ステップＳ３７）、再度の命令フェッチが実行される（ステップＳ３８）。ステップＳ３７とステップＳ３８は図７において論理積回路２０４、２０７の出力が共に０、比較回路２０５の出力が１となって論理積回路２０６の出力が１となることで実現される。一方、ステップＳ３５で確定した分岐の成立又は不成立の結果が予測と一致する場合には（ＮＯ）、第１ＧＨＲ１０１及びＢＲＨＩＳ１０２は更新されない（ステップＳ３９）。ステップＳ３９は図７において論理積回路２０４、２０７の出力が共に０、比較回路２０５の出力が０となることで実現される。
【００７７】
上記ステップ３３で命令が条件分岐である場合には（ＹＥＳ）、ＲＥＳＵＬＴ−ＴＡＫＥＮ≠Ｄ−ＥＸＰＥＣＴ−ＢＩＴであるか、即ち、確定した分岐の成立又は不成立の結果が、デコードされた命令の分岐成立又は不成立の期待値と不一致であるか否かを判別する（ステップＳ４０）。ステップＳ４０は図７において比較回路２０８がＲＥＳＵＬＴ−ＴＡＫＥＮの値（０又は１）及びＤ−ＥＸＰＥＣＴ−ＢＩＴの値（０又は１）の組み合わせを判別することで実現する。
【００７８】
ステップＳ４０でＲＥＳＵＬＴ−ＴＡＫＥＮ≠Ｄ−ＥＸＰＥＣＴ−ＢＩＴでない場合（即ち、ＲＥＳＵＬＴ−ＴＡＫＥＮ＝１且つＤ−ＥＸＰＥＣＴ−ＢＩＴ＝１、又はＲＥＳＵＬＴ−ＴＡＫＥＮ＝０且つＤ−ＥＸＰＥＣＴ−ＢＩＴ＝０）、ＰＨＴ１０３の更新対象のエントリのＢＰ２’［1：0］は、ＢＰ２’＝ＢＰ２［1：0］−１として更新される（ステップＳ４１及びＳ４４）。一方、ステップＳ４０でＲＥＳＵＬＴ−ＴＡＫＥＮ≠Ｄ−ＥＸＰＥＣＴ−ＢＩＴである場合（即ち、ＲＥＳＵＬＴ−ＴＡＫＥＮ＝１且つＤ−ＥＸＰＥＣＴ−ＢＩＴ＝０、又はＲＥＳＵＬＴ−ＴＡＫＥＮ＝０且つＤ−ＥＸＰＥＣＴ−ＢＩＴ＝１）、ＰＨＴ１０３の更新対象のエントリのＢＰ２’［1：0］は、ＢＰ２’＝ＢＰ２［1：0］＋１として更新される（ステップＳ４２及びＳ４３）。
【００７９】
次に、分岐履歴更新部２４は、分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでいるか否かを判別する（ステップＳ４５及びＳ４６）。
【００８０】
ステップＳ４５で分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでおり（ＹＥＳ）且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝１である場合には、第２ＧＨＲ２０２は「１ａｂｃｄｅ」に更新される（ステップＳ４７）。その後、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ≠ＲＥＳＵＬＴ−ＴＡＫＥＮであるか、即ち、確定した分岐の成立又は不成立の結果が予測と異なるか否かを判別する（ステップＳ４８）。ステップＳ４８で確定した分岐の成立又は不成立の結果が予測と異なる場合には（ＹＥＳ）、第１ＧＨＲ１０１は、更新後の第２ＧＨＲ２０２の値「１ａｂｃｄｅ」で更新される（ステップＳ４９）。その後、ステップＳ３７及びＳ３８の工程が実行される。ステップＳ４８で確定した分岐の成立又は不成立の結果が予測と一致する場合には（ＮＯ）、ステップＳ３９の工程が実行される。ステップ４５の判定は図７において判別回路２０３によって、ステップＳ４８の判定は図７において比較回路２０５によって、それぞれ実現される。
【００８１】
ステップＳ４５で分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでおらず（ＮＯ）且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝１である場合には、第２ＧＨＲ２０２は「１ｂｃｄｅｆ」に更新される（ステップＳ５０）。その後、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ≠ＲＥＳＵＬＴ−ＴＡＫＥＮであるか、即ち、確定した分岐の成立又は不成立の結果が予測と異なるか否かを判別する（ステップＳ５１）。ステップＳ５１で確定した分岐の成立又は不成立の結果が予測と異なる場合には（ＹＥＳ）、第１ＧＨＲ１０１は、更新後の第２ＧＨＲ２０２の値「１ｂｃｄｅｆ」で更新される（ステップＳ５２）。その後、ステップＳ３７及びＳ３８の工程が実行される。ステップＳ５１で確定した分岐の成立又は不成立の結果が予測と一致する場合には（ＮＯ）、ステップＳ３９の工程が実行される。ステップ４５の判定は図７において判別回路２０３によって、ステップＳ５１の判定は図７において比較回路２０５によって、それぞれ実現される。
【００８２】
ステップＳ４６で分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでおり（ＹＥＳ）且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝０である場合には、第２ＧＨＲ２０２は「０ａｂｃｄｅ」に更新される（ステップＳ５３）。その後、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ≠ＲＥＳＵＬＴ−ＴＡＫＥＮであるか、即ち、確定した分岐の成立又は不成立の結果が予測と異なるか否かを判別する（ステップＳ５４）。ステップＳ５４で確定した分岐の成立又は不成立の結果が予測と異なる場合には（ＹＥＳ）、第１ＧＨＲ１０１は、更新後の第２ＧＨＲ２０２の値「０ａｂｃｄｅ」で更新される（ステップＳ５５）。その後、ステップＳ３７及びＳ３８の工程が実行される。ステップＳ５４で確定した分岐の成立又は不成立の結果が予測と一致する場合には（ＮＯ）、ステップＳ３９の工程が実行される。ステップ４６の判定は図７において判別回路２０３によって、ステップＳ５４の判定は図７において比較回路２０５によって、それぞれ実現される。
【００８３】
ステップＳ４６で分岐命令アドレスＢＩＡＲ［31：0］が３２Ｂｙｔｅ境界を跨いでおらず（ＮＯ）且つＲＥＳＵＬＴ−ＴＡＫＥＮ＝０である場合には、第２ＧＨＲ２０２は「ａｂｃｄｅｆ」に更新される（ステップＳ５６）。尚、この場合、第２ＧＨＲ２０２は、第２ＧＨＲ２０２の最新の情報とＲＥＳＵＬＴ−ＴＡＫＥＮとの論理和に更新されるので、第２ＧＨＲ２０２は、更新前の状態と変わらない。その後、ＰＲＥＤＩＣＴ−ＴＡＫＥＮ≠ＲＥＳＵＬＴ−ＴＡＫＥＮであるか、即ち、確定した分岐の成立又は不成立の結果が予測と異なるか否かを判別する（ステップＳ５７）。ステップＳ５７で確定した分岐の成立又は不成立の結果が予測と異なる場合には（ＹＥＳ）、第１ＧＨＲ１０１は、更新後の第２ＧＨＲ２０２の値「ａｂｃｄｅｆ」で更新される（ステップＳ５８）。その後、ステップＳ３７及びＳ３８の工程が実行される。ステップＳ５７で確定した分岐の成立又は不成立の結果が予測と一致する場合には（ＮＯ）、ステップＳ３９の工程が実行される。ステップ４６の判定は図７において判別回路２０３によって、ステップＳ５７の判定は図７において比較回路２０５によって、それぞれ実現される。
【００８４】
以上説明したように、本実施の形態によれば、演算処理装置としてのＣＰＵ２Ａ，２Ｂは、演算完了時の分岐の成立又は不成立が確定した結果を時系列に示した第２ＧＨＲ２０２に加え、命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示した第１ＧＨＲ１０１を実装する。分岐予測部１２は、命令フェッチ時に、分岐履歴（ＢＲＨＩＳ１０２）だけでなく、第１ＧＨＲ１０１に基づいて決定される、期待通りの分岐方向であるか否かを示す分岐成立確度を使って、分岐予測を行う。これにより、少なくとも分岐予測が成功している間は第１ＧＨＲと分岐予測とのズレを無くすことができ、迅速且つ高精度の分岐予測が可能となる。
【００８５】
分岐予測が失敗したときは第１ＧＨＲ１０１が正しく更新されないため、それ以降の分岐予測が正しく行われない。そこで、分岐演算の結果に基づいて分岐予測が失敗であったと確定した場合には、分岐履歴更新部２４が第２ＧＨＲ２０２の値を第１ＧＨＲ１０１へコピーする。分岐予測が失敗した場合は、分岐制御部２１は、分岐予測の対象となった命令の後続命令の処理は全てキャンセルする（即ち、ズレが生じた後の第１ＧＨＲ１０１に基づいた命令の処理は全て破棄する）。そして、命令フェッチ制御部１１が、分岐演算の結果に基づいて正しいアドレスから再度命令フェッチをやり直す。再度の命令フェッチ時には、第１ＧＨＲ１０１が分岐確定後の値に更新されるため、高精度の分岐予測が可能となる。
【符号の説明】
【００８６】
１  情報処理装置、２Ａ，２Ｂ  ＣＰＵ、３Ａ，３Ｂ  メインメモリ、１１  命令フェッチ制御部、１２  分岐予測部、１３  一次命令キャッシュ、１４  二次キャッシュ、１５  メモリコントローラ、１６  命令バッファ、１７  命令デコーダ、１８  命令発行制御部、１９  一次オペランドキャッシュ、２０  演算器、２１  分岐制御部、２２  レジスタ、２３  命令完了制御部、２４  分岐履歴更新部
【図１】
2012127666.tif 000003
【図２】
2012127666.tif 000004
【図３】
2012127666.tif 000005
【図４】
2012127666.tif 000006
【図５】
2012127666.tif 000007
【図６】
2012127666.tif 000008
【図７】
2012127666.tif 000009
【図８】
2012127666.tif 000010
【図９】
2012127666.tif 000011
【手続補正書】
【提出日】平成25年10月3日(2013.10.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項５
【補正方法】変更
【補正の内容】
【請求項５】
演算処理装置と、当該演算処理装置に接続されるメモリとを備える情報処理装置であって、
前記メモリは、前記演算処理装置でフェッチされた命令フェッチアドレスに対応するデータを格納し、
前記演算処理装置は、
前記命令フェッチアドレスを確定し、命令フェッチを実行する実行手段と、
命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す情報を保持する第１グローバル履歴レジスタ、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスをエントリとして保持する分岐履歴テーブル、前記命令フェッチアドレスに対応する命令が期待通りの分岐方向であるか否かを示す分岐成立確度をエントリとして保持するパターン履歴テーブル、及び前記命令フェッチアドレスをインデックスとして前記分岐履歴テーブルから検索される分類情報と、前記命令フェッチアドレス並びに前記第１グローバル履歴レジスタの情報をインデックスとして前記パターン履歴テーブルから検索される分岐成立確度とに基づいて、前記命令フェッチアドレスに対応する命令の分岐予測を行う予測部を備える分岐予測手段と、
前記メモリから前記データを読み出し、分岐演算を実行する分岐演算手段と、
分岐演算完了時の分岐の成立又は不成立が確定した結果を時系列に示す情報を保持する第２グローバル履歴レジスタを備え、前記分岐演算手段による分岐演算の結果に基づいて前記予測部による分岐予測が失敗であると確定した場合に、前記第１グローバル履歴レジスタを前記第２グローバル履歴レジスタの情報で更新する更新手段とを備え、
前記第１グローバル履歴レジスタの更新後に、前記実行手段は、前記命令フェッチを再実行することを特徴とする情報処理装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
上記目的を達成するため、開示された情報処理装置は、演算処理装置と、当該演算処理装置に接続されるメモリとを備える情報処理装置であって、前記メモリは、前記演算処理装置でフェッチされた命令フェッチアドレスに対応するデータを格納し、前記演算処理装置は、前記命令フェッチアドレスを確定し、命令フェッチを実行する実行手段と、命令フェッチ時の分岐の成立又は不成立を予測した結果を時系列に示す情報を保持する第１グローバル履歴レジスタ、過去に分岐成立した分岐命令の分類情報及び分岐ターゲットアドレスをエントリとして保持する分岐履歴テーブル、前記命令フェッチアドレスに対応する命令が期待通りの分岐方向であるか否かを示す分岐成立確度をエントリとして保持するパターン履歴テーブル、及び前記命令フェッチアドレスをインデックスとして前記分岐履歴テーブルから検索される分類情報と、前記命令フェッチアドレス並びに前記第１グローバル履歴レジスタの情報をインデックスとして前記パターン履歴テーブルから検索される分岐成立確度とに基づいて、前記命令フェッチアドレスに対応する命令の分岐予測を行う予測部を備える分岐予測手段と、前記メモリから前記データを読み出し、分岐演算を実行する分岐演算手段と、分岐演算完了時の分岐の成立又は不成立が確定した結果を時系列に示す情報を保持する第２グローバル履歴レジスタを備え、前記分岐演算手段による分岐演算の結果に基づいて前記予測部による分岐予測が失敗であると確定した場合に、前記第１グローバル履歴レジスタを前記第２グローバル履歴レジスタの情報で更新する更新手段とを備え、前記第１グローバル履歴レジスタの更新後に、前記実行手段は、前記命令フェッチを再実行する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
図３は、分岐予測部１２の概略構成図である。図３において、垂直方向の破線は、タイミングが異なる実行ステージを示す。また、図３では、一例として、命令フェッチ制御部１１から分岐予測部１２が受け取る命令フェッチアドレスＦＩＡＲ(Fetched Instruction AddRess)１００は、３２ビットで構成されている。図３において、命令フェッチアドレスＦＩＡＲ１００は、ＦＩＡＲ［31：0］と記載されており、［31：0］は第０〜第３１ビットの計３２ビットであることを示す。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
ステップＳ１５でＰ−ＣＯＮＤ−ＢＩＴが１である場合には（ＹＥＳ）、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］≧２（ＢＰ［1：0］＝「１０」又は「１１」）であるか又はＰ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］＜２（ＢＰ［1：0］＝「００」又は「０１」）であるか否かを判別する（ステップＳ１９）。ステップＳ１９でＰ−ＥＸＰＥＣＴ−ＢＩＴ＝１且つＢＰ［1：0］≧２である場合には、分岐予測部１２の結果として分岐不成立と予測し（ステップＳ２０）、第１ＧＨＲ１０１は「０ａｂｃｄｅ」に更新される（ステップＳ２１）。その後、上記ステップＳ１４が実行される。ステップＳ２０及びステップＳ２１は図３において論理積回路１０９の出力が１、論理積回路１１０〜１１２の出力が全て０となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして０を出力し、論理和回路１１４は、第１ＧＨＲ１０１の更新値として０を出力する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００５３
【補正方法】変更
【補正の内容】
【００５３】
さらに、ステップＳ１５でＰ−ＣＯＮＤ−ＢＩＴが１である場合には（ＹＥＳ）、Ｐ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］≧２（ＢＰ［1：0］＝「１０」又は「１１」）であるか又はＰ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］＜２（ＢＰ［1：0］＝「００」又は「０１」）であるか否かを判別する（ステップＳ２４）。ステップＳ２４でＰ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］≧２（ＢＰ［1：0］＝「１０」又は「１１」）である場合には、分岐予測部１２の結果として分岐成立と予測し（ステップＳ２５）、第１ＧＨＲ１０１は「１ａｂｃｄｅ」に更新される（ステップＳ２６）。その後、上記ステップＳ１８の工程が実行される。ステップＳ２５及びステップＳ２６は図３において論理積回路１０９の出力が１、論理積回路１１２の出力が１となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして１を出力、論理和回路１１４は、第１ＧＨＲ１０１の更新値として１を出力する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００５４
【補正方法】変更
【補正の内容】
【００５４】
ステップＳ２４でＰ−ＥＸＰＥＣＴ−ＢＩＴ＝０且つＢＰ［1：0］＜２（ＢＰ［1：0］＝「００」又は「０１」）である場合には、分岐予測部１２の結果として分岐不成立と予測し（ステップＳ２７）、第１ＧＨＲ１０１は「０ａｂｃｄｅ」に更新される（ステップＳ２８）。その後、上記ステップＳ１４の工程が実行される。ステップＳ２７及びステップＳ２８は図３において論理積回路１０９の出力が１、論理積回路１１０〜１１２の出力が全て０となることで実現され、論理和回路１１３は、ＰＲＥＤＩＣＴ−ＴＡＫＥＮとして０を出力、論理和回路１１４は、第１ＧＨＲ１０１の更新値として０を出力する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
第２ＧＨＲ２０２は、分岐成立を１、分岐不成立を０の１ビットで表した分岐演算結果を時系列に６ビット記憶したものである。第２ＧＨＲ２０２は、一度に命令フェッチした命令列の固まり（例えば命令フェッチの単位を３２Ｂｙｔｅ，１命令を３２ビットで表した場合は８命令分）を単位として、条件分岐命令の分岐演算が完了したときに更新される。即ち、分岐演算自体は１命令毎に行われるが、例えば、命令フェッチの中に２つ以上の分岐命令が入っている場合には、２つ以上の分岐命令を１単位として、第２ＧＨＲ２０２は更新される。従って、図７の論理積回路２０４の出力、ＲＥＳＵＬＴ−ＴＡＫＥＮ、及び論理積回路２０６の出力は、命令フェッチに含まれる分岐命令の数だけそれぞれレジスタ２０９〜２１１に一時保存され、条件分岐命令の分岐演算が完了したときに一括で出力される。第２ＧＨＲ２０２を命令フェッチの単位ごとに更新することは、第１ＧＨＲ１０１と同等の履歴を作成する上で必要である。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
論理積回路２０７は、ＣＯＭＰＬＥＴＥ＝１且つＤ−ＣＯＮＤ−ＢＩＴ＝１である場合に、レジスタ２１４を介してＰＨＴ１０３に更新指示を出力する。比較回路２０８は、Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと不一致であるか否かを判別する。Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと不一致である場合は、比較回路２０８は、レジスタ２１５を介して加算器２１６の選択を示す「１」を選択回路２１８に出力する。尚、Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと不一致である場合は、分岐の演算結果が期待通りでなかったことを示す。Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと一致する場合は、比較回路２０８は、レジスタ２１５を介して減算器２１７の選択を示す「０」を選択回路２１８に出力する。尚、Ｄ−ＥＸＰＥＣＴ−ＢＩＴがＲＥＳＵＬＴ−ＴＡＫＥＮと一致する場合は、分岐の演算結果が期待通りであることを示す。
【国際調査報告】
2012127666.tif 000012
2012127666.tif 000013
2012127666.tif 000014
2012127666.tif 000015