JPWO2005103886A1 - 分岐予測装置、その方法、及びプロセサ - Google Patents

Abstract

分岐命令の出現頻度を検出し、分岐命令が分岐すると予測する確度を示す予測情報を格納した分岐ヒストリテーブルのインデックスの計算に用いる分岐ヒストリレジスタのなかで有効とするビット幅を、検出した出現頻度を基に動的に変更する。

Description

本発明は、最近の分岐命令の分岐結果を複数、格納する分岐ヒストリレジスタ、及びインデックス毎に分岐命令が分岐すると予測する確度を示す予測情報を格納した分岐ヒストリテーブルを用いて分岐予測を行う技術に関する。

パイプライン機能を有するプロセサでは、性能を最大限に発揮させるために、分岐命令が分岐するか否かを分岐予測装置により予測して先に処理を進めるようになっている。その予測がはずれた場合、後戻りさせなくてはならない。これは、先に進めた分の処理は無駄になり、後戻りさせるための処理を別に行わなければならないことを意味する。そのようなペナルティが発生することから、予測精度はプロセサの性能に大きく影響する。このため、分岐予測装置では、より高い精度で予測を行えるようにすることが強く望まれている。

従来の分岐予測装置としては、例えば特許文献１に記載された２レベル型分岐予測装置がある。その型の分岐予測装置は、比較的に高い予測精度が得られると注目されている。
図１Ａは、２レベル型の従来の分岐予測装置で行われる分岐予測を説明する図である。

分岐ヒストリレジスタ７０２は、最近の分岐命令における分岐結果を複数、履歴として格納するレジスタである。１分岐命令の分岐結果は１ビットの値で表現される。例えば分岐不成立は「０」、分岐成立は「１」で表現される。その分岐結果は、１ビットずつシフトしながらレジスタ７０２に格納する。それにより、レジスタ７０２には、最近のそのビット数分の分岐結果が格納されるようになっている。例えばビット数が４ビットであり、現在の内容が「１００１」である状態で分岐成立の分岐命令を実行した場合には、その内容は「００１１」に更新される。

排他的論理和（ＸＯＲ）演算回路７０３は、分岐ヒストリテーブル７０４に格納された内容と分岐命令アドレス値７０１との排他的論理和を算出する。その排他的論理和は、分岐ヒストリテーブル７０４のインデックスとして使われる。

分岐ヒストリテーブル７０４には、インデックス毎に、分岐命令による分岐が成立する確度を示す予測情報である状態が格納されている。その状態（予測情報）は２ビットで表現され、その２ビットで表現される値は大きくなるほど、分岐が成立する確度が高いことを示している。それにより、その値が「１１」或いは「１０」のときは分岐命令による分岐が成立すると予測し、その値が「０１」或いは「００」のときは分岐が成立しないと予測する。

図１Ｂは、分岐ヒストリテーブル７０４に格納した状態の更新方法を説明する図である。
その状態としての値は、実際の分岐結果に応じて更新するようになっている。その更新は、図１Ｂに示すように、分岐が成立した場合には「１１」を上限に値をインクリメントし、分岐が成立しなかった場合には「００」を下限に値をデクリメントすることで行っている。そのような更新を行うことにより、実行するプログラムに応じて分岐ヒストリテーブル７０４を最適化し、予測精度を常に高く維持させるようにしている。

ところで、プロセサの性能はベンチマークテストを行って計測するのが普通である。そのテスト用のソフトウェアとしては、ＳＰＥＣ（Standard Performance Evaluation Corporation）ベンチマークやＴＰＣ（Transaction Processing Performance Council）−Ｃベンチマークなどが知られている。

ＳＰＥＣベンチマークには、プロセサの性能を表す指標として、整数演算の性能評価用のＳＰＥＣｉｎｔや、浮動小数点数演算の性能評価用のＳＰＥＣｆｐなどがある。一方のＴＰＣ−Ｃベンチマークは、トランザクション処理システムをシミュレートしてプロセサの性能を評価するものである。

図２は、分岐ヒストリレジスタ７０２のビット幅と分岐予測のミス率の関係をベンチマーク別に説明する図である。そのミス率は平均値である。
その図２に示すように、２レベル型の分岐予測装置では、分岐ヒストリレジスタ７０２のビット幅（数）が大きいほどＳＰＥＣベンチマークでのミス率は低下し、ＴＰＣ−Ｃベンチマークでのミス率は高くなる。それにより、その分岐予測装置を搭載したプロセサでは、分岐ヒストリレジスタ７０２のビット幅（数）が大きいほどＳＰＥＣベンチマークでの性能が向上し、ＴＰＣ−Ｃベンチマークでの性能が低下するという両立困難な問題点があった。

それぞれのベンチマークの特徴として、ＳＰＥＣベンチマークには、最近の分岐命令の分岐／非分岐の履歴に強く依存した命令列が存在するが、分岐命令数自体は比較的に多くないという特徴がある。他方のＴＰＣ−Ｃベンチマークには、最近の分岐命令の分岐／非分岐の履歴には殆ど依存しないが、分岐命令数自体は比較的に非常に多いという特徴がある。このことから、そのような特徴に応じて分岐ヒストリレジスタ７０２のビット幅を変更することが考えられる。

分岐ヒストリテーブル７０４のインデックスは、上述したように、分岐ヒストリレジスタ７０２の値と分岐命令アドレス値７０１のＸＯＲとしている（Ｇ−ｓｈａｒｅ）。このため、分岐ヒストリレジスタ７０２のビット幅が大きいほど、同じアドレス値７０１の分岐命令の予測情報が分岐ヒストリテーブル７０４内を占める領域が大きくなり、他の分岐命令と共有せずに格納できる分岐命令の数が減少する。それにより、分岐ヒストリレジスタ７０２のビット幅を大きくすると、分岐命令数が比較的に少ないＳＰＥＣベンチマークでは、共有せずに予測情報を格納できる分岐命令数が少なくとも最近の分岐命令の履歴パターン（分岐／非分岐の組み合わせ）毎に予測情報を独立に格納できるようになって予測精度が向上すると考えられる。他方のＴＰＣ−Ｃベンチマークでは、分岐命令数が比較的に多いため、予測情報を独立に格納できる分岐命令数が減少して予測精度が低下すると考えられる。

特許文献２には、複数の方法で分岐予測を行えるようにして、そのうちの一つを実際の分岐予測に用いる分岐予測装置が記載されている。特許文献３には、モジュールが各種の処理を行う際のパフォーマンスを測定して、コンフィグレーションを変更するプロセサが記載されている。

それら特許文献２、３に記載された技術は何れも、分岐予測では分岐予測ミス率に着目している。しかし、そのミス率は、分岐予測装置自体の予測精度が低いことが原因で大きくなる場合がある。このため、上述したようなプログラム（ベンチマーク）の持つ特徴（分岐命令の出現頻度）に対応するうえでは、不適切となる可能性がある。
特開２００３−５９５６号公報 特開平１０−２４０５２６号公報 特開２００２−１６３１５０号公報

本発明は、実行するプログラムに係わらず、常に高い予測精度を維持可能な分岐予測装置、及びそれを搭載したプロセサを提供することを目的とする。
本発明の分岐予測装置は、最近の分岐命令の分岐結果を複数、履歴として格納する分岐ヒストリレジスタと、該分岐ヒストリレジスタに格納された分岐結果を用いて計算されるインデックス毎に分岐命令が分岐すると予測する確度を示す予測情報を格納した分岐ヒストリテーブルと、を用いて分岐予測を行うことを前提とし、異なるアドレスの分岐命令の出現頻度を検出する頻度検出手段と、頻度検出手段が検出した出現頻度に基づいて、分岐ヒストリレジスタのなかで有効とするビット幅を動的に変更するビット幅変更手段と、を具備する。

本発明の分岐予測方法は、最近の分岐命令の分岐結果を複数、履歴として格納する分岐ヒストリレジスタと、該分岐ヒストリレジスタに格納された分岐結果を用いて計算されるインデックス毎に分岐命令が分岐すると予測する確度を示す予測情報を格納した分岐ヒストリテーブルと、を用いて分岐予測を行うことを前提としたものであり、異なるアドレスの分岐命令の出現頻度を検出し、該検出した出現頻度に基づいて、分岐ヒストリレジスタのなかで有効とするビット幅を動的に変更する。

本発明のプロセサは、最近の分岐命令の分岐結果を複数、履歴として格納する分岐ヒストリレジスタと、該分岐ヒストリレジスタに格納された分岐結果を用いて計算されるインデックス毎に分岐命令が分岐すると予測する確度を示す予測情報を格納した分岐ヒストリテーブルと、を用いて分岐予測を行うことを前提とし、異なるアドレスの分岐命令の出現頻度を検出する頻度検出手段と、頻度検出手段が検出した出現頻度に基づいて、分岐ヒストリレジスタのなかで有効とするビット幅を動的に変更するビット幅変更手段と、を具備する。

本発明では、異なるアドレスの分岐命令の出現頻度を検出し、最近の分岐命令の分岐結果を複数、履歴として格納する分岐ヒストリレジスタのなかで有効とするビット幅（数）を、検出した出現頻度を基に動的に適宜、変更する。

異なるアドレスの分岐命令の出現頻度はプログラムによって異なり、その出現頻度によって分岐ヒストリレジスタの最適なビット幅も変化する。このため、その出現頻度を基に分岐ヒストリレジスタのヒット幅を動的に適宜、変更することにより、そのビット幅を最適化することができる。その結果、実行するプログラムに係わらず、常に高い予測精度を維持することができるようになり、プロセサの性能は常に最大限に発揮できることとなる。

２レベル型の従来の分岐予測装置で行われる分岐予測を説明する図である。 分岐ヒストリテーブル７０４に格納した状態の更新方法を説明する図である 分岐ヒストリレジスタ７０２のビット幅と分岐予測のミス率の関係をベンチマーク別に説明する図である。 本実施の形態による分岐予測装置の構成を説明する図である。 本実施の形態による分岐予測装置を搭載したプロセサの構成を説明する図である。 ベンチマークと分岐予測ミス率の関係を説明する図である。 ベンチマークと分岐命令キャッシュミス率の関係を説明する図である。 本実施の形態による分岐予測装置の動作の流れを示すフローチャートである。 分岐ヒストリレジスタの有効とするビット幅の動的な変更を行った場合のベンチマークと分岐予測ミス率の関係を説明する図である。

以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。
図３は、本実施の形態による分岐予測装置の構成を説明する図であり、図４は、その分岐予測装置を搭載したプロセサの構成を説明する図である。

そのプロセサは、図４に示すように、命令フェッチ部１００、命令実行部２００、２次キャッシュ部３００、及びシステムインターフェース部４００、を備えた構成となっている。

命令フェッチ部１００は、分岐予測装置１、命令キャッシュ２、及び命令バッファ（ＩＢＦ）１０１を備えている。その命令フェッチ部１００は、命令実行部２００とは独立して動作し、分岐予測装置１による分岐予測に従って、将来実行すると予測される命令列をなぞるように命令キャッシュ２から取り出してＩＢＦ１０１に取り込む。命令キャッシュ２への命令のプリフェッチは、ハードウェア、或いはソフトウェアによって行われる。

命令実行部２００は、ＩＢＦ１０１にプリフェッチされた命令を取り出して実行するものである。ＩＷＲ（Instruction Word Register）部２０１には、例えばＩＢＦ１０１から４命令がまとめてセットされる。

そのＩＷＲ部２０１は、ＩＢＦ１０１から取り出した命令をデコードし、実行に必要な資源を決定して命令を発行する発行制御回路３（図３）を備えている。その発行制御回路３は、命令識別子（ＩＩＤ）を割り当てて命令を発行する。発行した命令は、ロード・ストア用リザベーション・ステーション（ＲＳＬＳ：Reservation Station for Lord and Store）２０２、アドレス生成用リザベーション・ステーション（ＲＳＡ：Reservation Station for Address generaion）２０３、整数演算用リザベーション・ステーション（ＲＳＥ：Reservation Station for Execution）２０４、浮動小数点演算用リザベーション・ステーション（ＲＳＦ：Reservation Station for Floating point）２０５、及び分岐用リザベーション・ステーション（ＲＳＢ：Reservation Station for Branch）４（図３）の何れかに送出される。

ＲＳＬＳ２０２は、ロード命令はフェッチキューＦＱでデータキャッシュ２０６を制御して実行する。ストア命令は、ストアデータキューＳＤＱでデータの書き込みを制御する。

演算器２０７は、アドレス生成演算器（ＡＧ）、及び整数演算器（ＥＸ）をそれぞれ２つ備えたものである。ＲＳＡ２０３は、アドレス生成演算器に命令を実行させてアドレスを生成させる。生成されたアドレスは、ＲＳＬＳ２０２のストアデータキューにエントリされる。ＲＳＥ２０４は、整数演算器に命令を実行させる。

浮動小数点演算器（ＦＬ）２０８も同様に２つ用意されている。ＲＳＦ２０５は、浮動小数点演算器２０８に命令を実行させる。
ＲＳＢ４には、分岐命令が発行される。そのＲＳＢ４は、分岐確定、分岐予測情報の更新、分岐予測失敗時の再命令フェッチなどの処理を行う。分岐確定は、命令に割り当てられた命令識別子を手がかりにして演算動作を監視することで行う。

次に、命令フェッチ部１００を構成する分岐予測装置１について、図３を参照して詳細に説明する。
分岐命令キャッシュ１３は、分岐命令アドレス別に、命令の種類を示すタグ情報や分岐先アドレスを格納するものである。それらの情報は、プログラムカウンタ１２から出力された値（アドレス）によって読み出される。命令フェッチ制御回路１１は、分岐命令キャッシュ１３から読み出された情報を入力し、次にプリフェッチする命令の種類等を認識する。分岐先アドレスの有無から、キャッシュミスが発生したか否か判定する。プログラムカウンタ１２から出力された値によって命令キャッシュ２から読み出された命令は、ＩＢＦ１０１を介してＩＷＲ部２０１の発行制御回路３に送られる。キャッシュミスの発生は、ＲＳＢ４に直接、或いは間接的に通知する。分岐予測ミスが判明した時のＲＳＢ４による再命令フェッチは、ＲＳＢ４がプログラムカウンタ１２等の内容を直接、更新するか、或いは命令フェッチ制御回路１１を制御して行わせる。

分岐ヒストリレジスタ１４は、最近の分岐命令における分岐結果を複数、履歴として格納する。命令フェッチ制御回路１１は、例えばＲＳＢ４からの分岐確定の通知により、その内容を更新する。その更新は、分岐ヒストリテーブル１５の対応する状態の更新と併せて行う。

分岐ヒストリテーブル１５は、インデックス毎に、分岐命令による分岐が成立する確度を示す予測情報である状態が格納されている。その状態（予測情報）は２ビットで表現される値である。そのインデックスは、プログラムカウンタ１２から出力されたアドレスと、分岐ヒストリレジスタ１４の値との排他的論理和（ＸＯＲ）により計算される。

分岐ヒストリレジスタ１４から読み出された値はマスク回路１６、及び排他的論理和（ＸＯＲ）演算回路１７にそれぞれ出力される。そのマスク回路１６は、分岐ヒストリレジスタ１４の総ビット幅分のうち、状況によってマスクすべきとするビット幅（以降「マスク対象ビット幅」と呼ぶ）分の論理積演算回路を備えた構成である。それら論理積演算回路は、分岐ヒストリレジスタ１４の対応するビットの値と、分岐ヒストリレジスタモードレジスタ部（以降「モードレジスタ部」と略記）２１が出力する信号の値を反転した値の論理積を出力する。それにより、排他的論理和（ＸＯＲ）演算回路１７には、分岐ヒストリレジスタ１４の総ビット幅のうち、マスク回路１６に出力されないビット幅分の値が出力される。例えば、分岐ヒストリレジスタ１４の総ビット幅は１０ビット、マスク対象ビット幅は８ビットである。

ＸＯＲ演算回路１７は、分岐ヒストリレジスタ１４、或いはマスク回路１６から入力する値と、プログラムカウンタ１２から読み出されたアドレス値との排他的論理和をビット単位でとり、その結果をインデックスとして分岐ヒストリテーブル１５に出力する。命令フェッチ制御回路１１は、そのインデックスにより分岐ヒストリテーブル１５から読み出された状態（予測情報）に従って分岐命令による分岐が発生するか否か予測する。命令キャッシュ２に格納された命令は、その予測結果に従ってプリフェッチされ、ＩＢＦ１０１を介して発行制御回路１１に送られる。プリフェッチされる命令は、分岐不成立と予測すれば、プログラムカウンタ１２が示すアドレスに格納された命令であり、分岐成立と予測すれば、分岐命令キャッシュ１３に格納されている対応の分岐先アドレスに格納された命令である。

分岐命令数カウンタ部１８は、実行が完了した分岐命令数をカウントするためのものである。
比較器１８ａは、所定値（ここでは６５５３６）と加算器１８ｂの出力値を比較し、それらが一致する場合に出力信号をＨにするものである。その加算器１８ｂは、ＲＳＢ４が出力する分岐命令の完了通知により、レジスタ１８ｄの値とそのＲＳＢ４が出力する値（ここでは１）を加算し、その加算結果を出力する。その加算結果は、比較器１８ａの他に、論理積演算回路１８ｃに出力される。その論理積演算回路１８ｃは、その加算結果と、比較器１８ａの出力信号を反転した信号との論理積をビット単位でとる。レジスタ１８ｄには、その結果が格納される。論理積演算回路１８ｃに比較器１８ａの出力信号が反転されて入力されることから、その出力信号がＨとなるとレジスタ１８ｄに格納される値は０となる。このようなことから、分岐命令数カウンタ部１８は、比較器１８ａが出力信号をＨに変化させてから次にＨに変化させるまでの間、ＲＳＢ４が分岐命令の完了通加を出力した回数をカウントする。 分岐命令キャッシュミス数カウンタ部１９は、所定値の分岐命令を実行する間に、分岐命令キャッシュ１３で発生したキャッシュミス数をカウントするためのものである。

比較器１９ａは、所定値（ここでは５１２）と加算器１９ｂの出力値を比較し、その出力値が所定値より大きい場合に出力信号をＨにするものである。その加算器１９ｂは、ＲＳＢ４が出力する分岐命令のキャッシュミス通知により、レジスタ１９ｄの値とそのＲＳＢ４が出力する値（ここでは１）を加算し、その加算結果を出力する。その加算結果は、比較器１９ａの他に、論理積演算回路１９ｃに出力される。その論理積演算回路１９ｃは、その加算結果と、分岐命令数カウンタ部１８の比較器１８ａの出力信号を反転した信号との論理積をビット単位でとる。レジスタ１９ｄには、その結果が格納される。論理積演算回路１９ｃに比較器１８ａの出力信号が反転されて入力されることから、その出力信号がＨとなるとレジスタ１９ｄに格納される値は０となる。このようなことから、分岐命令数カウンタ部１９は、比較器１８ａが出力信号をＨに変化させてから次にＨに変化させるまでの間、ＲＳＢ４が分岐命令のキャッシュミス通知を出力した回数をカウントする。

分岐命令キャッシュミス率閾値越えフラグバッファ部（以降「バッファ部」と略記）２０は、比較器１８ａが出力信号をＨとした際の比較器１９ａの信号値を過去、複数分保存するためのものである。ここでは、過去４回分、保存すると想定する。

シフタ２０ａは、レジスタ２０ｂが保持している値を１ビット、シフトするものである。レジスタ２０ｂは、比較器１８ａの出力信号がＨとなると、シフタ２０ａがシフトした後の値を保持する。比較器１９ａの信号は、シフトする値のないビットの値としてレジスタ２０ｂに入力されて保持される。それにより、レジスタ２０ｂの４ビットの各値が「０１１０」、比較器１９ａの信号値が「１」の状態で比較器１８ａの出力信号がＨとなった場合には、レジスタ２０ｂには新たに「１１０１」が保持されることになる。

比較器２２は、レジスタ２０ｂの値と４ビットの値「００００」を比較し、それらが一致している場合に出力信号をＨとするものである。同様に比較器２３は、レジスタ２０ｂの値と４ビットの値「１１１１」を比較し、それらが一致している場合に出力信号をＨとするものである。比較器２２の出力信号がＨとなることは、分岐命令を６５５３６個実行する間に５１２個より多くのキャッシュミスが発生する状況が連続して４回以上、継続したことを意味する。比較器２３の出力信号がＨとなることは、分岐命令を６５５３６個実行する間に５１２個以下のキャッシュミスが発生する状況が連続して４回以上、継続したことを意味する。

モードレジスタ部２１は、論理積演算回路２１ａ、論理和演算回路２１ｂ、及びレジスタ２１ｃを備えている。比較器２２の出力信号は、反転されて論理積演算回路２１ｂに入力される。論理積演算回路２１ｂは、その反転された出力信号と、レジスタ２１ｃの値の論理積を算出する。それにより、その算出結果は、レジスタ２１ｃの値が「１」であり、且つ比較器２２の出力値が「０」の場合に「１」となる。

論理積演算回路２１の算出結果は論理和演算回路２１ｂに出力され、その演算回路２１ｂによって、比較器２３の出力値との論理和が算出される。レジスタ２１ｃには、その算出結果が保持される。その算出結果は、論理積演算回路２１ａ、及び比較器２３の各出力値の一方が「１」の場合に「１」となる。

上記マスク回路１６には、レジスタ２１ｃに保持された値が反転されて入力される。その値は、比較器２３の出力値が「１」となるか、或いはレジスタ２１ｃに「１」が保持された状態で比較器２２の出力値が「０」となった場合に「１」となる。「１」となった値が「０」となるのは、比較器２３の出力値が「０」となり、且つ比較器２３の出力値が「１」となった場合である。

このようにして、本実施の形態では、分岐命令キャッシュ１３におけるキャッシュミスの発生に注目して、分岐ヒストリレジスタ１４のなかで有効とするビット幅を動的に変化させるようにしている。これは、以下のような理由からである。

図５は、ベンチマークと分岐予測ミス率の関係を説明する図である。その関係は、分岐ヒストリレジスタ１４のビット幅が７ビットの場合のものである。
分岐予測ミス率の観点では、ＳＰＥＣベンチマークには最近の分岐命令の分岐／非分岐の履歴に強く依存するという特徴があることから、分岐命令が実際に分岐するか否かの予測は複雑なものとなる。そのため、分岐予測ミス率は、ＳＰＥＣベンチマークの種類によって大きく異なり、分岐予測ミス率が低いものから高いものまである。

一方、ＴＰＣ−Ｃベンチマークの場合には、最近の分岐命令の分岐／非分岐にはあまり依存せず、分岐命令が実際に分岐するか否かの予測は比較的に単純なものとなる。しかし、異なるアドレスの分岐命令の出現頻度が高いため、分岐命令キャッシュ１３に対応するタグ情報等を格納できないことが発生し易く、また、分岐ヒストリテーブル１５も容量不足により、状態（予測情報）を独立に格納できる分岐命令数が減少する。それにより、分岐予測ミス率は高くなってしまうことが多いのが実状である。このようなことから、プログラムがＳＰＥＣベンチマーク、ＴＰＣ−Ｃベンチマークの何れであるかを見分けるのは非常に困難である。

ベンチマーク以外のプログラムでは、２レベル型分岐予測装置が行う分岐予測そのものの精度が低いことがありうる。分岐予測ミス率では、そのような相性の関係を正確に判断することは非常に困難である。このようなことからも、異なるアドレスの分岐命令の出現頻度を表す指標（情報）として採用することは非常に困難である。分岐予測ミス率に着目して分岐ヒストリレジスタ１４のビット幅を変更する場合、その変更制御を安定的に行えない可能性があることがシミュレーションによって判明している。具体的には、分岐予測ミス率が高いことからビット幅をより小さくするとそのミス率が低下し、その低下によってビット幅をより大きくするというように、ビット幅を頻繁に変更するようなことが発生してしまう可能性がある。そのような不安定性は望ましくない。

分岐命令キャッシュ１３のキャッシュミス率の観点では、ＳＰＥＣベンチマークには分岐命令数が比較的に少ないという特徴があるため、そのキャッシュミス率は低い値を示すと言える。逆にＴＰＣ−Ｃベンチマークでは、分岐命令数が比較的に多いという特徴があるため、そのキャッシュミス率は高い値を示すと言える。このようなことから、そのキャッシュミスに着目することにより、プログラム中に存在する異なるアドレスの分岐命令の出現頻度を正確に予測することができる。

図６は、ベンチマークと分岐命令キャッシュミス率の関係を説明する図である。
図６に示すように、ＳＰＥＣベンチマークとＴＰＣ−Ｃベンチマークとでは、分岐命令キャッシュミス率に明確な差が存在している。このため、分岐命令キャッシュミスに着目することにより、分岐命令の出現頻度に応じたビット幅の動的な変更を正確に行うことができる。それにより、プログラムとしてＳＰＥＣベンチマーク、及びＴＰＣ−Ｃベンチマークを考慮する場合には、その両方で最大限の性能を発揮させることができる。

図８は、分岐ヒストリレジスタ１４の有効とするビット幅の動的な変更を行った場合のベンチマークと分岐予測ミス率の関係を説明する図である。分岐命令キャッシュミスに着目してビット幅を動的に変更することにより、図８に示すように、その変更を行わない場合（図５）と比較して、各ベンチマークの分岐予測ミス率はより低く抑えられている。そのため、ベンチマークの種類に係わらず、より性能が発揮できていることが判る。

図７は、本実施の形態による分岐予測装置１の動作の流れを示すフローチャートである。分岐ヒストリレジスタ１４の有効とするビット幅の動的な変更に着目して、それに係わる各部の動作、及びその一連の流れを示したものである。次に図７を参照して、分岐予測装置１の動作について詳細に説明する。

先ず、ステップＳ１では、ＲＳＢ４が次の命令をフェッチして実行する。その命令は発行制御回路３が発行したものであり、フェッチした命令の実行後はステップＳ２に移行して、その命令が分岐命令か否か判定する。実行した命令が分岐命令であった場合、判定はＹＥＳとなってステップＳ３に移行する。そうでない場合には、判定はＮＯとなって上記ステップＳ１に戻る。

ステップＳ３では、分岐命令数カウンタ部１８に分岐命令の完了通知を出力し、加算器１８ｂによりレジスタ１８ｄに保持された値をインクリメントさせる。続くステップＳ４では、分岐命令キャッシュミスが発生したか否か判定する。そのミスの発生が命令フェッチ制御回路１１から通知された場合、判定はＹＥＳとなり、ステップＳ５でキャッシュミス通知を分岐命令キャッシュミス数カウンタ部１９に出力し、加算器１９ｂによりレジスタ１９ｄに保持された値をインクリメントさせる。その後はステップＳ６に移行する。一方、そうでない場合には、判定はＮＯとなり、次にそのステップＳ６に移行する。

ステップＳ６〜Ｓ１２は、各カウンタ部１８、１９、バッファ部２０、モードレジスタ部２１、比較器２２、２３が自動的に動作することで実現される。
先ず、ステップＳ６では、比較器１８ａが加算器１８ｂの加算結果を所定値である６５５３６と比較する。それにより、それらが一致すると比較した場合、判定はＹＥＳとなってステップＳ７に移行し、そうでない場合には、判定はＮＯとなり、ここで一連の動作は終了する。

ステップＳ７では、比較器１９ａが加算器１９ｂの加算結果を所定値である５１２と比較する。それにより、加算結果が５１２より大きいと比較した場合、判定はＹＥＳとなってステップＳ８に移行し、１ビットの出力値を「１」にセットする。その後はステップＳ１０に移行する。そうでない場合には、判定はＮＯとなってステップＳ９に移行し、その出力値を「０」にセットする。それにより、出力値を「０」に維持させたままの状態でステップＳ１０に移行する。

ステップＳ１０では、比較器２２、２３により、バッファ部２０ｂのレジスタ２０ｂに保持された４ビットの値が「００００」「１１１１」及びその他の何れであるか判定する。その値が「００００」と判定した場合、ステップＳ１１でモードレジスタ部２１のレジスタ２１ｃに０を保持させた後、ステップＳ１３に移行する。その値が「１１１１」と判定した場合には、ステップＳ１２でそのレジスタ２１ｃに１を保持させた後、ステップＳ１３に移行する。その値がそれら以外と判定した場合には、次にそのステップＳ１３に移行する。

ステップＳ１３では、ＲＳＢ４が分岐命令数カウンタ部１８に分岐命令の完了通知、分岐命令キャッシュミス数カウンタ部１９にキャッシュミス通知をそれぞれ出力することにより、それらのレジスタ１８ｄ、１９ｄの値を０にする。その後、一連の動作が終了する。

なお、本実施の形態では、分岐命令キャッシュミス率が４回以上、連続して閾値（分岐命令６５５３６個のなかでキャッシュミス数が５１２より大きいミス率）を越えたか否かにより、分岐ヒストリレジスタ１４のビット幅をより小さくさせるようにしているが、そのような回数の条件を設けなくとも良い。つまり、そのミス率が閾値を越えた場合にビット幅を直ちにより小さくさせるようにしても良い。或いは、予め定めた回数のなかで閾値を越えた回数をカウントし、カウントした回数が所定値より大きい場合にビット幅をより小さくさせるようにしても良い。ミス率が閾値を越えたか否かではなく、その大きさによりビット幅をより小さくすべきか否か判定するようにしても良い。それら以外の方法を採用しても良い。これはビット幅をより大きくする場合でも同様である。

異なるアドレスの分岐命令の出現頻度を表す情報として、分岐命令キャッシュミス率に注目しているが、それ以外の情報に注目しても良い。例えば命令キャッシュミス率と分岐命令の出現頻度の積を求め、それをキャッシュミス率の代わりに用いても良い。キャッシュミス率については、分岐命令キャッシュ１３とは異なる種類のキャッシュのものであっても良い。つまり採用するキャッシュの種類に応じたもので良い。

異なるアドレスの分岐命令の出現頻度はプログラムによって異なり、実行させるプログラムが、コンテキストスイッチにより順次、変わる場合もある。このことから、コンテキスト単位でその出現頻度の検出結果や有効とする（適用させる）分岐ヒストリレジスタ１４のビット幅情報を保存して、コンテキストの変更に対応するようにしても良い。そのようにした場合には、より早く性能を最大限に発揮させることができるようになり、分岐ヒストリテーブル１５を汚さずに済む。

出現頻度を考慮すべき分岐命令は、分岐命令のアドレスが異なるものである。そのアドレスによって分岐ヒストリテーブル１５のインデックスは変化する。このことから、分岐命令のアドレスのインデックス毎に、異なるアドレスの分岐命令の出現頻度の検出結果や有効とする（適用させる）分岐ヒストリレジスタ１４のビット幅情報を保存し、フェッチする命令のアドレスのインデックスに応じて適用する分岐ヒストリレジスタ１４のビット幅を変更しても良い。

分岐ヒストリレジスタ１４のなかで有効とするビット幅は２段階で変更しているが、より他段階で変更するようにしても良い。その場合には、異なるアドレスの分岐命令の出現頻度によって段階的に順次ビット幅を変更するか、或いはその出現頻度の大きさに応じて変更すべきビット幅を選択すれば良い。

Claims (6)

1. 最近の分岐命令の分岐結果を複数、履歴として格納する分岐ヒストリレジスタと、該分岐ヒストリレジスタに格納された分岐結果を用いて計算されるインデックス毎に分岐命令が分岐すると予測する確度を示す予測情報を格納した分岐ヒストリテーブルと、を用いて分岐予測を行う分岐予測装置において、
   異なるアドレスの分岐命令の出現頻度を検出する頻度検出手段と、
   前記頻度検出手段が検出した出現頻度に基づいて、前記分岐ヒストリレジスタのなかで有効とするビット幅を動的に変更するビット幅変更手段と、
   を具備することを特徴とする分岐予測装置。
2. 請求項１記載の分岐予測装置であって、
   前記ビット幅変更手段は、前記頻度検出手段が検出する出現頻度が所定値を越えた場合に前記ビット幅を必要に応じてより小さくし、該出現頻度が該所定値以下の場合に必要に応じて該ビット幅をより大きくする。
3. 請求項１記載の分岐予測装置であって、
   前記ビット幅変更手段は、前記頻度検出手段が検出した複数の出現頻度を基に、前記ビット幅を動的に変更する。
4. 請求項１記載の分岐予測装置であって、
   前記頻度検出手段は、前記出現頻度として、分岐命令の有無を示すタグ情報を格納したキャッシュにおけるキャッシュミス率を検出する。
5. 最近の分岐命令の分岐結果を複数、履歴として格納する分岐ヒストリレジスタと、該分岐ヒストリレジスタに格納された分岐結果を用いて計算されるインデックス毎に分岐命令が分岐すると予測する確度を示す予測情報を格納した分岐ヒストリテーブルと、を用いて分岐予測を行う分岐予測方法において、
   異なるアドレスの分岐命令の出現頻度を検出し、
   該検出した出現頻度に基づいて、前記分岐ヒストリレジスタのなかで有効とするビット幅を動的に変更する、
   ことを特徴とする分岐予測方法。
6. 最近の分岐命令の分岐結果を複数、履歴として格納する分岐ヒストリレジスタと、該分岐ヒストリレジスタに格納された分岐結果を用いて計算されるインデックス毎に分岐命令が分岐すると予測する確度を示す予測情報を格納した分岐ヒストリテーブルと、を用いて分岐予測を行うプロセサにおいて、
   異なるアドレスの分岐命令の出現頻度を検出する頻度検出手段と、
   前記頻度検出手段が検出した出現頻度に基づいて、前記分岐ヒストリレジスタのなかで有効とするビット幅を動的に変更するビット幅変更手段と、
   を具備することを特徴とするプロセサ。