(57)【特許請求の範囲】
【請求項１】
分岐予測を伴うパイプライン処理を行う情報処理装置であって、
命令が事象待ちのための分岐命令であることを検出する検出手段と、
前記検出手段が前記事象待ちのための分岐命令を検出したとき、該分岐命令に対する分岐予測を抑止する抑止手段と
を備えることを特徴とする情報処理装置。
【請求項２】
前記抑止手段は、前記事象待ちのための分岐命令により分岐操作が実行されたとき、実行結果に基づく分岐予測テーブルの更新を抑止することで、該分岐命令のフェッチ時に行われる分岐予測を抑止することを特徴とする請求項１記載の情報処理装置。
【請求項３】
前記抑止手段は、前記事象待ちのための分岐命令のデコード時に行われる分岐予測を抑止することを特徴とする請求項１記載の情報処理装置。
【請求項４】
事象待ちのための専用の条件コード情報を格納する格納手段をさらに備え、前記検出手段は、前記事象待ちのための分岐命令が該専用の条件コード情報を参照する条件分岐命令であることを検出し、該専用の条件コード情報を参照するための制御信号を出力することを特徴とする請求項１記載の情報処理装置。
【請求項５】
前記格納手段に格納された前記専用の条件コード情報は、待ち事象の発生元からの信号により更新されることを特徴とする請求項４記載の情報処理装置。
【請求項６】
前記検出手段は、前記事象待ちのための分岐命令が、前記専用の条件コード情報を条件として分岐判定を行うようなあらかじめ決められた条件分岐命令であることを検出することを特徴とする請求項４記載の情報処理装置。
【請求項７】
分岐予測を伴うパイプライン処理を行う情報処理方法であって、
与えられた命令が事象待ちのための分岐命令であるか否かを判定し、
前記与えられた命令が前記事象待ちのための分岐命令以外の分岐命令であるとき、該与えられた命令に対する分岐予測を行い、
前記与えられた命令が前記事象待ちのための分岐命令であるとき、該与えられた命令に対する分岐予測を抑止する
ことを特徴とする情報処理方法。
【請求項８】
前記与えられた命令が前記事象待ちのための分岐命令であるとき、該事象待ちのための分岐命令が事象待ちのための専用の条件コード情報を参照する条件分岐命令であるか否かを判定し、該事象待ちのための分岐命令が該条件分岐命令であるとき、該専用の条件コード情報を参照して分岐判定を行うことを特徴とする請求項７記載の情報処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、分岐予測機構を用いてパイプライン処理を行う情報処理装置およびその方法に関する。
【０００２】
【従来の技術】
近年の計算機においては、命令処理の高速化、特に、分岐処理の高速化を図るために、分岐予測テーブルを使用した分岐予測機構が用いられている。この分岐予測機構は、指定された命令アドレスに対して、分岐命令の有無、分岐するか否かの予測情報、および分岐先（分岐ターゲット）命令アドレスの情報を分岐予測テーブルに持ち、命令フェッチの時に命令フェッチアドレスを用いてこのテーブルを検索する。もし、分岐命令でありかつ分岐するという情報が登録されていた場合には、対応する分岐先命令アドレスを用いて分岐先の命令フェッチが起動される。
【０００３】
これにより、命令をフェッチしデコードすることなく、より早いタイミングで分岐先の命令のフェッチを起動することが可能となる。その結果、分岐先命令のフェッチを待つ時間等が改善され、計算機の処理が高速化される。
【０００４】
このようなテーブルを使用した分岐予測の詳細は、各種文献や特許出願に記載されている。例えば、特開平６−３２４８６５（「マルチ予測型分岐予測機構」、特願平３−２５２８７２）では、デコード時に行う分岐予測と命令フェッチ時に行う分岐予測の両方を使う技術が示されている。また、この文献では、分岐予測に関する各種先行技術が紹介されている。
【０００５】
ループ構造を持つプログラムは、分岐予測を行うことにより、ほとんどの場合に高速化される。なぜなら、以前に分岐した命令による分岐操作は再び分岐すると予測され、ループ処理を行うプログラムの分岐予測は、ループから抜ける場合を除いて当たるからである。特に、ループの高速化に着目している先行技術としては、以下のような特許出願が存在する。
・特開平７−７３１０４
（「キャッシュ・システム」、特願平６−１１７０５６）
・特表平１０−５１００７６
（「限定ラン分岐予測」、特願平８−５１８８７６）
・特開平１０−３３３９０６
（「分岐予測装置」、特願平９−１３９７３６）
・特開平４−１０１２１９
（「命令分岐予測方式」、特願平２−２１８６５５）
・特開昭６３−１４１１３２
（「命令先取り装置」、特願昭６１−２８９３６３）
・特開平１−２７１８４２
（「情報処理装置」、特願昭６３−１００８１８）
これらの技術は、大きく分類すると以下のように分類される。
（１）分岐先の命令フェッチを高速化する。
（２）ループの振る舞いを正確に予測する。
（３）分岐予測失敗時のペナルティを低減する。
【０００６】
図１６は、一般的なパイプライン計算機の概略構成図である。命令フェッチ制御部１１から命令フェッチアドレスとフェッチリクエストが、命令メモリアクセスパイプライン（命令フェッチパイプライン）１２に送られると、そのアドレスに従って命令コードがフェッチされ、命令バッファ１３に供給される。そして、命令バッファ１３に蓄積された命令は命令実行パイプライン１４に渡され、命令の実行が開始される。
【０００７】
命令実行パイプライン１４では、演算命令の実行の他に、命令が分岐命令であった場合には分岐判定を行い、分岐するか否かを示す情報（分岐taken 情報）や分岐先アドレス等を命令フェッチ制御部１１に送る。そして、命令フェッチ制御部１１の制御により、新しい命令フェッチアドレスに従って命令フェッチが継続される。
【０００８】
図１７は、命令フェッチ制御部１１の回路の構成図である。図１７の回路は、インクリメンタ２１、２２、分岐予測テーブル（Branch Target Table ，ＢＴＢ）２３、比較回路（ＣＭＰ）２４、ＡＮＤ回路２５、選択回路（セレクタ，ＳＥＬ）２６、２７、およびプリフェッチプログラムカウンタ（Pre-Fetch Program Counter ，ＰＦＰＣ）２８を備える。
【０００９】
分岐フェッチ制御において、分岐予測をまったく行わない場合には、信号Ｄ ＴＡ（デコードステージで処理されている命令の分岐先アドレス）、ＢＴＢ２３、比較回路２４、ＡＮＤ回路２５、および２入力選択回路２６は不要である。
【００１０】
この場合には、最初のフェッチアドレスは信号ＰＣを経由し、選択回路２７により選択されて、ＰＦＰＣ２８に入る。このＰＦＰＣ２８に保持されたアドレスが命令フェッチアドレスとなり、図１６の命令メモリアクセスパイプライン１２に送られる。このとき、インクリメンタ２２は、ＰＦＰＣ２８の出力信号を入力として、それに８を加算したアドレスを出力する。
【００１１】
ここで、分岐成立を表す信号（後述するＴＡＫＥＮ）がアサートされなければ（論理“１”にならなければ）、次のクロックで、インクリメンタ２２の出力が選択され、そのアドレスがフェッチされる。このようにして、連続した命令のフェッチが行われる。ただし、ここでは、命令の大きさは４バイトであり、一度に２命令ずつフェッチされるものとする。
【００１２】
図１８は、図１６の命令実行パイプライン１４の回路を示している。図１８の回路は、ＢＴＢ２３、レジスタ３１、３３、３４、３５、３６、３８、３９、４１、４２、４３、４４、４５、４６、４７、４８、４９、５１、５３、５４、５５、５６、５７、５８、５９、汎用レジスタ（general purpose register，ＧＲ）３２、演算器（arithmetic and logic unit ）３７、デコーダ（ＤＥＣ）４０、分岐判定回路（ＢＲＣ ＤＥＣＩＳＩＯＮ）５０、および加算器５２を備える。
【００１３】
図１８において、各命令の処理ステージを表す記号Ｄ、Ａ、Ｅ、Ｗは、それぞれ、デコードステージ（Ｄステージ）、アドレス計算ステージ（Ａステージ）、実行ステージ（Ｅステージ）、ライトステージ（Ｗステージ）に対応する。
【００１４】
この例では、２つの命令がパイプライン動作している様子が示されている。先行する命令は比較命令（ＣＭＰ）で、この命令は、比較する２つの値をＧＲ３２から読み出し、ＥステージでＡＬＵ３７を使用して比較演算を行い、その結果の条件コード（ＣＣ）をレジスタ３８に書き込んでいる。
【００１５】
また、後続の命令が分岐命令（ＢＲＣ）で、この命令は、Ｄステージで、信号Ｄ ＰＣ（Ｄステージで処理されている命令のプログラムカウンタ）と分岐命令の中の分岐先アドレスオフセット部分（ＯＦＦＳ）と定数４から分岐先アドレスを計算している。
【００１６】
また、デコードによって分岐命令か否かを示す信号Ｄ ＢＲＣ、分岐の条件を示す信号Ｄ ＣＮＤを作成し、パイプラインタグとして管理して、後続ステージに転送している。先行する比較命令の結果のＣＣを分岐判定に用いるので、後続の分岐命令の分岐判定はＥステージで行われる。ここでは、Ｅ ＣＮＤで選択されたＣＣの条件を用いて、分岐判定回路５０により分岐判定が行われる。
【００１７】
分岐が成立した場合には、分岐判定回路５０からの信号ＴＡＫＥＮがアサートされ、図１７において信号Ｅ ＴＡ（Ｅステージで処理されている命令の分岐先アドレス）が選択されて、このアドレスがＰＦＰＣ２８に入る。
【００１８】
このアドレスＥ ＴＡは、図１８に示すように、分岐命令のＤステージで、信号Ｄ ＰＣ、オフセット、および４を加算して得られたアドレスを、パイプラインタグとして管理し、Ｅステージまで転送したものに対応する。ただし、ここでは、分岐命令の分岐先アドレスは、後続命令を指し示すプログラムカウンタの値と分岐命令の中のオフセットの和で定義されているものとする。
【００１９】
次に、ＨＩＮＴビットと呼ばれる命令の一部を使って分岐予測を行った場合の動作を説明する。このＨＩＮＴビットに基づく予測は、命令によっては分岐する場合としない場合の予測が命令を実行する前に高い確率で可能な場合があるという特徴を使って、処理の高速化を図る技術である。
【００２０】
例えば、ｆｏｒｔｒａｎのＤＯ文やＣ言語のｆｏｒ文でループを繰り返すために使用される分岐操作は、分岐する可能性が高く、ループを抜け出す判定で使用される分岐操作は、分岐する可能性が低い。この情報を命令コードの一部にＨＩＮＴビットとして埋め込み、ＣＣ等を使った条件判断ができる前のデコード時に分岐先のフェッチを起動することで、処理が高速化される。
【００２１】
このために、図１７では、信号Ｄ ＴＡが使用され、図１８のＤステージでデコードされた信号Ｄ ＨＩＮＴがアサートされた場合には、信号Ｄ ＴＡが選択され、これによりＰＦＰＣ２８が更新される。この結果、Ｅステージで切り替えるのに比べて、２クロック早く分岐先の命令フェッチを行うことができる。
【００２２】
ただし、Ｅステージの分岐判定で分岐予測が誤ったことが判明した場合には、インクリメンタ２１から出力されるＥ ＰＣ＋４が選択され、分岐命令の直後の命令からフェッチし直す。分岐予測が誤った場合の他の処理方法としては、予測しなかった側の命令もあらかじめフェッチしておき、命令実行のやり直しだけを行う方法や、分岐しない場合の後続命令もあらかじめ実行しておく方法等が存在する。
【００２３】
分岐予測を誤ったかどうかは、パイプラインタグによりＥステージまで転送されてきたＨＩＮＴ情報（Ｅ ＨＩＮＴ）と、ＥステージでＣＣから作成した信号ＴＡＫＥＮを比較することで、判定できる。このとき、Ｅ ＨＩＮＴ＝１  ａｎｄ  ＴＡＫＥＮ＝０が成立すれば、分岐予測が誤ったものと判定できる。
【００２４】
次に、ＢＴＢ２３を使用して分岐予測を行う場合の動作を説明する。先のＨＩＮＴビットを使った予測では、分岐予測の起動を早くしているものの、図１６の命令実行パイプライン１４に命令が読み出されて初めてそれが起動されるため、上述の例では分岐先の命令フェッチが２クロックしか早くなっていない。さらに早いタイミングで分岐先の命令フェッチを起動するためには、図１６の命令フェッチ制御部１１による制御の段階で分岐先のフェッチを行う必要がある。
【００２５】
そのために、フェッチアドレスから分岐先アドレスを求めるための分岐予測機構が追加される。図１８のＢＴＢ２３は、あたかも主記憶に対する命令キャッシュのように、分岐先アドレスをキャッシュする。分岐命令が実行されると、その分岐命令のアドレスとそのときの分岐先命令のアドレスが、ＢＴＢ２３に登録される。
【００２６】
図１９は、このようなＢＴＢ２３を含む命令メモリアクセスパイプライン１２の回路を示している。命令メモリアクセスパイプライン１２は、Ｐ（プライオリティ）ステージ、Ｔ（テーブル）ステージ、Ｃ（チェック）ステージ、およびＲ（結果）ステージからなり、図１８のＢＴＢ２３の他に、レジスタ６０、６１、命令キャッシュ（Ｉ−ｃａｃｈｅ）６２、レジスタ群６３、および選択回路（Ｗａｙ  ｓｅｌ）６４を備える。
【００２７】
ＢＴＢ２３は、レジスタ６０に保持される読み出しアドレスを入力とする読み出しポートと、図１８のレジスタ５８に保持される書き込みアドレスを入力とする書き込みポートとを備える２ポートＲＡＭ（random access memory）で構成されている。図１９においては、ＢＴＢ２３の読み出し系の回路のみが示されている。
【００２８】
また、命令バッファ１３は、レジスタ群６５と選択回路６６を備え、レジスタ６７は、図１８のレジスタ３１または３９に対応する。
命令フェッチ時において、ＰＦＰＣ２８からのアドレスを用いて命令キャッシュ６２が検索されると同時に、同様の方法でＢＴＢ２３の検索が行われる。もし、ＰＦＰＣ２８のアドレスがＢＴＢ２３に登録されていれば、次にＰＦＰＣ２８に保持されるアドレスがＢＴＢ２３の分岐先アドレスに変更される。これにより、命令フェッチ時に、命令フェッチアドレスが予測された分岐先アドレスに切り替えられる。
【００２９】
命令実行パイプライン１４において、実際に分岐操作が行われた場合には、信号Ｅ ＢＲＣがアサートされ、ＢＴＢ２３が更新される。このとき、図１８および後述する図９に示すように、パイプラインタグで転送された信号Ｅ ＰＲＤおよび信号ＴＡＫＥＮから、分岐判定回路５０により分岐予測情報ＮＷ ＰＲＤ（Ｎｅｘｔ  Ｗｒｉｔｅ Ｐｒｅｄｉｃｔｉｏｎ）が作成される。そして、信号ＮＷ ＰＲＤが、信号Ｅ ＰＣおよびＥ ＴＡとともに、ＢＴＢ２３に書き込まれる。以上が従来の典型的な分岐予測動作の概要である。
【００３０】
【発明が解決しようとする課題】
しかしながら、上述した従来の分岐予測技術には、次のような問題がある。
上述した（２）の方法では、ループの回数がレジスタに保持されており、前回のループの回数やパターンからループの脱出が予測される。しかし、このような予測が不可能なループも存在する。例えば、入出力装置（ＩＯ）の動作完了、複数のプロセッサエレメント（ＰＥ）間のバリア同期の完了、または主記憶アクセスの完了を待つようなループ処理が行われる場合がある。
【００３１】
図２０は、このような事象待ちを行う並列計算機の例を示している。図２０の並列計算機は、ｎ＋１個のプロセッサエレメントＰＥ０，ＰＥ１，．．．，ＰＥｎを備える。また、各ＰＥは、中央処理装置（ＣＰＵ）７１、メモリ（主記憶）７２、入出力装置（ＩＯ）７３、ベクトルユニット（Vector Unit ，ＶＵ）７４、および同期回路（ＰＥ  Ｓｙｎｃ）７５を備える。
【００３２】
ＣＰＵ７１、メモリ７２、ＩＯ７３、ベクトルユニット７４、および同期回路７５は、アドレスバス７６（Ａ）およびデータバス７７（Ｄ）により互いに結合されており、ＣＰＵ７１とベクトルユニット７４は、ベクトルコマンドバス７８（ＶＣ）およびベクトルデータバス７９（ＶＤ）により結合されている。また、ＣＰＵ７１は、分岐ユニット（Branch Unit ，ＢＲＵ）８１、アクセス制御ユニット（Access Control Unit ）８２、およびベクトルインタフェース制御ユニット（Vector Interface Control Unit ）８３を備える。
【００３３】
ＩＯ７３は、データの入出力に関する動作を行い、ＣＰＵ７１は、必要に応じて、その動作の完了を待ち合わせる。
同期回路７５は、ＰＥ間の同期を取るために設けられる。この同期回路７５は、ＩＯの一部として（メモリマップドＩＯも含む）、あるいは専用命令で、ＣＰＵ７１からアクセスできるようになっている。各ＰＥが分担している仕事を完了すると、ＣＰＵ７１は、事象完了を示すデータを同期回路７５に書き込む。書き込まれた情報は、各ＰＥの同期回路７５同士を接続する信号線８４により、すべてのＰＥに伝播する。そして、あらかじめ決められた条件が成立した場合に、ＰＥ間の同期待ち解除が成立する。
【００３４】
また、ベクトルユニット（ＶＵ）７４は、計算処理を高速化するために設けられ、ベクトル演算器を含む。ベクトル演算器では高速な連続演算等は可能であるが、すべての処理を行うことはできない。このため、ベクトル計算機と呼ばれる計算機では、ベクトルユニット７４と共に一般的な構成のＣＰＵ７１も具備している。このＣＰＵ７１は、ベクトル処理を行わないことを明示的に示すために、スカラプロセッサあるいはスカラユニット（Scalar Unit ，ＳＵ）と呼ばれる。
【００３５】
ＶＵ７４で計算した結果をＳＵ７１でさらに処理したり、ＳＵ７１で準備したデータをＶＵ７４で受け取って処理する場合に、これらの２つのユニットのデータの同期を取る機構が必要となる。データ量が少ない場合は、ベクトルデータバス７９が使用されることもあるが、大量のデータを授受する場合は、メモリ７２経由で同期処理が行われる。
【００３６】
まず、ＶＵ７４の計算結果をＳＵ７１が受け取る場合、計算結果はメモリ７２に書き込まれる。ＳＵ７１は、この書き込みの完了を待って、メモリ読み出し命令の実行を開始しなければならない。また、ＳＵ７１の計算結果をメモリ７２経由でＶＵ７４が受け取る場合、計算結果はメモリ７２に書き込まれる。ＶＵ７４は、この書き込みの完了を待って、メモリ読み出し命令の実行を開始しなければならない。したがって、いずれの場合においても、メモリ７２に対する書き込みの完了が待ち合わせられる。
【００３７】
このように、事象の成立を待つことは、計算機の性能を向上させるにあたって、非常に重要な要素となる。ループ処理により事象待ちを行う場合、ループを繰り返すための分岐の性能もさることながら、待ち事象が成立した時にループから脱出する性能が重要になる。
【００３８】
このような事象待ちのための分岐では、ループ回数がレジスタに設定されておらず、毎回ループ回数が不定であるために、従来の技術では予測が不可能であったり不正確であったりした。具体的には、ほとんどの予測方法において、最近の実行で分岐していた回数が多ければ分岐すると予測するために、ループ脱出時には分岐予測ミスとなり、事象待ちで重要となるループ脱出速度が低下していた。
【００３９】
また、従来の計算機では、分岐条件フラグについて、先行する演算の結果から符号や大小関係を判断していた。したがって、ＣＰＵ７１の外部のＩＯ７３の動作完了やバリア同期完了等の条件を待つ場合は、外部信号を参照するロード命令（メモリマップドＩＯの場合）やＩＯ命令で外部情報を参照し、論理演算等で条件フラグに外部状態を反映させてから、分岐操作を行っていた。
【００４０】
このため、分岐操作が高速に実行できても、外部情報の参照時間と論理演算時間の和より短時間でループを実行することができない。したがって、この和の時間以上に速く待ち解除の判断（サンプリング）を行うことはできず、ループ解除のための待ち時間が長くなっていた。
【００４１】
すなわち、従来の方法では、待ち解除のためのサンプリング時間のコストと、ループ脱出時に発生する分岐予測ミスによるペナルティ（分岐予測を行うことによる追加所要時間）のコストが発生し、高速な待ち処理を実現することが不可能であった。
【００４２】
本発明の課題は、分岐予測を伴うパイプライン処理において、事象待ち分岐ループの振る舞いの予測を改善し、ループの脱出速度を向上させる情報処理装置およびその方法を提供することである。
【００４３】
【課題を解決するための手段】
図１は、本発明の情報処理装置の原理図である。図１の情報処理装置は、検出手段１０１と抑止手段１０２を備え、分岐予測を伴うパイプライン処理を行う。
【００４４】
検出手段１０１は、命令が事象待ちのための分岐命令であることを検出し、抑止手段１０２は、検出手段１０１が事象待ちのための分岐命令を検出したとき、その分岐命令に対する分岐予測を抑止する。
【００４５】
情報処理装置は、通常、前述したＨＩＮＴビット、分岐予測テーブル等を使用して分岐予測を行いながらパイプライン処理を行っている。検出手段１０１は、例えば、分岐命令認識回路に対応し、与えられた命令が事象待ちのための分岐命令であるか否かを判定する。命令が事象待ちのための分岐命令以外の分岐命令であれば、通常通り、その命令に対する分岐予測が行われ、命令が事象待ちのための分岐命令であれば、抑止手段１０２により、その命令に対する分岐予測が抑止される。
【００４６】
抑止手段１０２は、例えば、事象待ちのための分岐命令により分岐操作が実行されたとき、実行結果に基づく分岐予測テーブルの更新を抑止する。これにより、その分岐命令のフェッチ時に行われる分岐予測が抑止され、分岐命令の後続命令のプリフェッチが促進される。あるいは、抑止手段１０２は、事象待ちのための分岐命令のデコード時にＨＩＮＴビットを用いて行われる分岐予測を抑止する。
【００４７】
このように、本発明のポイントは、事象待ちのための分岐命令に対する分岐予測を抑止することである。これにより、分岐命令の後続命令のプリフェッチが促進され、待ち事象が成立したときに直ちに後続命令を実行することが可能になる。したがって、事象待ち分岐ループからの脱出時の待ち時間が削減される。
【００４８】
さらに、事象待ちのための専用の条件コード情報を格納する格納手段を備えれば、事象待ち分岐ループの処理がさらに高速化される。この場合、上記専用の条件コード情報は待ち事象の発生元からの信号により更新され、検出手段１０２は、事象待ちのための分岐命令が上記専用の条件コード情報を参照する条件分岐命令であることを検出すると、この専用の条件コード情報を参照するための制御信号を出力する。
【００４９】
そして、情報処理装置は、外部参照の命令と論理演算で分岐判定を行う代わりに、出力された制御信号に従って、専用の条件コード情報を参照して分岐判定を行う。これにより、外部参照の命令と論理演算を実行する時間がなくなるため、分岐判定が高速化される。
【００５０】
例えば、図１の検出手段１０１は、後述する図２のデコーダ１１０に対応し、図１の抑止手段１０２は、図２のＡＮＤ回路１１１、１１２、およびレジスタ１１３、１１４に対応する。
【００５１】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本発明においては、計算機等の情報処理装置に、命令が事象待ち分岐命令であることを検出する回路を追加する。そして、事象待ち分岐命令が検出された場合には、分岐予測テーブルを更新しないことにより、期待していないループの高速化を抑止し、代わりにループの脱出速度を向上させる。
【００５２】
まず、次のようなループ処理を例に取って、本発明により分岐予測テーブルによる予測を抑止した場合の待ち時間を評価してみる。
0003683439.tif 000002
分岐予測において予測が成功した場合のペナルティを１τと仮定し、予測が失敗した場合のペナルティを６τと仮定すると、分岐予測を行う場合と行わない場合において、条件フラグが立った後、後続の命令を実行するまでの時間は次のようになる。
【００５３】
分岐予測を行う場合は、２τに１回フラグをサンプリングできるので、サンプリング誤差は平均的には（０＋１）／２＝０．５（τ）となる。また、分岐予測を行わない場合は、７τに１回しかサンプリングできないので、平均的には（０＋１＋２＋３＋４＋５＋６）／７＝３（τ）のサンプリング誤差が発生する。
【００５４】
これらのサンプリング誤差に、さらに、後続命令を実行するまでのペナルティを加算して、ループ脱出のための待ち時間を求めてみる。分岐予測を行う場合は、前述したように、ループ脱出時には分岐予測が失敗するため、ペナルティは６τとなる。したがって、ループ脱出時の待ち時間は、０．５＋６＝６．５（τ）となる。これに対して、分岐予測を行わない場合は、ペナルティが発生しないので、ループ脱出時の待ち時間は、３＋０＝３（τ）となる。このように、ループ脱出の性能を向上させるためには、分岐予測を行わない方がよいことが分かる。
【００５５】
ここでは、命令フェッチ時に行われる分岐予測を抑止する例を示したが、命令デコード時に分岐予測が行われる場合には、それも抑止する必要がある。また、デコード時だけに分岐予測を行う計算機においても、分岐予測の抑止が有効なことは明らかである。デコード時の分岐予測を抑止する方法としては、命令コード中に含まれているＨＩＮＴビットのように、デコード時に分岐を示す信号を、非分岐側にマスクする方法が考えられる。
【００５６】
また、本発明においては、条件フラグの変更を外部参照の命令と論理演算で行う代わりに、新たに事象待ち用の専用条件フラグビットを導入し、命令によってその事象待ち条件フラグの指定を行えるようにする。これにより、外部参照および論理演算の時間をなくし、分岐条件のサンプリングに要する時間を短縮することができる。この条件フラグを分岐予測テーブルの更新を抑止する機能と共に用いてループの脱出速度を向上させることで、事象待ちループに対する性能がさらに向上する。
【００５７】
図２は、図１８に示した命令実行パイプライン１４に、このような機構を追加した回路を示している。図２において、図１８と同様の構成要素には同じ符号が付加されており、新たにデコーダ１１０、ＡＮＤ回路１１１、１１２、レジスタ１１３、１１４、１１５、および分岐判定回路５０′が追加されている。図２の回路を図１８の回路と比べると、以下の点で異なっていることが分かる。
（１）デコーダ１１０により、分岐予測を行わないことを示す信号Ｄ ＮＯ ＰＲＤが生成されている。
（２）レジスタ１１３および１１４により、信号Ｄ ＮＯ ＰＲＤがパイプラインタグとして実装されている。
（３）ＡＮＤ回路１１１により、信号Ｄ ＮＯ ＰＲＤがアサートされている時、デコード時における分岐予測を制御する信号Ｄ ＨＩＮＴが無効化（ネゲート）されている。
（４）ＡＮＤ回路１１２により、信号Ｅ ＮＯ ＰＲＤがアサートされている時、ＢＴＢ２３への書き込みを行うための信号ＷＥが抑止されている。
【００５８】
これらの新たな回路の動作を説明する前に、まず、ＢＴＢ２３を用いた分岐予測に関する動作をより詳細に説明する。ＢＴＢ２３の各エントリは、図３に示されるようなフィールドから構成されており、各フィールドは次のような情報を保持している。
【００５９】
Ｖ：ＢＴＢエントリが有効であることを示す情報。
ＰＲＤ：登録されている分岐命令が分岐する可能性を示す分岐予測情報。
ＰＣ：登録されている分岐命令自身のアドレスの一部。
【００６０】
ＴＡ：登録されている分岐命令の分岐先の命令アドレス。
レジスタ６８は、ＰＦＰＣ２８のフィールドＰＣを保持する。比較回路２４は、レジスタ６８に保持された情報とＢＴＢ２３のフィールドＰＣを比較し、両者が一致すれば、信号ＭＡＴＣＨをアサートする。そして、ＡＮＤ回路２５は、フィールドＶの値を表す信号ＶＡＬＩＤ、フィールドＰＲＤのＬＳＢ（Least Significant Bit ）（ビット１）を表す信号ＰＲＤ（１）、および信号ＭＡＴＣＨがアサートされたとき、ＰＦＰＣ２８のアドレスがＢＴＢ２３にヒットしたことを示す信号ＢＴＢ−ＨＩＴをアサートする。
【００６１】
これにより、選択回路２６は、ＢＴＢ２３のフィールドＴＡのアドレスを選択し、ＰＦＰＣ２８のアドレスが予測された分岐先アドレスに切り替えられる。
フィールドＰＲＤに保持される予測ビット（２ビット）は、例えば、図４のように定義される。図４において、ＰＲＤが“１１”、“０１”、“００”、“１０”のとき、分岐予測は、それぞれ、ＳＴ（Strongly Taken）、ＬＴ（Likely Taken）、ＬＮＴ（Likely Not Taken）、ＳＮＴ（Strongly Not Taken）となる。このうち、ＳＴおよびＬＴの場合は、ＰＲＤ（１）＝１であり、ＬＮＴおよびＳＮＴの場合は、ＰＲＤ（１）＝０である。
【００６２】
図５は、この予測ビットの状態遷移を示している。状態ＳＮＴ、ＬＮＴ、およびＬＴにおいて、対応する分岐が実行された場合は、１つ右側の状態に遷移し、状態ＬＮＴ、ＬＴ、およびＳＴにおいて、対応する分岐が実行されなかった場合は、１つ左側の状態に遷移する。
【００６３】
また、ＢＴＢ２３により分岐予測を行う場合、命令バッファ１３は、命令だけでなく、ＢＴＢ２３を使って分岐予測が行われたことを示す信号ＴＡＫＥＮＥＤと分岐予測情報ＰＲＤを保持する。また、予測された分岐先アドレスＴＡは、バッファＴＡ−ＢＵＦ（不図示）に保持される。このＴＡ−ＢＵＦは、後で予測されたアドレスが正しいか否かの判定に使用される。
【００６４】
命令デコード時に命令バッファ１３から読み出された信号ＴＡＫＥＮＥＤが、ＢＴＢ２３を使用した分岐予測を行ったことを示していない場合は、前述したＨＩＮＴビットを用いた制御、あるいは分岐予測をまったく行わない制御を行う。これに対して、信号ＴＡＫＥＮＥＤがＢＴＢ２３を用いた分岐予測を行ったことを示している場合には、分岐予測の正当性を検査する。
【００６５】
まず、命令書換えにより命令が分岐命令でなくなったことは、命令をデコードすることで検査できる。また、分岐先アドレスが正しかったか否かは、プログラムカウンタと命令の分岐先アドレスのオフセット部分と定数を加算した値（Ｄ ＴＡ）と、ＴＡ−ＢＵＦのアドレスを比較することで検査できる。
【００６６】
このような検査により、分岐予測ミスが発生したことが分かれば、ＨＩＮＴビットを用いた制御、あるいは分岐予測をまったく行わない制御を行うことで、分岐先フェッチをやり直すことが可能である。また、分岐予測が失敗したことを示す信号ＦＡＵＬＴと分岐予測情報ＰＲＤは、分岐予測の成功／失敗の判定やＢＴＢ書き込みのために、後続のパイプラインステージに転送される。
【００６７】
ところで、命令のデコード時には、分岐するか否かを完全に判定することはできない。その完全な判定は、ＨＩＮＴビットを用いた場合と同様に、Ｅステージで行われる。Ｅステージまでパイプラインタグとして転送されてきた信号ＴＡＫＥＮＥＤ、ＦＡＵＬＴ、およびＨＩＮＴの情報と、Ｅステージにおいて分岐判定回路５０′により作成された信号ＴＡＫＥＮを比較することで、分岐予測が誤ったかどうかを判定することができる。
【００６８】
図６は、この判定論理と分岐予測ミスが発生した場合の再フェッチアドレスを示している。図６において、記号“−”は“Don't care”を表し、信号ＭＩＳＳは、分岐予測に対する判定結果を表している。ただし、ＢＴＢ２３による分岐予測を行っていない（ＴＡＫＥＮＥＤ＝０）のに、デコード時のＢＴＢ２３による分岐予測が失敗すること（ＦＡＵＬＴ＝１）はありえない。分岐予測ミス（ＭＩＳＳ＝１）の場合には、アドレスＥ ＴＡまたはＥ ＰＣ＋４から命令の再フェッチ等を行って、パイプライン動作がリカバーされる。
【００６９】
次に、本発明に特徴的な動作を説明する。本実施形態においては、同じ条件コードＣＣを参照して分岐判定を行う分岐命令であっても、事象待ちを目的とする分岐命令を通常の分岐命令とは異なる新たな命令コードを用いて定義する。そして、デコーダ１１０がその命令コードをデコードしたとき、事象待ちの分岐命令を検出したことを示す信号Ｄ ＮＯ ＰＲＤを生成する。この信号Ｄ ＮＯ ＰＲＤは、分岐予測を行わないことを示す制御信号として用いられる。
【００７０】
また、信号Ｄ ＮＯ ＰＲＤの別の実現方法としては、事象待ちの条件をＣＣの特定のビットに割り当てることが考えられる。この方法では、分岐の条件コードＣＣのどのビットで分岐判断を行うかを選択する信号Ｄ ＣＮＤが、上記特定のビットを選択しているときに、信号Ｄ ＮＯ ＰＲＤをアサートする。
【００７１】
このような命令実行パイプラインにおいて、通常の分岐命令の場合は、信号Ｄ ＮＯ ＰＲＤがネゲートされるので、従来の分岐予測が機能する。これに対して、事象待ちの分岐命令がデコードされると、信号Ｄ ＮＯ ＰＲＤがアサートされる（Ｄ ＮＯ ＰＲＤ＝１）。
【００７２】
このとき、まず、ＡＮＤ回路１１１には信号Ｄ ＮＯ ＰＲＤが反転されて入力されるため、信号Ｄ ＨＩＮＴの値に依らず、ＡＮＤ回路１１１の出力は“０”となる。したがって、信号Ｄ ＨＩＮＴは、信号Ｄ ＮＯ ＰＲＤにより強制的にネゲートされ、デコード時に分岐先フェッチが起動されることはない。
【００７３】
同様にして、パイプラインタグでＥステージに転送された信号Ｅ ＮＯ ＰＲＤは、ＡＮＤ回路１１２に入力される信号Ｅ ＢＲＣをネゲートするため、ＢＴＢ２３への書き込みを制御する信号ＷＥがネゲートされる。したがって、実際に分岐操作が実行されても、その分岐先アドレス等の情報はＢＴＢ２３に書き込まれない。
【００７４】
この結果、事象待ちの分岐命令は、命令フェッチ時にＢＴＢ２３にヒットすることはなく、フェッチ時に分岐予測に基づく分岐先フェッチを行うことが抑止される。このようにして、事象待ちの分岐命令の場合、分岐命令の後続命令が常にフェッチされるため、待ち事象が成立したときのループ脱出時間を削減することができる。
【００７５】
ところで、図１８および図２の回路では、ＢＴＢ２３に分岐命令だけを登録する構成になっているが、分岐命令に限らず、すべての命令の後続命令のアドレスを指定するオフセットをＢＴＢ２３に登録することもできる。
【００７６】
この場合、命令フェッチ制御部の構成は、図７に示すようになり、命令実行パイプラインの構成は、図８に示すようになる。図７において、図１７と同様の構成要素には同じ符号が付加されており、新たに加算器１１６が追加されている。また、図８において、図１８と同様の構成要素には同じ符号が付加されており、新たにレジスタ１１７、１１８、および選択回路１１９が追加されている。
【００７７】
図７のＢＴＢ２３の中には、オフセットの初期値として“＋８”が入っており、加算器１１６の出力は、通常、２命令後の後続命令を指し示すようになっている。したがって、命令を２命令ずつフェッチすることができる。ＢＴＢ２３の更新時には、分岐先アドレスではなく、分岐先オフセットがＢＴＢ２３に書き込まれる。
【００７８】
分岐先オフセットの値は、図８の回路により生成される。分岐先を指定するオフセットＯＦＦＳは、レジスタ１１７、１１８によりパイプラインタグとして管理され、選択回路１１９に入力される。選択回路１１９は、分岐予測情報ＮＷ ＰＲＤが分岐すると予測している場合は、信号Ｅ ＯＦＦＳを選択し、分岐しないと予測している場合は、２命令後の後続命令へのオフセットを示す“＋８”を選択し、選択された信号を分岐先オフセットとして出力する。
【００７９】
このような構成においても、図２と同様の回路を追加することにより、ＢＴＢ２３への書き込み制御信号がネゲートされ、ＢＴＢ２３による分岐予測が抑止される。
【００８０】
また、図２では、ＢＴＢ２３への書き込みを分岐判定の済んだ後で行う例が示されているが、より速いタイミングで分岐予測を行うために、命令デコードにより分岐命令が検出された直後や命令フェッチ時に、ＢＴＢ２３への新規登録あるいはＢＴＢ２３の更新を行う場合がある。
【００８１】
このような場合であっても、新規登録時には命令がデコードされているので、事象待ち分岐命令のように、分岐予測を行わない方が有効であると考えられる分岐命令を検出することができる。したがって、ＢＴＢ２３への新規登録を抑止することで、ＢＴＢ２３による分岐予測が抑止される。
【００８２】
このような分岐予測抑止回路に加えて、図２では、事象待ちのための専用の条件コード（フラグビット）ＣＣ２を保持するレジスタ１１５がＥステージに追加されている。レジスタ１１５を設けることで、外部ＩＯの状態等（１つまたは複数）を表す信号ＥＶＥＮＴを、ＩＯ命令等を使わなくても、直接、保持することができる。これにより、従来のようなＩＯ読み出し操作や比較操作を行うための命令の実行が不要となり、それに要する時間が削除される。したがって、高速な条件待ち判断が可能となり、待ち解除の性能が向上する。
【００８３】
ＣＣ２を用いて分岐判定を行う場合には、ＣＣ２を条件として参照する新たな条件分岐命令コードが定義される。そして、デコーダ１１０は、その命令コードをデコードしたとき、ＣＣ２を参照する条件分岐命令を検出したことを示す信号Ｄ ＢＲＣ（１）を生成する。この信号Ｄ ＢＲＣ（１）は、ＣＣの代わりにＣＣ２を条件として選択するための制御信号として用いられる。
【００８４】
また、デコーダ１１０は、図１８のデコーダ４０と同様に、従来のＣＣを用いて分岐判定を行うための回路も備えている。そのために、ＣＣを参照する条件分岐命令を検出したことを示す信号Ｄ ＢＲＣ（０）も生成する。この信号Ｄ ＢＲＣ（０）は、ＣＣを条件として選択するための制御信号として用いられる。これらの２つの制御信号は、２ビットの信号Ｄ ＢＲＣ（０：１）として扱われ、パイプラインタグとして管理されて、後続ステージに伝播される。
【００８５】
ＣＣ２を参照する条件分岐命令が追加されたため、図２では、図示されないＯＲ回路によって２つの信号Ｅ ＢＲＣ（０）およびＥ ＢＲＣ（１）の論理和が生成される。そして、そのＯＲ回路の出力が、ＣＣのみを参照する図１８の回路で分岐命令を表す信号として使用されていた信号Ｅ ＢＲＣ等に対応する信号として使用される。
【００８６】
図９は、図２の分岐判定回路５０′の構成例を示している。分岐判定回路５０′は、図１８の分岐判定回路５０の機能に加えて、ＣＣ２を参照する機能を有する。図９の回路は、選択回路１２１、１２２、インバータ１２３、およびゲート回路（ＡＮＤ回路、ＯＲ回路、ＥＸＯＲ回路）１２４〜１３７を備え、信号ＴＡＫＥＮ、ＭＩＳＳ、およびＮＷ ＰＲＤ（０：１）を生成する。このうち、信号ＭＩＳＳは、図６に示した判定論理に従って生成され、分岐予測ミスが発生したときアサートされる。
【００８７】
信号ＴＡＫＥＮは、Ｄステージから転送されてきた信号Ｅ ＣＮＤ、Ｅ ＢＲＣ（０：１）を制御信号として、条件コードＣＣまたはＣＣ２のフラグビットを選択することにより、生成される。選択回路１２１、１２２は、複数ビットの信号Ｅ ＣＮＤにより制御され、それぞれ、ＣＣ２、ＣＣのフラグビットを選択する。
【００８８】
また、２ビットの信号Ｅ ＢＲＣ（０：１）は“００”、“１０”、および“０１”の３通りの値をとり、ビット０はＡＮＤ回路１２５に入力され、ビット１はＡＮＤ回路１２４に入力される。ＯＲ回路１２６は、ＡＮＤ回路１２４の出力とＡＮＤ回路１２５の出力の論理和を、信号ＴＡＫＥＮとして出力する。
【００８９】
したがって、信号Ｅ ＢＲＣ（０：１）が“１０”のとき、ＣＣのフラグビットが信号ＴＡＫＥＮとして出力され、信号Ｅ ＢＲＣ（０：１）が“０１”のとき、ＣＣ２のフラグビットが信号ＴＡＫＥＮとして出力される。前者の信号“１０”は、デコーダ１１０により、ＣＣを参照する通常の条件分岐命令が検出されたときに生成され、後者の信号“０１”は、ＣＣ２を参照する新たな条件分岐命令が検出されたときに生成される。
【００９０】
図１０は、図２０に示した並列計算機において、条件コードＣＣ２の書き込みを行う例を示している。図１０において、ＣＣ２を保持するレジスタ１１５は、ＢＲＵ８１内に設けられ、同期回路７５、ＡＣＵ８２、およびＶＩＣＵ８３と直接接続されている。ＢＲＵ８１は、例えば、図２のＢＴＢ２３および分岐判定回路５０′等を含む回路に対応する。
【００９１】
ＣＣ２は、事象待ち信号として用いられる４つのフラグＣＣ２．ＰＳＹＮＣ、ＣＣ２．ＶＳＴＰ、ＣＣ２．ＳＴＰ、およびＣＣ２．ＩＯＰを有し、各フラグの値は、対応する待ち事象の発生元からの信号により更新される。
【００９２】
ＣＣ２．ＰＳＹＮＣは、ＰＥ間の同期待ち状態を表し、ＣＣ２．ＶＳＴＰは、ベクトルユニット７４による主記憶書き込み中の状態を表し、ＣＣ２．ＳＴＰは、ＣＰＵ７１による主記憶書き込み中の状態を表し、ＣＣ２．ＩＯＰは、ＩＯ７３の動作完了待ち状態を表す。
【００９３】
同期回路７５は、信号線８４の信号をモニターし、あらかじめ決められた条件が成立すると、ＰＥ間の同期待ちを解除してもよいと判定する。そして、レジスタ１１５に直接接続された信号線１５１の信号ＰＳＹＮＣを介して、フラグＣＣ２．ＰＳＹＮＣをネゲートする。
【００９４】
あらかじ決められた条件は、複数ＰＥ上で動作しているプログラムによって異なる。例えば、各ＰＥがデータの一部を計算し、計算が収束したら、すべてのＰＥのデータを集めた後で、再度、各ＰＥにデータを分散し、さらに次のステップの計算を行うようなプログラムが考えられる。この場合、各ＰＥで受け持った部分データの収束を報告するために、ＰＥ間同期が使用され、与えられたジョブを行うすべてのＰＥの部分作業の完了のＡＮＤ条件が、全体の同期待ち解除の条件となる。
【００９５】
また、データベース検索において、検索条件に一致するデータを１つだけ検索する場合は、計算機は、各ＰＥに大きなデータベースの一部を検索させ、データベース全体を並列に検索する。一致するデータを検出したＰＥは、部分作業の完了を他のＰＥに報告する。この場合、すべてのＰＥの部分作業の完了のＯＲ条件が、全体の同期待ち解除の条件となる。
【００９６】
また、ベクトルユニット（ＶＵ）７４の計算結果をＣＰＵ（ＳＵ）７１が受け取る場合、計算結果はメモリ７２に書き込まれる。ＳＵ７１は、この書き込みの完了を待って、メモリ読み出し命令の実行を開始しなければならない。そこで、ＶＵ７４によるメモリ書き込み中を表示する信号ＶＳＴＰ（Ｖｅｃｔｏｒ  Ｓｔｏｒｅ  Ｐｅｎｄｉｎｇ）が、信号線１５２を介してＶＵ７４からＶＩＣＵ８３に接続され、さらに信号線１５３を介してレジスタ１１５に接続されている。
【００９７】
ここで、ＶＩＣＵ８３を経由しているのは、ＶＵ７４にまさに発信中のベクトルコマンドの情報を信号ＶＳＴＰに反映させるためである。例えば、発信中のベクトルコマンドがＶＵ７４からのメモリ書き込みである場合には、信号ＶＳＴＰがメモリ書き込み中でないことを示していても、ＶＩＣＵ８３は、ＣＣ２．ＶＳＴＰがメモリ書き込み中を示すように、信号ＶＳＴＰを補正することができる。
【００９８】
これとは逆に、ＳＵ７１の計算結果をメモリ７２経由でＶＵ７４が受け取る場合も、計算結果はメモリ７２に書き込まれる。ＶＵ７４は、この書き込みの完了を待って、メモリ読み出し命令の実行を開始しなければならない。そこで、ＳＵ７１によるメモリ書き込み中を表示する信号ＳＴＰ（Ｓｔｏｒｅ  Ｐｅｎｄｉｎｇ）が、信号線１５４を介してＡＣＵ８２からレジスタ１１５に接続されている。
【００９９】
この場合、メモリ７２からＡＣＵ８２への信号線は存在しない。なぜなら、メモリ書き込みがＡＣＵ８２からメモリ７２に発信されたとき、一定時間内に書き込みが完了するようになっているためである。したがって、一定時間が経過すると、自動的に信号ＳＴＰがネゲートされる。
【０１００】
また、ＩＯ７３の動作中を表示する信号ＩＯＰ（ＩＯ  Ｐｅｎｄｉｎｇ）は、信号線１５５を介してＩＯ７３からＡＣＵ８２に接続され、さらに信号線１５６を介してレジスタ１１５に接続されている。
【０１０１】
このように、事象待ちのための条件コードＣＣ２を保持するレジスタ１１５をＣＰＵ７１内に設け、待ち事象の発生元と専用の信号線により接続することで、待ち事象の発生を直ちにＣＰＵ７１に伝えることができる。したがって、待ち事象が成立したとき、事象待ちのループ処理から迅速に脱出することが可能になる。
【０１０２】
ここで、本実施形態において導入された新たな命令コードを分類すると、少なくとも次の２通りの命令に分類される。
（１）事象待ちの分岐命令であって、ＣＣを条件として参照する条件分岐命令
（２）事象待ちの分岐命令であって、ＣＣ２を条件として参照する条件分岐命令
これらの命令コードは、待ち事象の種類や参照されるフラグビット等に応じて、さらに詳細に分類される。
【０１０３】
以上説明した実施形態では、分岐命令のパイプラインを他の命令のパイプラインと同様のステージからなるパイプラインとして説明したが、分岐命令専用のパイプラインが実装されている場合であっても、同様にして本発明を適用することができる。
【０１０４】
次に、図１１から図１５までを参照しながら、本発明によりループからの脱出時間がどの程度改善されるかについて考察してみる。
図１１は、次のようなループ処理において、分岐予測テーブルによる分岐予測を行った場合の処理シーケンスを示している。
ｌａｂｅｌ：ｂｒｃ  ｂｕｓｙ，ｌａｂｅｌ
図１１において、Ｐステージ、Ｔステージ、Ｃステージ、およびＲステージは、図１９の命令メモリアクセスパイプラインに対応し、Ｄステージ、Ａステージ、Ｅステージ、およびＷステージは、命令実行パイプラインに対応する。このうち、Ｔステージの“ＢＴＢ”は、ＢＴＢを用いた分岐予測が行われたことを表し、Ｅステージの“ＴＫＮ”は、分岐が実行されたことを表し、“Ｎ−ＴＫＮ”は、分岐が実行されなかったことを表している。
【０１０５】
まず、１番目（１ｓｔ）のループ実行命令のＥステージにおいて分岐が実行され、ＷステージにおいてＢＴＢが更新される。この更新結果は、すぐ直後には効かないが、何回もループを繰り返しているうちに、ＢＴＢによる予測に反映される。あるいは、前回にこの命令が実行された結果、ＢＴＢによる予測に反映される。
【０１０６】
その結果、ｉ番目（ｉ−ｔｈ）のループ実行命令のＴステージにおいて、ＢＴＢの検索がヒットし、Ｅステージにおいて分岐が実行される。このようにしてループが繰り返されている間は、分岐予測に伴う待ち時間（ペナルティ）は、罫線“＝”が示すように、１クロック（１τ）である。
【０１０７】
その後、待ち事象が成立したため、ｊ番目（ｊ−ｔｈ）のループ実行命令のＥステージにおいて分岐が実行されなかったとすると、改めて非分岐側の命令フェッチが開始される。この場合のループの脱出に伴う待ち時間は、記号“＃”が示すように、６クロック（６τ）となる。
【０１０８】
これに対して、分岐予測テーブルによる分岐予測を行わない場合の処理シーケンスは、図１２のようになる。この場合、常に、非分岐側の後続命令があらかじめフェッチされる。
【０１０９】
まず、１番目のループ実行命令のＥステージにおいて分岐が実行されると、あらかじめフェッチされた後続命令のループ実行命令はキャンセルされ、改めて分岐先の命令がフェッチされる。したがって、ループ中の待ち時間は、記号“＃”が示すように、６τである。
【０１１０】
その後、待ち事象が成立したため、ｊ番目（ｊ−ｔｈ）のループ実行命令のＥステージにおいて分岐が実行されなかったとすると、あらかじめフェッチされた後続命令はそのまま実行される。したがって、ループの脱出に伴う待ち時間は０τとなる。
【０１１１】
このように、分岐予測を抑止するような制御を行うことにより、この例ではループ脱出時間を６τだけ短縮することができる。さらに、前述したサンプリング時間の平均誤差を加味したとしても、（６＋０．５）−（０＋３）＝３．５（τ）の改善が平均的に行われる。
【０１１２】
次に、事象待ちのための専用の条件コードＣＣ２を用いることにより、ループ脱出時間がさらに改善されることを示す。
図１３は、通常の条件コードＣＣを用いてＩＯの動作完了を待ち合わせるループ処理のフローチャートである。ＣＰＵは、まず、ＩＯステータス読み出し命令（外部参照）を実行し（ステップＳ１）、Ｂｉｔ  ＡＮＤ命令（論理演算）を実行して、ＣＣのゼロフラグＣＣ．Ｚを更新する（ステップＳ２）。次に、フラグＣＣ．Ｚの値をチェックし（ステップＳ３）、ＣＣ．Ｚ＝０であれば、ステップＳ１の処理に分岐する。そして、ＩＯが動作を完了し、ＣＣ．Ｚ＝１になると、ループを脱出して、後続命令の処理に移る。
【０１１３】
この場合、ステップＳ１、Ｓ２、Ｓ３の実行時間は、それぞれ、１０〜１００クロック、１クロック、２〜７クロックであり、合計実行時間は、１３〜１０８クロックとなる。このうち、大部分は、ＩＯステータス読み出し命令の実行時間であることが分かる。
【０１１４】
これに対して、専用の条件コードＣＣ２を用い、分岐予測テーブルによる分岐予測を行って、ＩＯの動作完了を待ち合わせる場合のフローチャートは、図１４のようになる。ＣＰＵは、ＣＣ２のＩＯフラグＣＣ２．ＩＯＰの値をチェックし（ステップＳ１１）、ＣＣ２．ＩＯＰ＝１であれば、ステップＳ１１の処理を繰り返す。そして、ＩＯが動作を完了し、ＣＣ２．ＩＯＰ＝０になると、ループを脱出して、後続命令の処理に移る。
【０１１５】
この場合、図１１に示したように、ループを繰り返すときの実行時間は２（＝１＋１）クロックであり、ループを脱出するときの実行時間は７（＝１＋６）クロックである。したがって、図１３の場合に比べて、はるかに短い時間でループ処理が実行される。
【０１１６】
また、ここでは、２クロックに１回フラグをサンプリングできるので、サンプリング誤差は平均的には（０＋１）／２＝０．５（τ）となる。したがって、ループ脱出時の待ち時間は、平均的に０．５＋６＝６．５（τ）となる。
【０１１７】
次に、専用の条件コードＣＣ２を用い、分岐予測テーブルによる分岐予測を行わずに、ＩＯの動作完了を待ち合わせる場合のフローチャートは、図１５のようになる。ＣＰＵは、フラグＣＣ２．ＩＯＰの値をチェックし（ステップＳ２１）、ＣＣ２．ＩＯＰ＝１であれば、ステップＳ２１の処理を繰り返す。そして、ＩＯが動作を完了し、ＣＣ２．ＩＯＰ＝０になると、ループを脱出して、後続命令の処理に移る。
【０１１８】
この場合、図１２に示したように、ループを繰り返すときの実行時間は７（＝１＋６）クロックであり、ループを脱出するときの実行時間は１（＝１＋０）クロックである。したがって、図１３の場合に比べて、はるかに短い時間でループ処理が実行される。
【０１１９】
また、ここでは、７クロックに１回フラグをサンプリングできるので、サンプリング誤差は平均的には（０＋１＋２＋３＋４＋５＋６）／７＝３（τ）となる。したがって、ループ脱出時の待ち時間は、平均的に３＋０＝３（τ）となり、図１４の場合より改善されていることが分かる。
【０１２０】
また、分岐予測を抑止することにより、分岐予測テーブルの資源を無駄に消費しないで済む。このため、分岐予測テーブルのエントリ数を増加させることと同様の効果が得られ、計算機の性能向上に寄与する。
【０１２１】
【発明の効果】
本発明によれば、分岐予測を伴うパイプライン処理を行う情報処理装置において、事象待ち分岐ループの振る舞いの予測が改善され、ループ脱出時の待ち時間が短縮される。
【図面の簡単な説明】
【図１】本発明の情報処理装置の原理図である。
【図２】本発明の命令実行パイプラインを示す図である。
【図３】分岐予測テーブルを示す図である。
【図４】予測ビットの定義を示す図である。
【図５】予測ビットの状態遷移を示す図である。
【図６】分岐予測の成否を示す図である。
【図７】他の命令フェッチ制御部の構成図である。
【図８】他の命令実行パイプラインを示す図である。
【図９】分岐判定回路の構成図である。
【図１０】条件コードの書き込みを示す図である。
【図１１】第１のループ処理シーケンスを示す図である。
【図１２】第２のループ処理シーケンスを示す図である。
【図１３】第１のループ処理のフローチャートである。
【図１４】第２のループ処理のフローチャートである。
【図１５】第３のループ処理のフローチャートである。
【図１６】計算機の構成図である。
【図１７】命令フェッチ制御部の構成図である。
【図１８】従来の命令実行パイプラインを示す図である。
【図１９】命令メモリアクセスパイプラインを示す図である。
【図２０】事象待ちの例を示す図である。
【符号の説明】
１１  命令フェッチ制御部
１２  命令メモリアクセスパイプライン
１３  命令バッファ
１４  命令実行パイプライン
２１、２２  インクリメンタ
２３  分岐予測テーブル
２４  比較回路
２５、１１１、１１２、１２４、１２５、１２６、１２７、１２８、１２９、１３０、１３１、１３２、１３３、１３４、１３５、１３６、１３７  ゲート回路
２６、２７、６４、６６、１１９、１２１、１２２  選択回路
２８  プリフェッチプログラムカウンタ
３１、３３、３４、３５、３６、３８、３９、４１、４２、４３、４４、４５、４６、４７、４８、４９、５１、５３、５４、５５、５６、５７、５８、５９、６０、６１、６３、６５、６７、６８、１１３、１１４、１１５、１１７、１１８  レジスタ
３２  汎用レジスタ
３７  演算器
４０、１１０  デコーダ
５０、５０′  分岐判定回路
５２、１１６  加算器
６２  命令キャッシュ
７１  ＣＰＵ
７２  メモリ
７３  ＩＯ
７４  ベクトルユニット
７５  同期回路
７６、７７、７８、７９、８４、１５１、１５２、１５３、１５４、１５５、１５６  信号線
８１  ＢＲＵ
８２  ＡＣＵ
８３  ＶＩＣＵ
１０１  検出手段
１０２  抑止手段
１２３  インバータ
【図１】
0003683439.tif 000003
【図２】
0003683439.tif 000004
【図３】
0003683439.tif 000005
【図４】
0003683439.tif 000006
【図５】
0003683439.tif 000007
【図６】
0003683439.tif 000008
【図７】
0003683439.tif 000009
【図８】
0003683439.tif 000010
【図９】
0003683439.tif 000011
【図１０】
0003683439.tif 000012
【図１１】
0003683439.tif 000013
【図１２】
0003683439.tif 000014
【図１３】
0003683439.tif 000015
【図１４】
0003683439.tif 000016
【図１５】
0003683439.tif 000017
【図１６】
0003683439.tif 000018
【図１７】
0003683439.tif 000019
【図１８】
0003683439.tif 000020
【図１９】
0003683439.tif 000021
【図２０】
0003683439.tif 000022