(57)【要約】【課題】  フルアソシアティブ方式の記憶装置において、新たな資源を使用することなく不要なエントリをリプレース対象として選択できるようにして、効率的なリプレースを実現する。【解決手段】  ブランチヒストリ１５を用いて分岐命令の分岐先を予測する情報処理装置１において、分岐履歴記憶部２４に新たな分岐命令についての分岐履歴を登録する際に、分岐履歴記憶部２４のすべてのエントリが使用中である場合に、分岐履歴記憶部２４のすべてのエントリの中から一のエントリを選択する選択部２２と、この選択部２２によって選択された一のエントリに新たな分岐命令についての分岐履歴を登録するリプレース部２３とをそなえ、選択部２２が、分岐履歴記憶部２４に保持された分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有する。【選択図】  図１
2006099528.tif 000002
【特許請求の範囲】
【請求項１】
分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、
前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、
該分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、
該分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部と、
前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合に、前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択部と、
該選択部によって選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレース部とをそなえ、
前記選択部が、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有していることを特徴とする、情報処理装置。
【請求項２】
前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で最も古く登録されたものを選択する第２選択機能を有し、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用することを特徴とする、請求項１記載の情報処理装置。
【請求項３】
前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で前記分岐方向予測部による予測に用いられたのが最も古いものを選択する第２選択機能を有し、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用することを特徴とする、請求項１記載の情報処理装置。
【請求項４】
前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴がすべて分岐成立であるエントリを前記一のエントリとして選択することを特徴とする、請求項１〜３のいずれか１項に記載の情報処理装置。
【請求項５】
前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴の分岐成立回数が所定回数以上であるエントリを選択することを特徴とする、請求項４記載の情報処理装置。
【請求項６】
前記分岐履歴記憶部は、前記分岐命令の前記分岐方向としての分岐成立／分岐不成立が２度切り替わるまでの分岐成立連続回数及び分岐不成立連続回数を前記分岐履歴として保持するとともに、
前記分岐方向予測部は、前記分岐成立連続回数及び前記分岐不成立連続回数に基づいて、前記分岐命令の分岐方向である分岐成立／分岐不成立を予測することを特徴とする、請求項１〜５のいずれか１項に記載の情報処理装置。
【請求項７】
前記分岐履歴記憶部に保持された前記分岐履歴が初期構築状態にあるか否かを判定する分岐履歴構築状態判定部をそなえ、
前記分岐方向予測部は、前記分岐履歴構築状態判定部が、前記分岐履歴が初期構築状態であると判定した場合には、当該分岐履歴に基づく前記分岐方向の予測を行なわないことを特徴とする、請求項１〜６のいずれか１項に記載の情報処理装置。
【請求項８】
分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、該分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、該分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部とをそなえた情報処理装置において、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合の前記エントリのリプレース方法であって、
前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択ステップと、
該選択ステップにおいて選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレースステップとを含み、
前記選択ステップが、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択ステップを含んでいることを特徴とする、リプレース方法。
【請求項９】
分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、該分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、該分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部とをそなえた情報処理装置において、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合の前記エントリのリプレース機能をコンピュータに実現させるためのリプレースプログラムであって、
前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択部、及び、
該選択部によって選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレース部として、前記コンピュータを機能させるとともに、
前記選択部が、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有するように、前記コンピュータを機能させることを特徴とする、リプレースプログラム。
【請求項１０】
分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、該分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、該分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部とをそなえた情報処理装置において、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合の前記エントリのリプレース機能をコンピュータに実現させるためのリプレースプログラムを記録したコンピュータ読取可能な記録媒体であって、
前記リプレースプログラムが、
前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択部、及び、
該選択部によって選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレース部として、前記コンピュータを機能させるとともに、
前記選択部が、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有するように、前記コンピュータを機能させることを特徴とする、リプレースプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フルアソシアティブ方式の記憶装置においてすべてのエントリが使用中である場合にエントリをリプレースする技術に関し、例えば、フルアソシアティブ方式の分岐履歴記憶部に保持された過去の分岐履歴を参照して分岐命令の分岐方向の予測を行なう、グローバルヒストリ方式又はローカルヒストリ方式を採用した情報処理装置において、上記分岐履歴記憶部に新たなエントリをリプレースする際に用いて好適の技術に関する。
【背景技術】
【０００２】
従来から、所定数のエントリを持つフルアソシアティブ方式の記憶装置が種々の装置に装備され、広く普及している。
例えば、分岐命令のアドレスとその分岐命令の予測分岐先のアドレスとの対を保持するブランチヒストリを用いて分岐命令の分岐先を予測する情報処理装置において、予測精度の向上を目的として、過去の分岐履歴に関する情報を保持するフルアソシアティブ方式の記憶装置を含む、グローバルヒストリをそなえる技術がある（下記特許文献１参照）。
【０００３】
このグローバルヒストリのように、一定エントリ数しか持たないフルアソシアティブ方式の記憶装置においては、限られたエントリを如何に有効に使うかが性能向上の鍵となり、エントリをリプレースする際には、複数エントリの中で不要なエントリを確実にリプレースすることが重要になる。
従来から、フルアソシアティブ方式の記憶装置におけるエントリのリプレース方法として、登録したのが最も古いエントリをリプレースするラウンドロビンや、アクセスしてから最も時間の経過しているエントリをリプレースするＬＲＵ（Least Recently Used）がある。
【０００４】
また、その他のリプレース方法として、例えば、分岐命令の分岐予測に関する技術分野において、分岐予測の正解率（一致回数）に基づいてリプレースするエントリを選択する技術がある（下記特許文献２，３参照）。
【特許文献１】特開２００４−３８３２３号公報
【特許文献２】特開２００２−２７８７５２号公報
【特許文献３】特開平６−６７８８０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述したラウンドロビンは、エントリの有効性が全く考慮されず、分岐予測に非常に有効なエントリや使用中のエントリでも、登録した時期が最も古ければ容赦なく消してしまうため、効率的なリプレース手法とは言い難い。
また、上述したＬＲＵでは、アクセスしてから最も時間の経過しているエントリをリプレース対象の不要なエントリとして選択するため、特に、履歴が繰り返すことを期待してその周期性から期待値を出すグローバルヒストリ（上記特許文献１参照）のようなものにおいては、その性質上、アクセスしてから最も時間の経過したエントリが不要なエントリであるとは限らない。
【０００６】
つまり、グローバルヒストリの特徴として、出現頻度が低いだけで一定周期で出現するような周期の長い分岐命令についてのエントリは出来る限りリプレース対象とすることを避けたいが、ＬＲＵでは出現頻度の低い分岐命令についてのエントリをリプレース対象にする確率が高くなってしまい、ＬＲＵも効率的なリプレース手法とは言い難い。
さらに、ＬＲＵでは、アクセスした履歴に関する情報を別途保持する必要があるため、かかる情報を保持するために資源コストが必要になり、フルアソシアティブ方式の記憶装置の有限な資源を有効に利用することができない。
【０００７】
また、上記特許文献２，３に開示された分岐予測の正解率等を使用する技術でもＬＲＵと同様に、正解率等に関する情報を別途保持する必要があるため、資源コストが嵩んでしまう。
本発明は、このような課題に鑑み創案されたもので、フルアソシアティブ方式の記憶装置において、新たな資源を使用することなく不要なエントリをリプレース対象として選択できるようにして、効率的なリプレースを実現することを目的とする。
【０００８】
特に、本発明は、例えば、グローバルヒストリ方式を採用した情報処理装置において、新たな資源を使用することなく、分岐履歴記憶部のエントリの中で、そのエントリが無くても分岐命令の分岐方向予測に影響を与えないエントリをリプレース対象として選択できるようにして、効率的なリプレースを実現することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明の情報処理装置は、分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、この分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、この分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部と、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合に、前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択部と、この選択部によって選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレース部とをそなえ、前記選択部が、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有していることを特徴としている（請求項１）。
【００１０】
なお、前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で最も古く登録されたものを選択する第２選択機能を有し、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用することが好ましい（請求項２）。
また、前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で前記分岐方向予測部による予測に用いられたのが最も古いものを選択する第２選択機能を有し、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用することが好ましい（請求項３）。
【００１１】
さらに、前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴がすべて分岐成立であるエントリを前記一のエントリとして選択することが好ましく（請求項４）、このとき、前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴の分岐成立回数が所定回数以上であるエントリを選択することが好ましい（請求項５）。
【００１２】
また、前記分岐履歴記憶部は、前記分岐命令の前記分岐方向としての分岐成立／分岐不成立が２度切り替わるまでの分岐成立連続回数及び分岐不成立連続回数を前記分岐履歴として保持するとともに、前記分岐方向予測部は、前記分岐成立連続回数及び前記分岐不成立連続回数に基づいて、前記分岐命令の分岐方向である分岐成立／分岐不成立を予測することが好ましい（請求項６）。
【００１３】
さらに、前記分岐履歴記憶部に保持された前記分岐履歴が初期構築状態にあるか否かを判定する分岐履歴構築状態判定部をそなえ、前記分岐方向予測部は、前記分岐履歴構築状態判定部が、前記分岐履歴が初期構築状態であると判定した場合には、当該分岐履歴に基づく前記分岐方向の予測を行なわないことが好ましい（請求項７）。
また、上記目的を達成するために、本発明のリプレース方法は、分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、この分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、この分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部とをそなえた情報処理装置において、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合の前記エントリのリプレース方法であって、前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択ステップと、この選択ステップにおいて選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレースステップとを含み、前記選択ステップが、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択ステップを含んでいることを特徴としている（請求項８）。
【００１４】
さらに、上記目的を達成するために、本発明のリプレースプログラムは、分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、この分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、この分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部とをそなえた情報処理装置において、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合の前記エントリのリプレース機能をコンピュータに実現させるためのリプレースプログラムであって、前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択部、及び、この選択部によって選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレース部として、前記コンピュータを機能させるとともに、前記選択部が、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有するように、前記コンピュータを機能させることを特徴としている（請求項９）。
【００１５】
なお、上記目的を達成するため、本発明のコンピュータ読取可能な記録媒体は、上記リプレースプログラムを記録したものである（請求項１０）。
【発明の効果】
【００１６】
このように、本発明によれば、分岐履歴記憶部が分岐方向の予測に使用するために元々備えている分岐履歴に基づいて、リプレース対象のエントリを選択するため、リプレースのために新たな情報を特別に保持することなく、つまり、新たな資源を使用することなく分岐予測には不要なエントリを優先的に選択することができ、効率的なリプレースを実行することができる。
【００１７】
さらに、分岐履歴記憶部に保持された前記分岐履歴がすべて分岐成立であるエントリ、つまり、登録されてからすべて分岐成立している分岐履歴であって、かかる分岐成立回数が所定回数以上であるエントリをリプレース対象として優先的に選択することによって、分岐履歴記憶部のエントリの中で、そのエントリが無くても分岐命令の分岐方向予測に影響を与えないエントリをリプレース対象として選択することができる。これにより、効率的なリプレースを実現することができ、分岐履歴記憶部の有限な資源を有効利用できるとともに、分岐履歴記憶部を用いた分岐方向予測の精度（性能）を向上させることができる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照しながら本発明の実施の形態について説明する。
〔１〕本発明の一実施形態について
まず、本発明の一実施形態としての情報処理装置の構成について説明すると、図１は本発明の一実施形態としての情報処理装置１の構成を示すブロック図である。この図１に示すように、本発明の一実施形態としての情報処理装置１は、命令フェッチアドレス生成部１０，命令フェッチ部１１，命令デコーダ１２，分岐命令制御部１３，ブランチヒストリ１５，及びグローバルヒストリ２０をそなえて構成されている。
【００１９】
本情報処理装置１では、命令フェッチ部１１が、命令フェッチアドレス生成部１０によって生成された命令フェッチアドレスを用いて、命令フェッチ要求を出すと同時に、ブランチヒストリ１５を検索する。
そして、かかる命令フェッチアドレスに対応する分岐命令がブランチヒストリ１５に登録されている場合には、ブランチヒストリ１５により予測された分岐先の命令アドレスを読み出し、読み出された命令アドレスに基づいて次の命令フェッチを行なう。
【００２０】
図２はブランチヒストリ１５の保持する対応表１５ａのデータ構造を示す図である。この図２に示すように、ブランチヒストリ１５は、分岐命令アドレス（ＩＡＲ）及び予測分岐先アドレス（ＴＩＡＲ）から構成される対応表１５ａを保持しており、ブランチヒストリ１５は、この対応表１５ａに、過去に実行された分岐命令であって、分岐すると予測されている分岐命令毎に分岐命令アドレスと予測分岐先アドレスとを対応させて記憶している。
【００２１】
上述したように、ブランチヒストリ１５は命令フェッチ部１１によって取り出される命令データに分岐命令が含まれる場合に、かかる分岐命令の分岐先アドレスを予測するために用いられるものであり、対応表１５ａに基づいて分岐命令アドレスから予測分岐先アドレスを検索することができる。
つまり、ブランチヒストリ１５の対応表１５ａが保持する分岐命令アドレスは分岐命令の命令アドレスであり、索引として用いられる。また、予測分岐先アドレスは過去に当該分岐命令が実行されたときの分岐先アドレスであり、次に当該分岐命令を実行する場合の分岐先アドレスの予測値として用いられる。
【００２２】
一方、命令フェッチ部１１によってフェッチされた分岐命令は、命令デコーダ１２によってデコードされ、分岐命令制御部１３によって当該分岐命令の処理が実行される。
また、分岐命令制御部１３は分岐リザベーションステーション（図中分岐ＲＳと表記；以下、分岐ＲＳという）１４をそなえており、分岐ＲＳ１４は処理を実行した分岐命令についての情報を保持している。
【００２３】
ここで、分岐ＲＳ１４は、例えば、処理を実行された分岐命令毎に、分岐命令のアドレスと当該分岐命令の分岐先の命令アドレスとを保持するとともに、当該分岐命令の分岐成立／分岐不成立についての分岐情報等を保持しており、これらの情報は分岐命令制御部１３によって分岐ＲＳ１４に登録される。
そして、分岐ＲＳ１４に登録された情報は、必要に応じて分岐命令制御部１３からブランチヒストリ１５や後述するグローバルヒストリ２０に渡される。
【００２４】
グローバルヒストリ２０は、分岐命令の分岐履歴に基づいて当該分岐命令が次回分岐するか否かの分岐方向を予測して、かかる予測の結果に基づいてブランチヒストリ１５を更新するものであり、分岐履歴更新部２１，分岐履歴記憶部２４，分岐方向予測部２５，分岐履歴構築段階判定部２６，及びブランチヒストリ更新部２７をそなえて構成されている。
【００２５】
分岐履歴更新部２１は、分岐命令制御部１３から受け取った分岐ＲＳ１４が保持する分岐命令についての情報に基づいて、後述する分岐履歴記憶部２４に対して分岐履歴の登録もしくは更新を行なうものである。また、分岐履歴更新部２１は、選択部２２及びリプレース部２３をそなえている。なお、これら選択部２２及びリプレース部２３の詳細については後述する。
【００２６】
分岐履歴記憶部２４は、フルアソシアティブ方式の記憶装置であり、過去に実行されて分岐が成立した条件分岐命令であって、分岐ＲＳ１４から渡された（つまり、分岐履歴更新部２１によって登録・更新される）分岐命令についての過去の分岐成立／分岐不成立（即ち、分岐方向）を分岐履歴として保持するものであり、所定数（ここでは、エントリ０〜ｎ−１のｎ個）のエントリを持ち、複数の分岐命令についてそれぞれの分岐履歴を保持している。
【００２７】
図３は分岐履歴記憶部２４の各エントリに保持される分岐履歴のデータ構成を示す図である。この図３に示すように、分岐履歴記憶部２４は、各エントリにおいて、Ｉ−Ａｄｄｒｅｓｓ２４ａ，ＴＡＫＥＮカウンタ（図３中ＴＡＫＥＮ．ＣＴＲと表記）２４ｂ，ＮＯＴ−ＴＡＫＥＮカウンタ（図３中Ｎ＿ＴＫＮ．ＣＴＲと表記）２４ｃ，ＣＵＲＲＥＮＴカウンタ（図３中ＣＵＲＲＥＮＴ．ＣＴＲと表記）２４ｄ，ＣＵＲＲＥＮＴ方向（図３中ＣＵＲＲ．ＤＩＲと表記）２４ｅをそなえている。
【００２８】
Ｉ−Ａｄｄｒｅｓｓ２４ａは、このエントリに対応する分岐命令のアドレスである。ここでこのアドレスは、アドレス全体である必要はなく、このエントリと分岐命令とを対応付けることが出来ればアドレスの部分ビット列等であってもよい。
ＴＡＫＥＮカウンタ２４ｂは、分岐が成立してから不成立に切り替わるまでの分岐成立連続回数を保持するものである。
【００２９】
ＮＯＴ−ＴＡＫＥＮカウンタ２４ｃは、分岐が成立から不成立に切り替わった後、再度分岐成立に切り替わるまでの分岐不成立連続回数を保持するものである。
ＣＵＲＲＥＮＴカウンタ２４ｄは、後述するＣＵＲＲＥＮＴ方向２４ｅが示す前回の分岐方向が連続して発生している回数をカウントして保持するものである。
ＣＵＲＲＥＮＴ方向２４ｅは、前回の分岐命令の実行で分岐が成立したか否かを示すものであり、例えば１ビットの情報（フラグ）で構成されている。
【００３０】
なお、ＣＵＲＲＥＮＴカウンタ２４ｄは、ｍ回（ｍは０以上の整数）までの連続回数をカウントすることができるようになっており、ＴＡＫＥＮカウンタ２４ｂ及びＮＯＴ−ＴＡＫＥＮカウンタ２４ｃは、０〜ｍまでの値を保持することができるようになっている。したがって、ＣＵＲＲＥＮＴカウンタ２４ｄにおいてはｍ回が限界値であり、ＣＵＲＲＥＮＴカウンタ２４ｄの値が“ｍ”を示しているときは、オーバーフローを意味している。
【００３１】
ここで、分岐履歴記憶部２４が保持する分岐履歴の構成について図４（ａ），（ｂ）を参照しながら具体例を用いて説明する。なお、図４（ａ）において“Ｔ”はＴＡＫＥＮ（分岐成立）を示し、“Ｎ”はＮＯＴ―ＴＡＫＥＮ（分岐不成立）を示しており、図４（ｂ）においてＣＵＲＲＥＮＴ方向２４ｅが“１”は、前回の分岐命令の実行で分岐が成立したことを示している。
【００３２】
この図４（ａ），（ｂ）に示す具体例の場合、前回と前々回は連続して分岐成立しているため、ＣＵＲＲＥＮＴ方向２４ｅは“１”となり、ＣＵＲＲＥＮＴカウンタ２４ｄは“２”となる。また、分岐が成立してから不成立に切り替わるまでに３回連続して分岐が成立しているため、ＴＡＫＥＮカウンタ２４ｂは“３”となり、さらにその後分岐が不成立となってから再度分岐成立に切り替わるまでに６回連続して分岐が不成立しているため、ＮＯＴ−ＴＡＫＥＮカウンタ２４ｃは“６”となる。つまり、分岐履歴記憶部２４は、分岐命令の分岐方向としての分岐成立／不成立が２度切り替わるまでの分岐成立連続回数（ＴＡＫＥＮカウンタ２４ｂ）及び分岐不成立連続回数（ＮＯＴ−ＴＡＫＥＮカウンタ２４ｃ）を保持している。
【００３３】
このように、グローバルヒストリ２０の分岐履歴記憶部２４では、過去の分岐結果をすべて記憶するのではなく、最近の連続する分岐成立／分岐不成立の連続回数を分岐履歴として記憶することにより、効率良く分岐履歴を記憶することができ、必要となるハードウェア（資源）の量を減らすことができる。
分岐方向予測部２５は、分岐履歴記憶部２４に保持された分岐履歴に基づいて、分岐命令の分岐方向（分岐成立／分岐不成立）を予測するものであり、ＴＡＫＥＮカウンタ２４ｂの分岐成立連続回数及びＮＯＴ−ＴＡＫＥＮカウンタ２４ｃの分岐不成立連続回数に基づいて分岐命令の次回の分岐方向を予測する。
【００３４】
また、分岐方向予測部２５は、後述する分岐履歴構築段階判定部２６が予測対象の分岐命令についての分岐履歴が初期構築段階（状態）にあると判定した場合には、当該分岐履歴を用いた予測を実行しないようになっている。
分岐方向予測部２５についてさらに詳述すると、図４（ａ），（ｂ）に示す具体例の場合には、前々回の分岐命令実行時に、分岐不成立から分岐成立に切り替わり、前回実行時にも分岐が成立している。従って、ＣＵＲＲＥＮＴカウンタ２４ｄは“２”となりＣＵＲＲＥＮＴ方向２４ｅは“１”となっている。ここで、ＴＡＫＥＮカウンタ２４ｂは“３”であるため、分岐方向予測部２５は、当該分岐命令がＴＡＫＥＮカウンタ２４ｂに保持された分岐成立連続回数及びＮＯＴ―ＴＡＫＥＮカウンタ２４ｃに保持された分岐不成立連続回数を周期的に繰り返すことを前提として、次回も分岐が成立すると予測する。
【００３５】
分岐履歴構築段階判定部２６は、分岐履歴記憶部２４に保持された分岐履歴が初期構築段階（状態）にあるか否かを判定するものであり、分岐履歴記憶部２４のＴＡＫＥＮカウンタ２４ａもしくはＮＯＴ−ＴＡＫＥＮカウンタ２４ｃのいずれかが“０”である場合には、当該エントリの分岐命令の分岐履歴は初期構築状態であると判定する。
ブランチヒストリ更新部２７は、分岐方向予測部２５によって予測された分岐方向に基づいてブランチヒストリ１５に保持された対応表１５ａを更新するものであり、分岐方向予測部２５によって分岐が成立すると予測された分岐命令についてはブランチヒストリ１５の対応表１５ａが保持するように更新するとともに、分岐方向予測部２５によって分岐が不成立となると予測された分岐命令についてはブランチヒストリ１５の対応表１５ａに保持されないように更新する。
【００３６】
ここで、ブランチヒストリ更新部２７が動作する場合について図５に示すフローチャート（ステップＳ１０〜Ｓ１４）を参照しながら説明すると、この図５に示すように、分岐命令制御部１３による分岐命令の処理完了後、当該分岐命令が条件分岐命令でない場合には（ステップＳ１０のＮｏルート）、ブランチヒストリ更新部２７は機能せず、ブランチヒストリ１５による予測に基づいてブランチヒストリ１５が更新される（ステップＳ１１）が、当該分岐命令が条件分岐であった場合（ステップＳ１０のＹｅｓルート）であって、グローバルヒストリ２０が検索されて（ステップＳ１２）、グローバルヒストリ２０から予測が出た場合（ステップＳ１３のＹｅｓルート）、つまり、分岐方向予測部２５によって予測が行なわれた場合に（後述する図６のステップＳ３２，Ｓ３４，Ｓ３５参照）、この分岐方向予測部２５による予測に基づいて、ブランチヒストリ更新部２７がブランチヒストリ１５の対応表１５ａ（図２参照）の更新を行なう（ステップＳ１４）。なお、グローバルヒストリ２０から予測が出なかった場合（ステップＳ１３のＮｏルート）には、ブランチヒストリ更新部２７は機能しない。
【００３７】
次に、分岐履歴更新部２１，分岐方向予測部２５，及び分岐履歴構築段階判定部２６の動作（分岐履歴記憶部２４の検索手順）について図６に示すフローチャート（ステップＳ２０〜Ｓ３５）を参照しながら説明すると、この図６に示すように、分岐命令の実行後、分岐命令制御部１３から当該分岐命令に関する情報がグローバルヒストリ２０に送られてくると、分岐履歴更新部２１が、まず、当該分岐命令が分岐履歴記憶部２４のエントリに存在するか否かを検索する（ステップＳ２０）。
【００３８】
そして、グローバルヒストリ２０内の分岐履歴記憶部２４のエントリに当該分岐命令の分岐履歴が存在していなければ（ステップＳ２１のＮｏルート）、分岐履歴更新部２１は必要に応じて当該分岐命令についての新規エントリを生成して分岐履歴記憶部２４に登録する（ステップＳ２２）。なお、このとき分岐履歴記憶部２４のエントリに空きがあれば、空いているエントリに当該分岐命令の新規エントリを登録する一方、分岐履歴記憶部２４のエントリに空きがなければ、選択部２２により分岐履歴記憶部２４のエントリから一のエントリを選択し、リプレース部２３により選択部２２によって選択されたエントリに新規エントリを登録する。選択部２２及びリプレース部２３の詳細については図１１〜図２２を参照しながら後述する。
【００３９】
なお、分岐履歴更新部２１が当該分岐命令についての新規エントリを生成して分岐履歴記憶部２４に登録する場合（ステップＳ２２）には、図７に示す信号生成回路３０において、分岐履歴記憶部２４に新規エントリを登録するための信号（ＣＲＥＡＴＥ＿ＮＥＷ＿ＷＲＧＨＴ信号）が生成される。つまり、ブランチヒストリ１５に当該分岐命令についてのエントリが登録されることにより発生する、分岐履歴記憶部２４への新規エントリ登録指示があると、分岐履歴記憶部２４のエントリから当該分岐命令が発見されたことを示す信号（ＷＲＧＨＴ＿ＨＩＴ＿ＯＲ信号）が発生しなかった場合（つまり、当該分岐命令の分岐履歴が分岐履歴記憶部２４にない場合）に、ＣＲＥＡＴＥ＿ＮＥＷ＿ＷＲＧＨＴ信号が生成される。なお、図７及び後述する図９，図１０，図１２〜図１９，図２１，図２２において、ＷＲＧＨＴは分岐履歴記憶部２４のエントリを示し、ＷＲＧＨＴの末尾に０〜ｎ−１を付している場合には、各エントリ０〜ｎ−１を示す。
【００４０】
つまり、図８のフローチャート（ステップＳ２２ａ〜Ｓ２２ｃ）に示すごとく、分岐履歴更新部２１は、分岐命令制御部１３で実行後ブランチヒストリ１５に登録される条件分岐命令について、ブランチヒストリ１５から当該分岐命令の生成指示が出た場合（つまり、ブランチヒストリ１５に条件分岐命令のエントリを新たに登録する場合；ステップＳ２２ａのＹｅｓルート）であって、当該分岐命令が分岐履歴記憶部２４のいずれのエントリからもヒットしなかった場合（ステップＳ２２ｂのＹｅｓルート）には、当該分岐命令についての新規エントリを分岐履歴記憶部２４に生成する（ステップＳ２２ｃ）。
【００４１】
また、図６に示すように、分岐履歴記憶部２４に当該分岐命令のエントリが存在していない場合には（ステップＳ２１のＮｏルート）、分岐履歴記憶部２４に基づく分岐方向予測部２５による予測（即ち、グローバルヒストリ２０による予測）は行なわれない（ステップＳ２３）。
一方、分岐履歴記憶部２４に当該分岐命令のエントリが存在していれば（ステップＳ２１のＹｅｓルート）、分岐履歴更新部２１は、分岐命令制御部１３から送られてきた当該分岐命令に関する情報に含まれる当該分岐命令の分岐方向（分岐成立／分岐不成立）と、ＣＵＲＲＥＮＴ方向２４ｅが示す分岐方向とが一致するか否かを調べる（ステップＳ２４）。
【００４２】
なお、分岐履歴記憶部２４に当該分岐命令のエントリが存在している場合には（ステップＳ２１のＹｅｓルート）、図９に示す信号生成回路３１において、分岐履歴記憶部２４に当該分岐命令のエントリが存在していることを示す信号（ＷＲＧＨＴ＿ＨＩＴ信号）が生成される。
つまり、分岐命令の実行が完了したことを示す信号（ＣＯＭＰＬＥＴＥ信号）が発生し、さらに、当該ＣＯＭＰＬＥＴＥ信号に含まれる分岐命令アドレス（ＣＯＭＰ＿ＩＡＲ）と分岐履歴記憶部２４に保持されたＩ−Ａｄｄｒｅｓｓとが一致した場合に、ＷＲＧＨＴ＿ＨＩＴ信号が生成される。
【００４３】
さらに、図１０に示す信号生成回路３２において、分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１からの信号（ＷＲＧＨＴ０＿ＨＩＴ信号〜ＷＲＧＨＴｎ−１＿ＨＩＴ信号）に基づいて、分岐履歴記憶部２４のいずれかのエントリから当該分岐命令のエントリが発見されたことを示す信号（ＷＲＧＨＴ＿ＨＩＴ＿ＯＲ信号）が生成される。
そして、図６に示すように、当該分岐命令の分岐方向とＣＵＲＲＥＮＴ方向２４ｅが示す分岐方向とが一致しない場合であって（ステップＳ２４のＮｏルート）、現在の（つまり、分岐命令制御部１３から送られてきた当該分岐命令の分岐方向に更新する以前の前回の）ＣＵＲＲＥＮＴ方向２４ｅが“１”、即ち分岐成立を示している場合には（ステップＳ２５のＹｅｓルート）、現在のＣＵＲＲＥＮＴカウンタ２４ｄの値をＴＡＫＥＮカウンタ２４ｂに保持させる（ステップＳ２６）とともに、ＣＵＲＲＥＮＴ方向２４ｅを分岐命令制御部１３から送られてきた分岐方向（この場合には分岐不成立“０”）に更新し、さらにＣＵＲＲＥＮＴカウンタ２４ｄの値を“１”に変更する（ステップＳ２８）。
【００４４】
また、現在のＣＵＲＲＥＮＴ方向２４ｅが“０”、即ち分岐不成立を示している場合には（ステップＳ２５のＮｏルート）、現在のＣＵＲＲＥＮＴカウンタ２４ｄの値をＮＯＴ−ＴＡＫＥＮカウンタ２４ｃに保持させる（ステップＳ２７）とともに、ＣＵＲＲＥＮＴ方向２４ｅを分岐命令制御部１３から送られてきた分岐方向（この場合には分岐成立“１”）に更新し、さらにＣＵＲＲＥＮＴカウンタ２４ｄの値を“１”に変更する（ステップＳ２８）。
【００４５】
なお、分岐履歴更新部２１は、分岐命令制御部１３から送られてきた当該分岐命令の分岐方向（分岐成立／分岐不成立）と、ＣＵＲＲＥＮＴ方向２４ｅが示す分岐方向とが一致する場合には（ステップＳ２４のＹｅｓルート）、ＣＵＲＲＥＮＴ方向２４ｅが示す分岐方向はそのままにＣＵＲＲＥＮＴカウンタ２４ｄの値を一つカウントアップする（ステップＳ２９）。
【００４６】
次いで、分岐履歴構築段階判定部２６が、当該分岐命令の分岐履歴が初期構築段階であるか否かを判定する（ステップＳ３０）。つまり、分岐履歴構築段階判定部２６は、当該分岐命令の分岐履歴におけるＴＡＫＥＮカウンタ２４ｂもしくはＮＯＴ−ＴＡＫＥＮカウンタ２４ｃの少なくとも一方が“０”であるか否かを判定し、ここで分岐履歴構築段階判定部２６が、ＴＡＫＥＮカウンタ２４ｂ及びＮＯＴ−ＴＡＫＥＮカウンタ２４ｃの少なくともいずれか一方が“０”である（つまり、初期構築段階である）と判定した場合（ステップＳ３０のＹｅｓルート）、分岐方向予測部２５による当該分岐命令の次の分岐方向の予測を行なわない（ステップＳ２３）。
【００４７】
しかし、分岐履歴構築段階判定部２６が、ＴＡＫＥＮカウンタ２４ｂ及びＮＯＴ−ＴＡＫＥＮカウンタ２４ｃいずれも“０”でない（つまり、初期構築段階でない）と判定した場合（ステップＳ３０のＮｏルート）、分岐方向予測部２５によって、当該分岐命令の次回の分岐方向についての予測が行なわれる（ステップＳ３１〜Ｓ３５）。
つまり、分岐方向予測部２５は、分岐履歴更新部２１による更新（ステップＳ２８もしくはステップＳ２９）後のＣＵＲＲＥＮＴ方向２４ｅが“１”（即ち、分岐成立）であり、且つ、ＣＵＲＲＥＮＴカウンタ２４ｄの値とＴＡＫＥＮカウンタ２４ｂの値とが一致するか否かを判断し（ステップＳ３１）、この条件に一致すると判断した場合には（ステップＳ３１のＹｅｓルート）、当該分岐命令の次回は分岐不成立となると予測する（ステップＳ３２）。
【００４８】
一方、上記条件に一致しない場合には（ステップＳ３１のＮｏルート）、分岐方向予測部２５は、分岐履歴更新部２１による更新後のＣＵＲＲＥＮＴ方向２４ｅが“０”（即ち、分岐不成立）であり、且つ、ＣＵＲＲＥＮＴカウンタ２４ｄの値とＮＯＴ−ＴＡＫＥＮカウンタ２４ｃの値とが一致するか否かを判断し（ステップＳ３３）、一致すると判断した場合には（ステップＳ３３のＹｅｓルート）、当該分岐命令は次回分岐成立となると予測する（ステップＳ３４）。
【００４９】
そして、ここ（ステップＳ３３）でも一致しないと判断した場合には（ステップＳ３３のＮｏルート）、分岐方向予測部２５は、当該分岐命令は次回も現在（更新後）の分岐方向が続く（つまり、現在の分岐方向と同方向になる）と予測する（ステップＳ３５）。
このように、分岐方向予測部２５は、分岐履歴記憶部２４に保持された分岐履歴（図３参照）に基づいて分岐命令の分岐方向を予測する（ステップＳ３２，Ｓ３４，Ｓ３５）。
【００５０】
次に、分岐履歴更新部２１の選択部２２及びリプレース部２３について説明する。
選択部２２は、分岐履歴更新部２１が分岐履歴記憶部２４に新たな分岐命令についての分岐履歴を登録する際（図８参照）に、分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１が使用中である場合に、これらｎ個のエントリ０〜ｎ−１の中から一のエントリを選択するものであり、選択部２２は後述する第１選択機能及び第２選択機能の２つの選択機能を有している。
【００５１】
選択部２２の第１選択機能は、分岐履歴記憶部２４に新たな分岐命令についての分岐履歴を登録する際に、分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１が使用中である場合に、これらｎ個のエントリ０〜ｎ−１の中から一のエントリを分岐履歴記憶部２４の分岐履歴に基づいて選択するものであり、具体的には、分岐履歴記憶部２４に保持された分岐履歴がすべて分岐成立であり、且つ、その分岐成立連続回数が所定回数（ここではｍ回）以上であるエントリを選択する。
【００５２】
すなわち、選択部２２の第１選択機能は、分岐履歴において、ＴＡＫＥＮカウンタ２４ｂ及びＮＯＴ−ＴＡＫＥＮカウンタ２４ｃが“０”であり、ＣＵＲＲＥＮＴ方向２４ｅが“１”を示しており、さらに、ＣＵＲＲＥＮＴカウンタ２４ｄが“ｍ”であるエントリを選択する。
ここで、選択部２２の第１選択機能によるリプレース対象のエントリ選択手順（第１選択ステップ）について図１１に示すフローチャート（ステップＳ４０〜Ｓ４５）を参照しながら説明する。図１１に示すように、選択部２２の第１選択機能は、分岐履歴記憶部２４のエントリに新たな分岐命令についての分岐履歴を登録する際に、分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１が使用中である場合に、各エントリの分岐履歴をチェックする（ステップＳ４０）。
【００５３】
なお、選択部２２は、分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１が使用中であるか否かを、図１２に示す信号生成回路３３により生成された分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１が使用中であることを示す信号（ＷＲＧＨＴ＿ＦＵＬＬ信号）によって検知する。図１２に示すように、ＷＲＧＨＴ＿ＦＵＬＬ信号が発生されるのは、新規エントリ登録指示信号（ＣＲＥＡＴＥ＿ＮＥＷ＿ＷＲＧＨＴ信号）が発生された際に、後述する選択部２２の第２選択機能によってエントリ０からエントリｎ−１の順に分岐履歴を登録すべく発生されるポインタ（ＷＲＧＨＴ＿ＮＸＴ＿ＰＴＲ）の指定するエントリの番号と、最後のエントリ番号（即ち、ｎ−１）とが一致する場合である。
【００５４】
そして、図１１に示すように、選択部２２の第１選択機能は、まず、ＣＵＲＲＥＮＴ方向２４ｅが示す現在の分岐方向が分岐成立（“１”）であるか否かを判断し（ステップＳ４１）、ここで分岐不成立（ＣＵＲＲＥＮＴ方向２４ｅが“０”）である場合には（ステップＳ４１のＮｏルート）、これからも分岐不成立する可能性があると判断して、この分岐履歴のエントリは選択しない（ステップＳ４２）。つまり、この分岐履歴のエントリはブランチヒストリ１５の予測を変更するために必要であると判断する。
【００５５】
一方、分岐成立（ＣＵＲＲＥＮＴ方向２４ｅが“１”）である場合には（ステップＳ４１のＹｅｓルート）、ＣＵＲＲＥＮＴカウンタ２４ｄの分岐成立連続回数が所定数（ここではｍ）を超えているか否かを判断する（ステップＳ４３）。
ここで、かかる分岐成立連続回数が所定数を超えていない場合には（ステップＳ４３のＮｏルート）、この分岐履歴のエントリは選択せず、上記ステップＳ４０にリターンする。
【００５６】
また、かかる分岐成立連続回数が所定数を超えている場合には（ステップＳ４３のＹｅｓルート）、この分岐履歴のＮＯＴ−ＴＡＫＥＮカウンタ２４ｃが“０”であるか否か、即ち、一度も分岐不成立になっていないか否かを判断する（ステップＳ４４）。
なお、かかる分岐成立連続回数が所定数（限界値；ｍ）と一致した場合には、図１３に示す信号生成回路３４において、ＣＵＲＲＥＮＴカウンタ２４ｄに保持された値が所定値（ｍ）以上になったこと、つまりオーバーフローしたことを示すＣＵＲＲＥＮＴ＿ＣＴＲ＿ＯＶＥＲＦＬＯＷ信号が生成される。
【００５７】
そして、ＮＯＴ−ＴＡＫＥＮカウンタ２４ｃが“０”以外である場合には（ステップＳ４４のＮｏルート）、これからも分岐不成立する可能性があると判断して、この分岐履歴のエントリは選択しない（ステップＳ４２）。
一方、ＮＯＴ−ＴＡＫＥＮカウンタ２４ｃが“０”である場合には（ステップＳ４４のＹｅｓルート）、これからも分岐成立がずっと続くと考えられ、この分岐履歴についてのブランチヒストリ１５における予測は変更不要であると判断し、この分岐履歴のエントリをリプレース対象として選択する（ステップＳ４５）。
【００５８】
つまり、図１４の信号生成回路３５に示すように、ＣＵＲＲＥＮＴ方向が“１”を示し、且つ、このエントリに対する新たな登録信号（ＣＲＥＡＴＥ＿ＷＲＧＨＴ信号）が発生されておらず、且つ、ＴＡＫＥＮカウンタ２４ｂが“０”であり、且つ、ＣＵＲＲＥＮＴカウンタ２４ｄからのオーバーフローを示す信号（ＣＵＲＲＥＮＴ＿ＣＴＲ＿ＯＶＥＲＦＬＯＷ信号；図１３参照）が発生されている場合に、選択部２２の第１選択機能によって、この分岐履歴のエントリをリプレース対象（上書き対象）とするＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ信号が生成される。
【００５９】
なお、図１５に示すように、ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ信号は分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１について発生されうる。
ここで、本情報処理装置１においてＣＵＲＲＥＮＴ＿ＣＴＲ＿ＯＶＥＲＦＬＯＷ信号が発生されるまでの経緯を図１６（ａ）〜（ｋ）に示すタイムチャートを参照しながら説明する。なお、図１６においてＴ１〜Ｔｘは情報処理装置１における処理時間単位を示す。
【００６０】
この図１６に示すように、分岐命令制御部１３からＣＯＭＰＬＥＴＥ信号と、実行された分岐命令の分岐が成立したことを示す信号（ＣＯＭＰ＿ＴＡＫＥＮ信号）とが発生されると（Ｔ１参照）、グローバルヒストリ２０内に新規エントリの登録指示信号（ＣＲＥＡＴＥ＿ＷＲＧＨＴ信号）が発生する（Ｔ２参照）。
そして、ここではエントリｎ−１に分岐履歴を新規登録したとすると、エントリｎ−１の分岐履歴におけるＣＵＲＲＥＮＴカウンタ２４ｄ（図中ＣＵＲＲＥＮＴ＿ＣＴＲと表記）の値が“１”にカウントアップされるとともに、ＣＵＲＲＥＮＴ方向２４ｅ（図中ＣＵＲＲＥＮＴ＿ＤＩＲと表記）が“１” （フラグがオン状態）になる（Ｔ３参照）。なお、ここでは、この時点で分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１が使用されたことになり、ＷＲＧＨＴ＿ＦＵＬＬ信号（図１２参照）も発生する（Ｔ３参照）。なお、このＷＲＧＨＴ＿ＦＵＬＬ信号は今後ずっと発生され続けることになる。
【００６１】
その後、再度同じ分岐命令が実行されるとＣＯＭＰＬＥＴＥ信号が発生されるが（Ｔ５参照）、当該分岐命令の分岐履歴がエントリｎ−１に既に保持されているため、当該分岐命令についての分岐履歴が分岐履歴記憶部２４に保持されていることを示すＷＲＧＨＴ＿ＨＩＴ＿ＯＲ信号が発生するとともに、エントリｎ−１でヒットしたことを示すＷＲＧＨＴｎ−１＿ＨＩＴ信号も発生する（Ｔ５参照）。
【００６２】
また、今回も当該分岐命令の分岐が成立すると、ＣＯＭＰ＿ＴＡＫＥＮ信号が発生し（Ｔ５参照）、当該分岐命令についての分岐履歴を保持するエントリｎ−１のＣＵＲＲＥＮＴカウンタ２４ｄの値が“２”にカウントアップされる（Ｔ６参照）。
さらに、その後も当該分岐命令が実行されて分岐が成立すると、Ｔ５及びＴ６の際の動作と同様の動作が繰り返される（Ｔ７〜Ｔｘ−１０参照）。
【００６３】
そして、当該分岐命令が、ｍ回連続して分岐成立すると（Ｔｘ−９参照）、エントリｎ−１のＣＵＲＲＥＮＴカウンタ２４ｄの値が“ｍ”にカウントアップされるとともに、ＣＵＲＲＥＮＴ＿ＣＴＲ＿ＯＶＥＲＦＬＯＷ信号が分岐履歴記憶部２４から発生され、さらに、リプレースする際にこのエントリｎ−１を使用すべくリプレース候補信号（ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴｎ−１信号；図中ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤと表記）が発生される（Ｔｘ−８参照）。
【００６４】
その後、当該分岐命令が実行されて分岐成立しても（Ｔｘ−５，Ｔｘ−３，Ｔｘ参照）、ＣＵＲＲＥＮＴカウンタ２４ｄはカウントアップされず（Ｔｘ−４，Ｔｘ−２参照）、このエントリｎ−１を対象にリプレースが行なわれない限り、ＣＵＲＲＥＮＴ＿ＣＴＲ＿ＯＶＥＲＦＬＯＷ信号及びＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴｎ−１信号が発生され続ける（Ｔｘ−７〜Ｔｘ参照）。
【００６５】
なお、選択部２２の第１選択機能によってリプレースの候補として選択されうるエントリが分岐履歴記憶部２４のエントリ０〜ｎ−１において同時に複数存在する場合が生じるが、第１選択機能では、分岐成立連続回数が所定回数以上である分岐履歴のエントリが同時に複数存在した場合でも、エントリ０からエントリｎ−１の順に最も上位の一のエントリをリプレース対象のエントリとして選択するようになっている。
【００６６】
図１７（ａ）〜（ｆ）は選択部２２の第１選択機能による一のエントリの選択手法を説明するための図である。この図１７（ａ）〜（ｆ）に示すように、選択部２２の第１選択機能は、リプレース候補信号（ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ信号）が発生しているかをエントリ０からエントリｎ−１の順に調べ、リプレース候補信号を検知した時点で検知されたリプレース候補信号を発生しているエントリをリプレース対象のエントリとして選択する。
【００６７】
つまり、図１７（ａ）に示すように、選択部２２の第１選択機能は、エントリ０からリプレース候補信号（ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ０）が発生している場合には、このエントリ０をリプレース候補として選択して、
また、図１７（ｂ）に示すように、エントリ０からはリプレース候補信号が出ていないが、エントリ１からリプレース候補信号（ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ１信号）が出ている場合には、エントリ１をリプレース対象のエントリとして選択して、エントリ１をリプレースに用いるための信号（ＵＳＥ＿ＷＲＧＨＴ１＿ＯＶＥＲＷＲＩＴＥ信号）を生成する。
【００６８】
さらに、図１７（ｃ）に示すように、エントリ０及びエントリ１からはリプレース候補信号が出ていないが、エントリ２からリプレース候補信号（ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ２）が出ている場合には、エントリ２をリプレース対象のエントリとして選択して、エントリ２をリプレースに用いるための信号（ＵＳＥ＿ＷＲＧＨＴ２＿ＯＶＥＲＷＲＩＴＥ信号）を生成する。なお、以下、図１７（ｄ）〜（ｆ）においても同様である。
【００６９】
選択部２２の第２選択機能は、分岐履歴記憶部２４に新たな分岐命令についての分岐履歴を登録する際に、分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１が使用中である場合に、これらｎ個のエントリ０〜ｎ−１の中から最も古く登録された一のエントリ選択するものである。つまり、選択部２２の第２選択機能は、ラウンドロビンでリプレース対象のエントリを選択する。
【００７０】
選択部２２の第２選択機能では、図１８に示す信号生成回路３６によってリプレース対象のエントリを選択するためのポインタ（ＷＲＧＨＴ＿ＮＥＸＴ＿ＰＴＲ＜Ｋ：０＞）が生成される。つまり、新規エントリ登録指示（ＣＲＥＡＴＥ＿ＮＥＷ＿ＷＲＧＨＴ）が発生すると、カウンタ３７によって１ずつカウントアップしていくことで、が生成される。
なお、図１９に示すように、このＷＲＧＨＴ＿ＮＥＸＴ＿ＰＴＲ＜Ｋ：０＞をデコーダ（図中ＤＥＣＯＲＤＥＲと表記）３１でデコードして各エントリ０〜ｎ−１を選択する信号（ＷＲＧＨＴ＿ＮＥＸＴ＿ＰＴＲ＿ＥＱ＿０〜ＷＲＧＨＴ＿ＮＥＸＴ＿ＰＴＲ＿ＥＱ＿ｎ−１）が得られる。
【００７１】
リプレース部２３は、選択部２２によって選択された一のエントリに新たな分岐命令についての分岐履歴を登録するものである。
次に、図２０に示すフローチャート（ステップＳ５０〜Ｓ５７）を参照しながら、本発明の一実施形態としてのリプレース方法の手順を説明すると、図２０に示すように、分岐履歴記憶部２４のエントリに新たな分岐命令についての分岐履歴を登録する際には、まず、選択部２２が分岐履歴記憶部２４のすべてのエントリ０〜ｎ−１が使用中であるか否かを判断し（ステップＳ５０）、ここですべてのエントリが使用中でなければ（ステップＳ５０のＮｏルート）、分岐履歴更新部２１が、ラウンドロビンで現在使用していない空きエントリを選択し、選択されたエントリに新たな分岐命令についての分岐履歴を登録する（ステップＳ５１）。
【００７２】
一方、すべてのエントリが使用中であれば（ステップＳ５０のＹｅｓルート）、選択部２２の第１選択機能が、図１１を参照しながら上述したように、分岐履歴記憶部２４に保持された分岐履歴に基づいて一のエントリを選択する（第１選択ステップ；ステップＳ５２）。つまり、現在までの分岐履歴がすべて分岐成立であって分岐成立回数が所定回数（ｍ回）以上である分岐履歴が存在すれば、この分岐履歴のエントリをリプレース対象のエントリとして選択する。
【００７３】
また、すべてのエントリが使用中であれば（ステップＳ５０のＹｅｓルート）、選択部２２の第２選択機能が、ラウンドロビンですべてのエントリ０〜ｎ−１の中で最も古く登録されたものをリプレース対象のエントリとして選択する（第２選択ステップ；ステップＳ５３）。
そして、選択部２２は、現在までの分岐履歴がすべて分岐成立であって分岐成立回数が所定回数（ｍ回）以上である分岐履歴が存在し、第１選択ステップ（ステップＳ５２）において第１選択機能により一のエントリが選択された場合には（ステップＳ５４のＹｅｓルート）、この第１選択ステップにおいて分岐履歴に基づいて選択された一のエントリを、第２選択ステップにおいて第２選択機能により選択された一のエントリよりも優先的に採用し（ステップＳ５５）、リプレース部２３が、第１選択ステップにおいて選択（採用）された一のエントリに新たな分岐命令についての分岐履歴を登録する（リプレースステップ；ステップＳ５７）。
【００７４】
なお、選択部２２は、現在までの分岐履歴がすべて分岐成立であって分岐成立回数が所定回数（ｍ回）以上である分岐履歴が存在せず、第１選択ステップ（ステップＳ５２）において第１選択機能により一のエントリが選択されなかった場合には（ステップＳ５４のＮｏルート）、第２選択ステップにおいて第２選択機能により選択された最も古く登録されたエントリを採用し（ステップＳ５６）、リプレース部２３が、第２選択ステップにおいて選択（採用）された一のエントリに新たな分岐命令についての分岐履歴を登録する（リプレースステップ；ステップＳ５７）。
【００７５】
なお、図２０におけるステップＳ５１，Ｓ５３〜Ｓ５７が選択ステップとして機能する。
また、選択部２２の第１選択機能によれば、図２１に示す信号生成回路３８によって、第１選択機能が選択した一のエントリを採用させるための信号（ＵＳＥ＿ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ信号）が生成される。つまり、エントリ０〜ｎ−１のいずれかからリプレース候補信号（ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ）が発生されると、ＵＳＥ＿ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ信号が生成されるのである。
【００７６】
そして、選択部２２では、図２２に示す信号生成回路３９によって、第１選択機能（第１選択ステップ）で選択された一のエントリが優先的に採用される。つまり、各エントリ０〜ｎ−１においてＵＳＥ＿ＷＲＧＨＴ＿ＴＯ＿ＯＶＥＲＷＲＩＴＥ信号（図１７参照）及びＷＲＧＨＴ＿ＮＥＸＴ＿ＰＴＲ＿ＥＱ信号（図１９参照）が生成されていても、第１選択機能によって、ＵＳＥ＿ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ信号（図２１参照）及びＷＲＧＨＴ＿ＦＵＬＬ信号（図１２参照）が生成された場合には、これら第１選択機能によって生成された信号が選択される。そして、選択された信号と新規エントリ登録指示（ＣＲＥＡＴＥ＿ＮＥＷ＿ＷＲＧＨＴ信号；図７参照）とによって、各エントリ０〜ｎ−１に新規エントリ（分岐履歴）を登録するためのＣＲＥＡＴＥ＿ＷＲＧＨＴ０信号〜ＣＲＥＡＴＥ＿ＷＲＧＨＴｎ−１信号が生成される。
【００７７】
このように、本発明の一実施形態としての情報処理装置１及びリプレース方法によれば、分岐履歴記憶部２４がリプレースのために新たな情報を特別に保持することなく、つまり、分岐履歴記憶部２４が本来から予測に使用するために元々備えている情報（即ち、Ｉ−Ａｄｄｒｅｓｓ２４ａ，ＴＡＫＥＮカウンタ２４ｂ，ＮＯＴ−ＴＡＫＥＮカウンタ２４ｃ，ＣＵＲＲＥＮＴカウンタ２４ｄ，ＣＵＲＲＥＮＴ方向２４ｅ）のみを用いて、分岐履歴更新部２１の選択部２２が、分岐履歴記憶部２４のエントリの中で、そのエントリが無くても分岐命令の分岐方向予測に影響を与えないエントリをリプレース対象として選択することができ、有限な資源を有効に利用することができるとともに、効率的なリプレースを実現することができる。
【００７８】
具体的には、選択部２２が分岐履歴記憶部２４のエントリに新規登録されてからすべて分岐成立している分岐履歴であって、かかる分岐成立の回数が所定回数（限界値）を超える分岐履歴を優先的に選択することによって、これからもずっと分岐成立すると考えられ、分岐予測に不要である分岐命令についてのエントリ（分岐履歴）を優先的にリプレース対象として選択することができるため、分岐履歴記憶部２４のエントリ０〜ｎ−１を効率良く使用することができるとともに、グローバルヒストリ２０の予測精度（性能）を向上させることができる。
【００７９】
〔２〕その他
なお、本発明は上述した実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で種々変形して実施することができる。
例えば、上述した実施形態では、選択部２２の第２選択機能がラウンドロビンで分岐履歴記憶部２４の複数エントリの中からリプレース対象のエントリを選択するように構成したが、本発明はこれに限定されるものではなく、選択部２２の第２選択機能がＬＲＵで分岐履歴記憶部２４の複数エントリの中からリプレース対象のエントリを選択するように構成してもよい。つまり、選択部２２の第２選択機能が、第２選択ステップにおいて、分岐履歴記憶部２４のすべてのエントリの中で分岐方向予測部２５による予測に用いられたのが最も古いエントリを選択するように構成してもよく、これによっても上述した実施形態と同様の効果を得ることができる。なお、この場合には、分岐履歴記憶部２４の分岐履歴において当該分岐履歴を使用（更新）した時期等の履歴を保持するように構成する必要がある。
【００８０】
また、上述した実施形態では、選択部２２の第１選択機能が第１選択ステップにおいて、分岐履歴記憶部２４に登録されてからすべて分岐成立であって分岐成立回数が所定回数以上である分岐履歴のエントリが同時に複数存在した場合でも、エントリ０からエントリｎ−１の順に最も上位の一のエントリをリプレース対象のエントリとして選択するように構成したが、本発明はこれに限定されるものではなく、選択部２２の第１選択機能によって複数のエントリが選択された場合には、選択された複数のエントリについて選択部２２の第２選択機能によって一のエントリに絞り込むようにしてもよい。
【００８１】
さらに、上述した実施形態では、選択部２２の第１選択機能によってリプレース対象の一のエントリが選択された場合に、第２選択機能によって選択された一のエントリを選択するためのポインタ（図１８及び図１９参照）は更新していなため、第１選択機能及び第２選択機能で選択されたエントリが一致していた場合には、まず、第１選択機能に基づいて当該エントリをリプレースした後に、再度、第２選択機能に基づいて当該エントリがリプレースされてしまうおそれがある。したがって、かかる場合には、第２選択機能に基づいて生成されるポインタを一つ進めるようにしてもよい。
【００８２】
また、上述した実施形態において、選択部２２によって選択されてリプレースされたエントリについての分岐命令が、再度分岐履歴記憶部２４に登録されないように構成してもよく、例えば、分岐ＲＳ１４において、分岐命令毎に分岐履歴記憶部２４に一旦登録されたがリプレースのために消去されたことを示す情報（フラグ等）を保持するように構成し、選択部２２がかかる情報に基づいてリプレース対象のエントリを選択するように構成してもよい。
【００８３】
なお、上述した実施形態では、本発明のリプレース方法をグローバルヒストリの分岐履歴記憶部２４に適用した場合について説明したが、本発明のリプレース方法の適用は、グローバルヒストリの分岐履歴記憶部２４に限定されるもではなく、例えば、フルアソシアティブ方式の各種記憶装置において、すべてのエントリが使用中である場合にエントリをリプレースする際に適用され、上述した実施形態と同様の作用効果を得ることができる。
【００８４】
例えば、アドレス変換に用いるＴＬＢ（Transration Lookaside Buffer）などにおいて、全プロセス空間で共通してエントリを用いることができることを意味するグローバルビットがオンであれば、リプレースの優先順位を下げるという手段が考えられる。あるいは、プロセス空間の識別に用いられるコンテキストが現在実行中の空間でないなら使用頻度が低いと考えられるので、優先的にリプレースするなどの手段が考えられる。
【００８５】
また、上述した命令フェッチアドレス生成部１０，命令フェッチ部１１，命令デコーダ１２，分岐命令制御部１３，分岐ＲＳ１４，ブランチヒストリ１５，分岐履歴更新部２１，選択部２２，リプレース部２３，分岐履歴記憶部２４，Ｉ−Ａｄｄｒｅｓｓ２４ａ，ＴＡＫＥＮカウンタ２４ｂ，ＮＯＴ−ＴＡＫＥＮカウンタ２４ｃ，ＣＵＲＲＥＮＴカウンタ２４ｄ，ＣＵＲＲＥＮＴ方向２４ｅ，分岐方向予測部２５，分岐履歴構築段階判定部２６，及びブランチヒストリ更新部２７としての機能は、コンピュータ（ＣＰＵ，情報処理装置，各種端末を含む）が所定のアプリケーションプログラム（リプレースプログラム）を実行することによって実現されてもよい。
【００８６】
そのプログラムは、例えばフレキシブルディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ等のコンピュータ読取可能な記録媒体に記録された形態で提供される。この場合、コンピュータはその記録媒体からストア命令制御プログラムを読み取って内部記憶装置または外部記憶装置に転送し格納して用いる。また、そのプログラムを、例えば磁気ディスク，光ディスク，光磁気ディスク等の記憶装置（記録媒体）に記録しておき、その記憶装置から通信回線を介してコンピュータに提供するようにしてもよい。
【００８７】
ここで、コンピュータとは、ハードウェアとＯＳ（オペレーティングシステム）とを含む概念であり、ＯＳの制御の下で動作するハードウェアを意味している。また、ＯＳが不要でアプリケーションプログラム単独でハードウェアを動作させるような場合には、そのハードウェア自体がコンピュータに相当する。ハードウェアは、少なくとも、ＣＰＵ等のマイクロプロセッサと、記録媒体に記録されたコンピュータプログラムを読み取るための手段とをそなえている。上記リプレースプログラムとしてのアプリケーションプログラムは、上述のようなコンピュータに、命令フェッチアドレス生成部１０，命令フェッチ部１１，命令デコーダ１２，分岐命令制御部１３，分岐ＲＳ１４，ブランチヒストリ１５，分岐履歴更新部２１，選択部２２，リプレース部２３，分岐履歴記憶部２４，Ｉ−Ａｄｄｒｅｓｓ２４ａ，ＴＡＫＥＮカウンタ２４ｂ，ＮＯＴ−ＴＡＫＥＮカウンタ２４ｃ，ＣＵＲＲＥＮＴカウンタ２４ｄ，ＣＵＲＲＥＮＴ方向２４ｅ，分岐方向予測部２５，分岐履歴構築段階判定部２６，及びブランチヒストリ更新部２７としての機能を実現させるプログラムコードを含んでいる。また、その機能の一部は、アプリケーションプログラムではなくＯＳによって実現されてもよい。
【００８８】
さらに、本実施形態としての記録媒体としては、上述したフレキシブルディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ，磁気ディスク，光ディスク，光磁気ディスクのほか、ＩＣカード，ＲＯＭカートリッジ，磁気テープ，パンチカード，コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ），外部記憶装置等や、バーコードなどの符号が印刷された印刷物等の、コンピュータ読取可能な種々の媒体を利用することもできる。
【００８９】
〔３〕付記
（付記１）
分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、
前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、
該分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、
該分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部と、
前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合に、前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択部と、
該選択部によって選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレース部とをそなえ、
前記選択部が、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有していることを特徴とする、情報処理装置。
【００９０】
（付記２）
前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で最も古く登録されたものを選択する第２選択機能を有し、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用することを特徴とする、付記１記載の情報処理装置。
【００９１】
（付記３）
前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で前記分岐方向予測部による予測に用いられたのが最も古いものを選択する第２選択機能を有し、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用することを特徴とする、付記１記載の情報処理装置。
【００９２】
（付記４）
前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴がすべて分岐成立であるエントリを前記一のエントリとして選択することを特徴とする、付記１〜３のいずれか１項に記載の情報処理装置。
（付記５）
前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴の分岐成立回数が所定回数以上であるエントリを選択することを特徴とする、付記４記載の情報処理装置。
【００９３】
（付記６）
前記分岐履歴記憶部は、前記分岐命令の前記分岐方向としての分岐成立／分岐不成立が２度切り替わるまでの分岐成立連続回数及び分岐不成立連続回数を前記分岐履歴として保持するとともに、
前記分岐方向予測部は、前記分岐成立連続回数及び前記分岐不成立連続回数に基づいて、前記分岐命令の分岐方向である分岐成立／分岐不成立を予測することを特徴とする、付記１〜５のいずれか１項に記載の情報処理装置。
【００９４】
（付記７）
前記分岐履歴記憶部に保持された前記分岐履歴が初期構築状態にあるか否かを判定する分岐履歴構築状態判定部をそなえ、
前記分岐方向予測部は、前記分岐履歴構築状態判定部が、前記分岐履歴が初期構築状態であると判定した場合には、当該分岐履歴に基づく前記分岐方向の予測を行なわないことを特徴とする、付記１〜６のいずれか１項に記載の情報処理装置。
【００９５】
（付記８）
分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、該分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、該分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部とをそなえた情報処理装置において、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合の前記エントリのリプレース方法であって、
前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択ステップと、
該選択ステップにおいて選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレースステップとを含み、
前記選択ステップが、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択ステップを含んでいることを特徴とする、リプレース方法。
【００９６】
（付記９）
前記選択ステップが、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で最も古く登録されたものを選択する第２選択ステップを含み、
前記選択ステップにおいて、前記第１選択ステップで選択されたエントリを、前記第２選択ステップで選択されたエントリよりも優先的に採用することを特徴とする、付記８記載のリプレース方法。
【００９７】
（付記１０）
前記選択ステップが、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で前記分岐方向予測部による予測に用いられたのが最も古いものを選択する第２選択ステップを含み、
前記選択ステップにおいて、前記第１選択ステップで選択されたエントリを、前記第２選択ステップで選択されたエントリよりも優先的に採用することを特徴とする、付記８記載のリプレース方法。
【００９８】
（付記１１）
前記選択ステップの前記第１選択ステップにおいて、前記分岐履歴記憶部に保持された前記分岐履歴がすべて分岐成立であるエントリを前記一のエントリとして選択することを特徴とする、付記８〜１０のいずれか１項に記載のリプレース方法。
（付記１２）
前記選択ステップの前記第１選択ステップにおいて、前記分岐履歴記憶部に保持された前記分岐履歴の分岐成立回数が所定回数以上であるエントリを選択することを特徴とする、付記１１記載のリプレース方法。
【００９９】
（付記１３）
分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、該分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、該分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部とをそなえた情報処理装置において、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合の前記エントリのリプレース機能をコンピュータに実現させるためのリプレースプログラムであって、
前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択部、及び、
該選択部によって選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレース部として、前記コンピュータを機能させるとともに、
前記選択部が、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有するように、前記コンピュータを機能させることを特徴とする、リプレースプログラム。
【０１００】
（付記１４）
前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で最も古く登録されたものを選択する第２選択機能を有するように、前記コンピュータを機能させるとともに、
前記選択部が、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用するように、前記コンピュータを機能させることを特徴とする、付記１３記載のリプレースプログラム。
【０１０１】
（付記１５）
前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で前記分岐方向予測部による予測に用いられたのが最も古いものを選択する第２選択機能を有するように、前記コンピュータを機能させるとともに、
前記選択部が、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用するように、前記コンピュータを機能させることを特徴とする、付記１３記載のリプレースプログラム。
【０１０２】
（付記１６）
前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴がすべて分岐成立であるエントリを前記一のエントリとして選択することを特徴とする、付記１３〜１５のいずれか１項に記載のリプレースプログラム。
（付記１７）
前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴の分岐成立回数が所定回数以上であるエントリを選択することを特徴とする、付記１６記載のリプレースプログラム。
【０１０３】
（付記１８）
分岐命令の分岐先を予測すべく当該分岐命令のアドレスと当該分岐命令の予測分岐先アドレスとの対応表を保持するブランチヒストリと、前記分岐命令の過去の分岐方向を分岐履歴として保持する分岐履歴記憶部と、該分岐履歴記憶部に保持された前記分岐履歴に基づいて前記分岐命令の分岐方向を予測する分岐方向予測部と、該分岐方向予測部によって予測された分岐方向に基づいて前記ブランチヒストリに保持された前記対応表を更新するブランチヒストリ更新部とをそなえた情報処理装置において、前記分岐履歴記憶部に新たな分岐命令についての分岐履歴を登録する際に前記分岐履歴記憶部のすべてのエントリが使用中である場合の前記エントリのリプレース機能をコンピュータに実現させるためのリプレースプログラムを記録したコンピュータ読取可能な記録媒体であって、
前記リプレースプログラムが、
前記分岐履歴記憶部のすべてのエントリの中から一のエントリを選択する選択部、及び、
該選択部によって選択された前記一のエントリに前記新たな分岐命令についての分岐履歴を登録するリプレース部として、前記コンピュータを機能させるとともに、
前記選択部が、前記分岐履歴記憶部に保持された前記分岐履歴に基づいて前記一のエントリを選択する第１選択機能を有するように、前記コンピュータを機能させることを特徴とする、リプレースプログラムを記録したコンピュータ読取可能な記録媒体。
【０１０４】
（付記１９）
前記リプレースプログラムが、
前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で最も古く登録されたものを選択する第２選択機能を有するように、前記コンピュータを機能させるとともに、
前記選択部が、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用するように、前記コンピュータを機能させることを特徴とする、付記１８記載のリプレースプログラムを記録したコンピュータ読取可能な記録媒体。
【０１０５】
（付記２０）
前記リプレースプログラムが、
前記選択部が、前記一のエントリとして、前記分岐履歴記憶部のすべてのエントリの中で前記分岐方向予測部による予測に用いられたのが最も古いものを選択する第２選択機能を有するように、前記コンピュータを機能させるとともに、
前記選択部が、前記第１選択機能によって選択されたエントリを、前記第２選択機能によって選択されたエントリよりも優先的に採用するように、前記コンピュータを機能させることを特徴とする、付記１８記載のリプレースプログラムを記録したコンピュータ読取可能な記録媒体。
【０１０６】
（付記２１）
前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴がすべて分岐成立であるエントリを前記一のエントリとして選択することを特徴とする、付記１８〜２０のいずれか１項に記載のリプレースプログラムを記録したコンピュータ読取可能な記録媒体。
【０１０７】
（付記２２）
前記選択部の前記第１選択機能は、前記分岐履歴記憶部に保持された前記分岐履歴の分岐成立回数が所定回数以上であるエントリを選択することを特徴とする、付記２１記載のリプレースプログラムを記録したコンピュータ読取可能な記録媒体。
（付記２３）
フルアソシアティブ方式の記憶装置において、該記憶装置に新たなエントリを登録する際に該記憶装置のすべてのエントリが使用中である場合の前記エントリのリプレース方法であって、
前記記憶装置のすべてのエントリの中から一のエントリを選択する選択ステップと、
該選択ステップにおいて選択された前記一のエントリに前記新たなエントリを登録するリプレースステップとを含み、
前記選択ステップが、前記記憶装置のエントリに元々そなわる情報に基づいて前記一のエントリを選択することを特徴とする、リプレース方法。
【図面の簡単な説明】
【０１０８】
【図１】本発明の一実施形態としての情報処理装置の構成を示すブロック図である。
【図２】本発明の一実施形態としての情報処理装置のブランチヒストリが保持する対応表のデータ構造を示す図である。
【図３】本発明の一実施形態としての情報処理装置のグローバルヒストリの分岐履歴記憶部が保持する分岐履歴のデータ構造を示す図である。
【図４】本発明の一実施形態としての情報処理装置のグローバルヒストリの分岐履歴記憶部が保持する分岐履歴の構成を説明するための図であり、（ａ）は分岐命令の分岐方向を示す具体例であり、（ｂ）は（ａ）の具体例のときの分岐履歴のデータ構造を示す図である。
【図５】本発明の一実施形態としての情報処理装置のグローバルヒストリのブランチヒストリ更新部の動作手順を説明するためのフローチャートである。
【図６】本発明の一実施形態としての情報処理装置のグローバルヒストリの分岐履歴更新部，分岐方向予測部，及び分岐履歴構築段階判定部の動作手順（分岐履歴記憶部の検索方法の手順）を説明するためのフローチャートである。
【図７】本発明の一実施形態としての情報処理装置においてＣＲＥＡＴＥ＿ＮＥＷ＿ＷＲＧＨＴ信号を生成する信号生成回路を示す図である。
【図８】本発明の一実施形態としての情報処理装置のグローバルヒストリの分岐履歴更新部による分岐履歴記憶部への新規エントリ登録のための手順を示すフローチャートである。
【図９】本発明の一実施形態としての情報処理装置においてＷＲＧＨＴ＿ＨＩＴ信号を生成する信号生成回路を示す図である。
【図１０】本発明の一実施形態としての情報処理装置においてＷＲＧＨＴ＿ＨＩＴ＿ＯＲ信号を生成する信号生成回路を示す図である。
【図１１】本発明の一実施形態としての情報処理装置の分岐履歴更新部の選択部の第１選択機能によるエントリ選択手順を説明するためのフローチャートである。
【図１２】本発明の一実施形態としての情報処理装置においてＷＲＧＨＴ＿ＦＵＬＬ信号を生成する信号生成回路を示す図である。
【図１３】本発明の一実施形態としての情報処理装置においてＣＵＲＲＥＮＴ＿ＣＲＴ＿ＯＶＥＲＦＬＯＷ信号を生成する信号生成回路を示す図である。
【図１４】本発明の一実施形態としての情報処理装置においてＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ信号を生成する信号生成回路を示す図である。
【図１５】本発明の一実施形態としての情報処理装置のグローバルヒストリの分岐履歴記憶部におけるすべてのエントリからＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ＿ＷＲＧＨＴ信号が発生されることを説明するための図である。
【図１６】本発明の一実施形態としての情報処理装置のグローバルヒストリの分岐履歴記憶部からＣＵＲＲＥＮＴ＿ＣＴＲ＿ＯＶＥＲＦＬＯＷ信号が発生されるまでの経緯を説明するためのタイムチャートである。
【図１７】（ａ）〜（ｆ）は本発明の一実施形態としての情報処理装置の分岐履歴更新部の選択部の第１選択機能による一のエントリの選択手法を説明するための図である。
【図１８】本発明の一実施形態としての情報処理装置においてＷＲＧＨＴ＿ＮＥＸＴ＿ＰＴＲ＜Ｋ：０＞信号を生成する信号生成回路を示す図である。
【図１９】本発明の一実施形態としての情報処理装置において生成されるＷＲＧＨＴ＿ＮＥＸＴ＿ＰＴＲ＜Ｋ：０＞信号を説明するための図である。
【図２０】本発明の一実施形態としてのリプレース方法の手順を説明するためのフローチャートである。
【図２１】本発明の一実施形態としての情報処理装置においてＵＳＥ＿ＯＶＥＲＷＲＩＴＥ＿ＣＡＮＤＩＤＡＴＥ信号を生成する信号生成回路を示す図である。
【図２２】本発明の一実施形態としての情報処理装置においてＣＲＥＡＴＥ＿ＷＲＧＨＴ信号を生成する信号生成回路を説明するための図である。
【符号の説明】
【０１０９】
１  情報処理装置
１０  命令フェッチアドレス生成部
１１  命令フェッチ部
１２  命令デコーダ
１３  分岐命令制御部
１４  分岐リザベーションステーション（分岐ＲＳ）
１５  ブランチヒストリ
１５ａ  対応表
２０  グローバルヒストリ
２１  分岐履歴更新部
２２  選択部
２３  リプレース部
２４  分岐履歴記憶部
２４ａ  Ｉ−Ａｄｄｒｅｓｓ
２４ｂ  ＴＡＫＥＮカウンタ
２４ｃ  ＮＯＴ−ＴＡＫＥＮカウンタ
２４ｄ  ＣＵＲＲＥＮＴカウンタ
２４ｅ  ＣＵＲＲＥＮＴ方向
２５  分岐方向予測部
２６  分岐履歴構築段階判定部
２７  ブランチヒストリ更新部
３０〜３６，３８，３９  信号生成回路
３７  カウンタ
【図１】
2006099528.tif 000003
【図２】
2006099528.tif 000004
【図３】
2006099528.tif 000005
【図４】
2006099528.tif 000006
【図５】
2006099528.tif 000007
【図６】
2006099528.tif 000008
【図７】
2006099528.tif 000009
【図８】
2006099528.tif 000010
【図９】
2006099528.tif 000011
【図１０】
2006099528.tif 000012
【図１１】
2006099528.tif 000013
【図１２】
2006099528.tif 000014
【図１３】
2006099528.tif 000015
【図１４】
2006099528.tif 000016
【図１５】
2006099528.tif 000017
【図１６】
2006099528.tif 000018
【図１７】
2006099528.tif 000019
【図１８】
2006099528.tif 000020
【図１９】
2006099528.tif 000021
【図２０】
2006099528.tif 000022
【図２１】
2006099528.tif 000023
【図２２】
2006099528.tif 000024