(57)【要約】  本発明の実施形態は、スーパースカラプロセッサ及び分岐が許可されたその他のプロセッサにおいて効率的な分岐予測を可能にする装置及び方法に関する。本発明の一実施形態に従った分岐予測器は、実行中の命令における分岐結果を変換索引バッファからの入力を用いてプロセッサにて予測する分岐予測回路を有している。
2008501166.tif 000002
【特許請求の範囲】
【請求項１】
実行中の命令における分岐結果を変換索引バッファからの入力を用いてプロセッサにて予測する分岐予測回路を有する分岐予測器。
【請求項２】
前記分岐予測回路が：
パターン履歴表；及び
前記パターン履歴表及び前記変換索引バッファに結合された履歴シフトレジスタであり、前記変換索引バッファからの間違い信号を受けて当該履歴シフトレジスタ自身をクリアする履歴シフトレジスタ；
を有するところの請求項１に記載の分岐予測器。
【請求項３】
前記分岐予測回路が：
前記履歴シフトレジスタに結合されたメモリであり、前記変換索引バッファからの間違い信号を受けてリセット値を前記履歴シフトレジスタに渡すメモリ；
をさらに有するところの請求項２に記載の分岐予測器。
【請求項４】
前記メモリが３状態バッファを有するところの請求項３に記載の分岐予測器。
【請求項５】
前記分岐予測回路が：
前記履歴シフトレジスタに結合され、前記履歴シフトレジスタの最上位ビット値を維持するフィードバックループ；
をさらに有するところの請求項３に記載の分岐予測器。
【請求項６】
前記フィードバックループが前記最上位ビット値を１に維持するところの請求項５に記載の分岐予測器。
【請求項７】
前記履歴シフトレジスタにおける最上位の値１のビット位置が、前記履歴シフトレジスタに格納されたグローバル分岐履歴の長さを決定するところの請求項５に記載の分岐予測器。
【請求項８】
前記履歴シフトレジスタに格納された前記グローバル分岐履歴の長さが、前記最上位の値１の前記ビット位置によって定められるところの請求項７に記載の分岐予測器。
【請求項９】
前記フィードバックループが：
前記履歴シフトレジスタに結合され、前記履歴シフトレジスタの出力ビット値、及び許可信号を受け取る論理積ゲート；及び
前記論理積ゲート及び履歴シフトレジスタに結合され、前記論理積ゲートからの第１の入力値及び前記履歴シフトレジスタからの第２の入力値を受け取り、且つ新たなビット値を前記履歴シフトレジスタに出力する論理和ゲート；
を有するところの請求項５に記載の分岐予測器。
【請求項１０】
前記履歴シフトレジスタが可変長のグローバル分岐履歴を含んでいるところの請求項２に記載の分岐予測器。
【請求項１１】
前記履歴シフトレジスタが、ｍビットを有し、且つｍビットのパターン履歴値を前記パターン履歴表に排他的論理和ゲートを介して出力するところの請求項２に記載の分岐予測器。
【請求項１２】
前記排他的論理和ゲートが、ｍビットの前記パターン履歴値及びｍビットの分岐アドレス値を受け取り、且つｍビットのパターン履歴値を前記パターン履歴表に出力するところの請求項１１に記載の分岐予測器。
【請求項１３】
ｍビットのグローバル分岐履歴を有する分岐予測回路；
変換索引バッファ及び前記分岐予測回路に結合され、前記変換索引バッファの間違いを示すものを受けて前記分岐予測回路をリセットするメモリ；及び
前記分岐予測回路に結合され、前記グローバル分岐履歴の長さがm-1に等しいとき前記分岐予測回路の最上位ビット値を維持するフィードバックループ；
を有する分岐予測器。
【請求項１４】
前記分岐予測回路が：
パターン履歴表；
前記パターン履歴表及び前記変換索引バッファに結合された履歴シフトレジスタであり、前記変換索引バッファからの間違いを示すものを受けて当該履歴シフトレジスタ自身をクリアする履歴シフトレジスタ；及び
前記履歴シフトレジスタ内に表された各分岐のアドレスを格納する分岐アドレスメモリ；
を有するところの請求項１３に記載の分岐予測器。
【請求項１５】
前記メモリが前記履歴シフトレジスタに結合されているところの請求項１４に記載の分岐予測器。
【請求項１６】
前記メモリが３状態バッファを有するところの請求項１３に記載の分岐予測器。
【請求項１７】
前記フィードバックループが：
前記履歴シフトレジスタに結合され、前記履歴シフトレジスタの出力ビット値、及び許可信号を受け取る論理積ゲート；及び
前記論理積ゲート及び履歴シフトレジスタに結合され、前記論理積ゲートからの第１の入力値及び前記履歴シフトレジスタからの第２の入力値を受け取り、且つ新たなビット値を前記履歴シフトレジスタに出力する論理和ゲート；
を有するところの請求項１３に記載の分岐予測器。
【請求項１８】
変換索引バッファ；
ｍビットのグローバル分岐履歴を有する分岐予測回路；
前記変換索引バッファ及び前記分岐予測回路に結合され、前記変換索引バッファの間違いを示すものを受けて前記分岐予測回路をリセットするメモリ；及び
前記分岐予測回路に結合され、前記グローバル分岐履歴の長さがm-1に等しいとき前記分岐予測回路の最上位ビット値を維持するフィードバックループ；
を有するプロセッサ。
【請求項１９】
前記分岐予測回路が：
パターン履歴表；
前記パターン履歴表及び前記変換索引バッファに結合された履歴シフトレジスタであり、前記変換索引バッファからの間違いを示すものを受けて当該履歴シフトレジスタ自身をクリアする履歴シフトレジスタ；及び
前記履歴シフトレジスタ内に表された各分岐のアドレスを格納する分岐アドレスメモリ；
を有するところの請求項１８に記載のプロセッサ。
【請求項２０】
前記メモリが前記履歴シフトレジスタに結合されているところの請求項１９に記載のプロセッサ。
【請求項２１】
前記メモリが３状態バッファを有するところの請求項１８に記載のプロセッサ。
【請求項２２】
前記フィードバックループが：
前記履歴シフトレジスタに結合され、前記履歴シフトレジスタの出力ビット値、及び許可信号を受け取る論理積ゲート；及び
前記論理積ゲート及び履歴シフトレジスタに結合され、前記論理積ゲートからの第１の入力値及び前記履歴シフトレジスタからの第２の入力値を受け取り、且つ新たなビット値を前記履歴シフトレジスタに出力する論理和ゲート；
を有するところの請求項１８に記載のプロセッサ。
【請求項２３】
メモリ；
前記メモリに結合されたプロセッサであり、
変換索引バッファ；及び
ｍビットのグローバル分岐履歴を有する分岐予測回路；
を有するプロセッサ；
前記変換索引バッファ及び前記分岐予測回路に結合され、前記変換索引バッファの間違いを示すものを受けて前記分岐予測回路をリセットするメモリ；並びに
前記分岐予測回路に結合され、前記グローバル分岐履歴の長さがm-1に等しいとき前記分岐予測回路の最上位ビット値を維持するフィードバックループ；
を有する計算システム。
【請求項２４】
前記分岐予測回路が：
パターン履歴表；
前記パターン履歴表及び前記変換索引バッファに結合された履歴シフトレジスタであり、前記変換索引バッファからの間違いを示すものを受けて当該履歴シフトレジスタ自身をクリアする履歴シフトレジスタ；及び
前記履歴シフトレジスタ内に表された各分岐のアドレスを格納する分岐アドレスメモリ；
を有するところの請求項２３に記載の計算システム。
【請求項２５】
前記メモリが前記履歴シフトレジスタに結合されているところの請求項２４に記載の計算システム。
【請求項２６】
実行中の複数の命令の分岐結果を変換索引バッファからの入力を用いてプロセッサ内で予測するステップを有する方法。
【請求項２７】
実行中の複数の命令の分岐結果を変換索引バッファからの入力を用いてプロセッサ内で予測する前記ステップが：
前記実行中の複数の命令の各々に対して分岐結果を予測するステップ；
前記実行中の複数の命令の各々に対して予測された分岐結果を維持するステップ；及び
前記実行中の複数の命令の１つに関連するデータの変換索引バッファに間違いが生じたことを示すものを受けてグローバル分岐履歴をクリアするステップ；
を有するところの請求項２６に記載の方法。
【請求項２８】
変換索引バッファに間違いが生じたことを示すものを受けてグローバル分岐履歴をクリアする前記ステップが、：
前記グローバル分岐履歴を所定のクリア値で置換すること
を有するところの請求項２７に記載の方法。
【請求項２９】
実行中の複数の命令の分岐結果を変換索引バッファからの入力を用いてプロセッサ内で予測するステップを有する方法を実行するための実行可能な命令を格納した機械読み取り可能媒体。
【請求項３０】
実行中の複数の命令の分岐結果を変換索引バッファからの入力を用いてプロセッサ内で予測する前記ステップが：
前記実行中の複数の命令の各々に対して分岐結果を予測するステップ；
前記実行中の複数の命令の各々に対して予測された分岐結果を維持するステップ；及び
前記実行中の複数の命令の１つに関連するデータの変換索引バッファに間違いが生じたことを示すものを受けてグローバル分岐履歴をクリアするステップ；
を有するところの請求項２９に記載の機械読み取り可能媒体。
【請求項３１】
変換索引バッファに間違いが生じたことを示すものを受けてグローバル分岐履歴をクリアする前記ステップが、：
前記グローバル分岐履歴を所定のクリア値で置換すること
を有するところの請求項３０に記載の機械読み取り可能媒体。
【請求項３２】
変換索引バッファからの入力を用いて予測入力項目を選択するステップ；
前記予測入力項目及び前記入力に基づいて分岐が為されるかどうかを予測するステップ；
前記分岐が実際に為されたかどうかについての情報を受け取るステップ；
前記分岐が実際に為されたかどうかについての前記情報を用いて前記予測入力項目を更新するステップ；
前記分岐が実際に為されたかどうかを表すようにグローバル履歴値を更新するステップ；及び
次の分岐命令を取得するステップ；
を有する方法。
【請求項３３】
変換索引バッファからの入力を用いて予測入力項目を選択する前記ステップが：
前記変換索引バッファからの前記入力を用いてパターン履歴表から予測入力項目を選択すること
を有するところの請求項３２に記載の方法。
【請求項３４】
前記予測入力項目を更新する前記ステップが：
パターン履歴表内の前記予測入力項目を更新すること
を有するところの請求項３２に記載の方法。
【請求項３５】
前記分岐が実際に為されたかどうかを表すようにグローバル履歴値を更新する前記ステップが：
前記分岐が実際に為されたかどうかを表すようにグローバル・シフトレジスタ内の前記グローバル履歴値を更新すること
を有するところの請求項３２に記載の方法。
【請求項３６】
変換索引バッファからの入力を用いて予測入力項目を選択するステップ；
前記予測入力項目及び前記入力に基づいて分岐が為されるかどうかを予測するステップ；
前記分岐が実際に為されたかどうかについての情報を受け取るステップ；
前記分岐が実際に為されたかどうかについての前記情報を用いて前記予測入力項目を更新するステップ；
前記分岐が実際に為されたかどうかを表すようにグローバル履歴値を更新するステップ；及び
次の分岐命令を取得するステップ；
を有する方法を実行するための実行可能な命令を格納した機械読み取り可能媒体。
【請求項３７】
変換索引バッファからの入力を用いて予測入力項目を選択する前記ステップが：
前記変換索引バッファからの前記入力を用いてパターン履歴表から予測入力項目を選択すること
を有するところの請求項３６に記載の機械読み取り可能媒体。
【請求項３８】
前記予測入力項目を更新する前記ステップが：
パターン履歴表内の前記予測入力項目を更新すること
を有するところの請求項３６に記載の機械読み取り可能媒体。
【請求項３９】
前記分岐が実際に為されたかどうかを表すようにグローバル履歴値を更新する前記ステップが：
前記分岐が実際に為されたかどうかを表すようにグローバル・シフトレジスタ内の前記グローバル履歴値を更新すること
を有するところの請求項３６に記載の機械読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は高性能プロセッサに関し、より具体的には、変換索引バッファ（translation  look-aside  buffer；TLB）入力及び可変長グローバル分岐履歴を用いる命令分岐予測器に関する。
【背景技術】
【０００２】
分岐命令の発生率及び命令パイプライン深さがともに増大するに連れ、スーパースカラのアウトオブオーダ・プロセッサの潜在的な性能を実現するために、正確な分岐予測がますます重要になってきている。従来技術に係る幾つかの分岐予測器が、グローバル履歴を有さない分岐予測器、又はグローバル履歴を有する２段階分岐予測器の何れかとして実現されている。
【０００３】
一部の分岐予測器では、グローバル履歴はｍ個の最近の分岐から構成され、分岐が為されたか否かを各々のビットが記録するｍビットのグローバル・シフトレジスタに導入されている。残念ながら、現行のグローバル・シフトレジスタは固定長のグローバル履歴を記録するのみである。しかしながら、最近の研究により、別個のプログラムからの別個の命令は別々の長さのグローバル履歴を用いることにより、より正確に予測される場合があることが示されている。
【０００４】
図１は、技術的に既知である分岐予測器の回路ブロック図を示している。図１において、ｍビット履歴シフトレジスタ110はビットｍの単一ビットのシフト入力と、ビット１の単一ビットのシフト出力とを含んでおり、単一ビットのシフト入力は個々の命令に対して分岐が為されたか否かを示すものを受け取る。例えば、分岐が為されたことを示すために値“1”が用いられ、分岐が為されなかったことを示すために値“0”が用いられる。履歴シフトレジスタ110は、固定長（すなわち、ｍビット長）のグローバル分岐予測の履歴を格納するため、最上位ビット値すなわち最初のビット値をシフト出力するため、そして格納されるべきｍビットの分岐予測履歴値の全体を出力するために用いられる。
【０００５】
図１では、履歴シフトレジスタ110は排他的論理和（排他的OR）ゲート120に結合されており、履歴シフトレジスタ110は履歴シフトレジスタ110に格納されたｍビットのグローバル分岐予測履歴値を排他的論理和ゲート120の第１の入力に出力する。排他的論理和ゲート120は分岐アドレスレジスタ130にも結合されており、分岐アドレスレジスタ130はｍビットの分岐アドレスを排他的論理和ゲート120の第２の入力に出力する。排他的論理和ゲート120は、分岐アドレスレジスタ130からのｍビット分岐アドレス入力が履歴シフトレジスタ110からのｍビットグローバル履歴入力と一致する場合に、ｍビットのグローバル履歴をパターン履歴表140に出力する。分岐アドレスレジスタ130からのｍビット分岐アドレスは、履歴シフトレジスタ110からの出力とビット数を合わせるために、出力される前にシフトされ、拡張され、あるいは切り取られる。その結果、グローバル分岐予測履歴値の長さは変化する場合があるが、分岐アドレスレジスタ130からのｍビット分岐アドレスビットストリング出力のビット数は、履歴シフトレジスタ110からのグローバル分岐予測値入力のビット数と常に一致する。
【０００６】
図１では、パターン履歴表140は2m個の入力項目で構成されており、この表内の各入力項目は“ローカル履歴”を含んでいる。ローカル履歴情報は一般に２ビット飽和（saturated）分岐予測器に格納される。排他的論理和ゲート120からのｍビットのグローバル履歴出力は、パターン履歴表140から１つの入力項目を選択するために用いられ、そして、選択された１つの入力項目は予測を実行するために用いられる。この設計によって確かな予測入力項目が用いられ、別個の分岐命令が互いに相関関係を有する有効な履歴情報が格納される。
【０００７】
図１では、２ビット分岐予測器は２ビットカウンタを保持している。それは、参照されるとその内容に基づいて分岐予測を出力する。例えば、ある１つの分岐に対し、その分岐に割り当てられた予測器（すなわち、パターン履歴表の入力項目）の２ビットの内容が“10”である場合、分岐が“為される”と予測する。しばらくして実際の指示が判明した後、その内容が更新される。例えば、分岐が“為された”場合は“10”は“11”に更新され、分岐が“為されなかった”場合は“10”は“01”に更新される。一般に、２ビットカウンタ値がその最大値の1/2すなわち22-1=2以上であるとき、分岐が為されると予測される。逆に、２ビットカウンタ値が2未満であるとき、分岐は為されないと予測される。換言すれば、２ビットカウンタが“10”（すなわち、2）又は“11”（すなわち、3）の何れかを含んでいるときは分岐が為されると予測され、２ビットカウンタが“00”（すなわち、0）又は“01”（すなわち、1）の何れかを含んでいるときは分岐が為されないと予測される。
【０００８】
ローカル履歴は分岐の出力がそれ自身の履歴に依存することを意味するものであるが、グローバル履歴は分岐の出力がその他の分岐の履歴に依存することを暗示するものである。以下の短いコードの例では、第１の分岐が“為される”を出力する場合、第２の分岐もまた“為される”を出力する。そして、この情報をこのグローバル履歴及び２段階（two-level）分岐予測手法を用いて維持するために、無関係な２ビット分岐予測器（グローバル履歴を有するパターン履歴の入力項目が分岐d==0に対応して採用される）が用いられることになる。
【０００９】
If(d==0)    //  もし  d=0
d=1；  //  ならば  d=1  に設定
If(d==1)    //  もし  d=1
…      //  ならば  d=1条件命令を継続する
残念ながら、図１のグローバル履歴レジスタ110は何れの場合にも固定長のグローバル履歴を記録するのみであるため、固定長のグローバル履歴に基づく分岐予測は十分に優れたものではない。例えば、固定長のグローバル履歴に基づく分岐予測は、先行の分岐命令が現下の分岐命令と相関関係を有するとしても、先行の分岐命令を常に正確に識別するわけではない。同様に、固定長のグローバル履歴を用いると、相関関係のないその他の分岐命令だけでなく、一部の文脈に相関が存在し、相関が存在すべきその他の文脈に相関が存在しない分岐命令も常に正確に予測されるわけではない。例えば、以下のコードの例で、メモリ・オペランドX、Yがデータ位置に起因して近接値を有すると仮定する。分岐予測器は上述のように機能し得る。しかしながら、この関係はデータ位置の喪失を伴って損なわれることになる。
【００１０】
If(d==0)    //  もし  d=0
d=X；  //  ならば  d=X  に設定
If(d==Y)    //  もし  d=Y
…      //  ならば  d=Y条件命令を継続する
この事例は、グローバルな相関はグローバル履歴又は分岐アドレスだけでなくデータ位置をも当てにするときがあることを示している。上記の例で示されたようなデータ位置の喪失は、第２の命令でdがXに等しく設定され、且つ第３の命令でdがYに等しくないと決定されるときに発生する。その結果、d=Yの条件命令は実行されない場合がある。これはまたグローバル履歴を損ね得るものである。故に、上述の欠陥を回避した分岐予測を備えることが望ましい。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、上述の欠陥を回避した分岐予測を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の実施形態は、変換索引バッファ（translation  look-aside  buffer）相関型分岐予測の装置及び方法に関し、以下に限られないが、動的制御される可変長の分岐履歴を有する場合と有しない場合の双方における、グローバル履歴の変換索引バッファ相関型分岐予測器、及び／又は２段階（two-level）の変換索引バッファ相関型分岐予測器を含む。例えば、本発明の一実施形態に従ったプロセッサは、変換索引バッファからグローバル分岐履歴シフトレジスタへの入力用配線を具備した相関型分岐予測器を有している。入力用配線は、変換索引バッファ内に間違いが生じている状態を示し得るものであり、グローバル分岐履歴シフトレジスタの内容を消去（クリア）するために使用可能である。グローバル分岐履歴シフトレジスタに格納されたグローバル分岐履歴はデータの局所性によって鍛えられ得るので、変換索引バッファの間違い時にグローバル分岐履歴シフトレジスタをクリアすることは、変換索引バッファからの間違ったデータによって引き起こされるデータの非局所性からの破損されたグローバル分岐履歴を無効にする助けとなり得る。
【発明を実施するための最良の形態】
【００１３】
図２は、本発明の一実施形態に従った、プロセッサ用の変換索引バッファ相関型分岐予測器の回路ブロック図である。図２において、プロセッサ200はｍビットの履歴シフトレジスタ210を有している。履歴シフトレジスタ210は、（図１の単一ビットシフト入力に類似とし得る）第１の単一ビットのシフト入力、第２の単一ビットのシフト入力、及び（図１の単一ビットシフト出力に類似とし得る）単一ビットのシフト出力を有しており、第１の単一ビットシフト入力は個々の命令に対して分岐が為されたか否かを示す信号を受け取る。履歴シフトレジスタ210は、実行中の命令に対する可変長のグローバル分岐履歴を格納するために用いられ得る。一般に、妥当な履歴長を特定するために、値“1”を有する最上位ビットが用いられる。例えば、最上位の“1”がｍビットのシフトレジスタの５番目のビットにある場合、グローバル履歴はm-5ビットの長さに決定され得る。その結果、最上位の“1”の値は分岐が起こったか否かを表さない。本発明の一実施形態に従って、“1”の値は分岐が為されたことを表す許可信号として使用され、“0”は分岐が為されなかったことを表す不許可信号として使用されてもよい。履歴シフトレジスタ210はm-1ビットの最大長を有する可変長のグローバル分岐予測履歴を格納するため、そして最上位ビット値すなわちm-1ビットの値を出力するために用いられてもよい。故に、“0000…01”のストリングは、グローバル履歴が履歴シフトレジスタ210から最近消去されたことを指し示す長さゼロのグローバル履歴を表してもよい。同様に、本発明の一実施形態に従って、“0000…00”のストリングは、存在しないグローバル履歴長を表すので意味がないとして扱われてもよく、“1X…Y”ストリング（X及びYは各々“0”又は“1”に等しい）は、レジスタが含み得る最長のグローバル履歴長、すなわち、m-1ビットの長さを含むとして扱われてもよい。
【００１４】
図２では、履歴シフトレジスタ210は排他的論理和（排他的OR）ゲート220に結合されており、履歴シフトレジスタ210は、履歴シフトレジスタ210に格納されたｍビットのグローバル分岐予測履歴の値を排他的論理和ゲート220の第１の入力に出力する。また、排他的論理和ゲート220は分岐アドレスレジスタ230に結合されており、分岐アドレスレジスタ230はｍビットの分岐アドレスを排他的論理和ゲート220の第２の入力に出力する。排他的論理和ゲート220は、分岐アドレスレジスタ230からのｍビットの分岐アドレス入力が履歴シフトレジスタ210からのｍビットのグローバル履歴入力と一致する場合、ｍビットのグローバル履歴をパターン履歴表240に出力する。分岐アドレスレジスタ230からのｍビット分岐アドレスは、履歴シフトレジスタ210からの出力とビット数を合わせるために、出力される前にシフトされ、拡張され、あるいは切り取られ得る。その結果、グローバル分岐予測履歴値の長さは変化する場合があるが、分岐アドレスレジスタ230からのｍビット分岐アドレスビットストリング出力のビット数は、一般に、履歴シフトレジスタ210からのグローバル分岐予測値入力のビット数と常に一致する。
【００１５】
図２では、パターン履歴表240は2m個の入力項目で構成されており、この表内の各入力項目は“ローカル履歴”を含んでいてもよい。ローカル履歴情報は一般に２ビット飽和（saturated）分岐予測器に格納され得る。排他的論理和ゲート220からのｍビットのグローバル履歴出力は、パターン履歴表240から１つの入力項目を選択するために用いられてもよく、また、選択された１つの入力項目は予測を実行するために用いられてもよい。この設計によって確かな予測入力項目が用いられ、別個の分岐命令が互いに相関関係を有する有効な履歴情報が格納される。
【００１６】
一般に、図２では、履歴シフトレジスタ210は図１にて述べられたように、２つの例外、すなわち、グローバル分岐履歴が消去されるべきとき、及びX、Y及びZは各々“0”又は“1”に等しいとしてグローバル履歴ストリングの値が“1XYZ…”に等しいとき、を設けてシフトする。第１に、図２において、履歴シフトレジスタ210が消去されるべき場合、履歴シフトレジスタ210内のグローバル分岐履歴ストリングがクリアされ“0000…01”に設定される。第２に、履歴シフトレジスタ210が履歴シフトレジスタ210の最上位ビット（すなわち、ビット1）に“1”が格納されてもよいことを意味するm-1ビット長のグローバル分岐履歴を含んでいるとき、ビット1に格納された値“1”は維持され、ビット2のビット値がシフトアウトされる。
【００１７】
履歴シフトレジスタ210はまた、例えば３状態バッファ等のラッチメモリ250に結合され、ラッチメモリ250は変換索引バッファ“ＴＬＢ”（図示せず）からＴＬＢ内に間違いがあったかどうかを示す信号を受け取り得る。また、ラッチメモリ250はｍビットの入力クリア値を受け取って格納し得る。このｍビットの入力クリア値は、“1”である右端の数字を除いて全て“0”を含む。例えば、m=16の場合、16ビットの入力クリア値は“0000000000000001”である。ＴＬＢ（図示せず）に間違いが生じると、ＴＬＢに間違いが生じたことを表す許可信号がＴＬＢによってＴＬＢ間違いライン260上で有効状態にされる。ＴＬＢに間違いが生じたことを表す許可信号がラッチメモリ250に到達すると、ラッチメモリ250に格納されたｍビット入力クリア値が履歴シフトレジスタ210に読み込まれる。その結果、履歴シフトレジスタ210は“クリアされ”、履歴シフトレジスタ210にその時点で格納されていたｍビット値が、ラッチメモリ250からのｍビット値、例えば“0000000000000001”、で上書きされる。
【００１８】
図２では、フィードバック回路270が履歴シフトレジスタ210のビット1の位置とビット2の位置とに結合されている。フィードバック回路270は論理積（AND）ゲート280を有しており、論理積ゲート280は履歴シフトレジスタ210に結合されて出力の最上位ビットを受け取るとともに論理和（OR）ゲート290にも結合されている。論理和ゲート290は履歴シフトレジスタ210のビット1及びビット2の位置に結合されている。フィードバック回路270は、履歴シフトレジスタ210のm-1ビット位置に最上位ビット値1を維持するために用いられ得る。具体的には、論理積ゲート280の第１の入力281は履歴シフトレジスタ210の出力に結合されている。論理積ゲート280の第２の入力283は値“1”を受け取り、その値は履歴シフトレジスタ210の出力値と掛け合わされて論理積値となり、論理積ゲート280から出力287を介して論理和ゲート290の第１の入力291に出力される。論理和ゲート290の第２の入力293は履歴シフトレジスタ210のビット2の位置に結合され、そこから値を受け取る。論理和ゲート290の出力297は履歴シフトレジスタ210のビット1の位置に結合され、そこに論理和値を出力する。論理積ゲート280の第２の入力283は一定の入力である“1”を有するので、２つの入力の組み合わせ（0,1）及び（1,1）のみが可能である。すなわち、論理積ゲート280からの取り得る出力値は２つのみであり、履歴シフトレジスタ210のm-1ビット位置の出力値も“1”である場合には論理積ゲート280から“1”が出力され、履歴シフトレジスタ210のm-1ビット位置の出力値が“0”である場合には論理積ゲート280から“0”が出力されることになる。同様に、論理和ゲート290もまた同じ２つの取り得る出力値（すなわち、“0”又は“1”）を有するのみであるが、その結果は４つの取り得る入力の組み合わせ、すなわち、（0,0）、（0,1）、（1,0）及び（1,1）から生じる。なぜなら、論理和ゲート290への第１の入力291及び第２の入力293の何れも単一の値には限定されていないからである。
【００１９】
【表１】
2008501166.tif 000003
表１に示された論理和の論理表に見られるように、取り得る４つの入力値の組み合わせのうちの３つの結果として“1”が出力される。故に、履歴シフトレジスタ210のビット1の値が“1”であるとき論理積ゲート280は常に“1”を出力するので、履歴シフトレジスタ210がＴＬＢの間違いによってクリアされるまで、フィードバック回路はビット1の位置に値“1”を維持することが分かる。
【００２０】
本発明の実施形態は、フェッチ／復号化ユニットが例えば命令キャッシュ等の記憶位置からマクロ命令等の命令を取得してその命令を復号化するアウトオブオーダ・プロセッサに実装され得るものである。複数命令セットコンピュータ（Complex  Instruction  Set  Computer；“ＣＩＳＣ”）アーキテクチャでは、フェッチ／復号化ユニットは複雑な命令を１つ又は複数のマイクロ命令／操作に復号化し得る。通常、これらのマイクロ命令は負荷記憶型アーキテクチャを定義し、メモリ操作を含むマイクロ命令が、例えば、縮小命令セットコンピュータ（Ｒeduced  Instruction  Set  Computer；“ＲＩＳＣ”）又は超長命令語（Very  Long  Instruction  Word；“ＶＬＩＷ”）アーキテクチャ等の、その他のアーキテクチャで実行され得る。
【００２１】
典型的なＲＩＳＣアーキテクチャでは、命令はマイクロ命令には復号化されない。本発明はＣＩＳＣアーキテクチャだけでなくＲＩＳＣアーキテクチャでも実行され得るものであるので、特に断らない限り命令とマイクロ命令／操作との間で区別は設けず、単純にこれらを命令と呼ぶことにする。
【００２２】
図３は、本発明の一実施形態に従った方法の流れ図である。図３では、例えばパターン履歴表240から、ＴＬＢからの入力を用いて予測入力項目が選択され（310）、選択された予測入力項目及びＴＬＢ入力に基づいて分岐が為され得るかどうかが動的に予測される（320）。当該方法は分岐が実際に為されたかどうかについての情報を受け取り（330）、分岐が実際に為されたか否かに基づいて予測入力項目が更新される（340）。例えば、予測入力項目はパターン履歴表240内で更新される（340）。分岐が実際に為されたかどうかを表すグローバル履歴値とパターン履歴表240とが、例えば、分岐が実際に為されたかどうかに基づいて履歴シフトレジスタ210内で更新される。そして、次の分岐命令が取得される（360）。当該方法は、一般に、プロセッサの電源が落とされたとき、又はさらなる命令の処理が実行されないときにのみ終了する。
【００２３】
これに代わる本発明の一実施形態では、明示されていないが、図３の方法は更なる分岐命令がすぐには取得されない場合に、終了してから更なる分岐命令を待ってもよい。
【００２４】
図３の方法は、当該方法を実行する特定の順序に触れているが、本発明の実施形態を上記の順序に限定するものと解釈されるべきものではない。本発明では、実際、当該方法の構成要素の一部又は全てが如何なる順序でも実行され得る実施形態も意図される。例えば、以下には限られないが、全体的又は部分的にアウトオブオーダ（“ＯＯＯ”）プロセッサにて並列に実行されることが意図される。同様に、図示された事例では、図３の方法は一度に１つの分岐を処理することを反映するように単純化されているが、本発明では、当然ながら既存のデータの従属関係によって制限されるものの、複数の分岐が同時に処理され得る実施形態も意図される。
【００２５】
以下の単純化された疑似コード部分は、本発明の一実施形態に従ったＴＬＢ相関型グローバル履歴分岐予測器を実動させる操作を例示している：
check_and_initialize_predictor(argc,argv,&inTrace,&aPredictor);
while(!inTrace->EndOfTrace()){
aPredictor->SelectPredictionEntry(inTrace->GetAddress(),
inTrace->TLBMissOrNot());  //ＴＬＢ情報をここに
bool  pr-taken=aPredictor->prediction(inTrace->ForwardBranchOrNot());
//静的予測許可
aPredictor->UpdatePredictor(inTrace->TakenOrNot(),pr~taken);
//実際の分岐対象の判明後、
//  パターン履歴表の更新及びグローバルレジスタのシフト
inTrace->read~trace();  //シミュレーションで次の分岐命令の読み込み
}
aPredictor->ShowAccuracyo;
例えば、上記の擬似コードで、予測器は命令の実行中に命令に含まれる各分岐の結果を予測し、実際の結果の判明後それを用いて予測を更新するように動作することが分かる。上記の擬似コード例は直列実行を暗に示すものであるが、これは単に全体概念を例示しているに過ぎず、当然ながら境界内（inter-bound）のデータの従属関係に応じてであるが、分岐の並列実行及び／又はアウトオブオーダ実行が為される他の実施形態も意図される。
【００２６】
図４は、本発明の一実施形態に従って使用される、１つ又は複数のプロセッサ及びメモリを含むコンピュータシステムのブロック図である。図４では、コンピュータシステム400は、プロセッサ・バス420に結合された１つ又は複数のプロセッサ410(1)乃至410(n)を含んでおり、プロセッサ・バス420はシステムロジック430に結合されている。１つ又は複数のプロセッサ410(1)乃至410(n)の各々はNビットのプロセッサであり、復号器（図示せず）及び１つ又は複数のNビットレジスタ（図示せず）を含んでいてもよい。システムロジック430は、バス450を介してシステムメモリ440に結合されており、また、周辺バス460を介して不揮発性メモリ470及び１つ又は複数の周辺装置480(1)乃至480(m)に結合されている。周辺バス460は、例えば、ＰＣＩ分科会のＰＣＩローカルバス仕様書2.2版（1998年12月18日出版）にある１つ又は複数の周辺部品相互接続（Peripheral  Component  Interconnect；ＰＣＩ）バス、業界標準アーキテクチャ（Industry  Standard  Architecture；ＩＳＡ）バス、ＢＣＰＲサービス社のＥＩＳＡ仕様書3.12版（1992年）にある拡張（Extended）ＩＳＡ（ＥＩＳＡ）バス、ＵＳＢ仕様書1.1版（1998年9月23日出版）にあるユニバーサル・シリアル・バス（ＵＳＢ）、及び類似の周辺バスを表す。不揮発性メモリ470は、例えば読み出し専用メモリ（ＲＯＭ）又はフラッシュメモリ等のスタティックメモリ装置とし得る。周辺装置480(1)乃至480(m)は、例えば、キーボード、マウス若しくはその他のポインティング装置、ハードディスクドライブ、コンパクトディスク（ＣＤ）ドライブ、光ディスク、及びデジタル・ビデオディスク（ＤＶＤ）ドライブ等の大容量記憶装置、ディスプレー並びにこれらに類するものを含み得る。
【００２７】
本発明について詳細に述べてきたが、様々な変更、代替及び改変が為され得ることは理解されるべきところである。さらに、特定の機能を制御するソフトウェア及びハードウェアについて説明されているが、技術的に周知のように、このような機能はソフトウェア、ハードウェア、又はそれらの組み合わせの何れを用いて実現されてもよい。同様に、請求項における“命令”という用語は、ＲＩＳＣアーキテクチャでの命令又はＣＩＳＣアーキテクチャでの命令、及びその他のコンピュータ・アーキテクチャで用いられる命令を包含し得るものである。他の実施例が、当業者によって容易に確認され、特許請求の範囲によって定められる本発明の意図及び範囲を逸脱することなく作り出される。
【図面の簡単な説明】
【００２８】
【図１】従来の分岐予測器の回路ブロック図である。
【図２】本発明の一実施形態に従った、プロセッサ用の変換索引バッファ相関型分岐予測器の回路ブロック図である。
【図３】本発明の一実施形態に従った方法の流れ図である。
【図４】本発明の一実施形態に従って使用される、１つ又は複数のプロセッサ及びメモリを含むコンピュータシステムのブロック図である。
【図１】
2008501166.tif 000004
【図２】
2008501166.tif 000005
【図３】
2008501166.tif 000006
【図４】
2008501166.tif 000007
【国際調査報告】
2008501166.tif 000008
2008501166.tif 000009