"分岐命令の分岐正否の予測を行う第1分岐予測部と、前記第1分岐予測部による分岐予測ミスの数が閾値に達した分岐命令を記憶する記憶部と、前記記憶部に記憶された分岐命令それぞれについて個別に分岐正否の予測を行う第2分岐予測部と、を備え、予測の対象となる分岐命令が前記記憶部に記憶されている場合には、前記第2分岐予測部による予測を行うことを特徴とする分岐予測器。前記記憶部は、前記記憶部に記憶された分岐命令それぞれについて、前記第1分岐予測部と比較した前記第2分岐予測部による予測の有効性を示す有効性情報を記憶し、前記有効性情報に基づいて前記第2分岐予測部による予測が有効でないと判断された分岐命令を、前記記憶部から削除する請求項1記載の分岐予測器。前記記憶部は、前記記憶部に記憶されている分岐命令の数が、記憶可能な分岐命令の数の上限に達した場合には、LRUロジックに基づいて、前記記憶部に記憶されている分岐命令のうち最も最近使用されていない分岐命令に、前記第1分岐予測部による分岐予測ミスの数が前記閾値に達した新たな分岐命令を上書きすることで、前記新たな分岐命令を記憶し、前記LRUロジックでは、前記第2分岐予測部が正しく予測できた場合に、分岐命令が使用されたものとみなす請求項1又は2記載の分岐予測器。前記LRUロジックでは、第2分岐予測部が正しく予測でき、かつ、第1分岐予測部が正しく予測できなかった場合に、分岐命令が使用されたものとみなす請求項3記載の分岐予測器。前記第1分岐予測部による分岐予測ミスの数を分岐命令毎にカウントするカウンタを備え、前記カウンタの値が前記閾値に達した分岐命令が前記記憶部に記憶されるとともに、前記カウンタの値が前記閾値に達すると前記カウンタがリセットされる請求項1~4のいずれか1項に記載の分岐予測器。前記記憶部は、前記記憶部に記憶された分岐命令それぞれの分岐結果の履歴を示す履歴情報を記憶する請求項1~5のいずれか1項に記載の分岐予測器。前記第2分岐予測部は、分岐命令の分岐結果の履歴に基づいて分岐予測を行うためのPHTPatternHistoryTableを、前記記憶部に記憶された分岐命令毎に有している請求項1~6のいずれか1項に記載の分岐予測器。前記第1分岐予測部の予測結果と前記第2分岐予測部の予測結果とを選択的に出力するセレクタを備えている請求項1~7のいずれか1項に記載の分岐予測器。前記記憶部に記憶された分岐命令それぞれについて、前記第2分岐予想部による予測の信頼性を示す信頼性情報を記憶する信頼性情報記憶部を備え、前記信頼性情報は、前記第2分岐予測器の予測が成功した数に基づく情報であり、前記セレクタは、前記信頼性情報に基づいて、前記第1分岐予測部の予測結果及び前記第2分岐予測部の予測結果のいずれを出力するかを決定する請求項1~8のいずれか1項に記載の分岐予測器。請求項1~9のいずれか1項に記載の分岐予測器によって分岐命令の分岐予測を行うプロセッサ。これらの分岐予測器における予測ミスの主要な要因として破壊的競合がある。これは、図9に示すように、異なる分岐命令が同じPHTのエントリに分岐結果を登録することにより生じる競合である。現在の主流の分岐予測器では、Gshare予測器のように、分岐命令アドレスとグローバル分岐履歴を用いてPHTをアクセスするため、破壊的競合はより複雑な様相となり、本質的には避けられない。そこで、本発明は、破壊的競合を緩和して分岐予測の精度を向上させることを目的とする。1本発明は、分岐命令の分岐正否の予測を行う第1分岐予測部と、前記第1分岐予測部による分岐予測ミスの数が閾値に達した分岐命令を記憶する記憶部と、前記記憶部に記憶された分岐命令それぞれについて個別に分岐正否の予測を行う第2分岐予測部と、を備え、予測の対象となる分岐命令が前記記憶部に記憶されている場合には、前記第2分岐予測部による予測を行うことを特徴とする分岐予測器である。2前記記憶部は、前記記憶部に記憶された分岐命令それぞれについて、前記第1分岐予測部と比較した前記第2分岐予測部による予測の有効性を示す有効性情報を記憶し、前記有効性情報に基づいて前記第2分岐予測部による予測が有効でないと判断された分岐命令を、前記記憶部から削除するのが好ましい。3前記記憶部は、前記記憶部に記憶されている分岐命令の数が、記憶可能な分岐命令の数の上限に達した場合には、LRUロジックに基づいて、前記記憶部に記憶されている分岐命令のうち最も最近使用されていない分岐命令に、前記第1分岐予測部による分岐予測ミスの数が前記閾値に達した新たな分岐命令を上書きすることで、前記新たな分岐命令を記憶し、前記LRUロジックでは、前記第2分岐予測部が正しく予測できた場合に、分岐命令が使用されたものとみなすのが好ましい。4前記LRUロジックでは、第2分岐予測部が正しく予測でき、かつ、第1分岐予測部が正しく予測できなかった場合に、分岐命令が使用されたものとみなすのが好ましい。5前記第1分岐予測部による分岐予測ミスの数を分岐命令毎にカウントするカウンタを備え、前記カウンタの値が前記閾値に達した分岐命令が前記記憶部に記憶されるとともに、前記カウンタの値が前記閾値に達すると前記カウンタがリセットされるのが好ましい。6前記記憶部は、前記記憶部に記憶された分岐命令それぞれの分岐結果の履歴を示す履歴情報を記憶するのが好ましい。7前記第2分岐予測部は、分岐命令の分岐結果の履歴に基づいて分岐予測を行うためのPHTPatternHistoryTableを、前記記憶部に記憶された分岐命令毎に有しているのが好ましい。8前記第1分岐予測部の予測結果と前記第2分岐予測部の予測結果とを選択的に出力するセレクタを備えているのが好ましい。9前記記憶部に記憶された分岐命令それぞれについて、前記第2分岐予想部による予測の信頼性を示す信頼性情報を記憶する信頼性情報記憶部を備え、前記信頼性情報は、前記第2分岐予測器の予測が成功した数に基づく情報であり、前記セレクタは、前記信頼性情報に基づいて、前記第1分岐予測部の予測結果及び前記第2分岐予測部の予測結果のいずれを出力するかを決定するのが好ましい。10他の観点からみた本発明は、前記1~9のいずれか1項に記載の分岐予測器によって分岐命令の分岐予測を行うプロセッサである。本発明によれば、破壊的競合を緩和して分岐予測の精度を向上させることができる。以下、本発明の好ましい実施形態について添付図面を参照しながら説明する。[1.予測ミスの偏り]本発明者らは、分岐命令の予測ミスに偏りがあることを新たに見出した。ここでは、従来の分岐予測器において、予測ミスが少数の分岐命令に集中して発生することを示す。予測ミスの偏りの度合いを評価するため、まず、SimpleScalarToolSetDBurgerTMAustinTheSimpleScalarToolSetVersion20TechnicalReportUniversityofWisconsinMadisonComputerSciencesDptJuly1997を用いて、Combining予測器とBimode予測器を実行して評価を行う。ベンチマークには、SPECint2000TheStandardPerformanceEvaluationCorporationから、bzipgccgzipmcfparsertwolfvprvortexの8本を使用する。評価に用いたプロセッサの使用を表1に示す。命令セットは、SimpleScalarPISAを用いる。これらのベンチマークにおいて、最も多く予測ミスが発生する上位8個と上位16個の分岐命令を抽出し、これらの予測ミスが全体の予測ミスに占める割合を調べる。図1aは、Combining予測器において、予測ミスが最も多い上位8個と16個の分岐命令の予測ミスが全体の予測ミスに占める割合を示し、図1bは、Bimode予測器において、予測ミスが最も多い上位8個と16個の分岐命令の予測ミスが全体の予測ミスに占める割合を示す。なお、予測ミスはプログラムの実行状況に応じて変化するため、調べ方については、20M命令ごとに最もミスの多い上位8個あるいは16個の分岐命令を抽出し、それらの予測ミスが全体の予測ミスに占める割合を調べ、これを5回繰り返して100M命令まで評価する。予測器のハードウェア量は、8KB、16KB、32KBの3種類について評価を行う。非特許文献2では、Gshare予測器のサイズがBimode予測器のサイズの2倍になるとき、より良い性能が得られると報告されている。そのため、Combining予測器では、Bimode予測器とSelectorのエントリ数を8K,16K,32K、Gshare予測器のエントリ数を16K,32K,64Kと設定する。Bimode予測器については、Gshare予測器のエントリ数を8K,16K,32Kとし、ChoicePHTのエントリ数を16K,32K,64Kと設定する。図1ab横軸は実行命令数であり、縦軸はミスの多い分岐命令の予測ミスが全体の予測ミスに占める割合である。また、8-8KB8-16K8-32Kは、それぞれ、予測器のハードウェア量が8KB、16KB、32KBである場合について、予測ミスが最も多い上位8個の分岐命令の予測ミスが全体の予測ミスに占める割合を示している。16-8KB16-16K16-32Kは、それぞれ、予測器のハードウェア量が8KB、16KB、32KBである場合について、予測ミスが最も多い上位8個の分岐命令の予測ミスが全体の予測ミスに占める割合を示している。図1abより、Combining予測器とBimode予測器では、8個の分岐命令の予測ミスが、全体のミスの70以上を占めることが分かる。さらに、16個の分岐命令の予測ミスが、全体のミスの80以上を占めることが分かる。[2.実施形態に係る分岐予測器及びプロセッサ]本実施形態に係るプロセッサは、スーパースカラプロセッサであり、分岐予測器1を備えている。図1は、プロセッサが有する分岐予測器1を示している。この分岐予測器1は、予測ミスが少数の分岐命令に偏るという特性を利用したものである。つまり、予測ミスの多い特定の分岐命令については、破壊的競合が生じないように、予測ミスの多い特定の分岐命令毎の履歴ローカル履歴を用いて分岐予測を行う。図1に示すように、分岐予測器1は、第1分岐予測部であるベース予測器BasePredictor10と、MBPMissBiasPredictor20と、予測ミスの多い特定の分岐命令について分岐予測を行う第2分岐予測部であるLHBPLocalHistoryBranchpredictor30と、セレクタ40と、を備えている。[2.1ベース予測器第1予測器の構成]ベース予測器10は、分岐予測の必要な全ての分岐命令について分岐予測を行う。ベース予測器第1分岐予測部10としては、分岐命令の分岐成否の予測分岐予測を行う従来の分岐予測器が用いられている。ベース予測器10としては、例えば、Combining予測器、Bimode予測器、BimodPlus予測器、Agree予測器、Hybrid予測器、Gshare予測器など、破壊的競合の起こり得る予測器を採用することができる。ベース予測器10として、GBHGlobalBranchHistoryグローバル分岐履歴を用いる予測器を採用した場合、ベース予測器10には、GBHが与えられ、プログラムカウンタPC2が示すアドレスの分岐命令について、分岐予測の結果を出力し、セレクタ30に与える。[2.2MBPの構成]MBP20は、分岐予測ミスの多い分岐命令を検出して、その分岐命令を、ローカル分岐履歴などの情報とともに記憶するためのものである。MBP20は、拡張されたBTBBranchTargetBuffer機構であるEBTBExtendedBTB21と、予測ミスの多い分岐命令を記憶するMBBMissBiasBuffer22と、を有している。[2.2.1EBTBの構成]EBTBの基礎となるBTB機構は、分岐先予測BranchTargetPredictionのために予測アドレスTargetAddressを得るための機構であり、分岐命令のアドレスの一部を格納するTagと、各分岐命令のアドレスに対応する予測アドレス分岐アドレスを格納するTaddrと、を有している。EBTB21は、上記BTB機構を利用して、分岐予測ミスの多い分岐命令を検出するための検出部として機能する。BTBを拡張したEBTB21は、従来のBTBと同じように、Tag21aと、Taddr21cと、を備え、さらに、各エントリには、飽和カウンタによって構成されたMCTMissCounter21bを備えている。分岐命令のアドレスの下位ビットi~0に対応するエントリのTag21aには、当該分岐命令のnビットアドレスの上位ビットn-1~i1が格納される。プログラムカウンタPC2から、分岐命令のアドレスの下位ビットi~0が、EBTBのエントリに与えられると、分岐命令のアドレスの下位ビットi~0に対応するエントリのTag21aに格納されているビット列が、判定部21dに出力される。判定部21dは、プログラムカウンタ2から、当該分岐命令のアドレスの上位ビットn-1~i1のビット列も与えられる。判定部21dは、EBTB21から出力されたビット列とプログラムカウンタ2から出力されたビット列とが一致するか否かの判定を行い、一致の場合は、ヒットとなる。なお、EBTB2を通常のBTBとしても用いる場合、判定部21の結果がヒットであると、分岐命令のアドレスの下位ビットi~0に対応するエントリのTaddr21cが予測アドレスとして出力される。MCT21bは、ベース予測器10の分岐正否の分岐予測ミスの数カウントするためのものである。MCT21bは、EBTB21の各エントリに設けられているため、EBTB21では、Tag21aにアドレスの一部が格納されている分岐命令毎に、分岐予測ミスの数がカウントされることになる。なお、MCT21bのサイズは、例えば、4bit程度あれば足りる。また、EBTB21のエントリ数は、2i個である。[2.2.2MBB記憶部の構成]予測ミスの多発する分岐命令を格納するMBB記憶部22は、Addr22aと、LH22bと、U22cと、FR22dと、を備えている。Addr22aは、予測ミスの多発する分岐命令のアドレスnビットが格納される領域であり、分岐命令アドレスの格納により、分岐命令が記憶されていることになる。LHLocalbranchHistory22bは、分岐命令のローカル分岐履歴を記憶する領域であり、mビットのシフトレジスタによって構成され、過去m回の分岐正否を各ビットの0/1で記憶する。UUsebit22cは、該当するエントリが使用されているかどうかを示すビットであり、1が使用中を示し、0が未使用を示す。FRTraceFailureRate22dは、7bitの飽和カウンタであり、第2分岐予測部であるLHBP30の分岐予測ミスの数と、第1分岐予測部であるベース予測器10の分岐予測ミスの数と、の差を有効性情報として保持する。有効性情報は、ベース予測器第1分岐予測部10と比較したLHBP第2分岐予測部30の有効性を示す情報である。MBB22にアドレスが記憶されている分岐命令それぞれの有効性情報に基づいて、有効でないと判断された分岐命令は、MBB22から削除されるU22cが未使用を示す0にセットされる。MBB22のエントリ数が多いほど、分岐予測ミスの多発する分岐命令のアドレスを、MBB22に多く格納することができる。ただし、本発明者らの実験の結果、MBB22のエントリ数を多くしても、分岐予測ミスの減少は僅かであったことから、MBB22のエントリ数MBB22に記憶できる分岐命令数は、8個又は16個程度でよい。[2.3LHBP第2分岐予測部の構成]第2分岐予測部であるLHBP30は、ベース予測器10にて分岐予測がなされる分岐命令の一部について、分岐成否の予測を行う。具体的には、LHBP30は、MBB22に記憶されている分岐命令EBTB21によって分岐予測ミスが多いことが検出された分岐命令について、分岐予測を行う。つまり、LHBP30にて分岐予測がなされる分岐命令につては、ベース予測器10とLHBP30の双方で分岐予測がなされることになる。LHBP30は、MBB22に記憶されている分岐命令毎に個別の分岐履歴ローカル分岐履歴に基づいて分岐予測を行う複数のLPHTLocalPatternHistoryTable31,32,を備えている。LPHT31,32,は、それぞれ、分岐命令の分岐結果の履歴ローカル分岐履歴に基づいて分岐予測を行うためのPHTPatternHistoryTableとして構成されている。LPHT31,32,は、それぞれ、NTCT2bitTakenNotTakensaturatingCounTer31a,32aと、CFConFidence31b,32bと、を有している。NTCT31a,32aは、一般的なPHTと同様に、2ビット飽和カウンタによって構成され、分岐の成否について予測される4つの状態StronglyNotTakenWeaklyNotTakenWeaklyTakenStronglyTakenを保持している。NTCT31a,32aは、対応する分岐命令のみの分岐結果によって、インクリメント又はデクリメントされ、他の分岐命令の分岐結果によってはインクリメント又はデクリメントされない。CF31b,32bは、同一エントリのNTCT31a,32aによる予測の信頼性を示す信頼性情報を記憶する領域信頼性情報記憶部である。CF31a,32aは、2ビットMissResettingCounterとして構成されており、同一エントリのNTCT31a,32aによる予測が成功した場合には、CFがインクリメントされ、予測ミスの場合にはリセットされる。LPHT31,32の個数は、MBB22のエントリ数分岐予測ミスの多い分岐命令を記憶可能な数と同じである。例えば、MBB22の一番目のエントリの分岐命令は、LPHT131を用いて分岐予測がなされる。また、MBB22の二番目のエントリの分岐命令は、LPHT232を用いて分岐予測がなされる。これにより、LHBP20においては、MBB22に格納されている分岐命令同士での破壊的競合は生じない。また、MBB22に格納されている分岐命令の数は、ベース予測器第1分岐予測部10によって分岐予測がなされる分岐命令全体のうちのごく一部であるから、LHBP第2分岐予測部30を別途も受けても、ハードウェア量の増加は少ない。LPHT31,32のエントリ数は、使用する分岐履歴ローカル分岐履歴の長さにより決まる。すなわち、LPHT31,32は、それぞれ、分岐命令のローカル分岐履歴を記憶するLH22bのビット数mに対して、2mのエントリ数を持つ。LPHTのエントリ数は、例えば、512に設定することができる。[2.4MBPによる予測ミスの多発する分岐命令の発見に関する処理][2.4.1EBTBに関する動作予測ミスの多発する分岐命令の発見]MBP20は、岐命令がコミットされるときに、分岐命令のアドレスを用いてEBTB21の検索を行う。つまり、分岐命令が実行されてベース分岐予測器10による分岐正否の結果が判明し、コミット状態になると、プログラムカウンタ2が示す当該分岐命令のアドレスを用いて、EBTB21を検索する。EBTB21の検索の結果、検索対象の分岐命令アドレスがTag21aに格納されており、判定部21dの判定結果がヒットになり、かつ、当該分岐命令に対するベース予測器10による分岐予測が予測ミスであった場合には、対応するMCT21bがインクリメントされる。なお、判定部21dの判定結果がヒットになっても、予測ミスでない場合は、対応するMCT21bは変化しない。EBTB21の検索の結果、検索対象の分岐命令アドレスがTag21aに格納されておらず、判定部21dの判定結果がヒットにならない場合は、従来のBTBと同じように、Tag21aの更新を行い、当該分岐命令に対するベース予測器10による分岐予測が予測ミスであった場合には、MCTを1にセットし、予測成功であった場合には、MCTを0にセットする。このようにして、EBTB21には、予測ミスの生じた分岐命令と、それぞれの分岐命令の予測ミスの数が保持される。いずれかのEBTBエントリのMCT21bが第1閾値に達すると、当該エントリの分岐命令に予測ミスが多発しているものとみなす。このようにして、EBTB21は、予測ミスの多い分岐命令を検出することができる。[2.4.2MBBへの登録]MCT21bが第1閾値に達した分岐命令は、そのアドレスが、MBB22のAddr22aに登録される。そして、該当するEBTB21のエントリのMCT21bがリセットされる。第1閾値に一旦達した分岐命令のMCT21bがリセットされることで、当該分岐命令の予測ミス数が再度カウント可能となり、当該分岐命令が、再度、MBB22に登録される機会が得られ易くなる。MBB22への登録は、以下のように行われる。まず、登録しようとした分岐命令のアドレスが、MBB22のAddr22aに存在するかどうかをチェックされる。このアドレスがMBB22に存在しない場合には、U22cが0未使用のエントリが存在するならば、そのエントリに、そのアドレスを登録し、U22cを1使用にする。もし、MBB22のU22cがすべて1使用の場合、すなわち、MBB22に記憶されている分岐命令の数が、MBB22に記憶可能な分岐命令の数例えば、8個又は16個の上限に達している場合、MBB22は、LRULeastRecentlyUsedロジックを利用して、最も最近使用されていないエントリを選択し、そのエントリのAddr22aに、そのアドレスを上書き登録する。また、そのエントリのFR22dもリセットされる。なお、本実施形態では、上記LRUロジックにおいては、LHBP第2分岐予測部30が正しく分岐予測でき、かつ、ベース予測器第1分岐予測部10が正しく予測できなかった場合に、分岐命令が使用されたものとみなす。分岐命令が単に実行された場合に使用されたものとみなすのではなく、LHBP第2分岐予測部30が正しく分岐予測できた場合に、分岐命令が使用されたものとみなすことで、分岐予測ミスであった分岐命令は、MBB22から削除され易くなる。また、ベース予測器第1分岐予測部10が正しく予測できなかった場合であることも使用の条件に加えることで、ベース予測器10の方が有用である分岐命令が、MBB22から削除され易くなる。[2.4.3MBBの更新]分岐命令がコミットされるとき、当該分岐命令が既にMBB22に登録されているならば、MBB22の更新が行われる。当該分岐命令に対応するエントリのLH22bについては、ローカル履歴が更新される。つまり、シフトレジスタからなるLH22bに対して、当該分岐命令の実行結果分岐正否の結果としての0/1の入力によるシフトがなされる。FR22dの更新については、LHBP第2分岐予測部30での予測が失敗し、かつ、ベース予測器第1分岐予測部10の予測が成功の場合は、FR22dがインクリメントされる。一方、LHBP30での予想が成功、かつ、ベース予測器10の予測が失敗の場合は、デクリメントする。これにより、FR22dには、ベース予測器10と比較したLHBP30による予測の有効性情報として、ベース予測器10とLHBP30の予測の差を格納できる。FR22dの値が、第2閾値になると、LHBP30による予測ミスが、ベース予測器10よりも多く発生するために、LHBP30による予測が有効でないと判断し、MBB22は、当該エントリにおける各領域22a,22b,22c,22dをリセットする。これにより、LHBP30による予測が有効でないと判断された分岐命令が、MBB22から削除される。[2.4.4LPHTの更新]分岐命令がコミットされるときに、当該分岐命令のアドレスを用いて、MBB22を検索する。当該分岐命令のアドレスが、MBB22のいずれかのエントリのAddr22aに存在する場合には、そのAddr22aと同一エントリにあるLH22bのローカル分岐履歴を利用して、LPHTを更新する。具体的には、当該分岐命令のアドレスに対応するAddr22aと同一エントリにあるLH22bが示すローカル履歴mbitのビット列に対応するLPHTエントリのNTCT32aを、当該LH22bが占めるローカル履歴の情報で更新する。さらに、CF31b、32bの更新も行われる。すなわち、予測が成功した場合はインクリメントされ、予測ミスの場合はリセットされる。[2.5LHBPによる分岐予測]分岐命令がフェッチされるときに、フェッチされた分岐命令のアドレスを用いて、MBB22を検索する。当該アドレスが、MBB22のAddr22aに存在する場合には、そのAddr22aと同一エントリにあるLH22bに対応するLPHTのエントリのNTCTとCFの値を得る。得られたNTCTを用いて、フェッチされた分岐命令のLHBP第2分岐予測部30による分岐予測結果Taken又はNotTakenが出力され、CFの値とともにセレクタ40の取得部41に与えられる。取得部41は、LHBP30の分岐予測結果を、セレクタ本体42に与える。セレクタ本体42には、フェッチされた当該分岐命令のベース予測器第1分岐予測部10による分岐予測結果も与えられる。セレクタ本体42は、取得部41からCFの値を得て、ベース予測器10による分岐予測結果とLHBP30による分岐予測結果とを選択的に出力する。具体的には、セレクタ本体42は、CF信頼性情報の値が第3閾値に達している場合に、LHBP30の分岐予測結果を出力し、その他の場合はベース予測器10の分岐予測結果を、出力する。CFの値は、予測ミスがあるとリセットされるため、CFの値が第3閾値に達するまで連続して予測に成功しないと、LHBP30の予測結果は使用されず、ベース予測器10による予測結果が使用される。これにより、ローカル履歴のみを用いたLHBP30による分岐予測の誤動作を緩和することができる。[3.評価][3.1予測ミスの削減率の評価]ベース予測器10として、Combining予測器、Bimode予測器、BimodePlus予測器、Agree予測器、Hybrid予測器の5種類を用いる。ベース予測器10であるCombining、Bimode、BimodePlus、Agreeのサイズを、8KB、16KB,32KB,64KBの4種類とし、Hybrid予測器のサイズは、10.5KB,17.75KB,30KB,60.5KBと設定する。図3~図7は、それぞれ、分岐予測器1における予測ミスの削減率の評価結果を、ベンチマーク毎に示している。図3~図7において、横軸はベンチマークであり、縦軸は、本実施形態に係る分岐予測器1の、ベース分岐予測器に対する予測ミス削減率である。なお、ベンチマークとしては、CommBenchから、drrreeddecreedencrtrzipencの5種類を用い、SPECint2000から、bzipgccgzipmcfparsertwolfvortexvprの8種類を用いた。図3~図5に示すように、ベース予測器10として、CombiningBimodeBimodePlusを用いた分岐予測器1は、SPECint2000において、最大40以上、平均10以上の予測ミスを減らすことができ、CommBenchにおいて、最大30、平均6以上の予測ミスを減らすことができた。図6に示すように、ベース予測器10として、Agreeを用いた分岐予測器1は、SPECint2000において、最大23以上、平均10以上の予測ミスを減らすことができ、CommBenchにおいて、最大30、平均6程度の予測ミスを減らすことができた。図7に示すように、ベース予測器10として、Hybridを用いた分岐予測器1は、SPECint2000において、最大45以上、平均7以上の予測ミスを減らすことができ、CommBenchにおいて、最大20、平均3程度の予測ミスを減らすことができた。[3.2ハードウェア規模の検討]実施形態に係る分岐予測器1のうち、EBTB21に関しては、BTBが持つ検索ポートを利用するために、BTBを拡張したEBTB21には、検索用のポートを追加する必要がない。また、EBTB21に含まれるMCT21bは4bitのため、EBTB21のエントリ数が、64個であれば、BTBを拡張してEBTB21にするために必要なメモリ量は、1KBである。MBB22について、Addr22aが32bit、LH22bが9bit、U22cが1bit、FR22dが7bitであると、各エントリそれぞれについての語長は49ビットとなる。したがって、MBB22のエントリ数を8とすると、MBB22のために必要なメモリ量は392bitのCAMとなる。LPHT31,32,については、個数が8個、それぞれのエントリ数が512、NTCTが2bit、CFが2bitとすると、語長は4bitとなり、必要なメモリ量は2KBである。したがって、本実施形態に係る分岐予測器1は、従来の分岐予測器ベース予測器のみに対して、3KB程度、ハードウェア量が増加する。図8は、予測器のサイズとそれらのMPKIMisspredictionPerKiloInstructionの関係を示す。予測器の各欄は、対応するサイズでのMPKIである。図8に示すように、例えば、8KBのCombining予測器と、8KBのCombining予測器をベース予測器10として有する分岐予測器1とを比較すると、MPKIの値が低下している。8KBのCombining予測器をベース予測器10として有する分岐予測器1は、64KBのCombining予測器と同等以上の性能になる。これは、Bimode、BimodePlus、Agreeについても同様である。これらのことより、本実施形態の分岐予測器1は、従来の分岐予測器のエントリー数の増加以上の効果が得られる。[4.付記]なお、上記において開示した事項は、例示であって、本発明を限定するものではなく、様々な変形が可能である。"