(57)【要約】【課題】条件分岐命令の分岐予測の確度を向上させることができる演算処理装置を提供することを課題とする。【解決手段】演算処理装置は、条件分岐命令の過去の分岐履歴情報に基づき、フェッチされた条件分岐命令の分岐予測情報を出力する第１の予測部（３０２，３１０）と、分岐成立連続回数と分岐不成立連続回数とをパターン情報記憶部（３０３）に記憶し、パターン情報記憶部に記憶された過去の分岐成立連続回数又は分岐不成立連続回数に基づき、フェッチされた条件分岐命令の分岐予測情報を出力する第２の予測部（３１２）と、第１の予測部が出力する分岐予測情報又は第２の予測部が出力する分岐予測情報を選択的に出力する選択部（３１１，３１３〜３１５）と、選択部により出力された分岐予測情報に応じて、条件分岐命令の次の命令のアドレス又は条件分岐命令の分岐先アドレスを命令フェッチ部に出力するセレクタ（３０５）とを有する。【選択図】図３
2015036888.tif 000002
【特許請求の範囲】
【請求項１】
条件分岐命令の過去の分岐履歴情報を記憶する分岐履歴記憶部と、
前記分岐履歴記憶部が記憶する分岐履歴情報に基づき、フェッチされた条件分岐命令の分岐予測情報を出力する第１の予測部と、
条件分岐命令の分岐が連続して成立した回数である分岐成立連続回数と条件分岐命令の分岐が連続して成立しなかった回数である分岐不成立連続回数とをパターン情報記憶部に記憶し、前記パターン情報記憶部に記憶された過去の分岐成立連続回数又は分岐不成立連続回数に基づき、フェッチされた条件分岐命令の分岐予測情報を出力する第２の予測部と、
前記第１の予測部が出力する分岐予測情報又は前記第２の予測部が出力する分岐予測情報を選択的に出力する選択部と、
前記選択部により出力された分岐予測情報に応じて、前記条件分岐命令の次の命令のアドレス又は前記条件分岐命令の分岐先アドレスを命令フェッチ部に出力するセレクタと
を有することを特徴とする演算処理装置。
【請求項２】
前記選択部は、
前記分岐成立連続回数と前記分岐不成立連続回数とを有するパターンが、前記分岐履歴情報内に過去に２回以上現れた場合、前記第２の予測部が出力する分岐予測情報を出力するとともに、前記分岐成立連続回数と前記分岐不成立連続回数とを有するパターンが過去に１回以下現れた場合、前記第１の予測部が出力する分岐予測情報を出力することを特徴とする請求項１記載の演算処理装置。
【請求項３】
前記選択部は、
前記第２の予測部が出力する分岐予測情報を出力した場合、前記第２の予測部が出力する分岐予測情報による予測が失敗したとき、前記第２の予測部が出力する予測情報を無効化することを特徴とする請求項１又は２記載の演算処理装置。
【請求項４】
前記選択部は、
前記第２の予測部が出力する分岐予測情報を出力した場合、前記第１の予測部が出力する分岐予測情報と前記第２の予測部が出力する分岐予測情報とが異なっており、且つ、前記第２の予測部が出力する分岐予測情報による予測が失敗したとき、前記第２の予測部が出力する分岐予測情報を無効化することを特徴とする請求項１又は２記載の演算処理装置。
【請求項５】
条件分岐命令の過去の分岐履歴情報を記憶する分岐履歴記憶部を有する演算処理装置の制御方法において、
前記演算処理装置が有する第１の予測部が、前記分岐履歴記憶部が記憶する分岐履歴情報に基づき、フェッチされた条件分岐命令の分岐予測情報を出力し、
前記演算処理装置が有する第２の予測部が、条件分岐命令の分岐が連続して成立した回数である分岐成立連続回数と条件分岐命令の分岐が連続して成立しなかった回数である分岐不成立連続回数とをパターン情報記憶部に記憶し、
前記第２の予測部が、前記パターン情報記憶部に記憶された過去の分岐成立連続回数又は分岐不成立連続回数に基づき、フェッチされた条件分岐命令の分岐予測情報を出力し、
前記演算処理装置が有する選択部が、前記第１の予測部が出力する分岐予測情報又は前記第２の予測部が出力する分岐予測情報を選択的に出力し、
前記演算処理装置が有するセレクタが、前記選択部により出力された分岐予測情報に応じて、前記条件分岐命令の次の命令のアドレス又は前記条件分岐命令の分岐先アドレスを命令フェッチ部に出力することを特徴とする演算処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置及び演算処理装置の制御方法に関する。
【背景技術】
【０００２】
パイプライン制御方式を実行するプロセッサは、メモリから命令実行部への命令フェッチを効率的に行うために、分岐を予測する機構である分岐予測機構を有する。アウトオブオーダ制御を実行するプロセッサにおいては、命令実行に先行して命令フェッチが行われることがあるので、分岐予測機構の重要性が高い。
【０００３】
プロセッサによって実行される各条件分岐命令に対して条件分岐が行われたかの記録を記憶する分岐予測方法が知られている（例えば、特許文献１参照）。この記録は、各メモリーアドレスに各条件分岐の複数の発生を含み、条件分岐命令が実行された時、分岐が記録及び予測パターンに基づいて発生するか否かを予測し、予測に応答して命令ストリーム内の命令をフェッチする。
【０００４】
また、条件分岐命令が実行された時、分岐が過去最も新しい条件分岐の実績及び過去数回の分岐予測が的中したか否かの合否に基づいて発生するか否かを予測する分岐予測方法が知られている（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平６−５９８８７号公報
【特許文献２】特開２００１−１４１６２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
条件分岐命令の分岐予測を行う場合には、過去の条件分岐の分岐結果を記録し、過去の条件分岐履歴パターン毎の分岐予測情報を記録する必要がある。しかし、過去の条件分岐履歴パターンは、種類が多いため、過去の条件分岐履歴パターン毎の分岐予測情報を記録するには多大な時間を要する。それが記録されるまでは、正確な分岐予測を行うことが困難であり、分岐予測の確度が低くなってしまう課題がある。
【０００７】
１つの側面では、本発明の目的は、条件分岐命令の分岐予測の確度を向上させることができる演算処理装置及び演算処理装置の制御方法を提供することである。
【課題を解決するための手段】
【０００８】
演算処理装置は、条件分岐命令の過去の分岐履歴情報を記憶する分岐履歴記憶部と、前記分岐履歴記憶部が記憶する分岐履歴情報に基づき、フェッチされた条件分岐命令の分岐予測情報を出力する第１の予測部と、条件分岐命令の分岐が連続して成立した回数である分岐成立連続回数と条件分岐命令の分岐が連続して成立しなかった回数である分岐不成立連続回数とをパターン情報記憶部に記憶し、前記パターン情報記憶部に記憶された過去の分岐成立連続回数又は分岐不成立連続回数に基づき、フェッチされた条件分岐命令の分岐予測情報を出力する第２の予測部と、前記第１の予測部が出力する分岐予測情報又は前記第２の予測部が出力する分岐予測情報を選択的に出力する選択部と、前記選択部により出力された分岐予測情報に応じて、前記条件分岐命令の次の命令のアドレス又は前記条件分岐命令の分岐先アドレスを命令フェッチ部に出力するセレクタとを有する。
【発明の効果】
【０００９】
第１の予測部及び第２の予測部を設けることにより、条件分岐命令の分岐予測の確度を向上させることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、本実施形態による演算処理装置としてのプロセッサを含む情報処理システムの構成例を示す図である。
【図２】図２は、プロセッサの構成例を示す図である。
【図３】図３は、図２の分岐予測部の構成例を示す図である。
【図４】図４（Ａ）〜（Ｃ）は、テーブルの構成例を示す図である。
【図５】図５は、図３のパターン履歴テーブルを説明するための図である。
【図６】図６（Ａ）及び（Ｂ）は、ローカルパターンテーブルの例を説明するための図である。
【図７】図７は、図３の生成部の構成例を示す図である。
【図８】図８は、演算処理装置の制御方法を示すフローチャートである。
【図９】図９は、図２の分岐履歴更新部の入出力信号を示す図である。
【図１０】図１０は、図９の分岐履歴更新部の一部の構成例を示す図である。
【図１１】図１１は、図１０の回路の処理を示すフローチャートである。
【図１２】図１２は、図９の分岐履歴更新部の一部の構成例を示す図である。
【図１３】図１３は、図１２の回路の処理を示すフローチャートである。
【発明を実施するための形態】
【００１１】
図１は、本実施形態による演算処理装置としてのプロセッサを含む情報処理システムの構成例を示す図である。図１に示す情報処理システムは、例えば複数のプロセッサ１１Ａ、１１Ｂ及びメモリ１２Ａ、１２Ｂと、外部装置との入出力制御を行うインターコネクト制御部１３とを有する。
【００１２】
図２は、プロセッサ１１の構成例を示す図である。プロセッサ１１は、演算処理装置であり、図１のプロセッサ１１Ａ及び１１Ｂに対応し、例えば命令のアウトオブオーダ実行やパイプライン処理の機能を有する。
【００１３】
命令フェッチステージでは、命令フェッチ部２１、命令バッファ２４、分岐予測部２２、一次命令キャッシュメモリ２３、及び二次キャッシュメモリ３４等が動作する。命令フェッチ部２１は、分岐予測部２２からフェッチする命令の予測分岐先アドレス、分岐制御部３０から分岐演算により確定した分岐先アドレス等を受け取る。命令フェッチ部２１は、受け取った予測分岐先アドレス、分岐先アドレス、及び命令フェッチ部２１内で作成した分岐しない場合にフェッチする命令の連続した次のアドレス等から、１つのアドレスを選択して次の命令フェッチアドレスを確定する。命令フェッチ部２１は、確定した命令フェッチアドレスを一次命令キャッシュメモリ２３に出力し、出力された確定後の命令フェッチアドレスに対応する命令コードをフェッチする。
【００１４】
一次命令キャッシュメモリ２３は、二次キャッシュメモリ３４の一部のデータを格納しているものであり、二次キャッシュメモリ３４は、メモリコントローラ３５を介してアクセス可能なメモリの一部のデータを格納しているものである。一次命令キャッシュメモリ２３に該当するアドレスのデータが存在しない場合には二次キャッシュメモリ３４からデータをフェッチし、二次キャッシュメモリ３４に該当するデータが存在しない場合にはメモリからデータをフェッチする。本実施形態では、メモリはプロセッサ１１の外部に配置しているため、外部にあるメモリとの入出力制御はメモリコントローラ３５を介して行われる。一次命令キャッシュメモリ２３や二次キャッシュメモリ３４、メモリの該当するアドレスからフェッチされた命令コードは、命令バッファ２４に格納される。
【００１５】
分岐予測部２２は、命令フェッチ部２１から出力された命令フェッチアドレスを受け取り、命令フェッチと並行して分岐予測を実行する。分岐予測部２２は、受け取った命令フェッチアドレスを基に分岐予測を行い、分岐の成立又は不成立を示す分岐方向と予測分岐先アドレスとを命令フェッチ部２１へ返す。命令フェッチ部２１は、予測された分岐方向が成立であった場合には次の命令フェッチアドレスとして予測された分岐先アドレスを選択する。
【００１６】
命令発行ステージでは、命令デコーダ２５及び命令発行制御部２６が動作する。命令デコーダ２５は、命令バッファ２４から命令コードを受け取って命令の種別や必要な実行資源等を解析し、解析結果を命令発行制御部２６に出力する。命令発行制御部２６は、リザベーションステーションの構造を持つ。命令発行制御部２６は、命令で参照するレジスタ等の依存関係を見て、依存関係のあるレジスタの更新状況や同じ実行資源を用いる命令の実行状況等から実行資源が命令を実行可能かどうかを判断する。命令発行制御部２６は、実行資源が命令を実行可能であると判断した場合には、レジスタ番号やオペランドアドレス等の命令の実行に必要な情報を演算器２６及び一次オペランドキャッシュメモリ２９等の実行資源に対して出力する。また、命令発行制御部２６は、実行可能な状態になるまで命令を格納しておくバッファの機能も有する。
【００１７】
命令実行ステージでは、演算器２８、一次オペランドキャッシュメモリ２９、及び分岐制御部３０等の実行資源が動作する。演算器２８は、レジスタ３１や一次オペランドキャッシュメモリ２９からデータを受け取り、四則演算、論理演算、三角関数演算、及びアドレス計算等の命令に対応した演算を実行し、演算結果をレジスタ３１や一次オペランドキャッシュメモリ２９に出力する。一次オペランドキャッシュメモリ２９は、命令キャッシュメモリ２３と同様に、二次キャッシュメモリ３４の一部のデータを格納しているものである。一次オペランドキャッシュメモリ２９は、ロード命令によるメモリから演算器２８やレジスタ３１へのデータのロードや、ストア命令による演算器２８やレジスタ３１からメモリへのデータのストア等に用いられる。各実行資源は、命令実行の完了通知を命令完了制御部３２へ出力する。
【００１８】
分岐制御部３０は、命令デコーダ２５から分岐命令の種別を受け取り、演算器２８から分岐先アドレスや分岐条件となる演算の結果を受け取って、演算結果が分岐条件を満たしていれば分岐成立、満たしていなければ分岐不成立の判断を行い、分岐方向を確定する。また、分岐制御部３０は、演算結果と分岐予測時の分岐先アドレスと分岐方向が一致するかどうかの判断や、分岐命令の順序関係の制御も行う。分岐制御部３０は、演算結果と予測とが一致した場合には命令完了制御部３２へ分岐命令の完了通知を出力する。一方、演算結果と予測とが一致しなかった場合には分岐予測失敗を意味するので、分岐制御部３０は、命令完了制御部３２へ分岐命令の完了通知とともに後続命令のキャンセル及び再命令フェッチ要求を出力する。
【００１９】
命令完了ステージでは、命令完了制御部３２、レジスタ３１、及び分岐履歴更新部３３が動作する。命令完了制御部３２は、命令の各実行資源から受け取った完了通知を基に、コミットスタックエントリに格納された命令コード順に命令完了処理を行い、レジスタ３１の更新指示を出力する。レジスタ３１は、命令完了制御部３２からレジスタ更新指示を受け取ると、演算器２８や一次オペランドキャッシュメモリ２９から受け取る演算結果のデータを基にレジスタの更新を実行する。分岐履歴更新部３３は、分岐制御部３０から受け取る分岐演算の結果を基に分岐予測の履歴更新データを作成し、分岐予測部２２に出力する。
【００２０】
図３は、図２の分岐予測部２２の構成例を示す図である。分岐予測部２２は、命令フェッチアドレス（Fetched Instruction AddRess）FIAR[31:0]及びグローバル履歴レジスタ（Global History Register）GHR[5:0]の値を入力し、次の命令フェッチアドレスNEXT‐FIAR[31:0]を図２の命令フェッチ部２１に出力する。命令フェッチアドレスFIAR[31:0]は、図２の命令フェッチ部２１から入力され、命令フェッチされた命令の３２ビットのアドレスである。グローバル履歴レジスタGHR[5:0]は、図２の分岐履歴更新部３３から入力され、例えば過去６回の条件分岐命令の分岐履歴を記憶する６ビットレジスタである。
【００２１】
分岐履歴テーブル（BRHIS：BRanch HIStory table）３０１は、図４（Ａ）に示すように、命令フェッチアドレスFIAR[31:0]毎に、有効フラグVALID、３２ビットの分岐先アドレス（Predicted Target Instruction AddRess）PTIAR[31:0]、条件分岐命令ビットP-COND-BIT、条件成立期待値BRHIS-EXPECT-BITを記憶する。分岐履歴テーブル（分岐履歴記憶部）３０１は、命令フェッチと並行して、命令フェッチアドレスFIAR[31:0]を入力すると、命令フェッチアドレスFIAR[31:0]に対応する有効フラグVALID、分岐先アドレスPTIAR[31:0]、条件分岐命令ビットP-COND-BIT、条件成立期待値BRHIS-EXPECT-BITを出力する。
【００２２】
有効フラグVALIDは、０である場合に命令フェッチアドレスFIAR[31:0]の命令が分岐命令でないことを示し、１である場合に命令フェッチアドレスFIAR[31:0]の命令が分岐命令であることを示す。分岐先アドレスPTIAR[31:0]は、命令フェッチアドレスFIAR[31:0]の分岐命令の分岐先（分岐ターゲット）アドレスである。条件分岐命令ビットP-COND-BITは、０である場合に命令フェッチアドレスFIAR[31:0]の命令が条件分岐命令でないことを示し、１である場合に命令フェッチアドレスFIAR[31:0]の命令が条件分岐命令であることを示す。条件成立期待値BRHIS-EXPECT-BITは、０である場合に命令フェッチアドレスFIAR[31:0]の条件分岐命令の分岐期待値が不成立であることを示し、１である場合に命令フェッチアドレスFIAR[31:0]の条件分岐命令の分岐期待値が成立であることを示す。条件分岐命令は、条件が成立の場合には次回は分岐先アドレスPTIAR[31:0]の命令に移行し、条件が不成立の場合には次回は次のアドレスの命令に移行する。
【００２３】
バッファ３０６は、有効フラグVALIDをバッファリングし、分岐履歴テーブルヒットビットBRHIS-HITを出力する。論理積（ＡＮＤ）回路３０７は、分岐履歴テーブルヒットビットBRHIS-HITと条件分岐命令ビットP-COND-BITの論理反転ビットとの論理積を出力する。論理積回路３０８は、分岐履歴テーブルヒットビットBRHIS-HITと条件分岐命令ビットP-COND-BITと論理和（ＯＲ）回路３１５の出力値との論理積を出力する。論理和回路３０９は、論理積回路３０７の出力値と論理積回路３０８の出力値との論理和を分岐予測情報PREDICT-TAKENとして出力する。分岐予測情報PREDICT-TAKENは、０が分岐不成立の予測を示し、１が分岐成立の予測を示す。セレクタ３０５は、分岐予測情報PREDICT-TAKENが０の場合には、命令フェッチアドレスFIAR[31:0]に３２バイトを加算したアドレスを次の命令フェッチアドレスNEXT‐FIAR[31:0]として選択して出力し、分岐予測情報PREDICT-TAKENが１の場合には、分岐先アドレスPTIAR[31:0]を次の命令フェッチアドレスNEXT‐FIAR[31:0]として選択して出力する。ここで、一度にフェッチするデータの単位は３２バイトである。
【００２４】
有効フラグVALIDが０である場合には、フェッチする命令が分岐命令でないことを示すので、分岐予測情報PREDICT-TAKENが０になり、分岐不成立を予測する。有効フラグVALIDが１である場合には、フェッチする命令が分岐命令であることを示し、かつ条件分岐命令ビットP-COND-BITが０である場合には、フェッチする命令が無条件分岐命令であることを示すので、分岐予測情報PREDICT-TAKENが１になり、分岐成立を予測する。また、有効フラグVALIDが１かつ条件分岐命令ビットP-COND-BITが１である場合には、フェッチする命令が条件分岐命令であることを示すので、論理和回路３１５の出力値が分岐予測情報PREDICT-TAKENになる。
【００２５】
次に、パターン履歴テーブル（PHT：Patten History Table）３０２について説明する。排他的論理和回路３０４は、命令フェッチアドレスFIAR[5:0]とグローバル履歴レジスタGHR[5:0]の値との排他的論理和を出力する。命令フェッチアドレスFIAR[5:0]は、命令フェッチアドレスFIAR[31:0]のうちの下位６ビットのアドレスである。パターン履歴テーブル３０２は、図４（Ｂ）に示すように、命令フェッチアドレスFIAR[31:6]及び排他的論理和回路３０４の出力値毎に、２ビットの分岐成立確度情報BP1[1:0]を記憶する。命令フェッチアドレスFIAR[31:6]は、命令フェッチアドレスFIAR[31:0]のうちの上位２６ビットのアドレスである。分岐成立確度情報BP1[1:0]は、図２の分岐履歴更新部３３により、分岐結果が条件成立期待値BRHIS-EXPECT-BITと同じ場合にはデクリメントされ、分岐結果が条件成立期待値BRHIS-EXPECT-BITと異なる場合にはインクリメントされる。ただし、分岐成立確度情報BP1[1:0]は、０〜３の値であり、０の状態でデクリメントされても０を維持し、３の状態でインクリメントされても３を維持する。分岐成立確度情報BP1[1:0]の値が小さいほど、条件成立期待値BRHIS-EXPECT-BITの確度が高いことを意味する。
【００２６】
図５は、図３のパターン履歴テーブル３０２を説明するための図である。グローバル履歴レジスタGHR[5:0]は、例えば初期値が「００００００」であり、１が条件成立を示し、０が条件不成立を示す。分岐履歴更新部３３は、条件分岐命令１が条件不成立の場合には、グローバル履歴レジスタGHR[5:0]を右１ビットシフトし、左１ビット目を「０」にするので、グローバル履歴レジスタGHR[5:0]が「００００００」になる。次に、分岐履歴更新部３３は、条件分岐命令１が条件成立の場合には、グローバル履歴レジスタGHR[5:0]を右１ビットシフトし、左１ビット目を「１」にするので、グローバル履歴レジスタGHR[5:0]が「１０００００」になる。次に、分岐履歴更新部３３は、条件分岐命令１が条件成立の場合には、グローバル履歴レジスタGHR[5:0]を右１ビットシフトし、左１ビット目を「１」にするので、グローバル履歴レジスタGHR[5:0]が「１１００００」になる。次に、分岐履歴更新部３３は、条件分岐命令１が条件不成立の場合には、グローバル履歴レジスタGHR[5:0]を右１ビットシフトし、左１ビット目を「０」にするので、グローバル履歴レジスタGHR[5:0]が「０１１０００」になる。次に、分岐履歴更新部３３は、条件分岐命令１が条件成立の場合には、グローバル履歴レジスタGHR[5:0]を右１ビットシフトし、左１ビット目を「１」にするので、グローバル履歴レジスタGHR[5:0]が「１０１１００」になる。次に、分岐履歴更新部３３は、条件分岐命令１が条件成立の場合には、グローバル履歴レジスタGHR[5:0]を右１ビットシフトし、左１ビット目を「１」にするので、グローバル履歴レジスタGHR[5:0]が「１１０１１０」になる。これらのグローバル履歴レジスタGHR[5:0]に対応する分岐成立確度情報BP1[1:0]がパターン履歴テーブル３０２に記録される。
【００２７】
ここで、「１１０１１０」のグローバル履歴レジスタGHR[5:0]の値５０１が入力された場合、上記のグローバル履歴レジスタGHR[5:0]が「００００００」〜「１０１１００」の間は、「１１０１１０」のグローバル履歴レジスタGHR[5:0]の値５０１と不一致であるため、パターン履歴テーブル３０２による分岐予測はできない。その後、「１１０１１０」のグローバル履歴レジスタGHR[5:0]の分岐成立確度情報BP1[1:0]がパターン履歴テーブル３０２に記録されると、「１１０１１０」のグローバル履歴レジスタGHR[5:0]の値５０１と一致するため、パターン履歴テーブル３０２による分岐予測が可能になる。
【００２８】
条件分岐命令の分岐予測を行う場合には、グローバル履歴レジスタGHR[5:0]の履歴パターンに対応する分岐成立確度情報BP1[1:0]を記録し、グローバル履歴レジスタGHR[5:0]の履歴パターン毎の分岐成立確度情報BP1[1:0]を記録する必要がある。しかし、グローバル履歴レジスタGHR[5:0]の履歴パターンは、種類が多いため、グローバル履歴レジスタGHR[5:0]の履歴パターン毎の分岐成立確度情報BP1[1:0]を記録するには多大な時間を要する。それが記録されるまでは、正確な分岐予測を行うことが困難であり、分岐予測の確度が低くなってしまう。そこで、本実施形態では、それまでの間は、後述のローカルパターンテーブル（LPT：Local Pattern Table）３０３を用いて分岐予測を行うことにより、分岐予測の確度を向上させる。
【００２９】
排他的論理和回路５０３は、図３の排他的論理和回路３０４に対応し、グローバル履歴レジスタGHR[5:0]の値５０１と命令フェッチアドレスFIAR[5:0]の値５０２との排他的論理和をインデックス５０４として出力する。パターン履歴テーブル３０２は、命令フェッチアドレスFIAR[31:6]及びインデックス５０４を入力すると、それに対応する分岐成立確度情報BP1[1]を出力する。分岐成立確度情報BP1[1]は、２ビットの分岐成立確度情報BP1[1:0]のうちの上位１ビットの情報である。分岐成立確度情報BP1[1]が０の場合には、条件成立期待値BRHIS-EXPECT-BITの確度が高いことを示し、分岐成立確度情報BP1[1]が１の場合には、条件成立期待値BRHIS-EXPECT-BITの確度が低いことを示す。
【００３０】
排他的論理和回路３１０は、条件成立期待値BRHIS-EXPECT-BITと分岐成立確度情報BP1[1]との排他的論理和を出力する。条件成立期待値BRHIS-EXPECT-BITが１（成立）である場合、排他的論理和回路３１０は、分岐成立確度情報BP1[1]が０の場合には「１」（成立）を出力し、分岐成立確度情報BP1[1]が１の場合には「０」（不成立）を出力する。また、条件成立期待値BRHIS-EXPECT-BITが０（不成立）である場合、排他的論理和回路３１０は、分岐成立確度情報BP1[1]が０の場合には「０」（不成立）を出力し、分岐成立確度情報BP1[1]が１の場合には「１」（成立）を出力する。
【００３１】
ローカルパターンテーブル（パターン情報記憶部）３０３は、図４（Ｃ）に示すように、命令フェッチアドレスFIAR[31:0]毎に、有効フラグLPT-VALID、予測失敗ビットLPT-DIZZY、現在予測連続回数PRD-CNT[5:0]、現在予測条件成立ビットPRD-CNT-TKN、現在完了連続回数CMP-CNT[5:0]、現在完了条件成立ビットCMP-CNT-TKN、１周期条件成立連続回数THT-CNT[5:0]、条件成立連続回数確度ビットTHTC-PRD、条件成立変化ビットTHTC-DEF、１周期条件不成立連続回数THN-CNT[5:0]、条件不成立連続回数確度ビットTHNC-PRD、条件不成立変化ビットTHNC-DEFを記憶する。
【００３２】
図６（Ａ）は、ローカルパターンテーブル３０３の例を説明するための図である。ここで、「Ｔ」は条件分岐命令の条件成立を示し、「Ｎ」は条件分岐命令の条件不成立を示す。条件分岐命令は、例えば、第１の周期Ｒ１及び第２の周期Ｒ２で条件成立又は条件不成立になる。第１の周期Ｒ１では、条件成立Ｔが３回連続し、その後に、条件不成立Ｎが２回連続する。第２の周期Ｒ２でも、条件成立Ｔが３回連続し、その後に、条件不成立Ｎが２回連続する。第１の周期Ｒ１及び第２の周期Ｒ２は同じであるので、条件分岐命令は、例えば、第１の周期Ｒ１及び第２の周期Ｒ２で条件成立又は条件不成立になることを予測可能である。すなわち、条件成立Ｔが３回連続し、その後に、条件不成立Ｎが２回連続することが予測可能である。
【００３３】
この場合、１周期条件成立連続回数THT-CNT[5:0]は「３」になる。１周期条件不成立連続回数THNT-CNT[5:0]は「２」になる。条件成立連続回数確度ビットTHTC-PRDは、１周期条件成立連続回数THT-CNT[5:0]の確度を示し、第１の周期Ｒ１の条件成立Ｔの連続回数の「３」と第２の周期Ｒ２の条件成立Ｔの連続回数の「３」とが同じ場合に「１」になる。条件不成立連続回数確度ビットTHNC-PRDは、１周期条件不成立連続回数THN-CNT[5:0]の確度を示し、第１の周期Ｒ１の条件不成立Ｎの連続回数の「２」と第２の周期Ｒ２の条件不成立Ｎの連続回数の「２」とが同じ場合に「１」になる。条件成立変化ビットTHTC-DEFは、条件成立Ｔから条件不成立Ｎに変化した場合に「１」になる。条件不成立変化ビットTHNC-DEFは、条件不成立Ｎから条件成立Ｔに変化した場合に「１」になる。
【００３４】
有効フラグLPT-VALIDは、１である場合にローカルパターンテーブル３０３が有効であることを示し、０である場合にローカルパターンテーブル３０３が無効であることを示す。予測失敗ビットLPT-DIZZYは、一つ前に実行したローカルパターンテーブル３０３による分岐予測が失敗した場合に「１」になる。
【００３５】
現在予測連続回数PRD-CNT[5:0]は、現在の分岐予測の条件成立Ｔ又は条件不成立Ｎの連続回数を示す。現在予測条件成立ビットPRD-CNT-TKNは、１の場合には現在の分岐予測が条件成立Ｔを示し、０の場合には現在の分岐予測が条件不成立Ｎを示す。例えば、第１の周期Ｒ１内の２個目の分岐予測では、現在予測条件成立ビットPRD-CNT-TKNが「１」であり、現在予測連続回数PRD-CNT[5:0]が「２」である。この場合、次回の分岐予測は、条件成立Ｔであると予測することができる。また、第１の周期Ｒ１内の４個目の分岐予測では、現在予測条件成立ビットPRD-CNT-TKNが「０」であり、現在予測連続回数PRD-CNT[5:0]が「１」である。この場合、次回の分岐予測は、条件不成立Ｎであると予測することができる。
【００３６】
現在完了連続回数CMP-CNT[5:0]は、現在の分岐履歴更新部３３による分岐命令完了後の条件成立Ｔ又は条件不成立Ｎの連続回数を示す。現在完了条件成立ビットCMP-CNT-TKNは、１の場合には現在の分岐履歴更新部３３による分岐命令完了後の条件成立Ｔを示し、０の場合には現在の分岐履歴更新部３３による分岐命令完了後の条件不成立Ｎを示す。例えば、第１の周期Ｒ１内の２個目の分岐命令完了では、現在完了条件成立ビットCMP-CNT-TKNが「１」であり、現在完了連続回数CMP-CNT[5:0]が「２」である。また、第１の周期Ｒ１内の４個目の分岐命令完了では、現在完了条件成立ビットCMP-CNT-TKNが「０」であり、現在完了連続回数CMP-CNT[5:0]が「１」である。
【００３７】
図６（Ｂ）は、ローカルパターンテーブル３０３の他の例を説明するための図である。条件分岐命令は、例えば、第１の周期Ｒ１、第２の周期Ｒ２及び第３の周期Ｒ３を有する。第１の周期Ｒ１では、条件成立Ｔが３回連続し、その後に、条件不成立Ｎが２回連続する。これに対し、第２の周期Ｒ２では、条件成立Ｔが２回連続し、その後に、条件不成立Ｎが２回連続する。第１の周期Ｒ１及び第２の周期Ｒ２は異なるので、分岐予測失敗として、分岐予測を行わない。その後、第３の周期Ｒ３では、条件成立Ｔが２回連続し、その後に、条件不成立Ｎが２回連続する。第２の周期Ｒ２及び第３の周期Ｒ３は同じであるので、条件分岐命令は、以後、第２の周期Ｒ２及び第３の周期Ｒ３で条件成立又は条件不成立になることを予測可能である。すなわち、条件成立Ｔが２回連続し、その後に、条件不成立Ｎが２回連続することが予測可能である。
【００３８】
ローカルパターンテーブル３０３は、命令フェッチと並行して、命令フェッチアドレスFIAR[31:0]を入力すると、それに対応する条件成立連続回数確度ビットTHTC-PRD、条件不成立連続回数確度ビットTHNC-PRD、１周期条件成立連続回数THT-CNT[5:0]、１周期条件不成立連続回数THN-CNT[5:0]、現在予測連続回数PRD-CNT[5:0]及び現在予測条件成立ビットPRD-CNT-TKNを出力する。
【００３９】
論理積回路３１１は、条件成立連続回数確度ビットTHTC-PRDと条件不成立連続回数確度ビットTHNC-PRDとの論理積を出力する。条件成立連続回数確度ビットTHTC-PRDと条件不成立連続回数確度ビットTHNC-PRDが共に１である場合には、分岐成立Ｔの連続回数及び分岐不成立Ｎの連続回数の周期が過去に２周期以上現れた場合を意味するので、論理積回路３１１は１を出力し、ローカルパターンテーブル３０３による分岐予測をパターン履歴テーブル３０２による分岐予測より優先させる。
【００４０】
論理積回路３１３は、排他的論理和回路３１０の出力値と論理積回路３１１の出力値の論理反転値との論理積を出力する。論理積回路３１１の出力値が１の場合には、パターン履歴テーブル３０２による分岐予測を無効にするため、論理積回路３１３は０を出力する。論理積回路３１１の出力値が０の場合には、パターン履歴テーブル３０２による分岐予測を有効にするため、論理積回路３１３の出力値は排他的論理和回路３１０の出力値と同じになる。
【００４１】
生成部３１２は、１周期条件成立連続回数THT-CNT[5:0]、１周期条件不成立連続回数THN-CNT[5:0]、現在予測連続回数PRD-CNT[5:0]及び現在予測条件成立ビットPRD-CNT-TKNを入力し、分岐予測情報LPT-TKNを出力する。
【００４２】
図７は、図３の生成部３１２の構成例を示す図である。比較器７０１は、現在予測連続回数PRD-CNT[5:0]が１周期条件成立連続回数THT-CNT[5:0]より小さい場合には１を出力し、現在予測連続回数PRD-CNT[5:0]が１周期条件成立連続回数THT-CNT[5:0]以上である場合には０を出力する。比較器７０２は、現在予測連続回数PRD-CNT[5:0]が１周期条件不成立連続回数THN-CNT[5:0]と同じである場合には１を出力し、現在予測連続回数PRD-CNT[5:0]が１周期条件不成立連続回数THN-CNT[5:0]と同じでない場合には０を出力する。論理積回路７０３は、現在予測条件成立ビットPRD-CNT-TKNと比較器７０１の出力値との論理積を出力する。論理積回路７０４は、現在予測条件成立ビットPRD-CNT-TKNの論理反転値と比較器７０２の出力値との論理積を出力する。論理和回路７０５は、論理積回路７０３の出力値と論理積回路７０４の出力値との論理和を分岐予測情報LPT-TKNとして出力する。以上のように、生成部３１２は、図６（Ａ）に示すように、１周期条件成立連続回数THT-CNT[5:0]、１周期条件不成立連続回数THN-CNT[5:0]、現在予測連続回数PRD-CNT[5:0]及び現在予測条件成立ビットPRD-CNT-TKNを基に、次の条件分岐命令の分岐予測情報LPT-TKNを出力することができる。分岐予測情報LPT-TKNは、０が条件不成立を示し、１が条件成立を示す。
【００４３】
例えば、現在予測条件成立ビットPRD-CNT-TKNが１であり、かつ現在予測連続回数PRD-CNT[5:0]が１周期条件成立連続回数THT-CNT[5:0]よりも小さい場合、次の分岐方向は条件成立Ｔであることを予測するため、分岐予測情報LPT-TKNが１になる。この場合、現在予測連続回数PRD-CNT[5:0]は、インクリメントされる。
【００４４】
また、現在予測条件成立ビットPRD-CNT-TKNが１であり、かつ現在予測連続回数PRD-CNT[5:0]が１周期条件成立連続回数THT-CNT[5:0]と同じである場合、分岐方向は分岐不成立Ｎに切り替わるので、分岐予測情報LPT-TKNが０になり、条件不成立Ｎと予測する。この場合、現在予測連続回数PRD-CNT[5:0]は「１」に初期化され、現在予測条件成立ビットPRD-CNT-TKNは「１」に設定される。
【００４５】
また、現在予測条件成立ビットPRD-CNT-TKNが０であり、かつ現在予測連続回数PRD-CNT[5:0]が１周期条件不成立連続回数THN-CNT[5:0]よりも小さい場合、次の分岐方向は条件不成立Ｎであると予測するため、分岐予測情報LPT-TKNは０になる。この場合、現在予測連続回数PRD-CNT[5:0]は、インクリメントされる。
【００４６】
また、現在予測条件成立ビットPRD-CNT-TKNが０であり、かつ現在予測連続回数PRD-CNT[5:0]が１周期条件不成立連続回数THN-CNT[5:0]と同じ場合、分岐方向は分岐成立Ｔに切り替わるので、分岐予測情報LPT-TKNは１になり、分岐成立Ｔと予測する。この場合、現在予測連続回数PRD-CNT[5:0]は「１」に初期化され、現在予測条件成立ビットPRD-CNT-TKNは「１」に設定される。
【００４７】
図３の論理積回路３１４は、論理積回路３１１の出力値と分岐予測情報LPT-TKNとの論理積を出力する。論理積回路３１１の出力値が０の場合には、ローカルパターンテーブル３０３による分岐予測を無効にするため、論理積回路３１４は０を出力する。論理積回路３１１の出力値が１の場合には、ローカルパターンテーブル３０３による分岐予測を有効にするため、論理積回路３１４の出力値は分岐予測情報LPT-TKNと同じになる。論理和回路３１５は、論理積回路３１３の出力値と論理積回路３１４の出力値との論理和を出力する。論理積回路３１１の出力値が１の場合には、論理和回路３１５は、ローカルパターンテーブル３０３による分岐予測情報LPT-TKNを出力する。また、論理積回路３１１の出力値が０の場合には、論理和回路３１５は、排他的論理和回路３１０の出力値（パターン履歴テーブル３０２による分岐予測情報）を出力する。すなわち、論理積回路３１１の出力値が１の場合には、ローカルパターンテーブル３０３による分岐予測情報が選択され、論理積回路３１１の出力値が０の場合には、パターン履歴テーブル３０２による分岐予測情報が選択される。
【００４８】
命令フェッチアドレスFIAR[31:0]の命令が条件分岐命令である場合、分岐予測情報PREDICT-TAKENは、論理和回路３１５の出力値と同じ値になる。セレクタ３０５は、上記のように、分岐予測情報PREDICT-TAKENに応じて、次の命令フェッチアドレスNEXT‐FIAR[31:0]を選択する。
【００４９】
排他的論理和回路３１６は、排他的論理和回路３１０の出力値と分岐予測情報LPT-TKNとの排他的論理和を出力する。論理積回路３１７は、排他的論理和回路３１６の出力値と論理積回路３１１の出力値との論理積を予測不一致ビットPRD-BY-LPTとして出力する。予測不一致ビットPRD-BY-LPTは、排他的論理和回路３１０の出力値（パターン履歴テーブル３０２による分岐予測情報）ではなく、ローカルパターンテーブル３０３による分岐予測情報LPT-TKNが選択され、かつ排他的論理和回路３１０の出力値（パターン履歴テーブル３０２による分岐予測情報）とローカルパターンテーブル３０３による分岐予測情報LPT-TKNとが異なる場合に「１」になる。予測不一致ビットPRD-BY-LPTが１の状態で、分岐命令完了後に分岐予測の失敗が判明すると、後述のように、ローカルパターンテーブル３０３の無効化処理が行われる。
【００５０】
図８は、上記の演算処理装置の制御方法を示すフローチャートである。ステップＳ８０１では、分岐予測部２２は、分岐履歴テーブルヒットビットBRHIS-HITが１であるか否かをチェックする。分岐履歴テーブルヒットビットBRHIS-HITが１である場合には、フェッチした命令が分岐命令であるので、ステップＳ８０２へ進む。分岐履歴テーブルヒットビットBRHIS-HITが０である場合には、フェッチした命令が分岐命令でないので、ステップＳ８２１へ進む。
【００５１】
ステップＳ８２１では、分岐予測部２２は、フェッチした命令が分岐命令でないと予測する。次に、ステップＳ８２２では、分岐予測部２２は、分岐不成立と予測し、分岐予測情報PREDICT-TAKENが０になる。次に、ステップＳ８２３では、セレクタ３０５は、前回命令フェッチしたアドレスと連続した値を次の命令フェッチアドレスNEXT‐FIAR[31:0]として設定する。
【００５２】
ステップＳ８０２では、分岐予測部２２は、条件分岐命令ビットP-COND-BITが１であるか否かをチェックする。条件分岐命令ビットP-COND-BITが１である場合には、フェッチした命令が条件分岐命令であるので、ステップＳ８０３へ進む。条件分岐命令ビットP-COND-BITが０である場合には、フェッチした命令が無条件分岐命令であるので、ステップＳ８１８へ進む。
【００５３】
ステップＳ８１８では、分岐予測部２２は、フェッチした命令が無条件分岐命令であると予測する。次に、ステップＳ８１９では、分岐予測部２２は、分岐成立と予測し、分岐予測情報PREDICT-TAKENが１になる。次に、ステップＳ８２０では、セレクタ３０５は、分岐履歴テーブル（BRHIS）３０１に登録された分岐先アドレスPTIAR[31:0]を次の命令フェッチアドレスNEXT‐FIAR[31:0]として設定する。
【００５４】
ステップＳ８０３では、分岐予測部２２は、条件成立連続回数確度ビットTHTC-PRDが１であり、かつ条件不成立連続回数確度ビットTHNC-PRDが１であるか否かをチェックする。条件成立連続回数確度ビットTHTC-PRD及び条件不成立連続回数確度ビットTHNC-PRDが共に１である場合には、ローカルパターンテーブル（LPT）３０３を用いて分岐予測を行うため、ステップＳ８０４へ進む。条件成立連続回数確度ビットTHTC-PRD及び条件不成立連続回数確度ビットTHNC-PRDが共に１でない場合には、パターン履歴テーブル（PHT）３０２を用いて分岐予測を行うため、ステップＳ８１１へ進む。
【００５５】
ステップＳ８１１では、分岐予測部２２は、条件成立期待値BRHIS-EXPECT-BITが１であるか否かをチェックする。条件成立期待値BRHIS-EXPECT-BITが１である場合にはステップＳ８１２へ進み、条件成立期待値BRHIS-EXPECT-BITが０である場合にはステップＳ８１５へ進む。
【００５６】
ステップＳ８１２では、分岐予測部２２は、分岐成立確度情報BP1[1]が１であるか否かをチェックする。分岐成立確度情報BP1[1]が１である場合にはステップＳ８１３へ進み、分岐成立確度情報BP1[1]が０である場合にはステップＳ８１４へ進む。ステップＳ８１３では、分岐予測部２２は、分岐不成立と予測し、分岐予測情報PREDICT-TAKENが０になり、ステップＳ８２３に進む。ステップＳ８１４では、分岐予測部２２は、分岐成立と予測し、分岐予測情報PREDICT-TAKENが１になり、ステップＳ８２０に進む。
【００５７】
ステップＳ８１５では、分岐予測部２２は、分岐成立確度情報BP1[1]が１であるか否かをチェックする。分岐成立確度情報BP1[1]が１である場合にはステップＳ８１６へ進み、分岐成立確度情報BP1[1]が０である場合にはステップＳ８１７へ進む。ステップＳ８１６では、分岐予測部２２は、分岐成立と予測し、分岐予測情報PREDICT-TAKENが１になり、ステップＳ８２０に進む。ステップＳ８１７では、分岐予測部２２は、分岐不成立と予測し、分岐予測情報PREDICT-TAKENが０になり、ステップＳ８２３に進む。
【００５８】
ステップＳ８０４では、分岐予測部２２は、現在予測条件成立ビットPRD-CNT-TKNが１であるか否かをチェックする。現在予測条件成立ビットPRD-CNT-TKNが１である場合にはステップＳ８０５へ進み、現在予測条件成立ビットPRD-CNT-TKNが０である場合にはステップＳ８０８へ進む。
【００５９】
ステップＳ８０５では、分岐予測部２２は、現在予測連続回数PRD-CNT[5:0]が１周期条件成立連続回数THT-CNT[5:0]より小さいか否かをチェックする。現在予測連続回数PRD-CNT[5:0]が１周期条件成立連続回数THT-CNT[5:0]より小さい場合にはステップＳ８０６へ進み、現在予測連続回数PRD-CNT[5:0]が１周期条件成立連続回数THT-CNT[5:0]より小さくない場合にはステップＳ８０７へ進む。ステップＳ８０６では、分岐予測部２２は、分岐成立と予測し、分岐予測情報PREDICT-TAKENが１になり、ステップＳ８２０に進む。ステップＳ８０７では、分岐予測部２２は、分岐不成立と予測し、分岐予測情報PREDICT-TAKENが０になり、ステップＳ８２３に進む。
【００６０】
ステップＳ８０８では、分岐予測部２２は、現在予測連続回数PRD-CNT[5:0]が１周期条件不成立連続回数THN-CNT[5:0]と同じであるか否かをチェックする。現在予測連続回数PRD-CNT[5:0]が１周期条件不成立連続回数THN-CNT[5:0]と同じある場合にはステップＳ８０９へ進み、現在予測連続回数PRD-CNT[5:0]が１周期条件不成立連続回数THN-CNT[5:0]と同じでない場合にはステップＳ８１０へ進む。ステップＳ８０９では、分岐予測部２２は、分岐成立と予測し、分岐予測情報PREDICT-TAKENが１になり、ステップＳ８２０に進む。ステップＳ８１０では、分岐予測部２２は、分岐不成立と予測し、分岐予測情報PREDICT-TAKENが０になり、ステップＳ８２３に進む。
【００６１】
ステップＳ８２０では、セレクタ３０５は、分岐履歴テーブル（BRHIS）３０１に登録された分岐先アドレスPTIAR[31:0]を次の命令フェッチアドレスNEXT‐FIAR[31:0]として設定する。ステップＳ８２３では、セレクタ３０５は、前回命令フェッチしたアドレスと連続した値を次の命令フェッチアドレスNEXT‐FIAR[31:0]として設定する。
【００６２】
図９は、図２の分岐履歴更新部３３の入出力信号を示す図である。分岐履歴更新部３３は、図２の分岐制御部３０による分岐演算の結果を基に、分岐履歴テーブル（BRHIS）３０１、パターン履歴テーブル（PHT）３０２及びローカルパターンテーブル（LPT）３０３の更新を行う。分岐履歴更新部３３は、図２の分岐制御部３０から、確定分岐先アドレスRTIAR[31:0]、分岐命令アドレス（Branch Instruction AddRess）BIAR[31:0]、分岐命令完了ビットCOMPLETE、分岐成立確定ビットRESULT-TAKEN、条件分岐命令確定ビットD-COND-BIT、上記の現在完了条件成立ビットCMP-CNT-TKN、上記の現在完了連続回数CMP-CNT[5:0]、上記の１周期条件成立連続回数THT-CNT[5:0]、上記の条件成立変化ビットTHTC-DEF、上記の１周期条件不成立連続回数THN-CNT[5:0]、上記の条件不成立変化ビットTHNC-DEF、分岐予測失敗ビットPRD-MISS、上記の有効フラグLPT-VALID、ＬＰＴ無効ビットDISABLE-LPT、上記の予測失敗ビットLPT-DIZZY、上記の予測不一致ビットPRD-BY-LPTを入力する。なお、ＬＰＴ無効ビットDISABLE-LPT及び予測不一致ビットPRD-BY-LPTは、分岐予測時に作成され、パイプラインを伝搬する信号である。
【００６３】
確定分岐先アドレスRTIAR[31:0]は、分岐命令の演算完了により得られる分岐先アドレスである。分岐命令完了ビットCOMPLETEは、１が分岐命令の演算完了を示し、０が分岐命令の演算未完了を示す。分岐成立確定ビットRESULT-TAKENは、１が条件分岐成立の確定を示し、０が条件分岐不成立の確定を示す。条件分岐命令確定ビットD-COND-BITは、１である場合にフェッチ及びデコードした命令が条件分岐命令であることが確定したことを示し、０である場合にフェッチ及びデコードした命令が条件分岐命令でないことが確定したことを示す。分岐予測失敗ビットPRD-MISSは、１が分岐予測部２２による分岐予測の失敗を示し、０が分岐予測部２２による分岐予測の成功を示す。ＬＰＴ無効ビットDISABLE-LPTは、１がローカルパターンテーブル（LPT）３０３の無効を示し、０がローカルパターンテーブル（LPT）３０３の有効を示す。
【００６４】
分岐命令アドレスBIAR[31:0]は、分岐履歴テーブル（BRHIS）３０１及びローカルパターンテーブル（LPT）３０３に入力される。分岐予測失敗ビットPRD-MISSは、イネーブル信号ENとして、分岐履歴テーブル（BRHIS）３０１に入力される。論理積回路９０１は、分岐命令完了ビットCOMPLETE及び条件分岐命令確定ビットD-COND-BITの論理積をイネーブル信号ENとしてローカルパターンテーブル（LPT）３０３に出力する。
【００６５】
図１０は、図９の分岐履歴更新部３３の一部の構成例を示す図である。論理積回路１００１は、分岐命令完了ビットCOMPLETE及び条件分岐命令確定ビットD-COND-BITの論理積信号を出力する。論理積回路１００３は、論理積回路１００１の出力信号及び分岐成立確定ビットRESULT-TAKENの論理積信号を現在完了条件成立ビットS-CMP-CNT-TKNとしてローカルパターンテーブル（LPT）３０３に出力する。現在完了条件成立ビットS-CMP-CNT-TKNは、図４（Ｃ）の現在完了条件成立ビットCMP-CNT-TKNに対応する。
【００６６】
否定排他的論理和回路１００２は、分岐成立確定ビットRESULT-TAKEN及び現在完了条件成立ビットCMP-CNT-TKNの否定排他的論理和信号を出力する。論理積回路１００４は、論理積回路１００１の出力信号と分岐成立確定ビットRESULT-TAKENの論理反転信号と現在完了条件成立ビットCMP-CNT-TKNと有効フラグLPT-VALIDとの論理積信号を出力する。論理積回路１００５は、論理積回路１００１の出力信号と分岐成立確定ビットRESULT-TAKENと現在完了条件成立ビットCMP-CNT-TKNの論理反転信号と有効フラグLPT-VALIDとの論理積信号を出力する。加算器１００６は、現在完了連続回数CMP-CNT[5:0]の値をインクリメントして出力する。
【００６７】
論理積回路１００７は、否定排他的論理和回路１００２の出力信号の論理反転信号と「１」との論理積信号を出力する。論理積回路１００８は、否定排他的論理和回路１００２の出力信号と加算器１００６の出力信号との論理積信号を出力する。論理和回路１００９は、論理積回路１００７及び１００８の出力信号の論理和信号を現在完了連続回数S-CMP-CNT[5:0]としてローカルパターンテーブル（LPT）３０３に出力する。現在完了連続回数S-CMP-CNT[5:0]は、図４（Ｃ）の現在完了連続回数CMP-CNT[5:0]に対応する。
【００６８】
論理積回路１０１１は、論理積回路１００４の出力信号と条件成立変化ビットTHTC-DEFの論理反転信号との論理積信号を条件成立変化ビットS-THTC-DEFとしてローカルパターンテーブル（LPT）３０３に出力する。条件成立変化ビットS-THTC-DEFは、図４（Ｃ）の条件成立変化ビットTHTC-DEFに対応する。
【００６９】
ラッチ回路１０１３は、条件成立変化ビットS-THTC-DEFをイネーブル信号ENとして、加算器１００６が出力する現在完了連続回数CMP-CNT[5:0]をラッチし、１周期条件成立連続回数S-THT-CNT[5:0]としてローカルパターンテーブル（LPT）３０３に出力する。１周期条件成立連続回数S-THT-CNT[5:0]は、図４（Ｃ）の１周期条件成立連続回数THT-CNT[5:0]に対応する。
【００７０】
比較器１０１０は、現在完了連続回数CMP-CNT[5:0]と１周期条件成立連続回数THT-CNT[5:0]が同じ場合には「１」を出力し、異なる場合には「０」を出力する。論理積回路１０１２は、比較器１０１０の出力信号と論理積回路１００４の出力信号と条件成立変化ビットTHTC-DEFとの論理積信号を条件成立連続回数確度ビットS-THTC-PRDとしてローカルパターンテーブル（LPT）３０３に出力する。条件成立連続回数確度ビットS-THTC-PRDは、図４（Ｃ）の条件成立連続回数確度ビットTHTC-PRDに対応する。
【００７１】
論理積回路１０１６は、論理積回路１００５の出力信号と条件不成立変化ビットTHNC-DEFの論理反転信号との論理積信号を条件不成立変化ビットS-THNC-DEFとしてローカルパターンテーブル（LPT）３０３に出力する。条件不成立変化ビットS-THNC-DEFは、図４（Ｃ）の条件不成立変化ビットTHNC-DEFに対応する。
【００７２】
ラッチ回路１０１４は、条件不成立変化ビットS-THNC-DEFをイネーブル信号ENとして、加算器１００６が出力する現在完了連続回数CMP-CNT[5:0]をラッチし、１周期条件不成立連続回数S-THN-CNT[5:0]としてローカルパターンテーブル（LPT）３０３に出力する。１周期条件不成立連続回数S-THN-CNT[5:0]は、図４（Ｃ）の１周期条件不成立連続回数THN-CNT[5:0]に対応する。
【００７３】
比較器１０１５は、現在完了連続回数CMP-CNT[5:0]と１周期条件不成立連続回数THN-CNT[5:0]が同じ場合には「１」を出力し、異なる場合には「０」を出力する。論理積回路１０１７は、比較器１０１５の出力信号と論理積回路１００５の出力信号と条件不成立変化ビットTHNC-DEFとの論理積信号を条件不成立連続回数確度ビットS-THNC-PRDとしてローカルパターンテーブル（LPT）３０３に出力する。条件不成立連続回数確度ビットS-THNC-PRDは、図４（Ｃ）の条件不成立連続回数確度ビットTHNC-PRDに対応する。
【００７４】
以上のように、分岐成立確定ビットRESULT-TAKEN＝１は条件分岐成立を示し、分岐成立確定ビットRESULT-TAKEN＝０は条件分岐不成立を示す。RESULT-TAKEN＝１の場合、エントリにヒットした分岐命令が分岐成立／不成立の完了した回数をCMP-CNT[5:0]としてカウントし、S-CMP-CNT-TKNに「１」をセットする。不成立から成立に変化してなければ、CMP-CNT[5:0]に「１」を加えて、S-CMP-CNT[5:0]をカウントアップする。不成立から成立に変化している場合は、S-CMP-CNT[5:0]に「１」をセットして初期化を行う。THNC-DEFが「０」であったら、S-THNC-DEFに「１」にセットすると共に、CMP-CNT[5:0]の値をS-THN-CNT[5:0]にセットする。THNC-DEFが「１」であったら、CMP-CNT[5:0]の値とTHN-CNT[5:0]とを比較し、同一の値であったら、すなわち連続して値が同一であったら分岐予測可能な状態となり、S-THNC-PRDに「１」をセットする。
【００７５】
同様に、RESULT-TAKENが「０」の場合、CMP-CNT-TKNに「０」をセットする。成立から不成立に変化してなければ、CMP-CNT[5:0]に「１」を加えて、CMP-CNT[5:0]をカウントアップする。成立から不成立に変化している場合は、CMP-CNT[5:0]に「１」をセットして初期化を行う。THTC-DEFが「０」であったら、S-THTC-DEFに「１」をセットすると共に、CMP-CNT[5:0]の値をS-THT-CNT[5:0]にセットする。THTC-DEFが「１」であったら、CMP-CNT[5:0]の値とTHT-CNT[5:0]とを比較し、同一の値であったら、すなわち連続して値が同一であったら、分岐予測可能な状態となり、S-THTC-PRDに「１」をセットする。S-THTC-PRDとS-TDNC-PRDが共に「１」となると、ローカルパターンテーブル（LPT）３０３による分岐予測が選択される。
【００７６】
図１１は、図１０の回路の処理を示すフローチャートである。ステップＳ１１０１では、分岐履歴更新部３３は、分岐命令完了ビットCOMPLETEが１であるか否かをチェックする。分岐命令完了ビットCOMPLETEが１である場合には、分岐演算が完了しているので、ステップＳ１１０２へ進む。分岐命令完了ビットCOMPLETEが０である場合には、分岐演算が完了していないので、ステップＳ１１２１へ進む。ステップＳ１１２１では、分岐履歴更新部３３は、ローカルパターンテーブル（LPT）３０３の更新を行わない。
【００７７】
ステップＳ１１０２では、分岐履歴更新部３３は、条件分岐命令確定ビットD-COND-BITが１であるか否かをチェックする。条件分岐命令確定ビットD-COND-BITが１である場合、対象命令が条件分岐命令であることを示すので、ステップＳ１１０３へ進む。条件分岐命令確定ビットD-COND-BITが０である場合、対象命令が条件分岐命令でないことを示すので、ステップＳ１１２１へ進む。
【００７８】
ステップＳ１１０３では、分岐履歴更新部３３は、ローカルパターンテーブル（LPT）３０３のエントリを作成する。この処理の詳細は、後に図１３を参照しながら説明する。
【００７９】
次に、ステップＳ１１０４では、分岐履歴更新部３３は、分岐成立確定ビットRESULT-TAKENが１であるか否かをチェックする。分岐成立確定ビットRESULT-TAKENが１である場合、条件分岐成立であるので、ステップＳ１１０５へ進む。分岐成立確定ビットRESULT-TAKENが０である場合、条件分岐不成立であるので、ステップＳ１１１３へ進む。
【００８０】
ステップＳ１１０５では、分岐履歴更新部３３は、現在完了条件成立ビットS-CMP-CNT-TKNに「１」を設定する。
【００８１】
次に、ステップＳ１１０６では、分岐履歴更新部３３は、現在完了条件成立ビットCMP-CNT-TKNが０であるか否かをチェックする。現在完了条件成立ビットCMP-CNT-TKNが０である場合、条件分岐不成立から成立に変化したことを意味するので、ステップＳ１１０７へ進む。現在完了条件成立ビットCMP-CNT-TKNが１である場合、条件分岐不成立から成立に変化していないことを意味するので、ステップＳ１１１２へ進む。ステップＳ１１１２では、分岐履歴更新部３３は、現在完了連続回数CMP-CNT[5:0]＋１を現在完了連続回数S-CMP-CNT[5:0]に設定する。
【００８２】
ステップＳ１１０７では、分岐履歴更新部３３は、現在完了連続回数S-CMP-CNT[5:0]に「１」を設定する。
【００８３】
次に、ステップＳ１１０８では、分岐履歴更新部３３は、条件不成立変化ビットTHNC-DEFが１であるか否かをチェックする。条件不成立変化ビットTHNC-DEFが１である場合、条件分岐不成立から条件分岐成立に変化したことを意味するので、ステップＳ１１０９へ進む。条件不成立変化ビットTHNC-DEFが０である場合、条件分岐不成立から条件分岐成立に変化していないことを意味するので、ステップＳ１１１１へ進む。
【００８４】
ステップＳ１１１１では、分岐履歴更新部３３は、条件不成立変化ビットS-THNC-DEFに「１」を設定し、現在完了連続回数CMP-CNT[5:0]を１周期条件不成立連続回数S-THN-CNT[5:0]に設定する。
【００８５】
ステップＳ１１０９では、分岐履歴更新部３３は、現在完了連続回数CMP-CNT[5:0]と１周期条件不成立連続回数THN-CNT[5:0]が同じであるか否かをチェックする。両者が同じである場合にはステップＳ１１１０へ進み、両者が異なる場合には処理を終了する。ステップＳ１１１０では、分岐履歴更新部３３は、条件不成立連続回数確度ビットS-THNC-PRDに「１」を設定する。
【００８６】
ステップＳ１１１３では、分岐履歴更新部３３は、現在完了条件成立ビットS-CMP-CNT-TKNに「０」を設定する。
【００８７】
次に、ステップＳ１１１４では、分岐履歴更新部３３は、現在完了条件成立ビットCMP-CNT-TKNが１であるか否かをチェックする。現在完了条件成立ビットCMP-CNT-TKNが１である場合、条件分岐成立から不成立に変化したことを意味するので、ステップＳ１１１５へ進む。現在完了条件成立ビットCMP-CNT-TKNが０である場合、条件分岐成立から不成立に変化していないことを意味するので、ステップＳ１１２０へ進む。ステップＳ１１２０では、分岐履歴更新部３３は、現在完了連続回数CMP-CNT[5:0]＋１を現在完了連続回数S-CMP-CNT[5:0]に設定する。
【００８８】
ステップＳ１１１５では、分岐履歴更新部３３は、現在完了連続回数S-CMP-CNT[5:0]に「１」を設定する。
【００８９】
次に、ステップＳ１１１６では、分岐履歴更新部３３は、条件成立変化ビットTHTC-DEFが１であるか否かをチェックする。条件成立変化ビットTHTC-DEFが１である場合、条件分岐成立から条件分岐不成立に変化したことを意味するので、ステップＳ１１１７へ進む。条件成立変化ビットTHTC-DEFが０である場合、条件分岐成立から条件分岐不成立に変化していないことを意味するので、ステップＳ１１１９へ進む。
【００９０】
ステップＳ１１１９では、分岐履歴更新部３３は、条件成立変化ビットS-THTC-DEFに「１」を設定し、現在完了連続回数CMP-CNT[5:0]を１周期条件成立連続回数S-THT-CNT[5:0]に設定する。
【００９１】
ステップＳ１１１７では、分岐履歴更新部３３は、現在完了連続回数CMP-CNT[5:0]と１周期条件成立連続回数THT-CNT[5:0]が同じであるか否かをチェックする。両者が同じである場合にはステップＳ１１１８へ進み、両者が異なる場合には処理を終了する。ステップＳ１１１８では、分岐履歴更新部３３は、条件成立連続回数確度ビットS-THTC-PRDに「１」を設定する。
【００９２】
図１２は、図９の分岐履歴更新部３３の一部の構成例を示す図である。論理積回路１２００は、分岐命令完了ビットCOMPLETE及び条件分岐命令確定ビットD-COND-BITの論理積信号を出力する。論理積回路１２０１は、論理積回路１２００の出力信号と分岐予測失敗ビットPRD-MISSと有効フラグLPT-VALIDの論理反転ビットとＬＰＴ無効ビットDISABLE-LPTの論理反転ビットとの論理積信号を出力する。論理積回路１２０２は、論理積回路１２００の出力信号と有効フラグLPT-VALIDとＬＰＴ無効ビットS-DISABLE-LPTの論理反転ビットとの論理積信号を出力する。論理和回路１２０３は、論理積回路１２０１及び１２０２の出力信号の論理和信号を有効フラグS-LPT-VALIDとしてローカルパターンテーブル（LPT）３０３に出力する。有効フラグS-LPT-VALIDは、図４（Ｃ）の有効フラグLPT-VALIDに対応する。
【００９３】
論理積回路１２０４は、論理積回路１２００の出力信号と有効フラグLPT-VALIDと分岐予測失敗ビットPRD-MISSと予測不一致ビットPRD-BY-LPTと予測失敗ビットLPT-DIZZYの論理反転ビットとの論理積信号を出力する。否定論理積（ＮＡＮＤ）回路１２０５は、論理積回路１２００の出力信号と有効フラグLPT-VALIDと予測不一致ビットPRD-BY-LPTと分岐予測失敗ビットPRD-MISSの論理反転ビットとの否定論理積信号を出力する。論理積回路１２０６は、否定論理積回路１２０５の出力信号と予測失敗ビットLPT-DIZZYとの論理積信号を出力する。論理和回路１２０７は、論理積回路１２０４及び１２０６の出力信号の論理和信号を予測失敗ビットS-LPT-DIZZYとしてローカルパターンテーブル（LPT）３０３に出力する。予測失敗ビットS-LPT-DIZZYは、図４（Ｃ）の予測失敗ビットLPT-DIZZYに対応する。
【００９４】
論理積回路１２０８は、論理積回路１２００の出力信号と有効フラグLPT-VALIDと分岐予測失敗ビットPRD-MISSと予測不一致ビットPRD-BY-LPTと予測失敗ビットLPT-DIZZYとの論理積信号を出力する。論理和回路１２０９は、論理積回路１２０８の出力信号とＬＰＴ無効ビットDISABLE-LPTとの論理和信号をＬＰＴ無効ビットS-DISABLE-LPTとして分岐履歴テーブル（BRHIS）３０１に出力する。ＬＰＴ無効ビットS-DISABLE-LPTは、ＬＰＴ無効ビットDISABLE-LPTに対応する。
【００９５】
以上のように、ローカルパターンテーブル（LPT）３０３は、分岐命令完了ビットCOMPLETEが１であり、かつ条件分岐命令確定ビットD-COND-BITが１であった場合、有効フラグLPT-VALIDが０であり、かつＬＰＴ無効ビットDISABLE-LPTが０であり、分岐予測失敗ビットPRD-MISSが１（分岐予測失敗）である場合に、有効フラグS-LPT-VALIDに「１」を設定する。これにより、ローカルパターンテーブル（LPT）３０３のエントリが有効になる。
【００９６】
図１３は、図１２の回路の処理を示すフローチャートである。ステップＳ１３０１では、分岐履歴更新部３３は、分岐予測失敗ビットPRD-MISSが１であるか否かをチェックする。分岐予測失敗ビットPRD-MISSが１の場合、分岐予測失敗を意味するので、ステップＳ１３０２へ進む。分岐予測失敗ビットPRD-MISSが０の場合、分岐予測成功を意味するので、処理を終了する。
【００９７】
ステップＳ１３０２では、分岐履歴更新部３３は、有効フラグLPT-VALIDが１であるか否かをチェックする。有効フラグLPT-VALIDが１の場合、ローカルパターンテーブル（LPT）３０３のエントリは有効であるので、ステップＳ１３０３へ進む。有効フラグLPT-VALIDが０の場合、ローカルパターンテーブル（LPT）３０３のエントリは無効であるので、ステップＳ１３１０へ進む。
【００９８】
ステップＳ１３０３では、分岐履歴更新部３３は、予測不一致ビットPRD-BY-LPTが１であるか否かをチェックする。予測不一致ビットPRD-BY-LPTの１である場合、パターン履歴テーブル（PHT）３０２による予測結果とローカルパターンテーブル（LPT）３０３による予測結果が異なることを意味するので、ステップＳ１３０４へ進む。予測不一致ビットPRD-BY-LPTの０である場合、パターン履歴テーブル（PHT）３０２による予測結果とローカルパターンテーブル（LPT）３０３による予測結果が同じであることを意味するので、処理を終了する。
【００９９】
ステップＳ１３０４では、分岐履歴更新部３３は、予測失敗ビットLPT-DIZZYが１であるか否かをチェックする。予測失敗ビットLPT-DIZZYが１である場合、一つ前に実行したローカルパターンテーブル３０３による分岐予測が失敗したことを意味するので、ステップＳ１３０５へ進む。予測失敗ビットLPT-DIZZYが０である場合、ステップＳ１３０９へ進む。
【０１００】
ステップＳ１３０５では、分岐履歴更新部３３は、分岐予測失敗ビットPRD-MISSが１であるか否かをチェックする。分岐予測失敗ビットPRD-MISSが１の場合、分岐予測失敗を意味するので、ステップＳ１３０６へ進む。分岐予測失敗ビットPRD-MISSが０の場合、分岐予測成功を意味するので、処理を終了する。
【０１０１】
ステップＳ１３０６では、分岐履歴更新部３３は、ＬＰＴ無効ビットDISABLE-LPTが１であるか否かをチェックする。ＬＰＴ無効ビットDISABLE-LPTが１である場合、ローカルパターンテーブル（LPT）３０３の無効を意味するので、ステップＳ１３０７へ進む。ＬＰＴ無効ビットDISABLE-LPTが０である場合、ローカルパターンテーブル（LPT）３０３の有効を意味するので、ステップＳ１３０８へ進む。
【０１０２】
ステップＳ１３０７では、分岐履歴更新部３３は、ローカルパターンテーブル（LPT）３０３のエントリを無効化する。
【０１０３】
ステップＳ１３０８では、分岐履歴更新部３３は、ＬＰＴ無効ビットS-DISABLE-LPTに「１」を設定し、ローカルパターンテーブル（LPT）３０３のエントリを無効化する。
【０１０４】
ステップＳ１３０９では、分岐履歴更新部３３は、予測失敗ビットS-LPT-DIZZYに「１」を設定する。
【０１０５】
ステップＳ１３１０では、分岐履歴更新部３３は、ＬＰＴ無効ビットDISABLE-LPTが１であるか否かをチェックする。ＬＰＴ無効ビットDISABLE-LPTが１である場合、ローカルパターンテーブル（LPT）３０３の無効を意味するので、処理を終了する。ＬＰＴ無効ビットDISABLE-LPTが０である場合、ローカルパターンテーブル（LPT）３０３の有効を意味するので、ステップＳ１３１１へ進む。
【０１０６】
ステップＳ１３１１では、分岐履歴更新部３３は、有効フラグS-LPT-VALIDに「１」を設定する。
【０１０７】
以上のように、条件分岐の成立／不成立の連続回数が安定しないような分岐命令をローカルパターンテーブル（LPT）３０３により分岐予測すると、分岐予測性能が低下することが懸念される。そのような危険性を回避するために、ローカルパターンテーブル（LPT）３０３による分岐予測を無効化することにより、ローカルパターンテーブル（LPT）３０３に適さない分岐命令に対しては、パターン履歴テーブル（PHT）３０２による分岐予測を行う。
【０１０８】
このような構成にすることにより、パターン履歴テーブル（PHT）３０２の登録処理が終了するまでは、パターン履歴テーブル（PHT）３０２による分岐予測を行えないので、その間は、ローカルパターンテーブル（LPT）３０３による分岐予測を行う。これにより、分岐予測の精度を向上させることができる。ローカルパターンテーブル（LPT）３０３は、条件分岐の成立／不成立の連続回数の基づく分岐予測であるため、パターン履歴テーブル（PHT）３０２に比べ、早期に登録を完了させ、早期に分岐予測可能になる。
【０１０９】
パターン履歴テーブル（PHT）３０２を含む第１の予測部３１０は、条件分岐命令の過去の分岐履歴パターンを基に、フェッチされた条件分岐命令の分岐予測情報を出力する。ローカルパターンテーブル（LPT）３０３を含む第２の予測部３１２は、条件分岐命令の分岐成立連続回数及び分岐不成立連続回数を記憶し、過去の分岐成立連続回数又は分岐不成立連続回数を基に、フェッチされた条件分岐命令の分岐予測情報LPT-TKNを出力する。選択部３１１，３１３〜３１５は、第１の予測部３１０が出力する分岐予測情報又は第２の予測部３１２が出力する分岐予測情報LPT-TKNを選択的に出力する。セレクタ３０５は、選択部３１１，３１３〜３１５により出力された分岐予測情報に応じて、次のアドレス又は分岐先アドレスPTIAR[31:0]を命令フェッチ部２１に出力する。
【０１１０】
選択部３１１は、分岐成立連続回数及び分岐不成立連続回数の周期が過去に２周期以上現れた場合には第２の予測部３１２が出力する分岐予測情報LPT-TKNを出力し、分岐成立連続回数及び分岐不成立連続回数の周期が過去に２周期以上現れていない場合には第１の予測部３１０が出力する分岐予測情報を出力する。
【０１１１】
図１３のステップＳ１３０１では、選択部３１１，３１３〜３１５は、第２の予測部３１２が出力する分岐予測情報LPT-TKNを出力した場合に、第２の予測部３１２が出力する分岐予測情報LPT-TKNによる予測が失敗した場合には、第２の予測部３１２が出力する予測情報を無効化する。
【０１１２】
また、図１３のステップＳ１３０１及びＳ１３０３では、選択部３１１，３１３〜３１５は、第２の予測部３１２が出力する分岐予測情報LPT-TKNを出力した場合に、第１の予測部３１０が出力する分岐予測情報と第２の予測部３１２が出力する分岐予測情報LPT-TKNとが異なっており、かつ第２の予測部３１２が出力する分岐予測情報LPT-TKNによる予測が失敗した場合には、第２の予測部３１２が出力する分岐予測情報LPT-TKNを無効化する。
【０１１３】
なお、上記実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【０１１４】
１１  プロセッサ
２１  命令フェッチ部
２２  分岐予測部
２３  一次命令キャッシュメモリ
２４  命令バッファ
２５  命令デコーダ
２６  命令発行制御部
２８  演算器
２９  一次オペランドキャッシュメモリ
３０  分岐制御部
３１  レジスタ
３２  命令完了制御部
３３  分岐履歴更新部
３４  二次キャッシュメモリ
３５  メモリコントローラ
３０１  分岐履歴テーブル（BRHIS）
３０２  パターン履歴テーブル（PHT）
３０３  ローカルパターンテーブル（LPT）
３０５  セレクタ
３１２  生成部
【図１】
2015036888.tif 000003
【図２】
2015036888.tif 000004
【図３】
2015036888.tif 000005
【図４】
2015036888.tif 000006
【図５】
2015036888.tif 000007
【図６】
2015036888.tif 000008
【図７】
2015036888.tif 000009
【図８】
2015036888.tif 000010
【図９】
2015036888.tif 000011
【図１０】
2015036888.tif 000012
【図１１】
2015036888.tif 000013
【図１２】
2015036888.tif 000014
【図１３】
2015036888.tif 000015