(57)【要約】【課題】プリフェッチ動作に関する処理効率を向上させる。【解決手段】ＣＰＵ２、命令キャッシュ部１０を備え、命令キャッシュ部は、命令キャッシュデータメモリ１１、プリフェッチバッファ１４、命令キャッシュ書き込み制御部１５、プリフェッチバッファ１４に格納された命令列をＣＰＵ２がフェッチ要求した場合はプリフェッチバッファ１４から命令キャッシュデータメモリ１１へその命令列を転送して格納させ、プリフェッチバッファ１４に格納された命令列をＣＰＵ２が実行する前に分岐が発生した場合、あるいは分岐先の命令列の次の命令列をプリフェッチバッファ１４に格納した場合は、分岐の種類に従ってプリフェッチバッファ１４から命令キャッシュデータメモリ１１へ命令列を転送し格納させるか否か判定し制御するヒット又はミス判定アクセス制御部１２を有する。【選択図】図４
2008186233.tif 000002
【特許請求の範囲】
【請求項１】
外部メモリに格納された命令列を与えられて実行する中央処理装置（以下、ＣＰＵという）と、
前記ＣＰＵが実行する前記命令列を前記外部メモリから読み出して格納し、前記ＣＰＵに与える命令キャッシュ部とを備え、
前記命令キャッシュ部は、
前記命令列を与えられて格納する命令キャッシュデータメモリと、
前記ＣＰＵからフェッチ要求があった前記命令列の次の命令列が前記命令キャッシュデータメモリに格納されていない場合に、プリフェッチして格納するプリフェッチバッファと、
前記外部メモリから出力された前記命令列と、前記プリフェッチバッファに格納された前記命令列のいずれか一方を選択して前記命令キャッシュデータメモリに出力する命令キャッシュ書き込み制御部と、
前記プリフェッチバッファに格納された前記命令列を前記ＣＰＵがフェッチ要求した場合は、前記プリフェッチバッファから前記命令キャッシュデータメモリへその命令列を転送して格納させ、前記プリフェッチバッファに格納された命令列を前記ＣＰＵが実行する前に分岐が発生した場合、前記分岐の種類に従って前記プリフェッチバッファから前記命令キャッシュデータメモリへ前記命令列を転送し格納させるか否か判定し制御するヒット又はミス判定アクセス制御部と、
を有することを特徴とする命令キャッシュプリフェッチ制御装置。
【請求項２】
外部メモリに格納された命令列を与えられて実行する中央処理装置（以下、ＣＰＵという）と、
前記ＣＰＵが実行する前記命令列を前記外部メモリから読み出して格納し、前記ＣＰＵに与える命令キャッシュ部とを備え、
前記命令キャッシュ部は、
与えられた命令列を格納する命令キャッシュデータメモリと、
前記ＣＰＵからフェッチ要求があった前記命令列の次の命令列が、前記命令キャッシュデータメモリに格納されていない場合にプリフェッチして格納するプリフェッチバッファと、
前記外部メモリから出力された前記命令列と、前記プリフェッチバッファに格納された前記命令列のいずれか一方を選択して前記命令キャッシュデータメモリに出力する命令キャッシュ書き込み制御部と、
前記ＣＰＵから第１の命令列のフェッチ要求があったとき、前記命令キャッシュデータメモリに前記第１の命令列が存在しないと判定した場合、前記外部メモリから前記第１の命令列を読み出して前記命令キャッシュデータメモリに格納させ、前記第１の命令列の次の第２の命令列が前記キャッシュデータメモリ及びプリフェッチバッファのいずれにも格納されていないと判定した場合、前記外部メモリから読み出して前記プリフェッチバッファに格納させ、前記プリフェッチバッファに格納されている第３の命令列を前記ＣＰＵが実行する前に分岐が発生した場合、前記分岐の種類に従って前記プリフェッチバッファから前記命令キャッシュデータメモリへ前記第３の命令列を転送し格納させるか否か判定し制御するヒット又はミス判定アクセス制御部と、
を有することを特徴とする命令キャッシュプリフェッチ制御装置。
【請求項３】
前記分岐が、
（１）所定条件が成立するとき、前方の命令列へ分岐し、不成立の場合には分岐することなく後続の命令列を実行する場合、
（２）ループを形成する後方分岐である場合、
（３）関数呼び出しによるサブルーチンコール、又は所定命令列へ分岐する場合、
（４）例外発生による分岐である場合、
（５）サブルーチンの読み出しを行う場合、あるいは例外発生により所定の命令列を処理し終了した後にリターンする場合、
（６）前記命令キャッシュデータメモリの領域に存在せず前記外部メモリに格納された命令列へ分岐する場合、
のいずれであるかに応じて、前記プリフェッチバッファから前記命令キャッシュデータメモリへ前記命令列を転送し格納させるか否かを判定し制御する請求項１又は２記載の命令キャッシュプリフェッチ制御装置。
【請求項４】
外部メモリに格納された命令列を与えられて実行する中央処理装置（以下、ＣＰＵという）と、前記ＣＰＵが実行する前記命令列を前記外部メモリから読み出して格納し、前記ＣＰＵに与える命令キャッシュ部とを備えた命令キャッシュプリフェッチ制御装置における制御方法であって、
前記命令キャッシュ部において、
前記ＣＰＵから第１の命令列のフェッチ要求があり、ヒット又はミス判定アクセス制御部が、命令キャッシュデータメモリに前記第１の命令列が存在しないと判定した場合、前記外部メモリから前記第１の命令列を読み出して前記命令キャッシュデータメモリに格納させ、
前記ヒット又はミス判定アクセス制御部は、前記第１の命令列の次の第２の命令列が前記キャッシュデータメモリ及びプリフェッチバッファのいずれにも格納されていないと判定した場合、前記外部メモリから読み出して前記プリフェッチバッファに格納させ、
前記プリフェッチバッファに格納されている第３の命令列を前記ＣＰＵが実行する前に分岐が発生した場合、前記ヒット又はミス判定アクセス制御部により、前記分岐の種類に従って前記プリフェッチバッファから前記命令キャッシュデータメモリへ前記第３の命令列を転送し格納させるか否か判定し制御することを特徴とする命令キャッシュプリフェッチ制御方法。
【請求項５】
前記分岐が、
（１）所定条件が成立するとき、前方の命令列へ分岐し、不成立の場合には分岐することなく後続の命令列を実行する場合、
（２）ループを形成する後方分岐である場合、
（３）関数呼び出しによるサブルーチンコール、又は所定命令列へ分岐する場合、
（４）例外発生による分岐である場合、
（５）サブルーチンの読み出しを行う場合、あるいは例外発生により所定の命令列を処理し終了した後にリターンする場合、
（６）前記命令キャッシュデータメモリの領域に存在せず前記外部メモリに格納された命令列へ分岐する場合、
のいずれであるかに応じて、前記プリフェッチバッファから前記命令キャッシュデータメモリへ前記命令列を転送し格納させるか否か判定し制御することを特徴とする請求項４記載の命令キャッシュプリフェッチ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、命令キャッシュプリフェッチ制御方法及びその装置に関する。
【背景技術】
【０００２】
命令キャッシュデータメモリを利用してプログラムを実行する装置において、実行している命令列に連続する次の命令列が命令キャッシュデータメモリ内に存在しない時、専用のプリフェッチバッファにこの命令列をプリフェッチしておき、プリフェッチバッファから命令キャッシュデータメモリに転送するというプリフェッチ機構が存在する。この機構は、後述する非特許文献１に記載されている。
【０００３】
ここで、プリフェッチバッファにプリフェッチした命令列を命令キャッシュデータメモリ内に書き込む制御には、大きく分けて２つの手法が考えられる。
【０００４】
（Ａ）プリフェッチした命令列が実行されることが確定してから、命令キャッシュデータメモリに転送する。別の命令列をプリフェッチする必要が生じた場合には、その命令列を上書きしてプリフェッチを行う。この手法は、後述する特許文献１に開示された通りである。
【０００５】
（Ｂ）プリフェッチした命令列を、中央処理装置（以下、ＣＰＵという）が実行するか否かにかかわらず常に命令キャッシュデータメモリに転送して格納する。
【０００６】
上記手法（Ａ）の場合、プリフェッチした命令列が使われる前に破棄された場合、再度同じ命令列をプリフェッチする必要が生じる可能性がある。これが繰り返されると、無駄なプリフェッチによって外部バスのトラフィックが増大し、効率の低下を招くという問題があった。
【０００７】
その一方で、上記手法（Ｂ）の場合、実際には必要のない命令列を命令キャッシュデータメモリに格納する可能性がある。そのような場合に、不要な命令列によって、既に命令キャッシュデータメモリに格納されている必要な他の命令列が追い出されて、結果的に効率が低下する場合があった。
【非特許文献１】Wei-Chung-Hsu "A Performance Study of Instruction Cache Prefetching Methods" IEEE Transaction on COMPUTERS Vol.47, No.5, pp497-508 内のfall-through prefetch方式
【特許文献１】特開２００３−１６２４４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は上記事情に鑑み、不要な命令列をプリフェッチしたり、必要な命令列を繰り返しプリフェッチする等処理効率の低下を防止することが可能な命令キャッシュプリフェッチ制御方法及びその装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一態様による命令キャッシュプリフェッチ制御装置は、外部メモリに格納された命令列を与えられて実行するＣＰＵと、前記ＣＰＵが実行する前記命令列を前記外部メモリから読み出して格納し、前記ＣＰＵに与える命令キャッシュ部とを備え、前記命令キャッシュ部は、前記命令列を与えられて格納する命令キャッシュデータメモリと、前記ＣＰＵからフェッチ要求があった前記命令列の次の命令列が前記命令キャッシュデータメモリに格納されていない場合に、プリフェッチして格納するプリフェッチバッファと、前記外部メモリから出力された前記命令列と、前記プリフェッチバッファに格納された前記命令列のいずれか一方を選択して前記命令キャッシュデータメモリに出力する命令キャッシュ書き込み制御部と、前記プリフェッチバッファに格納された前記命令列を前記ＣＰＵがフェッチ要求した場合は、前記プリフェッチバッファから前記命令キャッシュデータメモリへその命令列を転送して格納させ、前記プリフェッチバッファに格納された命令列を前記ＣＰＵが実行する前に分岐が発生した場合、前記分岐の種類に従って前記プリフェッチバッファから前記命令キャッシュデータメモリへ前記命令列を転送し格納させるか否か判定し制御するヒット又はミス判定アクセス制御部とを有することを特徴とする。
【００１０】
本発明の一態様による命令キャッシュプリフェッチ制御装置は、外部メモリに格納された命令列を与えられて実行するＣＰＵと、前記ＣＰＵが実行する前記命令列を前記外部メモリから読み出して格納し、前記ＣＰＵに与える命令キャッシュ部とを備え、前記命令キャッシュ部は、与えられた命令列を格納する命令キャッシュデータメモリと、前記ＣＰＵからフェッチ要求があった前記命令列の次の命令列が、前記命令キャッシュデータメモリに格納されていない場合にプリフェッチして格納するプリフェッチバッファと、前記外部メモリから出力された前記命令列と、前記プリフェッチバッファに格納された前記命令列のいずれか一方を選択して前記命令キャッシュデータメモリに出力する命令キャッシュ書き込み制御部と、前記ＣＰＵから第１の命令列のフェッチ要求があったとき、前記命令キャッシュデータメモリに前記第１の命令列が存在しないと判定した場合、前記外部メモリから前記第１の命令列を読み出して前記命令キャッシュデータメモリに格納させ、前記第１の命令列の次の第２の命令列が前記キャッシュデータメモリ及びプリフェッチバッファのいずれにも格納されていないと判定した場合、前記外部メモリから読み出して前記プリフェッチバッファに格納させ、前記プリフェッチバッファに格納されている第３の命令列を前記ＣＰＵが実行する前に分岐が発生した場合、前記分岐の種類に従って前記プリフェッチバッファから前記命令キャッシュデータメモリへ前記第３の命令列を転送し格納させるか否か判定し制御するヒット又はミス判定アクセス制御部とを有することを特徴とする。
【００１１】
本発明の一態様による命令キャッシュプリフェッチ制御方法は、外部メモリに格納された命令列を与えられて実行するＣＰＵと、前記ＣＰＵが実行する前記命令列を前記外部メモリから読み出して格納し、前記ＣＰＵに与える命令キャッシュ部とを備えた命令キャッシュプリフェッチ制御装置における制御方法であって、前記命令キャッシュ部において、前記ＣＰＵから第１の命令列のフェッチ要求があり、ヒット又はミス判定アクセス制御部が、命令キャッシュデータメモリに前記第１の命令列が存在しないと判定した場合、前記外部メモリから前記第１の命令列を読み出して前記命令キャッシュデータメモリに格納させ、前記ヒット又はミス判定アクセス制御部は、前記第１の命令列の次の第２の命令列が前記キャッシュデータメモリ及びプリフェッチバッファのいずれにも格納されていないと判定した場合、前記外部メモリから読み出して前記プリフェッチバッファに格納させ、前記プリフェッチバッファに格納されている第３の命令列を前記ＣＰＵが実行する前に分岐が発生した場合、前記ヒット又はミス判定アクセス制御部により、前記分岐の種類に従って前記プリフェッチバッファから前記命令キャッシュデータメモリへ前記第３の命令列を転送し格納させるか否か判定し制御することを特徴とする。
【発明の効果】
【００１２】
本発明の命令キャッシュプリフェッチ制御方法及びその装置によれば、不要な命令列をプリフェッチする等の無駄をなくし、処理効率を向上させることが可能である。
【発明を実施するための最良の形態】
【００１３】
参考例１
先ず、参考例１として、上記手法（Ａ）に基づいてプリフェッチ制御を行う命令キャッシュプリフェッチ制御装置の構成について、図１を用いて説明する。
【００１４】
この装置は、命令列を格納する外部メモリ１、命令列を実行するＣＰＵ２、命令列のキャッシュを行う命令キャッシュ部１０を備える。命令キャッシュ部１０は、命令キャッシュデータメモリ１１、ヒット又はミス判定アクセス制御部１２、命令キャッシュタグメモリ１３、プリフェッチバッファ１４、命令キャッシュ書き込み制御部１５を有する。
【００１５】
プリフェッチバッファ１４は、外部メモリ１から与えられた命令列のプリフェッチを行う。尚、このプリフェッチバッファ１４は、一単位の命令列を格納する容量を有する。
【００１６】
命令キャッシュ書き込み制御部１５は、ヒット又はミス判定アクセス制御部１２から選択信号を与えられ、プリフェッチバッファ１４又は外部メモリ１のいずれか一方から出力された命令列を選択して出力する。
【００１７】
命令キャッシュデータメモリ１１は、命令キャッシュ書き込み制御部１５から出力された命令列を与えられて格納する。格納された命令列は、ＣＰＵ２に与えられて実行される。
【００１８】
命令キャッシュタグメモリ１３は、ＣＰＵ２からフェッチ要求が出されたアドレスに対応する命令列が命令キャッシュデータメモリ１１に存在するか否かを示すタグ内容を格納する。
【００１９】
ヒット又はミス判定アクセス制御部１２は、ＣＰＵ２からフェッチ要求のあった命令列が命令キャッシュデータメモリ１１に存在するか否か、即ちヒット又はミスの判定を行う。具体的には、フェッチ要求のあったアドレスと、読み出し信号とを命令キャッシュタグメモリ１３に与え、タグ内容信号を読み出す。タグ内容に命令キャッシュデータメモリ１１に対応する命令列が格納されていることが示されているとき（ヒットしたとき）は、このときのアドレスと読み出し信号とを命令キャッシュデータメモリ１１に与えて読み出し、ＣＰＵ２に与える。また、プリフェッチバッファ１４からはアドレス信号が与えられ、プリフェッチされた命令列のアドレスがヒット又はミス判定アクセス制御部１２に与えられる。
【００２０】
以下に、参考例１における処理の手順について説明する。
【００２１】
１）ＣＰＵ２から、ヒット又はミス判定アクセス制御部１２に、１番目の命令列のフェッチ要求とそのアドレスとが送られる。
【００２２】
２）ヒット又はミス判定アクセス制御部１２が、命令キャッシュタグメモリ１３にアドレスと読み出し信号とを転送する。命令キャッシュタグメモリ１３は、アドレスに対応するタグ内容を読み出して、ヒット又はミス判定アクセス制御部１２に出力する。
【００２３】
３）ヒット又はミス判定アクセス制御部１２は、タグ内容に基づいて、ＣＰＵ２がフェッチを要求した命令列が命令キャッシュメモリ１１に存在するか否か、即ちヒットしたかあるいはミスしたかを判定する。
【００２４】
ヒットした場合は、ヒット又はミス判定アクセス制御部１２からアドレス及び読み出し信号が命令キャッシュデータメモリ１１に転送され、アドレスに対応する１番目の命令列が読み出されてＣＰＵ２に出力される。ミスした場合、１番目の命令列は存在しない場合が通常であるが、その場合はヒット又はミス判定アクセス制御部１２は、プリフェッチバッファ１４から出力されているアドレスを参照し、１番目の命令列がプリフェッチ済みで存在するか否か判断する。
【００２５】
４）存在する場合は、プリフェッチバッファ１４から出力された１番目の命令列が命令キャッシュ書き込み制御回路１５に与えられ、ヒット又はミス判定アクセス制御部１２から出力された選択信号により選択されて命令キャッシュデータメモリ１１に与えられる。ヒット又はミス判定アクセス制御部１２からアドレスと書き込み信号とが命令キャッシュデータメモリ１１に与えられ、書き込まれる。
【００２６】
１番目の命令列がプリフェッチされていない場合、通常は１番目の命令列はプリフェッチされていないが、ヒット又はミス判定アクセス制御部１２が外部メモリ１に読み出し要求信号を出力する。読み出された１番目の命令列が命令キャッシュ書き込み制御回路１５を経て、命令キャッシュデータメモリ１１に与えられる。ヒット又はミス判定アクセス制御部１２からアドレスと書き込み信号とが命令キャッシュデータメモリ１１に与えられて書き込まれた後、ＣＰＵ２にこの命令列が読み出される。
【００２７】
５）ヒット又はミス判定アクセス制御部１２は、命令キャッシュデータメモリ１１に命令列が書き込まれる毎に、命令キャッシュタグメモリ１３にアドレスと書き込み信号とを与え、タグ内容を更新させる。
【００２８】
６）また、ヒット又はミス判定アクセス制御部１２は、ＣＰＵ２から１番目の命令列のフェッチ要求があった際に、次の２番目の命令列のプリフェッチ動作を開始する。プリフェッチバッファ１４から出力されているアドレスを参照し、プリフェッチ済みか否かを判断し、プリフェッチされていない場合、外部メモリ１に読み出し要求信号を出力する。
【００２９】
７）外部メモリ１から読み出された２番目の命令列がプリフェッチバッファ１４に与えられ、またヒット又はミス判定アクセス制御部１２から書き込み信号が出力されて、書き込まれる。
【００３０】
命令列が順にＣＰＵ２において実行されている間は、上記手順で処理が行われる。次に、分岐が発生した場合について説明する。
【００３１】
８）例えば、１番目の命令列がＣＰＵ２により実行され、次の２番目の命令列がプリフェッチされてプリフェッチバッファ１４に格納され、命令キャッシュデータメモリ１１には格納されていない状態で、ＣＰＵ２から１０番目の命令列のフェッチ要求があったと仮定する。このような場合、参考例１では２番目の命令列は実行されないので、命令キャッシュデータメモリ１１に書き込まない。先ず、ＣＰＵ２から１０番目の命令列のフェッチ要求及びアドレスがヒット又はミス判定アクセス制御部１２に出力される。
【００３２】
９）ヒット又はミス判定アクセス制御部１２は、命令キャッシュタグメモリ１３から読み出したタグ内容に基づいて、ヒット又はミスの判定を行う。ヒットしていた場合は、上述したように命令キャッシュデータメモリ１１から読み出してＣＰＵ２に与える。ミスの場合は、外部メモリ１から命令列を読み出して命令キャッシュデータメモリ１１に書き込んだ後、読み出してＣＰＵ２に与える。
【００３３】
１０）さらにヒット又はミス判定アクセス制御部１２は、次の１１番目の命令列のプリフェッチ動作を開始する。プリフェッチバッファ１４には２番目の命令列が格納されており、１１番目の命令列は格納されていない。そこで、外部メモリ１からこの命令列を読み出して、プリフェッチバッファ１４に書き込む。このとき、プリフェッチバッファ１４に書かれていた２番目の命令列は命令キャッシュデータメモリ１１に転送されることなく上書きされて破壊される。
【００３４】
１１）このプリフェッチされた１１番目の命令列が実行される場合には命令キャッシュデータメモリ１１に転送されて書き込まれる。実行されない場合は、ＣＰＵ２からフェッチ要求のあった命令列の次の命令列がプリフェッチバッファ１４に上書きされる。
【００３５】
ここで、プリフェッチバッファ１４にプリフェッチされた命令列を命令キャッシュデータメモリ１１に書き込む際の処理について、図２のフローチャートを用いて説明する。
【００３６】
先ず、ステップＳ１０として示されたように、プリフェッチバッファ１４は空の状態、あるいは破壊されてよい命令列が格納された状態にある。
【００３７】
ステップＳ１２として、ＣＰＵ２からフェッチ要求のあった例えば１番目の命令列の次の２番目の命令列をプリフェッチするよう、ヒット又はミス判定アクセス制御部１２が外部メモリ１に読み出し要求信号を出力する。読み出された２番目の命令列がプリフェッチバッファ１４に与えられ、ヒット又はミス判定アクセス制御部１２から書き込み信号がプリフェッチバッファ１４に与えられて書き込まれる。
【００３８】
ステップＳ１４において、ヒット又はミス判定アクセス制御部１２が、プリフェッチした２番目の命令列を実行するか否か判断する。ＣＰＵ２から、２番目の命令列をフェッチする要求があった時点で、ステップＳ１６において命令キャッシュデータメモリ１１にこの命令列を与えて格納させる。
【００３９】
２番目の命令列を実行することなく、分岐先の例えば１０番目の命令列をフェッチするようＣＰＵ２から要求があった場合は、２番目の命令列は命令キャッシュデータメモリ１１に与えない。ヒット又はミス判定アクセス制御部１２は、次の１１番目の命令列を外部メモリ１から読み出してプリフェッチバッファ１４に与えて格納させる。
【００４０】
このように参考例１では、プリフェッチされた命令列が実行されることが確定された場合に限り、命令キャッシュデータメモリ１１に格納される。実行されない場合には、ＣＰＵ２から要求のあった分岐先の命令列をフェッチするとともに、その次の命令列をプリフェッチしてプリフェッチバッファ１４に上書きする。これにより、プリフェッチ済みであるが実行されなかった命令列は破壊される。
【００４１】
参考例２
参考例２として、上記手法（Ｂ）に基づいてプリフェッチ制御を行う命令キャッシュプリフェッチ制御装置について説明する。
【００４２】
回路構成上は、図１に示された上記参考例１によるものと同一であり、ヒット又はミス判定アクセス制御部１２におけるプリフェッチに関する制御動作が異なる。以下に、参考例２における処理の手順を図３のフローチャートを用いて説明する。
【００４３】
ステップＳ２０として示されたように、プリフェッチバッファ１４は空の状態、あるいは破壊されてよい命令列が格納された状態にある。
【００４４】
ステップＳ２２として、ＣＰＵ２からフェッチ要求のあった例えば１番目の命令列の次の２番目の命令列をプリフェッチするよう、ヒット又はミス判定アクセス制御部１２が外部メモリ１に読み出し要求信号を出力する。読み出された２番目の命令列がプリフェッチバッファ１４に与えられ、ヒット又はミス判定アクセス制御部１２から書き込み信号がプリフェッチバッファ１４に与えられて書き込まれる。
【００４５】
ステップＳ２４において、ヒット又はミス判定アクセス制御部１２が、プリフェッチした２番目の命令列の実行の有無にかかわらず、命令キャッシュデータメモリ１１にこの命令列を与えて格納させる。
【００４６】
従って、プリフェッチバッファ１４に既に格納された２番目の命令列をＣＰＵ２が実行せずに、１０番目の命令列を実行する場合であっても、２番目の命令列は命令キャッシュデータメモリ１１に転送されて格納される。
【００４７】
命令キャッシュデータメモリ１１に格納された２番目の命令列は、次の命令列をプリフェッチする際に破壊されてもよい状態にあり、ステップＳ２０へ戻る。
【００４８】
このように参考例２では、プリフェッチされた命令列が実行されるか否かにかかわらず、必ずプリフェッチバッファ１４から命令キャッシュデータメモリ１１に転送されて格納される。プリフェッチバッファ１４への命令列の格納は、その後行われる。
【００４９】
実施の形態
本発明の実施の形態による命令キャッシュプリフェッチ制御方法及びその装置について説明する。
【００５０】
命令列に分岐が存在せず、常に連続する命令列が順次実行されている間は、プリフェッチされた命令列は順に実行される。
【００５１】
上記参考例１において手法（Ａ）に基づいて処理を行う場合に、プリフェッチされた命令列が実行されない場合に破棄されて命令キャッシュデータメモリに格納されず、その後その命令列が実行されるとき再度プリフェッチしなければならない現象、あるいは上記参考例２において手法（Ｂ）に基づいて処理を行う場合に、実行されることのない不要な命令列まで命令キャッシュデータメモリに格納される現象のいずれも、連続する命令列の実行中に分岐が発生することに起因する。
【００５２】
これに対し、図４に示された上記実施の形態は、ある命令列を実行している最中に分岐が発生した場合、この命令列に後続する命令列を既にプリフェッチバッファ３４にプリフェッチしていたとき、この命令列を命令キャッシュデータメモリ３１に格納するか否かを、分岐の種類に応じて判断する点に特徴がある。
【００５３】
ここで、分岐には以下のような種類が存在する。
【００５４】
（１）例えばＣ言語における"if(...)else(...)"のように、ある条件が成立する際に後続の命令列を飛ばして前方の命令列へ分岐し、不成立の場合には分岐することなく後続の命令列を実行する場合。但し、該条件が成立し前方の命令列へ分岐した後、分岐元の後続の命令列を実行されるか否かは不確定であり、通常は実行しない。
【００５５】
（２）Ｃ言語における"for(..){...}"や、"while(...){...}"のように、ループを形成する後方分岐である場合。ここで、ループの回数が指定される場合と指定されない場合とが存在する。ループ終了後は、ループ処理に含まれる命令列に後続する命令列を実行する確率が高い。
【００５６】
（３）関数呼び出しによるサブルーチンコールによって、特定の命令列へ分岐する場合。分岐した後は、分岐先の命令列を実行した後、リターンして分岐元へ戻ってくることが多く、分岐が生じた命令列の後続の命令列を実行する確率が高い。
【００５７】
（４）例外発生による"Jump"のように、プロセッサ外部から突発的に入力された信号により、割り込み処理が生じて一旦その信号に基づく処理をしなければならない場合。この場合は、割り込みが終了した後は、後続の命令列を実行する確率が高い。
【００５８】
（５）サブルーチンのような特定のプログラム、あるいは例外ベクタのような例外発生によって特定のプログラム列を処理し、終了した後にリターンする場合。この場合、サブルーチンや例外ベクタからリターンする命令に後続する命令列を実行するか否かは不確定である。
【００５９】
（６）命令キャッシュデータメモリ３１の領域外の外部メモリ１へ"Jump"する場合。この場合は、外部メモリ１における分岐先の命令列に後続する命令列を実行するか否か不確定であり、通常は実行しない。また、命令キャッシュデータメモリ３１において分岐が発生した命令列に後続する命令列に戻って実行するか否か不確定である。
【００６０】
上述したように、分岐が発生した命令列に後続する命令列、あるいは分岐先の命令列に後続する命令列が実行されるか否かは分岐の種類によりある程度予測がつく。上記（１）〜（６）のうち、分岐が発生した命令列に後続する命令列、あるいは分岐先の命令列に後続する命令列を実行する確率が低いのは、（１）、（５）、（６）であり、実行される確率が高いのは（２）〜（４）である。
【００６１】
本実施の形態ではその予測可能性を利用し、分岐の種類によって、分岐が生じた命令列に後続する命令列、あるいは分岐先の命令列に後続する命令列をプリフェッチした場合に、命令キャッシュデータメモリ３１へこの命令列の書き込みの有無を判断し制御する。
【００６２】
具体的には、（２）〜（４）の分岐が生じた場合はプリフェッチバッファ３４にプリフェッチした命令列を命令キャッシュデータメモリ３１に転送して書き込み、（１）、（５）、（６）の分岐が生じた場合は、命令キャッシュデータメモリ３１に転送せず書き込みを行わない。
【００６３】
命令キャッシュデータメモリ３１にプリフェッチした命令列を転送しない場合、実行すべき新たな命令列をプリフェッチすべき状況になった時点で、このプリフェッチバッファ３４内の実行されない命令列は破棄し、新たにプリフェッチした命令列によって上書きする。
【００６４】
図４に、上述した制御を行う本実施の形態による命令キャッシュプリフェッチ制御装置の構成を示す。
【００６５】
この装置は、命令列を格納する外部メモリ１、命令列を実行するＣＰＵ２、命令列のキャッシュを行う命令キャッシュ部３０を備える。命令キャッシュ部３０は、命令キャッシュデータメモリ３１、ヒット又はミス判定アクセス制御部３２、命令キャッシュタグメモリ３３、プリフェッチバッファ３４、命令キャッシュ書き込み制御部３５を有する。
【００６６】
ここで、ヒット又はミス判定アクセス制御部３２は、上記実施の形態１におけるヒット又はミス判定アクセス制御部１２と異なり、ＣＰＵ２からフェッチ要求、アドレスに加えて、さらに分岐情報を与えられる。この分岐情報に基づいて、プリフェッチバッファ３４に格納された命令列を命令キャッシュデータメモリ３１に格納するか否かを判断する。
【００６７】
次に、本実施の形態による命令キャッシュプリフェッチ制御装置における動作について説明する。
【００６８】
命令列が順にＣＰＵ２において実行されている間は、上記参考例１において述べた１）〜８）における処理と同様な処理が行われる。次に、分岐が発生した場合について説明する。
【００６９】
９）例えば、１番目の命令列がＣＰＵ２により実行され、次の２番目の命令列がプリフェッチされてプリフェッチバッファ３４に格納され、命令キャッシュデータメモリ３１には格納されていない状態で、ＣＰＵ２から１０番目の命令列のフェッチ要求及びアドレスがヒット又はミス判定アクセス制御部１２に出力されたと仮定する。
【００７０】
１０）ヒット又はミス判定アクセス制御部１２は、命令キャッシュタグメモリ１３から読み出したタグ内容に基づいて、ヒット又はミスの判定を行う。ヒットしていた場合は、上述したように命令キャッシュデータメモリ１１から読み出してＣＰＵ２に与える。ミスの場合は、外部メモリ１から命令列を読み出して命令キャッシュデータメモリ１１に書き込んだ後、読み出してＣＰＵ２に与える。
【００７１】
１１）さらにヒット又はミス判定アクセス制御部１２は、次の１１番目の命令列のプリフェッチ動作を開始する。プリフェッチバッファ１４には２番目の命令列が格納されており、１１番目の命令列は格納されていない。そこで、外部メモリ１からこの命令列を読み出して、プリフェッチバッファ１４に書き込む。
【００７２】
このような場合、参考例１では２番目の命令列は実行されないので、命令キャッシュデータメモリ１１に書き込まない。また、参考例２では２番目の命令列は実行されないが、常に命令キャッシュデータメモリ１１に転送されて書き込まれる。
【００７３】
一方、本実施の形態では、ＣＰＵ２から出力された分岐情報に基づいて、ヒット又はミス判定アクセス制御部３２が２番目の命令列を命令キャッシュデータメモリ３１に格納するか否か、判断する。
【００７４】
上記（１）〜（６）のうち、分岐が発生した命令列に後続する命令列、あるいは分岐先の命令列に後続する命令列を実行する確率が低いのは、上述したように（１）、（５）、（６）であり、実行される確率が高いのは（２）〜（４）である。そこで分岐情報に基づき、分岐の種類が、（１）、（５）、（６）であるとヒット又はミス判定アクセス制御部１２が判断した場合は、プリフェッチバッファ１４に格納されている２番目の命令列を命令キャッシュデータメモリ３１に転送して格納させる。この後、１１番目の命令列が外部メモリ１から読み出されてプリフェッチバッファ１４に与えられ、格納される。
【００７５】
逆に、分岐の種類が、（１）、（５）、（６）であるとヒット又はミス判定アクセス制御部１２が判断した場合は、プリフェッチバッファ１４に格納されている２番目の命令列を命令キャッシュデータメモリ３１に転送することなく、１１番目の命令列が外部メモリ１からプリフェッチバッファ１４に与えられて上書きされる。これにより、２番目の命令列は破壊される。
【００７６】
ここで、プリフェッチバッファ３４にプリフェッチされた命令列を命令キャッシュデータメモリ３１に書き込む際の処理を、図５のフローチャートに示す。
【００７７】
ステップＳ３０として示されたように、プリフェッチバッファ３４は空の状態、あるいは破壊されてよい命令列が格納された状態にある。
【００７８】
ステップＳ３２として、ＣＰＵ２からフェッチ要求のあった例えば１番目の命令列の次の２番目の命令列をプリフェッチするよう、ヒット又はミス判定アクセス制御部３２が外部メモリ１に読み出し要求信号を出力する。読み出された２番目の命令列がプリフェッチバッファ３４に与えられ、ヒット又はミス判定アクセス制御部３２から書き込み信号がプリフェッチバッファ３４に与えられて書き込まれる。
【００７９】
ステップＳ３４において、分岐が発生したか否か、即ちＣＰＵ２からのフェッチ要求のあったアドレスが連続しているかどうかを、ヒット又はミス判定アクセス制御部３２において判断する。分岐が発生しない間は、ステップＳ３８へ移行し、順次プリフェッチした命令列を命令キャッシュデータメモリ３１に転送して格納する。
【００８０】
分岐が発生した場合はステップＳ３６へ移行し、ヒット又はミス判定アクセス制御部３２が分岐情報に基づいて分岐の種類を判定する。分岐の種類が、上記（１）、（５）、（６）である場合は、プリフェッチ済みの命令列を実行する可能性は低いので、ステップＳ３０へ戻る。これにより、分岐した命令列の次の命令列がプリフェッチバッファ３４に上書きされる。分岐の種類が、上記（２）〜（４）である場合は、プリフェッチ済みの命令列を実行する可能性が高いので、ステップＳ３８へ移行し、命令キャッシュデータメモリ３１に書き込む。
【００８１】
以上説明したように、本実施の形態によれば、ある命令列を実行中に分岐が生じ、その命令列に後続する命令列をプリフェッチしている場合、命令キャッシュデータメモリに格納すべきかどうかの判断を、分岐の種類に基づいてその命令列の実行する可能性を予測して行うことにより、実行しない無駄な命令列により命令キャッシュデータメモリ３１内の領域が占有されたり、実行される命令列が一旦破棄され再度プリフェッチする無駄を抑制し、処理効率を向上させることができる。
【００８２】
上述した実施の形態は一例であり、本発明を限定するものではなく、本発明の技術的範囲内において様々に変形することが可能である。
【図面の簡単な説明】
【００８３】
【図１】参考例１による命令キャッシュプリフェッチ制御装置の構成を示すブロック図。
【図２】同参考例１における処理の手順を示したフローチャート。
【図３】参考例２による命令キャッシュプリフェッチ制御装置における処理の手順を示したフローチャート。
【図４】本発明の実施の形態による命令キャッシュプリフェッチ制御装置の構成を示すブロック図。
【図５】同実施の形態における処理の手順を示したフローチャート。
【符号の説明】
【００８４】
１  外部メモリ
２  ＣＰＵ
３０  命令キャッシュ部
３１  命令キャッシュデータメモリ
３２  ヒット又はミス判定アクセス制御部
３３  命令キャッシュタグメモリ
３４  プリフェッチバッファ
３５  命令キャッシュ書き込み制御部
【図１】
2008186233.tif 000003
【図２】
2008186233.tif 000004
【図３】
2008186233.tif 000005
【図４】
2008186233.tif 000006
【図５】
2008186233.tif 000007