(57)【要約】【課題】分岐命令のアドレスと該分岐命令の予測分岐先のアドレスとの対応表を有するブランチヒストリを用いて分岐命令の分岐先を予測する場合に、低コストで精度の高い予測を高速におこなうこと。【解決手段】分岐履歴記憶部２１が分岐命令ごとに過去複数回の分岐結果を分岐履歴として記憶し、分岐命令の処理が完了すると分岐履歴更新部２２ａが処理結果に基づいてその分岐命令に対応する分岐履歴記憶部２１の分岐履歴を更新し、ブランチヒストリ更新部２２ｂが更新された分岐履歴に基づいてブランチヒストリ１０を更新する構成とする。また、分岐履歴は、最近の連続分岐成立回数および最近の連続分岐不成立回数を記憶する構成とする。【選択図】　　　図２
2004038323.tif 000002
【特許請求の範囲】
【請求項１】
分岐命令のアドレスと該分岐命令の予測分岐先のアドレスとの対応表を有するブランチヒストリを用いて該分岐命令の分岐先を予測する分岐予測装置であって、
前記分岐命令の過去の複数回の分岐結果を分岐履歴として記憶した分岐履歴記憶手段と、
前記分岐履歴記憶手段により記憶された分岐履歴に基づいて前記分岐命令の分岐方向を予測し、該予測した分岐方向に基づいて前記対応表を更新するブランチヒストリ更新手段と、
を備えたことを特徴とする分岐予測装置。
【請求項２】
前記分岐履歴記憶手段は、分岐条件が成立するか否かの二者択一分岐命令だけを前記分岐履歴に記憶する対象とすることを特徴とする請求項１に記載の分岐予測装置。
【請求項３】
前記分岐履歴記憶手段は、前記分岐命令ごとに、最近の連続分岐成立回数および最近の連続分岐不成立回数を記憶し、前記ブランチヒストリ更新手段は、前記最近の連続分岐成立回数および最近の連続分岐不成立回数に基づいて前記分岐命令の分岐成立不成立を予測することを特徴とする請求項１に記載の分岐予測装置。
【請求項４】
前記ブランチヒストリ更新手段は、前記分岐命令の直近の連続分岐成立回数が最近の連続分岐成立回数に等しい場合には次回は分岐不成立と予測し、前記分岐命令の直近の連続分岐不成立回数が最近の連続分岐不成立回数に等しい場合には次回は分岐成立と予測することを特徴とする請求項３に記載の分岐予測装置。
【請求項５】
前記分岐履歴記憶手段により記憶された分岐履歴が初期構築状態にあるか否かを判定する分岐履歴構築段階判定手段をさらに備え、前記ブランチヒストリ更新手段は、前記分岐履歴が初期構築状態にある場合には、前記対応表を更新しないことを特徴とする請求項１に記載の分岐予測装置。
【請求項６】
前記ブランチヒストリ更新手段は、前記分岐命令の分岐予測が不成立である場合には、該分岐命令を前記対応表に登録する対象としないことを特徴とする請求項１に記載の分岐予測装置。
【請求項７】
分岐命令のアドレスと該分岐命令の予測分岐先のアドレスとの対応表を有するブランチヒストリを用いて該分岐命令の分岐先を予測する分岐予測方法であって、
前記分岐命令の過去の複数回の分岐結果を分岐履歴として記憶し、該記憶した分岐履歴を前記分岐命令の処理が完了した時点で該処理の結果に基づいて更新する分岐履歴更新工程と、
前記分岐履歴更新工程により更新された分岐履歴に基づいて前記分岐命令の分岐方向を予測し、該予測した分岐方向に基づいて前記対応表を更新するブランチヒストリ更新工程と、
を含んだことを特徴とする分岐予測方法。
【請求項８】
分岐条件が成立するか否かの二者択一分岐命令だけを前記分岐履歴に記憶する対象とすることを特徴とする請求項７に記載の分岐予測方法。
【請求項９】
前記分岐履歴は、前記分岐命令ごとに、最近の連続分岐成立回数および最近の連続分岐不成立回数を記憶し、前記ブランチヒストリ更新工程は、前記最近の連続分岐成立回数および最近の連続分岐不成立回数に基づいて前記分岐命令の分岐成立不成立を予測することを特徴とする請求項７に記載の分岐予測方法。
【請求項１０】
前記ブランチヒストリ更新工程は、前記分岐命令の分岐予測が不成立である場合には、該分岐命令を前記対応表に登録する対象としないことを特徴とする請求項７に記載の分岐予測方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、分岐命令のアドレスと該分岐命令の予測分岐先のアドレスとの対応表を有するブランチヒストリを用いて該分岐命令の分岐先を予測する分岐予測装置および分岐予測方法に関し、特に、低コストで精度の高い予測を高速におこなうことができる分岐予測装置および分岐予測方法に関する。
【０００２】
【従来の技術】
パイプライン処理手法以降の高度な命令処理手法を採用した情報処理装置においては、一つの命令の実行を待たずに、投機的に後続命令の処理を開始することで性能の向上を図ってきた。
【０００３】
しかし、分岐命令を実行する場合には、命令を実行した後でないと次に実行する命令アドレスが判明しないため、後続命令の処理を開始することができない。そこで、次に実行する命令アドレスを予測することによって、分岐命令を実行する前に後続命令の処理の開始を可能とする技術が注目されている。
【０００４】
たとえば、特開平６−８９１７３号公報には、ブランチヒストリを用いて次に実行する命令アドレスを予測する技術が開示されている。この従来技術では、過去に実行した分岐命令のアドレスとその分岐先アドレスとを対応させてブランチヒストリに登録し、ブランチヒストリに登録された分岐命令を新たに実行する場合には、その分岐命令に対応する分岐先アドレスを用いて次に実行する命令アドレスを予測している。
【０００５】
また、分岐予測の精度を向上するために、分岐命令の過去一回の分岐先だけでなく、各分岐命令の過去の複数回数の分岐履歴や、直前に実行された複数個数の分岐命令の分岐シーケンスも記憶するグローバルヒストリも用いられている。グローバルヒストリを利用すると、過去の分岐の規則性に基づいて次の分岐命令の分岐先を予測することができ、より精度の高い予測が可能となる。
【０００６】
しかし、グローバルヒストリでは、登録あるいは更新された分岐履歴や分岐シーケンスがいつ参照されるのかを、登録あるいは更新時には判断できない。ゆえにグローバルヒストリで性能を大きく向上させるためには命令フェッチ要求されうる範囲に対して十分余裕のある数だけ分岐命令を登録できる必要がある。しかしながら、コストの制約から使用できるハードウェア量には限界があるので、登録できる分岐命令の数が限られることとなる。このため、グローバルヒストリとブランチヒストリを併用し、グローバルヒストリに登録されている分岐命令についてはグローバルヒストリに基づいて予測をおこない、グローバルヒストリに登録されていない分岐命令についてはブランチヒストリに基づいて予測をおこなう手法が用いられている。
【０００７】
【発明が解決しようとする課題】
しかしながら、グローバルヒストリとブランチヒストリを併用した場合にも、前述のようにコストの制約から、グローバルヒストリの有する高い予測機能を利用できる分岐命令は限られるという問題がある。また、グローバルヒストリは、複雑な予測処理のために処理時間がかかり、ブランチヒストリと併用する場合には、さらに、両方の予測から一つの予測を得るための処理時間が必要となり、分岐予測先の命令フェッチ要求が遅くなるという問題がある。
【０００８】
なお、グローバルヒストリに登録する分岐命令の数を増やすために、グローバルヒストリへの分岐先アドレスの登録を省き、分岐方向だけを予測することも考えられる。たとえば、米国特許６，０５５，６２９号公報には、各分岐命令の分岐方向の履歴や複数の分岐命令の分岐方向のシーケンスを記憶し、これらの規則性に基づいて分岐方向を予測する技術が開示されている。しかし、かかる場合には、分岐命令をデコードするまで分岐先アドレスが判明せず、命令のフェッチが遅くなり、分岐方向を正しく予想することができても性能向上に結びつかないという問題がある。
【０００９】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、低コストで精度の高い予測を高速におこなうことができる分岐予測装置および分岐予測方法を提供することを目的とする。
【００１０】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、本発明は、分岐命令のアドレスと該分岐命令の予測分岐先のアドレスとの対応表を有するブランチヒストリを用いて該分岐命令の分岐先を予測する分岐予測装置であって、前記分岐命令の過去の複数回の分岐結果を分岐履歴として記憶した分岐履歴記憶手段と、前記分岐履歴記憶手段により記憶された分岐履歴に基づいて前記分岐命令の分岐方向を予測し、該予測した分岐方向に基づいて前記対応表を更新するブランチヒストリ更新手段と、を備えたことを特徴とする。
【００１１】
また、本発明は、分岐命令のアドレスと該分岐命令の予測分岐先のアドレスとの対応表を有するブランチヒストリを用いて該分岐命令の分岐先を予測する分岐予測方法であって、前記分岐命令の過去の複数回の分岐結果を分岐履歴として記憶し、該記憶した分岐履歴を前記分岐命令の処理が完了した時点で該処理の結果に基づいて更新する分岐履歴更新工程と、前記分岐履歴更新工程により更新された分岐履歴に基づいて前記分岐命令の分岐方向を予測し、該予測した分岐方向に基づいて前記対応表を更新するブランチヒストリ更新工程と、を含んだことを特徴とする。
【００１２】
かかる発明によれば、分岐命令の過去の複数回の分岐結果を分岐履歴として記憶し、記憶した分岐履歴に基づいて分岐命令の分岐方向を予測し、予測した分岐方向に基づいて、分岐命令のアドレスと分岐命令の予測分岐先のアドレスとの対応表を更新することとしたので、分岐確定時に分岐履歴を用いた予測結果をブランチヒストリに反映することができる。したがって、命令フェッチ要求時には大容量のブランチヒストリに既に予測状況が反映されていることになり、命令フェッチがおこなわれる範囲に対して、十分容量の大きいブランチヒストリがカバーする。ゆえに、分岐履歴を記憶する分岐命令の数は非常に少なくても高精度な予測が可能であり、低コストで精度の高い予測をおこなうことができる。また、このことで命令フェッチ要求時には複雑な予測処理をおこなう必要がなくなり、高速に分岐予測をおこなうことができる。
【００１３】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係る分岐予測装置および分岐予測方法の好適な実施の形態を詳細に説明する。
【００１４】
まず、本実施の形態に係る分岐予測の原理について説明する。図１は、本実施の形態に係る分岐予測の原理を説明するための説明図である。同図に示すように、この分岐予測では、命令フェッチ部が、命令フェッチアドレス生成部により生成された命令フェッチアドレスを用いて、命令フェッチ要求を出すと同時にブランチヒストリ１０を索引する。
【００１５】
そして、命令フェッチアドレスに対応する分岐命令がブランチヒストリ１０に登録されている場合には、ブランチヒストリ１０により予測された分岐先の命令アドレスを読み出し、次の命令フェッチは、この命令アドレスに基づいておこなう。
【００１６】
一方、フェッチされた分岐命令は、命令デコーダによりデコードされ、分岐命令制御部によって処理される。そして、分岐命令制御部によって分岐命令の処理が完了すると、分岐の成立不成立などの分岐情報が予測更新部２０に渡される。
【００１７】
予測更新部２０は、各分岐命令の分岐履歴を記憶しており、受け取った分岐情報を用いて対応する分岐命令の分岐履歴を更新する。そして、更新した分岐履歴に基づいて、この分岐命令の次回の分岐方向を予測し、予測した分岐方向に基づいてブランチヒストリ１０を更新する。
【００１８】
このように、本実施の形態では、予測更新部２０は、グローバルヒストリのように分岐履歴を用いて直接分岐先を予測するのではなく、分岐履歴を用いて分岐方向を予測し、その予測結果に基づいてブランチヒストリ１０を更新することとしている。
【００１９】
このため、この予測更新部２０は、分岐確定時に分岐履歴を用いた予測結果をブランチヒストリ１０に反映することができる。したがって、命令フェッチ要求時には、命令フェッチがおこなわれる範囲を、十分容量が大きなブランチヒストリ１０でカバーすることができ、分岐先アドレスを記憶するグローバルヒストリと比較して、登録できる分岐命令の数が非常に少ない場合でも高精度の予測をおこなうことができる。
【００２０】
また、命令フェッチ要求時には、ブランチヒストリ１０の索引だけが必要であり、グローバルヒストリとブランチヒストリ１０を索引した後に両方の予測から一つの予測を得るための処理を不要とすることができ、ハードウェア量を少なくするとともに、命令フェッチの遅れを防ぐことができる。
【００２１】
さらに、この予測更新部２０は、命令フェッチ部の設計には影響を与えることなく、従来からのブランチヒストリ１０による予測機構を変更することなく使用することができる。
【００２２】
次に、本実施の形態に係る分岐予測装置の構成について説明する。図２は、本実施の形態に係る分岐予測装置の構成を示す機能ブロック図である。同図に示すように、この分岐予測装置２００は、ブランチヒストリ１０と予測更新部２０とを有する。
【００２３】
ブランチヒストリ１０は、過去に実行された分岐命令ごとに、分岐命令アドレスと予測分岐先のアドレスを対応させて記憶した記憶部であり、命令フェッチ部により取り出される命令データに分岐命令が含まれる場合に、その分岐命令の分岐先アドレスを予測するために用いられる。このブランチヒストリ１０は、連想記憶であり、命令アドレスから予測分岐先のアドレスを索引することができる。
【００２４】
図３は、ブランチヒストリ１０のエントリのデータ構造の一例を示す図である。同図に示すように、ブランチヒストリ１０のエントリは、分岐命令アドレスと、予測分岐先アドレスとから構成される。
【００２５】
分岐命令アドレスは、分岐命令の命令アドレスであり、ブランチヒストリ１０の索引として用いられる。また、予測分岐先アドレスは、過去にこの分岐命令が実行された時の分岐先アドレスであり、次にこの分岐命令を実行する場合に、分岐先アドレスの予測値として用いられる。
【００２６】
なお、このブランチヒストリ１０には、次回の実行で分岐が成立すると予測される分岐命令だけが登録され、分岐が成立しないと予想される分岐命令は登録されない。
【００２７】
一方、グローバルヒストリの場合には、次回の分岐予測にかかわらず全ての分岐命令を登録する必要があり、このブランチヒストリ１０は、グローバルヒストリの半分のエントリ数で同等の予測をおこなうことができる。
【００２８】
予測更新部２０は、各分岐命令の分岐履歴に基づいて次回の分岐方向を予測し、この予測結果に基づいてブランチヒストリ１０を更新する処理部であり、分岐履歴記憶部２１と制御部２２とを有する。
【００２９】
分岐履歴記憶部２１は、過去に実行された分岐命令ごとに、過去の分岐方向の履歴を記憶した記憶部である。なお、分岐履歴記憶部２１の詳細については後述する。
【００３０】
制御部２２は、分岐履歴記憶部２１を用いて分岐予測をおこない、その予測結果に基づいてブランチヒストリ１０を更新する処理部であり、分岐履歴更新部２２ａとブランチヒストリ更新部２２ｂとを有する。
【００３１】
分岐履歴更新部２２ａは、分岐命令の処理結果に基づいて、その分岐命令に関する分岐履歴記憶部２１の分岐履歴を更新する処理部であり、分岐命令の処理が完了した時点で起動される。
【００３２】
ブランチヒストリ更新部２２ｂは、分岐履歴記憶部２１に記憶された分岐履歴が更新された分岐命令の次回の分岐方向を予測し、予測した次回の分岐方向に基づいてその分岐命令についてのブランチヒストリ１０の情報を更新する処理部である。
【００３３】
このブランチヒストリ更新部２２ｂが分岐履歴に基づく分岐予測を用いてブランチヒストリ１０を更新することにより、ブランチヒストリ１０は、グローバルヒストリを用いた場合と同等の分岐予測をおこなうことができ、分岐予測の精度を向上することができる。
【００３４】
次に、分岐履歴記憶部２１の詳細について説明する。図４は、分岐履歴記憶部２１のエントリのデータ構造の一例を示す図である。同図に示すように、分岐履歴記憶部２１のエントリは、Ｉ−Ａｄｄｒｅｓｓ、Ｔａｋｅｎ、Ｎ−Ｔａｋｅｎ、Ｃｕｒｒｅｎｔ、Ｃｕｒｒ．Ｄｉｒから構成される。
【００３５】
Ｉ−Ａｄｄｒｅｓｓは、このエントリに対応する分岐命令のアドレスである。ここで、このアドレスは、アドレス全体である必要はなく、このエントリと分岐命令を対応付けることができれば、アドレスの部分ビット列であってもかまわない。
【００３６】
Ｔａｋｅｎは、最近の連続分岐成立の回数であり、Ｎ−Ｔａｋｅｎは、最近の連続分岐不成立の回数である。Ｃｕｒｒ．Ｄｉｒは、前回の分岐命令の実行で分岐が成立したか否かを示す１ビットの情報であり、Ｃｕｒｒｅｎｔは、Ｃｕｒｒ．Ｄｉｒに示す分岐成立または不成立が、前回の分岐命令実行まで連続して発生している回数である。
【００３７】
ここで、Ｔａｋｅｎ、Ｎ−ＴａｋｅｎおよびＣｕｒｒｅｎｔについて、具体例を用いて説明する。図５は、Ｔａｋｅｎ、Ｎ−ＴａｋｅｎおよびＣｕｒｒｅｎｔを説明するための説明図である。なお、ここでは、Ｃｕｒｒ．Ｄｉｒ＝０は、前回の分岐命令の実行で分岐が成立しなかったことを示し、Ｃｕｒｒ．Ｄｉｒ＝１は、前回の分岐命令の実行で分岐が成立したことを示している。また、「Ｔ」は分岐成立を示し、「Ｎ］は分岐不成立を示し、左の方向がより古い分岐履歴を示している。
【００３８】
同図（ａ）は、Ｃｕｒｒ．Ｄｉｒ＝０の場合、すなわち前回の分岐命令の実行で分岐が成立しなかった場合の分岐履歴の一例を示している。同図（ａ）に示すように、直近の２回は、連続して分岐が成立しなかったためＣｕｒｒｅｎｔ＝２となり、その前の６回は、連続して分岐が成立したためＴａｋｅｎ＝６となる。また、さらにその前の５回は、連続して分岐が成立しなかったためＮ−Ｔａｋｅｎ＝５となる。
【００３９】
同様に、同図（ｂ）は、Ｃｕｒｒ．Ｄｉｒ＝１の場合、すなわち前回の分岐命令の実行で分岐が成立した場合の分岐履歴の一例を示している。同図（ｂ）に示すように、直近の２回は、連続して分岐が成立したためＣｕｒｒｅｎｔ＝２となり、その前の３回は、連続して分岐が成立しなかったためＮ−Ｔａｋｅｎ＝３となる。また、さらにその前の６回は、連続して分岐が成立したためＴａｋｅｎ＝６となる。
【００４０】
このように、過去の分岐結果を全て記憶するのではなく、最近の連続する分岐成立および不成立の回数を分岐履歴として記憶することにより、効率良く分岐履歴を記憶することができ、必要となるハードウェアの量を減らすことができる。
【００４１】
次に、図２に示した分岐履歴更新部２２ａによる分岐履歴更新処理の手順について説明する。図６は、図２に示した分岐履歴更新部２２ａによる分岐履歴更新処理の手順を示すフローチャートである。なお、この分岐履歴更新処理は、分岐命令の処理が完了した時点で起動される。
【００４２】
同図に示すように、この分岐履歴更新部２２ａは、分岐命令処理の結果、分岐が成立したか否かを調べ（ステップＳ６０１）、分岐が成立した場合には、Ｃｕｒｒ．Ｄｉｒ＝１であるか否か、すなわち前回この分岐命令が実行された時に分岐が成立したか否かを調べる（ステップＳ６０２）。
【００４３】
そして、前回は分岐が成立していなければ、今回新たに分岐成立が始まることになるので、Ｃｕｒｒｅｎｔの値、すなわちこれまでの分岐不成立の連続回数を、Ｎ−Ｔａｋｅｎにセットし（ステップＳ６０３）、Ｃｕｒｒ．Ｄｉｒを分岐成立に変更し（ステップＳ６０４）、Ｃｕｒｒｅｎｔを１に初期化する（ステップＳ６０５）。これに対して、前回も分岐が成立していれば、分岐成立が前回から連続していることになるので、Ｃｕｒｒｅｎｔに１を加える（ステップＳ６０６）。
【００４４】
また、分岐命令処理の結果、分岐が成立しなかった場合には、Ｃｕｒｒ．Ｄｉｒ＝１であるか否か、すなわち前回の分岐が成立したか否かを調べる（ステップＳ６０７）。そして、前回も分岐が成立していなければ、分岐不成立が前回から連続していることになるので、Ｃｕｒｒｅｎｔに１を加える（ステップＳ６０６）。
【００４５】
これに対して、前回は分岐が成立していれば、今回新たに分岐不成立が始まることになるので、Ｃｕｒｒｅｎｔの値、すなわちこれまでの分岐成立の連続回数を、Ｔａｋｅｎにセットし（ステップＳ６０８）、Ｃｕｒｒ．Ｄｉｒを分岐不成立に変更し（ステップＳ６０９）、Ｃｕｒｒｅｎｔを１に初期化する（ステップＳ６１０）。
【００４６】
なお、ここでは、分岐命令に対するエントリが分岐履歴記憶部２１に既に存在する場合の処理手順について説明したが、分岐命令に対するエントリが分岐履歴記憶部２１に存在しない場合には、この分岐履歴更新部２２ａは、新たなエントリを作成し、分岐履歴記憶部２１に登録する。
【００４７】
そして、作成される新たなエントリは、Ｃｕｒｒｅｎｔが１にセットされ、分岐が成立している場合には、Ｔａｋｅｎが任意の数に、Ｎ−Ｔａｋｅｎが０に、Ｃｕｒｒ．Ｄｉｒが１にセットされ、分岐が成立していない場合には、Ｔａｋｅｎが０に、Ｎ−Ｔａｋｅｎが任意の数に、Ｃｕｒｒ．Ｄｉｒが０にセットされる。
【００４８】
また、分岐履歴を用いて分岐予測をおこなう場合、分岐履歴の初期構築段階では履歴データが不十分なために予測がはずれることが多い。したがって、分岐履歴の初期構築段階では、分岐履歴記憶部２１の分岐履歴に基づくブランチヒストリ１０の更新は避ける必要がある。このため、ＴａｋｅｎまたはＮ−Ｔａｋｅｎの値が０である場合には、分岐履歴記憶部２１の分岐履歴に基づくブランチヒストリ１０の更新はおこなわれない。
【００４９】
また、この分岐履歴更新部２２ａは、無条件分岐命令および分岐先が頻繁に変更となる分岐命令は分岐履歴記憶部２１に登録しない。その理由は、無条件分岐命令は、分岐方向を予測する必要がなく、分岐先が頻繁に変更となる分岐命令は、分岐方向だけを予測しても分岐先のアドレスが予測できないからである。このため、全ての分岐命令を登録するグローバルヒストリと比較して、分岐履歴記憶部２１に登録されるエントリの数を減らすことができ、必要となるハードウェアの量を減らすことができる。
【００５０】
次に、図２に示したブランチヒストリ更新部２２ｂによるブランチヒストリ更新処理の手順について説明する。図７は、図２に示したブランチヒストリ更新部２２ｂによるブランチヒストリ更新処理の手順を示すフローチャートである。なお、このブランチヒストリ更新処理は、図６に示した分岐履歴更新処理の直後に起動されるが、同じ分岐命令が次に処理されるまでにブランチヒストリ１０を更新できれば、このブランチヒストリ更新処理を別のタイミングで起動することもできる。
【００５１】
図７に示すように、このブランチヒストリ更新部２２ｂは、分岐履歴更新部２２ａの更新処理が完了した分岐命令の分岐履歴が初期構築状態にあるか否か、すなわち、更新処理がおこなわれたエントリのＴａｋｅｎまたはＮ−Ｔａｋｅｎの値が０であるか否かを調べ（ステップＳ７０１）、ＴａｋｅｎまたはＮ−Ｔａｋｅｎの値が０である場合には、従来手法によってブランチヒストリ１０を更新し（ステップＳ７０７）、処理を終了する。
【００５２】
これに対して、ＴａｋｅｎまたはＮ−Ｔａｋｅｎの値が０でない場合には、処理を終了した分岐命令の分岐が成立しかつこれまでの連続分岐成立回数が前回の連続分岐成立回数と一致しているか否か、すなわち、Ｃｕｒｒ．Ｄｉｒ＝１かつＣｕｒｒｅｎｔ＝Ｔａｋｅｎであるか否かを調べる（ステップＳ７０２）。そして、Ｃｕｒｒ．Ｄｉｒ＝１かつＣｕｒｒｅｎｔ＝Ｔａｋｅｎである場合には、前回はこの分岐命令が次に実行された時に分岐が成立しなかったことになるので、次回の分岐予測を分岐不成立とするようにブランチヒストリ１０を更新する（ステップＳ７０６）。
【００５３】
また、Ｃｕｒｒ．Ｄｉｒ＝１かつＣｕｒｒｅｎｔ＝Ｔａｋｅｎではない場合には、処理を終了した分岐命令の分岐が不成立でありかつこれまでの連続分岐不成立回数が前回の連続分岐不成立回数と一致しているか否か、すなわち、Ｃｕｒｒ．Ｄｉｒ＝０かつＣｕｒｒｅｎｔ＝Ｎ−Ｔａｋｅｎであるか否かを調べる（ステップＳ７０３）。そして、Ｃｕｒｒ．Ｄｉｒ＝０かつＣｕｒｒｅｎｔ＝Ｎ−Ｔａｋｅｎである場合には、前回はこの分岐命令が次に実行された時に分岐が成立したことになるので、次回の予測を分岐成立とするようにブランチヒストリ１０を更新する（ステップＳ７０５）。
【００５４】
これに対して、Ｃｕｒｒ．Ｄｉｒ＝０かつＣｕｒｒｅｎｔ＝Ｎ−Ｔａｋｅｎではない場合には、次回も今回と同じ方向に分岐すると予測することができるので、次の予測を今回の分岐結果と同方向とするようにブランチヒストリ１０を更新する（ステップＳ７０４）。
【００５５】
上述してきたように、本実施の形態では、分岐履歴記憶部２１が分岐命令ごとに過去複数回の分岐結果を分岐履歴として記憶し、分岐命令の処理が完了すると分岐履歴更新部２２ａが処理結果に基づいてその分岐命令に対応する分岐履歴記憶部２１の分岐履歴を更新し、ブランチヒストリ更新部２２ｂが更新された分岐履歴に基づいてブランチヒストリ１０を更新することとしたので、分岐確定時に分岐履歴を用いた予測結果をブランチヒストリ１０に反映することができる。したがって、命令フェッチ要求時には、命令フェッチがおこなわれる範囲を、十分容量が大きなブランチヒストリ１０でカバーすることができ、分岐履歴記憶部２１に記憶できる分岐命令の数が非常に少ない場合でも高精度の予測が可能となり、低コストで精度の高い予測をおこなうことができる。また、命令フェッチ要求時には複雑な予測処理をおこなう必要がなくなり、高速に分岐予測をおこなうことができる。
【００５６】
（付記１）分岐命令のアドレスと該分岐命令の予測分岐先のアドレスとの対応表を有するブランチヒストリを用いて該分岐命令の分岐先を予測する分岐予測装置であって、
前記分岐命令の過去の複数回の分岐結果を分岐履歴として記憶した分岐履歴記憶手段と、
前記分岐履歴記憶手段により記憶された分岐履歴に基づいて前記分岐命令の分岐方向を予測し、該予測した分岐方向に基づいて前記対応表を更新するブランチヒストリ更新手段と、
を備えたことを特徴とする分岐予測装置。
【００５７】
（付記２）前記分岐履歴記憶手段により記憶された分岐履歴を、前記分岐命令の処理が完了した時点で該処理の結果に基づいて更新することを特徴とする付記１に記載の分岐予測装置。
【００５８】
（付記３）前記分岐履歴記憶手段は、前記分岐命令のアドレスを連想キーとして前記分岐履歴を索引することを特徴とする付記１または２に記載の分岐予測装置。
【００５９】
（付記４）前記分岐履歴記憶手段は、無条件分岐命令を前記分岐履歴に記憶する対象としないことを特徴とする付記１または２に記載の分岐予測装置。
【００６０】
（付記５）前記分岐履歴記憶手段は、分岐条件が成立するか否かの二者択一分岐命令だけを前記分岐履歴に記憶する対象とすることを特徴とする付記１または２に記載の分岐予測装置。
【００６１】
（付記６）前記分岐履歴記憶手段は、前記分岐命令ごとに、最近の連続分岐成立回数および最近の連続分岐不成立回数を記憶し、前記ブランチヒストリ更新手段は、前記最近の連続分岐成立回数および最近の連続分岐不成立回数に基づいて前記分岐命令の分岐成立不成立を予測することを特徴とする付記１または２に記載の分岐予測装置。
【００６２】
（付記７）前記ブランチヒストリ更新手段は、前記分岐命令の直近の連続分岐成立回数が最近の連続分岐成立回数に等しい場合には次回は分岐不成立と予測し、前記分岐命令の直近の連続分岐不成立回数が最近の連続分岐不成立回数に等しい場合には次回は分岐成立と予測することを特徴とする付記６に記載の分岐予測装置。
【００６３】
（付記８）前記分岐履歴記憶手段により記憶された分岐履歴が初期構築状態にあるか否かを判定する分岐履歴構築段階判定手段をさらに備え、前記ブランチヒストリ更新手段は、前記分岐履歴が初期構築状態にある場合には、前記対応表を更新しないことを特徴とする付記６に記載の分岐予測装置。
【００６４】
（付記９）前記分岐履歴構築段階判定手段は、前記最近の連続分岐成立回数または最近の連続分岐不成立回数が０である場合に、前記分岐履歴が初期構築状態にあると判定することを特徴とする付記８に記載の分岐予測装置。
【００６５】
（付記１０）前記ブランチヒストリ更新手段は、前記分岐命令の分岐予測が不成立である場合には、該分岐命令を前記対応表に登録する対象としないことを特徴とする付記１または２に記載の分岐予測装置。
【００６６】
（付記１１）分岐命令のアドレスと該分岐命令の予測分岐先のアドレスとの対応表を有するブランチヒストリを用いて該分岐命令の分岐先を予測する分岐予測方法であって、
前記分岐命令の過去の複数回の分岐結果を分岐履歴として記憶し、該記憶した分岐履歴を前記分岐命令の処理が完了した時点で該処理の結果に基づいて更新する分岐履歴更新工程と、
前記分岐履歴更新工程により更新された分岐履歴に基づいて前記分岐命令の分岐方向を予測し、該予測した分岐方向に基づいて前記対応表を更新するブランチヒストリ更新工程と、
を含んだことを特徴とする分岐予測方法。
【００６７】
（付記１２）前記分岐履歴は、前記分岐命令のアドレスを連想キーとする連想記憶であることを特徴とする付記１１に記載の分岐予測方法。
【００６８】
（付記１３）無条件分岐命令を前記分岐履歴に記憶する対象としないことを特徴とする付記１１または１２に記載の分岐予測方法。
【００６９】
（付記１４）分岐条件が成立するか否かの二者択一分岐命令だけを前記分岐履歴に記憶する対象とすることを特徴とする付記１１または１２に記載の分岐予測方法。
【００７０】
（付記１５）前記分岐履歴は、前記分岐命令ごとに、最近の連続分岐成立回数および最近の連続分岐不成立回数を記憶し、前記ブランチヒストリ更新工程は、前記最近の連続分岐成立回数および最近の連続分岐不成立回数に基づいて前記分岐命令の分岐成立不成立を予測することを特徴とする付記１１または１２に記載の分岐予測方法。
【００７１】
（付記１６）前記ブランチヒストリ更新工程は、前記分岐命令の直近の連続分岐成立回数が最近の連続分岐成立回数に等しい場合には次回は分岐不成立と予測し、前記分岐命令の直近の連続分岐不成立回数が最近の連続分岐不成立回数に等しい場合には次回は分岐成立と予測することを特徴とする付記１５に記載の分岐予測方法。
【００７２】
（付記１７）前記分岐履歴が初期構築状態にあるか否かを判定する分岐履歴構築段階判定工程をさらに含み、前記ブランチヒストリ更新工程は、前期分岐履歴が初期構築状態にある場合には、前記対応表を更新しないことを特徴とする付記１５に記載の分岐予測方法。
【００７３】
（付記１８）前記分岐履歴構築段階判定工程は、前記最近の連続分岐成立回数または最近の連続分岐不成立回数が０である場合に、前記分岐履歴が初期構築状態にあると判定することを特徴とする付記１７に記載の分岐予測方法。
【００７４】
（付記１９）前記ブランチヒストリ更新工程は、前記分岐命令の分岐予測が不成立である場合には、該分岐命令を前記対応表に登録する対象としないことを特徴とする付記１１または１２に記載の分岐予測方法。
【００７５】
【発明の効果】
以上説明したように、本発明によれば、分岐命令の過去の複数回の分岐結果を分岐履歴として記憶し、記憶した分岐履歴に基づいて分岐命令の分岐方向を予測し、予測した分岐方向に基づいて、分岐命令のアドレスと分岐命令の予測分岐先のアドレスとの対応表を更新するよう構成したので、分岐確定時に分岐履歴を用いた予測結果をブランチヒストリに反映することができる。したがって、命令フェッチ要求時には、命令フェッチがおこなわれる範囲を、十分容量が大きなブランチヒストリでカバーすることができ、分岐履歴に記憶する分岐命令の数が非常に少ない場合でも高精度の予測が可能となり、低コストで精度の高い予測をおこなうことができるという効果を奏する。また、命令フェッチ要求時には複雑な予測処理をおこなう必要がなくなり、高速に分岐予測をおこなうことができるという効果を奏する。
【図面の簡単な説明】
【図１】図１は、本実施の形態に係る分岐予測の原理を説明するための説明図である。
【図２】本実施の形態に係る分岐予測装置の構成を示す機能ブロック図である。
【図３】ブランチヒストリのエントリのデータ構造の一例を示す図である。
【図４】分岐履歴記憶部のエントリのデータ構造の一例を示す図である。
【図５】Ｔａｋｅｎ、Ｎ−ＴａｋｅｎおよびＣｕｒｒｅｎｔを説明するための説明図である。
【図６】図２に示した分岐履歴更新部による分岐履歴更新処理の手順を示すフローチャートである。
【図７】図２に示したブランチヒストリ更新部によるブランチヒストリ更新処理の手順を示すフローチャートである。
【符号の説明】
１０　ブランチヒストリ
２０　予測更新部
２１　分岐履歴記憶部
２２　制御部
２２ａ　分岐履歴更新部
２２ｂ　ブランチヒストリ更新部
２００　分岐予測装置
【図１】
2004038323.tif 000003
【図２】
2004038323.tif 000004
【図３】
2004038323.tif 000005
【図４】
2004038323.tif 000006
【図５】
2004038323.tif 000007
【図６】
2004038323.tif 000008
【図７】
2004038323.tif 000009