(57)【要約】  分岐命令の前にload命令があり、キャッシュミスを引き起こしていた場合、分岐命令が、このload命令でロードされる値に依存した条件分岐であると、キャッシュミスにより値のロードが遅れているので、分岐命令の分岐方向の確定が遅れてしまう。もし、分岐命令の実行時の分岐予測がミスしていると、load命令の値がロードされた後、分岐命令の分岐方向が確定するので、それまでに、間違った分岐予測にしたがって、投機的に分岐命令の後続の命令を発行してしまうことになる。しかし、分岐予測が間違っていたので、間違った分岐予測に基づく投機的命令をキャンセルし、正しい後続命令を発行しなくてはいけない。このために、正しい後続命令の発行が遅れてしまい、情報処理装置の性能劣化につながる。そこで、分岐命令が条件分岐命令などで、前のキャッシュミスするような命令に依存した分岐をする場合は、分岐命令の後続の命令の発行を抑止する。
2008029450.tif 000002
【特許請求の範囲】
【請求項１】
分岐命令の分岐予測を行い、命令を投機的に実行する情報処理装置であって、
ロード命令のキャッシュミスを検出するキャッシュミス検出手段と、
該ロード命令の後続の条件分岐命令が、実行時点で、分岐方向が確定していない場合に、該条件分岐命令の後続の命令の発行を停止する命令発行停止手段と、
を備え、
分岐予測ミスによって生じる発行命令のキャンセルのための時間を削除し、分岐予測ミスによるペナルティをキャッシュミスによる待ち時間に隠蔽する
ことを特徴とする情報処理装置。
【請求項２】
更に、
前記ロード命令と前記後続の条件分岐命令との依存関係を検出する依存関係検出手段を備え、
該ロード命令と該条件分岐命令とが依存関係にある場合に、該条件分岐命令の後続の命令の発行を停止することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
更に、
発行したロード命令がキャッシュミスするか否かが確定する前に、キャッシュミスするか否かを予測するキャッシュミス予測手段を備え、
該キャッシュミス予測手段がキャッシュミスを予測した場合に、前記条件分岐命令の後続の命令の発行を停止することを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記キャッシュミス予測手段がキャッシュミスと予測したロード命令がヒットだと判明した場合には、命令の発行を再開し、ヒットと予測したロード命令がキャッシュミスしたと判明した場合には、命令の発行を直ちに停止することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記キャッシュミス予測手段は、過去のロード命令の実行についてキャッシュミス、ヒットの履歴を有することを特徴とする請求項３に記載の情報処理装置。
【請求項６】
更に、
該分岐命令の命令フェッチ時の分岐予測の確度を検出する分岐予測確度検出手段を備え、
前記条件分岐命令の分岐予測確度が低い場合に、該条件分岐命令の後続の命令の発行を停止することを特徴とする請求項１に記載の情報処理装置。
【請求項７】
キャッシュミスするロード命令と後続の条件分岐命令とが、プログラムの命令列に沿って、閾値で示されるライン以上離れている場合に、該条件分岐命令の後続の命令の発行を停止することを特徴とする請求項１に記載の情報処理装置。
【請求項８】
更に、
予測された命令をフェッチし、実行系に投入する予測側実行手段と、
予測されなかった命令をフェッチし、実行系に投入する反予測側実行手段とを備え、
該反予測側実行手段が予測されなかった命令のフェッチ、実行を処理できなくなった場合に、前記条件分岐命令の後続の命令の発行を停止することを特徴とする請求項１に記載の情報処理装置。
【請求項９】
前記情報処理装置が、遅延スロットを有する命令セットアーキテクチャを採用している場合、遅延スロットの次の命令から発行を停止することを特徴とすることを特徴とする請求項１に記載の情報処理装置。
【請求項１０】
分岐命令の分岐予測を行い、命令を投機的に実行する情報処理装置の制御方法であって、
ロード命令のキャッシュミスを検出し、
該ロード命令の後続の条件分岐命令が、実行時点で、分岐方向が確定していない場合に、該条件分岐命令の後続の命令の発行を停止し、
分岐予測ミスによって生じる発行命令のキャンセルのための時間を削除し、分岐予測ミスによるペナルティをキャッシュミスによる待ち時間に隠蔽する
ことを特徴とする情報処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分岐予測ミスリカバリ機構を有する情報処理装置に関する。
【背景技術】
【０００２】
マイクロプロセサにおける命令実行方式としては、実行可能な命令からアウトオブオーダで命令を実行するスーパスカラ方式と呼ばれる方式が用いられるのが一般的である。その特徴として、大まかに命令フェッチ、命令デコード、命令発行、命令実行、命令コミットのような形のパイプラインで制御されることが多く、分岐命令のパスが確定する前にどちらのパスが正しいかを予測する分岐予測機構を備えているのが一般的である。分岐予測がはずれると、パイプラインをクリアして、正しいパスを命令フェッチからやり直すことになるため、プロセサの性能向上を図る上では、分岐予測精度を上げることに加え、命令フェッチからのやり直しを高速化することが重要である。【０００３】
図１は、一般的なスーパスカラ型プロセサの構成を示す図である。
命令フェッチ／分岐予測機構１０から命令フェッチの指示が出ると、Ｌ１命令キャッシュ１１から命令がフェッチされ、命令バッファ１２に格納される。ＡＰＢ１３は、分岐予測した場合の、予測された分岐先に分岐しなかったとした場合に実行されるべき、命令を格納するバッファである。セレクタ１４は、命令バッファ１２から、ＡＰＢ１３のいずれか一方からの命令をデコーダ１５に入力する。デコーダ１５でデコードされた命令は、分岐命令のリザベーションステーション１６、整数演算のリザベーションステーション１７、ロード、ストア命令のリザベーションステーション１８、あるいは、浮動小数点演算のリザベーションステーション１９に格納される。命令は、デコードされると、in-orderでのコミットのために、ＣＳＥ(Commit Stack Entry）２３にエントリされる。【０００４】
分岐命令のリザベーションステーション１６は、分岐予測先の命令と確定した分岐先の命令との一致を調べ、一致している場合には、ＣＳＥ２３に分岐命令の完了通知を行い、当該分岐命令をコミットする。命令は、コミットされると、ＣＳＥ２３が論理アドレスを物理アドレスに変換するリネームマップ２０をクリアすると共に、コミットされていない命令のデータを格納するリネームレジスタファイル２１の対応するデータをレジスタファイル２２に書き写させ、リネームレジスタファイル２１から当該データを消去する。【０００５】
整数演算のリザベーションステーションは、リネームレジスタファイル２１、レジスタファイル２２、Ｌ１データキャッシュ２４、Ｌ２キャッシュ２５、外部メモリ２６のいずれかから得たデータを整数演算器２７に投入して、演算を行わせる。演算の結果は、リネームレジスタファイル２１に書き込むか、すぐ次の演算使用する場合には、整数演算器２７の入力に持ってくるか、加算器２８の入力に与えられるか、分岐命令のリザベーションステーションに、予測一致検出のために与えられるかする。【０００６】
ロード、ストア命令のリザベーションステーション１８は、加算器２８を使って、ロードあるいはストア命令を実行するためのアドレス演算を行い、演算結果は、加算器の入力、Ｌ１データキャッシュ２４、リネームレジスタファイル２１のいずれかに与えられる。【０００７】
浮動小数点演算のための構成は図示を省略している。Ｌ１データキャッシュ２４、Ｌ２キャッシュ２５の制御は、ロード、ストア命令のリザベーションステーションが発行するデータキャッシュアクセス要求にしたがって、キャッシュ制御部２９によって行われる。【０００８】
整数演算命令、ロード、ストア命令、浮動小数点演算命令の何れも、実行が完了すると、ＣＳＥ２３に完了通知がなされ、コミットされる。
図２Ａ〜Ｄは、マシンサイクルを示すタイミング図である。【０００９】
図２Ａは、整数演算命令パイプラインの例を示す。図２Ｂは、浮動小数点演算命令パイプラインの例を示す。図２Ｃは、Load/Store命令パイプラインの例を示す。図２Ｄは、分岐命令パイプラインの例を示す。【００１０】
図２Ａ〜Ｄにおいて、ＩＡは、命令フェッチの１サイクル目であり、命令フェッチアドレスの生成や、Ｌ１命令キャッシュへのアクセスの開始をするサイクルである。ＩＴは、命令フェッチの２サイクル目であり、Ｌ１命令キャッシュタグの検索や、ブランチヒストリタグの検索を行う。ＩＭは、命令フェッチの３サイクル目であり、Ｌ１命令キャッシュタグのマッチ、ブランチヒストリタグのマッチを取り、分岐予測を行う。ＩＢは、命令フェッチの４サイクル目であり、命令フェッチデータが到達するサイクルである。Ｅは、命令発行プレサイクルであり、命令バッファから命令発行ラッチへ命令を送出するサイクルである。Ｄは、命令デコードのサイクルであり、レジスタリネーム、ＩＩＤ等の各種リソースの割り当てを行い、ＣＳＥ／ＲＳへ命令を送出するサイクルである。Ｐは、リザベーションステーションから古い命令を優先的に依存関係がそろった命令を選択するサイクルである。Ｂは、Ｐサイクルで選択された命令のソースデータをＲＦ（レジスタファイル）から読み出すサイクルである。Ｘｎは、演算器で処理を実行しているサイクルである（整数演算、浮動小数点演算）。Ｕは、実行完了をＣＳＥへ通知するサイクルである。Ｃは、コミット判断のサイクルであり、最速時には、Ｕと同時である。Ｗは、命令コミット、リネームＲＦのデータをＲＦに書き込み、ＰＣ（プログラムカウンタ）を更新するサイクルである。Ａは、load/store命令のアドレスを生成するサイクルである。Ｔは、load/store命令の２サイクル目であり、Ｌ１データキャッシュタグの検索を行う。Ｍは、load/store命令の３サイクル目であり、Ｌ１データキャッシュタグのマッチを取る細工するである。Ｂは、load/store命令の４サイクル目であり、loadデータの到着のサイクルである。Ｒは、load/store命令の５サイクル目であり、パイプラインが完了し、データが有効であることを示すサイクルである。Ｐｅｖａｌは、分岐のTaken、Not  Takenを評価するサイクルである。Ｐｊｕｇｅは、分岐予測のHit/Miss判定、Missの場合は、最速時に命令再フェッチの開始と同時である。【００１１】
図３は、従来の問題点を説明する図である。
プロセサシステムで近年最も主流の方式であるスーパスカラ型プロセサにおいては、命令フェッチ時に分岐予測機構を用いて正しいと予測した方向の命令列を決定し、分岐確定に先行してout-of-orderで命令実行を行うのが特徴である。もし、分岐命令が確定し、分岐予測が誤っていることが判明したら、直ちに、はずれた分岐命令後に発行された命令列を破棄し、CPUの状態をその分岐命令直後と等価な状態まで戻して、分岐命令直後の正しい方向の命令列のフェッチからやり直すため、処理に空き時間が生じ、性能低下を招く。【００１２】
また、分岐ミス時にCPUの状態をミスした分岐命令直後の状態に戻す方法として、分岐ミスした分岐命令コミット後に後続命令CPU内の各種リソースを初期化して、後続命令の発行を開始する方法がある。この場合、命令フェッチ部は、実行部の各種リソースとは独立しているため、分岐ミス判明直後に命令フェッチ部のみを初期化して後続命令の命令フェッチを開始する。【００１３】
この方法では、分岐命令直後の、やり直した命令フェッチを行う間に分岐命令までのコミットが行われれば、フェッチされた命令が最速で発行できるので分岐ミスによるペナルティは最小限で済ませることができる。【００１４】
しかし、分岐ミスが確定してから分岐命令がコミットするまでのサイクル数が、やり直しの命令フェッチのサイクル数よりも長い場合は、コミットまで命令発行が停止するため、性能低下を引き起こす。【００１５】
分岐ミスが確定してから分岐命令がコミットするまでのサイクル数が長くなる場合の代表例として、分岐ミスした分岐命令の前にLoad命令がキャッシュミスを引き起こした場合がある。CPU内部のキャッシュにミスし、システム上のDRAMからデータを供給する場合、そのレイテンシは典型的な例としてCPU cycleで200〜300cycleにも及ぶ。【００１６】
分岐命令コミットまでに命令発行が停止する理由は、正しい分岐方向の命令列を発行するためにはリネーミングレジスタやリザベーションステーション等のリソースの状態を分岐命令発行直後の状態に戻すか、分岐命令までコミットされて各種リソースの状態をクリアするかのいずれかが必要だからである。【００１７】
また、この問題を解決する手段として、各種リソースの状態を分岐命令毎に保存し、分岐ミス発生時に、その分岐命令発行時の状態に戻し、分岐命令コミットを待たずに正しい方向の分岐命令発行を継続するという方法がある。この方法であれば、本発明に依らず、性能の観点から見た場合上記の問題点は解決する。しかしながら、この方法はハードウエアリソースの飛躍的な増大や回路のサイクルタイムの増大を招くという問題があった。また、分岐ミスの頻度が低かったり、データキャッシュミスの頻度が低いコードなどでは効果が低く、実装コストの割に合わないという問題もあった。【００１８】
従来の分岐命令の処理方法については、以下の特許文献に記載がある。特許文献１には、計数分岐命令の先行命令が書き換えられることにより、分岐命令の解読サイクルにおいて分岐の判定ができないときに、データを演算装置に転送すると同時に分岐に判定をする技術が開示されている。特許文献２においては、分岐しない場合に、次命令を実行させたくないときに、ステージの時間を増大させずに処理可能な技術が開示されている。特許文献３には、キャッシュミスした場合に、命令実行が停止される構成の情報処理装置の技術が開示されている。
【特許文献１】特開昭６０−３７５０号公報
【特許文献２】特開平３−１３１９３０号公報
【特許文献３】特開昭６２−７３３４５号公報
【発明の開示】
【００１９】
本発明の課題は、簡単な構成の分岐予測ミスリカバリ機構を有した情報処理装置を提供することである。
本発明の情報処理装置は、分岐命令の分岐予測を行い、命令を投機的に実行する情報処理装置であって、ロード命令のキャッシュミスを検出するキャッシュミス検出手段と、該ロード命令の後続の条件分岐命令が、実行時点で、分岐方向が確定していない場合に、該条件分岐命令の後続の命令の発行を停止する命令発行停止手段とを備え、分岐予測ミスによって生じる発行命令のキャンセルのための時間を削除し、分岐予測ミスによるペナルティをキャッシュミスによる待ち時間に隠蔽することを特徴とする。
【００２０】
本発明では、所定の条件で、命令発行を停止するという簡単な方法により、分岐予測ミスリカバリを行うようにしたため、簡単な回路構成で、条件分岐命令の前にあるキャッシュミスを起こしたロード命令のキャッシュミスによる待ち時間に分岐ミスによるペナルティを隠すことができる。
【図面の簡単な説明】
【００２１】
【図１】一般的なスーパスカラ型プロセサの構成を示す図である。
【図２Ａ】マシンサイクルを示すタイミング図（その１）である。
【図２Ｂ】マシンサイクルを示すタイミング図（その２）である。
【図２Ｃ】マシンサイクルを示すタイミング図（その３）である。
【図２Ｄ】マシンサイクルを示すタイミング図（その４）である。
【図３】従来の問題点を説明する図である。
【図４】本発明の実施形態の原理を説明する図である。
【図５】本発明の実施形態に従った情報処理装置の構成例である。
【図６】前のload命令と後の分岐命令との依存関係を検出するための構成を説明する図である。
【図７】キャッシュヒット／ミス予測機構の構成例を示す図である。
【図８】分岐予測確度検出のための構成の一例を示した図（その１）である。
【図９Ａ】分岐予測確度検出のための構成の一例を示した図（その２）である。
【図９Ｂ】分岐予測確度検出のための構成の一例を示した図（その３）である。
【図１０】ＢＨＴを使った分岐予測方式について説明する図である。
【図１１】ＢＨＴとＷＲＧＨＴ＆ＢＲＨＩＳとを組み合わせた分岐予測確度検出のための構成例を示す図である。
【図１２】ＡＰＢと本発明の実施形態の使用形態について説明する図である。
【図１３】本発明による効果を表すタイミングの例を示す図である。
【図１４】リネーミングマップを分岐命令ごとに保持して、分岐ミスを契機に書き戻す機構を持つ場合の命令実行サイクルの例を示す図である。
【図１５】［方法１］、［方法２］の動作例を示すタイミング図である。
【図１６】１エントリのＡＰＢを有する場合に本発明を適用した場合のマシンサイクルの例を示すタイミング図である。
【発明を実施するための最良の形態】
【００２２】
図４は、本発明の実施形態の原理を説明する図である。
本発明の実施形態においては、命令発行を停止するという比較的容易な方法により従来の問題点を解決する。Loadデータのキャッシュミスを検出または予測した場合、分岐命令以降の後続の命令列発行を一時的に停止させる。命令発行を抑止したとしても、Loadデータの待ち時間が長く、Loadデータが届く前に分岐が確定すれば、分岐予測がはずれた場合は、分岐命令のコミットを待たなくても後続命令の発行を再開できることで性能向上が実現でき、分岐予測が当たった場合であっても、先行命令がリザベーションステーションに残ったままの状態であることから、命令発行を停止しなかった場合に比べて性能低下を起こすことがほとんど無い。【００２３】
しかしながら、本制御手法において、より性能向上効果を上げるためには、命令発行停止の対象となる分岐命令を適切に選択することが重要である。
従来の技術において、プロセサの命令発行部は、命令フェッチされた命令をできるだけ速やかに発行する制御であるが、本発明実施においては、以下の例に示すように命令の発行停止および再開制御を追加することになる。【００２４】
−発行停止、および、発行再開の条件
[方法１]
条件分岐命令までで命令発行を停止する条件
（１）先行するLoad命令がキャッシュミスしていることを検出するか、キャッシュミスすると予測する。(予測機構を省略時は検出のみ)
（２）分岐命令が条件分岐命令であること。
（３）分岐方向が発行時点で確定していない。
（４）分岐予測精度が低いと判断
（５）分岐命令に対する依存関係が無いこと。
（６）Load命令に対して分岐命令の距離が有る閾値以上離れていること。【００２５】
以上の条件をすべて満たす場合に、命令発行を停止する。
発行再開する条件
（１）キャッシュミスすると予測したLoad命令がキャッシュミスしなかった。(予測機構を省略時は不要)
（２）発行停止した条件分岐命令が確定した。【００２６】
(条件分岐命令がキャッシュミスしたLoad命令に対する依存関係がない場合は、一般的にLoad データが到達するより十分早く分岐が確定するため、長いキャッシュミスレーテンシに発行停止のペナルティは隠れる。このとき分岐ミスが判明したとしてもキャッシュミスしたLoadデータが届く前に予測ミスした分岐命令コミットを待たずに後続命令の発行を開始することができるため分岐ミスのペナルティも隠すことができる。)【００２７】
（３）キャッシュミスしたLoad データが到達する。(または、到達の予告信号をキャッシュ制御部より受け取る。)(これは、Loadデータ到達が先である可能性があるため、この条件を追加する。)
以上の条件がすべて満たされた場合、命令の発行を再開する。【００２８】
上記方法１においてLoad命令がキャッシュミスすることを検出するには、履歴テーブルを参照するなどの方法が考えられるが、実装コストが高くなることから現実的ではない。そこでキャッシュミス予測機構を省略してもよい。【００２９】
また、Load命令-分岐命令間の距離が有る程度離れている場合に限定することで、実行スループットの低下を最小限に抑えることができる。
スーパスカラプロセサにおいては、命令順に番号を割り付けることによってプログラムオーダの制御を行うことが一般的であり、命令間の距離を容易に知ることができる。【００３０】
キャッシュミスしたLoad命令に対して分岐命令に依存性があるかどうかを検出することが可能な実装であれば、依存性がないことを検出した場合に直ちに停止することができるため、その動作が優先される。【００３１】
依存性があるかどうかを検出することができない実装である場合、および、依存性がある場合に、Load命令以降どれだけ予測ミスする可能性がある1つまたは複数の分岐命令以降の命令発行を継続すべきかを決定するのは重要である。つまり、発行する命令が少なすぎれば(分岐ミスしない場合の)アウトオブオーダ実行効率を損ねるし、多すぎれば分岐ミス時のコミット待ちによるペナルティが大きくなる可能性があるというトレードオフが発生するからである。【００３２】
一方で、分岐ミスが判明し、再フェッチを開始してからその先頭命令が発行されるまでには、あるサイクル数がかかりその間に分岐命令までの全命令が実行を完了しコミットされれば滞りなく命令発行が開始されるためコミット待ちによるロス無く分岐ミス後の命令発行再開を行うことができる。【００３３】
そのような命令数閾値は
命令数閾値=max(「再フェッチから先頭命令発行再開までの最短ステージ数」,「命令実行から完了までのステージ数」)*（実行スループット）
で表される数が目安となる。【００３４】
しかしながら、命令の並列度(例えば、互いに依存しない複数の処理が並列にプログラミングされていれば、典型的なアウトオブオーダ実行を行う)、並列に実行するために実装されたパイプライン数(主に演算器やリザベーションステーション等のプロセサ固有のハードウエアエアリソース)、命令の実行レイテンシ(これもハードウエア実装固有)に依存する。【００３５】
命令の並列度が高い(各命令が互いに依存性を持たずに独立して実行可能な命令が多い)ほど、並列に実行するための演算器の数が多いほど、命令の実行レイテンシが小さいほど、実行スループットが大きくなる。【００３６】
ただし、並列に実行するためのパイプライン数については、並列に実行可能な命令列の数より大きい場合は意味がなく、実際の一般的なプログラムでも一般的に整数演算、浮動小数点演算、Load/Storeとも各2本程度なのが典型的である。整数演算、浮動小数点演算、Load/Storeがパイプライン各2本、分岐命令が1サイクルで2命令同時に処理できるとすると、同時に最大8命令実行可能であるが、同時命令発行数や同時命令コミット数が例えば4命令である場合、その数に制約されるため、理論的な最大命令スループットは4命令/サイクルである。【００３７】
しかしながら、4命令/サイクルを実現するためには、命令発行された命令が使用するソースデータが、最速で実行しようとするタイミングですでに利用可能である(依存性が解決する)状態が連続的に起こらなければならず、後述するように実際の命令列の並列度や、ハードウエアの命令実行レイテンシの制約から発行された命令が最速で実行可能にならないことも多く、理想的な4命令/サイクルより小さくなることが一般的である。【００３８】
整数演算命令およびload/Store命令のアドレス生成の実行レイテンシをLx, 浮動小数点演算命令の実行レイテンシをLf,整数Load命令の実行レイテンシをLxl,浮動小数点Load命令の実行レイテンシをLflとする。
(ハードウエア実装上の事情から命令毎(たとえば同じ整数命令でもadd命令とshift命令のLatencyが異なる場合には一般的な出現頻度から固定的な平均値を採用するなり、リザベーションステーションを占有する命令をデコードして直接レイテンシを計算するなどの方法が考えられるが、簡単のために平均的な値を採用する。)【００３９】
CSEを占有する命令(=発行されてからまだコミットされない命令)のうち、整数命令、浮動小数点命令、整数Load命令、整数Store命令、浮動小数点Load命令、浮動小数点Store命令の数をNx, Nf, Nxl, Nxs, Nfl, Nfsとすると、整数系の演算、Load、浮動小数点系の演算、Loadが互いに並列に実行可能であり、それらの実行並列度を1とすると、実行サイクル数(Worst Case)の概算は整数系、浮動小数点系それぞれの実行時間の大きい方を取ることになるので、
実行サイクル数(Worst Case)=max((Nx*Lx + Nxl*Lxl),(Nf*Lf + Nfl*Lfl))  (1)
と表すことができる。
(ここでストア命令、分岐命令は実行パイプラインを消費するが、後続命令の実行に際して直接的な被依存性が無いものと見なして考慮からはずす。)【００４０】
また、例えば整数系のLoad,演算結果に浮動小数点Loadのアドレス生成演算が全て依存関係を持つ場合は
実行サイクル数(Worst Case)=(Nx*Lx + Nxl*Lxl)+(Nf*Lf + Nfl*Lfl)
となるが、以下に示すように浮動小数点系の演算Loadが含まれるような場合は浮動小数点系が実行時間において支配的になるので、上記(1)式で代表するものとする。【００４１】
１つの実装例として
Lx=1,Lf=6,Lxl=4,Lfl=4とすると
実行サイクル数(Worst Case)=max((Nx*1 + Nxl*4),(Nf*6 + Nfl*4))
また、並列度2になる場合をTypical Caseとすると同様に
実行サイクル数(Typical Case)=max((Nx*1 + Nxl*4),(Nf*6 + Nfl*4))/2
となる。【００４２】
実際のプログラムでは平均的な並列度をこれ以上上げるのは困難な場合が多く、並列度1から2の間にあるものと考えることでたいていのケースをカバーできると考えられる。
max(「再フェッチから先頭命令発行再開までの最短ステージ数」,「命令実行から完了までのステージ数」)=6cycle
とすると、命令閾値が以下のような式であらわすことができる。
・Worst-case時で
max((Nx*1 + Nxl*4),(Nf*6 + Nfl*4))=6
・Typical-case時で
max((Nx*1 + Nxl*4),(Nf*6 + Nfl*4))/2=6
上の式で表される命令数を上限とした閾値をとればおよそコミット待ちによるムダなCPUサイクルを防止することができる。【００４３】
さらに、分岐ミス可能性を判断可能な実装であれば、組み合わせとして、分岐ミス可能性が高いと判断すればWorst-caseを採用し、分岐ミス可能性が低いと判断すればTypical-caseを採用するもしくは閾値を無視して命令発行を継続するという方法も例として考えられる。【００４４】
[方法２]
上記方法１における命令発行停止条件に使用している依存関係検出するためのハードウエアは比較的実装コストが高く、本発明を実施するためだけに実装するのはあまり得策ではない。【００４５】
そこで、方法２において、厳密に依存関係を検出する代わりに、簡略化した代替手段として以下の（１）または（２）の方法をもって依存関係検出を行うものとする。
（１）依存関係検出を全く行わずに、一律依存関係がないものと見なす。命令発行停止後一定時間経過しても分岐方向が確定しないのであればLoad Dataに対する依存関係があるものと見なして命令発行を再開する。
（２）浮動小数データのLoadに対して整数CC(Condition Code)を参照する条件分岐命令、逆に整数データのLoadに対して浮動小数点CCを参照する条件分岐命令をそれぞれ依存関係がないものと見なす。
条件分岐命令までで命令発行を停止する条件
（１）先行するLoad命令がキャッシュミスしていることを検出した。
（２）分岐命令が条件分岐命令であること。
（３）分岐方向が発行時点で確定していない。
（４）分岐予測精度が低いと判断
（５）分岐命令に対する依存関係が無いこと。（あるいは、Load命令から一定の命令数離れている。)
以上の条件がすべて満たされている場合に命令発行を停止する。【００４６】
発行再開する条件
（１）発行停止した条件分岐命令が確定した。(条件分岐命令がキャッシュミスしたLoad命令に対する依存関係がない場合は一般的にLoad データが到達するより十分早く分岐が確定するため長いキャッシュミスレーテンシに発行停止のペナルティは隠れる。このとき分岐ミスが判明したとしてもキャッシュミスしたLoadデータが届く前に予測ミスした分岐命令コミットを待たずに後続命令の発行を開始することができるため分岐ミスのペナルティも隠すことができる。)
（２）キャッシュミスしたLoad データが到達する。(または、到達の予告信号を受け取る。)
(依存関係がないと判断したが、依存関係があった場合も含めて、Loadデータ到達が先である可能性があるためこの条件を追加すべきである。)
以上の条件がすべて満たされたときに命令の発行を再開する。【００４７】
[分岐予測精度を判断する処理の例]
上記方法１、方法２において、分岐予測精度が低い場合と判断する処理例として、使用される分岐予測方式に応じて以下のような例が考えられる。【００４８】
いずれもプロセサハードウエアで使用されている分岐予測回路を極力流用することによって実現するのが得策である。
(1)ソフトウエア的な分岐予測と反する方向に予測する場合は予測確度が低いと判断する方法
SPARC V9命令セットにおいては条件分岐命令においてソフト的に分岐のしやすさを示すP-bitと呼ばれる命令フィールドを持つタイプがある。分岐予測がP-bitに反する場合は分岐予測確度が低いと判断する。
(2) BHT方式
命令フェッチアドレスと2-bit Saturation Counterを持ったテーブルを命令アドレス等で参照するBHT方式の場合、Taken, Not Takenを基準にカウントする方法とソフト的に予測されるP-bitに従った方向か逆の方向でカウントする方法(Agree Predict)がある。【００４９】
(Taken, Not Takenを基準にする場合)
00: Strongly Taken
01: Weekly Taken
10: Weekly Not Taken
11: Strongly Not Taken
(P-bitに対してAgree, Disagreeかを基準にする場合)
00: Strongly Disagree
01: Weekly Disagree
10: Weekly Agree
11: Strongly Agree
命令フェッチアドレスおよびBHR(直近の条件分岐命令のTaken, Not Takenのパタンを条件分岐予測毎に1bitずつシフトして生成するレジスタ)を組み合わせたものをテーブル検索に用い、条件分岐命令フェッチ時および、フェッチ時の補正の意味で分岐予測ミスが判明したときに+1または-1して更新する。【００５０】
この方法においてWeeklyな予測時(Counter値=01.10)には予測確度が低いものと判断することができる。
(3)複数階層を持った分岐予測方式
BRANCH HISTORY+WRGHT方式を例とする。【００５１】
BRANCH HISTORYはTakenと予測される分岐命令をテーブルに登録しておき、Not Takenと予測される分岐命令はテーブルから削除する。BRANCH HISTORYはフェッチアドレスで検索する。検索結果Hitしたらそのアドレスで分岐命令がTakenであると予測する。非分岐命令およびNot Takenな命令は検索してもHitしないで命令列が直線的に進むものと判断する。【００５２】
分岐予測および結果に応じて以下のような処理を行う。
BRANCH-HISTORYはたとえば16Kエントリの容量を持つとする。
WRGHTはBRANCH-HISTORYにくらべてより少ない、限られたエントリ数ながら、上記BRANCH HISORYの予測精度を大幅に向上する。WRGHTは最近の16個の条件分岐命令についてTaken, Not Takenが何回続いたかの直近の3回分の情報を持つ。(その間に2回分岐方向が変化したことになる。)【００５３】
この方式では、直近の極小量(例えば24Entry)のエントリに格納された条件分岐命令に対してはより正確な予測を行うが、それが追い出されてWRGHTにエントリが無い場合は予測精度が相対的に低いものと見なす。【００５４】
(4) 複数の分岐予測方式を組み合わせた予測分岐予測方式
上記(2),(3)のように、分岐予測方式によって、命令コードの特徴により得手不得手があり、複数の分岐予測方式の結果から、よりあたりそうな方を選択して予測する方法がある。【００５５】
予測精度を上げるために複数の予測方式、およびそれを選択するための予測結果の成否履歴Counterテーブルを備えた方法
分岐予測結果の成否履歴Counterテーブルは2-bit saturation counterを命令アドレスで索引する方法が典型的である。それぞれの予測方式について2-bit saturation counterは予測が正しかったら+1,失敗したら-2する。【００５６】
分岐予測にどちらを採用するかはこのCounter値の大小を比較した大きい方を選択する。(同じ値の場合は典型的なベンチマークプログラムの実結果等からどちらか平均的に良好な方を固定的に選択する)
この方式において、いずれの方式においても予測Counterの値が低い場合は予測確度が低いと見なす。【００５７】
図５は、本発明の実施形態に従った情報処理装置の構成例である。
図５において、図１と同じ構成要素には同じ参照番号を付して説明を省略する。
図５において、＄は、キャッシュを意味する。したがって、Ｌ１Ｉ＄は、Ｌ１命令キャッシュを意味する。たとえば、Ｌ１命令キャッシュ１１では、論理アドレスのタグと論理アドレスをＬ１Ｉ＄ＴＬＢ変換した結果とを比較し、一致した場合には、Ｌ１Ｉ＄Dataから、対応する命令を取り出す。ここで、Ｌ１ＩμＴＬＢは、Ｌ１命令マイクロＴＬＢを示す。Ｌ１データキャッシュでは、アドレス生成加算器２８から入力された論理アドレスを入力とし、論理アドレスのタグと、ＴＬＢ変換後の値とを比較し、ヒットした場合には、データをＬ１Ｄ＄Dataから読み出す。ヒットしなかった場合には、Ｌ２キャッシュへのアクセスリクエストがＬ１ムーブインバッファ（Ｌ１ＭＩＢ）に格納され、ＭＩポート（ＭＩＰ）を介して、Ｌ２キャッシュ２５に送られる。ここでは、Ｌ２キャッシュは、物理アドレスでアクセスされることになっているので、ＴＬＢは設けられていない。Ｌ２キャッシュでもミスした場合には、外部メモリにアクセスする。【００５８】
また、図５においては、浮動小数点演算器２７’が記載されているが、整数演算器と基本的に動作は同じである。更に、リネームマップ２０、及び、リネームレジスタファイル・レジスタファイル２１＆２２においては、整数用と浮動小数点用のものがそれぞれ設けられている。【００５９】
以上は、図１とは記載様式は異なるが、図１と共通する部分であり、従来のスーパスカラ型プロセッサの一般的な構成を示している。本発明の実施形態では、前述した処理を行う命令発行・停止制御部３５が設けられている。命令発行・停止制御部３５は、命令フェッチ／分岐予測部１０から、分岐予測確度情報を、リネームマップ２０からは、命令依存関係情報を、Ｌ１、Ｌ２キャッシュ２４、２５からは、Ｌ１データキャッシュヒット／ミス通知、Ｌ２キャッシュヒット／ミス通知、Ｌ２ミスデータ到達通知を受け取る。【００６０】
図６は、前のload命令と後の分岐命令との依存関係を検出するための構成を説明する図である。
図６は、リネームマップの各エントリを示している。リネームマップには、コミット前の命令の物理アドレスと論理アドレスがエントリされている。この各エントリに、Ｌ２キャッシュミスしたか否かを示すＬ２−ｍｉｓｓフラグを設ける。このように、各エントリにＬ２−ｍｉｓｓフラグを設けることにより、後に、分岐命令のＣＣ（Condition Code）を生成する場合に、ＣＣの生成に必要な命令のエントリのＬ２−ｍｉｓｓフラグを参照して、キャッシュミスしているか否かを知ることができる。【００６１】
図７は、キャッシュヒット／ミス予測機構の構成例を示す図である。
load, store命令用のアドレス生成器４１から出力されたアドレスは、Ｌ１Ｄキャッシュのタグ処理部に入力されるが、図７では、キャッシュヒット／ミスヒストリテーブル４０を設けている。キャッシュヒット／ミスヒストリテーブルは、キャッシュから、キャッシュミス、ヒットの通知を受け取り、Ｌ１キャッシュのインデックスごとに、キャッシュミス、ヒットした数をカウントした値を格納するものである。すなわち、インデックスごとに、Ｌ１ヒットの数、Ｌ１ミスの数を４ビット程度のカウンタ値として記憶しておき、Ｌ１ミスの数が比較的大きければ（４ビットであらわされる１６値の半分あるいは、１／４以上程度の大きさ）、ミスする可能性が高いとみなす。ヒット時には、ヒット値を＋１、ミス時にはミス値を＋１する。ヒット値あるいは、ミス値のいずれかがオーバフローして、次にその反対のキャッシュヒット／ミス結果となったときには、ヒット値、ミス値ともに０クリアする。基本的にＬ１アクセスと同時に検索するが、Ｌ１キャッシュが他の優先度の高い要因でビジー状態であった場合でもキャッシュヒット／ミスヒストリテーブルを検索できるようにしておく。ヒット／ミス予測部４２は、キャッシュヒットするか、ミスするかを予測し、この予測結果を命令発行停止／再開制御部へ通知する。インクリメンタ４３は、キャッシュヒットあるいはミスするたびに、ヒット値、ミス値をインクリメントするものである。【００６２】
キャッシュにヒットすると予測した場合には、命令発行は継続されるが、キャッシュミスが予測された場合には、条件分岐命令の後続の命令の発行を停止する。しかし、この予測が外れる場合がある。したがって、ミスを予測してヒットであったと確定した場合には、直ちに命令発行を再開し、ヒットと予測してミスであったと確定した場合には、直ちに、命令発行を停止する。【００６３】
図８及び図９Ａ、Ｂは、分岐予測確度検出のための構成の一例を示した図である。
図８は、ＷＲＧＨＴを用いた構成である。ＷＲＧＨＴについては、特開２００４−０３８３２３号公報に詳しく記載されているので、以下では概略説明する。【００６４】
図８において、図５と同じ構成要素には同じ参照符号を付している。
命令フェッチアドレス生成部４８から命令フェッチアドレスが発行されると、Ｌ１キャッシュ４５に入力され、命令が実行されるとともに、ブランチヒストリ４７に入力され、分岐予測がされる。分岐命令の実行によって分岐が確定すると、分岐命令用のリザベーションステーション１６からＷＲＧＨＴ４６とブランチヒストリＢＲＨＩＳ４７に確定分岐先が入力される。ＷＲＧＨＴ４６は、ローカルヒストリテーブルとも呼ばれるものであり、各アドレスの命令ごとに分岐履歴を格納するものである。ＷＲＧＨＴ４６とブランチヒストリＢＲＨＩＳ４７とが協同して、予測確度の付いた分岐予測を行う。ＷＲＧＨＴ４６の動作を、図８の（ａ）の四角の中に記載された図に基づいて説明する。現在の状態が、ＮＮＮＴＴＮであるとする。ここで、過去の分岐結果が、Ｎは、Not Taken、ＴはTakenであったことを意味する。次の回で、分岐結果がNot Takenであった場合、状態が、ＮＮＮＴＴＮＮとなる。ここで、最初のＮが３回続いているので、次のＮも３回続くであろうと予測し、次の分岐予測をＮ、すなわち、Not Takenとする。そして、ブランチヒストリＢＲＨＩＳ４７の対応するエントリを削除する。次の回での分岐結果がTakenであった場合には、状態が、ＮＮＮＴＴＮＴとなる。すると、Ｔは２回続いているので、またＴが２回続くであろうと予測し、次の分岐予測をＴとする。そして、ＢＲＨＩＳ４７にエントリを生成する。【００６５】
ＷＲＧＨＴ４６は、条件分岐命令の分岐確定後、ＣＳＥ２３へ完了通知送出と同時にブランチヒストリ（ＢＲＨＩＳ）更新制御部４９へ分岐情報を送り、ＢＲＨＩＳ４７の更新を行う。ＢＲＨＩＳ４７は、予めエントリを削除することで、次回の分岐予測をNot Takenとし、エントリを登録することで、次回の分岐予測をTakenと予測する情報を与えている。ＷＲＨＩＳ４６にエントリがない場合は、図９Ａの表１に示される論理で分岐予測して、ＢＲＨＩＳ４７を更新する。【００６６】
ＷＲＧＨＴ４６にエントリがある場合は、図９Ｂの表２に示される論理で分岐予測してＢＲＨＩＳ４７を更新する。基本的に、その分岐命令について、現在Takenが継続中であれば、前回Takenが継続した回数に一致しなければ、更にTakenが継続し、一致しなかったら、前回同様、次回はNot Takenになるものと予測する。【００６７】
また、ＷＲＧＨＴ４６にエントリが登録されるのは分岐ミスでTakenだった場合であり、登録順に古いものから捨てられる。
前回のＷＲＧＨＴ４６へのエントリの登録時に分岐ミスであり、ＷＲＧＨＴ４６にヒットしなかった場合、予測確度の高さを示すDizzyフラグが１となるので、
予測確度が高い：予測時Dizzy_Flag=0である。
予測確度が低い：予測時Dizzy_Flag=1である。【００６８】
図９Ａ、Ｂの表１及び表２において、最初の列は、「ＢＲＨＩＳを用いた分岐予測」であり、TakenかNot Takenとなる。２番目の列は、「分岐確定後の分岐結果」である。３番目の列は、表１が「次の分岐予測内容」であり、表２が「次の分岐予測内容がNot TakenのときのＢＲＨＩＳへの操作」である。４番目の列は、表１が「ＢＲＨＩＳへの操作」であり、表２が「次の分岐予測内容がTakenのときのＢＲＨＩＳへの操作」である。Dizzyフラグは、ＢＲＨＩＳに登録されるフラグであり、このフラグがｏｆｆのとき、すなわち、Dizzy_Flagが０のとき、予測確度が高いことを示し、このフラグがｏｎのとき、すなわち、Dizzy_Flagが１のとき、予測確度が低いことを示す。nopは何もしないことを示す。【００６９】
図１０は、ＢＨＴを使った分岐予測方式について説明する図である。
ＢＨＴ（Branch History Table）は、各アドレスに、００：確度の高いNot Taken、０１：確度の低いNot Taken、１０：確度の低いTaken、１１：確度の高いTakenの２ビットずつを格納する。ＢＨＴを索引する場合には、命令フェッチに使ったプログラムカウンタ（Fetch PC)の下位ビットと、ＢＨＲ（Branch History Register）のビットを結合したインデックスを使う。ＢＨＲは、どの分岐命令の分岐履歴かということは関係なく、プログラムを順次実行した場合の、実行順に分岐命令がどのように分岐したかを示す分岐履歴である。図１０の場合、５ビットのレジスタとなっている。すなわち、プログラムに沿って、現時点での実行位置より５つ前の分岐命令までさかのぼって、分岐命令がTakenだったか、Not Takenだったかを格納している。言い換えれば、ＢＲＨＩＳとＷＲＧＨＴが各分岐命令について分岐命令ごとに分岐履歴を利用して分岐予測を行う、ローカルな分岐予測である。これに対し、ＢＨＴ方式では、このＢＨＲの履歴が、プログラムの流れに沿ったものであり、どの分岐命令かを問題にしていないという意味で、グローバルな分岐履歴を用いている。したがって、ＢＨＴを用いた分岐予測は、プログラムカウンタＰＣでどの命令かを指定するのみではなく、ＢＨＴの履歴も使って、分岐予測をする点で、グローバルな内容を含んだ分岐予測である。【００７０】
ＢＨＴ方式と、ＢＲＨＩＳ＆ＷＲＧＨＴ方式とでは、分岐予測に得意不得意があり、いずれの予測方式がより優れているかを言うことができるものではない。むしろ、両方を適切に使い割ることが良いと考えられる。【００７１】
図１１は、ＢＨＴとＷＲＧＨＴ＆ＢＲＨＩＳとを組み合わせた分岐予測確度検出のための構成例を示す図である。
図１１において、図８と同じ構成要素には同じ参照符号を付して説明を省略する。図１１においては、図８の構成に、ＢＨＴ５０とプレディクションカウンタ５１を設けたものとなっている。ＢＨＴ５０は、ＷＲＧＨＴ＆ＢＲＨＩＳ４６＆４７と合い補って分岐予測をするものであり、プレディクションカウンタ５１が、いずれかからの分岐予測結果を最終的な分岐予測結果として選択する。分岐確度は、ＢＨＴからの予測の場合には、前述したことから明らかなように、どのようなビットが出力されているかを見れば、確度が高いか低いかがわかり、ＷＲＧＨＴ＆ＢＲＨＩＳからの予測の場合、Dizzyフラグを見れば、確度が高いか低いかがわかる。【００７２】
プレディクションカウンタ５１は、前述の2-bit saturation counterが２個組み合わされたものであり、一方が、ＷＲＧＨＴ＆ＢＲＨＩＳ用カウンタ、他方が、ＢＨＴ用カウンタとなっている。このsaturation counterは、分岐予測が当たると、カウンタ値を＋１し、外れると−２するようになっており、ＷＲＧＨＴ＆ＢＲＨＩＳとＢＨＴの内、分岐予測の確度が大きい方がカウンタ値が大きく、選択されるようになっている。【００７３】
図１２は、ＡＰＢと本発明の実施形態の使用形態について説明する図である。
ＡＰＢは、前述したように、分岐予測された側とは違う方向の分岐の命令をフェッチし、実行系に投入する機構である。ＡＰＢのエントリ数が２であり、順番にＡＰＢを使用する場合を考える。図１２の場合、まず、命令シーケンス０が実行され、分岐命令１に来たとする。分岐予測された方の命令シーケンスは、命令シーケンス１として命令バッファにフェッチし、デコーダやリザベーションステーションなどの実行系に投入される。一方、分岐予測されなかった方の命令とその後続の命令も命令シーケンス１Ａとして、ＡＰＢの１つ目のエントリにフェッチし、実行系に投入する。ここで、命令バッファからの命令シーケンスとＡＰＢからの命令シーケンスの両方を実行系に投入する必要があるが、この場合には、命令バッファとＡＰＢを選択するセレクタ（図１のセレクタ１４）が、１マシンサイクル毎に、交互に命令バッファとＡＰＢとを選択するなどをすることにより、それぞれからの命令シーケンスを実行系に投入するようにする。すると、分岐先が確定することにより、命令バッファかＡＰＢのどちらかからの命令シーケンスは間違ったものとなるが、この場合には、間違った命令シーケンスはコミットされず、分岐先が確定した時点で、ＣＳＥから削除されるようにする。【００７４】
図１２では、命令シーケンス１が正しい命令シーケンスであるとすると、次に、分岐命令２に到達する。ここでまた、分岐予測が行われ、予測された方の命令シーケンスが命令シーケンス２として命令バッファにフェッチされ、実行系に投入される。一方、ＡＰＢは、今、２エントリあるとしているので、２回目の分岐予測においても、予測された方向と反対方向の命令シーケンスを命令シーケンス２Ａとして、ＡＰＢの第２エントリにフェッチし、実行系に投入する。そして、命令シーケンスが分岐命令３に到達すると、やはり分岐予測が行われるが、今度はＡＰＢのエントリが空いていないので、予測方向と反対方向の命令シーケンスを実行系に投入することができない。したがって、本発明が問題とする課題が発生する。そこで、ＡＰＢを使い切った場合に、前述した本発明の実施形態を実行し、命令シーケンス３を命令発行停止制御の対象とする。【００７５】
なお、上記実施形態の説明では、条件分岐命令の次の命令から発行を停止することを述べたが、ＳＰＡＲＣなどマシンにおける命令セットでは、分岐命令の次のラインの命令まで発行してから、分岐先の命令の発行に飛ぶという、遅延スロットの問題がある。この場合には、発行を停止するのは、遅延スロットの次の命令からとすればよい。【００７６】
図１３は、本発明による効果を表すタイミングの例を示す図である。
図１３において、マシンサイクルの各記号は、図２と同じである。
命令（１）が生成するＣＣを分岐命令（３）が［１０］で受け取り、［１１］で分岐ミスが判明し、正しいパスの先頭命令（４）の命令フェッチが開始される。命令（２）は、load命令であり、キャッシュミスを起こし、キャッシュミスしたデータが供給可能となるタイミングに合わせて［１６］でＬ１データキャッシュパイプラインが起動される。コミットはin-orderで行われるため、命令（３）のコミットは、命令（２）と同時に行われる［２６］まで待たされる。分岐命令の後続命令が発行されている場合は、命令（５）のＥサイクルは、命令（３）のＷサイクル［２６］以降に可能となるため、それまで（５）以降の命令発行が待たされてしまっている。分岐命令の後続命令が発行抑止されている場合は、［１６］から直ちに正しいパスの命令発行を行うことが出来る。【００７７】
図１４は、リネーミングマップを分岐命令ごとに保持して、分岐ミスを契機に書き戻す機構を持つ場合の命令実行サイクルの例を示す図である。
図１４において、マシンサイクルの各記号は、図２と同じである。【００７８】
命令（１）が生成するＣＣを分岐命令（３）が［１０］で受け取り、［１１］で分岐ミスが判明し、正しいパスの先頭命令（４）の命令フェッチが開始される。命令（２）は、load命令であり、キャッシュミスを起こし、キャッシュミスしたデータが供給可能となるタイミングに合わせて［１６］でＬ１データキャッシュパイプラインが起動される。コミットは、in-orderで行われるため、命令（３）のコミットは命令（２）と同時に行われる［２２］まで待たされる。リネーミングマップは、誤ったパスの最後に発行された命令（４）における状態であるが、分岐命令（３）の状態に、［１５］までに戻すことにより、分岐命令（３）のコミットを待たずに、（５）以降の正しいパスの命令発行を行うことが出来る。【００７９】
図１５は、［方法１］、［方法２］の動作例を示すタイミング図である。
命令（１）が生成するＣＣを分岐命令（７）が［１２］で受け取り、［１３］で分岐ミスが判明し、正しいパスの先頭命令（９）の命令フェッチが開始される。命令（２）はload命令であり、キャッシュミスを起こし、キャッシュミスしたデータが供給可能となるタイミングに合わせて［２４］でＬ１データキャッシュパイプラインが起動される。（７）の分岐命令発行時、［９］において発行命令停止条件を検出して、以降の命令発行を停止する。コミットはin-orderで行われるため、命令（３）のコミットは命令（２）と同時に行われる［２２］まで待たされる。リネーミングマップは、ミスした分岐命令における状態であるため、分岐命令（７）のコミットを待たずに（９）以降の正しいパスの命令発行を［１８］から行い、（８）の分岐命令の次の誤ったパスの命令は命令フェッチパイプラインから削除する。また、分岐命令（７）の予測が正しいパスであった場合は、正しいパスであると判明する［１３］のＥサイクルが有効となり、［１４］から命令発行が再開される。【００８０】
図１６は、１エントリのＡＰＢを有する場合に本発明を適用した場合のマシンサイクルの例を示すタイミング図である。
図１６において、マシンサイクルの各記号は図２と同じである。【００８１】
命令（３）の分岐命令１をフェッチし、ＡＰＢのエントリが空いていてＡＰＢを使用する条件を満たすと判断され、予測の正方向の命令フェッチ（４）を継続する一方、予測と逆方向の命令フェッチ（５）を開始してＡＰＢに格納し、ＡＰＢから命令発行を行う。命令（６）の分岐命令２は、ＡＰＢを使い切っているなど、後続命令の発行を停止する条件を満たすと判断し、後続命令（８）の命令発行を待たせる。（７）の分岐命令２は予測ミスを起こすが、正しいパスの命令発行を分岐命令のコミットを待つことなく開始することができる。ＡＰＢが使用される場合は、ＡＰＢを使い切ってから後続命令発行停止が行われるため、命令発行停止による性能低下リスクをより抑えることができる。
【図１】
2008029450.tif 000003
【図２Ａ】
2008029450.tif 000004
【図２Ｂ】
2008029450.tif 000005
【図２Ｃ】
2008029450.tif 000006
【図２Ｄ】
2008029450.tif 000007
【図３】
2008029450.tif 000008
【図４】
2008029450.tif 000009
【図５】
2008029450.tif 000010
【図６】
2008029450.tif 000011
【図７】
2008029450.tif 000012
【図８】
2008029450.tif 000013
【図９Ａ】
2008029450.tif 000014
【図９Ｂ】
2008029450.tif 000015
【図１０】
2008029450.tif 000016
【図１１】
2008029450.tif 000017
【図１２】
2008029450.tif 000018
【図１３】
2008029450.tif 000019
【図１４】
2008029450.tif 000020
【図１５】
2008029450.tif 000021
【図１６】
2008029450.tif 000022
【手続補正書】
【提出日】平成20年12月17日(2008.12.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
分岐命令の分岐予測を行い、命令を投機的に実行する情報処理装置であって、
ロード命令のキャッシュミスを検出するキャッシュミス検出手段と、
該ロード命令の後続の条件分岐命令が、実行時点で、分岐方向が確定していない場合に、該条件分岐命令の後続の命令の発行を停止する命令発行停止手段と、
を備え、
分岐予測ミスによって生じる発行命令のキャンセルのための時間を削除し、分岐予測ミスによるペナルティをキャッシュミスによる待ち時間に隠蔽する
ことを特徴とする情報処理装置。
【請求項２】
更に、
前記ロード命令と前記後続の条件分岐命令との依存関係を検出する依存関係検出手段を備え、
該ロード命令と該条件分岐命令とが依存関係にある場合に、該条件分岐命令の後続の命令の発行を停止することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
更に、
発行したロード命令がキャッシュミスするか否かが確定する前に、キャッシュミスするか否かを予測するキャッシュミス予測手段を備え、
該キャッシュミス予測手段がキャッシュミスを予測した場合に、前記条件分岐命令の後続の命令の発行を停止することを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記キャッシュミス予測手段がキャッシュミスと予測したロード命令がヒットだと判明した場合には、命令の発行を再開し、ヒットと予測したロード命令がキャッシュミスしたと判明した場合には、命令の発行を直ちに停止することを特徴とする請求項３に記載の情報処理装置。
【国際調査報告】
2008029450.tif 000023
2008029450.tif 000024
2008029450.tif 000025
2008029450.tif 000026