分岐予測器及びプロセッサ
【課題】破壊的競合を緩和して分岐予測の精度を向上させる。
【解決手段】分岐予測器１は、分岐命令の分岐正否の予測を行う第１分岐予測部１０と、第１分岐予測部による分岐予測ミスの数が閾値に達した分岐命令を記憶する記憶部２０と、記憶部２０に記憶された分岐命令それぞれについて個別に分岐正否の予測を行う第２分岐予測部３０と、を備えている。予測の対象となる分岐命令が記憶部２０に記憶されている場合には、第２分岐予測部３０による予測を行う。
【解決手段】分岐予測器１は、分岐命令の分岐正否の予測を行う第１分岐予測部１０と、第１分岐予測部による分岐予測ミスの数が閾値に達した分岐命令を記憶する記憶部２０と、記憶部２０に記憶された分岐命令それぞれについて個別に分岐正否の予測を行う第２分岐予測部３０と、を備えている。予測の対象となる分岐命令が記憶部２０に記憶されている場合には、第２分岐予測部３０による予測を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分岐予測器及びプロセッサに関するものである。
【背景技術】
【０００２】
分岐予測は、分岐命令を投機的に実行することにより制御依存を回避する技術であり、高精度の予測を行うことにより、大幅な性能向上が実現される。しかし、分岐予測に失敗したときは、分岐命令以降の実行命令をフラッシュし、正しい分岐先命令を新たにフェッチするため性能が低下する。これは分岐予測ミスペナルティと呼ばれている。
【０００３】
近年の高性能プロセッサでは、パイプライン段数の増加、命令発行幅の増加により高い命令レベル並列性を抽出しており、これに伴い分岐予測ミスペナルティは増加傾向にある。このため、分岐予測精度の更なる向上はプロセッサの性能向上にとって不可欠な課題である。
【０００４】
分岐予測ミスペナルティを減少させるため、様々な分岐予測器が提案されている。１９８１年に最初に提案されたＢｉｍｏｄａｌ予測器（非特許文献１参照）では、各分岐命令の挙動を２ｂｉｔ飽和カウンタで保持し、その値に基づき分岐方向を予測する。飽和型カウンタはＰＨＴ（Pattern History Table）として構成され、分岐命令アドレスの下位ビットをインデクスとしてアクセスされる。
【０００５】
現在多くのプロセッサで用いられているＧｓｈａｒｅ予測器（非特許文献２参照）は、分岐命令のグローバル履歴と分岐命令アドレスの排他的論理和をインデクスとしてＰＨＴにアクセスして分岐予測を行う予測器である。これは分岐命令のグローバル履歴により分岐命令間の相関を利用した予測方法である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】J.E.Smith. "A Study of Branch Prediction Strategies", ISCA 1981, pp.135-148, 1981
【非特許文献２】S.McFarling. "Combining Branch Predictors", Technical report TN-36, Digital Western Research Laboratory, 1993
【発明の概要】
【発明が解決しようとする課題】
【０００７】
これらの分岐予測器における予測ミスの主要な要因として破壊的競合がある。これは、図９に示すように、異なる分岐命令が同じＰＨＴのエントリに分岐結果を登録することにより生じる競合である。現在の主流の分岐予測器では、Ｇｓｈａｒｅ予測器のように、分岐命令アドレスとグローバル分岐履歴を用いてＰＨＴをアクセスするため、破壊的競合はより複雑な様相となり、本質的には避けられない。
【０００８】
そこで、本発明は、破壊的競合を緩和して分岐予測の精度を向上させることを目的とする。
【課題を解決するための手段】
【０００９】
（１）本発明は、分岐命令の分岐正否の予測を行う第１分岐予測部と、前記第１分岐予測部による分岐予測ミスの数が閾値に達した分岐命令を記憶する記憶部と、前記記憶部に記憶された分岐命令それぞれについて個別に分岐正否の予測を行う第２分岐予測部と、を備え、予測の対象となる分岐命令が前記記憶部に記憶されている場合には、前記第２分岐予測部による予測を行うことを特徴とする分岐予測器である。
【００１０】
（２）前記記憶部は、前記記憶部に記憶された分岐命令それぞれについて、前記第１分岐予測部と比較した前記第２分岐予測部による予測の有効性を示す有効性情報を記憶し、前記有効性情報に基づいて前記第２分岐予測部による予測が有効でないと判断された分岐命令を、前記記憶部から削除するのが好ましい。
【００１１】
（３）前記記憶部は、前記記憶部に記憶されている分岐命令の数が、記憶可能な分岐命令の数の上限に達した場合には、ＬＲＵロジックに基づいて、前記記憶部に記憶されている分岐命令のうち最も最近使用されていない分岐命令に、前記第１分岐予測部による分岐予測ミスの数が前記閾値に達した新たな分岐命令を上書きすることで、前記新たな分岐命令を記憶し、前記ＬＲＵロジックでは、前記第２分岐予測部が正しく予測できた場合に、分岐命令が使用されたものとみなすのが好ましい。
【００１２】
（４）前記ＬＲＵロジックでは、第２分岐予測部が正しく予測でき、かつ、第１分岐予測部が正しく予測できなかった場合に、分岐命令が使用されたものとみなすのが好ましい。
【００１３】
（５）前記第１分岐予測部による分岐予測ミスの数を分岐命令毎にカウントするカウンタを備え、前記カウンタの値が前記閾値に達した分岐命令が前記記憶部に記憶されるとともに、前記カウンタの値が前記閾値に達すると前記カウンタがリセットされるのが好ましい。
【００１４】
（６）前記記憶部は、前記記憶部に記憶された分岐命令それぞれの分岐結果の履歴を示す履歴情報を記憶するのが好ましい。
【００１５】
（７）前記第２分岐予測部は、分岐命令の分岐結果の履歴に基づいて分岐予測を行うためのＰＨＴ（Pattern History Table）を、前記記憶部に記憶された分岐命令毎に有しているのが好ましい。
【００１６】
（８）前記第１分岐予測部の予測結果と前記第２分岐予測部の予測結果とを選択的に出力するセレクタを備えているのが好ましい。
【００１７】
（９）前記記憶部に記憶された分岐命令それぞれについて、前記第２分岐予想部による予測の信頼性を示す信頼性情報を記憶する信頼性情報記憶部を備え、前記信頼性情報は、前記第２分岐予測器の予測が成功した数に基づく情報であり、前記セレクタは、前記信頼性情報に基づいて、前記第１分岐予測部の予測結果及び前記第２分岐予測部の予測結果のいずれを出力するかを決定するのが好ましい。
【００１８】
（１０）他の観点からみた本発明は、前記（１）〜（９）のいずれか１項に記載の分岐予測器によって分岐命令の分岐予測を行うプロセッサである。
【発明の効果】
【００１９】
本発明によれば、破壊的競合を緩和して分岐予測の精度を向上させることができる。
【図面の簡単な説明】
【００２０】
【図１】（ａ）はＣｏｍｂｉｎｉｎｇ予測器によける予測ミスの偏りを示し、（ｂ）はＢｉｍｏｄｅ予測器における予測ミスの偏りを示す図である。
【図２】分岐予測器のブロック図である。
【図３】Ｃｏｍｂｉｎｉｎｇにおける予測ミス削減率を示す図である。
【図４】Ｂｉｍｏｄｅにおける予測ミス削減率を示す図である。
【図５】Ｂｉｍｏｄｅ−Ｐｌｕｓにおける予測ミス削減率を示す図である。
【図６】Ａｇｒｅｅにおける予測ミス削減率を示す図である。
【図７】Ｈｙｂｒｉｄにおける予測ミス削減率を示す図である。
【図８】ＭＰＫＩ結果を示す表である。
【図９】複数の命令が同一のＰＨＴエントリにアクセスすることを示す図である。
【発明を実施するための形態】
【００２１】
以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。
【００２２】
［１．予測ミスの偏り］
本発明者らは、分岐命令の予測ミスに偏りがあることを新たに見出した。ここでは、従来の分岐予測器において、予測ミスが少数の分岐命令に集中して発生することを示す。
【００２３】
予測ミスの偏りの度合いを評価するため、まず、SimpleScalar Tool Set（D.Burger, T.M.Austin. "The SimpleScalar ToolSet , Version2.0", Technical Report, University of Wisconsin-Madison Computer Sciences Dpt, July 1997）を用いて、Combining予測器とBimode予測器を実行して評価を行う。ベンチマークには、SPECint2000（The Standard Performance Evaluation Corporation)から、bzip, gcc, gzip, mcf, parser, twolf, vpr, vortexの８本を使用する。
【００２４】
評価に用いたプロセッサの使用を表１に示す。命令セットは、SimpleScalar PISAを用いる。
【表１】
【００２５】
これらのベンチマークにおいて、最も多く予測ミスが発生する上位８個と上位１６個の分岐命令を抽出し、これらの予測ミスが全体の予測ミスに占める割合を調べる。
【００２６】
図１（ａ）は、Ｃｏｍｂｉｎｉｎｇ予測器において、予測ミスが最も多い上位８個と１６個の分岐命令の予測ミスが全体の予測ミスに占める割合を示し、図１（ｂ）は、Ｂｉｍｏｄｅ予測器において、予測ミスが最も多い上位８個と１６個の分岐命令の予測ミスが全体の予測ミスに占める割合を示す。
なお、予測ミスはプログラムの実行状況に応じて変化するため、調べ方については、２０Ｍ命令ごとに最もミスの多い上位８個（あるいは１６個）の分岐命令を抽出し、それらの予測ミスが全体の予測ミスに占める割合を調べ、これを５回繰り返して１００Ｍ命令まで評価する。
【００２７】
予測器のハードウェア量は、８ＫＢ、１６ＫＢ、３２ＫＢの３種類について評価を行う。非特許文献２では、Gshare予測器のサイズがBimode予測器のサイズの２倍になるとき、より良い性能が得られると報告されている。そのため、Combining予測器では、Bimode予測器とSelectorのエントリ数を８Ｋ，１６Ｋ，３２Ｋ、Gshare予測器のエントリ数を１６Ｋ，３２Ｋ，６４Ｋと設定する。Bimode予測器については、Gshare予測器のエントリ数を８Ｋ，１６Ｋ，３２Ｋとし、ChoicePHTのエントリ数を１６Ｋ，３２Ｋ，６４Ｋと設定する。
【００２８】
図１（ａ）（ｂ）横軸は実行命令数であり、縦軸はミスの多い分岐命令の予測ミスが全体の予測ミスに占める割合である。また、「８−８ＫＢ」「８−１６Ｋ」「８−３２Ｋ」は、それぞれ、予測器のハードウェア量が８ＫＢ、１６ＫＢ、３２ＫＢである場合について、予測ミスが最も多い上位８個の分岐命令の予測ミスが全体の予測ミスに占める割合を示している。「１６−８ＫＢ」「１６−１６Ｋ」「１６−３２Ｋ」は、それぞれ、予測器のハードウェア量が８ＫＢ、１６ＫＢ、３２ＫＢである場合について、予測ミスが最も多い上位８個の分岐命令の予測ミスが全体の予測ミスに占める割合を示している。
【００２９】
図１（ａ）（ｂ）より、Combining予測器とBimode予測器では、８個の分岐命令の予測ミスが、全体のミスの７０％以上を占めることが分かる。さらに、１６個の分岐命令の予測ミスが、全体のミスの８０％以上を占めることが分かる。
【００３０】
［２．実施形態に係る分岐予測器及びプロセッサ］
本実施形態に係るプロセッサは、スーパースカラプロセッサであり、分岐予測器１を備えている。図１は、プロセッサが有する分岐予測器１を示している。この分岐予測器１は、予測ミスが少数の分岐命令に偏るという特性を利用したものである。つまり、予測ミスの多い特定の分岐命令については、破壊的競合が生じないように、予測ミスの多い特定の分岐命令毎の履歴（ローカル履歴）を用いて分岐予測を行う。
【００３１】
図１に示すように、分岐予測器１は、第１分岐予測部であるベース予測器（Base Predictor）１０と、ＭＢＰ（Miss Bias Predictor）２０と、予測ミスの多い特定の分岐命令について分岐予測を行う第２分岐予測部であるＬＨＢＰ（Local History Branch predictor）３０と、セレクタ４０と、を備えている。
【００３２】
［２．１ ベース予測器（第１予測器）の構成］
ベース予測器１０は、分岐予測の必要な全ての分岐命令について分岐予測を行う。
ベース予測器（第１分岐予測部）１０としては、分岐命令の分岐成否の予測（分岐予測）を行う従来の分岐予測器が用いられている。ベース予測器１０としては、例えば、Combining予測器、Bimode予測器、Bimod-Plus予測器、Agree予測器、Hybrid予測器、Gshare予測器など、破壊的競合の起こり得る予測器を採用することができる。
ベース予測器１０として、ＧＢＨ（Global Branch History;グローバル分岐履歴）を用いる予測器を採用した場合、ベース予測器１０には、ＧＢＨが与えられ、プログラムカウンタ（ＰＣ）２が示すアドレスの分岐命令について、分岐予測の結果を出力し、セレクタ３０に与える。
【００３３】
［２．２ ＭＢＰの構成］
ＭＢＰ２０は、分岐予測ミスの多い分岐命令を検出して、その分岐命令を、ローカル分岐履歴などの情報とともに記憶するためのものである。ＭＢＰ２０は、拡張されたＢＴＢ（Branch Target Buffer）機構であるＥＢＴＢ（Extended BTB）２１と、予測ミスの多い分岐命令を記憶するＭＢＢ（Miss Bias Buffer）２２と、を有している。
【００３４】
［２．２．１ ＥＢＴＢの構成］
ＥＢＴＢの基礎となるＢＴＢ機構は、分岐先予測（Branch Target Prediction）のために予測アドレス（Target Address）を得るための機構であり、分岐命令のアドレスの一部を格納するＴａｇと、各分岐命令のアドレスに対応する予測アドレス（分岐アドレス）を格納するＴａｄｄｒと、を有している。
【００３５】
ＥＢＴＢ２１は、上記ＢＴＢ機構を利用して、分岐予測ミスの多い分岐命令を検出するための検出部として機能する。
ＢＴＢを拡張したＥＢＴＢ２１は、従来のＢＴＢと同じように、Ｔａｇ２１ａと、Ｔａｄｄｒ２１ｃと、を備え、さらに、各エントリには、飽和カウンタによって構成されたＭＣＴ（Miss Counter）２１ｂを備えている。
【００３６】
分岐命令のアドレスの下位ビットｉ〜０に対応するエントリのＴａｇ２１ａには、当該分岐命令のｎビットアドレスの上位ビットｎ−１〜ｉ＋１が格納される。プログラムカウンタ（ＰＣ）２から、分岐命令のアドレスの下位ビットｉ〜０が、ＥＢＴＢのエントリに与えられると、分岐命令のアドレスの下位ビットｉ〜０に対応するエントリのＴａｇ２１ａに格納されているビット列が、判定部２１ｄに出力される。判定部２１ｄは、プログラムカウンタ２から、当該分岐命令のアドレスの上位ビットｎ−１〜ｉ＋１のビット列も与えられる。
【００３７】
判定部２１ｄは、ＥＢＴＢ２１から出力されたビット列とプログラムカウンタ２から出力されたビット列とが一致するか否かの判定を行い、一致の場合は、ヒットとなる。なお、ＥＢＴＢ２を通常のＢＴＢとしても用いる場合、判定部２１の結果がヒットであると、分岐命令のアドレスの下位ビットｉ〜０に対応するエントリのＴａｄｄｒ２１ｃが予測アドレスとして出力される。
【００３８】
ＭＣＴ２１ｂは、ベース予測器１０の分岐正否の分岐予測ミスの数カウントするためのものである。ＭＣＴ２１ｂは、ＥＢＴＢ２１の各エントリに設けられているため、ＥＢＴＢ２１では、Ｔａｇ２１ａにアドレス（の一部）が格納されている分岐命令毎に、分岐予測ミスの数がカウントされることになる。
なお、ＭＣＴ２１ｂのサイズは、例えば、４ｂｉｔ程度あれば足りる。
また、ＥＢＴＢ２１のエントリ数は、２ｉ個である。
【００３９】
［２．２．２ ＭＢＢ（記憶部）の構成］
予測ミスの多発する分岐命令を格納するＭＢＢ（記憶部）２２は、Ａｄｄｒ２２ａと、ＬＨ２２ｂと、Ｕ２２ｃと、ＦＲ２２ｄと、を備えている。
Ａｄｄｒ２２ａは、予測ミスの多発する分岐命令のアドレス（ｎビット）が格納される領域であり、分岐命令アドレスの格納により、分岐命令が記憶されていることになる。
ＬＨ（Local branch History）２２ｂは、分岐命令のローカル分岐履歴を記憶する領域であり、ｍビットのシフトレジスタによって構成され、過去ｍ回の分岐正否を各ビットの０／１で記憶する。
【００４０】
Ｕ（Use bit）２２ｃは、該当するエントリが使用されているかどうかを示すビットであり、１が使用中を示し、０が未使用を示す。
ＦＲ（Trace Failure Rate）２２ｄは、７ｂｉｔの飽和カウンタであり、第２分岐予測部であるＬＨＢＰ３０の分岐予測ミスの数と、第１分岐予測部であるベース予測器１０の分岐予測ミスの数と、の差を有効性情報として保持する。
【００４１】
有効性情報は、ベース予測器（第１分岐予測部）１０と比較したＬＨＢＰ（第２分岐予測部）３０の有効性を示す情報である。ＭＢＢ２２に（アドレスが）記憶されている分岐命令それぞれの有効性情報に基づいて、有効でないと判断された分岐命令は、ＭＢＢ２２から削除される（Ｕ２２ｃが未使用を示す０にセットされる）。
【００４２】
ＭＢＢ２２のエントリ数が多いほど、分岐予測ミスの多発する分岐命令（のアドレス）を、ＭＢＢ２２に多く格納することができる。ただし、本発明者らの実験の結果、ＭＢＢ２２のエントリ数を多くしても、分岐予測ミスの減少は僅かであったことから、ＭＢＢ２２のエントリ数（ＭＢＢ２２に記憶できる分岐命令数）は、８個又は１６個程度でよい。
【００４３】
［２．３ ＬＨＢＰ（第２分岐予測部）の構成］
第２分岐予測部であるＬＨＢＰ３０は、ベース予測器１０にて分岐予測がなされる分岐命令の一部について、分岐成否の予測を行う。具体的には、ＬＨＢＰ３０は、ＭＢＢ２２に記憶されている分岐命令（ＥＢＴＢ２１によって分岐予測ミスが多いことが検出された分岐命令）について、分岐予測を行う。つまり、ＬＨＢＰ３０にて分岐予測がなされる分岐命令につては、ベース予測器１０とＬＨＢＰ３０の双方で分岐予測がなされることになる。
【００４４】
ＬＨＢＰ３０は、ＭＢＢ２２に記憶されている分岐命令毎に個別の分岐履歴（ローカル分岐履歴）に基づいて分岐予測を行う複数のＬＰＨＴ（Local Pattern History Table）３１，３２，・・・を備えている。
【００４５】
ＬＰＨＴ３１，３２，・・・は、それぞれ、分岐命令の分岐結果の履歴（ローカル分岐履歴）に基づいて分岐予測を行うためのＰＨＴ（Pattern History Table）として構成されている。
ＬＰＨＴ３１，３２，・・・は、それぞれ、ＮＴＣＴ（2bit Taken Not Taken saturating CounTer）３１ａ，３２ａと、ＣＦ（ConFidence）３１ｂ，３２ｂと、を有している。
【００４６】
ＮＴＣＴ３１ａ，３２ａは、一般的なＰＨＴと同様に、２ビット飽和カウンタによって構成され、分岐の成否について予測される４つの状態（Strongly NotTaken, Weakly NotTaken, Weakly Taken, Strongly Taken）を保持している。ＮＴＣＴ３１ａ，３２ａは、対応する分岐命令のみの分岐結果によって、インクリメント又はデクリメントされ、他の分岐命令の分岐結果によってはインクリメント又はデクリメントされない。
【００４７】
ＣＦ３１ｂ，３２ｂは、同一エントリのＮＴＣＴ３１ａ，３２ａによる予測の信頼性を示す信頼性情報を記憶する領域（信頼性情報記憶部）である。ＣＦ３１ａ，３２ａは、２ビットMiss Resetting Counterとして構成されており、同一エントリのＮＴＣＴ３１ａ，３２ａによる予測が成功した場合には、ＣＦがインクリメントされ、予測ミスの場合にはリセットされる。
【００４８】
ＬＰＨＴ３１，３２・・・の個数は、ＭＢＢ２２のエントリ数（分岐予測ミスの多い分岐命令を記憶可能な数）と同じである。例えば、ＭＢＢ２２の一番目のエントリの分岐命令は、「ＬＰＨＴ１」３１を用いて分岐予測がなされる。また、ＭＢＢ２２の二番目のエントリの分岐命令は、「ＬＰＨＴ２」３２を用いて分岐予測がなされる。これにより、ＬＨＢＰ２０においては、ＭＢＢ２２に格納されている分岐命令同士での破壊的競合は生じない。
また、ＭＢＢ２２に格納されている分岐命令の数は、ベース予測器（第１分岐予測部）１０によって分岐予測がなされる分岐命令全体のうちのごく一部であるから、ＬＨＢＰ（第２分岐予測部）３０を別途も受けても、ハードウェア量の増加は少ない。
【００４９】
ＬＰＨＴ３１，３２・・・のエントリ数は、使用する分岐履歴（ローカル分岐履歴）の長さにより決まる。すなわち、ＬＰＨＴ３１，３２・・・は、それぞれ、分岐命令のローカル分岐履歴を記憶するＬＨ２２ｂのビット数ｍに対して、２ｍのエントリ数を持つ。ＬＰＨＴのエントリ数は、例えば、５１２に設定することができる。
【００５０】
［２．４ ＭＢＰによる予測ミスの多発する分岐命令の発見に関する処理］
［２．４．１ ＥＢＴＢに関する動作（予測ミスの多発する分岐命令の発見）］
ＭＢＰ２０は、岐命令がコミットされるときに、分岐命令のアドレスを用いてＥＢＴＢ２１の検索を行う。つまり、分岐命令が実行されてベース分岐予測器１０による分岐正否の結果が判明し、コミット状態になると、プログラムカウンタ２が示す当該分岐命令のアドレスを用いて、ＥＢＴＢ２１を検索する。
ＥＢＴＢ２１の検索の結果、検索対象の分岐命令アドレスがＴａｇ２１ａに格納されており、判定部２１ｄの判定結果がヒットになり、かつ、当該分岐命令に対するベース予測器１０による分岐予測が予測ミスであった場合には、対応するＭＣＴ２１ｂがインクリメントされる。なお、判定部２１ｄの判定結果がヒットになっても、予測ミスでない場合は、対応するＭＣＴ２１ｂは変化しない。
【００５１】
ＥＢＴＢ２１の検索の結果、検索対象の分岐命令アドレスがＴａｇ２１ａに格納されておらず、判定部２１ｄの判定結果がヒットにならない場合は、従来のＢＴＢと同じように、Ｔａｇ２１ａの更新を行い、当該分岐命令に対するベース予測器１０による分岐予測が予測ミスであった場合には、ＭＣＴを１にセットし、予測成功であった場合には、ＭＣＴを０にセットする。
このようにして、ＥＢＴＢ２１には、予測ミスの生じた分岐命令と、それぞれの分岐命令の予測ミスの数が保持される。
【００５２】
いずれかのＥＢＴＢエントリのＭＣＴ２１ｂが第１閾値に達すると、当該エントリの分岐命令に予測ミスが多発しているものとみなす。このようにして、ＥＢＴＢ２１は、予測ミスの多い分岐命令を検出することができる。
【００５３】
［２．４．２ ＭＢＢへの登録］
ＭＣＴ２１ｂが第１閾値に達した分岐命令は、そのアドレスが、ＭＢＢ２２のＡｄｄｒ２２ａに登録される。そして、該当するＥＢＴＢ２１のエントリのＭＣＴ２１ｂがリセットされる。第１閾値に一旦達した分岐命令のＭＣＴ２１ｂがリセットされることで、当該分岐命令の予測ミス数が再度カウント可能となり、当該分岐命令が、再度、ＭＢＢ２２に登録される機会が得られ易くなる。
【００５４】
ＭＢＢ２２への登録は、以下のように行われる。まず、登録しようとした分岐命令のアドレスが、ＭＢＢ２２のＡｄｄｒ２２ａに存在するかどうかをチェックされる。このアドレスがＭＢＢ２２に存在しない場合には、Ｕ２２ｃが０（未使用）のエントリが存在するならば、そのエントリに、そのアドレスを登録し、Ｕ２２ｃを１（使用）にする。
【００５５】
もし、ＭＢＢ２２のＵ２２ｃがすべて１（使用）の場合、すなわち、ＭＢＢ２２に記憶されている分岐命令の数が、ＭＢＢ２２に記憶可能な分岐命令の数（例えば、８個又は１６個）の上限に達している場合、ＭＢＢ２２は、ＬＲＵ（Least Recently Used）ロジックを利用して、最も最近使用されていないエントリを選択し、そのエントリのＡｄｄｒ２２ａに、そのアドレスを上書き登録する。また、そのエントリのＦＲ２２ｄもリセットされる。
【００５６】
なお、本実施形態では、上記ＬＲＵロジックにおいては、ＬＨＢＰ（第２分岐予測部）３０が正しく分岐予測でき、かつ、ベース予測器（第１分岐予測部）１０が正しく予測できなかった場合に、分岐命令が使用されたものとみなす。
分岐命令が単に実行された場合に使用されたものとみなすのではなく、ＬＨＢＰ（第２分岐予測部）３０が正しく分岐予測できた場合に、分岐命令が使用されたものとみなすことで、分岐予測ミスであった分岐命令は、ＭＢＢ２２から削除され易くなる。
また、ベース予測器（第１分岐予測部）１０が正しく予測できなかった場合であることも使用の条件に加えることで、ベース予測器１０の方が有用である分岐命令が、ＭＢＢ２２から削除され易くなる。
【００５７】
［２．４．３ ＭＢＢの更新］
分岐命令がコミットされるとき、当該分岐命令が既にＭＢＢ２２に登録されているならば、ＭＢＢ２２の更新が行われる。
当該分岐命令に対応するエントリのＬＨ２２ｂについては、ローカル履歴が更新される。つまり、シフトレジスタからなるＬＨ２２ｂに対して、当該分岐命令の実行結果（分岐正否の結果）としての０／１の入力によるシフトがなされる。
【００５８】
ＦＲ２２ｄの更新については、ＬＨＢＰ（第２分岐予測部）３０での予測が失敗し、かつ、ベース予測器（第１分岐予測部）１０の予測が成功の場合は、ＦＲ２２ｄがインクリメントされる。一方、ＬＨＢＰ３０での予想が成功、かつ、ベース予測器１０の予測が失敗の場合は、デクリメントする。これにより、ＦＲ２２ｄには、ベース予測器１０と比較したＬＨＢＰ３０による予測の有効性情報として、ベース予測器１０とＬＨＢＰ３０の予測の差を格納できる。
【００５９】
ＦＲ２２ｄの値が、第２閾値になると、ＬＨＢＰ３０による予測ミスが、ベース予測器１０よりも多く発生するために、ＬＨＢＰ３０による予測が有効でないと判断し、ＭＢＢ２２は、当該エントリにおける各領域２２ａ，２２ｂ，２２ｃ，２２ｄをリセットする。これにより、ＬＨＢＰ３０による予測が有効でないと判断された分岐命令が、ＭＢＢ２２から削除される。
【００６０】
［２．４．４ ＬＰＨＴの更新］
分岐命令がコミットされるときに、当該分岐命令のアドレスを用いて、ＭＢＢ２２を検索する。当該分岐命令のアドレスが、ＭＢＢ２２のいずれかのエントリのＡｄｄｒ２２ａに存在する場合には、そのＡｄｄｒ２２ａと同一エントリにあるＬＨ２２ｂのローカル分岐履歴を利用して、ＬＰＨＴを更新する。
具体的には、当該分岐命令のアドレスに対応するＡｄｄｒ２２ａと同一エントリにあるＬＨ２２ｂが示すローカル履歴（ｍｂｉｔのビット列）に対応するＬＰＨＴエントリのＮＴＣＴ３２ａを、当該ＬＨ２２ｂが占めるローカル履歴の情報で更新する。
さらに、ＣＦ３１ｂ、３２ｂの更新も行われる。すなわち、予測が成功した場合はインクリメントされ、予測ミスの場合はリセットされる。
【００６１】
［２．５ ＬＨＢＰによる分岐予測］
分岐命令がフェッチされるときに、フェッチされた分岐命令のアドレスを用いて、ＭＢＢ２２を検索する。当該アドレスが、ＭＢＢ２２のＡｄｄｒ２２ａに存在する場合には、そのＡｄｄｒ２２ａと同一エントリにあるＬＨ２２ｂに対応するＬＰＨＴのエントリのＮＴＣＴとＣＦの値を得る。
得られたＮＴＣＴを用いて、フェッチされた分岐命令のＬＨＢＰ（第２分岐予測部）３０による分岐予測結果（Taken 又は Not Taken）が出力され、ＣＦの値とともにセレクタ４０の取得部４１に与えられる。
【００６２】
取得部４１は、ＬＨＢＰ３０の分岐予測結果を、セレクタ本体４２に与える。セレクタ本体４２には、フェッチされた当該分岐命令のベース予測器（第１分岐予測部）１０による分岐予測結果も与えられる。
セレクタ本体４２は、取得部４１からＣＦの値を得て、ベース予測器１０による分岐予測結果とＬＨＢＰ３０による分岐予測結果とを選択的に出力する。具体的には、セレクタ本体４２は、ＣＦ（信頼性情報）の値が第３閾値に達している場合に、ＬＨＢＰ３０の分岐予測結果を出力し、その他の場合はベース予測器１０の分岐予測結果を、出力する。
【００６３】
ＣＦの値は、予測ミスがあるとリセットされるため、ＣＦの値が第３閾値に達するまで連続して予測に成功しないと、ＬＨＢＰ３０の予測結果は使用されず、ベース予測器１０による予測結果が使用される。これにより、ローカル履歴のみを用いたＬＨＢＰ３０による分岐予測の誤動作を緩和することができる。
【００６４】
［３．評価］
［３．１ 予測ミスの削減率の評価］
ベース予測器１０として、Combining予測器、Bimode予測器、Bimode-Plus予測器、Agree予測器、Hybrid予測器の５種類を用いる。ベース予測器１０であるCombining、Bimode、Bimode-Plus、Agreeのサイズを、８ＫＢ、１６ＫＢ，３２ＫＢ，６４ＫＢの４種類とし、Hybrid予測器のサイズは、１０．５ＫＢ，１７．７５ＫＢ，３０ＫＢ，６０．５ＫＢと設定する。
【００６５】
図３〜図７は、それぞれ、分岐予測器１における予測ミスの削減率の評価結果を、ベンチマーク毎に示している。図３〜図７において、横軸はベンチマークであり、縦軸は、本実施形態に係る分岐予測器１の、ベース分岐予測器に対する予測ミス削減率である。
なお、ベンチマークとしては、CommBenchから、drr, reed_dec, reed_enc, rtr, zip_enc の５種類を用い、SPECint2000から、bzip, gcc, gzip, mcf, parser, twolf, vortex, vpr の８種類を用いた。
【００６６】
図３〜図５に示すように、ベース予測器１０として、Combining, Bimode, Bimode-Plusを用いた分岐予測器１は、SPECint2000において、最大４０％以上、平均１０％以上の予測ミスを減らすことができ、CommBenchにおいて、最大３０％、平均６％以上の予測ミスを減らすことができた。
図６に示すように、ベース予測器１０として、Agreeを用いた分岐予測器１は、SPECint2000において、最大２３％以上、平均１０％以上の予測ミスを減らすことができ、CommBenchにおいて、最大３０％、平均６％程度の予測ミスを減らすことができた。
図７に示すように、ベース予測器１０として、Hybridを用いた分岐予測器１は、SPECint2000において、最大４５％以上、平均７％以上の予測ミスを減らすことができ、CommBenchにおいて、最大２０％、平均３％程度の予測ミスを減らすことができた。
【００６７】
［３．２ ハードウェア規模の検討］
実施形態に係る分岐予測器１のうち、ＥＢＴＢ２１に関しては、ＢＴＢが持つ検索ポートを利用するために、ＢＴＢを拡張したＥＢＴＢ２１には、検索用のポートを追加する必要がない。また、ＥＢＴＢ２１に含まれるＭＣＴ２１ｂは４ｂｉｔのため、ＥＢＴＢ２１のエントリ数が、６４個であれば、ＢＴＢを拡張してＥＢＴＢ２１にするために必要なメモリ量は、１ＫＢである。
【００６８】
ＭＢＢ２２について、Ａｄｄｒ２２ａが３２ｂｉｔ、ＬＨ２２ｂが９ｂｉｔ、Ｕ２２ｃが１ｂｉｔ、ＦＲ２２ｄが７ｂｉｔであると、各エントリそれぞれについての語長は４９ビットとなる。したがって、ＭＢＢ２２のエントリ数を８とすると、ＭＢＢ２２のために必要なメモリ量は３９２ｂｉｔのＣＡＭとなる。
【００６９】
ＬＰＨＴ３１，３２，・・・については、個数が８個、それぞれのエントリ数が５１２、ＮＴＣＴが２ｂｉｔ、ＣＦが２ｂｉｔとすると、語長は４ｂｉｔとなり、必要なメモリ量は２ＫＢである。
【００７０】
したがって、本実施形態に係る分岐予測器１は、従来の分岐予測器（ベース予測器のみ）に対して、３ＫＢ程度、ハードウェア量が増加する。
【００７１】
図８は、予測器のサイズとそれらのＭＰＫＩ（Miss-prediction Per Kilo Instruction）の関係を示す。予測器の各欄は、対応するサイズでのＭＰＫＩである。図８に示すように、例えば、８ＫＢのCombining予測器と、８ＫＢのCombining予測器をベース予測器１０として有する分岐予測器１とを比較すると、ＭＰＫＩの値が低下している。８ＫＢのCombining予測器をベース予測器１０として有する分岐予測器１は、６４ＫＢのCombining予測器と同等以上の性能になる。これは、Bimode、Bimode-Plus、Agreeについても同様である。
これらのことより、本実施形態の分岐予測器１は、従来の分岐予測器のエントリー数の増加以上の効果が得られる。
【００７２】
［４．付記］
なお、上記において開示した事項は、例示であって、本発明を限定するものではなく、様々な変形が可能である。
【符号の説明】
【００７３】
１ 分岐予測器
１０ 第１分岐予測部（ベース予測器）
２０ 記憶部（ＭＢＢ）
３０ 第２分岐予測部（ＬＨＢＰ）
４０ セレクタ
【技術分野】
【０００１】
本発明は、分岐予測器及びプロセッサに関するものである。
【背景技術】
【０００２】
分岐予測は、分岐命令を投機的に実行することにより制御依存を回避する技術であり、高精度の予測を行うことにより、大幅な性能向上が実現される。しかし、分岐予測に失敗したときは、分岐命令以降の実行命令をフラッシュし、正しい分岐先命令を新たにフェッチするため性能が低下する。これは分岐予測ミスペナルティと呼ばれている。
【０００３】
近年の高性能プロセッサでは、パイプライン段数の増加、命令発行幅の増加により高い命令レベル並列性を抽出しており、これに伴い分岐予測ミスペナルティは増加傾向にある。このため、分岐予測精度の更なる向上はプロセッサの性能向上にとって不可欠な課題である。
【０００４】
分岐予測ミスペナルティを減少させるため、様々な分岐予測器が提案されている。１９８１年に最初に提案されたＢｉｍｏｄａｌ予測器（非特許文献１参照）では、各分岐命令の挙動を２ｂｉｔ飽和カウンタで保持し、その値に基づき分岐方向を予測する。飽和型カウンタはＰＨＴ（Pattern History Table）として構成され、分岐命令アドレスの下位ビットをインデクスとしてアクセスされる。
【０００５】
現在多くのプロセッサで用いられているＧｓｈａｒｅ予測器（非特許文献２参照）は、分岐命令のグローバル履歴と分岐命令アドレスの排他的論理和をインデクスとしてＰＨＴにアクセスして分岐予測を行う予測器である。これは分岐命令のグローバル履歴により分岐命令間の相関を利用した予測方法である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】J.E.Smith. "A Study of Branch Prediction Strategies", ISCA 1981, pp.135-148, 1981
【非特許文献２】S.McFarling. "Combining Branch Predictors", Technical report TN-36, Digital Western Research Laboratory, 1993
【発明の概要】
【発明が解決しようとする課題】
【０００７】
これらの分岐予測器における予測ミスの主要な要因として破壊的競合がある。これは、図９に示すように、異なる分岐命令が同じＰＨＴのエントリに分岐結果を登録することにより生じる競合である。現在の主流の分岐予測器では、Ｇｓｈａｒｅ予測器のように、分岐命令アドレスとグローバル分岐履歴を用いてＰＨＴをアクセスするため、破壊的競合はより複雑な様相となり、本質的には避けられない。
【０００８】
そこで、本発明は、破壊的競合を緩和して分岐予測の精度を向上させることを目的とする。
【課題を解決するための手段】
【０００９】
（１）本発明は、分岐命令の分岐正否の予測を行う第１分岐予測部と、前記第１分岐予測部による分岐予測ミスの数が閾値に達した分岐命令を記憶する記憶部と、前記記憶部に記憶された分岐命令それぞれについて個別に分岐正否の予測を行う第２分岐予測部と、を備え、予測の対象となる分岐命令が前記記憶部に記憶されている場合には、前記第２分岐予測部による予測を行うことを特徴とする分岐予測器である。
【００１０】
（２）前記記憶部は、前記記憶部に記憶された分岐命令それぞれについて、前記第１分岐予測部と比較した前記第２分岐予測部による予測の有効性を示す有効性情報を記憶し、前記有効性情報に基づいて前記第２分岐予測部による予測が有効でないと判断された分岐命令を、前記記憶部から削除するのが好ましい。
【００１１】
（３）前記記憶部は、前記記憶部に記憶されている分岐命令の数が、記憶可能な分岐命令の数の上限に達した場合には、ＬＲＵロジックに基づいて、前記記憶部に記憶されている分岐命令のうち最も最近使用されていない分岐命令に、前記第１分岐予測部による分岐予測ミスの数が前記閾値に達した新たな分岐命令を上書きすることで、前記新たな分岐命令を記憶し、前記ＬＲＵロジックでは、前記第２分岐予測部が正しく予測できた場合に、分岐命令が使用されたものとみなすのが好ましい。
【００１２】
（４）前記ＬＲＵロジックでは、第２分岐予測部が正しく予測でき、かつ、第１分岐予測部が正しく予測できなかった場合に、分岐命令が使用されたものとみなすのが好ましい。
【００１３】
（５）前記第１分岐予測部による分岐予測ミスの数を分岐命令毎にカウントするカウンタを備え、前記カウンタの値が前記閾値に達した分岐命令が前記記憶部に記憶されるとともに、前記カウンタの値が前記閾値に達すると前記カウンタがリセットされるのが好ましい。
【００１４】
（６）前記記憶部は、前記記憶部に記憶された分岐命令それぞれの分岐結果の履歴を示す履歴情報を記憶するのが好ましい。
【００１５】
（７）前記第２分岐予測部は、分岐命令の分岐結果の履歴に基づいて分岐予測を行うためのＰＨＴ（Pattern History Table）を、前記記憶部に記憶された分岐命令毎に有しているのが好ましい。
【００１６】
（８）前記第１分岐予測部の予測結果と前記第２分岐予測部の予測結果とを選択的に出力するセレクタを備えているのが好ましい。
【００１７】
（９）前記記憶部に記憶された分岐命令それぞれについて、前記第２分岐予想部による予測の信頼性を示す信頼性情報を記憶する信頼性情報記憶部を備え、前記信頼性情報は、前記第２分岐予測器の予測が成功した数に基づく情報であり、前記セレクタは、前記信頼性情報に基づいて、前記第１分岐予測部の予測結果及び前記第２分岐予測部の予測結果のいずれを出力するかを決定するのが好ましい。
【００１８】
（１０）他の観点からみた本発明は、前記（１）〜（９）のいずれか１項に記載の分岐予測器によって分岐命令の分岐予測を行うプロセッサである。
【発明の効果】
【００１９】
本発明によれば、破壊的競合を緩和して分岐予測の精度を向上させることができる。
【図面の簡単な説明】
【００２０】
【図１】（ａ）はＣｏｍｂｉｎｉｎｇ予測器によける予測ミスの偏りを示し、（ｂ）はＢｉｍｏｄｅ予測器における予測ミスの偏りを示す図である。
【図２】分岐予測器のブロック図である。
【図３】Ｃｏｍｂｉｎｉｎｇにおける予測ミス削減率を示す図である。
【図４】Ｂｉｍｏｄｅにおける予測ミス削減率を示す図である。
【図５】Ｂｉｍｏｄｅ−Ｐｌｕｓにおける予測ミス削減率を示す図である。
【図６】Ａｇｒｅｅにおける予測ミス削減率を示す図である。
【図７】Ｈｙｂｒｉｄにおける予測ミス削減率を示す図である。
【図８】ＭＰＫＩ結果を示す表である。
【図９】複数の命令が同一のＰＨＴエントリにアクセスすることを示す図である。
【発明を実施するための形態】
【００２１】
以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。
【００２２】
［１．予測ミスの偏り］
本発明者らは、分岐命令の予測ミスに偏りがあることを新たに見出した。ここでは、従来の分岐予測器において、予測ミスが少数の分岐命令に集中して発生することを示す。
【００２３】
予測ミスの偏りの度合いを評価するため、まず、SimpleScalar Tool Set（D.Burger, T.M.Austin. "The SimpleScalar ToolSet , Version2.0", Technical Report, University of Wisconsin-Madison Computer Sciences Dpt, July 1997）を用いて、Combining予測器とBimode予測器を実行して評価を行う。ベンチマークには、SPECint2000（The Standard Performance Evaluation Corporation)から、bzip, gcc, gzip, mcf, parser, twolf, vpr, vortexの８本を使用する。
【００２４】
評価に用いたプロセッサの使用を表１に示す。命令セットは、SimpleScalar PISAを用いる。
【表１】
【００２５】
これらのベンチマークにおいて、最も多く予測ミスが発生する上位８個と上位１６個の分岐命令を抽出し、これらの予測ミスが全体の予測ミスに占める割合を調べる。
【００２６】
図１（ａ）は、Ｃｏｍｂｉｎｉｎｇ予測器において、予測ミスが最も多い上位８個と１６個の分岐命令の予測ミスが全体の予測ミスに占める割合を示し、図１（ｂ）は、Ｂｉｍｏｄｅ予測器において、予測ミスが最も多い上位８個と１６個の分岐命令の予測ミスが全体の予測ミスに占める割合を示す。
なお、予測ミスはプログラムの実行状況に応じて変化するため、調べ方については、２０Ｍ命令ごとに最もミスの多い上位８個（あるいは１６個）の分岐命令を抽出し、それらの予測ミスが全体の予測ミスに占める割合を調べ、これを５回繰り返して１００Ｍ命令まで評価する。
【００２７】
予測器のハードウェア量は、８ＫＢ、１６ＫＢ、３２ＫＢの３種類について評価を行う。非特許文献２では、Gshare予測器のサイズがBimode予測器のサイズの２倍になるとき、より良い性能が得られると報告されている。そのため、Combining予測器では、Bimode予測器とSelectorのエントリ数を８Ｋ，１６Ｋ，３２Ｋ、Gshare予測器のエントリ数を１６Ｋ，３２Ｋ，６４Ｋと設定する。Bimode予測器については、Gshare予測器のエントリ数を８Ｋ，１６Ｋ，３２Ｋとし、ChoicePHTのエントリ数を１６Ｋ，３２Ｋ，６４Ｋと設定する。
【００２８】
図１（ａ）（ｂ）横軸は実行命令数であり、縦軸はミスの多い分岐命令の予測ミスが全体の予測ミスに占める割合である。また、「８−８ＫＢ」「８−１６Ｋ」「８−３２Ｋ」は、それぞれ、予測器のハードウェア量が８ＫＢ、１６ＫＢ、３２ＫＢである場合について、予測ミスが最も多い上位８個の分岐命令の予測ミスが全体の予測ミスに占める割合を示している。「１６−８ＫＢ」「１６−１６Ｋ」「１６−３２Ｋ」は、それぞれ、予測器のハードウェア量が８ＫＢ、１６ＫＢ、３２ＫＢである場合について、予測ミスが最も多い上位８個の分岐命令の予測ミスが全体の予測ミスに占める割合を示している。
【００２９】
図１（ａ）（ｂ）より、Combining予測器とBimode予測器では、８個の分岐命令の予測ミスが、全体のミスの７０％以上を占めることが分かる。さらに、１６個の分岐命令の予測ミスが、全体のミスの８０％以上を占めることが分かる。
【００３０】
［２．実施形態に係る分岐予測器及びプロセッサ］
本実施形態に係るプロセッサは、スーパースカラプロセッサであり、分岐予測器１を備えている。図１は、プロセッサが有する分岐予測器１を示している。この分岐予測器１は、予測ミスが少数の分岐命令に偏るという特性を利用したものである。つまり、予測ミスの多い特定の分岐命令については、破壊的競合が生じないように、予測ミスの多い特定の分岐命令毎の履歴（ローカル履歴）を用いて分岐予測を行う。
【００３１】
図１に示すように、分岐予測器１は、第１分岐予測部であるベース予測器（Base Predictor）１０と、ＭＢＰ（Miss Bias Predictor）２０と、予測ミスの多い特定の分岐命令について分岐予測を行う第２分岐予測部であるＬＨＢＰ（Local History Branch predictor）３０と、セレクタ４０と、を備えている。
【００３２】
［２．１ ベース予測器（第１予測器）の構成］
ベース予測器１０は、分岐予測の必要な全ての分岐命令について分岐予測を行う。
ベース予測器（第１分岐予測部）１０としては、分岐命令の分岐成否の予測（分岐予測）を行う従来の分岐予測器が用いられている。ベース予測器１０としては、例えば、Combining予測器、Bimode予測器、Bimod-Plus予測器、Agree予測器、Hybrid予測器、Gshare予測器など、破壊的競合の起こり得る予測器を採用することができる。
ベース予測器１０として、ＧＢＨ（Global Branch History;グローバル分岐履歴）を用いる予測器を採用した場合、ベース予測器１０には、ＧＢＨが与えられ、プログラムカウンタ（ＰＣ）２が示すアドレスの分岐命令について、分岐予測の結果を出力し、セレクタ３０に与える。
【００３３】
［２．２ ＭＢＰの構成］
ＭＢＰ２０は、分岐予測ミスの多い分岐命令を検出して、その分岐命令を、ローカル分岐履歴などの情報とともに記憶するためのものである。ＭＢＰ２０は、拡張されたＢＴＢ（Branch Target Buffer）機構であるＥＢＴＢ（Extended BTB）２１と、予測ミスの多い分岐命令を記憶するＭＢＢ（Miss Bias Buffer）２２と、を有している。
【００３４】
［２．２．１ ＥＢＴＢの構成］
ＥＢＴＢの基礎となるＢＴＢ機構は、分岐先予測（Branch Target Prediction）のために予測アドレス（Target Address）を得るための機構であり、分岐命令のアドレスの一部を格納するＴａｇと、各分岐命令のアドレスに対応する予測アドレス（分岐アドレス）を格納するＴａｄｄｒと、を有している。
【００３５】
ＥＢＴＢ２１は、上記ＢＴＢ機構を利用して、分岐予測ミスの多い分岐命令を検出するための検出部として機能する。
ＢＴＢを拡張したＥＢＴＢ２１は、従来のＢＴＢと同じように、Ｔａｇ２１ａと、Ｔａｄｄｒ２１ｃと、を備え、さらに、各エントリには、飽和カウンタによって構成されたＭＣＴ（Miss Counter）２１ｂを備えている。
【００３６】
分岐命令のアドレスの下位ビットｉ〜０に対応するエントリのＴａｇ２１ａには、当該分岐命令のｎビットアドレスの上位ビットｎ−１〜ｉ＋１が格納される。プログラムカウンタ（ＰＣ）２から、分岐命令のアドレスの下位ビットｉ〜０が、ＥＢＴＢのエントリに与えられると、分岐命令のアドレスの下位ビットｉ〜０に対応するエントリのＴａｇ２１ａに格納されているビット列が、判定部２１ｄに出力される。判定部２１ｄは、プログラムカウンタ２から、当該分岐命令のアドレスの上位ビットｎ−１〜ｉ＋１のビット列も与えられる。
【００３７】
判定部２１ｄは、ＥＢＴＢ２１から出力されたビット列とプログラムカウンタ２から出力されたビット列とが一致するか否かの判定を行い、一致の場合は、ヒットとなる。なお、ＥＢＴＢ２を通常のＢＴＢとしても用いる場合、判定部２１の結果がヒットであると、分岐命令のアドレスの下位ビットｉ〜０に対応するエントリのＴａｄｄｒ２１ｃが予測アドレスとして出力される。
【００３８】
ＭＣＴ２１ｂは、ベース予測器１０の分岐正否の分岐予測ミスの数カウントするためのものである。ＭＣＴ２１ｂは、ＥＢＴＢ２１の各エントリに設けられているため、ＥＢＴＢ２１では、Ｔａｇ２１ａにアドレス（の一部）が格納されている分岐命令毎に、分岐予測ミスの数がカウントされることになる。
なお、ＭＣＴ２１ｂのサイズは、例えば、４ｂｉｔ程度あれば足りる。
また、ＥＢＴＢ２１のエントリ数は、２ｉ個である。
【００３９】
［２．２．２ ＭＢＢ（記憶部）の構成］
予測ミスの多発する分岐命令を格納するＭＢＢ（記憶部）２２は、Ａｄｄｒ２２ａと、ＬＨ２２ｂと、Ｕ２２ｃと、ＦＲ２２ｄと、を備えている。
Ａｄｄｒ２２ａは、予測ミスの多発する分岐命令のアドレス（ｎビット）が格納される領域であり、分岐命令アドレスの格納により、分岐命令が記憶されていることになる。
ＬＨ（Local branch History）２２ｂは、分岐命令のローカル分岐履歴を記憶する領域であり、ｍビットのシフトレジスタによって構成され、過去ｍ回の分岐正否を各ビットの０／１で記憶する。
【００４０】
Ｕ（Use bit）２２ｃは、該当するエントリが使用されているかどうかを示すビットであり、１が使用中を示し、０が未使用を示す。
ＦＲ（Trace Failure Rate）２２ｄは、７ｂｉｔの飽和カウンタであり、第２分岐予測部であるＬＨＢＰ３０の分岐予測ミスの数と、第１分岐予測部であるベース予測器１０の分岐予測ミスの数と、の差を有効性情報として保持する。
【００４１】
有効性情報は、ベース予測器（第１分岐予測部）１０と比較したＬＨＢＰ（第２分岐予測部）３０の有効性を示す情報である。ＭＢＢ２２に（アドレスが）記憶されている分岐命令それぞれの有効性情報に基づいて、有効でないと判断された分岐命令は、ＭＢＢ２２から削除される（Ｕ２２ｃが未使用を示す０にセットされる）。
【００４２】
ＭＢＢ２２のエントリ数が多いほど、分岐予測ミスの多発する分岐命令（のアドレス）を、ＭＢＢ２２に多く格納することができる。ただし、本発明者らの実験の結果、ＭＢＢ２２のエントリ数を多くしても、分岐予測ミスの減少は僅かであったことから、ＭＢＢ２２のエントリ数（ＭＢＢ２２に記憶できる分岐命令数）は、８個又は１６個程度でよい。
【００４３】
［２．３ ＬＨＢＰ（第２分岐予測部）の構成］
第２分岐予測部であるＬＨＢＰ３０は、ベース予測器１０にて分岐予測がなされる分岐命令の一部について、分岐成否の予測を行う。具体的には、ＬＨＢＰ３０は、ＭＢＢ２２に記憶されている分岐命令（ＥＢＴＢ２１によって分岐予測ミスが多いことが検出された分岐命令）について、分岐予測を行う。つまり、ＬＨＢＰ３０にて分岐予測がなされる分岐命令につては、ベース予測器１０とＬＨＢＰ３０の双方で分岐予測がなされることになる。
【００４４】
ＬＨＢＰ３０は、ＭＢＢ２２に記憶されている分岐命令毎に個別の分岐履歴（ローカル分岐履歴）に基づいて分岐予測を行う複数のＬＰＨＴ（Local Pattern History Table）３１，３２，・・・を備えている。
【００４５】
ＬＰＨＴ３１，３２，・・・は、それぞれ、分岐命令の分岐結果の履歴（ローカル分岐履歴）に基づいて分岐予測を行うためのＰＨＴ（Pattern History Table）として構成されている。
ＬＰＨＴ３１，３２，・・・は、それぞれ、ＮＴＣＴ（2bit Taken Not Taken saturating CounTer）３１ａ，３２ａと、ＣＦ（ConFidence）３１ｂ，３２ｂと、を有している。
【００４６】
ＮＴＣＴ３１ａ，３２ａは、一般的なＰＨＴと同様に、２ビット飽和カウンタによって構成され、分岐の成否について予測される４つの状態（Strongly NotTaken, Weakly NotTaken, Weakly Taken, Strongly Taken）を保持している。ＮＴＣＴ３１ａ，３２ａは、対応する分岐命令のみの分岐結果によって、インクリメント又はデクリメントされ、他の分岐命令の分岐結果によってはインクリメント又はデクリメントされない。
【００４７】
ＣＦ３１ｂ，３２ｂは、同一エントリのＮＴＣＴ３１ａ，３２ａによる予測の信頼性を示す信頼性情報を記憶する領域（信頼性情報記憶部）である。ＣＦ３１ａ，３２ａは、２ビットMiss Resetting Counterとして構成されており、同一エントリのＮＴＣＴ３１ａ，３２ａによる予測が成功した場合には、ＣＦがインクリメントされ、予測ミスの場合にはリセットされる。
【００４８】
ＬＰＨＴ３１，３２・・・の個数は、ＭＢＢ２２のエントリ数（分岐予測ミスの多い分岐命令を記憶可能な数）と同じである。例えば、ＭＢＢ２２の一番目のエントリの分岐命令は、「ＬＰＨＴ１」３１を用いて分岐予測がなされる。また、ＭＢＢ２２の二番目のエントリの分岐命令は、「ＬＰＨＴ２」３２を用いて分岐予測がなされる。これにより、ＬＨＢＰ２０においては、ＭＢＢ２２に格納されている分岐命令同士での破壊的競合は生じない。
また、ＭＢＢ２２に格納されている分岐命令の数は、ベース予測器（第１分岐予測部）１０によって分岐予測がなされる分岐命令全体のうちのごく一部であるから、ＬＨＢＰ（第２分岐予測部）３０を別途も受けても、ハードウェア量の増加は少ない。
【００４９】
ＬＰＨＴ３１，３２・・・のエントリ数は、使用する分岐履歴（ローカル分岐履歴）の長さにより決まる。すなわち、ＬＰＨＴ３１，３２・・・は、それぞれ、分岐命令のローカル分岐履歴を記憶するＬＨ２２ｂのビット数ｍに対して、２ｍのエントリ数を持つ。ＬＰＨＴのエントリ数は、例えば、５１２に設定することができる。
【００５０】
［２．４ ＭＢＰによる予測ミスの多発する分岐命令の発見に関する処理］
［２．４．１ ＥＢＴＢに関する動作（予測ミスの多発する分岐命令の発見）］
ＭＢＰ２０は、岐命令がコミットされるときに、分岐命令のアドレスを用いてＥＢＴＢ２１の検索を行う。つまり、分岐命令が実行されてベース分岐予測器１０による分岐正否の結果が判明し、コミット状態になると、プログラムカウンタ２が示す当該分岐命令のアドレスを用いて、ＥＢＴＢ２１を検索する。
ＥＢＴＢ２１の検索の結果、検索対象の分岐命令アドレスがＴａｇ２１ａに格納されており、判定部２１ｄの判定結果がヒットになり、かつ、当該分岐命令に対するベース予測器１０による分岐予測が予測ミスであった場合には、対応するＭＣＴ２１ｂがインクリメントされる。なお、判定部２１ｄの判定結果がヒットになっても、予測ミスでない場合は、対応するＭＣＴ２１ｂは変化しない。
【００５１】
ＥＢＴＢ２１の検索の結果、検索対象の分岐命令アドレスがＴａｇ２１ａに格納されておらず、判定部２１ｄの判定結果がヒットにならない場合は、従来のＢＴＢと同じように、Ｔａｇ２１ａの更新を行い、当該分岐命令に対するベース予測器１０による分岐予測が予測ミスであった場合には、ＭＣＴを１にセットし、予測成功であった場合には、ＭＣＴを０にセットする。
このようにして、ＥＢＴＢ２１には、予測ミスの生じた分岐命令と、それぞれの分岐命令の予測ミスの数が保持される。
【００５２】
いずれかのＥＢＴＢエントリのＭＣＴ２１ｂが第１閾値に達すると、当該エントリの分岐命令に予測ミスが多発しているものとみなす。このようにして、ＥＢＴＢ２１は、予測ミスの多い分岐命令を検出することができる。
【００５３】
［２．４．２ ＭＢＢへの登録］
ＭＣＴ２１ｂが第１閾値に達した分岐命令は、そのアドレスが、ＭＢＢ２２のＡｄｄｒ２２ａに登録される。そして、該当するＥＢＴＢ２１のエントリのＭＣＴ２１ｂがリセットされる。第１閾値に一旦達した分岐命令のＭＣＴ２１ｂがリセットされることで、当該分岐命令の予測ミス数が再度カウント可能となり、当該分岐命令が、再度、ＭＢＢ２２に登録される機会が得られ易くなる。
【００５４】
ＭＢＢ２２への登録は、以下のように行われる。まず、登録しようとした分岐命令のアドレスが、ＭＢＢ２２のＡｄｄｒ２２ａに存在するかどうかをチェックされる。このアドレスがＭＢＢ２２に存在しない場合には、Ｕ２２ｃが０（未使用）のエントリが存在するならば、そのエントリに、そのアドレスを登録し、Ｕ２２ｃを１（使用）にする。
【００５５】
もし、ＭＢＢ２２のＵ２２ｃがすべて１（使用）の場合、すなわち、ＭＢＢ２２に記憶されている分岐命令の数が、ＭＢＢ２２に記憶可能な分岐命令の数（例えば、８個又は１６個）の上限に達している場合、ＭＢＢ２２は、ＬＲＵ（Least Recently Used）ロジックを利用して、最も最近使用されていないエントリを選択し、そのエントリのＡｄｄｒ２２ａに、そのアドレスを上書き登録する。また、そのエントリのＦＲ２２ｄもリセットされる。
【００５６】
なお、本実施形態では、上記ＬＲＵロジックにおいては、ＬＨＢＰ（第２分岐予測部）３０が正しく分岐予測でき、かつ、ベース予測器（第１分岐予測部）１０が正しく予測できなかった場合に、分岐命令が使用されたものとみなす。
分岐命令が単に実行された場合に使用されたものとみなすのではなく、ＬＨＢＰ（第２分岐予測部）３０が正しく分岐予測できた場合に、分岐命令が使用されたものとみなすことで、分岐予測ミスであった分岐命令は、ＭＢＢ２２から削除され易くなる。
また、ベース予測器（第１分岐予測部）１０が正しく予測できなかった場合であることも使用の条件に加えることで、ベース予測器１０の方が有用である分岐命令が、ＭＢＢ２２から削除され易くなる。
【００５７】
［２．４．３ ＭＢＢの更新］
分岐命令がコミットされるとき、当該分岐命令が既にＭＢＢ２２に登録されているならば、ＭＢＢ２２の更新が行われる。
当該分岐命令に対応するエントリのＬＨ２２ｂについては、ローカル履歴が更新される。つまり、シフトレジスタからなるＬＨ２２ｂに対して、当該分岐命令の実行結果（分岐正否の結果）としての０／１の入力によるシフトがなされる。
【００５８】
ＦＲ２２ｄの更新については、ＬＨＢＰ（第２分岐予測部）３０での予測が失敗し、かつ、ベース予測器（第１分岐予測部）１０の予測が成功の場合は、ＦＲ２２ｄがインクリメントされる。一方、ＬＨＢＰ３０での予想が成功、かつ、ベース予測器１０の予測が失敗の場合は、デクリメントする。これにより、ＦＲ２２ｄには、ベース予測器１０と比較したＬＨＢＰ３０による予測の有効性情報として、ベース予測器１０とＬＨＢＰ３０の予測の差を格納できる。
【００５９】
ＦＲ２２ｄの値が、第２閾値になると、ＬＨＢＰ３０による予測ミスが、ベース予測器１０よりも多く発生するために、ＬＨＢＰ３０による予測が有効でないと判断し、ＭＢＢ２２は、当該エントリにおける各領域２２ａ，２２ｂ，２２ｃ，２２ｄをリセットする。これにより、ＬＨＢＰ３０による予測が有効でないと判断された分岐命令が、ＭＢＢ２２から削除される。
【００６０】
［２．４．４ ＬＰＨＴの更新］
分岐命令がコミットされるときに、当該分岐命令のアドレスを用いて、ＭＢＢ２２を検索する。当該分岐命令のアドレスが、ＭＢＢ２２のいずれかのエントリのＡｄｄｒ２２ａに存在する場合には、そのＡｄｄｒ２２ａと同一エントリにあるＬＨ２２ｂのローカル分岐履歴を利用して、ＬＰＨＴを更新する。
具体的には、当該分岐命令のアドレスに対応するＡｄｄｒ２２ａと同一エントリにあるＬＨ２２ｂが示すローカル履歴（ｍｂｉｔのビット列）に対応するＬＰＨＴエントリのＮＴＣＴ３２ａを、当該ＬＨ２２ｂが占めるローカル履歴の情報で更新する。
さらに、ＣＦ３１ｂ、３２ｂの更新も行われる。すなわち、予測が成功した場合はインクリメントされ、予測ミスの場合はリセットされる。
【００６１】
［２．５ ＬＨＢＰによる分岐予測］
分岐命令がフェッチされるときに、フェッチされた分岐命令のアドレスを用いて、ＭＢＢ２２を検索する。当該アドレスが、ＭＢＢ２２のＡｄｄｒ２２ａに存在する場合には、そのＡｄｄｒ２２ａと同一エントリにあるＬＨ２２ｂに対応するＬＰＨＴのエントリのＮＴＣＴとＣＦの値を得る。
得られたＮＴＣＴを用いて、フェッチされた分岐命令のＬＨＢＰ（第２分岐予測部）３０による分岐予測結果（Taken 又は Not Taken）が出力され、ＣＦの値とともにセレクタ４０の取得部４１に与えられる。
【００６２】
取得部４１は、ＬＨＢＰ３０の分岐予測結果を、セレクタ本体４２に与える。セレクタ本体４２には、フェッチされた当該分岐命令のベース予測器（第１分岐予測部）１０による分岐予測結果も与えられる。
セレクタ本体４２は、取得部４１からＣＦの値を得て、ベース予測器１０による分岐予測結果とＬＨＢＰ３０による分岐予測結果とを選択的に出力する。具体的には、セレクタ本体４２は、ＣＦ（信頼性情報）の値が第３閾値に達している場合に、ＬＨＢＰ３０の分岐予測結果を出力し、その他の場合はベース予測器１０の分岐予測結果を、出力する。
【００６３】
ＣＦの値は、予測ミスがあるとリセットされるため、ＣＦの値が第３閾値に達するまで連続して予測に成功しないと、ＬＨＢＰ３０の予測結果は使用されず、ベース予測器１０による予測結果が使用される。これにより、ローカル履歴のみを用いたＬＨＢＰ３０による分岐予測の誤動作を緩和することができる。
【００６４】
［３．評価］
［３．１ 予測ミスの削減率の評価］
ベース予測器１０として、Combining予測器、Bimode予測器、Bimode-Plus予測器、Agree予測器、Hybrid予測器の５種類を用いる。ベース予測器１０であるCombining、Bimode、Bimode-Plus、Agreeのサイズを、８ＫＢ、１６ＫＢ，３２ＫＢ，６４ＫＢの４種類とし、Hybrid予測器のサイズは、１０．５ＫＢ，１７．７５ＫＢ，３０ＫＢ，６０．５ＫＢと設定する。
【００６５】
図３〜図７は、それぞれ、分岐予測器１における予測ミスの削減率の評価結果を、ベンチマーク毎に示している。図３〜図７において、横軸はベンチマークであり、縦軸は、本実施形態に係る分岐予測器１の、ベース分岐予測器に対する予測ミス削減率である。
なお、ベンチマークとしては、CommBenchから、drr, reed_dec, reed_enc, rtr, zip_enc の５種類を用い、SPECint2000から、bzip, gcc, gzip, mcf, parser, twolf, vortex, vpr の８種類を用いた。
【００６６】
図３〜図５に示すように、ベース予測器１０として、Combining, Bimode, Bimode-Plusを用いた分岐予測器１は、SPECint2000において、最大４０％以上、平均１０％以上の予測ミスを減らすことができ、CommBenchにおいて、最大３０％、平均６％以上の予測ミスを減らすことができた。
図６に示すように、ベース予測器１０として、Agreeを用いた分岐予測器１は、SPECint2000において、最大２３％以上、平均１０％以上の予測ミスを減らすことができ、CommBenchにおいて、最大３０％、平均６％程度の予測ミスを減らすことができた。
図７に示すように、ベース予測器１０として、Hybridを用いた分岐予測器１は、SPECint2000において、最大４５％以上、平均７％以上の予測ミスを減らすことができ、CommBenchにおいて、最大２０％、平均３％程度の予測ミスを減らすことができた。
【００６７】
［３．２ ハードウェア規模の検討］
実施形態に係る分岐予測器１のうち、ＥＢＴＢ２１に関しては、ＢＴＢが持つ検索ポートを利用するために、ＢＴＢを拡張したＥＢＴＢ２１には、検索用のポートを追加する必要がない。また、ＥＢＴＢ２１に含まれるＭＣＴ２１ｂは４ｂｉｔのため、ＥＢＴＢ２１のエントリ数が、６４個であれば、ＢＴＢを拡張してＥＢＴＢ２１にするために必要なメモリ量は、１ＫＢである。
【００６８】
ＭＢＢ２２について、Ａｄｄｒ２２ａが３２ｂｉｔ、ＬＨ２２ｂが９ｂｉｔ、Ｕ２２ｃが１ｂｉｔ、ＦＲ２２ｄが７ｂｉｔであると、各エントリそれぞれについての語長は４９ビットとなる。したがって、ＭＢＢ２２のエントリ数を８とすると、ＭＢＢ２２のために必要なメモリ量は３９２ｂｉｔのＣＡＭとなる。
【００６９】
ＬＰＨＴ３１，３２，・・・については、個数が８個、それぞれのエントリ数が５１２、ＮＴＣＴが２ｂｉｔ、ＣＦが２ｂｉｔとすると、語長は４ｂｉｔとなり、必要なメモリ量は２ＫＢである。
【００７０】
したがって、本実施形態に係る分岐予測器１は、従来の分岐予測器（ベース予測器のみ）に対して、３ＫＢ程度、ハードウェア量が増加する。
【００７１】
図８は、予測器のサイズとそれらのＭＰＫＩ（Miss-prediction Per Kilo Instruction）の関係を示す。予測器の各欄は、対応するサイズでのＭＰＫＩである。図８に示すように、例えば、８ＫＢのCombining予測器と、８ＫＢのCombining予測器をベース予測器１０として有する分岐予測器１とを比較すると、ＭＰＫＩの値が低下している。８ＫＢのCombining予測器をベース予測器１０として有する分岐予測器１は、６４ＫＢのCombining予測器と同等以上の性能になる。これは、Bimode、Bimode-Plus、Agreeについても同様である。
これらのことより、本実施形態の分岐予測器１は、従来の分岐予測器のエントリー数の増加以上の効果が得られる。
【００７２】
［４．付記］
なお、上記において開示した事項は、例示であって、本発明を限定するものではなく、様々な変形が可能である。
【符号の説明】
【００７３】
１ 分岐予測器
１０ 第１分岐予測部（ベース予測器）
２０ 記憶部（ＭＢＢ）
３０ 第２分岐予測部（ＬＨＢＰ）
４０ セレクタ
【特許請求の範囲】
【請求項１】
分岐命令の分岐正否の予測を行う第１分岐予測部と、
前記第１分岐予測部による分岐予測ミスの数が閾値に達した分岐命令を記憶する記憶部と、
前記記憶部に記憶された分岐命令それぞれについて個別に分岐正否の予測を行う第２分岐予測部と、
を備え、
予測の対象となる分岐命令が前記記憶部に記憶されている場合には、前記第２分岐予測部による予測を行う
ことを特徴とする分岐予測器。
【請求項２】
前記記憶部は、前記記憶部に記憶された分岐命令それぞれについて、前記第１分岐予測部と比較した前記第２分岐予測部による予測の有効性を示す有効性情報を記憶し、
前記有効性情報に基づいて前記第２分岐予測部による予測が有効でないと判断された分岐命令を、前記記憶部から削除する
請求項１記載の分岐予測器。
【請求項３】
前記記憶部は、前記記憶部に記憶されている分岐命令の数が、記憶可能な分岐命令の数の上限に達した場合には、ＬＲＵロジックに基づいて、前記記憶部に記憶されている分岐命令のうち最も最近使用されていない分岐命令に、前記第１分岐予測部による分岐予測ミスの数が前記閾値に達した新たな分岐命令を上書きすることで、前記新たな分岐命令を記憶し、
前記ＬＲＵロジックでは、前記第２分岐予測部が正しく予測できた場合に、分岐命令が使用されたものとみなす
請求項１又は２記載の分岐予測器。
【請求項４】
前記ＬＲＵロジックでは、第２分岐予測部が正しく予測でき、かつ、第１分岐予測部が正しく予測できなかった場合に、分岐命令が使用されたものとみなす
請求項３記載の分岐予測器。
【請求項５】
前記第１分岐予測部による分岐予測ミスの数を分岐命令毎にカウントするカウンタを備え、
前記カウンタの値が前記閾値に達した分岐命令が前記記憶部に記憶されるとともに、前記カウンタの値が前記閾値に達すると前記カウンタがリセットされる
請求項１〜４のいずれか１項に記載の分岐予測器。
【請求項６】
前記記憶部は、前記記憶部に記憶された分岐命令それぞれの分岐結果の履歴を示す履歴情報を記憶する
請求項１〜５のいずれか１項に記載の分岐予測器。
【請求項７】
前記第２分岐予測部は、分岐命令の分岐結果の履歴に基づいて分岐予測を行うためのＰＨＴ（Pattern History Table）を、前記記憶部に記憶された分岐命令毎に有している
請求項１〜６のいずれか１項に記載の分岐予測器。
【請求項８】
前記第１分岐予測部の予測結果と前記第２分岐予測部の予測結果とを選択的に出力するセレクタを備えている
請求項１〜７のいずれか１項に記載の分岐予測器。
【請求項９】
前記記憶部に記憶された分岐命令それぞれについて、前記第２分岐予想部による予測の信頼性を示す信頼性情報を記憶する信頼性情報記憶部を備え、
前記信頼性情報は、前記第２分岐予測器の予測が成功した数に基づく情報であり、
前記セレクタは、前記信頼性情報に基づいて、前記第１分岐予測部の予測結果及び前記第２分岐予測部の予測結果のいずれを出力するかを決定する
請求項１〜８のいずれか１項に記載の分岐予測器。
【請求項１０】
請求項１〜９のいずれか１項に記載の分岐予測器によって分岐命令の分岐予測を行うプロセッサ。
【請求項１】
分岐命令の分岐正否の予測を行う第１分岐予測部と、
前記第１分岐予測部による分岐予測ミスの数が閾値に達した分岐命令を記憶する記憶部と、
前記記憶部に記憶された分岐命令それぞれについて個別に分岐正否の予測を行う第２分岐予測部と、
を備え、
予測の対象となる分岐命令が前記記憶部に記憶されている場合には、前記第２分岐予測部による予測を行う
ことを特徴とする分岐予測器。
【請求項２】
前記記憶部は、前記記憶部に記憶された分岐命令それぞれについて、前記第１分岐予測部と比較した前記第２分岐予測部による予測の有効性を示す有効性情報を記憶し、
前記有効性情報に基づいて前記第２分岐予測部による予測が有効でないと判断された分岐命令を、前記記憶部から削除する
請求項１記載の分岐予測器。
【請求項３】
前記記憶部は、前記記憶部に記憶されている分岐命令の数が、記憶可能な分岐命令の数の上限に達した場合には、ＬＲＵロジックに基づいて、前記記憶部に記憶されている分岐命令のうち最も最近使用されていない分岐命令に、前記第１分岐予測部による分岐予測ミスの数が前記閾値に達した新たな分岐命令を上書きすることで、前記新たな分岐命令を記憶し、
前記ＬＲＵロジックでは、前記第２分岐予測部が正しく予測できた場合に、分岐命令が使用されたものとみなす
請求項１又は２記載の分岐予測器。
【請求項４】
前記ＬＲＵロジックでは、第２分岐予測部が正しく予測でき、かつ、第１分岐予測部が正しく予測できなかった場合に、分岐命令が使用されたものとみなす
請求項３記載の分岐予測器。
【請求項５】
前記第１分岐予測部による分岐予測ミスの数を分岐命令毎にカウントするカウンタを備え、
前記カウンタの値が前記閾値に達した分岐命令が前記記憶部に記憶されるとともに、前記カウンタの値が前記閾値に達すると前記カウンタがリセットされる
請求項１〜４のいずれか１項に記載の分岐予測器。
【請求項６】
前記記憶部は、前記記憶部に記憶された分岐命令それぞれの分岐結果の履歴を示す履歴情報を記憶する
請求項１〜５のいずれか１項に記載の分岐予測器。
【請求項７】
前記第２分岐予測部は、分岐命令の分岐結果の履歴に基づいて分岐予測を行うためのＰＨＴ（Pattern History Table）を、前記記憶部に記憶された分岐命令毎に有している
請求項１〜６のいずれか１項に記載の分岐予測器。
【請求項８】
前記第１分岐予測部の予測結果と前記第２分岐予測部の予測結果とを選択的に出力するセレクタを備えている
請求項１〜７のいずれか１項に記載の分岐予測器。
【請求項９】
前記記憶部に記憶された分岐命令それぞれについて、前記第２分岐予想部による予測の信頼性を示す信頼性情報を記憶する信頼性情報記憶部を備え、
前記信頼性情報は、前記第２分岐予測器の予測が成功した数に基づく情報であり、
前記セレクタは、前記信頼性情報に基づいて、前記第１分岐予測部の予測結果及び前記第２分岐予測部の予測結果のいずれを出力するかを決定する
請求項１〜８のいずれか１項に記載の分岐予測器。
【請求項１０】
請求項１〜９のいずれか１項に記載の分岐予測器によって分岐命令の分岐予測を行うプロセッサ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１３−５８１３５（Ｐ２０１３−５８１３５Ａ）
【公開日】平成２５年３月２８日（２０１３．３．２８）
【国際特許分類】
【出願番号】特願２０１１−１９６９７３（Ｐ２０１１−１９６９７３）
【出願日】平成２３年９月９日（２０１１．９．９）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 情報処理学会 電子図書館 情報学広場のトップページ及び当該トップページから先進的計算基板システムシンポジウム２０１１のインデックスを表示させたページのプリントアウト２０１１年５月１８日掲載
【出願人】（５９３００６６３０）学校法人立命館 (359)
【Ｆターム（参考）】
【公開日】平成２５年３月２８日（２０１３．３．２８）
【国際特許分類】
【出願日】平成２３年９月９日（２０１１．９．９）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 情報処理学会 電子図書館 情報学広場のトップページ及び当該トップページから先進的計算基板システムシンポジウム２０１１のインデックスを表示させたページのプリントアウト２０１１年５月１８日掲載
【出願人】（５９３００６６３０）学校法人立命館 (359)
【Ｆターム（参考）】
[ Back to top ]