(57)【要約】【課題】分岐履歴長の表示器、分岐予測システム及び分岐予測方法を提供する。【解決手段】ＣＰＵのワーキングレジスタ及びワーキングレジスタの演算結果を参照して分岐する条件分岐命令語の間に存在するレジスタ従属性を記録する分岐レジスタ従属性テーブルを備える分岐履歴長の表示器と、データ従属テーブルを参照して、入力された分岐履歴データのうち分岐予測に実質的に使用される分岐履歴データの長さを決定するフィルタリングを行う分岐履歴フィルタリングユニットと、分岐履歴フィルタリングユニットで、フィルタリングされた分岐履歴データを参照して分岐予測を行う分岐予測ユニット器と、を備える分岐予測器である。これにより、プログラムコードを行いつつ分岐予測に適用される分岐履歴の長さを動的に決定して分岐予測性能を向上させることによって、ＣＰＵの命令語の実行性能を向上させ、テストプログラムコードの種類に関係なく分岐予測性能を最適化させる。【選択図】図１９
2008052684.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つ以上の分岐命令語と、少なくとも一つ以上のワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存する少なくとも一つのエントリを備える分岐レジスタ従属性テーブルと、
前記分岐命令語のうち、任意の分岐命令語が参照するソースレジスタに相応する前記エントリ値を参照して分岐履歴長の表示値を生成する分岐履歴長の表示ユニットと、を備える分岐履歴長の表示器。
【請求項２】
前記分岐レジスタ従属性テーブルは、
前記任意の分岐命令語が参照するソースレジスタ値に変化を与える基本ブロックの情報を保存することを特徴とする請求項１に記載の分岐履歴長の表示器。
【請求項３】
前記基本ブロックは、
実行プログラムコードで、一つの分岐命令語を基準に前記分岐命令語を備えるように分割した命令語グループであることを特徴とする請求項２に記載の分岐履歴長の表示器。
【請求項４】
前記分岐レジスタ従属性テーブルは、
前記ワーキングレジスタのうち、前記分岐命令語が参照するソースレジスタにそれぞれ相応するエントリを有することを特徴とする請求項１に記載の分岐履歴長の表示器。
【請求項５】
前記分岐レジスタ従属性テーブルは、
前記分岐レジスタ従属性テーブルの各カラムビットが実行された基本ブロックと相応することを特徴とする請求項１に記載の分岐履歴長の表示器。
【請求項６】
前記分岐レジスタ従属性テーブルは、
前記実行された基本ブロックのうち、最近に実行された基本ブロックであるほど、ＬＳＢに位置するように配置されたことを特徴とする請求項５に記載の分岐履歴長の表示器。
【請求項７】
前記分岐履歴長の表示ユニットは、
前記分岐レジスタ従属性テーブルのエントリ値を参照して有効分岐履歴データを生成する論理回路と、
前記有効分岐履歴データを保存する長さ表示レジスタと、を備えることを特徴とする請求項１に記載の分岐履歴長の表示器。
【請求項８】
前記有効分岐履歴データは、
入力データのビットのうち、最も上位に位置した‘１’の値を有するビットを基準に、それより高いビットは‘０’になり、残りのビットは‘１’になる変換データであることを特徴とする請求項７に記載の分岐履歴長の表示器。
【請求項９】
分岐命令語と、前記分岐命令語が参照するソースレジスタとの間の関係を示す従属性情報を利用して分岐履歴長の表示値を生成する分岐履歴長の表示器と、
前記分岐履歴長の表示器の出力を参照して分岐履歴データをフィルタリングする分岐履歴フィルタリングユニットと、
前記分岐履歴データを出力し、前記分岐履歴フィルタリングユニットによってフィルタリングされた分岐履歴データを参照して、分岐を予測する分岐予測ユニットと、を備える分岐予測器。
【請求項１０】
前記分岐履歴長の表示器は、
前記分岐命令語と、前記分岐命令語が参照するソースレジスタとの間の関係を示す従属性情報を保存する分岐レジスタ従属性テーブルと、
前記分岐命令語のソースレジスタに相応する前記分岐レジスタ従属性テーブルのエントリ値を参照して分岐履歴長の表示値を生成する分岐履歴長の表示ユニットと、をさらに備えることを特徴とする請求項９に記載の分岐予測器。
【請求項１１】
前記分岐履歴フィルタリングユニットは、
前記分岐履歴長の表示器の出力を参照して、前記分岐履歴データをマスキングする論理積回路であることを特徴とする請求項９に記載の分岐予測器。
【請求項１２】
前記分岐履歴は、
全域分岐履歴であることを特徴とする請求項９に記載の分岐予測器。
【請求項１３】
前記分岐履歴は、
地域分岐履歴であることを特徴とする請求項９に記載の分岐予測器。
【請求項１４】
前記分岐予測ユニットは、
プログラムカウンタと、
分岐履歴メモリと、
パターン履歴メモリと、
前記プログラムカウンタの出力及び前記フィルタリングされた分岐履歴データを参照して、前記パターン履歴メモリのインデックスを生成するインデックスユニットと、を備えることを特徴とする請求項９に記載の分岐予測器。
【請求項１５】
前記パターン履歴メモリは、
飽和カウンタであることを特徴とする請求項１４に記載の分岐予測器。
【請求項１６】
ハイブリッド分岐予測器において、
分岐命令語の分岐方向を予測する第１分岐予測器と、
前記分岐命令語と、前記分岐命令語が参照するソースレジスタとの間の関係を示す従属性情報を保存する分岐レジスタ従属性テーブルを参照して、条件分岐命令語の分岐方向を予測する第２分岐予測器と、
前記第１分岐予測器及び前記第２分岐予測器を選択する分岐予測器選択ユニットと、
前記第１分岐予測器の分岐予測結果及び前記第２分岐予測器の分岐予測結果のうち、何れか一つの分岐予測結果を参照して前記選択ユニットの選択信号を生成する選択器と、を備えるハイブリッド分岐予測器。
【請求項１７】
コンピュータシステムにおいて、
条件分岐命令語を備える実行プログラムを保存するメモリと、
前記メモリからフェッチされた命令語を実行する中央処理処置と、
前記中央処理処置に連結されて、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存する分岐レジスタ従属性テーブルを参照して、前記条件分岐命令語の分岐方向を予測する分岐予測器と、を備えるコンピュータシステム。
【請求項１８】
前記メモリと前記中央処理処置とを連結するシステムバスをさらに備えることを特徴とする請求項１７に記載のコンピュータシステム。
【請求項１９】
分岐履歴長の表示方法において、
命令語をフェッチするステップと、
前記フェッチした命令語が条件分岐命令語であるかを検査するステップと、
前記フェッチした命令語が条件分岐命令語である場合、条件分岐命令語と、前記条件分岐命令語が参照するソースレジスタとの間の関係を示すレジスタ従属性情報値を各ビット別に論理和演算するステップと、
前記論理演算結果を参照して分岐履歴長の表示値を生成するステップと、
前記生成された分岐履歴長の表示値を長さ表示レジスタに保存するステップと、を含むことを特徴とする分岐履歴長の表示方法。
【請求項２０】
前記レジスタ従属性情報値を保存する分岐レジスタ従属性テーブルを生成するステップをさらに含むことを特徴とする請求項１９に記載の分岐履歴長の表示方法。
【請求項２１】
前記分岐履歴長の表示値を生成するステップは、
前記分岐命令語の実行ステップ以前に実効されることを特徴とする請求項１９に記載の分岐履歴長の表示方法。
【請求項２２】
少なくとも一つのエントリを備える分岐レジスタ従属性テーブルの形成方法において、  命令語をフェッチするステップと、
前記フェッチした命令語が分岐命令語である場合、前記分岐レジスタ従属性テーブルで、ソースレジスタに相応するエントリのあらゆるカラムを１＿ビットずつ左側に論理シフトするステップと、
前記フェッチした命令語がレジスタ書き込み命令語である場合、ソースレジスタの有無を参照して、前記分岐レジスタ従属性テーブルで、各ソースレジスタと相応するあらゆるエントリ値と数字０とを各ビット別に論理和演算するステップと、
前記ビット別の論理和演算結果を、前記レジスタ書き込み命令語の目的レジスタに相応する分岐レジスタ従属性テーブルのエントリに保存するステップと、を含むことを特徴とする分岐レジスタ従属性テーブルの形成方法。
【請求項２３】
前記ビット別の論理和演算ステップは、
前記ビット別の論理和演算結果及び数字‘１’のビット別の論理和演算ステップをさらに含むことを特徴とする請求項２２に記載の分岐レジスタ従属性テーブルの形成方法。
【請求項２４】
前記論理シフト演算ステップは、
前記論理シフト結果及び数字‘１’のビット別の論理和演算ステップをさらに含むことを特徴とする請求項２２に記載の分岐レジスタ従属性テーブルの形成方法。
【請求項２５】
分岐予測方法において、
命令語をフェッチするステップと、
前記フェッチされた命令語を参照して、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存する分岐レジスタ従属性テーブルを生成するステップと、
前記生成された分岐レジスタ従属性テーブルを参照して分岐履歴長の表示値を生成するステップと、
前記生成された分岐履歴長の表示値を参照して、入力された分岐履歴データをフィルタリングするステップと、
前記フィルタリングされた分岐履歴データを参照して分岐方向を予測するステップと、を含むことを特徴とする分岐予測方法。
【請求項２６】
前記分岐レジスタ従属性テーブルを形成するステップは、
命令語をフェッチするステップと、
前記フェッチした命令語が分岐命令語である場合、前記分岐レジスタ従属性テーブルで、ソースレジスタに相応するエントリのあらゆるカラムを１＿ビットずつ左側に論理シフト演算するステップと、
前記フェッチした命令語がレジスタ書き込み命令語である場合、ソースレジスタ有無を参照して、前記分岐レジスタ従属性テーブルで、各ソースレジスタと相応するあらゆるエントリ値と数字０とを各ビット別に論理和演算するステップと、
前記ビット別の論理和演算結果を、前記レジスタ書き込み命令語の目的レジスタに相応する分岐レジスタ従属性テーブルのエントリに保存するステップと、を含むことを特徴とする請求項２５に記載の分岐予測方法。
【請求項２７】
前記分岐履歴長表示値の生成ステップは、
分岐履歴の幅より広くない大きさを有する分岐履歴長の表示値を生成することを特徴とする請求項２５に記載の分岐履歴長の表示方法。
【請求項２８】
前記フィルタリングステップは、
前記分岐履歴長の表示器の出力を参照してマスキングされた分岐履歴データを生成するステップであることを特徴とする請求項２５に記載の分岐予測方法。
【請求項２９】
前記分岐方向を予測するステップは、
プログラムカウンタと、前記フィルタリングステップで生成されたフィルタリングされた分岐履歴データとを参照して、パターン履歴テーブルのインデクシングアドレスを生成するステップと、
前記インデクシングアドレスに相応するパターン履歴テーブルエントリ値によって分岐方向を決定するステップと、をさらに含むことを特徴とする請求項２５に記載の分岐予測方法。
【請求項３０】
前記インデクシングアドレスの生成ステップは、
前記フィルタリングされた分岐履歴データとプログラムカウンタとを各ビット別に排他的論理和演算するステップであることを特徴とする請求項２９に記載の分岐予測方法。
【請求項３１】
前記分岐履歴データは、
全域分岐履歴であることを特徴とする請求項２５に記載の分岐予測方法。
【請求項３２】
ハイブリッドの分岐予測方法において、
条件分岐命令語の分岐方向を予測する第１分岐予測器による分岐予測ステップと、
前記条件分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存する分岐レジスタ従属性テーブルを参照して、前記条件分岐命令語の分岐方向を予測する第２分岐予測器による分岐予測ステップと、
前記第１分岐予測器の分岐予測結果と前記第２分岐予測器の分岐予測結果とを比較するステップと、
前記第１分岐予測器の分岐予測結果及び前記第２分岐予測器の分岐予測結果のうち、一つの分岐予測結果を選択するステップと、を含むことを特徴とするハイブリッドの分岐予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分岐予測器に係り、さらに詳細には、分岐履歴を利用して条件分岐命令語の分岐方向を予測する分岐予測器で、分岐履歴の長さを可変的に参照して分岐予測を行う装置及び方法に関する。
【背景技術】
【０００２】
一般的に、ＣＰＵの命令語実行性能を向上させるための技術は種々あるが、そのうち分岐予測は、ＣＰＵの命令語実行性能を向上させる一つの重要な技術である。
【０００３】
一般的に、一つのプログラムコードには、平均的に約１５％〜２０％の条件分岐命令語が含まれると知られている。さらに、ＣＰＵの単位クロック当り実行命令語数を増加させるために、パイプライン構造の命令語実行技法が導入され、複数の命令語実行パイプラインを有するスーパースカラー技法も多く利用されている。このようなパイプラインには、条件分岐命令語の次の命令語が、条件分岐命令語実行前にフェッチされるため、条件分岐命令語の予測が、ＣＰＵ命令語実行性能の向上に重要な技術になった。
【０００４】
一般的に、分岐予測は、大きく静的分岐予測方法と動的分岐予測との２つに分けられる。静的分岐予測とは、プログラムコードをコンパイルする過程において、コンパイルされたコードを分析して分岐予測を行う方法をいう。動的分岐予測とは、コンパイルされたプログラムコードを実行しつつ、リアルタイムで分岐予測を行う方法をいう。
【０００５】
動的分岐予測方法において、一般的に多く用いられる方法は、リアルタイムで生成される条件分岐命令語の分岐履歴を保存し、これに基づいて分岐を予測する方法である。一般的に、多く用いられた分岐履歴を使用する分岐予測器は、２レベル分岐予測器である。一般的な２レベル分岐予測器は、行われた条件分岐命令語の分岐結果を保存する分岐履歴メモリと、前記保存された分岐履歴を利用して条件分岐命令語の分岐方向を予測する分岐予測ユニットとを備える。
【０００６】
図１は、一般的な２レベル分岐予測器のブロック図である。
図１に示すように、一般的な２レベル分岐予測器１０は、分岐履歴レジスタ１、分岐命令語のアドレスを表示するＰＣ（Ｐｒｏｇｒａｍ  Ｃｏｕｎｔｅｒ）２、前記分岐命令語の最近の分岐傾向を表示するパターン履歴テーブル（Ｐａｔｔｅｒｎ  Ｈｉｓｔｏｒｙ  Ｔａｂｌｅ：ＰＨＴ）３、そして、前記分岐履歴レジスタ１の値及び前記ＰＣ ２の値を入力されて前記ＰＨＴ ３をインデクシングするためのインデクシングアドレスを生成するインデクシングユニット４を備える。前記ＰＨＴ ３は、各エントリが前記分岐命令語の最新分岐傾向によって増加または減少する２＿ビット飽和カウンタ（ｓａｔｕｒａｔｉｎｇ ｃｏｕｎｔｅｒ）からなるメモリである。また、前記インデクシングユニット４は、インデクシング過程で発生する制限されたＰＨＴ ３の大きさのために発生するインデクシング重複（エイリアシングまたはインターフェランス）問題を解決するために、前記分岐履歴メモリ１の値及び前記ＰＣ ２の値を参照して、インデクシングアドレスを調整するインデクシング演算を行う。例えば、各ビット別の排他的論理和（ＸＯＲ）演算のようなインデクシング演算を行う。
【０００７】
また、図１に示すように、分岐履歴レジスタ１は、現在まで行われた条件分岐命令語の分岐結果が順に記録されており、最近に実行された条件分岐命令語であるほどＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ）ビットに記録される。また、分岐履歴レジスタ及び現在のＰＣ値を参照して、ＰＨＴをインデクシングすることによって、最近の分岐傾向を参照して分岐方向を決定する。また、最終に行われた分岐結果を参照して、当該エントリ値を増加または減少してアップデートする。一般的に、ＰＨＴの選択されたエントリ値の上位ビットが１であればｔａｋｅｎ（分岐）であり、それともｎｏｔ−ｔａｋｅｎ（非分岐）と予測する。
【０００８】
このような分岐履歴を使用する分岐予測器は、多様な形態がありうるが、通常、所定長さの分岐履歴値を使用して分岐方向を予測する。
【０００９】
図２は、テストプログラムを使用した分岐履歴の長さによる分岐予測失敗率を示すグラフである。１８１.ｍｃｆは、ＳＰＥＣｉｎｔ２０００に定義されたｗｏｒｋｌｏａｄのうち一つである。
図２に示すように、同じテストプログラムであっても、所定の分岐履歴の長さによって分岐予測失敗率が変化するということが分かる。一方、図２には示されていないが、行われるｗｏｒｋｌｏａｄが変われば、分岐予測失敗率も変わるという結果が得られる（図示せず）。
【００１０】
また、図２に示すように、ＰＨＴが５１２バイト、１キロバイト、２キロバイト、そして、４キロバイトの場合を区分しても、固定された分岐履歴長によって予測失敗率が変わるということが分かる。すなわち、最適の分岐履歴長は、ＰＨＴの大きさによって異なり、行われるプログラムによって異なる。
したがって、一定の長さの分岐履歴値を参照する従来の分岐予測方法は、行うプログラムによって最適の性能を表せないという問題点がある。すなわち、一定の長さの分岐履歴を使用する分岐予測器は、多様な環境で最適の分岐予測性能を表せない。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、前述のように、一定の長さの分岐履歴を参照して条件分岐の方向を予測する従来の技術の問題点を解決するためになされたものであって、本発明の目的は、有効分岐履歴データを利用して分岐予測の性能を向上させるための分岐履歴長の表示装置及びその方法を提供するところにある。
【００１２】
また、本発明の他の目的は、前記分岐履歴長の表示器を備える分岐予測器及びシステムを提供するところにある。
【課題を解決するための手段】
【００１３】
本発明は、分岐履歴長の表示器に関する。本発明に係る分岐履歴長の表示器は、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存する分岐レジスタ従属性テーブル（Ｂｒａｎｃｈ  Ｒｅｇｉｓｔｅｒ  Ｄｅｐｅｎｄｅｎｃｙ  Ｔａｂｌｅ：Ｂｒ＿ＲＤＴ）、及び前記分岐命令語のソースレジスタに相応する前記Ｂｒ＿ＲＤＴのエントリ値を参照して分岐履歴長の表示値を生成する分岐履歴長の表示ユニットを備える。
【００１４】
前記Ｂｒ＿ＲＤＴは、前記分岐命令語のソースレジスタ値の変化を与える基本ブロック情報を保存するメモリであることを特徴とする。また、前記Ｂｒ＿ＲＤＴは、ワーキングレジスタに相応するエントリを有するメモリであることを特徴とする。また、前記Ｂｒ＿ＲＤＴは、前記Ｂｒ＿ＲＤＴの各カラムビットが実行された基本ブロックと相応することを特徴とする。また、前記Ｂｒ＿ＲＤＴは、前記実行された基本ブロックのうち、最近に実行された基本ブロックであるほどＬＳＢに位置するように配置されたことを特徴とする。
【００１５】
前記基本ブロックは、実行プログラムコードで、一つの分岐命令語を基準に前記分岐命令語を備えるように分割した命令語グループであることを特徴とする。
【００１６】
前記分岐履歴長の表示ユニットは、前記分岐レジスタ従属性テーブルのエントリ値を参照して有効分岐履歴データを生成する論理回路と、前記有効分岐履歴データを保存する長さ表示レジスタと、を備えることを特徴とする。
【００１７】
前記有効分岐履歴データは、入力データのビットのうち、最も上位に位置した‘１’の値を基準に、それより高いビットは‘０’にして、それ以外のビットは‘１’を出力する変換データであることを特徴とする分岐履歴長の表示器である。
【００１８】
本発明は、分岐予測器に関する。本発明に係る分岐予測器は、分岐履歴長の表示器、前記分岐履歴長の表示器の出力を参照して分岐履歴データをフィルタリングする分岐履歴フィルタリングユニット、及び前記分岐履歴データを出力して、前記分岐履歴フィルタリングユニットによってフィルタリングされた分岐履歴データを参照して分岐を予測する分岐予測ユニットを備える。前記分岐履歴長の表示器は、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存するＢｒ＿ＲＤＴ、及び前記分岐命令語のソースレジスタに相応する前記Ｂｒ＿ＲＤＴのエントリ値を参照して分岐履歴長の表示値を生成する分岐履歴長の表示ユニットをさらに備える。前記分岐履歴フィルタリングユニットは、前記分岐履歴長の表示器の出力を参照して、前記分岐履歴データをマスキングする論理積回路であることを特徴とする。
【００１９】
実施形態として、本発明に係る分岐予測器は、全域分岐履歴を使用する分岐予測器である。
【００２０】
さらに他の実施形態として、本発明に係る分岐予測器は、地域分岐履歴を使用する分岐予測器である。
【００２１】
本発明は、ハイブリッド分岐予測器に関する。本発明に係るハイブリッド分岐予測器は、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存するＢｒ＿ＲＤＴを参照して、条件分岐命令語の分岐方向を予測する第１分岐予測器と、前記第１分岐予測器と異なる少なくとも一つの第２分岐予測器と、前記第１分岐予測器及び前記第２分岐予測器を選択する分岐予測器選択ユニットと、前記第１分岐予測器の分岐予測結果及び前記第２分岐予測器の分岐予測結果のうち、何れか一つの分岐予測結果を参照して前記選択ユニットの選択信号を生成する選択器と、を備える。
【００２２】
本発明は、コンピュータシステムに関する。本発明に係るコンピュータシステムは、条件分岐命令語を備える実行プログラムを保存するメモリ、前記メモリからフェッチされた命令語を実行する中央処理処置、前記メモリと前記中央処理処置装置とを連結するシステムバス、及び前記システムバス及び前記中央処理処置に連結されて、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存するＢｒ＿ＲＤＴを参照して前記条件分岐命令語の分岐方向を予測する分岐予測器を備える。
【００２３】
本発明は、分岐履歴長の表示方法に関する。前記分岐履歴長の表示方法は、命令語をフェッチするステップ、前記フェッチした命令語が条件分岐命令語であるかを検査するステップ、前記分岐命令語のソースレジスタのそれぞれに相応するＢｒ＿ＲＤＴのエントリ値と数字０とを各ビット別に論理和演算するステップ、前記論理演算結果を参照して分岐履歴長の表示値を生成するステップ、及び前記生成された分岐履歴長の表示値を長さ表示レジスタに保存するステップを含む。
【００２４】
本発明は、Ｂｒ＿ＲＤＴの形成方法に関する。前記Ｂｒ＿ＲＤＴを形成する方法は、命令語をフェッチするステップ、前記フェッチされた命令語を参照して、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存するＢｒ＿ＲＤＴを形成するステップ、前記生成された従属性テーブルを参照して分岐履歴長の表示値を生成するステップ、前記生成された分岐履歴長の表示値を参照して、入力された分岐履歴データをフィルタリングするステップ、及び前記フィルタリングされた分岐履歴データを参照して分岐方向を予測するステップを含む。
【００２５】
本発明は、分岐予測方法に関する。前記分岐予測方法は、命令語をフェッチするステップ、前記フェッチされた命令語を参照して、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存するＢｒ＿ＲＤＴを形成するステップ、前記生成された従属性テーブルを参照して分岐履歴長の表示値を生成するステップ、前記生成された分岐履歴長の表示値を参照して、入力された分岐履歴データをフィルタリングするステップ、及び前記フィルタリングされた分岐履歴データを参照して分岐方向を予測するステップを含む。前記Ｂｒ＿ＲＤＴを形成するステップは、命令語をフェッチするステップ、前記フェッチした命令語が分岐命令語である場合、前記Ｂｒ＿ＲＤＴのあらゆるカラムを１＿ビットずつ左側に論理シフト演算するステップ、前記フェッチした命令語がレジスタ書き込み命令語である場合、ソースレジスタ有無を参照して、Ｂｒ＿ＲＤＴで各ソースレジスタと相応するあらゆるエントリ値と数字０とを各ビット別に論理和演算するステップ、及び前記ビット別論理和演算結果を、前記レジスタ書き込み命令語の目的レジスタに相応するＢｒ＿ＲＤＴのエントリに保存するステップを含む。
【００２６】
本発明は、ハイブリッドの分岐予測方法に関する。前記ハイブリッドの分岐予測方法は、分岐命令語とワーキングレジスタとの間の関係を示すレジスタ従属性情報を保存するＢｒ＿ＲＤＴを参照して、条件分岐命令語の分岐方向を予測する第１分岐予測器による分岐予測ステップ、前記第１分岐予測器と異なる少なくとも一つの第２分岐予測器による前記条件分岐命令語の分岐予測ステップ、前記第１分岐予測器の分岐予測結果と前記第２分岐予測器の分岐予測結果とを比較するステップ、及び前記第１分岐予測器の分岐予測結果及び前記第２分岐予測器の分岐予測結果のうち、一つの分岐予測結果を選択するステップを含む。
【発明の効果】
【００２７】
本発明は、動的に変化する長さのフィルタリングされた分岐履歴データを生成し、これを参照することによって効果的な分岐予測が可能である。
【００２８】
また、本発明は、応用プログラムに関係なく最も理想的な長さでフィルタリングされた分岐履歴データを動的に生成するために、実行プログラムに関係なく理想的な分岐予測が可能である。
【００２９】
また、ＰＨＴの大きさが変化しても、変化したＰＨＴの大きさに適応的に動作して理想的な分岐予測が可能である。
【００３０】
また、本発明は、分岐予測のために、分岐履歴データを使用する多様な分岐予測器に適用可能である。
【００３１】
また、本発明の分岐予測器は、既存の分岐履歴データを使用する分岐予測器に、ＣＰＵワーキングレジスタと相応する小さなＢｒ＿ＲＤＴを備える分岐履歴長の表示器、及び前記分岐履歴長の表示器と関連したフィルタリングユニットのみを追加することによって具現されうるため、小さなハードウェアを追加するだけで大きな性能の効果を得ることができる。
【００３２】
また、本発明は、一般的なＣＰＵのワーキングレジスタを基にするＢｒ＿ＲＤＴを利用するため、ワーキングレジスタを使用するＣＰＵに汎用的に適用されうる。
【発明を実施するための最良の形態】
【００３３】
以下、当業者が、本発明の技術的思想を容易に実施できる程度に詳細に説明するために、添付した図面を参照して、本発明の望ましい実施形態を説明する。
【００３４】
本発明の理解を容易にするために、図３は、基本ブロックの概念を説明し、図４ないし図１７は、分岐履歴長を決定するために、Ｂｒ＿ＲＤＴのエントリを形成する方法及び分岐予測方法を示す。また、図１８ないし図２０は、分岐履歴長の表示器を備える分岐予測器の実施形態を示す。これらの装置及び方法の説明を通じて、分岐予測の性能を向上させる本願発明の特徴をさらに理解できるであろう。
【００３５】
図３は、本発明の基本ブロックの概念図である。
図３に示すように、基本ブロックは、コンパイルされたプログラムコードを一定の基準をもって単位ブロック化させたものであって、一つの基本ブロックは、一つの分岐命令語を備える。また、一つの基本ブロックは、分岐命令語を除いた他の命令語を備えうる。基本ブロックの形成方法は、実行プログラムの命令語を順次にチェックして、一つの分岐命令語が存在する度に、当該分岐命令語を備える命令語ブロックを一つの基本ブロックと定義することである。また、一つの基本ブロックを定義した後には、それ以後の命令語からさらに他の分岐命令語を備える命令語ブロックを一つの基本ブロックに定義する。それと同様に、全体プログラムコードを分岐命令語を基準に基本ブロックに分割する。各基本ブロックの下端の左側矢印は、条件分岐命令語の分岐結果が非分岐であることを意味し、右側矢印は、条件分岐命令語の分岐結果が分岐されたことを意味する。
【００３６】
一般的に、条件分岐命令語は、ＣＰＵ内の状態値を参照して分岐方向を決定する。前記状態値は、ＣＰＵワーキングレジスタと関連した各種の演算結果によって決定される。したがって、条件分岐の方向は、前記ワーキングレジスタの変更履歴及び前記条件分岐命令語による条件分岐履歴の関係を把握すれば、さらに正確な分岐予測が可能である。すなわち、条件分岐命令語の分岐方向は、基本的に先立つ条件分岐命令語の分岐方向と関連があり、前記先立つ条件分岐命令語の分岐方向も、ワーキングレジスタ値を変更させるレジスタ書き込み命令語とも関連がある。本発明では、前記関連性を分岐レジスタ従属性と定義し、Ｂｒ＿ＲＤＴを作成して分岐方向を予測する情報として活用する。
【００３７】
図４は、本発明の基本ブロックから構成された分岐フローチャートである。
図４に示すように、図面において基本ブロックは、“ＢＢ”（Ｂａｓｉｃ  Ｂｌｏｃｋ）と表示されている。図４においては、基本ブロックが全部で１１個であり、ＢＢ０からＢＢ１０まで示されており、それぞれの基本ブロックは、ブロックの最後の命令語として分岐命令語を有している。図４においては、説明の便宜のために、各基本ブロックの最後に条件分岐命令語が存在しているものを示す。図４に示す基本ブロックの下端に表示された２個の矢印の意味は、図３で説明したように、各基本ブロックの下端の左側矢印は、条件分岐命令語の分岐結果がＮｏｔ−ｔａｋｅｎされたことを意味し、右側矢印は、条件分岐命令語の分岐結果がＴａｋｅｎされたことを意味する。例えば、基本ブロックＢＢ０の条件分岐命令語“ｉｆ（Ｒ２）”が、Ｒ２の値が０であれば、基本ブロックＢＢ１に分岐し、Ｒ２値が０でなければ、基本ブロックＢＢ２に分岐する。一方、もし、基本ブロックが無条件分岐命令語を備える場合、分岐方向は常にＴａｋｅｎされる。
【００３８】
また、図４に示すように、図４の基本ブロックのうち、灰色で表示された基本ブロックは、ＢＢ０（ｔａｋｅｎ）から出発したプログラムの実行経路が、ＢＢ２（ｎｏｔ−ｔａｋｅｎ）、ＢＢ３（ｎｏｔ−ｔａｋｅｎ）、ＢＢ４（ｔａｋｅｎ）、ＢＢ８（ｔａｋｅｎ）、ＢＢ９（ｔａｋｅｎ）を順次に経てＢＢ１０に到達したことを意味する。現在、分岐予測器は、基本ブロックＢＢ１０で条件分岐命令語“ｉｆ（Ｒ４）”を実行する前に、分岐方向を予測するステップにあると仮定する。ＢＢ０以前に行われた以前の基本ブロックは考慮対象から除かれる。基本ブロックＢＢ１０で、最近に実行されたＢＢ０からＢＢ９までの総６個の分岐履歴“ＴＮＮＴＴＮ”が分岐履歴レジスタに保存されていると仮定する。記録順序は、最近に実行された基本ブロックの分岐結果であるほど、分岐履歴レジスタの最下位ビットに位置するように表示する。ここで“Ｔ”は、Ｔａｋｅｎを意味し、“Ｎ”は、Ｎｏｔ−ｔａｋｅｎを意味する。
【００３９】
また、図４に示すように、各基本ブロックは、分岐命令語を除いた他の命令語を備えうるが、分岐命令語と共にレジスタ書き込み命令語が付加的に示される。レジスタ書き込み命令語で例示されたレジスタＲ１〜Ｒ４は、ＣＰＵ内のワーキングレジスタを意味する。一般的に、ＣＰＵのワーキングレジスタは、ＣＰＵがフェッチされた命令語を処理しつつ臨時的に使用するレジスタセットを意味する。また、あらゆるＣＰＵは、構造が異なるか、または命令語セットが異なる場合、保有したレジスタセットも異なりうる。本発明においてワーキングレジスタは、レジスタＲ０〜Ｒ３１を例にとって説明する。図４のＢＢ２を参照すれば、ＢＢ２で命令語“Ｒ１＝Ｒ２＋Ｒ３”は、レジスタＲ２及びＲ３の値を合算してレジスタＲ１に使う命令語を意味する。ＢＢ３の命令語“Ｒ１＝４”は、ｉｍｍｅｄｉａｔｅ値である“４”をレジスタＲ１に使う命令語である。ＢＢ４の命令語“ＬＤＲ３，ＭＥＭ”は，ＭＥＭ項目が示すアドレスの内容をレジスタＲ３にロードするレジスタ書き込み命令語である。ＢＢ８の命令語“Ｒ４＝Ｒ１＋Ｒ３”は、ＢＢ２と同じレジスタ書き込み命令語である。
【００４０】
また、図４を参照して、制御フローチャートの分岐レジスタ従属性を分析すれば、次のような事実が分かる。まず、ＢＢ１０の分岐命令語“ｉｆ（Ｒ４）”の分岐結果は、ソースレジスタＲ４の値と密接な関連があるということが分かる。また、レジスタＲ４の値は、ＢＢ８でレジスタＲ１及びレジスタＲ３の値により決定され（Ｒ４＝Ｒ１＋Ｒ３）、次いで、レジスタＲ１の値は、ＢＢ３で再決定される（Ｒ１＝４）。もちろん、レジスタＲ１の場合、ＢＢ２のレジスタＲ２及びレジスタＲ３により再び再決定されるが（Ｒ１＝Ｒ２＋Ｒ３）、ＢＢ３の“Ｒ１＝４”演算により新たに更新されたため、以前のレジスタ従属成果は断絶される。したがって、ＢＢ１０の“ｉｆ（Ｒ４）”分岐の立場では、レジスタＲ１の値がＢＢ３で決定された。一方、レジスタＲ４と関連しているＢＢ８に表れたさらに他のレジスタのＲ３は、ＢＢ４の“ＬＤＲ３，ＭＥＭ”演算により新たに更新されるということが分かり、それ以上、レジスタＲ３と関連したレジスタ従属性を発見できないということも分かる。
【００４１】
レジスタ書き込み観点から説明すれば、ＢＢ１０の“ｉｆ（Ｒ４）”に対する分岐予測は、ＢＢ３の“Ｒ１＝４”及びＢＢ４の“ＬＤＲ３，ＭＥＭ”で表れるレジスタ従属性を有する基本ブロックの当該レジスタ値により大きく左右され、結局、ＢＢ３及びＢＢ４の“Ｒ１＝４”と“ＬＤＲ３，ＭＥＭ”との実行如何が、ＢＢ１０の“ｉｆ（Ｒ４）”の分岐予測に決定的である。以上の事実を基本ブロックの観点から説明すれば、基本ブロックＢＢ３及び基本ブロックＢＢ４の実行如何が、基本ブロックＢＢ１０に表された分岐予測に大きな影響を及ぼすということを意味する。
【００４２】
一方、分岐命令語の分岐結果の観点から説明すれば、ＢＢ３の実行如何は、ＢＢ２の“ｉｆ（Ｒ３）”分岐の分岐予測結果に、そして、ＢＢ４の実行如何は、ＢＢ３に含まれた“ｉｆ（Ｒ４）”分岐の分岐予測結果に大きな影響を受けるということが分かる。しかしながら、ＢＢ４の実行に影響を及ぼすＢＢ３の実行如何は、結局、ＢＢ２の実行如何によって再決定されるため、さらに遠くに離れている基本ブロックＢＢ２からさらに根本的な影響を受ける。
【００４３】
以上の分析を通じて、現在予測しようとする分岐と強く関連しているレジスタ及び分岐命令語を把握できる。すなわち、条件分岐命令語が参照するレジスタの値を変更させる基本ブロックを参照することによって、条件分岐方向を予測するために、条件分岐履歴をどの程度の長さほど参照することが適切であるかを判断すれば、さらに正確な分岐予測が可能である。
【００４４】
以下、図５を参照して、本発明の分岐予測システム及び分岐予測方法を詳細に説明する。
図５は、本発明のＢｒ＿ＲＤＴの構成図である。
本発明の一実施形態において、Ｂｒ＿ＲＤＴの幅は、保存された分岐結果を提供する分岐履歴メモリの最大幅より大きくなく構成されうる。Ｂｒ＿ＲＤＴの各エントリは、ＣＰＵが条件分岐命令語を実行するとき、参照するワーキングレジスタのそれぞれに相応するように構成される。また、それぞれのエントリは、相応するワーキングレジスタの保存値の変更がどの基本ブロックと関連しているかを各ビット別に記録した履歴を含む。
【００４５】
図５に示すように、本発明の一実施形態として、ＣＰＵのワーキングレジスタがＲ０からＲ３１まで備えられている場合、Ｂｒ＿ＲＤＴは、少なくともＲ０からＲ３１に相応するエントリを備える。Ｂｒ＿ＲＤＴのエントリ値のカラムに表示された“１”は、当該基本ブロックと現在分岐方向を予測しようとする条件分岐命令語とが関連していることを表し、“０”は、関連していないことを表す。Ｂｒ＿ＲＤＴの各カラムは、それぞれ以前に行われた基本ブロックと相応する。本発明では、ＣＰＵがプログラムコードを行いつつ基本ブロックを経る度に、当該基本ブロックにおいて、レジスタ書き込み命令語のソースレジスタ、目的レジスタ、または条件分岐命令語が条件分岐を判別するために参照するソースレジスタをチェックして、毎基本ブロック単位でＢｒ＿ＲＤＴエントリをアップデートする。
【００４６】
図５のＢｒ＿ＲＤＴは、本発明のＢｒ＿ＲＤＴエントリの形成アルゴリズムを支援しつつ、レジスタの相互従属性を追跡できる保存要素である。Ｂｒ＿ＲＤＴは、実際のプロセッサが支援する構造レジスタ数ほどのエントリにも構成され、各エントリの幅は、２”サイズ（ｄｅｐｔｈ）のＰＨＴと関連した最大分岐履歴長であるｎになる。各Ｂｒ＿ＲＤＴのｉ番目のエントリは、本発明のＢｒ＿ＲＤＴの形成アルゴリズムと連係して、各レジスタＲｉの実行如何に影響を及ぼす基本ブロック情報を含む。このとき、当該エントリの特定のビットが１であるという意味は、分岐履歴上で当該カラムと相応する位置の基本ブロックに含まれた分岐命令語が、ｉ番目のレジスタＲｉ値の変更に影響を及ぼす分岐であることを意味し、０は、そうでない分岐であることを意味する。
【００４７】
本発明の実施形態に係るＢｒ＿ＲＤＴの形成方法は、３つである。第１ Ｂｒ＿ＲＤＴの形成アルゴリズムは、レジスタ書き込み命令語を基準にしたＢｒ＿ＲＤＴの形成アルゴリズムであり、第２形成アルゴリズムは、条件分岐命令語が参照するレジスタを基準とするＢｒ＿ＲＤＴの形成アルゴリズムである。また、第３形成アルゴリズムは、第１形成アルゴリズムと第２形成アルゴリズムとを結合したＢｒ＿ＲＤＴの形成アルゴリズムである。この３つの方法について、図６ないし図１３で詳細に説明する。
【００４８】
図６は、本発明の第１Ｂｒ＿ＲＤＴの形成アルゴリズムである。
図７は、図６に示す本発明の第１ Ｂｒ＿ＲＤＴの形成アルゴリズムを示す分岐フローチャートである。
図８は、図６に示す本発明の第１ Ｂｒ＿ＲＤＴの形成アルゴリズムによる分岐履歴長表示値の形成図である。
【００４９】
図６ないし図８を参照して、本発明の第１ Ｂｒ＿ＲＤＴの形成アルゴリズム及び分岐履歴長の表示方法を説明する。
まず、図６に示すように、ＣＰＵが分岐命令語に出合う場合と、レジスタ書き込み命令語に出合う場合とを区分して、Ｂｒ＿ＲＤＴの各エントリをアップデートする方法を説明する。
【００５０】
図６のアルゴリズムで、Ｂｒ＿ＲＤＴは、図５のＢｒ＿ＲＤＴの構造を基盤とし、Ｒｅｇ＿ｄｅｓｔ及びＲｅｇ＿ｓｒｃｉ（ｉ＝１、２…）のそれぞれは、レジスタ書き込み命令語の目的レジスタ及びソースレジスタを意味する。
【００５１】
図６のＢｒ＿ＲＤＴの形成方法は、分岐結果の予測のために、分岐命令語が参照する関連レジスタの間のレジスタ従属性を追跡する。そして、最終的に関連のあるレジスタを備えるように誘導する分岐命令語を把握した後、関連分岐命令語の分岐履歴のみを選別的に使用させる方式である。このときの分析過程では、レジスタ従属性を、レジスタ書き込み演算命令語を対象として追跡する。
【００５２】
図６で、実行命令語がレジスタ書き込み命令語であれば、レジスタ書き込み命令語のそれぞれのソースレジスタに対するＢｒ＿ＲＤＴエントリ値を、数字‘１’と共に相互各ビット別の論理和演算を行って、その結果をＢｒ＿ＲＤＴの目的レジスタの値として保存する。一方、実行命令語が条件分岐命令語であれば、分岐命令語のソースレジスタ値、または複数のソースレジスタ値の各ビット別の論理和演算を経て最終的に分岐履歴長値を生成する。その後、Ｂｒ＿ＲＤＴの当該エントリを１＿ビット論理シフト（ｓｈｉｆｔ ｌｅｆｔ、＜＜）する。実行命令語が無条件分岐命令語 であれば、ソースレジスタを参照するか、または分岐履歴長値を生成する必要なしに、単に、Ｂｒ＿ＲＤＴの当該エントリを１＿ビット論理シフトのみを行う。
【００５３】
図８は、以上で説明した図７のシナリオ下で、図６に与えられたアルゴリズムを、図５で提示されたＢｒ＿ＲＤＴ構造を使用して実行させた場合、各ステップ別の実行結果を示すＢｒ＿ＲＤＴの形成過程を示すＢｒ＿ＲＤＴの形成図である。
【００５４】
図８に示すように、ＢＢ０が初めて行われる基本ブロックであると仮定するとき、Ｂｒ＿ＲＤＴのあらゆるエントリは、その値が分からない（ｕｎｋｎｏｗｎ）状態である。Ｕｎｋｎｏｗｎビットは、何れも“Ｘ”で表記した。図８で、Ｂｒ＿ＲＤＴの幅は、便宜上、最下位の７＿ビットのみを示す。
【００５５】
ＢＢ２の開始ステップは、ＢＢ０からＢＢ２に分岐した直後の状態である。ＢＢ０の条件分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトした。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。
【００５６】
次のＢＢ２の最後のステップは、ＢＢ２のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ３）”を実行する直前の状態である。ＢＢ２で、レジスタ書き込み命令語Ｒ１＝Ｒ２＋Ｒ３が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタＲ２及びＲ３に相応するエントリ値を各ビット別に論理和し、追加的に二進数‘…０００００１’とさらに論理和して、目的レジスタＲ１に相応するエントリに記録する。
【００５７】
ＢＢ３の開始ステップは、ＢＢ２からＢＢ３に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ２の分岐命令語“ｉｆ（Ｒ３）”が実行されるため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。
【００５８】
次のＢＢ３の最後のステップは、ＢＢ３のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ４）”を実行する直前の状態である。ＢＢ３で、レジスタ書き込み命令語Ｒ１＝４が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタに相応するエントリ値を各ビット別に論理和し、追加的に二進数‘…０００００１’とさらに論理和して、目的レジスタＲ１に相応するエントリに記録する動作を行う。しかし、Ｂｒ＿ＲＤＴのソースレジスタがないため、二進数‘…０００００１’を目的レジスタＲ１に相応するエントリに記録する。すなわち、レジスタ従属性が、以前基本ブロックによる分岐履歴とは断絶された。
【００５９】
ＢＢ４の開始ステップは、ＢＢ３からＢＢ４に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ３の分岐命令語“ｉｆ（Ｒ４）”が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。
【００６０】
次のＢＢ４の最後のステップは、ＢＢ４のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ１）”を実行する直前の状態である。ＢＢ４で、レジスタ書き込み命令語“ＬＤＲ３，ＭＥＭ”が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタに相応するエントリ値を各ビット別に論理和し、追加的に数字１とさらに論理和して、目的レジスタＲ３に相応するエントリに記録する動作を行う。しかし、Ｂｒ＿ＲＤＴのソースレジスタがないため、二進数‘…０００００１’を目的レジスタＲ３に相応するエントリに記録する。ＢＢ３の最後のステップと同様に、レジスタ従属性が、以前の基本ブロックによる分岐履歴とは断絶された。
【００６１】
ＢＢ８の開始ステップは、ＢＢ４からＢＢ８に分岐（Ｔａｋｅｎ）した直後の状態である。ＢＢ４の分岐命令語“ｉｆ（Ｒ１）”が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。
【００６２】
次のＢＢ８の最後のステップは、ＢＢ８のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語Ｒ４＝Ｒ１＋Ｒ３が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタＲ１及びＲ３に相応するエントリ値を各ビット別に論理和し、追加的に二進数‘…０００００１’を目的レジスタＲ４に相応するエントリに記録する動作を行う。
【００６３】
ＢＢ９の開始ステップ（図示せず）は、ＢＢ８からＢＢ９に分岐（Ｔａｋｅｎ）した直後の状態である。ＢＢ８の分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。
【００６４】
次のＢＢ９の最後のステップは、ＢＢ９のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語がないため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴは、ＢＢ９の開始ステップと比較して変更事項がない。
【００６５】
ＢＢ１０の開始ステップ（図示せず）は、ＢＢ９からＢＢ１０に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ９の分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。
【００６６】
次のＢＢ１０の最後のステップは、ＢＢ９のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語がないため、図６のアルゴリズムによって、Ｂｒ＿ＲＤＴは、ＢＢ１０の開始ステップと比較して変更事項がない。
【００６７】
図８のＢＢ１０の最後のステップのＢｒ＿ＲＤＴエントリを参照すれば、ソースレジスタＲ４に該当する４番目のエントリ値が、“・・・００１１１００”の値を有し、最も０ではない最上位ビットは、最下位ビットから５だけ離れているということが分かる。そして、この値は、分岐履歴長の表示値として最終的に使用される。すなわち、ＢＢ１０の“ｉｆ（Ｒ４）”分岐方向を予測するためには、５ほどの分岐履歴を使用する。すなわち、図８の結果は、あらゆる分岐履歴を参照するより、最下位５ほどの分岐履歴のみを使用することが、分岐方向をさらに正確に予測することを示す。
【００６８】
Ｂｒ＿ＲＤＴを参照して分岐履歴長を決定する分岐履歴長の表示値は、図６の第１ Ｂｒ＿ＲＤＴの形成アルゴリズムだけでなく、図９及び図１２に提示された第１ Ｂｒ＿ＲＤＴ及び第２ Ｂｒ＿ＲＤＴの形成アルゴリズムにもそのまま使用される。図６、図９及び図１２に提示されたＢｒ＿ＲＤＴの形成アルゴリズムを実行する場合、現在、実行結果を予測しようとする分岐命令語の関連レジスタＲｉに対するＢｒ＿ＲＤＴのｉ番目のエントリ値を有するリストを分岐履歴長の表示値とする。分岐履歴長表示値のＬＳＢから始まって、‘０’ではない最上位値を有するｊ番目のビットに対して、長さ表示値がｊになると定義する。
【００６９】
図８に示すように、結局、ＢＢ１０の“ｉｆ（Ｒ４）”に対する分岐履歴長の表示値が５の値を有するということが分かる。すなわち、当該分岐の予測時に、既存の所定の分岐履歴（・・・ＴＮＮＴＴＮ）の長さで最近の５個である（ＮＮＴＴＮ）のみを使用することが、分岐予測の実効性を高める。
【００７０】
本発明は、実際に具現されるマイクロプロセッサのＩＳＡ（Ｉｎｓｔｒｕｃｔｉｏｎ Ｓｅｔ Ａｒｃｈｉｔｅｃｔｕｒｅ）によって若干の変形がありうる。すなわち、条件分岐演算とレジスタ書き込み演算との命令語で必要とするレジスタ数が異なりうる。アルゴリズムでの括弧部分はこれを反映する。特に、レジスタ書き込み演算で、Ｂｒ＿ＲＤＴ（Ｒｅｇ＿ｄｅｓｔ）の部分がソースレジスタなしに１のみに決定されてもよいが、このような場合には、当該エントリを何れもリセットした後、最後のフィールドのみを１にセッティングする。すなわち、目的レジスタに相応するＢｒ＿ＲＤＴエントリに“・・・００００１”を保存する。最後のビットを除いて、何れも０に設定されるとは、レジスタ従属性が以前と断絶されたということを意味する。図６に示すＢＢ３の“Ｒ１＝４”と同じ命令語がこれに該当する。後述する図７のＢＢ３の最後のステップで、レジスタＲ１のエントリ変化が（“ＸＸＸＸＸ１０”−＞“００００００１”がこれを示している。
【００７１】
図９は、本発明の第２ Ｂｒ＿ＲＤＴの形成アルゴリズムである。
図１０は、図８に示す本発明の第２ Ｂｒ＿ＲＤＴの形成アルゴリズムによる分岐レジスタ従属性を示す分岐フローチャートである。
図１１は、図８に示す本発明の第２ Ｂｒ＿ＲＤＴの形成アルゴリズムによるＢｒ＿ＲＤＴのアップデート過程を示す分岐履歴長表示値の形成図である。
【００７２】
図９ないし図１１を参照して、本発明の第２ Ｂｒ＿ＲＤＴの形成アルゴリズム及び分岐履歴長の表示方法を説明する。
まず、図９に示すように、ＣＰＵが分岐命令語に出合う場合と、レジスタ書き込み命令語に出合う場合とを区分して、Ｂｒ＿ＲＤＴの各エントリをアップデートする方法を説明する。
【００７３】
図９で、実行命令語がレジスタ書き込み命令語であれば、レジスタ書き込み命令語のそれぞれのソースレジスタに対するＢｒ＿ＲＤＴエントリ値を各ビット別に論理和演算を行って、その結果を、Ｂｒ＿ＲＤＴの目的レジスタの値として保存する。一方、実行命令語が条件分岐命令語であれば、分岐命令語のソースレジスタ値、または複数のソースレジスタ値の各ビット別に論理和演算を経て、最終的に分岐履歴長値を生成する。その後、Ｂｒ＿ＲＤＴの当該エントリを、１＿ビット論理シフト（ｓｈｉｆｔ ｌｅｆｔ、＜＜）する。実行命令語が無条件分岐命令語であれば、ソースレジスタを参照するか、または分岐履歴長値を生成する必要なしに、単に、Ｂｒ＿ＲＤＴの当該エントリを１＿ビット論理シフト（ｓｈｉｆｔ ｌｅｆｔ、＜＜）のみを行う。また、条件分岐のためにソースレジスタを参照する条件分岐命令語である場合には、各ソースレジスタと相応するＢｒ＿ＲＤＴエントリ値の最下位ビットを‘１’として保存する動作を行う。
【００７４】
図１０に示すように、図１０は、図７のようなシナリオを有する分岐フローチャートである。まず、分岐命令語“ｉｆ（Ｒ４）”の分岐結果は、レジスタＲ４の値と密接な関連があるということが分かる。そして、このようなレジスタＲ４の値は、ＢＢ８で、レジスタＲ１及びレジスタＲ３の値により決定（Ｒ４＝Ｒ１＋Ｒ３）される。一方、ＢＢ１０の“ｉｆ（Ｒ４）”分岐に影響を及ぼすレジスタＲ１及びレジスタＲ３は、ＢＢ２の“ｉｆ（Ｒ３）”分岐命令語とＢＢ４の“ｉｆ（Ｒ１）”分岐命令語とでそれぞれ使用される。したがって、基本的に、これらの分岐命令語は、ＢＢ１０の“ｉｆ（Ｒ４）”分岐命令語と強い相互関連性を有する。すなわち、レジスタＲ１及びレジスタＲ３の実際値によって、ＢＢ２の“ｉｆ（Ｒ３）”及びＢＢ４の“ｉｆ（Ｒ１）”の分岐方向が決定され、当該二つの分岐命令語の分岐結果によって、ＢＢ８のレジスタＲ４値の変更如何が決定される。そして、その結果によって決定されたレジスタＲ４の値は、ＢＢ１０の“ｉｆ（Ｒ４）”により分岐予測に使用される。すなわち、レジスタＲ４と相互関連のあるレジスタであるＲ１及びＲ３を使用する分岐命令語が、レジスタＲ４を使用する分岐命令語と強い相互関連性を有しうる。
【００７５】
しかしながら、二つのレジスタＲ１及びＲ３が、ＢＢ１０の分岐命令語である“ｉｆ（Ｒ４）”分岐と継続的にレジスタ従属性を有するのではない。まず、所定の制御フローチャートで、ＢＢ２の“ｉｆ（Ｒ３）”分岐で使用されたレジスタＲ３の値は、ＢＢ４の“ＬＤＲ３，ＭＥＭ”演算により、以前と存在していたレジスタ従属性が断絶され、新たにその値が定義されるということが分かる。したがって、ＢＢ２の“ｉｆ（Ｒ３）”分岐のレジスタＲ３の値は、事実上、ＢＢ１０の“ｉｆ（Ｒ４）”分岐と相互関連性が欠如する。
【００７６】
同じ方法で、ＢＢ４の“ｉｆ（Ｒ１）”分岐命令語でも、継続的にレジスタ従属性を追跡してさかのぼりうる。所定の例題では、ＢＢ３の“Ｒ１＝４”演算が相互レジスタ従属性を有する命令語である。しかしながら、ＢＢ３の“Ｒ１＝４”の演算においては、レジスタＲ１の値が、他のレジスタと関連した値を有するのではなく、独自的に新たな定数値４によりその値が再定義された。すなわち、レジスタＲ１の場合、以前の基本ブロックとの関連性がＢＢ３の“Ｒ１＝４”により断絶されたということが分かる。
【００７７】
以上の事実を通じて、ＢＢ１０の“ｉｆ（Ｒ４）”分岐は、分岐命令語間に使用されたレジスタのレジスタ従属性の観点から分析した結果、レジスタＲ１及びレジスタＲ３と相互関連性を有するが、ＢＢ４の“ｉｆ（Ｒ１）”分岐と特に強い相互関連性を有するという事実が分かる。
【００７８】
このように分析した方法を利用して、現在予測しようとする分岐命令語と強く関連しているレジスタを把握できる。特に、レジスタ間のレジスタ従属性を、分岐命令語が使用するソースレジスタ間で追跡して行くところにその特徴がある。すなわち、本発明の第２ Ｂｒ＿ＲＤＴの形成方法はあらゆるレジスタ間に存在する書き込み演算に対してレジスタ従属性を追跡して行く方式の代わりに、分岐命令語が実際使用するレジスタ間のレジスタ従属性だけを追跡して行く方法である。
【００７９】
また、図１０に示すように、分岐命令語のソースレジスタ（ｏｐｅｒａｎｄ）に示されたレジスタ間のレジスタ従属性を追跡して、最終的に関連のあるレジスタを把握した後、これを含むように誘導するアルゴリズムは、図６に示す通りである。しかし、図９のアルゴリズムは、分岐命令語と、その以前の分岐命令語との間のソースレジスタの間に相互レジスタ従属性があれば、当該分岐命令語は、相互関連性を有しうるという前提に基づく。すなわち、分岐命令語が有しているソースレジスタのレジスタ従属性を追跡していきつつ、当該ソースレジスタを使用する以前分岐命令語も、現在の分岐命令語との相互関連性が強いという仮定下でこれを追跡する。
【００８０】
図１１は、以上で説明された図１０のシナリオ下で、図９に与えられたアルゴリズムを、図５で提示されたＢｒ＿ＲＤＴ構造を使用して実行させた場合、各ステップ別の実行結果を示すＢｒ＿ＲＤＴの形成過程を示すＢｒ＿ＲＤＴの形成図である。
図１１に示すように、ＢＢ０が初めて実行される基本ブロックであると仮定するとき、Ｂｒ＿ＲＤＴのあらゆるエントリは、その値が分からない（ｕｎｋｎｏｗｎ）状態である。図１１で、Ｂｒ＿ＲＤＴの幅は、便宜上、最下位７＿ビットのみを示す。
【００８１】
ＢＢ２の開始ステップは、ＢＢ０で、ＢＢ２に分岐（Ｔａｋｅｎ）した直後の状態である。ＢＢ０の条件分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【００８２】
次のＢＢ２の最後のステップは、ＢＢ２のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ３）”を実行する直前の状態である。ＢＢ２で、レジスタ書き込み命令語Ｒ１＝Ｒ２＋Ｒ３が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタＲ２及びＲ３に相応するエントリ値を各ビット別に論理和し、目的レジスタＲ１に相応するエントリに記録する。
【００８３】
ＢＢ３の開始ステップは、ＢＢ２からＢＢ３に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ２の分岐命令語“ｉｆ（Ｒ３）”が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【００８４】
次のＢＢ３の最後のステップは、ＢＢ３のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ４）”を実行する直前の状態である。ＢＢ３で、レジスタ書き込み命令語Ｒ１＝４が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタに相応するエントリ値を各ビット別に論理和し、目的レジスタＲ１に相応するエントリに記録する動作を行う。しかし、Ｂｒ＿ＲＤＴのソースレジスタがないため、目的レジスタＲ１に相応するエントリのあらゆるビットは‘０’と記録する。
【００８５】
ＢＢ４の開始ステップは、ＢＢ３からＢＢ４に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ３の分岐命令語“ｉｆ（Ｒ４）”が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【００８６】
次のＢＢ４の最後のステップは、ＢＢ４のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ１）”を実行する直前の状態である。ＢＢ４で、レジスタ書き込み命令語ＬＤＲ３，ＭＥＭが実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタに相応するエントリ値を各ビット別に論理和し、追加的に二進数‘…０００００１’とさらに論理和して、目的レジスタＲ１に相応するエントリに記録する動作を行う。しかし、Ｂｒ＿ＲＤＴのソースレジスタがないため、目的レジスタＲ３に相応するエントリのあらゆるビットは‘０’と記録する。
【００８７】
ＢＢ８の開始ステップは、ＢＢ４からＢＢ８に分岐（Ｔａｋｅｎ）した直後の状態である。ＢＢ４の分岐命令語“ｉｆ（Ｒ１）”が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【００８８】
次のＢＢ８の最後のステップは、ＢＢ８のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語Ｒ４＝Ｒ１＋Ｒ３が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタＲ１及びＲ３に相応するエントリ値を各ビット別に論理和し、目的レジスタＲ４に相応するエントリに記録する動作を行う。
【００８９】
ＢＢ９の開始ステップ（図示せず）は、ＢＢ８からＢＢ９に分岐（Ｔａｋｅｎ）した直後の状態である。ＢＢ８の分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【００９０】
次のＢＢ９の最後のステップは、ＢＢ９のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語がないため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴは、ＢＢ９の開始ステップと比較して変更事項がない。
【００９１】
ＢＢ１０の開始ステップ（図示せず）は、ＢＢ９からＢＢ１０に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ９の分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【００９２】
次のＢＢ１０の最後のステップは、ＢＢ９のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語がないため、図９のアルゴリズムによって、Ｂｒ＿ＲＤＴは、ＢＢ１０の開始ステップと比較して変更事項がない。
【００９３】
図１１のＢＢ１０の最後のステップのＢｒ＿ＲＤＴエントリを参照すれば、ソースレジスタＲ４に該当する４番目のエントリ値が“・・・００００１００”の値を有し、０ではない最上位ビットは、最下位ビットから３ほど離れているということが分かる。そして、この値は、分岐履歴長の表示値として最終的に使用される。すなわち、ＢＢ１０の“ｉｆ（Ｒ４）”分岐方向を予測するためには、３ほどの分岐履歴を使用する。すなわち、図１１の結果は、あらゆる分岐履歴を参照するより、最下位３ほどの分岐履歴のみを使用することが、分岐方向をさらに正確に予測することを示す。すなわち、図９に提示されたアルゴリズムを通じて、当該分岐命令語の分岐結果予測において、既存に所定の分岐履歴（・・・ＴＮＮＴＴＮ）の長さで最近の３個の（ＴＴＮ）のみを利用する。
【００９４】
図９のアルゴリズムは、分岐予測において関連したレジスタ間のレジスタ従属性を追跡して、最終的に関連のあるレジスタを把握した後、これを含むように誘導する分岐命令語の履歴を選択的に使用させるアルゴリズムである。すなわち、分岐命令語のソースレジスタに影響を及ぼすレジスタを把握し、当該レジスタに対する書き込み演算を含んでいる基本ブロックへの分岐を可能にする直前分岐命令語を検索する方式である。すなわち、このように検索された分岐命令語が、現在実行しようとする分岐命令語の予測結果に強い影響を及ぼしうるという前提に基づく。
【００９５】
図１２は、本発明の第３ Ｂｒ＿ＲＤＴの形成アルゴリズムである。
図１３は、図１２に示す本発明の第３ Ｂｒ＿ＲＤＴの形成アルゴリズムによる分岐レジスタ従属性を示す分岐フローチャートである。
図１４は、図１２に示す本発明の第３ Ｂｒ＿ＲＤＴの形成アルゴリズムによるＢｒ＿ＲＤＴのアップデート過程を示す分岐履歴長表示値の形成図である。
【００９６】
図１２ないし図１４に示すように、図１２のアルゴリズムは、前述の第１ Ｂｒ＿ＲＤＴの形成方法及び第２ Ｂｒ＿ＲＤＴの形成方法の複合アルゴリズムである。言い換えれば、分岐命令語のソースレジスタに影響を及ぼすレジスタを把握し、当該レジスタに対する書き込み演算を含んでいる基本ブロックへの分岐を可能にする直前分岐命令語を検索する方法と、分岐命令語が有しているソースレジスタの間のレジスタ従属性を追跡していきつつ、当該ソースレジスタを使用する以前の分岐命令語のレジスタ従属性を追跡する方法とを相互結合する。
【００９７】
図１２で、実行命令語が、レジスタ書き込み命令語（Ｒｅｇｉｓｔｅｒ Ｗｒｉｔｉｎｇ Ｉｎｓｔｒｕｃｔｉｏｎ）であれば、レジスタ書き込み命令語のそれぞれのソースレジスタに対するＢｒ＿ＲＤＴエントリ値を、二進数‘１’と共に相互各ビット別に論理和演算を行い、その結果を、Ｂｒ＿ＲＤＴの目的レジスタの値として保存する。一方、実行命令語が、条件分岐命令語（Ｂｒａｎｃｈ Ｉｎｓｔｒｕｃｔｉｏｎ）であれば、分岐命令語のソースレジスタの値、または複数のソースレジスタ値の各ビット別の論理和演算を経て、最終的に分岐履歴長値を生成する。その後、Ｂｒ＿ＲＤＴの当該エントリを１＿ビット論理シフト（ｓｈｉｆｔ ｌｅｆｔ、＜＜）する。実行命令語が無条件分岐命令語であれば、ソースレジスタを参照するか、または分岐履歴長値を生成する必要なしに、単に、Ｂｒ＿ＲＤＴの当該エントリを１＿ビット論理シフト（ｓｈｉｆｔ ｌｅｆｔ、＜＜）のみを行う。また、条件分岐のために、ソースレジスタを参照する条件分岐命令語である場合には、各ソースレジスタと相応するＢｒ＿ＲＤＴエントリ値の最下位ビットを‘１’として保存する動作を行う。
【００９８】
図１４に示すように、図１４は、以上で説明された図１３のシナリオ下で、図１２に与えられたアルゴリズムを、図５で提示されたＢｒ＿ＲＤＴ構造を使用して実行させた場合、各ステップ別の実行結果を示すＢｒ＿ＲＤＴの形成過程を示すＢｒ＿ＲＤＴの形成図である。
【００９９】
図１４に示すように、ＢＢ０が初めて実行される基本ブロックであると仮定するとき、Ｂｒ＿ＲＤＴのあらゆるエントリは、その値が分からない（ｕｎｋｎｏｗｎ）状態である。図１１で、Ｂｒ＿ＲＤＴの幅は、便宜上、最下位７＿ビットのみを示す。
【０１００】
ＢＢ２の開始ステップは、ＢＢ０からＢＢ２に分岐（Ｔａｋｅｎ）した直後の状態である。ＢＢ０の条件分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【０１０１】
次のＢＢ２の最後のステップは、ＢＢ２のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ３）”を実行する直前の状態である。ＢＢ２で、レジスタ書き込み命令語Ｒ１＝Ｒ２＋Ｒ３が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタＲ２及びＲ３に相応するエントリ値を各ビット別に論理和し、追加的に二進数‘…０００００１’とさらに論理和して、目的レジスタＲ１に相応するエントリに記録する。
【０１０２】
ＢＢ３の開始ステップは、ＢＢ２からＢＢ３に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ２の分岐命令語“ｉｆ（Ｒ３）”が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【０１０３】
次のＢＢ３の最後のステップは、ＢＢ３のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ４）”を実行する直前の状態である。ＢＢ３で、レジスタ書き込み命令語Ｒ１＝４が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタに相応するエントリ値を各ビット別に論理和し、追加的に二進数‘…０００００１’とさらに論理和して、目的レジスタＲ１に相応するエントリに記録する。しかし、Ｂｒ＿ＲＤＴのソースレジスタがないため、目的レジスタＲ１に相応するエントリは‘…０００００１’と記録する。
【０１０４】
ＢＢ４の開始ステップは、ＢＢ３からＢＢ４に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ３の分岐命令語“ｉｆ（Ｒ４）”が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【０１０５】
次のＢＢ４の最後のステップは、ＢＢ４のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ１）”を実行する直前の状態である。ＢＢ４で、レジスタ書き込み命令語ＬＤＲ３，ＭＥＭが実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタに相応するエントリ値を各ビット別に論理和し、追加的に二進数‘…０００００１’とさらに論理和して、目的レジスタＲ３に相応するエントリに記録する動作を行う。しかし、Ｂｒ＿ＲＤＴのソースレジスタがないため、目的レジスタＲ３に相応するエントリのあらゆるビットは、‘０’と記録する。
【０１０６】
ＢＢ８の開始ステップは、ＢＢ４からＢＢ８に分岐（Ｔａｋｅｎ）した直後の状態である。ＢＢ４の分岐命令語“ｉｆ（Ｒ１）”が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【０１０７】
次のＢＢ８の最後のステップは、ＢＢ８のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語Ｒ４＝Ｒ１＋Ｒ３が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴのソースレジスタＲ１及びＲ３に相応するエントリ値を各ビット別に論理和し、追加的に二進数‘…０００００１’とさらに論理和して、目的レジスタＲ４に相応するエントリに記録する動作を行う。
【０１０８】
ＢＢ９の開始ステップ（図示せず）は、ＢＢ８からＢＢ９に分岐（Ｔａｋｅｎ）した直後の状態である。ＢＢ８の分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされる。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【０１０９】
次のＢＢ９の最後のステップは、ＢＢ９のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語がないため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴは、ＢＢ９の開始ステップと比較して変更事項がない。
【０１１０】
ＢＢ１０の開始ステップ（図示せず）は、ＢＢ９からＢＢ１０に分岐（Ｎｏｔ−Ｔａｋｅｎ）した直後の状態である。ＢＢ９の分岐命令語“ｉｆ（Ｒ２）”が実行されたため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴが左側に１＿ビット論理シフトする。したがって、あらゆるＢｒ＿ＲＤＴの最下位カラムは、‘０’で満たされた。また、前記条件分岐命令語が参照するソースレジスタに相応するＢｒ＿ＲＤＴのエントリ値の最下位ビットを‘１’と記録する。
【０１１１】
次のＢＢ１０の最後のステップは、ＢＢ９のあらゆる命令語が実行され、最後の命令語である条件分岐命令語“ｉｆ（Ｒ２）”を実行する直前の状態である。ＢＢ８で、レジスタ書き込み命令語がないため、図１２のアルゴリズムによって、Ｂｒ＿ＲＤＴは、ＢＢ１０の開始ステップと比較して変更事項がない。
【０１１２】
図１４のＢＢ１０の最後のステップのＢｒ＿ＲＤＴエントリを参照すれば、ソースレジスタＲ４に該当する４番目のエントリ値が、“・・・００１１１００”の値を有し、０ではない最上位ビットは、最下位ビットから５だけ離れているということが分かる。そして、この値は、分岐履歴長の表示値として最終的に使用される。すなわち、ＢＢ１０の“ｉｆ（Ｒ４）”分岐方向を予測するためには、５ほどの分岐履歴を使用する。すなわち、図１４の結果は、あらゆる分岐履歴を参照するより、最下位３だけの分岐履歴のみを使用することが、分岐方向をさらに正確に予測することを示す。すなわち、図１２に提示されたアルゴリズムを通じて、当該分岐命令語の分岐結果予測において、既存に所定の分岐履歴（・・・ＴＮＮＴＴＮ）の長さで最近の５個である（ＮＮＴＴＮ）のみを利用する。
【０１１３】
また、図１４に示すように、ＣＰＵが、命令語実行中に基本ブロック内にレジスタ書き込み命令語に出合えば、前述のＢｒ＿ＲＤＴの形成アルゴリズムに基づいてＢｒ＿ＲＤＴをアップデートする。また、ＣＰＵが、命令語実行中に条件分岐命令語が存在すれば、前記条件分岐命令語が参照するソースレジスタレジスタに相応するＢｒ＿ＲＤＴエントリを参照して分岐履歴長を決定する。また、Ｂｒ＿ＲＤＴ ｔａｂｌｅを左側に１＿ビットシフトし、前述のＢｒ＿ＲＤＴの形成アルゴリズムに基づいてＢｒ＿ＲＤＴをアップデートする。
【０１１４】
図１５は、図６の第１ Ｂｒ＿ＲＤＴの形成アルゴリズム及び分岐履歴長表示値の生成方法を示すフローチャートである。
図１５に示すように、分岐履歴長の表示値を生成する方法（１５２）は、フェッチされた命令語をチェックするステップ（１５１）、前記チェックした命令語が分岐命令語であるかをチェックするステップ（１５２−１）、前記チェックした命令語が条件分岐命令語であるかをチェックするステップ（１５２−２）、前記チェックした命令語が条件分岐命令語であれば、前記条件分岐命令語のソースレジスタレジスタに相応するＢｒ＿ＲＤＴエントリを読み取って、長さ表示レジスタ（Ｔｅｍｐ）に保存するステップ（１５２−４）、及び前記長さ表示レジスタに保存された長さ表示値を出力するステップ（１５２−６）を含む。前記長さ表示レジスタに保存するステップは、前記ソースレジスタが複数個であるかをチェックするステップ（１５２−３）、前記ソースレジスタが複数個である場合、読み取ったＢｒ＿ＲＤＴエントリを全て各ビット別に論理和演算を行って、前記長さ表示レジスタ（Ｔｅｍｐ）に保存するステップ（１５２−５）をさらに含むことを特徴とする。すなわち、ＣＰＵが、条件分岐命令語に出合えば、条件分岐命令語が参照するソースレジスタレジスタに該当するＢｒ＿ＲＤＴエントリを参照して、前記条件分岐命令語と関連した基本ブロックを把握する。前記各ビット別の論理和演算過程は、ソースレジスタが複数個である場合、各ソースレジスタの分岐レジスタ従属性の情報を全て継承するという意味を有する。このように、Ｂｒ＿ＲＤＴエントリを参照する過程は、分岐命令語のソースレジスタが有する分岐レジスタ従属性の情報を継承して、最終分岐履歴長の表示値を生成するためのものである。
【０１１５】
さらに、図１５を参照してＢｒ＿ＲＤＴの形成過程１５０を説明すれば、分岐履歴長表示値の生成（１５２−６）が終了した後には、Ｂｒ＿ＲＤＴのあらゆるカラムを左側に１ずつ論理シフト（１５６）するステップを含む。前記論理シフトステップは、一つの分岐命令語が実行されてからは、次の基本ブロックに進むためである。また、前記Ｂｒ＿ＲＤＴの形成過程（１５０）は、フェッチされた命令語がレジスタ書き込み命令語であるかチェックするステップ（１５４−１）、レジスタ書き込み命令語であれば、前記レジスタ書き込み命令語のソースレジスタが存在しているかをチェックするステップ（１５４−２）、前記ソースレジスタに相応するＢｒ＿ＲＤＴエントリを読み取るステップ（１５２−５）、前記読み取ったＢｒ＿ＲＤＴエントリを数字‘１’と論理和して臨時レジスタに保存するステップ（１５４−６）、及び前記臨時レジスタに保存された論理和値を、前記レジスタ書き込み命令語の目的レジスタに相応するＢｒ＿ＲＤＴエントリに保存（１５４−７）するステップを含む。前記Ｂｒ＿ＲＤＴの形成過程（１５０）は、前記レジスタ書き込み命令語のソースレジスタレジスタが複数個である場合、前記複数のソースレジスタに相応するＢｒ＿ＲＤＴエントリを全て各ビット別に論理和演算を行って、前記（１５４−６）ステップ以前に前記臨時レジスタに保存するステップ（１５４−４）をさらに含む。このように、Ｂｒ＿ＲＤＴエントリを参照する過程は、分岐命令語のソースレジスタが有する分岐レジスタ従属性の情報を継承して、目的レジスタに相応するエントリに保存するためのものである。一方、前記フェッチされた命令語がレジスタ書き込み命令語であるときには、前記分岐履歴長の表示レジスタを長さ表示値を出力するための用途として使用しないので、前記臨時レジスタは、前記分岐履歴長の表示レジスタと同じレジスタでありうる。
【０１１６】
図１６は、図９の第２ Ｂｒ＿ＲＤＴの形成アルゴリズム及び分岐履歴長表示値の生成方法を示すフローチャートである。
図１６に示すように、分岐履歴長の表示値を生成する方法（１６２）は、前述の第１ Ｂｒ＿ＲＤＴの形成方法（１５０）による分岐履歴長表示値の生成方法（１５２）と同じである。また、図１６の第２ Ｂｒ＿ＲＤＴの形成アルゴリズムによるＢｒ＿ＲＤＴの形成方法（１６０）で、分岐履歴長表示値の生成（１６２−６）が終了した後には、Ｂｒ＿ＲＤＴのあらゆるカラムを左側に１ずつ論理シフトするステップ（１６６−１）を含むことも、前述の第１ Ｂｒ＿ＲＤＴの形成方法（１５０）と同じである。前記論理シフトステップ（１６６−１）後に、前記条件分岐命令語のソースレジスタに相応するＢｒ＿ＲＤＴのあらゆるエントリ別にそれぞれ数字１と論理和演算を行って、本来のソースレジスタに相応するＢｒ＿ＲＤＴエントリに保存するステップ（１６６−２）を含む。前記論理シフトステップは、一つの条件分岐命令語が実行されてからは、次の基本ブロックに進むためであり、前記論理和演算後に保存するステップ（１６６−２）は、条件分岐命令語と、前記条件分岐命令語のソースレジスタレジスタとの間の関係を示す分岐レジスタ従属性情報をＢｒ＿ＲＤＴに記録するためである。また、前記Ｂｒ＿ＲＤＴの形成過程（１６０）は、フェッチされた命令語がレジスタ書き込み命令語であるかをチェックするステップ（１６４−１）、レジスタ書き込み命令語であれば、前記レジスタ書き込み命令語のソースレジスタが存在するかをチェックするステップ（１６４−２）、前記ソースレジスタに相応するＢｒ＿ＲＤＴエントリを、前述のステップ（１６２−５）、前記読み取ったＢｒ＿ＲＤＴエントリを臨時レジスタに保存するステップ（１６４−６）、及び前記臨時レジスタに保存された値を、前記レジスタ書き込み命令語の目的レジスタに相応するＢｒ＿ＲＤＴエントリに保存（１６４−６）するステップを含む。前記Ｂｒ＿ＲＤＴの形成過程（１６０）は、前記レジスタ書き込み命令語のソースレジスタレジスタが複数個である場合、前記複数のソースレジスタに相応するＢｒ＿ＲＤＴエントリを全て各ビット別に論理和演算を行って、前記（１６４−６）ステップ以前に、前記臨時レジスタに保存するステップ（１６４−４）をさらに含む。このように、Ｂｒ＿ＲＤＴエントリを参照する過程は、分岐命令語のソースレジスタが有する分岐レジスタ従属性の情報を継承して、目的レジスタに相応するエントリに保存するためである。一方、前記フェッチされた命令語がレジスタ書き込み命令語であるときには、前記分岐履歴長の表示レジスタを、長さ表示値を出力するための用途として使用しないので、前記臨時レジスタは、前記分岐履歴長の表示レジスタと同じレジスタでありうる。
【０１１７】
図１７は、本発明の分岐履歴長表示値の生成方法を示すフローチャートである。
図１７に示すように、分岐履歴長表示値の生成方法（１７０）でフェッチされた命令語の種類を参照して、基本ブロック単位で分岐命令語とワーキングレジスタとの間の関係を示す分岐レジスタ従属性の情報をＢｒ＿ＲＤＴにアップデートするステップ（１７１）、及び前記フェッチされた命令語のうち、条件分岐命令語のソースレジスタに相応するＢｒ＿ＲＤＴエントリを参照して分岐履歴長の表示値を生成するステップ（１７２）を含む。
【０１１８】
図１８は、本発明の分岐予測方法を示すフローチャートである。
図１８に示すように、前記分岐予測方法（１８０）は、図１７のステップ（１７１）及びステップ（１７２）と同じステップ（１８１、１８２）を経て生成された分岐履歴長情報及び分岐履歴レジスタを参照して、フィルタリングされた分岐履歴データをフィルタリングするステップ（１８３）、及び前記フィルタリングされた分岐履歴データを利用して分岐方向を予測するステップ（１８４）を含む。前記分岐方向を予測するステップ（１８４）は、前記フィルタリングされた分岐履歴データを参照して、ＰＨＴに接近するためのインデックスを生成するステップ、及び前記生成されたＰＨＴインデックスに相応して出力された分岐予測情報を参照して、現在条件分岐命令語の分岐方向を予測するステップをさらに含む。
【０１１９】
本発明では、条件分岐命令語の分岐方向を予測するために、プログラムコードを基本ブロック単位に分割し、基本ブロック単位で前記分岐レジスタ従属性の情報をメモリに保存する。また、前記保存された分岐レジスタ従属性データに基づいて、分岐履歴の有効な長さを判断し、前記分岐履歴データをフィルタリングする。前記フィルタリングされた分岐履歴データを参照して分岐予測を行う。
【０１２０】
以上で、図４ないし図１８を利用してＢｒ＿ＲＤＴの構造及び形成アルゴリズム、そして、分岐予測方法について記述した。以下では、図１９ないし図２４の実施形態によって、本発明の分岐予測器及び分岐予測システムの構造について説明する。
【０１２１】
図１９は、本発明の一実施形態である分岐履歴を使用する分岐予測器である。
図１９に示すように、分岐予測器１９０は、分岐履歴長の表示器１９１と、前記分岐履歴長の表示器１９１の出力ＬＩ及び保存された分岐履歴ＢＨを参照して、前記分岐履歴ＢＨをフィルタリングする分岐履歴フィルタリングユニット１９４と、前記保存された分岐履歴ＢＨを出力して、前記分岐履歴フィルタリングユニット１６４によってフィルタリングされた分岐履歴データＦＢＨを参照して、条件分岐命令語の分岐を予測する分岐予測ユニット１９９とを備える。前記分岐履歴フィルタリングユニット１９４は、ＣＰＵのワーキングレジスタと、前記ワーキングレジスタを参照して分岐する条件分岐命令語の間に存在するレジスタ従属性とを記録するＢｒ＿ＲＤＴ １９２から生成された分岐履歴長の表示値ＬＩを参照する。前記分岐履歴フィルタリングユニット１９４は、前記分岐履歴長の表示値ＬＩ及び前記入力された分岐履歴データＢＨを参照して、フィルタリングされた分岐履歴データＦＢＨを生成する。前記分岐予測器１９０は、前記分岐履歴フィルタリングユニット１９４でフィルタリングされた分岐履歴データＦＢＨを参照して分岐予測を行う。
【０１２２】
また、図１９に示すように、前記分岐予測ユニット１９９は、プログラムカウンタ１９５、分岐履歴メモリ１９７、パターン履歴メモリ１９８、及び前記プログラムカウンタ１９５の出力及び前記フィルタリングされた分岐履歴データＦＢＨを参照して、前記パターン履歴メモリ１９８のインデックスを生成するインデクシングユニット１９６を備える。前記インデクシングユニット１９６は、インデクシング過程で発生する制限されたＰＨＴの大きさのために発生するインデクシング重複（エイリアシングまたはインターフェランス）問題を解決するために、前記フィルタリングされた分岐履歴データＦＢＨ及び前記ＰＣ １９５値を参照して、インデクシングアドレスを調整するインデクシング演算を行う。例えば、各ビット別（ｂｉｔ−ｗｉｓｅ）に排他的論理和（ＸＯＲ）演算のようなインデクシング演算を行う。前記ＰＨＴ １９８は、各条件分岐命令語の最近の分岐実行の結果パターンが保存されたメモリである。例えば、前記ＰＨＴ １９８は、各エントリが２−ビットから構成された飽和カウンタから構成されうる。前記分岐予測器１９０は、ＰＨＴインデクシング結果によって出力された分岐予測情報Ｔ／ＮＴを利用して分岐方向を予測する。
【０１２３】
図２０は、本発明の一実施形態である分岐履歴長の表示器を示す図面である。
図２０に示すように、本発明の一実施形態に係る前記分岐履歴長の表示器２１０は、入力された条件分岐命令語のソースレジスタに相応するエントリ値ＢＳ［７：０］を参照して、有効分岐履歴データＬＩ＿ＩＮを生成する論理和ロジックゲート２０１−０ないし２０１−６を備える論理回路２０１、及び前記有効分岐履歴データＬＩ＿ＩＮを保存する長さ表示レジスタ（ＬＩＲ）２１３を備える。前記論理回路２０１は、前記条件分岐命令語のソースレジスタ数が複数個である場合、各ソースレジスタに相応するＢｒ＿ＲＤＴエントリ値を全て各ビット別に論理和する論理和回路２０２をさらに備える。前記論理回路２０１は、入力された前記入力されたエントリ値ＢＳを参照して、入力されたエントリＢＳ内のビットのうち、最も上位に位置した‘１’の値を基準に、それより高いビットは‘０’にして、それ以外のビットは‘１’を出力する分岐履歴長の表示値を生成する。
【０１２４】
図２１は、本発明の一実施形態であるフィルタリングユニットの回路図である。
図２１に示すように、本発明の一実施形態に係る前記フィルタリングユニット１９４は、入力された前記分岐履歴長の表示値ＬＩと、入力された前記分岐履歴値ＢＨとを各ビット別に論理積演算を行う論理積ゲート２１０を備える。前記フィルタリングユニット１９４は、入力された前記分岐履歴長の表示値ＬＩと、入力された前記分岐履歴値ＢＨとを各ビット別に論理積演算を行う動作を行って、入力された分岐履歴ビットのうち、上位の一部ビットを‘０’でマスキングする動作を行う。フィルタリングユニット１９４は、前記マスキング動作を行って、入力された分岐履歴データＢＨから現在分岐方向を予測しようとする条件分岐命令語と関連した基本ブロックを判断する。すなわち、現在条件分岐命令語と関連した分岐履歴のみを抽出して、分岐予測ユニット１９９を分岐予測に使用させる。
このようにして、本発明の一実施形態である図１９の分岐予測器は、既存の固定された大きさの分岐予測データを使用する分岐予測器に比べて、さらに正確な分岐予測が可能である。
【０１２５】
図２２は、本発明の一実施形態であるハイブリッド方式の分岐予測器である。
図２２に示すように、本発明のハイブリッド分岐予測器は、プログラムカウンタ２２４と、前記プログラムカウンタ２２４を参照して、Ｂｒ＿ＲＤＴに基づいた動的分岐履歴長を使用する第１分岐予測器２２１と、前記プログラムカウンタ２２４を参照して分岐を予測する第２分岐予測器２２３と、前記第１分岐予測器２２１及び前記第２分岐予測器２２４の出力のうち一つを選択する選択器２２６と、前記第１分岐予測器及び前記第２分岐予測器の予測性能に基づいて前記選択器の選択信号を出力する分岐予測器選択ユニット２２５とを備える。
【０１２６】
また、図１８に示すように、前記第２分岐予測器２２３は、飽和カウンタを備える簡単な分岐予測器でありうる。前記第２分岐予測器２２３は、“Ｃｏｍｂｉｎｉｎｇ Ｂｒａｎｃｈ Ｐｒｅｄｉｃｔｏｒｓ，Ｓｃｏｔｔ ＭａｃＦａｒｌｉｎｇ．Ｗｅｓｔｅｒｎ Ｒｅｓｅａｒｃｈ Ｌａｂｏｒａｔｏｒｙ，Ｔｅｃｈｎｉｃａｌ ｎｏｔｅ ＴＮ−３６，Ｊｕｎｅ，１９９３”に発表された飽和カウンタを参照して分岐方向を予測する分岐予測器のうち一つでありうる。
【０１２７】
図２３は、本発明の一実施形態である動的可変長の分岐予測器を使用するコンピュータシステムを示す図面である。
図２３に示すように、本発明の一実施形態であるコンピュータシステム２３０は、条件分岐命令語を備える実行プログラムを保存するメモリ２３４；Ｂｒ＿ＲＤＴ２３２、前記Ｂｒ＿ＲＤＴを備える可変分岐履歴分岐予測器２３２、前記可変分岐履歴分岐予測器２３２を備えて前記メモリから命令語をフェッチして行う中央処理処置２３１；前記メモリ２３４と中央処理処置２３１とを連結したシステムバス２３５を備える。前記コンピュータシステムは、前記メモリ２３４から条件分岐命令語をフェッチして行うとき、前記Ｂｒ＿ＲＤＴ ２３３を参照して、動的に可変される分岐履歴データを使用して分岐方向を予測する。
【０１２８】
図２４は、本発明の一実施形態である２レベル方式の分岐予測器の性能を比較するための予測失敗率の比較グラフである。
図２５は、本発明の一実施形態である２レベル方式の分岐予測器の性能を比較するためのＩＰＣ（Ｉｎｓｔｒｕｃｔｉｏｎ Ｐｅｒ Ｃｌｏｃｋ）比較グラフである。
【０１２９】
図２４及び図２５に示すように、１番目の棒は、プロファイルド−ベストであって、多様なテストプログラムを多様な長さの分岐履歴の組合わせを適用して性能測定したとき、最高の分岐予測性能を表す組合わせに対する予測失敗率とＩＰＣとを測定比較した結果である。プロファイルド−ベストは、固定された分岐履歴を使用する多様な組合わせに対する最高の性能を表す指標である。２番目の棒は、固定された長さ（Ｆｉｘｅｄ ｌｅｎｇｔｈ）は、あらゆるプログラムに一つの固定された分岐履歴を適用したときの性能指標である。３番目の棒は、本発明の動的に長さが可変される分岐履歴データを有する分岐予測器による予測結果である。特に、本発明の第１ Ｂｒ＿ＲＤＴの生成方法による分岐予測結果である。本発明によれば、本発明の第２ Ｂｒ＿ＲＤＴの生成方法及び第３ Ｂｒ＿ＲＤＴの生成方法は、前記第１ Ｂｒ＿ＲＤＴの生成方法と近似の分岐予測結果を表す（図示せず）。前記の３つのテスト結果は、ＰＨＴの大きさを５１２ｂｙｔｅと仮定したときの数値である。
【０１３０】
また、図２４及び図２５に示すように、本発明に係る分岐予測器の性能は、理想的な性能を表すプロファイルド−ベスト方式に比べて多少低いか、多少改善された数値を表す。但し、前記二つの方式の性能の差は、０.５％以内を維持する。図２４では、ＰＨＴが５１２ｂｙｔｅである場合を例にとって説明したが、ＰＨＴの大きさを変えても、類似した性能の結果が得られる。図２４に示すように、本発明の分岐予測器の分岐予測失敗率を基準にした分岐予測の性能は、プロファイルド−ベストより平均０.９％向上した。図２５に示すように、本発明の分岐予測器のＩＰＣサイクルを基準にした分岐予測の性能は、プロファイルド−ベストより平均０.９５％向上した。したがって、図２４及び２５の結果を参照すれば、本発明の動的分岐予測器は、固定長さを使用する理想的な組合わせよりもさらに優れた性能を発揮するということが分かる。
【０１３１】
以上のように、本発明によれば、分岐命令語またはレジスタ書き込み命令語と、前記命令語が参照するソースレジスタまたは目的レジスタとの間の関係を示すレジスタ従属性を把握することによって、動的に長さが変化する分岐履歴データを新たに生成し、前記新たに生成された分岐履歴データを参照して効果的な分岐予測が可能である。
【０１３２】
以上の本発明は、前述の実施形態により限定されず、当業者によって多様な変形及び変更が可能であり、これは、特許請求の範囲で定義される本発明の趣旨及び範囲に含まれる。
【産業上の利用可能性】
【０１３３】
本発明は、ＣＰＵに関連した技術分野に好適に適用されうる。
【図面の簡単な説明】
【０１３４】
【図１】一般的な２レベル方式の分岐予測器のブロック図である。
【図２】基本テストプログラムを使用した分岐履歴の長さによる分岐予測失敗率を示すグラフである。
【図３】本発明の基本ブロックの概念図である。
【図４】本発明の基本ブロックから構成された分岐フローチャートの例である。
【図５】本発明のＢｒ＿ＲＤＴの構成図である。
【図６】本発明の第１Ｂｒ＿ＲＤＴの形成アルゴリズムである。
【図７】図６に示す本発明の第１ Ｂｒ＿ＲＤＴの形成アルゴリズムを示す分岐フローチャートである。
【図８】図６に示す本発明の第１ Ｂｒ＿ＲＤＴの形成アルゴリズムによる分岐履歴長表示値の形成図である。
【図９】本発明の第２ Ｂｒ＿ＲＤＴの形成アルゴリズムである。
【図１０】図９に示す本発明の第２ Ｂｒ＿ＲＤＴの形成アルゴリズムを示す分岐フローチャートである。
【図１１】図９に示す本発明の第２ Ｂｒ＿ＲＤＴの形成アルゴリズムによる分岐履歴長表示値の形成図である。
【図１２】本発明の第３ Ｂｒ＿ＲＤＴの形成アルゴリズムである。
【図１３】図１２に示す本発明の第３ Ｂｒ＿ＲＤＴの形成アルゴリズムを示す分岐フローチャートである。
【図１４】図１２に示す本発明の第３ Ｂｒ＿ＲＤＴの形成アルゴリズムによる分岐履歴長表示値の形成図である。
【図１５】図６の第１ Ｂｒ＿ＲＤＴの形成アルゴリズム及び分岐履歴長表示値の生成方法を示すフローチャートである。
【図１６】図９の第２ Ｂｒ＿ＲＤＴの形成アルゴリズム及び分岐履歴長表示値の生成方法を示すフローチャートである。
【図１７】本発明の分岐履歴長表示値の生成過程を示すフローチャートである。
【図１８】本発明の分岐予測方法を示すフローチャートである。
【図１９】本発明の一実施形態である２レベル方式の分岐予測器である。
【図２０】本発明の一実施形態である分岐履歴長の表示器である。
【図２１】本発明の一実施形態であるフィルタリングユニットの回路図である。
【図２２】本発明の一実施形態であるハイブリッド方式の分岐予測器である。
【図２３】本発明の一実施形態である動的可変長の分岐予測器を使用するコンピュータシステムを示す図面である。
【図２４】本発明の一実施形態である２レベル方式の分岐予測器の性能を比較するための予測失敗率を比較したグラフである。
【図２５】本発明の一実施形態である２レベル方式の分岐予測器の性能を比較するためのＩＰＣを比較したグラフである。
【符号の説明】
【０１３５】
１９０  分岐予測器
１９１  分岐履歴長の表示器
１９２  Ｂｒ＿ＲＤＴ
１９３  分岐履歴長の表示ユニット
１９４  分岐履歴フィルタリングユニット
１９５  プログラムカウンタ
１９６  インデクシングユニット
１９７  分岐履歴メモリ
１９８  パターン履歴メモリ
１９９  分岐予測ユニット
ＢＨ  分岐履歴
ＦＢＨ  分岐履歴データ
ＬＩ  分岐履歴長の表示値
Ｔ／ＮＴ  分岐予測情報
【図１】
2008052684.tif 000003
【図２】
2008052684.tif 000004
【図３】
2008052684.tif 000005
【図５】
2008052684.tif 000006
【図６】
2008052684.tif 000007
【図８】
2008052684.tif 000008
【図９】
2008052684.tif 000009
【図１１】
2008052684.tif 000010
【図１２】
2008052684.tif 000011
【図１４】
2008052684.tif 000012
【図１５】
2008052684.tif 000013
【図１６】
2008052684.tif 000014
【図１７】
2008052684.tif 000015
【図１８】
2008052684.tif 000016
【図１９】
2008052684.tif 000017
【図２０】
2008052684.tif 000018
【図２１】
2008052684.tif 000019
【図２２】
2008052684.tif 000020
【図２３】
2008052684.tif 000021
【図２４】
2008052684.tif 000022
【図２５】
2008052684.tif 000023
【図４】
2008052684.tif 000024
【図７】
2008052684.tif 000025
【図１０】
2008052684.tif 000026
【図１３】
2008052684.tif 000027