JPH10510076A - 限定ラン分岐予測 - Google Patents

Abstract

(57)【要約】 条件的分岐命令の方向を正しく予測する傾向を高める分岐予測技術を提供する。本発明の技術は、多くの分岐が、一定または緩やかに変化するラン長さ、すなわち１の幾つかの連続ランが同じ長さを有するとの見解に基づくものである。本発明の技術は、各分岐について記憶されたヒストリーであって、２つの小さなカウンタ（１０２、１１３）すなわちアップカウンタ（１０２）およびダウンカウンタ（１１３）により高められるヒストリーを使用する。これらのカウンタ（１０２、１１３）は、非常に正確な予測について従来技術のステートマシンの分岐予測子（１０１）に関連して作動する。

Description

【発明の詳細な説明】 限定ラン分岐予測 発明の背景 パイプラインプロセッサの性能は、条件的分岐の実行に要する時間により厳格 に制限される。通常、プロセッサは、命令を連続態様でフェッチしかつ実行する 。すなわち、アドレスからフェッチされた命令Ｅｉの直後に実行される命令Ｅｉ ＋１（Ｅｉの直後の要素）は、ｎにＥｉの長さを加えることにより求められる。 無条件的分岐は、非連続アドレスでの命令への制御の転送を引き起こす。或るコ ンピュータでは、分岐命令Ｂの目的アドレスは命令内に含まれ、一方、目的は、 命令Ｂ内に含まれるオフセットを、命令Ｂ自体がフェッチされたアドレスに加え ることにより形成される。 条件的分岐命令は、幾つかのデータの試験に基づいて、制御の転送を条件的に 引き起こす。このような命令は、目的アドレスの仕様と一緒に、試験すべき条件 を含んでいる。この条件は、一般に、数字の代数的属性の小さなセットの１つで あり、数字は、零または非零、正または非正、負または非負等である。条件が適 合する場合には、分岐がなされる（すなわち、直後の要素の命令が分岐の目的ア ドレスからフェッチされる）。条件が適合しない場合には、直後の要素の命令は 、非分岐命令としての次の連続命令である。 パイプラインコンピュータは、各命令を、幾つか（通常、少なくとも５つ）の 処理段からなるパイプラインに通す。新しい命令は、各クロックサイクル中にパ イプラインに入れられる。この結果、パイプラインコンピュータは、異なる実行 段での幾つかの命令をもつことができ、従って各段でのハードウェア資源の利用 を最小にする。 パイプラインコンピュータの条件的分岐により引き起こされる性能低下は、試 験すべきデータの代数的条件が決定される前に分岐がフェッチされるときに生じ る。この現象は、分岐命令自体が試験すべきデータの位置を特定する構成のこれ らのコンピュータにおいては最悪である。代数的条件は、パイプラインの幾つか の段が走査(traversed)された後にのみ評価される。これは分岐命令がフェッチ されるまで開始されないので、試験すべき条件は、分岐がフェッチされた後の幾 つかのクロックサイクルまで知られない。フェッチされるべき次の命令の位置は 、データが試験されるまで確実に決定されないので、幾つかのクロックサイクル についていかなる命令もフェッチされない。 分岐予測は、条件的分岐をフェッチすると瞬時に、試験の成果の決定を待機す ることなく、分岐がなされるか否かを予測する試みである。このようにして、命 令は全速力で取出し続けられる。分岐が予測されると、この予測の妥当性を実証 しかつ正しくない予測から回復することが必要になる。予測が正しくない場合に は、誤って予測された（「悪い」）分岐後にフェッチされた全ての命令がエラー としてフェッチされ、このため、これらの実行の効果を逆にしなければならない 。予測した分岐を記録し、妥当性を実証しかつ修復する技術は本発明の要旨では ない。 悪い分岐の後にフェッチされた全ての命令は廃棄しなければならないので、こ れらは廃棄努力を表す。従って、マシンの性能は、分岐予測の精度に直接関係す る。 分岐予測スキームは、静的または動的に構成できる。静的スキームでは、分岐 命令自体が予測を含んでいる。すなわち、これは、一般に、一般的なデータセッ トでプログラムを実行するコンパイラーに基づいて、プログラムを作ったコンパ イラーにより供給される。静的予測は、コンピュータの命令セットがこれを考慮 に入れて設計されている場合にのみ可能である。商業的に成功している殆どの命 令セットは、静的分岐予測を可能にする設備を提供しない。 動的分岐予測は、プログラム実行中にハードウェアにより集められる分岐に関 する情報を使用している。ハードウェアは所与の分岐命令の過去の実行パターン について「知っている」に過ぎず、このため、その動的分岐予測はこのような情 報に基づかなくてはならない。条件的分岐は非常に頻繁（５つの命令毎に１つの 密度）であるので、各々について記憶されるヒストリーの量は、非常に大きな記 憶容量を必要としないで非常に大きくすることはできない。一般に、分岐予測情 報は極く僅かに維持されるが、プログラムの分岐の部分集合（subset）を変化さ せる。 プログラムの実行中の任意の時点での所与の分岐命令の正しい実行ヒストリー は、二進記号１および０のシーケンスとして表される。このシーケンスは、分岐 命令が（１）を取るか、（０）を取らないかを見分ける。分岐命令が実行される 度毎に、当該分岐のヒストリーは、分岐の正しい（必ずしも予測したものではな い）実行がなされたか否かに基づいて、その終時に１または０を加えることによ り延長される。 分岐命令の実行ヒストリーは、ランに分割できる。分岐ランは、１だけ直前お よび直後（またはこの逆）の連続０のシーケンスである。すなわち、ヒストリー における各記号は正確に１つのランであり、各ランは全ての０または全ての１か らなる。ランの長さは、ランにおける記号の個数である。 従来技術の動的分岐予測機構は、プログラムの多くの分岐について、０のラン の全てまたは殆ど全てが長いものであるという見解を用いている。これらは、通 常、ループを終了させる分岐である。ループは、一般に、該ループの本体を構成 する連続命令の終時に条件的分岐を設けることにより実施される。条件的分岐は ループ終了条件を試験し、この条件が正当でない場合にはループ本体であるシー ケンスの第１命令に分岐する。分岐がなされない場合には、ループは終了される 。この分岐が実行される次の時点はループの次の付勢での第１実行であり、これ は、この付勢が一走査(one traversal)後に終了しない限り行なわれる。従って 、ループの終了を表す単一０（single 0）からなるランがある。（幾つかのコン パイラーは、本体の終時ではなく開始時における条件的分岐でループを構成する 。このようなループは、分岐が行なわれると終了する。このループ構造は、単一 １(single 1)からなるランでヒストリーを実行させる）。 従来技術の分岐予測子は、各予測を、各分岐について記憶されたヒストリーの ２ビットに基づかせている。これらのビットは、４状態のステートマシン（第１ 図）の状態である。このステートマシンの効果は、分岐が、１より大きい長さの 最終ランと同じ成果を得ることを予測することである。従って、その実行ヒスト リーが２つ以上の０のランをもたないように、常に１回以上走査されるループの 場合には、予測は一定になるであろう。 この従来技術のステートマシンの予測精度は、１のランの長さに直接関係して いる。平均ラン長さがｎである場合には、ｎ個の全ての正しい予測について１つ の正しくない予測がある。かくして、短いランほど効率が悪くなる。本発明の目 的は、短いラン長さの分岐についての予測精度を改善することにある。 発明の要約 多くの分岐は、一定であるか緩やかに変化するラン長さを有する（すなわち、 １の幾つかの実行ランが同じ長さを有する）。本発明は、２つの小さなカウンタ （アップカウンタおよびダウンカウンタ）を加えることにより、各分岐について 記憶されるヒストリーを向上させる。カウンタは、従来技術のステートマシン分 岐予測子に関連して作動する。 アップカウンタは、現在ランの長さをカウントする。カウンタがオーバーフロ ーする前にランが終了する場合には、アップカウンタの値がダウンカウンタにコ ピーされ、アップカウンタはゼロに再初期化される。次に、ダウンカウンタは、 次のランの間にカウントダウンする。使用される予測は、ダウンカウンタがゼロ に達するまでステートマシンにより作られた予測である。ダウンカウンタがゼロ であるときの第１実行で、ステートマシン予測が補完される。これは、現在ラン の長さが先行ランの長さに等しいときには、正しい。ラン長さが一定に維持され る限り、本発明の予測精度は１００％である。ランがカウントされるよりも長い 場合には、カウンタが作動不能になり、予測はステートマシンにのみ基づいて行 なわれる。 任意の条件的分岐Ｂが発行される各時点でその予測ヒストリーが試験され、分 岐を予測すべきか否か、およびヒストリーが予測に部分的に基づいて瞬時に更新 されているかを決定する。更新は、これがＢの再発行であるか否かに基づいても 行なわれる。Ｂの再発行は、Ｂの任意の実行ＢＥが正しくなく予測されたそのと きに生じ、今や正しい方向が知られ、かつＢＥに先行するいかなる分岐の実行も 、正しくなく予測されていないことが判明する。この場合、ＢＥについての分岐 修復が行なわれ、連続するあらゆる命令のＢＥおよび全ての実行が廃棄されかつ Ｂが再発行される。 カウンタを更新するためのアルゴリズムは、ステートマシン予測子が常に同じ 方向を予測するとの仮定に基づいている。従って、ランの終時はカウンタのみに より予測される。再発行とは、ラン長さが正しく予測されなかったこと、すなわ ち、ラン長さについていかなる予測もなされなかったか、ラン長さの予測が短過 ぎまたは長過ぎたことを意味する。先行ランが長過ぎてカウントできないために ラン長さが全く予測されなかった場合で、新たに開始するランが短くて充分にカ ウントできる場合には、アップカウンタが０にセットされかつダウンカウンタが −１にセットされ、これにより予測子が不能にされる。ランが期待されたよりも 早期に終了したため再発行分岐が誤って予測された場合には、より短い新しい長 さがアップカウンタからダウンカウンタにコピーされかつアップカウンタが０に リセットされる。予測されたラン長さが短過ぎる場合には、アップカウンタが、 より長い正しい長さをカウントするように増大を続け、かつこのより長いランの 終時が正しく予測されないことを知るので、ダウンカウンタが−１にセットされ る。 再発行ではない分岐の任意の発行時に、アップカウンタがその最大カウントに 到達すると、カウンタは当該カウントに留まり、ダウンカウンタは−１にセット されて、あらゆるラン長さ予測を防止する。一方、アップカウンタは、ダウンカ ウンタが０でなければ増大され、ランの予測終時を表示する。この場合、アップ カウンタがダウンカウンタにコピーされ、次に０にリセットされる。アップカウ ンタがその最大値になくかつダウンカウンタが不能状態にない場合には、ダウン カウンタは、これが０に到達していなければ減少する。 本発明により各分岐について記憶しなければならない付加情報は実質的なもの である。好ましいことは、少数のビットにより高性能ゲインが得られることであ る。３ビットカウンタは、７より小さい全ての一定ラン長さを正しく予測する。 正しく予測されない最短のラン長さ（７）は、ステートマシン予測子のみから８ ７％の精度を有している。４ビットカウンタは少なくとも９３％の精度が得られ る。 好ましい実施例の説明 本発明の好ましい実施例は、スーパースカラープロセッサ（superscalar proc essor）にある。スーパースカラープロセッサは、単一クロックサイクル当たり の多数（この場合、４つ）の命令を取出してパイプラインに発行する。プロセッ サの全ての要素が本発明にとって関係するものではないので、これらの要素のう ちの幾つかの要素は本発明の説明には含めない。「プロセッサアーキテクチャー （Processor Architecture）」という名称に係るPopescu 等による１９９０年１ ２月５日付米国特許出願第07/622,893号を参照されたい。 本発明の分岐命令の予測に関し、全ての分岐の実行ヒストリーが２つの構造（ すなわち、プロセッサの分岐予測ＲＡＭ１０および分岐シェルフ２０）に記憶さ れる。分岐予測ＲＡＭ１０は、最古の未解決予測分岐までの（但し、該未解決予 測分岐は含まない）分岐実行の全てのヒストリーを記憶する。分岐シェルフ２０ は未解決予測分岐である（または未解決予測分岐に続く）全ての分岐実行のヒス トリーを保持する。 好ましい実施例では、分岐予測ＲＡＭ１０は１Ｋ（1024）ワードからなる。分 岐予測ＲＡＭ１０を読取るため、プロセッサのプログラムカウンタレジスタ１１ は、値ＰＣ（value PC）を用いてアドレスバス１３を介してＲＡＭ１０にアドレ スする。ＰＣは、次にプロセッサで取出される命令のメモリアドレスである。分 岐予測ＲＡＭ１０は、４つのデータ出力ポートDOUT 0〜DOUT 3を有し、これらは それぞれ出力ライン１４Ａ〜１４Ｄに接続されている。これらの４つのポートに は、それぞれ４つのアドレスＰＣ、ＰＣ＋１、ＰＣ＋２およびＰＣ＋３での命令 についての分岐予測状態が通され、プロセッサのスーパースカラー特性に適合さ れる。もちろん、本発明は、簡単なスカラーにも等しく適用できることを理解す べきである。 分岐予測ＲＡＭ１０は倍長語アドレスされている。すなわち、アドレスバス１ ３を通るＰＣの最下位ビットは無視される。従って、２つの連続命令（一方の連 続命令は偶数ＰＣ値、他方の連続命令は次に高い奇数ＰＣ値）が、必然的に、分 岐予測ＲＡＭ１０からの同じ予測ヒストリーに割当てられる。２つの連続分岐命 令が現れることは希であり、このため、１ＫディープＲＡＭ（1K-deep RAM）１ ０は、２Ｋ命令までのユニークな予測ヒストリーを記憶する。 分岐予測ＲＡＭ１０はキャッシュではない。そのコンテンツ（内容）は、所与 の分岐命令の予測状態を正確に反映するものでもよいし、反映しなくてもよい。 例えば、ＰＣ値が正確に２Ｋの倍数だけ異なる２つの命令は別名である。両命令 のヒストリーは同じＲＡＭ語で記憶され、このため、破壊的に干渉するであろう 。これは、分岐予測ＲＡＭ１０が予測機構に過ぎず、あらゆる分岐予測が後で実 証されかつ正しくない場合には修復されるため許容される。従って、破壊的別名 付け（destructive aliasing）は、予測精度（従って性能）の潜在的低下の場合 にのみ生じる。すなわち、分岐予測ＲＡＭ１０のサイズは、性能低下に対して釣 合いがとれたものである。 分岐シェルフ２０は、全ての推論的分岐命令の予測ヒストリーを記憶する１２ ディープコンテントアドレッサブル先入れ先出し構造（12-deep content-addres sable First-In First-Out（FIFO）structure）である。正しい方向が未だ知ら れていない予測分岐実行であるか、該予測分岐実行に続く全ての命令実行は、推 論的実行（speculative executions）である。分岐シェルフ２０は、アドレスバ ス１３に接続されるサーチポートと、後述の３つのライン３７Ｂ、３９、４０に 接続される入力ポートと、分岐予測ＲＡＭ１０に接続される更新ポートとを有す る。 分岐シェルフ２０は、推論的分岐実行の分岐予測ヒストリーを、これらが発行 される順序に記憶する。分岐シェルフ２０に記憶された各エントリーは本発明に 関連する２つの部分（すなわち、条件的分岐命令の予測ヒストリーおよび命令の アドレス）を有している。付加エントリー信号４０が真（すなわち、論理「１」 ）であるとき、各クロックサイクルで、１つの新しいエントリーが、入力ポート を介して分岐シェルフ２０に付加される。 分岐シェルフ２０は棚のスタックのように作動する。各エントリーは、「最下 方」の空位置に書込まれ、最下方位置は、更新ポートを介して分岐予測ＲＡＭ１ ０に取り出すことができる。更新ポートは３つのライン、すなわち、分岐シェル フ２０の最下方位置の条件的分岐命令の予測ヒストリーデータを転送するデータ バス１９Ａと、最下方位置の条件的分岐命令のアドレスを転送するアドレスバス １９Ｂと、書込み作動を遂行すべきであることを分岐予測ＲＡＭ１０に信号伝達 する書込み許可制御ライン１９Ｃとを有する。この取出しが生じると、分岐シェ ルフ２０の全てのエントリーが１つにシフトダウンされる。分岐修復には、誤 予測されたことが発見された分岐実行へのエントリーを、この上の全てのエント リーと一緒に削除することが含まれる。このようにして、分岐シェルフ２０の全 ての有効エントリーは、これらが入れられる順序で、最下方エントリーから連続 的に記憶される。 ＰＣ値が、アドレスバス１３を介して分岐シェルフ２０のサーチポートに入力 されると、ＰＣ、ＰＣ＋１、ＰＣ＋２およびＰＣ＋３アドレスが、記憶された各 分岐命令アドレスと比較され、かつ付加エントリー信号が真である場合には入力 ポートでのアドレスと同時に比較される。これらの比較の結果は、４つのデータ 出力ポートBOUT 0〜BOUT 3で、分岐シェルフ２０から送られる。分岐シェルフ２ ０の各データ出力ポートは２つの部分を有しかつ２セットのラインに接続される 。１つのセットは、各ポートBOUT 0〜BOUT 3の１ビットマッチライン２２Ａ〜２ ２Ｄである。他のセットは、記憶された各分岐命令アドレスに対する予測ヒスト リーデータについて、それぞれ各ポートBOUT 0〜BOUT 3のデータバス２１Ａ〜２ １Ｄである。これらの出力ポートのマッチライン２２Ａ〜２２Ｄは、それぞれＰ Ｃ、ＰＣ＋１、ＰＣ＋２またはＰＣ＋３とマッチする少なくとも１つの記憶され たアドレスである場合にのみ論理「１」を搬送する。マッチライン２２Ａ〜２２ Ｄが論理「１」であるあらゆるポートについては、該ポートでの対応する予測ヒ ストリーデータは、そのアドレスがマッチする最上方（すなわち、最も後に入れ られた）エントリー（ここで、入力ポートの値は最上方であると考えられる）に 記憶されたデータである。 マッチライン２２Ａ〜２２Ｄは、それぞれ、２対１マルチプレクサ１５Ａ〜１ ５Ｄに接続されかつ該マルチプレクサを制御する。論理１でのマッチライン２２ Ａ〜２２Ｄを備えた各データ出力ポートBOUT 0〜BOUT 3について、対応するマル チプレクサ１５Ａ〜１５Ｄは分岐シェルフ２０からデータバス２１Ａ〜21Dを選 択する。前記ポートからの予測ヒストリーデータは、当該マルチプレクサ１５Ａ 〜１５Ｄへの出力として選択される。データ出力ポートのマッチライン２２Ａ〜 ２２Ｄが論理０である場合には、対応するマルチプレクサ１５Ａ〜15Dの出力は 、分岐予測ＲＡＭ１０の対応するデータ出力ポートDOUT 0〜DOUT 3から、バス１ ４Ａ〜１４Ｄを介して予測ヒストリーデータを選択する。 この構成では、４つのマルチプレクサ１５Ａ〜１５Ｄの出力は、ＰＣ、PC＋1 、ＰＣ＋２、ＰＣ＋３での任意の分岐についての最も新しい予測ヒストリーであ る。任意の時点で、ＰＣ＋ｉ（ここで、ｉは０、１、２、３）に分岐命令Ｂが存 在する場合には、２つの可能性（すなわち、Ｂの推論的実施が存在しないか、１ つ以上の推論的実施が存在するか）が存在する。前者の場合には、分岐シェルフ ２０からのＰＣ＋１に対応するマッチライン２２Ａ〜２２Ｄは論理０であり、こ のため、マルチプレクサ１５Ａ〜１５Ｄの出力は、分岐予測ＲＡＭ１０から対応 する出力バス１４Ａ〜１４Ｄを介して出力される。マルチプレクサ１５Ａ〜１５ Ｄからの出力信号は、その最も新しい実行による分岐命令Ｂ（この場合には、非 推論的である）を表す。 Ｂの推論的実行が存在する場合には、分岐シェルフ２０の出力ポートBOUT 0〜 BOUT 3のうちの１つのポートからのマッチライン２２Ａ〜２２Ｄが論理１信号を 搬送し、当該ポートの予測ヒストリー出力は、Ｂの最も新しい推論的実行の後の 出力である。全ての推論的実行は、全ての非推論的実行より新しいので、これは 最も新しい実行でありかつ対応するマルチプレクサ１５Ａ〜１５Ｄにより出力と して選択される。 各マルチプレクサ１５Ａ〜１５Ｄの出力バスは、４つの同一予測モジュール１ ６Ａ〜１６Ｄのうちの１つの入力バスである。第３図に示す各予測モジュール１ ６Ａ〜１６Ｄは、それぞれのマルチプレクサ１５Ａ〜１５Ｄからの予測ヒストリ ーデータを試験して、分岐命令の現在の実行の予測を決定する。予測ヒストリー データは、２ビット予測状態、３ビットアップカウンタ値および３ビットダウン カウンタ値からなる８ビットを有する。予測ヒストリーデータは、各マルチプレ クサ１５Ａ〜１５Ｄの出力バスを形成する８つのバスラインで搬送される。 各予測モジュール１６Ａ〜１６Ｄは、ＮＯＲゲート２３および排他的ＯＲゲー ト２４を有している。ＮＯＲゲート２３は、入力としてダウンカウンタの３ビッ トを受入れ、ＮＯＲゲート２３の出力は１つの入力として排他的ＯＲゲート２４ に接続される。排他的ＯＲゲート２４への第２入力は予測状態の上位のビットお よび予測状態ビットの状態〔１〕である。第３図に示すように、下位ビット、状 態〔０〕およびアップカウンタの３ビットが、ＮＯＲゲート２３および排他的 ＯＲゲート２４に接続することなく、予測モジュール１６Ａ〜１６Ｄに通される 。 ステートマシンにより与えられる予測は、状態、状態〔１〕の最上位ビットに 等しいことは理解されよう。ゼロのダウンカウンタ値（論理０に等しい３つの全 てのビット）は、ＮＯＲゲート２３に出力論理１を発生させ、これにより、排他 的ＯＲゲート２４に状態〔１〕の値を補完させる。ダウンカウンタがゼロでない 場合には、ＮＯＲゲート２３は論理０の出力を有し、これにより、排他的ＯＲゲ ート２４に状態〔１〕の値を出力させる。排他的ＯＲゲート２４の出力は予測値 である。 予測モジュール１６Ａ〜１６Ｄの出力、および予測ヒストリーデータの８ビッ トプラスＰＣ＋ｉ（i＝１〜３）での４つの各命令についての現在の予測は、そ れぞれ、命令デコードＦＩＦＯ２５の入力ポート２６Ａ〜２６Ｄに接続される。 ＦＩＦＯ２５は５つの命令深層(instructions deep)であり、かつ命令が、命令 キャッシュ（図示せず）から取出されるときからプロセッサのパイプラインの実 行段に発行されるまで命令を記憶する。４つまでの命令の予測ヒストリーデータ は、入力ポート２６Ａ〜２６Ｄで各クロックサイクルに付加できる。予測ヒスト リーデータは、最下方の空位置からのアドレスを増大させるため付加される。す なわち、入力ポート２６Ａ（該ポートは、ＰＣでの命令についての予測ヒストリ ーを受入れる）を通るデータは、ＦＩＦＯ２５の最下方空エントリーに入る。入 力ポート２６Ｂを通るデータはこの直ぐ上に入り、以下同様に行なう。 命令の予測ヒストリーは入力ポート２６Ａに入力されるけれども、命令アドレ スおよびＰＣは、ＦＩＦＯ２５のアドレス入力ポート３０を通ってバス１３によ り供給される。命令デコードＦＩＦＯ２５は、この中に記憶された各命令に関連 する論理を含んでおり、これからのアドレスが取出される。 命令発行論理５０は、命令デコードＦＩＦＯ２５の４つの最下方命令デコード ＦＩＦＯ２５を試験する。命令発行論理５０の１次応答性は、命令デコードFIFO ２５の各命令について、命令を「発行」できる時点すなわちプロセッサパイプラ インにおける次の状態まで前進される時点を決定する。命令発行論理５０が遂行 すべき２つの仕事は、（１）発行された各命令の結果のアベイラビリティ（可用 性）および位置をトラッキングすること、および（２）命令デコードＦＩＦＯ ２５における各命令の、前に発行された命令への依存性を決定することである。 これらの仕事を如何に遂行するかの詳細は、本発明とは無関係である。 命令発行論理５０が次のパイプライン段への命令を発行するとき、命令発行論 理５０は、命令デコードＦＩＦＯ２５の下方（bottom）から命令を取出す。好ま しい実施例では、命令デコードＦＩＦＯ２５内の前記下方の命令より「下」の全 ての命令が発行されなければ、いかなる命令も発行されない。従って、命令デコ ードＦＩＦＯ２５は真のＦＩＦＯ（先入れ先出し）である。 命令デコードＦＩＦＯ２５が分岐命令を含んでいる場合には、命令発行論理５ ０が最下方のこのような命令を試験する。それが非条件的分岐である場合には、 命令発行論理５０は２つの特定ステップ、すなわち、（１）命令がフェッチされ るシーケンスを変えるため分岐命令により指向されるように、プログラムカウン タレジスタ１１を変化させる段、および（２）命令デコードＦＩＦＯ２５の「最 上方(top)」から実行すべきではない、分岐に続くこれらの命令を取り出す段を 遂行する。 命令デコードＦＩＦＯ２５の最下方命令が条件的分岐である場合には、命令発 行論理５０は、上記のようにして、（１）前に発行したどの命令（単一または複 数）にこの分岐が基づいているか、（２）これらの先行命令が可用性を有するか 、可用性を有するとすれば、これらの結果の値はいくつか、を決定する。分岐が 基づいている全ての結果が知られている場合には、命令発行論理５０は、これら の結果を評価して、分岐命令を行なうべきか、行なわないべきかを決定する。分 岐命令を行なう場合には、命令発行論理５０は、上記２つのステップ、すなわち プログラムカウンタレジスタ１１を変更すること、および命令デコードＦＩＦＯ ２５から、後続の全ての廃棄命令を除去することを遂行する。 命令デコードＦＩＦＯ２５の最下方分岐命令が条件的分岐でありかつ該分岐命 令が基づいている結果に可用性がない場合には、命令発行論理５０は予測を用い て分岐の廃棄を決定する。この予測は予測モジュール１６Ａ〜１６Ｄにより発生 されかつ分岐命令により、入力ポート２６Ａ〜２６Ｄを介して命令デコードFIFO に書き込まれる。再び、分岐が予測される場合には、プログラムカウンタレジス タ１１のコンテンツが変更されかつ分岐に続く命令がＦＩＦＯ２５から廃棄され る。 分岐シェルフ２０の書込みを制御する命令発行論理５０により発生される３つ の制御信号出力が存在する。アッドエントリー信号４０は、条件的分岐命令が発 行される（すなわちＦＩＦＯ２５の下方から取り出される）全てのクロックサイ クルでの論理１である。アッドエントリー信号４０が論理１であるときにはいつ でも、２ビットの選択分岐信号３５は、発行される分岐命令のＦＩＦＯにおける インデックスであり、取出し信号（Taken signal）４１は、分岐がなされた場合 には論理１であり、分岐がなされない場合には論理０である。 命令デコードＦＩＦＯ２５は４つの出力ポートFOUT 0〜FOUT 3有し、該ポート FOUT 0〜FOUT 3には、それぞれ、データバス３１Ａ〜３１Ｄおよびアドレスバス ３２Ａ〜３２Ｄに接続される。これらの各出力ポートFOUT 0〜FOUT 3は２ピース の情報、すなわち、データバス３１Ａ〜３１Ｄの１つのＦＩＦＯ２５に記憶され た予測ヒストリーおよび対応するアドレスバス３２Ａ〜３２Ｄの関連命令アドレ スを発生する。これらの４つの出力ポートFOUT 0〜FOUT 3は、命令ＦＩＦＯ２５ の最下方の４つのエントリーを出力する。 データバス３１Ａ〜３１Ｄおよびアドレスバス３２Ａ〜３２Ｄは、２つの選択 制御ライン３５を有するマルチプレクサ３６の入力ターミナルに接続される。制 御ライン３５の命令発行論理５０により発生される選択分岐制御信号は、命令デ コードFＩＦＯ２５の４つの出力のうちの最古の条件的分岐のインデックスであ る。この制御信号は、マルチプレクサ３６に、それぞれアドレスバス３７Ｂおよ びデータバス３７Ａの出力として、出力ポートFOUT 0〜FOUT 3のうちの１つから 、当該最古の分岐のアドレスおよび予測状態情報を選択させる。アドレスバス37 Bは、分岐シェルフ２０の入力ポート１８に直接接続される。 データバス３７Ａの予測状態情報は更新モジュール３８に向かう。モジュール ３８は、後述のようにして、予測状態を「更新」しかつ当該データを、分岐シェ ルフ２０の入力ポート１８Ａに接続されたライン３９に導く。命令発行論理５０ からの制御ライン４０のアッドエントリー信号は、命令デコードＦＩＦＯ２５の 条件的分岐命令が発行されると、入力ポート１８Ａ、１８Ｂでのアドレスおよび 更新状態情報が分岐シェルフ２０に書き込まれるようにする。 ランダム論理メモリまたはＲＯＭベースメモリに実施される更新モジュール３ ８は、４状態分岐予測子およびアップカウンタおよびダウンカウンタのための新 しい値をつくり出す。分岐予測子のこの新しい値は、第１図の状態図に示すよう にして計算される。当該ステートマシンへの入力は、命令発行論理５０により発 生された取出し信号４１である。その値は、分岐がなされる場合には論理１であ り、分岐がなされない場合には論理０である。 第４図は、更新モジュール３８がアップカウンタおよびダウンカウンタのため の新しい値を計算するアルゴリズムを示す。モジュール３８は、最初に、ステッ プ１０１で、分岐の予測方向が正しくないことが知られているか否かを決定する 。これは、分岐が基づいているデータが知られていること、および予測モジュー ル１６Ａ〜１６Ｄにより発生されかつ命令デコードＦＩＦＯ２５に記憶された予 測方向が正しい方向ではないことを必要とする。 予測が誤りであることが知られていない場合には、パス２０２に進み、アップ カウンタが試験されて、ステップ１０２で、アップカウンタがその最大値に到達 しているか否かを決定する。最大値に到達している場合には、分岐ラン長さは、 これらのカウンタによりトラッキングするには長過ぎる。パス２０３に進み、ス テップ１０３で、ダウンカウンタが最大値（本発明の実施例では７）にセットさ れる。これは、分岐ラン予測を不能にする効果を有する。なぜならば、ダウンカ ウンタが減少することはなく、従って決してゼロに到達しないからである。アッ プカウンタは既に最大値に到達しているので、変更されることはない。 アップカウンタがその最大値に到達していない場合には、パス２０４に進む。 ステップ１０４、１０５により、ダウンカウンタは、これが最大値、ゼロまたは これらの中間値にあるか否かが試験される。ダウンカウンタが中間値にある場合 には（ステップ１０４、１０５の後で、それぞれパス２０５、２０６に進み）、 これは、この分岐については分岐ラン予測が不能になっておらず、分岐ランが予 測ランの終時に到達していないことを意味する。従って、ダウンカウンタは、ス テップ１０７により１だけ減少される。なぜならば、今や、予測ランの終時に近 い１分岐実行になっているからである。 ステップ１０４で、ダウンカウンタがその最大値にあると決定された場合には 、 アップカウンタはステップ１０８により１だけ増大される。かくして、現在ラン の長さは、分岐ラン予測子が不能になった場合でも、（カウンタが最大値に到達 するまで）常にアップカウンタ内に維持される（ステップ１０４の後、パス207 に進む）。 ステップ１０５で、ダウンカウンタがゼロであると決定された場合には、パス ２０８に進む。ダウンカウンタには、ステップ１０９で、アップカウンタの現在 値が再ロードされ、次に、ステップ１１０でアップカウンタが再初期化される。 ゼロにあるダウンカウンタは予測ランの終時を意味する（すなわち、第１分岐は 逆方向に進む）。ダウンカウンタへのアップカウンタのコピーイングは、次のラ ンが、丁度終了したばかりのランと同じ長さになるであろう。アップカウンタの ０へのセッティングは、この１つの逆分岐の後の次の分岐が、新しいランでの最 初の分岐になることを予測する。従って、単一分岐により逆方向に分離された（ 最大カウンタ値より小さい）一定長さのランをもつ分岐は、常に正しく予測され るであろう。 ステップ１０１に戻り、分岐予測が誤っていることが判明した場合には、パス ２１０に進む。ステップ１１１で、アップカウンタが最大値にあるか否かを決定 すべくチェックされる。カウンタが最大値に到達した場合には、完了したばかり の現在ランが、（正しくない予測により表示されたように）カウンタにとって長 くなり過ぎるけれども、次のランは充分に短くなる。パス２１１に進み、ステッ プ１１２において、ダウンカウンタは最大値にセットされ、分岐ラン予測子を不 能にするけれども、アップカウンタは、ステップ１１０で再初期化される。 ステップ１１１で、アップカウンタがその最大値に到達していないことが決定 されると、パス２１２に進む。ステップ１１３で、ダウンカウンタがゼロである か否かがチェックされる。ダウンカウンタがゼロであれば、現在ランは終了した （すなわち、予測長さが短過ぎた）と、正しくなく予測されたことになる。この 場合にはアップカウンタがこのランの実際の長さをカウントしており、このカウ ントが続けられる。パス２１３に進み、ステップ１１４でダウンカウンタが最大 値にセットされ、現在ラン中にこれ以上予測することが防止される。アップカウ ンタはステップ１０８で増大される。 ステップ１１３で、ダウンカウンタがゼロでないことが決定された場合には、 現在ランは、未だ終了していないと正しくなく予測された（すなわち、予測され た長さは長過ぎた）ことになる。現在ランの実際の長さを保持するアップカウン タは、ダウンカウンタにコピーされ、ステップ１０９により、次のランが同じ長 さのランであることを予測する。次に、ステップ１１０で、アップカウンタがゼ ロに再初期化される。 第５Ａ図は、３つの一定ラン長さをもつ分岐についての分岐予測子の定常状態 挙動を示す。左端欄は分岐予測子の状態を示し、また、「アップ」欄はアップカ ウンタの値を、「ダウン」欄はダウンカウンタの値を、「予測」欄は分岐予測子 からの予測ビットを示す。右端欄は分岐の実際の方向を示し、この欄で、１は選 択された分岐を意味し、０は選択されない分岐を意味する（これらの値を逆にす れば、同じ挙動が得られるであろう）。この欄は、１つの０の後に、３つの１が 続く反復パターンを示している。この場合、優勢方向（predominant direction ）が１であるので、４つの状態予測子は常に１を予測する。その予測は最上位の 状態ビットである。なぜならば、０の逆ランは１より長くはなく、このステート マシンの状態の最下位ビットのみが常に変化するからである。 第５Ａ図の第１列に示すように、ダウンカウンタはゼロであり、アップカウン タはランの長さ（３）に等しい。ダウンカウンタのゼロの値は、分岐予測子のス テートマシンにより与えられる予測（この予測は１である）が、予測モジュール １６Ａ〜１６Ｄにより補完されるようにする。この０分岐が発行されかつ分岐シ ェルフ２０に書き込まれると、更新モジュール３８は、アップカウンタが最大値 より小さくかつダウンカウンタがゼロであるという事実に応答して、ステップ１ ０９で、アップカウンタをダウンカウンタにコピーしかつステップ１１０でアッ プカウンタをゼロにリセットする。 次の時点でこの分岐がフェッチされ、第５Ａ図の第２列に与えられた値が、分 岐シェルフ２０または分岐予測ＲＡＭ１０のいずれかにより読み取られる。この とき、予測モジュール１６Ａ〜１６Ｄは非ゼロのダウンカウンタ値を確認し、従 って１の非修正ステートマシン予測を可能にする。この分岐が発行されると、更 新モジュール３８はアップカウンタが最大値より小さくかつダウンカウンタがゼ ロと最大値との間の中間値にあることを確認する。従って、更新モジュール３８ は、ステップ１０７でダウンカウンタを簡単に減少させかつステップ １０８で アップカウンタを増大させる。これと同じ挙動が次の２回反復され、分岐がフェ ッチされかつ発行される。第５Ａ図の列５に示すこの１のランの終時に、ダウン カウンタは再びゼロに到達し、これにより、予測が再び補完されかつカウンタが 再初期化されて次のランをカウントする。 第５Ｂ図は、長さ３のランの後に短いランが続くときの挙動を示し、長さ２の この場合には、長さ４の長いランが続く。第５Ｂ図の第１列に示す状態では、長 さ３の先行ランの終時が、第５Ａ図に示すように正しく予測されている。カウン タは、次のランも長さ３になると仮定して再初期化される（第２列）。アップカ ウンタは増大されかつダウンカウンタは列３および列４を通って減少される。列 ４では、予測は依然として１である。なぜならば、予測ランが完了していないけ れども、実際の方向は０だからである。 次の時点で、列４で発行される分岐の正しい方向が知られる。分岐修復機構は 当該分岐の効果およびこれに続く全ての命令を廃棄する。次に、この分岐が再フ ェッチおよび再発行される。再フェッチ（列４′で示す）時のステートマシンお よびカウンタの値は、元のフェッチ（列４で示す）にあったときと同じ値である 。分岐修復機構が、分岐シェルフ２０に対するあらゆる修正を含む元の発行の全 ての効果を取り出しているので、これらの修正は分岐予測ＲＡＭ１０には決して 書き込まれない。なぜならば、分岐が未だ解決されていないからである。 修復の後で分岐が再発行されると、更新モジュール３８が、０の既知の正しい 方向に対し、予測（これは、再び１である）を比較し、予測が誤っていることを 決定する。ステップ１０１の後は、パス２１０に進む。第５Ｂ図の列５に示すよ うに、アップカウンタが最大値より小さくかつダウンカウンタがゼロでないので 、更新モジュール３８はアップカウンタをダウンカウンタにコピーしかつアップ カウンタを０にリセットする。かくして、分岐ラン予測子は、次のランが長さ２ になることを予測するようにセットされる。 アップカウンタおよびダウンカウンタは、列６および列７における２の予測ラ ン長さをカウントアウトする。ダウンカウンタがゼロであるので、列７で発行さ れる分岐はランの終時であると予測される。従って、予測は０に変更される。こ れは、正しくない予測であると後で発見されるため、列７′に示すように、分岐 は予測子のための同じ値が再発行される。この時点で、更新モジュール３８は、 ステップ１０１で、予測が誤っていることを決定し、かつパス２１０に再び進む 。ステップ１１１で、アップカウンタが最大値でないことを決定した後、次のス テップ１１３で、ダウンカウンタがゼロであることを決定する。この場合、ラン の実際の長さは未だ知られていないので、その終時を予測することはできない。 従って、ステップ１１４でダウンカウンタが最大値にセットされ、ランの終時を 予測するあらゆる試みを防止する。アップカウンタは増大を続け（ステップ１０ ８）、現在ランの長さをカウントする。 ダウンカウンタが不能になっているので、列８、９での予測が、ステートマシ ン予測子から直接なされる。列９で発行された分岐は１であると予測されかつ０ （０は、長さ４のランの終時を示す）であることが発見される（列５、６、７、 ８）。分岐が再発行されると（列９′）、更新モジュール３８は、ステップ101 で、この予測が誤っていたことを再び決定する。ステップ１１１の後、パス212 に進み、ステップ１１３で、ダウンカウンタがゼロでないと決定され、これによ り、ステップ１０９でアップカウンタがダウンカウンタにコピーされ、ステップ １１０でアップカウンタがゼロに再初期化される。従って、列１０では、分岐ラ ン予測子は、次のランが長さ４になることを予測するようにセットされる。 分岐ラン予測子を用いないで、第５Ｂ図に示す例の全ての分岐は、１であると 予測されるであろう。従って、列４、９の分岐は正しく予測されないことがあろ うが、列７の分岐は正しく予測されているであろう。すなわち、７より短いラン に長いランが続くときには、特別な分岐修復が行なわれる。列４におけるように 、７以下の長さのランに短いランが続く場合には、分岐ラン予測子を用いて（ま たは用いることなく）、修復が行なわれる。短いランに同じ長さのランが続く場 合には、いつでも、分岐ラン予測子は分岐修復を回避する。 一定のまたはゆっくりと変化するラン長さの分岐についての分岐予測速度は、 本発明の使用により極めて改善される。急速に変化するラン長さの分岐は、ラン 長さの正確な分布により、悪い性能を有するであろう。 以上、本発明の好ましい実施例について完全に説明したが、種々の変更および 均等物を使用できるであろう。上記実施例に適当な変更を加えることにより、本 発明を等しく適用できることは明らかである。従って、上記説明が本発明の範囲 を制限するものではなく、本発明の範囲は請求の範囲の記載により定められるも のである。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 イーザマン ディヴィッド エル アメリカ合衆国 カリフォルニア州 92131 サンディエゴ アヴェニダ マグ ニフィカ 10232

Claims (1)

1. 【特許請求の範囲】 １．コンピュータシステムの実行用命令メモリから、非条件的制御転送命令およ び条件的制御転送命令の両方を有する命令のシーケンスをフェッチングする方法 において、 各クロックサイクルにおいて、プログラムカウンタに保持された命令から始 まる連続アドレスで、命令メモリから１つ以上の命令を読取るステップと、 前記１つ以上の命令からの各制御転送命令を、非条件的命令、条件的かつ取 り出すべきものと知られた命令、取り出すべきではないと知られた命令、または 推論的命令に級別するステップと、 シーケンスにおける各推論的制御転送命令についての制御条件を予測するス テップと、 非条件的命令、取り出すべきものと知られた命令、または取り出すべきもの と予測された命令である第１制御転送命令により指向された次のクロックサイク ルの前記読取りステップのためのプログラムカウンタを変えるステップとを有し 、 上記フェッチング方法は、命令メモリに記憶された条件的分岐を制御する条 件が不変のルーピング挙動を呈する場合には、前記条件をいつでも正確に予測し 、各ループがｎ回同じくその条件を有し、該条件とは逆の条件が１回続くことを 特徴とするフェッチング方法。 ２．前記条件がルーピング挙動を呈する場合には、条件的分岐を制御する条件を いつでも正しく予測し、各ループが１回以上からなり、条件は同じ優勢値であり 、これには逆の条件が１回続き、該条件はループにあり、ループの長さは直前ル ープと同じであることを特徴とする請求の範囲第１項に記載のフェッチング方法 。 ３．前記条件がルーピング挙動を呈し、かつ現在ループおよび直前ループの長さ は或る定数より小さい場合には、条件的分岐を制御する条件をいつでも正しく予 測することを特徴とする請求の範囲第２項に記載のフェッチング方法。 ４．前記条件がルーピング挙動を呈する場合には、条件的分岐を制御する条件を 正しく予測し、先行ループの長さは前記定数に等しいかこれより大きく、この条 件的分岐は現在ループの終時における条件的分岐ではなく、その条件は該ループ のうちの他の全てのループの条件とは逆であることを特徴とする請求の範囲第３ 項に記載のフェッチング方法。 ５．２つ以上のフェッチを列に最も新しく保持すべく、知られたまたは予測され た値として分岐条件のための優勢値を確立することを特徴とする請求の範囲第４ 項に記載のフェッチング方法。 ６．条件値が知られているか予測されている最終フェッチが優勢値とは逆になっ た以降の分岐のフェッチ数のカウントを維持することを特徴とする請求の範囲第 ５項に記載のフェッチング方法。 ７．条件値が優勢値とは逆であった分岐の最終フェッチでカウンタの値を思い出 すことを特徴とする請求の範囲第６項に記載のフェッチング方法。 ８．カウンタの思い出された値とカウンタの現在値とを比較し、現在値が思い出 されたカウントに等しくなければ優勢条件値を予測することを特徴とする請求の 範囲第７項に記載のフェッチング方法。 ９．条件値が優勢値とは逆であった分岐の最新フェッチの時点で、カウンタの容 量を超えたフェッチにより終了されたループの長さのためにカウンタがオーバー フローしているか否かを検出しかつ思い出すことを特徴とする請求の範囲第７項 に記載のフェッチング方法。 10．カウンタの思い出された値（オーバーフローを含む）とカウンタの現在値と を比較し、思い出されたカウントがオーバーフローすることなくかつ現在カウン トに等しくなければ優勢条件値を予測することを特徴とする請求の範囲第９項に 記載のフェッチング方法。 11．条件的分岐により第１二進カウンタを維持し、当該カウンタをリフェッチで はなくかつ逆の値をもつことが知られまたは予測されまたはリフェッチでありか つ逆の値をもたないように元々予測されていた分岐のフェッチ時にゼロに初期化 し、かつカウンタがその最大カウントに到達しなければ当該分岐の他の各フェッ チにおいて１だけカウンタを増大させ、カウンタがその最大カウントに到達して いる場合にはカウンタを変化させないことを特徴とする請求の範囲第 １０項に記載のフェッチング方法。 12．条件的分岐により、第１二進カウンタと同じ容量の第２二進カウンタを維持 し、第２二進カウンタがゼロを保持する場合およびこの場合にのみ、逆の条件値 を予測し、分岐の各フェッチでこの第２二進カウンタを修正し、この修正は、こ のフェッチが分岐の早期フェッチで正しくない予測により必要とされるリフェッ チであるか否かに基づいて次のように、すなわち、 リフェッチでない場合には、第２二進カウンタをその最大値にセットし、第 １二進カウンタが最大値を保持する場合には、第２二進カウンタがゼロを保持し なければ該第２二進カウンタを減少させ、この場合には、第１二進カウンタの値 を第２二進カウンタにコピーし、 これがリフェッチである場合には、早期フェッチが優勢方向とは逆であると 予測していなければ、早期フェッチの時点で第１二進カウンタにある値を第２二 進カウンタにコピーし、この場合には、第２二進カウンタをその最大値にセット することを特徴とする請求の範囲第１１項に記載のフェッチング方法。 13．リフェッチするときには必ず、分岐、優勢予測、およびリフェッチされてい る当該分岐のフェッチの直前に分岐に優勢な第１および第２二進カウンタの値を 回復させることを特徴とする請求の範囲第１２項に記載のフェッチング方法。 14．分岐をフェッチングした後、分岐シェルフの分岐の第１および第２二進カウ ンタの更新された優勢予測および値を、当該分岐命令の命令メモリアドレスと一 緒に記憶することを特徴とする請求の範囲第１３項に記載のフェッチング方法。 15．優勢予測およびフェッチした分岐の第１および第２二進カウンタの値を、分 岐シェルフから、前記フェッチした分岐を制御する条件後の或る時点で、まさし くこの目的のための命令メモリまたは補助ＲＡＭである分岐予測ＲＡＭに移動さ せ、任意の分岐の全ての先行フェッチが知られていることを特徴とする請求の範 囲第１４項に記載のフェッチング方法。 16．分岐のフェッチング時に、分岐のアドレスを記憶するエントリーの分岐シェ ルフをサーチし、分岐予測ＲＡＭを読み取ることにより、優勢予測および当該分 岐の第１および第２二進カウンタの値を決定し、かつ分岐シェルフに見出さ れる最も新しく付加されたマッチングエントリーを用いて、分岐予測ＲＡＭから 読取られる値を決定することを特徴とする請求の範囲第１５項に記載のフェッチ ング方法。 17．１つ以上のフェッチした分岐の制御条件が正しくなく予測されたことを検出 すると、分岐シェルフから、フェッチした各分岐のエントリーおよびこれらのい かなる分岐よりも新しくフェッチされた全ての分岐を取り出すことを特徴とする 請求の範囲第１６項に記載のフェッチング方法。 18．コンピュータシステムの実行用命令メモリから、非条件的分岐命令および条 件的分岐命令の両方を有する命令のシーケンスをフェッチングするコンピュータ システムの作動方法において、 各クロックサイクルにおいて、プログラムカウンタのアドレスで、前記命令 メモリから少なくとも１つの命令を読取るステップと、 前記命令メモリからの各分岐命令を、非条件的命令、条件的かつ取り出すべ きものと知られた命令、取り出すべきではないと知られた命令、または推論的命 令に級別するステップと、 前記制御条件のラン長さより大きい最新のラン長さに等しいラン長さを得る ため、シーケンスにおける各推論的分岐命令についての制御条件を予測するステ ップと、 非条件的命令、取り出すべきものと知られた命令、または取り出すべきもの と予測された命令である第１分岐命令により指向された次のクロックサイクルの 読取りステップのためのプログラムカウンタを変えるステップとを有し、 前記フェッチング方法は、前記条件が不変のルーピング挙動を呈する場合に は、前記命令メモリに記憶された条件的分岐を制御する条件を正確に予測するこ とを特徴とするコンピュータシステムの作動方法。 19．前記予測ステップは回数をカウントすることを含み、条件的分岐命令の制御 条件は第２状態に変化する前の１つの状態に留まって、前記条件的分岐命令のラ ン長さを決定することを特徴とする請求の範囲第１８項に記載の作動方法。 20．前記カウンティングサブステップが、所定の定数までカウントアップするこ とを含むことを特徴とする請求の範囲第１９項に記載の作動方法。 21．前記予測ステップは、前記条件的分岐命令の現在ランの長さが前記所定の定 数に等しいかこれより大きい場合に、条件的分岐命令が、該条件的分岐命令の少 なくとも２つ以上のフェッチと同じになるように条件的分岐命令を制御する条件 を予測することを特徴とする請求の範囲第２０項に記載の作動方法。 22．前記カウンティングサブステップは、前記条件的分岐命令の最終の２つ以上 の連続フェッチについての不変の条件を補完するための知られたまたは予測され た条件をもつ最終フェッチ以降の前記条件命令のフェッチ数をカウントすること を含むことを特徴とする請求の範囲第１９項に記載の作動方法。 23．前記予測ステップは、前記条件的分岐命令の最終の２つ以上のフェッチにつ いての不変の条件を補完するための知られたまたは予測された条件をもつ最終フ ェッチ以降の前記条件命令のフェッチ数を記憶することを含むことを特徴とする 請求の範囲第２２項に記載の作動方法。 24．前記予測ステップは、先行ラン長さと前記条件的分岐命令のフェッチの現在 数とを比較すること、および前記先行ラン長さがフェッチの前記現在数に等しく なければ、前記制御条件が前記条件的分岐命令の最終の２つ以上のフェッチと同 じであると仮定することを含むことを特徴とする請求の範囲第２３項に記載の作 動方法。 25．前記予測ステップは、前記先行ラン長さが所定の定数に等しいかこれより大 きいかを決定することを含むことを特徴とする請求の範囲第２４項に記載の作動 方法。 26．前記仮定サブステップは、前記先行ラン長さが前記所定の定数より小さくか つフェッチの前記現在数に等しくなければ、前記制御条件が前記条件的分岐命令 の最終の２つ以上のフェッチと同じであると仮定することを特徴とする請求の範 囲第２５項に記載の作動方法。 27．前記予測ステップは、 第１二進カウンタと各条件的分岐命令とを関連付けること、 関連付けられたカウンタを、前記分岐命令が該分岐命令のリフェッチではな くかつ前記分岐命令の直前フェッチの制御条件を補完する制御条件をもつことが 知られているか予測されている場合、または前記分岐命令が該分岐命令のリ フェッチでありかつ前記分岐命令の直前フェッチの制御条件と同じである制御条 件をもつことが予測されている場合に、条件的分岐命令のフェッチ時に初期化す ること、および、 前記カウンタが所定の最大カウントに到達していなければ、前記カウンタを 、前記分岐命令の各連続フェッチで１つだけ増大させることを含むことを特徴と する請求の範囲第１８項に記載の作動方法。 28．前記予測ステップが更に、 第２二進カウンタと各条件的分岐命令とを関連付けることを含み、前記第２ カウンタは前記第１二進カウンタと同じ最大カウントを行い、 前記第２カウンタがゼロカウントを保持する場合およびこの場合にのみ、関 連付けられた分岐命令の前記制御条件が補完するように予測すること、および、 前記フェッチが、前記分岐命令の早期フェッチでの正しくない予測により必 要とされるリフェッチであるか否かに応答して、前記分岐命令の各フェッチで前 記第２二進カウンタを修正することを含むことを特徴とする請求の範囲第２７項 に記載の作動方法。 29．前記フェッチが前記分岐命令のリフェッチではなく、前記第２二進カウンタ の修正サブステップが更に、 第１二進カウンタが前記最大カウントを保持する場合には、前記第２二進カ ウンタを前記最大カウントにセットすること、 第２二進カウンタがゼロカウントを保持しなければ、第２二進カウンタを１ だけ減少させること、 前記第２二進カウンタがゼロカウントを保持する場合には、第１二進カウン タのカウントを前記第２二進カウンタにコピーすることを含むことを特徴とする 請求の範囲第２８項に記載の作動方法。 30．前記フェッチが前記分岐命令のリフェッチである場合には、前記第２二進カ ウンタの修正サブステップが更に、 前記早期フェッチの前記制御条件が、前記条件的分岐命令の最終の２つ以上 のフェッチについて不変となるように補完されることを予測していなければ、早 期フェッチの時点で、前記第１二進カウンタを第２二進カウンタにコピーす ること、および、 前記早期フェッチの前記制御条件が、前記条件的分岐命令の最終の２つ以上 のフェッチについて不変となるように補完されることを予測している場合には、 前記第２二進カウンタを前記最大カウントにセットすることを含むことを特徴と する請求の範囲第２８項に記載の作動方法。 31．前記予測ステップは、 リフェッチされている前記分岐命令のフェッチの直前の前記分岐命令につい ての前記第１および第２二進カウンタの最終の２つ以上のフェッチおよびカウン トについて不変の前記分岐命令の前記制御条件を回復させることを含むことを特 徴とする請求の範囲第３０項に記載の作動方法。 32．前記予測ステップは、 条件的分岐命令の最終の２つ以上のフェッチ、前記分岐命令についての前記 第１および第２二進カウンタ、および前記分岐命令の各フェッチにおける前記分 岐命令の命令メモリのアドレスについて不変の前記分岐命令の前記制御条件を記 憶することを含むことを特徴とする請求の範囲第１３項に記載の作動方法。 33．コンピュータの条件的分岐命令の方向を予測する方法において、 所定限度までの前記分岐命令の第１ラン長さを決定するステップと、 前記条件的分岐命令の次のラン長さをカウントするステップと、 前記次のラン長さが前記第１ラン長さに等しくなるかこれを超える前に終了 しなければ、前記次のラン長さが前記第１ラン長さに等しいと仮定するステップ とを有し、 正しく予測された条件的分岐命令の入力が高められることを特徴とする方法 。 34．前記次のラン長さが前記第１ラン長さを超える場合に、前記次のラン長さが 無制限に連続することを特徴とする請求の範囲第３３項に記載の方法。 35．前記第１ラン長さに等しくなる前に前記分岐命令の次のラン長さが終了する 場合に、前記次のラン長さを決定するステップと、 前記次のランに続く前記条件的分岐命令のラン長さをカウントするステップ と、 前記次のランに続く前記ランが、前記次のラン長さに等しくなるかこれを超 える前に終了しなければ、前記次のランに続く前記ランが、前記次のラン長さに 等しいと仮定するステップとを更に有することを特徴とする請求の範囲第３４項 に記載の方法。 36．コンピュータシステムの分岐命令を制御する条件の結果を予測する方法にお いて、 前記制御条件の回数が第２状態に変化する前の第１状態にあることを決定す るステップと、 制御条件が、第１状態において前記第２状態に変化する前と同じ回数に留ま ることを予測するステップとを有することを特徴とする方法。 37．前記決定ステップおよび予測ステップが、各条件的分岐命令に対して遂行さ れることを特徴とする請求の範囲第３６項に記載の方法。 38．前記予測ステップに従って前記分岐命令をするステップを更に有することを 特徴とする請求の範囲第３６項に記載の方法。 39．前記分岐命令をするステップが、 前記制御条件の前記第１状態に従って前記分岐命令を前記回数行なうこと、 および、 次に、前記制御条件の前記第２状態に従って前記分岐命令を行なうことを有 することを特徴とする請求の範囲第３８項に記載の方法。 40．前記決定ステップでは、前記回数が制限されることを特徴とする請求の範囲 第３９項に記載の方法。 41．前記決定ステップが、 前記条件的分岐命令の現在ランの長さの第１カウントを維持すること、およ び、 前記第１カウントおよび前記条件的分岐命令の最も新しく完了したラン長さ に応答する第２カウントを維持することを含むことを特徴とする請求の範囲第４ ０項に記載の方法。 42．前記第１カウントは、前記条件的分岐命令が正しく行なわれる度毎に前記第 １カウントを増大させることにより維持されることを特徴とする請求の範囲第４ １項に記載の方法。 43．前記第２カウントは、前記条件的分岐命令が正しく行なわれる度毎に前記最 も新しく完了したラン長さのカウントを減少させることにより維持されることを 特徴とする請求の範囲第４１項に記載の方法。 44．前記決定ステップが、 前記条件的分岐命令が正しく行なわれる度毎に前記第１カウントを増大させ ることにより、前記条件的分岐命令の現在ランの長さの第１カウントを維持する こと、 前記条件的分岐命令が正しく行なわれる度毎に前記最も新しく完了したラン 長さのカウントを減少させることにより、前記第１カウントおよび前記条件的分 岐命令の最も新しく完了したラン長さに応答する第２カウントを維持することを 有することを特徴とする請求の範囲第４０項に記載の方法。 45．前記予測ステップは、前記制御条件が前記制限回数を超えて前記第１状態に 留まる場合に、前記制御条件が前記第１状態に留まることの予測を有することを 特徴とする請求の範囲第４０項に記載の方法。 46．前記予測ステップは更に、 前記行なわれた分岐命令が誤って予測されるときに前記現在ランの長さが所 定限度を超える場合に前記第１カウントを再開すること、および 前記条件的分岐命令の前記最も新しく完了したラン長さについて、前記第２ カウントを前記従前の第１カウントにセットすることを有することを特徴とする 請求の範囲第４４項に記載の方法。 47．前記現在ランの長さが前記最も新しく完了したラン長さより短い場合に、前 記条件的分岐命令の前記最も新しく完了したラン長さについて、前記第１カウン トから前記第２カウントをコピーすること、および、 前記第１カウントを再開することを更に有することを特徴とする請求の範囲 第４４項に記載の方法。