(57)【要約】【課題】  分岐予測の精度向上に有効な情報が分岐予測回路内に残る確率をあげたことを特徴とする分岐予測手法及びその分岐予測手法を実行する分岐予測回路を提供することを目的とする。【解決手段】  分岐命令と、分岐予測と、分岐予測に示された分岐がおきる可能性の程度と、を含む分岐情報を記憶する第１記憶部及び第２記憶部を有する分岐予測回路による分岐予測方法において、上記分岐情報を第１記憶部又は第２記憶部に記憶する情報記憶工程と、上記分岐命令により設定された分岐条件と、実現した分岐とから、上記分岐予測が実現したかを判断する工程と、上記判断及び上記分岐予測に示された分岐がおきる可能性の程度に応じて上記第１記憶部又は上記第２記憶部の内の一つの上記情報の書き換えを行う書き換え工程と、上記分岐命令を前記処理装置で実行する際に、上記分岐情報に応じて分岐予測を行う工程と、を備えることを特徴とする分岐予測方法を提供する。 【選択図】    図３
2011209774.tif 000002
【特許請求の範囲】
【請求項１】
分岐命令と、分岐予測と、分岐予測に示された分岐がおきる可能性の程度と、を含む分岐情報を記憶する第１記憶部及び第２記憶部を有し、前記分岐命令を実行する処理装置に含まれる分岐予測回路による分岐予測方法において、
前記分岐情報を前記第１記憶部又は前記第２記憶部に記憶する情報記憶工程と、
前記分岐命令により設定された分岐条件と、実現した分岐とから、前記分岐予測が実現したかを判断する工程と、
前記判断及び前記分岐予測に示された分岐がおきる可能性の程度に応じて前記第１記憶部又は前記第２記憶部の内の一つの前記分岐情報の書き換えを行う書き換え工程と、
前記分岐命令を前記処理装置で実行する際に、前記分岐情報に応じて分岐予測を行う工程と、
を備えることを特徴とする分岐予測方法。
【請求項２】
前記第１記憶部における前記分岐情報と、前記第２記憶部における前記分岐情報について、記憶順序を記憶する工程を含み、
前記書き換え工程において、
前記分岐予測に示された分岐がおきる可能性の程度が、前記第１記憶部における前記分岐情報と、前記第２記憶部における前記分岐情報とで、同程度であった場合に、前記記憶順序に応じて、前記第１記憶部又は前記第２記憶部の内の一つの前記分岐情報の書き換えを行うことを特徴とする請求項１記載の分岐予測方法。
【請求項３】
前記書き換え工程において、
前記分岐予測に示された分岐がおきる可能性の程度が、前記第１記憶部に記憶された前記分岐情報と、前記第２記憶部に記憶された前記分岐情報とで、同程度であった場合に、前記第１記憶部に記憶された前記分岐情報又は前記第２記憶部に記憶された前記分岐情報の内の一つを順番に選択して書き換えを行うことを特徴とする請求項１記載の分岐予測方法。
【請求項４】
前記書き換え工程において、
前記分岐予測に示された分岐がおきる可能性の程度が、前記第１記憶部に記憶された前記分岐情報と、前記第２記憶部に記憶された前記分岐情報とで、同程度であった場合に、前記第１記憶部に記憶された前記分岐情報又は前記第２記憶部に記憶された前記分岐情報の内の一つをランダムに選択して書き換えを行うことを特徴とする請求項１記載の分岐予測方法。
【請求項５】
分岐命令と、分岐予測と、分岐予測に示された分岐がおきる可能性の程度と、を含む情報を記憶する第１記憶部、及び、第２記憶部と、
前記分岐命令により設定された分岐条件と、実現した分岐とから、前記分岐予測が実現したか否かを判断し、前記判断及び前記分岐予測に示された分岐がおきる可能性の程度に応じて前記第１記憶部又は前記第２記憶部の内の一つの前記分岐情報の書き換えを制御する制御回路と、
前記制御回路による制御を受けて、前記第１記憶部又は第２記憶部内の前記分岐情報の書き換えを行う書き換え回路と、を備えることを特徴とする分岐予測回路。
【請求項６】
前記分岐予測に示された分岐がおきる可能性の程度は、前記分岐予測が実現した場合又実現しなかった場合に、更新されることを特徴とする請求項５記載の分岐予測回路。
【請求項７】
分岐命令と、分岐予測と、分岐予測に示された分岐がおきる可能性の程度と、を含む分岐情報を記憶する、複数の記憶部と、
前記分岐命令により設定された分岐条件と、実現した分岐とから、前記分岐予測が実現したか否かを判断し、前記判断及び前記分岐予測に示された分岐がおきる可能性の程度に応じて前記複数の記憶部の内の一つの前記分岐情報の書き換えを制御する制御回路と、
前記制御回路による制御を受けて、前記複数の記憶部内の一つの前記分岐情報の書き換えを行う書き換え回路と、を備えることを特徴とする分岐予測回路。
【発明の詳細な説明】
【技術分野】
【０００１】
パイプライン処理プロセッサにおける分岐予測方法及びその方法を実行する分岐予測回路。
【背景技術】
【０００２】
命令コードをパイプラインにより処理するパイプライン処理プロセッサでは、命令コード処理の効率の低下を防止するため、命令コードを次々にフェッチし、パイプラインを構成する各段階を途切れなく動作させている。
しかし、プログラムに分岐がある場合には、次に処理する命令コードが未決定なため、フェッチが待たされ、パイプラインの効果が低下し、パイプライン処理プロセッサの性能劣化を招くことになる。
その性能劣化を防止するため、分岐予測を行い、パイプライン処理プロセッサは分岐予測に基づいて次に処理する命令コードをフェッチしている。ここで、分岐予測が当たった場合にはフェッチが有効となりパイプラインの効果が維持される。しかし、分岐予測がはずれたときにはフェッチした命令コードを破棄して正しい分岐先の命令コードを再フェッチすることになる。
従って、分岐予測がはずれる確率が高ければ、分岐予測処理のための回路の増分等のデメリットが大きい。とはいえ、分岐予測があたる確率が高ければ、回路の増大というデメリットより、分岐予測処理によるメリットが上回る。
【０００３】
そこで、分岐予測精度の向上のための提案がされている（特許文献１参照。）。特許文献１によれば、並列したパイプラインを複数もち、過去の履歴に基づいて、分岐予測があたりにくい条件分岐命令コードを特定して分岐側と非分岐側の両方を投機的に行う並列処理装置が記載されている。そして、条件分岐命令コードに対して、分岐側と非分岐側の両方を投機的に実行が行えない場合、すなわち、並列パイプラインに空きがない場合、過去の履歴情報から条件の成否を予測し、その予測結果に基づいて分岐側か、非分岐側かのどちらかの命令コードを並列処理装置は選択して実行する。
【０００４】
しかし、過去の履歴情報から条件の成否を予測するときに、一般的にいって、高い予測精度を得るには、処理装置が大量の履歴情報を登録するＢＴＢ（Branch Target Buffer:分岐アドレスバッファ）を保有することになる。その結果、コストの観点から、大規模なＢＴＢがもてない場合には予測精度が低下することになる。また、予測手法によっては、履歴情報を登録するＢＴＢの特定の領域に有効な情報が集中することによる頻繁な履歴情報の入れ替え動作により、ＢＴＢへのアクセス回数が増大するため、処理装置の消費電力が増大することになる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１１−９６００５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明によれば、分岐予測の精度向上に有効な情報が分岐予測回路内に残る確率をあげたことを特徴とする分岐予測手法及びその分岐予測手法を実行する分岐予測回路を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記の課題を解決するため、分岐命令、分岐予測、及び、分岐予測に示された分岐がおきる可能性の程度を表す情報を記憶する第１記憶部及び第２記憶部を有し、前記分岐命令を実行する処理装置に含まれる分岐予測回路による分岐予測方法において、
上記情報を第１記憶部又は第２記憶部に記憶する情報記憶工程と、
上記分岐命令により設定された分岐条件と、実現した分岐とから、上記分岐予測が実現したかを判断する工程と、
上記判断及び上記分岐予測に示された分岐がおきる可能性の程度に応じて上記第１記憶部又は上記第２記憶部の内の一つの上記情報の書き換えを行う書き換え工程と、
上記分岐命令を前記処理装置で実行する際に、上記情報に応じて分岐予測を行う工程と、
を備えることを特徴とする分岐予測方法を提供する。
【発明の効果】
【０００８】
分岐予測回路に、分岐予測の精度向上に有効な情報が残る確率をあげたことを特徴とする分岐予測手法及びその分岐予測手法を実行する分岐予測回路が提供される。
【図面の簡単な説明】
【０００９】
【図１】図１は実施例に関わるコンピュータ１０を示す図である。
【図２】図２Ａ、Ｂは図１のコンピュータ１０に対して命令を入力したときのパイプライン動作を説明する図である。
【図３】図３は、ブランチアドレスを蓄積するＢＴＢ（Branch Target Buffer）に新しい履歴情報及びＢＴＢエントリを登録する際のフローチャートを示す。
【図４】図４はＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に含まれるＢＴＢエントリ管理回路２００を示す回路ブロック図である。
【図５】図５はＢＴＢエントリ管理回路２００の予測動作について詳細に説明する図である。
【発明を実施するための形態】
【００１０】
本発明は、以下に説明する実施例に対し、当業者が想到可能な、設計上の変更が加えられたもの、及び、実施例に現れた構成要素の組み換えが行われたものも含む。また、本発明は、その構成要素が同一の作用効果を及ぼす他の構成要素へ置き換えられたもの等も含み、以下の実施例に限定されない。
【実施例】
【００１１】
図１は実施例に関わるコンピュータ１０を示す図である。コンピュータ１０は、Ｉ−Ｃａｃｈｅ１１、レジスタ１２、レジスタ１３、レジスタ１４、Ｄｅｃｏｄｅ１５、レジスタ１６、レジスタ１７、レジスタ１８、レジスタ１９、レジスタ２０、レジスタ２１、ＢＴＡＧ２２、ＩＦＥＡＧ２３、Ｓｅｌｅｃｔｏｒ２４、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５、ＲｅｇＮｏ２６、ＲｅｇｉｓｔｅｒＦｉｌｅ２７、Ｓｒｃ２８、ＡＬＵ／ＥＡＧ２９、Ｒｅｓｕｌｔ３０、Ｄ−Ｃａｃｈｅ３１、Ｓｅｌｅｃｔｏｒ３２、Ｗｒｉｔｅｄａｔａ３３、ＲＣＤレジスタ３７、ＥＸＣＤレジスタ３８から構成されるパイプライン４０、５０を含むコンピュータである。なお、パイプラインは後に説明するように、ＩＦ（命令プリフェッチ）、ＩＤ（命令デコード）、ＲＲ（レジスターリード）、ＥＸ（命令実行）、ＭＡ（メモリアクセス）、ＷＢ（ライトバック）の段階からなっている。なお、図１における点線はパイプラインの各段階に属する回路の境目を表す。
【００１２】
命令プリフェッチ段階において、ＩＦＥＡＧ２３は次にフェッチする命令（インストラクション）が記憶されている記憶領域を示すアドレス、ＩＦＩＡ(Instruction Fetch Instruction Address)を計算により求める回路である。その後、ＩＦＥＡＧ２３はＳｅｌｅｃｔｏｒ２４及びＢｒａｎｃｈＰｒｅｄｅｃｔｉｏｎ２５に対してＩＦＩＡを出力する。
Ｉ−Ｃａｃｈｅ１１はコンピュータ１０の外部から、矢印で示すように外部バス３４を介して供給される命令（Ｉｎｓｔｒｕｃｔｉｏｎ）を蓄積している命令キャッシュでありである。そして、パイプライン処理中の命令プリフェッチ（ＩＦ）段階において、Ｉ−Ｃａｃｈｅ１１はＳｅｌｅｃｔｏｒ２４からＩＦＩＡを受け取ると、対応する命令（インストラクション(Instruction)）を、Ｉ−Ｃａｃｈｅ１１が有する記憶領域から読出、レジスタ１２に出力する。
【００１３】
命令プリフェッチ段階において、ＩＦＥＡＧ２３からＩＦＩＡを受け取ると、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は分岐命令に対して、分岐方向や分岐先アドレスの予測を行う回路であり、分岐予測機構を含む。分岐予測の後、分岐予測に応じた分岐先を示すＩＦｔａｒｇｅｔをｓｅｌｅｃｔｏｒ２４に出力し、ＩＦＰＦ(Instruction Fetch Profile)をＩＤＰＦ(Instructiondecode Profile)としてレジスタ１４に出力する。
ＩＦＰＦとは２ビットからなるデジタルのカウント値であり、カウント値は分岐命令に対応するＩＦｔａｒｇｅｔにより示された分岐が起こる可能性の程度を示す。例えば、カウンタ値”１１”はストロングリーｔａｋｅｎ（分岐可能性大）を表し、カウンタ値”１０”はウィークリーｔｅｋｅｎ（分岐可能性小）を表し、カウンタ値”０１”はウイクリーｎｏｔｔａｋｅｎ（分岐しない可能性小）を表し、カウンタ値”００”はストロングリーｎｏｔｔａｋｅｎ（分岐しない可能性大）を表す。カウンタ値は分岐命令に対応して分岐が起こったか否かの評価に対応して更新される履歴情報である。例えば、分岐命令に対して、分岐しない場合、その分岐命令に対応するカウンタ値はデクリメント（減少）され、カウント値は「ウィークリーｎｏｔｔａｋｅｎ（分岐しない可能性大）」の方向に移行する。
命令プリフェッチ段階において、Ｓｅｌｅｃｔｏｒ２４は、分岐命令のときには、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５からのＩＦｔａｒｇｅｔとＩＦＩＡとの組合せを選択し、Ｉ−Ｃａｃｈｅ１１に出力する。ただし、ＢＴＡＧ２２から出力されたＥＸｔａｒｇｅｔにより、ＩＦｔａｒｇｅｔが示す分岐先と異なる分岐先が指定されたときは、ＥＸｔａｒｇｅｔを再度、Ｉ−Ｃａｃｈｅ１１に出力する。分岐命令でないときには、Ｓｅｌｅｃｔｏｒ２４はＩＦＥＡＧ２３からのＩＦＩＡのみをＩ−Ｃａｃｈｅ１１に出力する。
また、ＩＦＩＡは０番目ビットから３１番目ビットまでを有し、Ｓｅｌｅｃｔｏｒ２４はＩＦＩＡの１２番目のビットから３１番目のビットまでを、ＩＤＩＡ(Instruction decode Instruction Address)としてレジスタ１３に出力する。なお、ＩＤＩＡは、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５内の分岐予測機構が有する記憶領域に対するアドレスとして使用される。
【００１４】
次いで、パイプライン処理中の命令デコード段階（ＩＤ）において、レジスタ１２はＩ−Ｃａｃｈｅ１１から出力された命令を格納する命令格納レジスタである。
命令デコード段階において、レジスタ１３はＳｅｌｅｃｔｏｒ２４から出力されるＩＤＩＡを格納するアドレスレジスタである。
命令デコード段階において、レジスタ１４はＩ−Ｃａｃｈｅ１１から出力される命令のプロファイルを格納するプロファイルバッファである。
命令デコード段階において、Ｄｅｃｏｄｅ１５は命令（ｉｎｓｔｒｕｃｔｉｏｎ）から即値（ｉｍｍｅｄｉａｔｅ）をデコードし、ＲＲＢＣＤ(resister read branch condition code)を算出する。
【００１５】
ここで、ＲＲＢＣＤは、複数の分岐条件の内、どの条件にあてはまったかを示すコードである。なお、分岐条件の中には、分岐がおきないという条件も含まれる。
【００１６】
パイプラインのレジスターリード段階（ＲＲ）において、レジスタ１６はＤｅｃｏｄｅ１５から供給されたｉｍｍｅｄｉａｔｅ（即値：処理対象を特定する値）を格納するレジスタである。また、ＲｅｇｉｓｔｅｒＦｉｌｅ２７はＲｅｇＮｏ２６からｉｍｍｅｄｉａｔｅを受け取り、ｉｍｍｅｄｉａｔｅを蓄積する記憶回路である。
レジスターリード段階において、レジスタ１７はＤｅｃｏｄｅ１５から出力されるｉｍｍｅｄｉａｔｅに関連するＲＲＩＡ(resister read instruction address)を格納するアドレスレジスタである。レジスタ１３に格納されたＩＤＩＡが、ＲＲＩＡ(Register read instruction address)としてレジスタ１７に格納される。
レジスターリード段階において、レジスタ１８はレジスタ１４から出力されるＩＤＰＦを、ＲＲＰＦ(Register read profile)として格納するプロファイルレジスタである。
レジスターリード段階において、分岐コンディションレジスタ３７はＤｅｃｏｄｅ１５から出力されるＲＲＢＣＤを格納するレジスタである。
【００１７】
パイプラインの命令実行段階（ＥＸ）において、レジスタ１９はレジスタ１６に格納されたＩｍｍｅｄｉａｔｅを受け取り、格納するレジスタである。
パイプラインの命令実行段階（ＥＸ）において、レジスタ２０はレジスタ１７格納するＲＲＩＡを受け取り、ＥＸＩＡ(Execute instruction Address)として格納するアドレスレジスタである。
パイプラインの命令実行段階（ＥＸ）において、レジスタ２１はレジスタ１８に格納されたＲＲＰＦを受け取り、ＥＸＰＦ(Execute Profile)として格納するプロファイルバッファである。
パイプラインの命令実行段階（ＥＸ）において、レジスタ３８は、レジスタ３７が格納しているＲＲＢＣＤを受け取り、ＥＸＢＣＤ(Execute branch condition code)として格納する。
パイプラインの命令実行段階（ＥＸ）において、ＢＴＡＧ２２は予測した分岐が行われず、分岐予測ミスの場合及び分岐予測をしなかった場合に、分岐先アドレスを計算し、その分岐先のアドレス(ＥＸ  ｔａｒｇｅｔ)をＳｅｌｅｃｔｏｒ２４へ出力するとともに、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に出力する回路である。
パイプラインの命令実行段階（ＥＸ）において、Ｓｒｃ２８は、ＲｅｇｉｓｔｅｒＦｉｌｅ２７から読み出したｉｍｍｅｄｉｔｅ（処理対象を特定する値）を格納するレジスタである。
パイプラインの命令実行段階（ＥＸ）において、ＡＬＵ／ＥＡＧ２９は命令で指定された演算、データアクセスのためのアドレス計算を行う。ここで、演算とは、例えば、値の大小比較、減算、加算などである。また、ＡＬＵ／ＥＡＧ２９は分岐命令に関連するｃｏｎｄｉｔｉｏｎ  ｃｏｄｅ（分岐条件）を、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に出力する。
【００１８】
メモリアクセスの段階（ＭＡ）において、Ｒｅｓｕｌｔ３０はＡＬＵ／ＥＡＧ２９で行った演算の結果及びデータアクセスのためのアドレス計算の結果を格納するレジスタである。
メモリアクセスの段階（ＭＡ）において、Ｄ−Ｃａｃｈｅ３１はＲｅｓｕｌｔ３０から供給された演算の結果及びデータアクセスのためのアドレス計算の結果を一時格納し、その後、Ｓｅｌｅｃｔｏｒ３２に出力するキャッシュである。
メモリアクセスの段階（ＭＡ）において、Ｓｅｌｅｃｔｏｒ３２はＲｅｓｕｌｔ３０からの演算の結果及びデータアクセスのためのアドレス計算の結果、又は、Ｄ−Ｃａｃｈｅ３１に格納された演算の結果及びデータアクセスのためのアドレス計算の結果の内、どちらかを選択してＷｒｉｔｅｄａｔａ３３に出力するデータを選択する回路である。
【００１９】
ライトバックの段階（ＷＢ）において、Ｗｒｉｔｅｄａｔａ３３はＲｅｇｉｓｔｅｒＦｉｌｅ２７に格納するデータを蓄積するレジスタである。
【００２０】
図２Ａ、Ｂは図１のコンピュータ１０に対して命令を入力したときのパイプライン動作を説明する図である。なお、パイプラインは、ＩＦ（命令プリフェッチ）、ＩＤ（命令デコード）、ＲＲ（レジスターリード）、ＥＸ（命令実行）、ＭＡ（メモリアクセス）、ＷＢ（ライトバック）の段階からなっている。
図２Ａは、分岐予測と実際の分岐が一致した場合のパープラインの動作を示す。図２Ａにおいて、命令ｃｍｐ  ｒ１、ｒ２、命令ｂｌｔ＿ｌａｂｅｌ１、命令ｓｕｂ  ｒ１、ｒ２、ｒ３、（命令ｂｒａ＿ｌａｂｅｌ１）、（命令ｓｕｂ  ｒ１、ｒ２、ｒ３）、命令ｓｔ  ｒ３，＠（ｒ９，ｒ０）を行う場合に、パイプライン動作において分岐予測があたった例を示す。上記の命令の主旨は、以下である。まず数値ｒ１と数値ｒ２を比較する。次いで、ｒ１が大きければ、ｒ３＝ｒ１−ｒ２を行い、ｒ２が大きければ、ｒ３＝ｒ２−ｒ１を行う。ついで、結
果ｒ３を数値ｒ９と数値ｒ０で指定されるレジスタに格納する。
【００２１】
そこで、図１に示すコンピュータ１０では、パイプライン４０、５０により、上記の命令を並列して２個づつ処理している。まず、命令ｃｍｐ  ｒ１、ｒ２、命令ｂｌｔ＿ｌａｂｅｌ１を命令フェッチ段階にセットする。次いで、パイプライン４０、５０の分岐予測機構を含むＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５からのブランチアドレスの出力により命令ｓｕｂ  ｒ１、ｒ２、ｒ３、命令ｓｔ  ｒ３，＠（ｒ９，ｒ０）について命令フェッチ段階にセットする。ここで、最初に命令フェッチ段階にセットした命令ｃｍｐ  ｒ１、ｒ２、命令ｂｌｔ＿ｌａｂｅｌ１が命令実行段階にきて、結果が確定し、分岐予測があたると、次に命令フェッチ段階にセットされたｓｕｂ  ｒ１、ｒ２、ｒ３、命令ｓｔ  ｒ３，＠（ｒ９，ｒ０）はそのまま継続して実行が進められる。そして、パイプライン５０のＡＬＵ／ＥＡＧ２９から演算結果は、パイプライン４０、５０のＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５へ伝達される。その結果、パイプライン４０、５０のＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５において、分岐予測と実際の分岐が一致したことについてブランチアドレスのプロファイル（履歴情報）の更新が行われる。
【００２２】
図２Ｂは、分岐予測と実際の分岐が一致しなかった場合のパープラインの動作を示す。図２Ｂにおいて、命令ｃｍｐ  ｒ１、ｒ２、命令ｂｌｔ＿ｌａｂｅｌ１、命令ｓｕｂ  ｒ１、ｒ２、ｒ３、命令ｂｒａ＿ｌａｂｅｌ１、命令ｓｕｂ  ｒ１、ｒ２、ｒ３、命令ｓｔ  ｒ３，＠（ｒ９，ｒ０）を行う場合に、パイプライン動作において分岐予測があたった例を示す。上記の命令の主旨は、以下である。まず数値ｒ１と数値ｒ２を比較する。次いで、ｒ１が大きければ、ｒ３＝ｒ１−ｒ２を行い、ｒ２が大きければ、ｒ３＝ｒ２−ｒ１を行う。ついで、結果ｒ３を数値ｒ９と数値ｒ０で指定されるレジスタに格納する。
【００２３】
そこで、図１に示すコンピュータ１０では、パイプライン４０、５０に対して、まず、命令ｃｍｐ  ｒ１、ｒ２、命令ｂｌｔ＿ｌａｂｅｌ１を命令フェッチ段階にセットする。
次いで、同様にパイプライン４０、５０の分岐予測機構を含むＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５からのブランチアドレスの出力により命令ｓｕｂ  ｒ１、ｒ２、ｒ３、命令ｓｔ  ｒ３，＠（ｒ９，ｒ０）について命令フェッチ段階にセットする。ここで、分岐予測がはずれるように、命令実行段階にセットされた命令ｃｍｐ  ｒ１、ｒ２、命令ｂｌｔ＿ｌａｂｅｌ１の結果が確定すると、命令ｓｕｂ  ｒ１、ｒ２、ｒ３、命令ｓｔ  ｒ３，＠（ｒ９，ｒ０）に対するパイプライン動作は停止される。そして、正しい分岐先の命令ｂｒａ＿ｌａｂｅｌ１、及び、命令ｓｕｂ  ｒ１、ｒ２、ｒ３が行われる。命令ｓｕｂ  ｒ１、ｒ２、ｒ３、命令ｓｔ  ｒ３，＠（ｒ９，ｒ０）に対するパイプライン動作が停止されたときに、パイプライン５０のＡＬＵ／ＥＡＧ２９から演算結果は、パイプライン４０、５０のＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５へ伝達される。その結果、パイプライン４０、５０のＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５において、分岐予測と実際の分岐が一致しなかったことについてブランチアドレスのプロファイル（履歴情報）の更新が行われる。
【００２４】
図３は、ブランチアドレスを蓄積するＢＴＢ（Branch Target Buffer）に新しい履歴情報及びＢＴＢエントリを登録する際のフローチャートを示す。
ここで、ＢＴＢエントリを記憶するＢＴＢエントリ管理回路２００は分岐予測機構を含むＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に備えられている。また、ＢＴＢエントリは分岐命令（ｉｎｓｔｒｕｃｔｉｏｎ）の格納アドレス、分岐先を示すアドレス（ｔａｒｇｅｔ）、その分岐が起こる可能性の程度を示すプロファイル（ＰＦ：履歴情報）、及び、ＢＴＢエントリが確定したものであることを示すＶＦＬＡＧ(valid flag)を含む。
【００２５】
コンピュータ１０において、ＢＴＡＧ２２から実際の分岐条件を示すＥＸｔａｒｇｅｔがＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に出力されたときに、図３のフローチャートにおけるオペレーションｏｐ１００の判断が行われる。
オペレーションｏｐ１００において、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は予測に基づく分岐が行われたかいなか、すなわち、予測のもととなったＢＴＢエントリに対応する分岐がｔａｋｅｎになったか否かを判断する。分岐が行われたとき（ｔａｋｅｎになったとき）はオペレーションｏｐ１２０へ進む。一方、分岐が行われなかったとき（ｎｏｔｔａｋｅｎのとき）はオペレーションｏｐ１１０へ進む。
オペレーションｏｐ１１０においては、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は分岐が行われなかったブランチアドレスを含むＢＴＢエントリがＢＴＢエントリ管理回路２００のＢＴＢに登録されているかを判断する。そのＢＴＢエントリがＢＴＢエントリ管理回路２００のＢＴＢに登録されていなければ、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５はＢＴＢエントリ管理回路２００に記憶されているすべてのＢＴＢエントリに修正を加えずに動作を終了する。
【００２６】
オペレーションｏｐ１２０においては、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は分岐が行われたインストラクションアドレスを含むＢＴＢエントリがＢＴＢエントリ管理回路２００のＢＴＢに登録されているかを判断する。登録されていた場合はオペレーションｏｐ１３０へ進む。登録されていなかった場合は、オペレーションｏｐ１４０へ進む。
オペレーションｏｐ１３０においては、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は分岐が行われたブランチアドレスを含むＢＴＢエントリのプロファイル（履歴情報）を更新する。
【００２７】
オペレーションｏｐ１４０においては、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は分岐が行われたインストラクションアドレスを含むＢＴＢエントリがＢＴＢエントリ管理回路２００のＢＴＢの記憶領域に空きがあるか否かを判断する。ＢＴＢエントリ管理回路２００のＢＴＢの記憶領域に空きがある場合は、オペレーションｏｐ１５０へ進む。記憶領域に空きがない場合はオペレーションｏｐ１６０へ進む。
オペレーションｏｐ１５０においては、空いているＢＴＢエントリ管理回路２００のＢＴＢの記憶領域に、分岐が行われたブランチアドレスを含むＢＴＢエントリを書き込む。その後、オペレーションｏｐ１９０へ進む。
【００２８】
オペレーションｏｐ１６０においては、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５はＢＴＢの記憶領域に空きがない場合に、ＥＸＩＡと分岐命令（ｉｎｓｔｒｕｃｔｉｏｎ）の格納アドレスが一致するＢＴＢエントリを検出する。ＢＴＢエントリ管理回路２００においては、ＢＴＢとしてＢＴＢ２４０とＢＴＢ２５０を備えているため、ＥＸＩＡと分岐命令（ｉｎｓｔｒｕｃｔｉｏｎ）の格納アドレスが一致するＢＴＢエントリは、ＢＴＢ２４０とＢＴＢ２５０とからそれぞれ１個ずつ、合計２個のＢＴＢエントリを検出する。
そして、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は、検出したＢＴＢエントリのプロファイル（履歴情報、すなわち、taken確率）同士を比較する。
その結果、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は、検出したＢＴＢエントリのカウンタ値が同一であった場合は、オペレーションｏｐ１７０へ進む。また、検出されたＢＴＢエントリのカウンタ値が低いものがあった場合は、オペレーションｏｐ１８０へ進む。
【００２９】
ここで、カウンタ値が高いか低いかの判断をせずに、すなわち、ｔａｋｅｎ確率が低いか否かの判断をせずに最後に参照された時刻が古いか否かによってＢＴＢエントリのリプレースを行うと、分岐のｔａｋｅｎ確率が確実な場合にも、ＢＴＢエントリの入れ替えが行われることになる。すなわち、分岐のｔａｋｅｎ確率が低いＢＴＢエントリがＢＴＢ内に残ることになるため、予測機構の分岐予測の精度が低くなる。
そこで、入れ替えの回数を減少させるため、記憶するＢＴＢエントリを多くすることが考えられる。その場合、ＢＴＢエントリは分岐命令（ｉｎｓｔｒｕｃｔｉｏｎ）の格納アドレスを表す２０ビットと、分岐先を示すアドレス（ｔａｒｇｅｔ）を表す３０ビットと、プロファイルを表す２ビットと、バリットを表す１ビットの合計５３ビットからなっているため、ＢＴＢの記憶領域が大幅に増加することになり、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に含まれる予測機構を構成する回路の面積が増大することになる。
【００３０】
従って、検出されたＢＴＢエントリと、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に入力された、検出されたのＢＴＢエントリのプロファイル同士を比較してｔａｋｅｎ確率が低いか否かの判断をおこなって、検出されたＢＴＢエントリ内のｔａｋｅｎ確率が低いＢＴＢエントリを、ＥＸｔａｒｇｅｔ、ＥＸＩＡ、及び、ＥＸＰＦを組み合わせたものにリプレースすることとすれば、記憶するＢＴＢエントリの数を多くすることなく、すなわち、予測機構の回路面積の増大がなく、予測機構の予測確率を上昇させることになる。
なお、上記では、２個のＢＴＢエントリについて、ｔａｋｅｎ確率が低いか否かの判断をしたが、ＢＴＢエントリのｔａｋｅｎ確率とは関係なく、優先度を設けずに順番に選択ることであってもよい。さらに、ランダムにリプレース対象とするＢＴＢエントリを一つに絞ってもよい。さらに、カウンタ値が低いＢＴＢエントリの内、後に説明するＬＲＵ（Late Recently Used）管理回路により、最後に参照された時刻が古いＢＴＢエントリに対象を絞ってもよい。
オペレーションｏｐ１７０においては、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は、すでに登録されており、分岐命令（ｉｎｓｔｒｕｃｔｉｏｎ）の格納アドレスが一致するＢＴＢエントリの内、ＬＲＵ管理回路により最後に参照された時刻が古いＢＴＢエントリを検出する。そこで、最後に参照された時刻が古いＢＴＢエントリを、新しく登録しようするＥＸｔａｒｇｅｔ、ＥＸＩＡ、及び、ＥＸＰＦを組み合わせたものに置き換える。その後、オペレーションｏｐ１９０へ進む。
なお、上記のおいては、参照された時刻によって、古いＢＴＢエントリか新しいＢＴＢエントリかを検出したが、参照された時刻に基づいて設定された順序情報によって、古いＢＴＢエントリか新しいＢＴＢエントリかを検出することとしてもよい。
【００３１】
オペレーションｏｐ１８０においては、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５は、すでに登録されており、分岐命令（ｉｎｓｔｒｕｃｔｉｏｎ）の格納アドレスが一致するＢＴＢエントリの内、ｔａｋｅｎ確率が低い（プロファイルに対するカウンタ値が低い）ＢＴＢエントリを、ＥＸｔａｒｇｅｔ、ＥＸＩＡ、及び、ＥＸＰＦを組み合わせたものに置き換える。その後、オペレーションｏｐ１９０へ進む。
オペレーションｏｐ１９０においては、その置き換えた後のＢＴＢエントリにおけるプロファイル（履歴情報）を初期化する。初期化とは、プロファイルのカウンタ値を予め決められた値に設定することをいい、例えば、カウンタ値を”１１”（ストロングリーｔａｋｅｎ（分岐可能性大））に設定する。
【００３２】
図４はＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に含まれるＢＴＢエントリ管理回路２００を示す回路ブロック図である。
ＢＴＢエントリ管理回路２００はｃｏｎｄｉｔｉｏｎ−ｃｏｄｅ−ｒｅｓｉｓｔｅｒ２１０、ＬＲＵ管理回路２３０、ＢＴＢ２４０、２５０、リプレース制御回路２６０、マッチング検出回路２８０、２９０、マルチプレクサ３００、及び、制御回路３１０から構成されている。
【００３３】
命令プリフェッチ段階において、ＢＴＢエントリ管理回路２００は、フェッチした分岐条件を示す命令に対して、分岐先アドレスの予測を行う。詳細については後に図５を用いて説明する。
【００３４】
パイプラインの命令実行段階（ＥＸ）において、ＢＴＢエントリ管理回路２００は、分岐予測結果に基づいて、ＢＴＢエントリの履歴情報の更新、ＢＴＢエントリのリプレース、ＢＴＢエントリの更新又はリプレースを行うかの判断をする。
ｃｏｎｄｉｔｉｏｎ−ｃｏｄｅ−ｒｅｓｉｓｔｅｒ２１０は分岐命令に対する分岐条件を記憶するレジスタである。そして、ｃｏｎｄｉｔｉｏｎ−ｃｏｄｅ−ｒｅｓｉｓｔｅｒ２１０は、分岐条件を制御回路３１０に出力する。
【００３５】
制御回路３１０は、分岐命令を実行する際に、図４を用いて説明した判断を行う。そして、ＢＴＢ２４０、２５０にＢＴＢエントリを登録するか、又は、すでに登録済みのＢＴＢエントリを、現在実行中の分岐命令に関連するＢＴＢエントリにリプレースする必要があるか、又は、すでに登録済みのＢＴＢエントリのプロファイル（履歴情報）を更新する必要があるかを判断するため、リプレース制御回路２６０及びＬＲＵ管理回路２３０へ活性化信号を出力する。
【００３６】
まず、制御回路３１０はｃｏｎｄｉｔｉｏｎ−ｃｏｄｅ−ｒｅｓｉｓｔｅｒ２１０から分岐条件を受け取り、ＢＴＡＧ２２から受け取ったＥＸＢＣＤとから、分岐ｔａｋｅｎとなったか否かを判断する。さらに、マッチング検出回路２８０のマッチング信号によって、分岐ｔａｋｅｎとならなかった分岐命令と分岐予測の組合せに関わるＢＴＢエントリがＢＴＢ２４０又はＢＴＢ２５０に登録されていたかを判断し、さらに、分岐ｔａｋｅｎとなった分岐命令と分岐予測の組合せに関わるＢＴＢエントリがＢＴＢ２４０又はＢＴＢ２５０に登録されていたかを判断する。
その結果、分岐ｔａｋｅｎとならなかった場合において、さらに、その分岐命令と分岐予測の組合せに関わるＢＴＢエントリがＢＴＢ２４０又はＢＴＢ２５０に登録されていた場合には、制御回路３１０はリプレース制御回路２６０に活性化信号を送付し、ＥＸＩＡをアドレスとしてＢＴＢ２４０又はＢＴＢ２５０にアクセスし、そのアドレスで指定された記憶領域に登録されているＢＴＢエントリのＰＦ(プロファイル:履歴情報)を、履歴情報のカウント値を下げるように、書き換える。
【００３７】
一方、分岐ｔａｋｅｎとなった場合において、さらに、その分岐命令と分岐予測の組合せに関わるＢＴＢエントリがＢＴＢ２４０又はＢＴＢ２５０に登録されていた場合には、制御回路３１０はリプレース制御回路２６０に活性化信号を送付し、ＢＴＢ２４０又はＢＴＢ２５０に登録されているＢＴＢエントリのＰＦ(プロファイル:履歴情報)を、履歴情報のカウント値を上げるように書き換える。すなわち、制御回路３１０はＥＸＰＦのカウント値を一つあげた後、ＥＸＰＦをリプレース制御回路２６０に送り、リプレース制御回路２６０はＢＴＢエントリのＰＦをＥＸＰＦに置き換える。
【００３８】
ところで、分岐ｔａｋｅｎとなった場合において、さらに、マッチング検出回路２８０のマッチング信号より判断して、その分岐命令と分岐予測の組合せに関わるＢＴＢエントリがＢＴＢ２４０又はＢＴＢ２５０に登録されていなかった場合には、ＥＸＩＡをアドレスとしてＢＴＢ２４０又はＢＴＢ２５０にアクセスし、ＢＴＢ２４０又はＢＴＢ２５０に空き領域があるか否かを判断する。
ＢＴＢ２４０又はＢＴＢ２５０に空き領域があった場合は、分岐ｔａｋｅｎとなった、その分岐命令と分岐予測の組合せに関わるＢＴＢエントリを空き領域に登録するように、制御回路３１０はＥＸＩＡをアドレスとして使用し、リプレース制御回路２６０を制御する。
【００３９】
ＢＴＢ２４０又はＢＴＢ２５０に空き領域がなかった場合は、制御回路３１０はＥＸＩＡで示されたＢＴＢ２４０の記憶領域に登録されているＢＴＢエントリ及びＢＴＢ２５０の領域に登録されているＢＴＢエントリを検出する。上記、リプレース制御回路２６０は検出されたＢＴＢエントリのＰＦ(プロファイル:履歴情報)を受け取り、２個のＢＴＢエントリの内どちらのカウンタ値が小さいか、すなわち、どちらのｔａｋｅｎ確率が小さいか、又は、同一かを判断する。そして、カウンタ値が小さいほうのＢＴＢエントリを、入力されたＥＸＩＡ、ＥＸｔａｒｇｅｔ、及び、ＥＸＰＦを組み合わせたものに置き換える。
【００４０】
一方、カウンタ値が同一と判断したときには、制御回路３１０はＬＲＵ管理回路２３０を活性化する信号を出力する。ＬＲＵ管理回路２３０はＥＸＩＡで示されたＢＴＢ２４０の記憶領域に登録されているＢＴＢエントリの登録時刻及びＢＴＢ２５０の領域に登録されているＢＴＢエントリの登録時刻をリプレース制御回路２６０に送信する。リプレース制御回路２６０は、ＢＴＢエントリの登録時刻に基づいて、上記の２つのＢＴＢエントリの内、古い登録時刻を有するＢＴＢエントリを特定する。リプレース制御回路２６０は、古い登録時刻を有するＢＴＢエントリを、分岐ｔａｋｅｎとなった、その分岐命令と分岐予測の組合せに関わるＢＴＢエントリ（入力されたＥＸＩＡ、ＥＸｔａｒｇｅｔ、及び、ＥＸＰＦを組み合わせたもの）にリプレースする。
ところで、上記では、ＬＲＵ管理回路２３０における登録時刻の新しい、古いによって置き換えるＢＴＢエントリを選択したが、ＢＴＢ２４０に記憶されたＢＴＢエントリと、ＢＴＢ２５０に記憶されたＢＴＢエントリと、を交互に選択するラウンドロピンアルゴリズムによって置き換えるＢＴＢエントリを選択してもよい。さらに、ＢＴＢ２４０に記憶されたＢＴＢエントリと、ＢＴＢ２５０に記憶されたＢＴＢエントリとから、ランダムアルゴリズムによって、置き換えるＢＴＢエントリを選択してもよい。
【００４１】
なお、上記において、分岐ｔａｋｅｎとなった、その分岐命令と分岐予測の組合せに関わるＢＴＢエントリをＢＴＢ２４０又はＢＴＢ２５０に登録するとき、及び、登録時刻が古いＢＴＢエントリをリプレースするときには、新しいＢＴＢエントリのＰＦ（履歴情報）をリプレース制御回路２６０は、初期値にリセットする。例えば、初期値とはストロングリーｔａｋｅｎ（分岐可能性大）に相当するカウント値”１１”とすることが考えられる。
また、ＬＲＵ管理回路２３０は、ＢＴＢ２４０又はＢＴＢ２５０において新しＢＴＢエントリにリプレースが行われるときに、登録時刻を記録する。ただし、登録時刻そのものを記録するのみに限られず、登録時刻に応じた登録順序情報を記録することであってもよい。
【００４２】
ところで、図４において、ＢＴＢエントリ管理回路２００はＢＴＢエントリを記憶する回路として、ＢＴＢ２４０、２５０を含むこととしているが、ＢＴＢエントリを記憶する回路は２個に限られず、３個以上の複数であってもよい。ＢＴＢエントリを記憶する回路が３個以上ある場合には、ＥＸＩＡをアドレスとして、同時にすべてのＢＴＢエントリを記憶する回路にアクセスすると、ＢＴＢエントリを記憶する回路の個数分のＢＴＢエントリを取得する。上記の場合において、複数のＢＴＢエントリの内、どのＢＴＢエントリをリプレースするかを決定するには、ｔａｋｅｎ確率の大小、すなわち、カウンタ値の大小によって決定することはいうまでもない。
【００４３】
図５はＢＴＢエントリ管理回路２００の予測動作について詳細に説明する図である。なお、図５は図４の回路ブロック図から予測動作を行う回路ブロックを抜き出した回路ブロック図である。
命令プリフェッチ段階において、ＢＴＢエントリ管理回路２００は、フェッチした分岐条件を示す命令に対して、分岐先アドレスの予測を行う。
【００４４】
ＢＴＢ２４０、２５０はＢＴＢエントリを記憶し、リプレース制御回路２６０からのアドレスに従って、ＢＴＢエントリを読み出す回路である。
制御回路３１０はＩＦＩＡを受け取ると、活性化信号をリプレース制御回路２６０に対して送信する。リプレース制御回路２６０は、ＩＦＩＡの１２ビット目から３１ビット目までをアドレスとして使用し、そのアドレスにより指定されたＢＴＢ２４０の領域及びＢＴＢ２５０の領域からＢＴＢエントリを読み出す。ここで、ＢＴＢエントリは５３ビットからなり、ＩＦＰＦに相当する部分は２ビット、ＩＦｔａｒｇｅｔに相当する部分は３０ビット、ＩＦＩＡの１２ビット目から３１ビット目に相当する部分は２０ビット、ＶＦＬＡＧに相当する部分は１ビットである。従って、分岐予測の精度をあげるために、ＢＴＢエントリ数を増やすと、ＢＴＢ２４０、２５０が占める面積は増加する。
【００４５】
マッチング検出回路２８０、２９０はＢＴＢ２４０、２５０から出力されるＩＡ３１−１２と、入力されたＩＦＩＡの１２ビット目から３１ビット目を比較し、それぞれ、一致信号をマルチプレクサ３００及び制御回路３１０へ出力する回路である。ただし、一致信号を出力するのは、ＢＴＢエントリのＶＦＬＡＧの論理が”１”のときのみである。
マルチプレクサ３００はＢＴＢ２４０、２５０それぞれから出力される一致信号、ＩＦｔａｒｇｅｔ、及び、ＩＦＰＦを受け、ＢＴＢ２４０、２５０から出力されたＩＦＰＦのカウンタ値が大きい方に対応するＩＦｔａｒｇｅｔと、そのＩＦＰＦを出力する。なお、ＩＦｔａｒｇｅｔはＳｅｌｅｃｔｏｒ２４へ出力され、ＩＦＰＦはレジスタ１４へ出力される。
【００４６】
ところで、図５において、ＢＴＢエントリ管理回路２００はＢＴＢエントリを記憶する回路として、ＢＴＢ２４０、２５０を含むこととしているが、ＢＴＢエントリを記憶する回路は２個に限られず、３個以上の複数であってもよい。ＢＴＢエントリを記憶する回路が３個以上ある場合には、ＩＦＩＡをアドレスとして、同時にすべてのＢＴＢエントリを記憶する回路にアクセスすると、ＢＴＢエントリを記憶する回路の個数分のＢＴＢエントリを取得する。上記の場合においても、複数のＢＴＢエントリの内、どのＢＴＢエントリをリプレースするかを決定するには、ｔａｋｅｎ確率の大小、すなわち、ＩＦＰＦのカウンタ値の大小によって決定することはいうまでもない。
【００４７】
以上より、分岐予測回路（ＢＴＢエントリ管理回路２００）は、
分岐命令と、分岐予測と、分岐予測に示された分岐がおきる可能性の程度と、を含む情報（ＢＴＢエントリ）を記憶する第１記憶部（ＢＴＢ２４０）及び、第２記憶部（ＢＴＢ２５０）と、
上記分岐命令により設定された分岐条件（ｃｏｎｄｉｔｉｏｎ−ｃｏｄｅ−ｒｅｓｉｓｔｅｒ２１０に格納されたｃｏｎｄｉｔｉｏｎ  ｃｏｄｅ）と、実現した分岐（ＥＸＢＣＤ）とから、上記分岐予測が実現したか否かを判断し、上記判断及び上記分岐予測に示された分岐がおきる可能性の程度に応じて上記第１記憶部又は上記第２記憶部の内の一つの上記情報の書き換えを制御する制御回路（制御回路３１０）と、
上記制御回路（制御回路３１０）による制御を受けて、上記第１記憶部又は第２記憶部内の上記情報の書き換えを行う書き換え回路と、を備えることを特徴とする。
【００４８】
さらに、上記分岐予測に示された分岐がおきる可能性の程度は、上記分岐予測が実現した場合又は実現しなかった場合に、更新されることを特徴とする。
【００４９】
分岐予測方法は、
分岐命令、分岐予測、及び、分岐予測に示された分岐がおきる可能性の程度を表す情報（ＢＴＢエントリ）を記憶する第１記憶部（ＢＴＢ２４０）及び第２記憶部（ＢＴＢ２５０）を含み分岐予測回路（ＢＴＢエントリ管理回路２００）を有し、上記の分岐命令を実行する処理装置（コンピュータ１０）において、
上記情報を第１記憶部又は第２記憶部に記憶する情報記憶工程と、
上記分岐命令により設定された分岐条件（ｃｏｎｄｉｔｉｏｎ−ｃｏｄｅ−ｒｅｓｉｓｔｅｒ２１０に格納されたｃｏｎｄｉｔｉｏｎ  ｃｏｄｅ）と、実現した分岐（ＥＸＢＣＤ）とから、上記分岐予測が実現したかを判断する工程と、
上記判断及び上記分岐予測に示された分岐がおきる可能性の程度に応じて上記第１記憶部又は上記第２記憶部の内の一つの上記情報の書き換えを行う書き換え工程と、
上記分岐命令を処理装置で実行する際に、上記情報に応じて分岐予測を行う工程と、
を備えることを特徴とする。
【００５０】
さらに、
上記分岐予測方法は、第１記憶部における上記情報と、第２記憶部における上記情報について、記憶順序を記憶する工程を含み、
前記書き換え工程において、
前記上記分岐予測に示された分岐がおきる可能性の程度が、第１記憶部における上記情報と、第２記憶部における上記情報とで、同程度であった場合に、前記記憶順序に応じて、上記第１記憶部又は上記第２記憶部の内の一つの上記情報の書き換えを行うことを特徴とする。
【００５１】
さらに、上記分岐予測方法は、
前記書き換え工程において、
前記上記分岐予測に示された分岐がおきる可能性の程度が、第１記憶部における上記情報と、第２記憶部における上記情報とで、同程度であった場合に、上記第１記憶部に記憶された前記情報又は上記第２記憶部に記憶された前記情報の内の一つを順番に選択して書き換えを行うことを特徴とする。
【００５２】
さらに、上記分岐予測方法は、
前記書き換え工程において、
前記上記分岐予測に示された分岐がおきる可能性の程度が、第１記憶部における上記情報と、第２記憶部における上記情報とで、同程度であった場合に、上記第１記憶部に記憶された前記情報又は上記第２記憶部に記憶された前記情報の内の一つをランダムに選択して書き換えを行うことを特徴とする。
【００５３】
ｔａｋｅｎ確率が低いか否かの判断をせずに最後に参照された時刻が古いか否かによってＢＴＢエントリのリプレースを行うと、分岐のｔａｋｅｎ確率が確実な場合にも、ＢＴＢエントリの入れ替えが行われることになる。すなわち、分岐のｔａｋｅｎ確率が低いＢＴＢエントリがＢＴＢ内に残ることになるため、予測機構の分岐予測の精度が低くなってしまう。
しかし、上記のように、分岐のｔａｋｅｎ確率が高いＢＴＢエントリを残すこととすると、ＢＴＢエントリ管理回路２００で管理する過去の履歴情報の内、分岐予測の精度向上に有効な情報がＢＴＢ内に残る確率をあげる効果がある。
さらに、入れ替えの回数を減少させるため、記憶するＢＴＢエントリを多くすることが考えられる。その場合、ＢＴＢエントリはインストラクションアドレスを表す２０ビットと、ターゲットアドレスを表す３０ビットと、プロファイルを表す２ビットと、バリットを表す１ビットの合計５３ビットからなっているため、ＢＴＢの記憶領域が大幅に増加することになり、ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ２５に含まれる予測機構を構成する回路の面積が増大することになる。
従って、すでに登録されているＢＴＢエントリと、新しく登録したいＢＴＢエントリとについて、ｔａｋｅｎ確率が低いか否かの判断をおこなって、ｔａｋｅｎ確率が低いものとリプレースをすることとすれば、記憶するＢＴＢエントリの数を多くすることなく、すなわち、予測機構の回路面積の増大がなく、予測機構の予測確率を上昇させることになる。
【産業上の利用可能性】
【００５４】
分岐予測回路に、分岐予測の精度向上に有効な情報が残る確率をあげたことを特徴とする分岐予測手法及びその分岐予測手法を実行する分岐予測回路が提供される。
【符号の説明】
【００５５】
１１  Ｉ−Ｃａｃｈｅ
１２  Ｉｎｓｔｒｕｃｔｉｏｎ
１３、１７、２０  Ａｄｄ
１４、１８、２１  ＰＦ
１５  Ｄｅｃｏｄｅ
１６  Ｉｍｍｅｄａｔｅ
１９  Ｉｍｍｅｄｉａｔｅ
２２  ＢＴＡＧ
２３  ＩＦＥＡＧ
２４  Ｓｅｌｅｃｔｏｒ
２５  ＢｒａｎｃｈＰｒｅｄｉｃｔｉｏｎ
２６  ＲｅｇＮｏ
２７  ＲｅｇｉｓｔｅｒＦｉｌｅ
２８  Ｓｒｃ
２９  ＡＬＵ／ＥＡＧ
３０  Ｒｅｓｕｌｔ
３１  Ｄ−Ｃａｃｈｅ
３２  Ｓｅｌｅｃｔｏｒ
３３  Ｗｒｉｔｅｄａｔａ
４０、５０  パイプライン
ｏｐ１００、ｏｐ１１０、ｏｐ１２０、ｏｐ１３０、ｏｐ１４０、ｏｐ１５０、ｏｐ１６０、ｏｐ１７０、ｏｐ１８０、ｏｐ１９０  オペレーション
２００  ＢＴＢエントリ管理回路
２１０  ｃｏｎｄｉｔｉｏｎ−ｃｏｄｅ−ｒｅｓｉｓｔｅｒ
２２０  情報履歴の更新回路
２３０  ＬＲＵ管理回路
２４０、２５０  ＢＴＢ
２６０  リプレース制御回路
２７０  ｔａｋｅｎ情報管理回路
２８０、２９０  マッチング検出回路
３００  マルチプレクサ
３１０  制御回路
３２０、３３０  シフト回路
【図１】
2011209774.tif 000003
【図２】
2011209774.tif 000004
【図３】
2011209774.tif 000005
【図４】
2011209774.tif 000006
【図５】
2011209774.tif 000007