(57)【要約】【課題】  多段化したパイプライン構造のプロセッサが分岐命令を効率良く実行するために大容量の分岐ターゲットバッファを実装すると、回路規模が増大してしまう。【解決手段】  ＣＰＵ１０１からの命令フェッチにおいて、キャッシュメモリ１０２のアクセスエントリが変わる場合、先行して分岐ターゲットバッファ１０４をアクセスし、予測分岐先アドレスに対して予めキャッシュアクセスすることにより、後に分岐命令が実行されて分岐予測が行われた際にキャッシュヒットさせるようにする。これにより、予測分岐先アドレスに対する命令フェッチで分岐命令実行時にキャッシュメモリ１０２から命令データを読み出すことが可能となり、分岐ターゲットバッファ１０４に分岐先アドレスの命令データを保持しない、あるいは保持するデータ量を減らすことが可能であり、回路規模を削減できる。【選択図】  図１
2005122343.tif 000002
【特許請求の範囲】
【請求項１】
中央処理装置（ＣＰＵ）と、前記ＣＰＵが実行する命令を格納するキャッシュメモリと、分岐ターゲットバッファとを有する情報処理システムにおけるキャッシュメモリ制御方法であって、
前記ＣＰＵから第１のアドレスで前記キャッシュメモリへアクセスする第１のステップと、
前記ＣＰＵから第２のアドレスで前記キャッシュメモリへアクセスする第２のステップと、
前記第１のアドレスの前記キャッシュメモリに対するエントリアドレス部分である第１のエントリアドレスと、前記第２のアドレスの前記キャッシュメモリに対するエントリアドレス部分である第２のエントリアドレスとを比較する第３のステップと、
前記第３のステップにおいて一致しないと判定した場合に前記分岐ターゲットバッファ内に前記キャッシュメモリに対するエントリアドレス部分及びタグアドレス部分が、前記第２のアドレスのタグアドレス及びエントリアドレスと一致する分岐元アドレスが存在するか否かを判定する第４のステップと、
前記第４のステップにおいて存在すると判定した場合に、前記分岐ターゲットバッファから前記分岐元アドレスに対応する分岐先アドレスを出力する第５のステップと、
前記分岐先アドレスへの分岐が成立するか否かを予測する第６のステップと、
前記第６のステップにおいて分岐成立と予測した場合に前記分岐先アドレス又は前記分岐先アドレス以降のアドレスで前記キャッシュメモリをアクセスし、前記分岐先アドレスのデータ又は前記分岐先アドレス以降のアドレスのデータが前記キャッシュメモリ内に存在するか否かを判定する第７のステップと、
前記第７のステップにおいて存在しないと判定された場合に前記第７のステップでアクセスしたアドレスのブロックデータを前記キャッシュメモリに転送する第８のステップとを備えたことを特徴とするキャッシュメモリ制御方法。
【請求項２】
請求項１記載のキャッシュメモリ制御方法において、
前記第７のステップにて、前記分岐先アドレスの前記キャッシュメモリに対するエントリアドレスと前記第２のエントリアドレスとが一致しない場合に、前記キャッシュメモリにアクセスすることを特徴とするキャッシュメモリ制御方法。
【請求項３】
請求項１記載のキャッシュメモリ制御方法において、
前記第７のステップにて、前記分岐先アドレスの前記キャッシュメモリに対するエントリアドレスと前記第２のエントリアドレスとが任意のアドレス以上離れている場合に、前記キャッシュメモリをアクセスすることを特徴とするキャッシュメモリ制御方法。
【請求項４】
請求項１記載のキャッシュメモリ制御方法において、
前記第７のステップにて存在しないと判定した場合には、前記キャッシュメモリ内の前記分岐先アドレスのブロックデータを転送するエントリのアドレスデータとブロックデータとを一時バッファに転送する第９のステップと、
前記分岐先アドレスのブロックデータを前記キャッシュメモリ内に転送する第１０のステップと、
前記第２のアドレスより以降のアドレスである第３のアドレスの分岐命令を前記ＣＰＵが実行した際に分岐予測が不正解な場合に分岐先アドレスのブロックデータが前記キャッシュメモリ内に格納されたか否かを判定する第１１のステップと、
前記第１１のステップで格納されていないと判定した場合には処理を中断し、格納されたと判定された場合には、前記一時バッファ内の前記アドレスデータ及び前記ブロックデータを、前記分岐先アドレスのブロックデータを格納した前記キャッシュメモリ内の前記エントリに書き戻す第１２のステップとを更に備えたことを特徴とするキャッシュメモリ制御方法。
【請求項５】
請求項４記載のキャッシュメモリ制御方法において、
前記第７のステップにて、前記分岐先アドレスの前記キャッシュメモリに対するエントリアドレスと前記第２のエントリアドレスとが一致しない場合に、前記キャッシュメモリにアクセスすることを特徴とするキャッシュメモリ制御方法。
【請求項６】
請求項４記載のキャッシュメモリ制御方法において、
前記第７のステップにて、前記分岐先アドレスの前記キャッシュメモリに対するエントリアドレスと前記第２のエントリアドレスとが任意のアドレス以上離れている場合に、前記キャッシュメモリをアクセスすることを特徴とするキャッシュメモリ制御方法。
【請求項７】
中央処理装置（ＣＰＵ）と、前記ＣＰＵが実行する命令を格納するキャッシュメモリと、前記キャッシュメモリの制御装置と、分岐ターゲットバッファと、前記分岐ターゲットバッファの制御装置と、前記ＣＰＵから前記キャッシュメモリへのアクセスアドレスのエントリアドレス部分を保持するエントリアドレスバッファと、前記ＣＰＵから前記キャッシュメモリへのアクセスアドレスのエントリアドレス部分と前記エントリアドレスバッファ内の値とを比較するエントリアドレス比較器とを有する情報処理システムにおけるキャッシュメモリ制御装置であって、
前記エントリアドレス比較器による比較結果が一致しない場合に、前記キャッシュメモリ制御装置は前記分岐ターゲットバッファの制御装置に検索要求を出力することを特徴とするキャッシュメモリ制御装置。
【請求項８】
請求項７記載のキャッシュメモリ制御装置において、
前記キャッシュメモリへのアクセスアドレスと、前記検索要求による前記分岐ターゲットバッファからの予測分岐先アドレスとを比較し、前記予測分岐先アドレスによる前記キャッシュメモリへのアクセスを行うか否かの判定を行うことを特徴とするキャッシュメモリ制御装置。
【請求項９】
中央処理装置（ＣＰＵ）と、前記ＣＰＵが実行する命令を格納するキャッシュメモリと、分岐ターゲットバッファとを有する情報処理システムにおけるキャッシュメモリ制御方法であって、
前記ＣＰＵは、前記分岐ターゲットバッファ内の情報を用いて分岐予測を行うＣＰＵであり、
前記ＣＰＵが分岐予測を行う第１のステップと、
前記第１のステップでの予測結果である予測分岐先アドレス又は当該予測分岐先アドレス以降のアドレスにより前記キャッシュメモリをアクセスする第２のステップと、
前記キャッシュメモリ内に前記第２のステップでアクセスしたアドレスのブロックデータが存在するか否かを判定する第３のステップと、
前記第３のステップで存在しないと判定した場合に前記第２のステップでアクセスしたアドレスのデータを含むブロックデータを前記キャッシュメモリに転送するエントリの前記キャッシュメモリ内のアドレスデータとブロックデータとを一時バッファに転送する第４のステップと、
前記第２のステップでアクセスしたアドレスのデータを含むブロックデータの主記憶から前記キャッシュメモリへの転送を行う第５のステップと、
前記分岐予測が正解か不正解かを判定する第６のステップと、
前記第６のステップにより不正解と判定された場合、前記主記憶から前記キャッシュメモリへの転送による前記第２のステップでアクセスしたアドレスのブロックデータが前記キャッシュメモリ内に格納されたか否かを判定する第７のステップと、
前記第７のステップで格納されていないと判定した場合には処理を中断し、格納したと判定した場合には前記一時バッファから前記キャッシュメモリへ前記アドレスデータと前記ブロックデータとを書き戻す第８のステップとを備えたことを特徴とするキャッシュメモリ制御方法。
【請求項１０】
分岐元情報と分岐先情報とを格納する分岐ターゲットバッファであって、
前記分岐元情報は、分岐命令のキャッシュメモリ内での格納位置情報であることを特徴とする分岐ターゲットバッファ。
【請求項１１】
中央処理装置（ＣＰＵ）と、キャッシュヒットした位置情報を出力するキャッシュメモリと、分岐元情報と分岐先情報とを格納する分岐ターゲットバッファとを有する情報処理システムにおけるキャッシュメモリ制御方法であって、
前記分岐元情報は、分岐命令の前記キャッシュメモリ内での格納位置情報であり、
前記ＣＰＵから前記キャッシュメモリにアクセスする第１のステップと、
前記第１のステップにおいてキャッシュヒットである場合に命令データを出力するとともに、ヒットした位置情報を出力する第２のステップと、
前記第２のステップによって出力された命令データ内の分岐命令を前記ＣＰＵが実行した場合に分岐成立か否かを判断する第３のステップと、
前記位置情報が前記分岐ターゲットバッファ内に存在するか否かを検索する第４のステップと、
前記第４のステップにおいて前記位置情報が前記分岐ターゲットバッファ内に存在しないと判断した場合に前記位置情報を前記分岐ターゲットバッファ内に格納する第５のステップとを備えたことを特徴とするキャッシュメモリ制御方法。
【請求項１２】
中央処理装置（ＣＰＵ）と、キャッシュヒットした位置情報を出力するキャッシュメモリと、分岐元情報と分岐先情報とを格納する分岐ターゲットバッファとを有する情報処理システムにおけるキャッシュメモリ制御方法であって、
前記分岐元情報は、分岐命令の前記キャッシュメモリ内での格納位置情報であり、
前記ＣＰＵから前記キャッシュメモリにアクセスする第１のステップと、
前記第１のステップにおいてキャッシュヒットである場合に前記分岐ターゲットバッファへ前記キャッシュメモリのキャッシュヒットした位置情報と前記キャッシュメモリに対するエントリアドレスとを入力する第２のステップと、
前記分岐ターゲットバッファ内に位置情報及びエントリアドレスが一致する分岐元情報があるか否かを検索する第３のステップと、
前記第３のステップにおいて一致する分岐元情報がある場合に対応する分岐先アドレスを出力する第４のステップと、
前記分岐先アドレスへの分岐が成立するか否かを予測する第５のステップと、
前記分岐先アドレス又は前記分岐先アドレス以降のアドレスのブロックデータが前記キャッシュメモリ内に存在するか否かを判定する第６のステップと、
前記第６のステップにおいて存在しないと判定した場合に前記分岐先アドレス又は前記分岐先アドレス以降のアドレスのブロックデータを前記キャッシュメモリ内に転送する第７のステップとを備えたことを特徴とするキャッシュメモリ制御方法。
【請求項１３】
請求項１２記載のキャッシュメモリ制御方法において、
前記第６のステップにて存在しないと判断した場合、前記分岐先アドレスのブロックデータを格納する前記キャッシュメモリ内のアドレスデータとブロックデータとを一時バッファに退避する第８のステップと、
前記分岐先アドレスのブロックデータを転送する第９のステップと、
前記分岐元アドレスの分岐命令実行により分岐予測不成立の場合に前記第９のステップで退避した前記アドレスデータと前記ブロックデータとを前記キャッシュメモリ内に書き戻す第１０のステップとを備えたことを特徴とするキャッシュメモリ制御方法。
【請求項１４】
請求項１２記載のキャッシュメモリ制御方法において、
前記第１のステップでのアクセスアドレスが、前記第１のステップより１回前の前記キャッシュメモリへのアクセスエントリアドレスと異なる場合に、前記第３のステップを行うことを特徴とするキャッシュメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリを搭載し、かつ分岐予測を行うマイクロプロセッサに関するものである。
【背景技術】
【０００２】
命令を順次実行するマイクロプロセッサにおいて、処理性能向上のために高周波数動作を実現する多くの改良が行われている。例えば、パイプラインの多段化は、高速動作実現のための一般的な手法として多くのプロセッサで取り入れられている。
【０００３】
パイプライン構造のプロセッサにおいては、単位時間あたりの命令実行数が増加する。ただし、分岐命令実行、特に条件分岐命令の実行時には、条件分岐命令の実行と分岐先命令の実行開始サイクルまでの間、パイプラインに命令が投入されないサイクルである「パイプラインバブル」が発生し、単位時間あたりの命令実行効率が低下する。特に高周波数動作のために多段化したパイプラインを実装するプロセッサでは、このパイプラインバブルによる実行効率の低下の度合いが大きい。
【０００４】
この実行効率の低下を極力抑えるための技術として、分岐ターゲットバッファ（Branch Target Buffer：ＢＴＢ）又は分岐履歴バッファと呼ばれるものが知られている。この技術は、分岐命令実行時に過去の分岐命令実行の情報から分岐先を予測し、予測した分岐先の命令フェッチを分岐命令の分岐先が確定する前に先行的に開始し、あるいは保持しておいた分岐命令データを先行的に実行するものである。
【０００５】
分岐ターゲットバッファによれば、過去に実行した分岐命令、主に条件分岐命令の実行ＰＣ（プログラムカウンタ）、及び、分岐先ＰＣ、分岐成立度合いの情報を保持している。同じＰＣの分岐命令を再度実行した際には、過去の分岐命令実行時の情報から分岐先、分岐成立／不成立を予測し、先行的に命令フェッチ、あるいは命令実行させ、前述のパイプラインの実行効率低下を抑える。
【０００６】
一方で、パイプラインの段数を多段化する高周波数動作のマイクロプロセッサでは、プロセッサの動作周波数に対して外部のメモリアクセスの周波数が大きく異なるため、プロセッサが行うメモリアクセスのペナルティが実行性能に大きく影響する。これを解決するため、一般的にキャッシュメモリを実装する。
【０００７】
また、キャッシュメモリのタグ部に分岐先アドレスと、その有効ビットとを保持する方法がある。しかしながら、肥大化するプログラムに対応する大容量のキャッシュメモリを実装すると、全エントリに対して分岐先アドレスの情報を保持する回路がキャッシュメモリに必要であり、回路規模が増大する欠点がある（特許文献１の図３参照）。
【０００８】
以上のとおり、多段化したパイプラインを持つ高周波数動作のマイクロプロセッサにおいては、分岐ターゲットバッファとキャッシュメモリとを実装するのが一般的である。しかしながら、分岐ターゲットバッファとキャッシュメモリとをともに実装することにより、回路規模が増大する。
【０００９】
分岐ターゲットバッファに分岐元アドレス及び分岐先アドレスのみを保持することとすると回路規模は減少するが、分岐先アドレスがキャッシュヒットしない場合には予測分岐先の命令フェッチのペナルティにより分岐予測の効果が消えてしまう。
【００１０】
また、分岐先アドレスを予測し、予め命令フェッチした場合、キャッシュミスの場合には既にキャッシュメモリにある他の命令データを追い出さなくてはならない。しかしながら、分岐ターゲットバッファの出力である分岐先アドレスは分岐先の予測アドレスであり、実際にプロセッサが分岐元アドレスの命令を実行した場合に予測不成立（分岐予測ミス）になる可能性もある。この場合、従来の方法では、結果として無駄なアクセスによって有効なキャッシュメモリ内のデータを追い出してしまうことになり、後のキャッシュヒット率の低下を招いてしまう。
【特許文献１】特開平７−２００４０６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
以上のとおり、パイプライン構成のマイクロプロセッサにおいて、キャッシュメモリを実装し、かつ分岐命令実行時の実行効率低下を防ぐために分岐ターゲットバッファを実装する場合、回路規模が増大する。
【００１２】
また、分岐予測を行った際、分岐予測ミスの場合には既にキャッシュメモリ内部に存在する有効なデータを追い出し、実際には実行されない分岐予測ミスした予測アドレスに対するブロックデータをキャッシュにリフィルしてしまう。
【００１３】
本発明の目的は、キャッシュメモリと分岐ターゲットバッファとを搭載したマイクロプロセッサにおける以上の課題を解決することにある。
【課題を解決するための手段】
【００１４】
本発明によれば、キャッシュメモリと分岐ターゲットバッファとを搭載したマイクロプロセッサの命令フェッチにおいて、キャッシュメモリのアクセスエントリが変わるような場合に、キャッシュメモリにアクセスすると同時に分岐ターゲットバッファにもアクセスし、分岐ターゲットバッファの出力により再度キャッシュメモリをアクセスする。これにより予測分岐先の命令を予めキャッシュメモリに取り込むことが可能となる。プロセッサが後にそのエントリのブロックデータ内に存在する分岐命令を実行した際には、分岐先の命令データをキャッシュメモリから短いサイクルで読み出し完了することが可能となる。また、実際にプロセッサが分岐命令を実行し分岐ターゲットバッファをアクセスした際にキャッシュメモリ内に分岐先命令が存在する可能性が高くなる。
【００１５】
また、分岐ターゲットバッファの分岐元アドレスの代わりに、分岐命令が存在する命令キャッシュの位置情報を保持し、検索する場合でもその位置情報により検索する。先の方法に加え、キャッシュメモリと分岐ターゲットバッファを連動させて動作させることにより、分岐元情報としてアドレスをプログラムカウンタの全アドレスビット保持する分岐ターゲットバッファよりも回路規模の縮小が可能である。
【００１６】
また、予測された分岐先アドレスによるキャッシュアクセスにおいて、キャッシュミスの場合に、置き換える命令キャッシュ内のデータを一時バッファに退避しておく。分岐予測が成立しなかった場合、キャッシュメモリ内の元の位置に一時バッファから書き戻すことにより、分岐不成立時の余分なキャッシュデータの置き換えの発生をなくすことが可能となり、分岐予測ミスによるキャッシュヒット率の低下を低減することが可能となる。
【発明の効果】
【００１７】
本発明によれば、分岐ターゲットバッファを実装する場合に、予測分岐先の命令データを保持する必要がない、あるいは予測分岐先の命令を持つ場合でも少ない容量での実装で分岐実行時の分岐ペナルティ、命令フェッチペナルティを低減することが可能であり、省面積で高効率の分岐命令実行が可能となる。
【００１８】
また、分岐元情報として少ない容量での実装で、一般的な分岐ターゲットバッファと同等の効果を得ることが可能である。
【００１９】
更に、分岐予測が不正解となった場合、予測分岐先アドレスへの先行する命令フェッチによる不必要な命令キャッシュデータの追い出しが発生しないため、全体でのキャッシュヒット率を分岐予測の不正解で低下することを防ぐことが可能である。
【発明を実施するための最良の形態】
【００２０】
以下、図面を参照しながら、本発明の実施の形態を説明する。
【００２１】
《第１の実施形態》
図１は本発明の第１の実施の形態におけるシステム構成図である。図１のシステムは、命令を順次実行するＣＰＵ１０１と、ＣＰＵ１０１の命令を格納するキャッシュメモリ１０２と、キャッシュメモリ１０２の制御を行うキャッシュ制御部１０３と、分岐ターゲットバッファ１０４と、分岐ターゲットバッファ制御部１０５と、主記憶からデータを読み出すＢＣＵ（バスコントロールユニット）１０６とからなる。
【００２２】
ＣＰＵ１０１は、１命令２バイト（１６ビット）長の命令セットアーキテクチャに基づくプロセッサであり、命令供給不足による実行ペナルティを低減するために８バイトの命令バッファ（ＩＢ）１０７を装備している。デコーダ１３６には、デコードデータセレクタ１３７により命令バッファ１０７内の命令データからのみではなく、命令フェッチデータバス１３４上のデータも直接入力可能である。
【００２３】
キャッシュメモリ１０２は、４Ｋバイトの２ウェイセットアソシアティブ構成である。すなわち、キャッシュメモリ１０２は１ウェイにつき１２８エントリのラインメモリで構成され、ＣＰＵ１０１からのアドレスのビット１０からビット４の７ビットでエントリ指定される。例えばアドレスが「００００００１０」の場合、エントリアドレスは「０１」である。
【００２４】
分岐ターゲットバッファ１０４は、分岐命令実行によりアドレスが現在までのＰＣから連続的に変化しない場合（一般的には分岐成立側）のアドレスを保持し、その情報を元に分岐予測を行う。
【００２５】
ＣＰＵ１０１が命令フェッチを行う場合、まず命令アドレス生成部１０８により命令フェッチを行うアドレスが生成され、フェッチアドレスバス１１１にアドレスが出力される。同時にキャッシュ制御部１０３にキャッシュ要求１３５が出力される。フェッチアドレスバス１１１は３２ビットのアドレスバスである。
【００２６】
ここで、分岐命令以外の命令を実行しているものとする。命令フェッチにおいて、フェッチアドレスバス１１１のフェッチアドレスは、タグ入力セレクタ１１２を通り、かつ、エントリを示すアドレスフィールドであるビット１０からビット４のみタグアドレス１１３としてタグメモリ１１４に入力される。
【００２７】
タグアドレス１１３により指定されたエントリのタグデータは、タグデータ出力バス１１５を通じて比較器１１６に入力される。フェッチアドレスバス１１１上のアドレスデータが比較器入力セレクタ１１７を通り、そのうちのタグフィールドが比較アドレス１１８として比較器１１６に入力される。キャッシュメモリ１０２は１ウェイが１２８エントリのキャッシュメモリであるので、比較アドレス（タグデータ）１１８はアドレスのビット３１からビット１１の値である。
【００２８】
比較器１１６は、比較アドレス１１８とタグデータ出力バス１１５上のタグデータとを比較し、一致した場合にヒット信号１１９をキャッシュ制御部１０３に出力する。ここでヒット信号１１９はウェイ毎、つまり２ビットの信号で出力され、どのウェイにヒットしたかもキャッシュ制御部１０３は判断することができる。例えば、ウェイ０にヒットした場合には「０１」が、ウェイ１にヒットした場合には「１０」が出力され、「００」の場合にはどのウェイにもヒットしなかった、つまりキャッシュミスであったことを示す。
【００２９】
キャッシュ制御部１０３は、ヒット信号１１９が「００」である場合、すなわちキャッシュミスの場合には、不図示の主記憶からキャッシュメモリ１０２へのブロックデータの転送（リフィル）を行うため、ＢＣＵ１０６にリフィル要求信号１２０を出力する。
【００３０】
ヒット信号１１９が「０１」又は「１０」の場合はキャッシュヒットであり、キャッシュメモリ１０２内のデータメモリ１２１からキャッシュリードデータバス１３２に命令データを出力し、命令フェッチデータバス１３４を通じて命令バッファ１０７に命令データを格納し、あるいはデコードデータセレクタ１３７を通してデコーダ１３６に命令データを入力する。
【００３１】
キャッシュデータメモリ１２１は、フェッチアドレスバス１１１上のアドレスに該当するデータを含む６４ビットの命令データをキャッシュリードデータバス１３２に出力する。すなわち、図１のシステムは、キャッシュヒットの場合に１回の命令フェッチで６４ビットの命令データをフェッチすることが可能なシステムである。
【００３２】
また、キャッシュライトデータバス１３８は３２ビット幅であり、キャッシュメモリ１０２のリフィルはアドレスを１つ指定し、連続した４回のデータ転送で実施する。例えば、エントリ「００」へのリフィルの場合には、アドレスとして「００」を指定し、連続した４サイクルでデータを書き込むことでリフィルが完了する。
【００３３】
図２に、動作のフローチャートを示す。まず、ＣＰＵ１０１の命令フェッチが発生するとフェッチするアドレスが生成され、フェッチアドレスバス１１１に出力される（ステップＳ１）。
【００３４】
出力されたアドレスはエントリアドレスバッファ１２２に入力され、キャッシュメモリ１０２のエントリアドレスを指定するフィールド部分であるビット１０からビット４までのデータがエントリアドレスバッファ１２２に格納される（ステップＳ２）。保持される期間は次のキャッシュアクセスが発生するまでである。
【００３５】
同時に、フェッチアドレスはフェッチアドレスバス１１１を介してエントリアドレス比較器１２３にも入力される。エントリアドレスバッファ１２２が保持している値はエントリアドレス保持データ１２４としてエントリアドレス比較器１２３に入力され、エントリアドレス比較器１２３は入力されているフェッチアドレスバス１１１のエントリ部と、エントリアドレス保持データ１２４とを比較する（ステップＳ３）。一致する場合には今のキャッシュアクセスと以前のキャッシュアクセスのアクセスエントリ先は同じであり、異なる場合には連続して命令フェッチを行っているシーケンスにおいて命令フェッチ先のブロックデータが異なるところにアクセスすることを意味する。
【００３６】
キャッシュ制御部１０３は、フェッチアドレスバス１１１上のアドレスでキャッシュメモリ１０２をアクセスしたサイクルで、エントリアドレス比較器１２３からエントリ一致信号１２５を受け取る。エントリ一致信号１２５が「不一致」である場合、キャッシュ制御部１０３は分岐ターゲットバッファ制御部１０５に検索要求（ＣＨ）１２６を出力する（ステップＳ４）。一致である場合、処理は終了する（ステップＳ５）。
【００３７】
分岐ターゲットバッファ制御部１０５は、ＣＰＵ１０１からの検索要求１２７なのか、あるいはキャッシュ制御部１０３からの検索要求１２６なのかを判断し（ステップＳ６）、検索モード信号１２８を出力する。
【００３８】
この検索モード信号１２８は、フェッチアドレスバス１１１上のアドレスデータのエントリアドレス部分以下のビット（ビット３からビット０）を除くフィールドが一致する分岐元アドレスを検索するのか、全ビット比較するのかを指定する信号であり、「１」の場合にはアドレスのビット４以上のフィールドが一致する分岐元アドレスを検索するものとする。この信号１２８は、検索要求（ＣＨ）１２６が入力されたときに「１」が（ステップＳ７）、検索要求（ＣＰＵ）１２７が入力されたときには「０」が出力される（ステップＳ８）。
【００３９】
分岐ターゲットバッファ１０４は、分岐元アドレス保持部１２９内でフェッチアドレスバス１１１上のアドレスのエントリアドレス以上（ビット４以上）のフィールドが一致する分岐元アドレスを検索し（ステップＳ９）、分岐先アドレス保持部１３０から対応する分岐先アドレスを予測分岐先アドレスバス１３１に出力する（ステップＳ１１）。なお、検索要求（ＣＰＵ）１２７の場合には、アドレスが一致する分岐元アドレスを検索する（ステップＳ１０）。
【００４０】
予測分岐先アドレスバス１３１は、キャッシュメモリ１０２の比較器１１６に入力され、予測分岐先アドレスバス１３１上のアドレスで指定されるエントリのタグデータと、予測分岐先アドレスバス１３１上のデータのタグフィールドとが比較器１１６で比較される（ステップＳ１２）。ここで「一致」である場合、予測分岐先は既にキャッシュメモリ１０２内に存在することになり終了する（ステップＳ１３）。
【００４１】
「不一致」である場合、分岐先アドレスはキャッシュメモリ１０２内に存在しないので、ＢＣＵ１０６にリフィル要求信号１２０を出力し、予測分岐先アドレスのブロックデータのリフィルを開始する（ステップＳ１４）。
【００４２】
以上のフローにより、実際にＣＰＵ１０１が分岐命令をパイプラインに投入する前に、予め予測される分岐先アドレスの分岐命令を転送することができる。
【００４３】
次に、図３、図４を用いて、詳細なシーケンスを説明する。図３に、実行するプログラムを示す。アドレス「００００」からアドレス「００２Ｅ」及び「１０２０」から「１０２８」までの命令を実行する。図３には本実施形態の説明で必要な命令のみ示している。また、ＣＰＵ１０１は３２ビットのアドレスデータを扱うが、ここでは下位１６ビットのみの表記としている（上位アドレスは全て０とする）。
【００４４】
アドレス「００００」から「０００Ｅ」までは、キャッシュメモリ１０２のエントリアドレスが「００」であるエントリに格納される。同様に、アドレス「００１０」からアドレス「００１Ｅ」まではエントリアドレスが「０１」、アドレス「００２０」からアドレス「００２Ｅ」まではエントリアドレスが「０２」、アドレス「１０２０」から「１０２８」まではエントリアドレスが「０２」の各エントリに格納される。
【００４５】
ＣＰＵ１０１内の命令バッファ１０７は８バイト（６４ビット）すなわち４命令を格納することが可能であり、かつ、３命令消費すると、次の６４ビット分の命令データを含む命令フェッチのアドレスを命令アドレス生成部１０８が生成し、キャッシュメモリ１０２へのフェッチアクセスを開始する。
【００４６】
実行する命令は各命令１サイクルで実行されるものとし、アドレス「００１８」にある「ｉｎｓｔ４」命令がアドレス「１０２０」への条件分岐命令であるものとする。
【００４７】
ＣＰＵ１０１は、一般的な６段のパイプライン構造のＣＰＵであり、ＩＦ、ＤＥＣ０，ＤＥＣ１，ＥＸ０，ＥＸ１，ＷＢの６ステージで構成される。ＩＦステージは命令をフェッチするステージ、ＤＥＣ０は命令のデコードの第１処理であり、ＤＥＣ１は第２処理である。分岐命令であるか否かはＤＥＣ０ステージにおいて判定される。ＥＸ０は第１実行ステージ、ＥＸ１は第２実行ステージである。条件分岐命令が実行されるとき、分岐条件の成立・不成立はＥＸ０ステージで判定され、分岐先アドレスはＥＸ１ステージで計算される。ＷＢはライトバックステージである。
【００４８】
更に、アドレス「００００」、「００１０」、「００２０」のブロックデータは既にキャッシュメモリ１０２内に存在し、アドレス「００００」から「００１Ｅ」までの命令をフェッチする場合にはキャッシュヒットになるものとする。また、アドレス「１０２０」以降の命令はまだキャッシュメモリ１０２内に存在せず、アドレス「１０２０」へのアクセスはキャッシュミスとなるものとする。
【００４９】
図４に本実施形態のタイミング図を示す。サイクル２０１からサイクル２０３まで、命令バッファ１０７にはアドレス「０００８」から「０００Ｅ」までの命令が入っており、ＣＰＵ１０１は順次命令を実行しているものとする。サイクル２０２では次の命令フェッチのアドレスである「００１０」が命令アドレス生成部１０８により生成され、キャッシュアクセスが開始される。タグアドレス１１３は「０１」となる。このアクセスはキャッシュヒットであり、サイクル２０３でキャッシュリードデータバス１３２として命令ｉｎｓｔ０，ｉｎｓｔ１，ｉｎｓｔ２，ｉｎｓｔ３を含む６４ビットのデータ（図中２１１）が読み出され、サイクル２０４に命令バッファ１０７に格納される。
【００５０】
サイクル２０４から４サイクルの間、ＣＰＵ１０１は命令を順次命令バッファ１０７から取り込み実行していく。サイクル２０４では、同時にフェッチアドレスバス１１１のエントリアドレスデータがエントリアドレスバッファ１２２のエントリアドレス保持データ１２４と比較される。図４中に示すように、エントリアドレスバッファ１２２はサイクル２０２で「００」である。今、フェッチアドレスは「００１０」であり、エントリアドレスは「０１」のため不一致であり、エントリ一致信号１２５は０が出力され、キャッシュ制御部１０３は分岐ターゲットバッファ制御部１０５に検索要求（ＣＨ）１２６を出力する。分岐ターゲットバッファ制御部１０５は、サイクル２０２で分岐ターゲットバッファ１０４へ検索モード信号１２８として「１」を出力する。分岐ターゲットバッファ１０４は、フェッチアドレスバス１１１上のアドレスデータのエントリアドレスとタグアドレスとが一致する分岐元アドレスを検索し、対応する分岐先アドレスを予測分岐先アドレス１３１としてサイクル２０３で出力する。サイクル２０３で出力されるのは「１０２０」である。
【００５１】
更に、予測分岐先アドレス１３１はサイクル２０３でキャッシュメモリ１０２に入力され、サイクル２０４で比較器１１６によりアドレス「１０２０」がキャッシュヒットか否かを判定する。
【００５２】
アドレス「１０２０」はまだキャッシュメモリ１０２内に存在してないためキャッシュミスとなり、ＢＣＵ１０６にアドレス「１０２０」のブロックデータのリフィル要求信号１２０をサイクル２０４で出力する。
【００５３】
ＢＣＵ１０６からのリフィルのデータ転送は、リフィル要求信号１２０を受けてから３サイクル目で最初のデータ転送が行われ、連続して４サイクルの転送サイクルにより完了する。図４においては、サイクル２０６からサイクル２０９でキャッシュライトデータバス１３８にアドレス「１０２０」のブロックデータ２１２が出力されリフィルが実行される。
【００５４】
ＣＰＵ１０１は順次命令を実行し続けている。サイクル２０７では条件分岐命令である「ｉｎｓｔ４」命令がパイプラインのＩＦステージに入り、条件分岐命令が実行開始される。次のサイクル２０８ではＤＥＣ０ステージに「ｉｎｓｔ４」命令が入り、このサイクルで条件分岐命令と判定される。
【００５５】
サイクル２０８では同時にＤＥＣ０の命令のＰＣ（図１中の分岐命令ＰＣ１０９）がフェッチアドレスバス１１１に出力され、分岐ターゲットバッファ１０４を検索するため、検索要求（ＣＰＵ）１２７が分岐ターゲットバッファ制御部１０５に出力され、分岐ターゲットバッファ制御部１０５から検索モード信号１２８として「０」が出力される。
【００５６】
分岐ターゲットバッファ１０４は、フェッチアドレスバス１１１上の値、すなわちＤＥＣ０ステージのＰＣの値に対応する予測分岐先アドレスをアドレスバス１３１へ出力し、キャッシュメモリ１０２内に予測分岐先アドレスのブロックデータがあるかどうかを検索する。
【００５７】
予測分岐先アドレスである「１０２０」のデータは、サイクル２０２における分岐ターゲットバッファ１０４の先行的なアクセスにより、サイクル２０４から既にキャッシュメモリ１０２へのブロックデータ転送の準備が開始している。サイクル２０８ではキャッシュメモリ１０２内にアドレス「１０２０」のデータが存在するため、キャッシュヒットとして読み出し可能である（図４中のデータ２１３）。
【００５８】
つまり、サイクル２０９では、予測分岐先アドレス１３１の命令はキャッシュヒットとして命令バッファ１０７に格納されると同時に命令デコーダ１３６に入力され、分岐先アドレスの命令データである「ｉｎｓｔ  ｔ０」はサイクル２０９で直ちにパイプラインに投入可能となる。したがって、条件分岐命令の実行によるパイプラインバブルは、図４中に２１４で示すように２サイクルのペナルティで済む。
【００５９】
本実施形態によれば、予測分岐先の命令データを分岐ターゲットバッファ１０４に持たずに、分岐元アドレスと、分岐先アドレスと、分岐先アドレスの命令データとを保持する従来の分岐ターゲットバッファと同じ又は１サイクル増加のサイクル数となる。つまり、従来と同様のパイプライン効率を、より少ない回路規模で実現できる。
【００６０】
《第２の実施形態》
図５には、第２の実施形態でのシステム構成を示す。これは、図１のシステムに、エントリアドレス保持データ１２４と予測分岐先アドレスバス１３１上のアドレスデータのエントリアドレスとを比較する第２エントリアドレス比較器５０１と、アクセス続行信号５０２とが追加されたシステムである。
【００６１】
図６に、第２の実施形態における動作のフローを示す。図２に示すフローとステップＳ１１までは同じであるため、図６ではステップＳ１１に続くステップＳ２１から示す。
【００６２】
前記ステップＳ１１において分岐ターゲットバッファ１０４が出力した予測分岐先アドレス１３１と、今アクセスしている命令フェッチアドレスとのエントリ比較を第２エントリアドレス比較器５０１で行う（ステップＳ２１）。このエントリアドレス比較において、予測分岐先アドレスのエントリアドレスが一致する場合は処理を終了する（ステップＳ２４）。一致しない場合には、アクセス続行要求５０２をキャッシュ制御部１０３に出力し（ステップＳ２２）、第１の実施形態と同様、分岐先アドレスのリフィルを開始する。図６のステップＳ２３〜Ｓ２５は、図２中のステップＳ１２〜Ｓ１４と同様である。
【００６３】
なお、図６のステップＳ２１においては一致するか否かを判定したが、あるアドレス範囲を設定し、分岐先アドレスと今のキャッシュアクセスアドレスとのエントリが所定のアドレス範囲以上離れている場合に続行するような判定を行ってもよい。アドレスの範囲は予め回路的に固定するのもよいし、ＣＰＵ１０１からアクセス可能なレジスタに設定して反映させてもよい。
【００６４】
一般的にキャッシュメモリはプログラムの参照の局所性を利用しており、現在命令フェッチしているアドレスに対するキャッシュアクセスがキャッシュヒットである場合、その近傍のエントリアドレスに対するキャッシュアクセスはキャッシュヒットとなる可能性が高い。逆にエントリアドレスが今アクセスしているアドレスのエントリアドレスから離れるにつれ、キャッシュミスする可能性が高くなるのである。
【００６５】
《第３の実施形態》
図７に、第３の実施形態のシステム構成図を示す。図７のシステムでは、図１のシステムに加え、キャッシュメモリ１０２の任意のエントリのタグデータを一時的に保持するタグ一時バッファ３０１と、そのエントリのブロックデータを保持するデータ一時バッファ３０２とを有する。
【００６６】
タグ一時バッファ３０１のデータはタグ一時バッファ出力バス３０３を経由してタグメモリ１１４に書き込みが可能であり、データ一時バッファ３０２のデータはデータ一時バッファ出力バス３０４をライトデータセレクタ３０５で選択することにより、データメモリ１２１に書き込み可能である。
【００６７】
タグ一時バッファ３０１及びデータ一時バッファ３０２のデータは、ＣＰＵ１０１による分岐予測の正解・不正解の結果、及び、分岐ターゲットバッファ１０４の予測分岐先アドレスを保持している予測アドレスバッファ３０６のアドレスと、現在分岐ターゲットバッファ１０４が出力している予測分岐先アドレスとの比較結果から復帰判定を行う復帰判定器３０７の復帰要求３０８により、復帰処理が行われる。
【００６８】
図８に、第３の実施形態における動作のフローを示す。第３の実施形態では図２、及び、図６のステップＳ１２までは同じフローであるので、以降のフローについてのみ図示している。
【００６９】
前記ステップＳ１２においてキャッシュミスと判定されると、キャッシュリフィルの開始（ステップＳ１４）と並行し、キャッシュリフィル先のウェイを決定する（ステップＳ３１）。更にキャッシュリフィルするアドレス（予測分岐先アドレス）を保持させる（ステップＳ３４）。
【００７０】
次に、リフィル先に決定したウェイの予測分岐先アドレスで指定されるエントリ、すなわち予測分岐先アドレスのリフィルによってキャッシュメモリ１０２から追い出されるブロックデータ（タグデータと命令データ）をタグ一時バッファ３０１及びデータ一時バッファ３０２に退避させる（ステップＳ３２、Ｓ３３）。
【００７１】
次に、実際に分岐命令がＣＰＵ１０１によって実行された時点で分岐ターゲットバッファ１０４の検索、予測分岐先アドレスの出力が行われる（ステップＳ３５）。
【００７２】
次に、ステップＳ１１での予測分岐先アドレス（先行予測分岐先アドレス）と、分岐命令実行時の予測分岐先アドレスとが一致するかどうかを調べる（ステップＳ３６）。これと並行して、分岐先アドレスのフェッチを行う（ステップＳ４１）。
【００７３】
ステップＳ３６の判定では、ステップＳ３４で保持しておいたアドレスデータと今行っている予測に係る分岐先アドレスとが一致するかどうかを判定する。一致しない場合にはリフィルのデータ転送が既にキャッシュメモリ１０２内に格納されたかどうかの判定を行い（ステップＳ４０）、まだ格納されていない場合はリフィルを中断（ステップＳ４１）して終了する（ステップＳ４３）。ステップＳ４０において既に格納済みと判断した場合には、ステップＳ３１での予測分岐先アドレスのブロックデータをリフィルしたキャッシュメモリ１０２のエントリにタグ一時バッファ３０１、データ一時バッファ３０２のデータの書き戻しを行う（ステップＳ３８、Ｓ３９）。
【００７４】
ステップＳ３６、Ｓ４０、Ｓ４１と並行して、分岐命令がＥＸ０ステージに入ると分岐予測が正解か不正解かの分岐予測判定をする（ステップＳ３７）。正解の場合には処理を終了する（ステップＳ４３）。不正解の場合にはステップＳ３６の判定の不一致時と同様のフローにて、予測分岐先アドレスのブロックデータをリフィルしたキャッシュメモリ１０２のエントリにタグ一時バッファ３０１、データ一時バッファ３０２のデータの書き戻しを行う（ステップＳ３８、Ｓ３９）。
【００７５】
図９には、第３の実施形態におけるタイミング図を示す。図９のサイクル４０２までは図４中のサイクル２０３までと同じである。また、サイクル４０１での分岐ターゲットバッファ１０４の先行的なアクセスによる予測分岐先アドレスはサイクル４０７でのＣＰＵ１０１による分岐ターゲットバッファ１０４のアクセスによる予測分岐先アドレスと同じアドレスであるものとし、かつ、サイクル４０７でのＣＰＵ１０１による分岐ターゲットバッファ１０４の分岐予測は不正解になるものとする。
【００７６】
今、キャッシュリフィルにおいて最初のデータが転送されてくるまでに最低３サイクルかかるシステムを想定する。第３の実施形態ではこの３サイクル内で次の動作を行う。
【００７７】
まず、サイクル４０２においてキャッシュミスと判定されると、サイクル４０３で予測分岐先アドレスのブロックデータを格納するキャッシュメモリ１０２内のデータを、タグ一時バッファ３０１、データ一時バッファ３０２に退避開始する。この動作において、ブロックデータを退避させるデータのアドレスをキャッシュ制御部１０３から出力することにより、データアドレス１４１を変化させる。
【００７８】
本実施形態においては、キャッシュリフィルでウェイ０をリフィルの対象に選択するものとし、ウェイ０のエントリ「２」のオフセット「０」から６４ビットを読み出すのに「０２０」（図中４２０）、同エントリのオフセット８のデータを読み出すのに「０２８」（図中４２１）をデータアドレス１４１に出力する。
【００７９】
データメモリ１２１は１回のアクセスで６４ビットの読み出しが可能であるため、１ブロックデータを読み出すには２サイクルあればよい。図９に示すようにサイクル４０３、サイクル４０４において、データアドレス１４１を「０２０」（図中４２０）、「０２８」（図中４２１）と変化させ、データ一時バッファ３０２にデータを退避させる。この結果、図９中に示すようにタグ一時バッファ３０１はサイクル４０５からタグデータ出力１１５の値を保持開始、データ一時バッファ３０２の下位６４ビットはサイクル４０５から、上位６４ビットはサイクル４０６からキャッシュリードデータ１３２の値を保持する。
【００８０】
第３の実施形態のシステムでは、サイクル４０６から先のリフィル要求に対するブロックデータ転送が開始される（図中２１２は、リフィルの転送データ）。
【００８１】
なお、キャッシュリフィルの最初のデータの転送までにタグ一時バッファ３０１、データ一時バッファ３０２への転送を行うことができない場合、これら一時バッファ３０１，３０２への転送を行った後にリフィル要求信号１２０を出力すればよい。
【００８２】
次に、分岐命令が実際にＣＰＵ１０１で実行され、サイクル４０７、サイクル４０８では第１の実施形態の図４中のサイクル２０８、サイクル２０９と同様の分岐予測が行われる。
【００８３】
サイクル４０８において、サイクル４０２で先行的に予測した分岐先アドレスと、サイクル４０８での予測分岐先アドレスとが一致するかどうかを判定する。「ｉｎｓｔ４」命令、すなわち分岐（branch）命令の実行において、分岐予測がはずれ分岐不成立となった場合には、分岐不成立側のアドレスの命令フェッチを再開し、先に退避したデータをキャッシュメモリ１０２内に書き戻す。ただし、この説明では「一致する」ものとする。
【００８４】
分岐不成立側の命令フェッチ、本実施形態の場合、「ｉｎｓｔ５」命令の命令フェッチであるため、フェッチアドレスとしてアドレス「００１Ａ」を生成してキャッシュアクセスを開始する（サイクル４０９）。このアドレスはキャッシュヒットとなるためサイクル４１０で命令データを読み出し可能であり、「ｉｎｓｔ５」命令はサイクル４１０でパイプラインに投入される。
【００８５】
次にタグ一時バッファ３０１、データ一時バッファ３０２に退避したデータをキャッシュメモリ１０２に復帰させる（サイクル４１１〜サイクル４１２）。図９において、４２５、４２６、４２７、４２８がデータ一時バッファ３０２からのライトデータである。
【００８６】
サイクル４０８で不一致の場合には、サイクル４１０からの復帰処理をサイクル４０８から行う。
【００８７】
以上の手法により、分岐予測が外れた場合でも分岐予測の不正解による命令キャッシュ１０２内のデータの無駄な追い出しが発生しなくなる。結果として、分岐予測が正解の場合には分岐予測側のデータがキャッシュメモリ１０２内に格納され、不正解の場合には元のキャッシュメモリ１０２の状態とすることが可能であり、分岐予測の不正解によるキャッシュヒット率の低下を抑えることが可能となる。
【００８８】
なお、本実施形態では分岐ターゲットバッファ１０４に分岐元アドレスと分岐先アドレスとを保持するものとし、サイクル４０１において先行的に分岐ターゲットバッファ１０４を検索する例を示したが、従来の分岐ターゲットバッファを用いたシステムにおいて、サイクル４０１での先行的な分岐ターゲットバッファアクセスを行わず、サイクル４０７でのＣＰＵ１０１の分岐ターゲットバッファアクセス時に同様のタグ一時バッファ、データ一時バッファへの退避処理を行ってもよい。従来の分岐ターゲットバッファを用いた場合でも、不必要なキャッシュデータの追い出しによるキャッシュヒット率の低減が可能である。
【００８９】
《第４の実施形態》
図１０は、第４の実施形態のシステム構成図である。図１のシステムに対して、図１１に示す分岐ターゲットバッファ６０１を有し、キャッシュメモリ１０２のヒットしたウェイ情報を保持するヒットウェイバッファ６０２を有するシステムである。また、キャッシュメモリ１０２にアクセスしたフェッチアドレスのエントリアドレスより下位のアドレス（オフセットアドレス）を保持する下位アドレスバッファ６０５も有し、分岐ターゲットバッファ６０１にその保持データが入力される。
【００９０】
図１１の分岐ターゲットバッファ６０１は、有効ビット１０００に加えて、分岐元情報としてウェイ番号１００１と、エントリアドレス１００２と、オフセットアドレス１００３とを保持し、かつ対応する分岐先アドレス１００４を保持する。すなわち、ＣＰＵ１０１がフェッチしたあるアドレスに対して、キャッシュメモリ１０２内でヒットとなる場合に、当該キャッシュメモリ１０２からヒットした位置情報としてウェイ番号、あるいは相当する情報を出力させ、ウェイ番号、エントリアドレス及びオフセットアドレスが一致するものに対応する分岐先アドレスを予測分岐先アドレスとして出力するのである。
【００９１】
通常、キャッシュメモリ１０２が有効な状態でＣＰＵ１０１が分岐命令を実行する場合、実際に分岐命令がＩＦステージ以降で実行状態にある場合には、その分岐命令自身はキャッシュメモリ１０２内に存在する。なぜなら、ＩＦステージではキャッシュメモリ１０２から実行している分岐命令を読み出しているからである。つまり、分岐命令の読み出しをキャッシュメモリ１０２からのみ行っている場合には、分岐命令実行中に再度自命令のアドレスでキャッシュメモリ１０２をアクセスした場合、必ずキャッシュヒットとなる。
【００９２】
さて、図１０のシステムにおいて、検索モード信号１２８が「１」の場合は、エントリアドレス保持データ１２４と分岐ターゲットバッファ６０１内の分岐元情報であるエントリアドレス１００２とが一致するエントリを検索する。「０」の場合には、「１」の検索条件に加え、ヒットウェイバッファ６０２のヒットウェイ保持データ６０３と分岐ターゲットバッファ６０１内のウェイ番号１００１とが一致し、かつ下位アドレス出力６０６とオフセットアドレス１００３とが一致する分岐元情報を検索する。
【００９３】
まず、分岐ターゲットバッファ６０１へ分岐元情報と分岐先情報とをセットする動作を説明する。
【００９４】
ＣＰＵ１０１が分岐命令を含む命令データをキャッシュメモリ１０２から読み出す。この読み出し時点においてキャッシュヒットであっても、ミスであっても命令バッファ１０７に分岐命令を含む命令データが格納された時点ではキャッシュメモリ１０２にはその分岐命令を含むブロックデータが存在している。
【００９５】
次に、実際に分岐命令がＣＰＵ１０１により実行され、分岐成立、不成立が確定したサイクルに、確定した分岐先が現在実行中の命令のラインアドレスと異なる場合、すなわちＰＣが非連続変化する場合に、ＣＰＵ１０１から分岐先命令のフェッチアドレスが出力された後に分岐命令のＰＣの値をフェッチアドレスバス１１１に出力し、キャッシュメモリ１０２をアクセスする。
【００９６】
また、同時に分岐命令ＰＣバッファ６０４に分岐命令のＰＣを格納する。分岐命令ＰＣバッファ６０４は、分岐ターゲットバッファ６０１に予測分岐先アドレスとして書き込みが行われるまでデータを保持する。
【００９７】
比較器１１６から出力されるヒット信号１１９は、エントリアドレス保持データ１２４とともに分岐ターゲットバッファ６０１に入力される。分岐先情報としては分岐命令ＰＣバッファ６０４の値を格納する。
【００９８】
図１２は、分岐ターゲットバッファ６０１への分岐元情報及び分岐先情報のセット時の動作タイミングチャートである。実行する命令列は、図３に示す命令列である。図１２において、アドレス「００１８」の「ｉｎｓｔ４」命令（分岐命令）の分岐情報は、分岐ターゲットバッファ６０１内にまだ存在していないものとする。また、キャッシュのヒット、ミス状態は第１の実施形態と同じであるものとする。
【００９９】
サイクル７０１において、「ｉｎｓｔ４」命令がパイプラインのＩＦステージに入る。この「ｉｎｓｔ４」命令の分岐方向及び分岐先アドレスが実際に確定するのはサイクル７０２である。このサイクル７０２で確定した分岐先アドレスがフェッチアドレスバス１１１に出力され、キャッシュメモリ１０２へのアクセスが行われる。
【０１００】
分岐先であるアドレス「１０２０」がキャッシュヒットである場合、サイクル７０３で命令データが読み出される。一方、キャッシュミスである場合、サイクル７０４でリフィル要求信号１２０が出力され、分岐先アドレス「１０２０」のキャッシュリフィルが行われる。図１２はキャッシュミスの場合のタイミング図である。
【０１０１】
サイクル７０２で分岐先アドレスのキャッシュアクセスが行われ、次のサイクル７０３で分岐ターゲットバッファ６０１への書き込みのためのキャッシュアクセスが行われる。
【０１０２】
サイクル７０２において、「ｉｎｓｔ４」命令のＰＣがフェッチアドレスバス１１１に出力され、「ｉｎｓｔ４」命令のキャッシュメモリ１０２内のヒットミスが判定される。本実施形態において、「ｉｎｓｔ４」命令はキャッシュウェイ０に存在しているとしているので、サイクル７０４でヒット信号１１９として「０１」が出力され、ヒットウェイバッファ６０２に入力される。
【０１０３】
同時に分岐命令ＰＣバッファ６０４に「ｉｎｓｔ４」命令のＰＣが格納され、エントリアドレスバッファ１２２は分岐命令のＰＣのエントリアドレスである「０１」となり、この値が分岐ターゲットバッファ６０１に入力される（図中７１０、７１１）。これらの値がサイクル７０４に分岐ターゲットバッファ６０１に書き込まれ、分岐元情報としてセットされる。
【０１０４】
つまり、アドレス「００１８」に対応して、「ウェイ０、エントリ１、下位アドレス８」が分岐元情報として、分岐先アドレス「１０２０」が分岐先情報としてそれぞれ分岐ターゲットバッファ６０１に登録される。
【０１０５】
次に、既に分岐ターゲットバッファ６０１内に「ｉｎｓｔ４」命令に対する分岐情報が存在している場合の「ｉｎｓｔ４」分岐命令実行時の動作を説明する。
【０１０６】
図１３は、この場合の動作タイミング図である。まず、サイクル８０１でアドレス「００１０」への命令フェッチが開始される。「ｉｎｓｔ０」命令を含む命令データはキャッシュヒットであり、サイクル８０２ではヒット信号１１９として「０１」が出力される。
【０１０７】
サイクル８０２ではアドレス「００１０」の命令データの出力が行われると同時に、ヒット信号１１９とエントリアドレス保持データ１２４とが分岐ターゲットバッファ６０１に入力され、キャッシュ制御部１０３から分岐ターゲットバッファ６０１に検索要求（ＣＨ）１２６が出力され、分岐先アドレスの予測が行われる。サイクル８０２での検索はキャッシュ制御部１０３からの検索であるために検索モードは「１」である。
【０１０８】
サイクル８０３では検索アドレスが出力され、再度キャッシュメモリアクセスが行われ、予測分岐先アドレスがキャッシュヒットするかミスするかが判定される。ここでキャッシュヒットの場合は何も行わない。ミスの場合は第１及び第２の実施形態と同様の処理が行われる。
【０１０９】
図１３には、キャッシュミス時の動作を示している。第１及び第２の実施形態と同様に、分岐先アドレスのキャッシュヒットミス判定サイクル８０３においてＢＣＵ１０６にリフィル要求信号１２０が出力され、予測分岐先アドレスのリフィルが行われる。
【０１１０】
次に「ｉｎｓｔ４」命令がパイプラインに入った時点での分岐予測動作を説明する。まず、サイクル８０４で「ｉｎｓｔ４」命令がＤＥＣ０ステージに入った時点で、ＣＰＵ１０１から分岐命令のＰＣであるアドレス「００１８」がフェッチアドレスバス１１１に出力される。このアドレスでキャッシュメモリ１０２をアクセスする。また、同時にエントリアドレスバッファ１２２にエントリアドレスである「０１」が、下位アドレス保持部６０５に下位アドレスである「８」がそれぞれ格納される。
【０１１１】
サイクル８０５では「ｉｎｓｔ４」命令を含む命令データがキャッシュメモリ１０２内に必ず存在するため、アドレス「００１８」のキャッシュアクセスはキャッシュヒットとなり、ヒット信号１１９として「０１」が出力され分岐ターゲットバッファ６０１に入力される。
【０１１２】
サイクル８０５では検索要求（ＣＨ）１２６がキャッシュ制御部１０３から分岐ターゲットバッファ６０１に出力される。分岐ターゲットバッファ制御部１０５にはサイクル８０４で既に検索要求（ＣＰＵ）１２７が入力されているため、サイクル８０５の検索要求（ＣＨ）１２６はＣＰＵ１０１の分岐予測の検索と判断し、検索モード１２８として「０」を出力する。
【０１１３】
サイクル８０５では、分岐ターゲットバッファ６０１を検索し、ヒット信号１１９とウェイ情報１００１、エントリアドレス保持データ１２４とエントリアドレス１００２、下位アドレス出力６０６とオフセットアドレス１００３をそれぞれ比較し、全てが一致する分岐元情報を検索して、対応する分岐先アドレス１００４をサイクル８０６で出力する。
【０１１４】
図１０で示したように分岐ターゲットバッファ６０１にはアドレス「００１８」のキャッシュアクセス情報、「ウェイ０、エントリ１、下位アドレス８」に対応する分岐先アドレスとして「１０２０」が格納されているため、サイクル８０６では予測分岐先アドレスバス１３１にアドレス「１０２０」が出力され、分岐先アドレスのキャッシュアクセスが行われる。
【０１１５】
サイクル８０７では予測分岐先アドレス「１０２０」の命令データが読み出される。サイクル８０７では「ｉｎｓｔ４」命令は既にＥＸ０ステージを終えて、分岐方向が確定しているため、分岐予測が正解か不正解かの判定が可能である。
【０１１６】
分岐予測が正解の場合、読み出したアドレス「１０２０」の命令をデコーダ１３６に入力し、命令実行を続行する。不正解の場合には分岐不成立側の命令フェッチをやり直す。
【０１１７】
本実施形態では、アドレス「００１８」の分岐命令実行によるパイプラインバブルは図中８０８に示すように３サイクルとなる。
【０１１８】
以上の方法を用いれば、分岐ターゲットバッファ６０１内に分岐元情報としてアドレスの全てのフィールドを保持した場合と比較して、１サイクルのペナルティ増加のみとなる。一般的にプロセッサは実施形態で示すように全ての命令が１サイクルで動作することは少なく、何らかの実行ペナルティが入り、この１サイクルのペナルティ増加は全体の性能にあまり影響がない。一方、分岐元情報としては、ウェイ情報の２ビットと、エントリアドレス７ビット、下位アドレス４ビットの計１３ビットである。一般的な３２ビットのマイクロプロセッサの分岐ターゲットバッファのように、３２ビット全てのアドレスを保持する場合と比較し、分岐ターゲットバッファの回路構成を低減可能である。分岐ターゲットバッファとして多くのエントリを持つ場合に本発明を用いると、従来の方法に比べてパイプライン実行効率は同等の効果で分岐ターゲットバッファの面積削減が可能となる。
【０１１９】
なお、第２の実施形態と同様に、第２エントリアドレス比較器５０１とアクセス続行要求５０２とを装備し、分岐先アドレスによって先行する分岐先アドレスへのキャッシュアクセスをするか否かを判定し、その後の処理を行ってもよい。
【０１２０】
また、第４の実施形態でも、第３の実施形態と同様にタグ一時バッファ３０１、データ一時バッファ３０２を装備し、第３の実施形態でのこれらバッファ制御と同様の制御を行ってもよい。
【産業上の利用可能性】
【０１２１】
以上説明してきたとおり、本発明に係るキャッシュメモリ制御は、省面積で高効率の分岐命令実行が可能となるので、キャッシュメモリを搭載しかつ分岐予測を行うマイクロプロセッサ等として有用である。
【図面の簡単な説明】
【０１２２】
【図１】第１の実施形態のシステム構成図である。
【図２】第１の実施形態でのフローチャートである。
【図３】実行命令列を示す図である。
【図４】第１の実施形態でのタイミング図である。
【図５】第２の実施形態でのシステム構成図である。
【図６】第２の実施形態でのフローチャートである。
【図７】第３の実施形態でのシステム構成図である。
【図８】第３の実施形態でのフローチャートである。
【図９】第３の実施形態でのタイミング図である。
【図１０】第４の実施形態でのシステム構成図である。
【図１１】第４の実施形態での分岐ターゲットバッファである。
【図１２】第４の実施形態での分岐ターゲットバッファのセットのタイミング図である。
【図１３】第４の実施形態での全体タイミング図である。
【符号の説明】
【０１２３】
１０１  ＣＰＵ
１０２  キャッシュメモリ
１０３  キャッシュ制御部
１０４  分岐ターゲットバッファ
１０５  分岐ターゲットバッファ制御部
１０６  ＢＣＵ
１０７  命令バッファ
１０８  命令アドレス生成部
１０９  分岐命令ＰＣ
１２３  エントリアドレス比較器
１２４  エントリアドレス保持データ
１２５  エントリ一致信号
１２８  検索モード信号
３０１  タグ一時バッファ
３０２  データ一時バッファ
３０７  復帰判定器
３０８  復帰要求
３０９  ＣＰＵ復帰要求
５０１  第２エントリアドレス比較器
５０２  アクセス続行要求
６０１  分岐ターゲットバッファ
６０２  ヒットウェイバッファ
６０３  ヒットウェイ保持データ
６０４  分岐命令ＰＣバッファ
６０５  下位アドレスバッファ
６０６  下位アドレス出力
１０００  有効ビット
１００１  ウェイ番号
１００２  エントリアドレス
１００３  オフセットアドレス
１００４  分岐先アドレス
【図１】
2005122343.tif 000003
【図２】
2005122343.tif 000004
【図３】
2005122343.tif 000005
【図４】
2005122343.tif 000006
【図５】
2005122343.tif 000007
【図６】
2005122343.tif 000008
【図７】
2005122343.tif 000009
【図８】
2005122343.tif 000010
【図９】
2005122343.tif 000011
【図１０】
2005122343.tif 000012
【図１１】
2005122343.tif 000013
【図１２】
2005122343.tif 000014
【図１３】
2005122343.tif 000015