JPH06124206A - 分岐命令予測処理装置及びその処理方法 - Google Patents

Abstract

(57)【要約】 【目的】 電源投入直後やリセット時にも分岐予測を行
なえるようにする。 【構成】 電源投入直後やリセット時は分岐予測テーブ
ル１０の内容はすべて“０”であるが、プログラムの実
行前に分岐予測テーブル変更命令実行部１１により分岐
予測テーブル１０の各エントリに所定のデータをセット
することができる。これにより、プログラムの実行開始
直後から分岐予測テーブル１０内のデータを使って分岐
予測を行なう。新たなジョブを実行する前も分岐予測テ
ーブル変更命令実行部１１により分岐予測テーブル１０
の各エントリにそのジョブに適合したデータをセットす
ることができる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、分岐命令の分岐方向と
分岐先を、分岐命令の実行結果が判明する前に予測する
ことによっていち早く分岐命令に続く命令をフェッチす
る分岐命令予測処理装置及びその処理方法に関するもの
である。

【０００２】

【従来の技術】従来、分岐命令予測は以下に示すような
方法で行なわれていた。まず、第１の方式としては、予
め分岐方向を一意に決めて予測するものがある。これは
過去の命令実行結果にかかわらず、常に一方向に予測す
るものであり、分岐すると予測する方式（taken 予
測）、分岐しないものと予測する方式（not-taken 予
測）がある。しかしながら、これらの方式では、分岐方
向が固定されているので、予測の的中率が低くかった。
また、分岐方向の予測に留まっており、分岐先の命令を
先行的にフェッチすることができなかった。そこで、分
岐方向の予測を実行時に動的に行ない、更に分岐命令の
実行が終了して分岐方向と分岐先アドレスが決定する前
に分岐先命令を先行的にフェッチすることができる方式
として分岐予測テーブルを用いる方式が提案された。

【０００３】図２は、分岐予測テーブルの説明図であ
る。図示の分岐予測テーブルは、分岐命令アドレス、分
岐先アドレス、分岐方向予測、Ｖａｌｉｄの４つのフィ
ールドから構成されている。分岐方向予測については、
Johnny K.F.Lee,Alan Jay Smith 「Branch Prediction S
trategies and Branch target Buffer Design」 IEEE CO
MPUPER January 1984 に詳述されている。この分岐方向
予測のための情報は、通常２ビットで構成されている。
そして、例えば２回予測が外れたときに分岐方向予測を
変更するといったアルゴリズムで更新される。また、Ｖ
ａｌｉｄビットは、通常“１”の時に当該エントリが有
効であることを示し、“０”の時に無効であることを示
す。このような分岐予測テーブルを用いることによっ
て、分岐命令を実行して分岐条件の判断と分岐先アドレ
スの計算を行なうよりも早く、分岐命令をフェッチした
ときに分岐先を予測することが可能となる。これによ
り、分岐命令実行結果が得られるまでの無駄な待ち時間
がなくなる。もし、この予測が成功しなかった場合に
は、分岐先と予測して先行的に実行した結果を破棄す
る。

【０００４】このような分岐予測テーブルは、分岐命令
を処理する度に更新される。つまり、ある分岐命令を実
行したときに分岐命令アドレスフィールドに該当するア
ドレスを持つものがあり、そのエントリのＶａｌｉｄフ
ィールドが“１”であれば、そのエントリの分岐方向予
測フィールドに分岐命令によって分岐が行なわれたか否
かによって、あるアルゴリズムによって求められる値を
書き込む。例えば、この分岐命令は過去において常に分
岐が行なわれていたとすると、分岐方向予測フィールド
は“１１”であり、新たにこの分岐命令を実行した結
果、分岐が行なわれなければ、このフィールドは“１
０”に変化する。

【０００５】更に、当該エントリの分岐先アドレスフィ
ールドには分岐命令によって分岐が行なわれたときの分
岐先アドレスを書き込む。もし、分岐命令アドレスフィ
ールドに該当するアドレスが存在せず、すべてのエント
リのＶａｌｉｄフィールドが“１”であれば、最も古く
アクセスされた分岐命令アドレスを持つエントリを削除
して、新しい分岐命令アドレスに関する情報を書き込
む。もし、分岐命令アドレスに、該当するアドレスが存
在せず、Ｖａｌｉｄフィールドが“０”であるエントリ
があれば、それらのエントリの内から１つを選び出して
用いる。ここで、分岐予測テーブルにおいてＶａｌｉｄ
フィールドの値が“１”であるものの分岐命令アドレス
の中にフェッチされた分岐命令のアドレスに該当するア
ドレスが存在しないときに、分岐命令を実行した結果、
分岐を行なわなければならなくなったときの動作につい
て考える。

【０００６】図３は、命令列と命令実行タイミングの例
の説明図である。図示の例において、図３（ａ）の命令
は、条件レジスタの内容が“０”の時分岐を行ない、分
岐先のアドレスがレジスタＲ１０に保持されていること
を示す。図３（ｂ）の命令は図３（ａ）の命令の直後の
アドレスの命令であり、レジスタＲ１１とＲ１２の内容
の和を求めてＲ１３に書き込むことを示す。図３（ｃ）
の命令はＲ１０の内容のアドレス命令であり、図３
（ｂ）と同様にレジスタＲ２１とＲ２２の内容の和を求
めてＲ２３に書き込むことを示す。図３に示すような実
行を行なう装置は、実行がｆ（命令フェッチ）、ｄ（命
令デコード、レジスタからのオペランド読み出し）、ｅ
（命令実行、分岐の条件判断、分岐先アドレス計算）、
ｗ（結果の書き込み）の４つのステージで表わされるパ
イプライン処理を行なう。

【０００７】図３（ａ）の命令をフェッチ中に分岐予測
テーブルの分岐命令アドレスの検索が行なわれるが、該
当する命令アドレスが存在しないので、次のステージで
は、先にフェッチを行なったアドレスに連続するアドレ
スの命令がフェッチされる。しかし、図３（ａ）の命令
のｅステージで分岐条件判断を行ない、分岐条件が成立
することが判明したとする。尚、この場合は条件レジス
タの内容が“０”である。そして、更に分岐先アドレス
が計算されるので、次のステージにおいて図３（ｃ）の
分岐先命令がフェッチされ、以降このアドレスの命令か
ら連続に処理される。ただし、図３（ｂ）の命令はｄス
テージまで進んだのみで実行を取り止める。この時、分
岐予測が成功した場合と比較して２ステージの遅れが生
じている。

【０００８】

【発明が解決しようとする課題】しかしながら、上述し
た従来の技術には、次のような問題があった。即ち、上
述した分岐予測テーブルのＶａｌｉｄフィールドの初期
状態はすべて“０”であり、電源投入直後及びリセット
直後に計算機がプログラムの実行を開始する場合、分岐
予測は全く行なえなかった。更に、計算機が新たなジョ
ブを開始する場合には、それ以前とは全く異なるアドレ
スの命令の実行を開始するために、分岐予測テーブルの
Ｖａｌｉｄフィールドがすべて“１”であっても、該当
する命令アドレスが分岐予測テーブルの分岐命令アドレ
スフィールドになく、分岐予測ができない状態が発生す
る。従って、計算機の処理速度が低下するという問題が
あった。本発明は、以上の点に着目してなされたもの
で、電源投入直後及びリセット直後に計算機が実行を開
始する場合にも分岐予測が行なえるようにした分岐命令
予測処理装置及びその処理方法を提供することを目的と
するものである。

【０００９】

【課題を解決するための手段】本発明の分岐命令予測処
理装置は、計算機で順に実行される分岐命令に続く命令
をフェッチする際に、当該分岐命令による分岐方向と分
岐先を、当該分岐命令の実行結果が判明する前に予測す
ることによっていち早く分岐命令に続く命令をフェッチ
する分岐命令予測処理装置において、前記分岐命令の実
行時に、当該分岐命令のアドレスと、当該分岐命令によ
って分岐が行なわれたか否かを示す情報と、当該分岐命
令の分岐先の命令のアドレスとを保持する分岐予測テー
ブルと、計算機によりプログラムを正規に実行する前
に、当該分岐予測テーブルの内容を明示的に書き換え得
る分岐予測テーブル変更命令実行部とを備えたことを特
徴とするものである。

【００１０】本発明の分岐命令予測処理方法は、プログ
ラム実行時の分岐に関して、個々の分岐命令での分岐方
向を記録するとともに、分岐命令のアドレス及び分岐先
命令のアドレスを記録する分岐予測テーブルを用意し、
計算機によりプログラムを正規に実行する前に、当該分
岐予測テーブルに前記分岐方向と、分岐命令のアドレス
及び分岐先命令のアドレスを記録するための準備的な実
行を１回以上行ない、正規のプログラム実行時の分岐予
測のための分岐方向と、分岐命令のアドレス及び分岐先
命令のアドレスを前記分岐予測テーブルに予め設定する
ことを特徴とするものである。

【００１１】

【作用】本発明の分岐命令予測処理装置及びその処理方
法においては、電源投入直後及びリセット直後、更には
新たなジョブを開始するときに、準備的なプログラムの
実行を行なう。この準備用のプログラムは正規の実行用
のプログラムでもよく、また、分岐予測テーブルの変更
のための特殊な命令を含んだプログラムでもよい。これ
により、正規にプログラムの実行をしようとするとき
は、常に既にこれから実行される分岐命令に該当する分
岐予測テーブルエントリが設定されている。従って、電
源投入直後等でも分岐命令をフェッチすると、直ちに分
岐予測が行なわれ、分岐予測先の命令がフェッチされ
る。

【００１２】

【実施例】以下、本発明の実施例を図面を参照して詳細
に説明する。図１は、本発明の分岐命令予測処理装置を
含む情報処理装置の一実施例のブロック図である。図示
の情報処理装置は、命令メモリ１、命令バッファ２、演
算処理部３、レジスタファイル４、メモリ制御部５、デ
ータメモリ６、命令フェッチ制御部７、分岐命令実行部
８及び分岐命令予測処理部９から成る。更に、分岐命令
予測処理部９は、分岐予測テーブル１０と、分岐予測テ
ーブル変更命令実行部１１から成る。命令メモリ１は、
図３又は図７に示すような命令を格納する。

【００１３】命令バッファ２は、実行する命令を一時的
に格納するメモリである。演算処理部３は、命令バッフ
ァ２から取り出した命令を実行する。レジスタファイル
４は、汎用レジスタ等から成る。メモリ制御部５は、デ
ータメモリ６とレジスタファイル４との間のデータ転送
を制御する。データメモリ６は、演算処理部３で処理す
るデータを格納する。命令フェッチ制御部７は、命令メ
モリ１から命令バッファ２への命令の転送を制御する。
分岐命令実行部８は、命令バッファ２から取り出した分
岐命令を実行し、分岐する場合には分岐先のアドレスの
命令を命令メモリ１から命令バッファ２に転送する。一
方、分岐しない場合には当該分岐命令の次のアドレスの
命令を命令メモリ１から命令バッファ２に転送する。

【００１４】分岐命令予測処理部９は、分岐命令実行部
８で分岐命令が実行される前にその分岐命令のアドレス
から分岐方向を予測し、命令フェッチ部７に予め次の命
令をフェッチさせる。分岐予測テーブル１０は、分岐命
令アドレスに対応して分岐先アドレス、分岐方向予測、
Ｖａｌｉｄを格納している。分岐予測テーブル変更命令
実行部１１は、演算処理部３で実行される所定の命令に
より、分岐予測テーブル１０中の命令アドレス、分岐先
アドレス、分岐方向予測を明示的に書き換え得る。

【００１５】図４は、分岐予測テーブルを設定するプロ
グラムの例を示す図である。即ち、この図には、分岐予
測テーブルに書き込みを行なう命令列の例を示す。この
命令中ｍｏｖｉは第１引数で示される分岐予測テーブル
のフィールドに第２引数で示される値を書き込む命令で
ある。ｂｐ，ｂｐａ，ｂｐｔは各々分岐予測テーブルの
分岐予測、分岐命令アドレス、分岐予測アドレスの各フ
ィールドを示している。演算処理部３で分岐予測テーブ
ル変更命令であることが認識されると、これを分岐命令
予測処理部９の分岐予測テーブル変更命令実行部１１に
通知する。分岐予測テーブル変更命令実行部１１では、
Ｖａｌｉｄフィールドが“０”であるエントリを１つ選
んでそのエントリの各フィールドの内容を書き換える。
この場合、Ｖａｌｉｄフィールドが“０”であるエント
リがなければＶａｌｉｄフィールドが“１”であって最
後に利用されたものを検索してそのエントリの各フィー
ルドの内容を書き換える。

【００１６】分岐予測テーブルが図２に示される状態で
あったときに、図４による分岐予測テーブルの設定が実
行されると、図１に示すように分岐予測テーブルが書き
換えられる。つまり、図１に示す分岐予測テーブル１０
の第３行に示されるエントリが追加される。図５は、分
岐予測テーブルエントリの決定手順を説明するフローチ
ャートである。即ち、このフローチャートは、分岐予測
テーブルに書き込むエントリを決定し、分岐予測テーブ
ルに書き込む方法の手順を示す。各エントリを決定する
に当り、まず高速化の対象となるジョブプログラムを実
行する（ステップＳ１）。更に、実行中に分岐命令を検
索し（ステップＳ２）、分岐命令があれば、その分岐命
令アドレスを記録する（ステップＳ３）。更に、当該分
岐命令の結果を収集し（ステップＳ４）、分岐命令によ
る分岐先アドレスと分岐方向を記録する（ステップＳ
５）。以上、記録された各項目について、実行開始から
分岐予測テーブルエントリ数と同数の分岐命令アドレス
について、各２回の分岐命令実行の記録を取り出す（ス
テップＳ６、Ｓ７、Ｓ８）。

【００１７】図６は、分岐方向予測フィールドの決定方
法の説明図である。図示のように、１回目に分岐してい
れば分岐方向予測フィールドの上位ビットの値は“１”
になる。また、２回目に分岐していれば分岐方向予測フ
ィールドの下位ビットの値は“１”になる。図７は、分
岐命令を含む命令列と本発明による実行タイミングの例
を示す図である。即ち、この図は、上記のように分岐予
測テーブルを書き換えた後に、図３に示した命令と同じ
命令を実行したときのタイミングを示している。以下、
図１を参照しつつ、図７に示す実行タイミングについて
説明する。

【００１８】始めに、分岐命令をフェッチするステージ
ｆで、分岐予測テーブル１０は命令フェッチ制御部７か
らアドレスを取り出し、分岐予測テーブル１０内の各エ
ントリの分岐命令アドレスと比較する。この時、分岐予
測テーブル１０の分岐命令アドレスには、前述のとおり
プログラムによって書き込んだエントリが存在し、これ
が現在フェッチ中の命令アドレスと一致する。従って、
当該エントリのＶａｌｉｄフィールドが“１”であるこ
とを確認した上で、分岐方向予測を読み出す。分岐方向
予測はこの時“１１”であるので、分岐が行なわれると
予測される。従って、当該エントリの分岐先アドレスを
分岐方向予測と共に分岐命令実行部８に通知する。分岐
命令実行部８では、このアドレスを命令フェッチ制御部
７に通知する。次のステージでは、命令アドレスを分岐
予測先のアドレスに変更して命令フェッチを行なう。更
に次のステージでは、分岐命令の条件判断が行なわれ、
前述の分岐予測が正しければ図７に示すようにそのまま
実行が続けられる。

【００１９】

【発明の効果】以上説明したように、本発明の分岐命令
予測処理装置及びその処理方法によれば、電源投入直後
及びリセット直後、更には新たなジョブを開始するとき
に、既にこれから実行される分岐命令に該当する分岐予
測テーブルが設定されるようにしたので、分岐命令をフ
ェッチすると、直ちに分岐予測を行なうことができ、分
岐予測先の命令をフェッチすることができる。従って、
分岐予測テーブルの内容がすべて無効である場合や、プ
ロセッサが新たなジョブを開始し、それに続く命令のア
ドレスが全く分岐予測テーブルに登録されていない場合
でも、すぐに高速な処理を開始することが可能になる。

【図面の簡単な説明】

【図１】本発明の分岐命令予測処理装置を含む情報処理
装置の一実施例のブロック図である。

【図２】分岐予測テーブルの構成の説明図である。

【図３】分岐命令を含む命令列と従来の実行タイミング
の例の説明図である。

【図４】分岐予測テーブルを設定するプログラムの例の
説明図である。

【図５】分岐予測テーブルエントリの決定手順を説明す
るフローチャートである。

【図６】分岐方向予測フィールドの決定方法の説明図で
ある。

【図７】分岐命令を含む命令列と本発明による実行タイ
ミングの例の説明図である。

【符号の説明】

１ 命令メモリ ２ 命令バッファ ３ 演算処理部 ４ レジスタファイル ５ メモリ制御部 ６ データメモリ ７ 命令フェッチ制御部 ８ 分岐命令実行部 ９ 分岐命令予測処理部 １０ 分岐予測テーブル １１ 分岐予測テーブル変更命令実行部

Claims (2)

【特許請求の範囲】
1. 【請求項１】 計算機で順に実行される分岐命令に続く
   命令をフェッチする際に、当該分岐命令による分岐方向
   と分岐先を、当該分岐命令の実行結果が判明する前に予
   測することによっていち早く分岐命令に続く命令をフェ
   ッチする分岐命令予測処理装置において、 前記分岐命令の実行時に、当該分岐命令のアドレスと、
   当該分岐命令によって分岐が行なわれたか否かを示す情
   報と、当該分岐命令の分岐先の命令のアドレスとを保持
   する分岐予測テーブルと、 計算機によりプログラムを正規に実行する前に、当該分
   岐予測テーブルの内容を明示的に書き換え得る分岐予測
   テーブル変更命令実行部とを備えたことを特徴とする分
   岐命令予測処理装置。
2. 【請求項２】 プログラム実行時の分岐に関して、個々
   の分岐命令での分岐方向を記録するとともに、分岐命令
   のアドレス及び分岐先命令のアドレスを記録する分岐予
   測テーブルを用意し、 計算機によりプログラムを正規に実行する前に、当該分
   岐予測テーブルに前記分岐方向と、分岐命令のアドレス
   及び分岐先命令のアドレスを記録するための準備的な実
   行を１回以上行ない、 正規のプログラム実行時の分岐予測のための分岐方向
   と、分岐命令のアドレス及び分岐先命令のアドレスを前
   記分岐予測テーブルに予め設定することを特徴とする分
   岐命令予測処理方法。