(57)【要約】【課題】プリフェッチ命令を多用するとキャッシュの効率が悪化する。【解決手段】プロトコルスロット生成部５０は、ＣＰＵ１２からプリフェッチデータの利用予定時刻が指定されたプリフェッチ命令を受け取った場合は、利用予定時刻にもとづいてプロトコルスロットを生成して、スケジュールリスト記憶部５６に登録し、通常のアクセス命令を受け取った場合は、プロトコルスロットを通常プロトコルキュー記憶部５８に登録する。コスト評価部５２は、プリフェッチ命令の発行コストをプリフェッチデータのキャッシュ滞留時間にもとづいて評価し、通常のアクセス命令の発行コストをリソースの占有コストにより評価する。プロトコル発行部５４は、これらの発行コストの評価結果にもとづき、プリフェッチ命令を発行するか、通常のアクセス命令を発行するかを決定する。【選択図】        図５
2004348175.tif 000002
【特許請求の範囲】
【請求項１】
データのプリフェッチ命令に、そのデータの利用時刻に関する情報を付加し、前記利用時刻に関する情報をもとに前記プリフェッチ命令の発行タイミングをスケジュールすることを特徴とするプリフェッチ命令制御方法。
【請求項２】
前記プリフェッチ命令を発行した場合にプリフェッチされたデータがキャッシュに滞留する時間をもとに、前記プリフェッチ命令の発行コストを計算し、前記発行コストにもとづいて前記プリフェッチ命令の前記発行タイミングをスケジュールすることを特徴とする請求項１に記載のプリフェッチ命令制御方法。
【請求項３】
データの通常のアクセス命令を発行した場合にアクセスされたリソースが占有される時間をもとに、前記通常のアクセス命令の発行コストを計算し、前記プリフェッチ命令の発行コストと前記通常のアクセス命令の発行コストを比較して、前記プリフェッチ命令と前記通常のアクセス命令のいずれを発行するかを決定することを特徴とする請求項２に記載のプリフェッチ命令制御方法。
【請求項４】
データの利用時刻に関する情報が付加された、外部リソースに対するプリフェッチ命令を記憶する記憶部と、
記憶された前記プリフェッチ命令を発行した場合に、前記利用時刻に到達するまでプリフェッチされたデータがキャッシュに滞留することによるコストを評価するコスト評価部と、
前記コスト評価部による評価結果にもとづいて、記憶された前記プリフェッチ命令を前記外部リソースに対して発行するタイミングを調整する発行部とを含むことを特徴とするプリフェッチ命令制御装置。
【請求項５】
前記コスト評価部は、前記プリフェッチ命令の発行コストと、前記外部リソースのアクセスリクエストのキューに格納された通常のアクセス命令の発行コストを比較し、前記発行部は、前記コスト評価部による比較結果にもとづいて、現時刻で前記プリフェッチ命令と前記通常のアクセス命令のいずれを発行するかを決定することを特徴とする請求項４に記載のプリフェッチ命令制御装置。
【請求項６】
前記コスト評価部は、前記プリフェッチ命令の発行により前記外部リソースのアクセスリクエストのキューに格納された前記通常のアクセス命令の発行が遅延することによるコストを、前記プリフェッチ命令の発行コストの評価に含めることを特徴とする請求項４または５に記載のプリフェッチ命令制御装置。
【請求項７】
前記コスト評価部は、現時刻から前記利用時刻までの時間間隔をもとにしたプリフェッチの時間制限によるリスクを、前記プリフェッチ命令の発行コストの評価に含めることを特徴とする請求項４から６のいずれかに記載のプリフェッチ命令制御装置。
【請求項８】
外部リソースから取得したデータをキャッシュしてプロセッサに供給するキャッシュメモリと、
前記プロセッサから前記外部リソースに対するアクセスプロトコルを受け取り、アクセスプロトコルをスケジュールして前記外部リソースのリクエストキューに設定するスケジューラと、
前記リクエストキューから前記アクセスプロトコルを読み出し、前記外部リソースにアクセスして前記キャッシュメモリにデータを供給する外部リソースコントローラとを含み、
前記スケジューラは、
前記プロセッサから送られた、データの利用時刻に関する情報が付加されたプリフェッチ命令を記憶する記憶部と、
記憶された前記プリフェッチ命令を発行した場合に、前記利用時刻に到達するまでプリフェッチされたデータが前記キャッシュメモリに滞留することによるコストを評価するコスト評価部と、
前記コスト評価部による評価結果にもとづいて、記憶された前記プリフェッチ命令を前記外部リソースに対して発行するタイミングを調整して、前記リクエストキューに設定する発行部とを含むことを特徴とするキャッシュメモリ制御装置。
【請求項９】
前記スケジューラは、前記プリフェッチ命令の発行後に、前記利用時刻に関する情報にもとづき、前記キャッシュメモリにおけるプリフェッチデータのキャッシュをロックすることを特徴とする請求項８に記載のキャッシュメモリ制御装置。
【請求項１０】
ソースコードを解析して中間コードに変換するステップと、
前記中間コードにもとづいて、キャッシュメモリへプリフェッチすべきデータを決定し、そのデータに対するアクセス命令を元の実行順序位置よりも前の位置にプリフェッチ命令として挿入し、そのプリフェッチ命令にデータの利用時刻に関する情報を付加するステップと、
前記プリフェッチ命令を含む前記中間コードを最適化してオブジェクトコードを生成するステップとをコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項１１】
前記利用時刻に関する情報は、プリフェッチ命令の挿入位置に対する相対的な位置で示される、プリフェッチデータの利用開始時点に関する情報を含むことを特徴とする請求項１０に記載のコンピュータプログラム。
【請求項１２】
前記利用時刻に関する情報は、プリフェッチ命令の挿入位置に対する相対的な位置で示される、プリフェッチデータの利用終了時点に関する情報をさらに含むことを特徴とする請求項１１に記載のコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明はキャッシュ制御技術、とくにプリフェッチ命令を制御する方法と装置、ならびにキャッシュメモリ制御装置に関する。
【０００２】
【従来の技術】
コンピュータのプロセッサによるＩ／ＯやＤＲＡＭなどの主記憶の参照には局所性がある。この局所性を利用して、頻繁に参照される主記憶のデータを高速で小容量の内部メモリであるキャッシュメモリにコピーし、主記憶へのアクセスをこのキャッシュメモリに対して行うことによって、メモリアクセスにかかるレーテンシーを短縮することができる。プロセッサの処理性能の向上が進められる中、プロセッサに高速にデータを供給する上でキャッシュメモリの重要性は高まっている。
【０００３】
キャッシュがヒットした場合、プロセッサはキャッシュメモリのアクセス速度で必要なデータを得ることができるが、キャッシュミスの場合、プロセッサは主記憶からキャッシュメモリにデータが転送される間、プログラムの実行を停止しなければならない。キャッシュミスは、キャッシュの容量が十分でないため、キャッシュしたデータが追い出されることや、アクセスしたいデータが初期参照であるため、キャッシュメモリ内に主記憶のデータのコピーが存在していないために起こる。前者の問題は、キャッシュメモリの容量を大きくすることで回避できるが、キャッシュメモリの容量を大きくすると高価になり、大容量化は困難である。後者の問題に対しては、将来使用されることが予想されるデータを実行に先だってあらかじめキャッシュメモリへ転送しておくプリフェッチと呼ばれる方法がある。
【０００４】
【発明が解決しようとする課題】
プリフェッチはメモリアクセス時間をさらに短縮するために有効な手段であるが、投機的なプリフェッチによりかえってキャッシュメモリの効率が下がることもある。キャッシュメモリの容量が小さい場合にプリフェッチを多用すると、プリフェッチしたデータにより既にキャッシュされていたデータがキャッシュアウトされてしまうからである。プリフェッチ命令をどのような状況でいつ発行するのがよいのか、はっきりとした指針がないため、プリフェッチ命令の利用できるプロセッサは多いものの、プリフェッチ命令はあまり有効に使用されていないのが現状である。
【０００５】
本発明はこうした課題に鑑みてなされたものであり、その目的は、効率的なメモリアクセスが可能なプリフェッチ命令制御方法と装置、ならびにキャッシュメモリ制御装置を提供することにある。
【０００６】
【課題を解決するための手段】
本発明のある態様はプリフェッチ命令制御方法に関する。この方法は、データのプリフェッチ命令に、そのデータの利用時刻に関する情報を付加し、前記利用時刻に関する情報をもとに前記プリフェッチ命令の発行タイミングをスケジュールする。プリフェッチデータの利用時刻に関する情報には、そのデータの利用開始時点や利用終了時点を相対時間または絶対時間で指定した情報が含まれる。発行タイミングとは、プリフェッチ命令が外部リソースに対する実プロトコルとして実行に移されるタイミングをいう。発行タイミングのスケジュールとは、プリフェッチ命令の発行時刻を調整したり、複数のプリフェッチ命令の間で発行順序を調整することなどである。また、プリフェッチ命令と、通常のロード命令やストア命令などのアクセス命令との間で発行タイミングを調整してもよい。
【０００７】
本発明の別の態様はプリフェッチ命令制御装置に関する。この装置は、データの利用時刻に関する情報が付加された、外部リソースに対するプリフェッチ命令を記憶する記憶部と、記憶された前記プリフェッチ命令を発行した場合に、前記利用時刻に到達するまでプリフェッチされたデータがキャッシュに滞留することによるコストを評価するコスト評価部と、前記コスト評価部による評価結果にもとづいて、記憶された前記プリフェッチ命令を前記外部リソースに対して発行するタイミングを調整する発行部とを含む。
【０００８】
前記コスト評価部は、前記プリフェッチ命令の発行コストと、前記外部リソースのアクセスリクエストのキューに格納された通常のアクセス命令の発行コストを比較し、前記発行部は、前記コスト評価部による比較結果にもとづいて、現時刻で前記プリフェッチ命令と前記通常のアクセス命令のいずれを発行するかを決定してもよい。前記コスト評価部は、前記発行部による命令の発行の度に、発行コストを再計算し、発行コストを現時刻における値に更新してもよい。
【０００９】
プリフェッチ命令の発行コストの評価の際、プリフェッチ命令の発行により外部リソースのアクセスリクエストのキューに格納された通常のアクセス命令の発行が遅延するコストや、データの利用時刻までにプリフェッチが間に合わなくなるリスクを合わせて評価してもよい。
【００１０】
本発明のさらに別の態様はキャッシュメモリ制御装置に関する。この装置は、外部リソースから取得したデータをキャッシュしてプロセッサに供給するキャッシュメモリと、前記プロセッサから前記外部リソースに対するアクセスプロトコルを受け取り、アクセスプロトコルをスケジュールして前記外部リソースのリクエストキューに設定するスケジューラと、前記リクエストキューから前記アクセスプロトコルを読み出し、前記外部リソースにアクセスして前記キャッシュメモリにデータを供給する外部リソースコントローラとを含み、前記スケジューラは、前述のプリフェッチ命令制御装置である。
【００１１】
前記スケジューラは、前記プリフェッチ命令の発行後に、前記利用時刻に関する情報に含まれるプリフェッチデータの利用開始時刻および利用終了時刻にもとづき、利用開始から終了までの間、前記キャッシュメモリにおけるプリフェッチデータのキャッシュをロックしてもよい。
【００１２】
本発明のさらに別の態様はコンピュータプログラムに関する。このプログラムは、ソースコードを解析して中間コードに変換するステップと、前記中間コードにもとづいて、キャッシュメモリへプリフェッチすべきデータを決定し、そのデータに対するアクセス命令を元の実行順序位置よりも前の位置にプリフェッチ命令として挿入し、そのプリフェッチ命令にデータの利用時刻に関する情報を付加するステップと、前記プリフェッチ命令を含む前記中間コードを最適化してオブジェクトコードを生成するステップとをコンピュータに実行させる。
【００１３】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【００１４】
【発明の実施の形態】
図１は、実施の形態に係るプロセッサシステムの構成図である。このプロセッサシステムは、プロセッサモジュール１０と、ブリッジモジュール２０と、Ｉ／Ｏモジュール３０と、メモリモジュール４０とを含む。プロセッサモジュール１０は内部バス３２に、Ｉ／Ｏモジュール３０はＩ／Ｏバス３４に、メモリモジュール４０はメモリバス３６にそれぞれ接続されている。ブリッジモジュール２０は、内部バス３２とＩ／Ｏバス３４をブリッジして、プロセッサモジュール１０によるＩ／Ｏモジュール３０に対するデータの読み書きを制御する。また、ブリッジモジュール２０は、内部バス３２とメモリバス３６をブリッジして、プロセッサモジュール１０によるメモリモジュール４０に対するデータの読み書きを制御する。
【００１５】
プロセッサモジュール１０は、ＣＰＵ１２と、キャッシュメモリ１４と、キャッシュコントローラ１６を含む。ＣＰＵ１２がＩ／ＯやＤＲＡＭなどのリソースＩＤとデータのアドレスを指定してロード命令、ストア命令、プリフェッチ命令などのアクセスプロトコルを発行すると、ブリッジモジュール２０のスケジューラ２２はアクセスプロトコルのスロットをバッファメモリ２４に登録する。スケジューラ２２は、各リソースのアクセスの待ち時間やアクセス速度などのスタティックなリソース情報と、登録されたアクセスプロトコルの待ち状態などのダイナミックな情報を管理し、これらの情報にもとづいて、アクセスプロトコルの発行タイミングをスケジュールして、各リソースのリクエストキューにアクセスプロトコルを設定する。
【００１６】
Ｉ／Ｏコントローラ２６およびメモリコントローラ２８は、それぞれのリクエストキューに設定されたアクセスプロトコルを読み出し、それぞれＩ／Ｏモジュール３０およびメモリモジュール４０にアクセスして指定されたアドレスのデータを読み出す。読み出されたデータは内部バス３２を介してプロセッサモジュール１０のキャッシュコントローラ１６に供給され、キャッシュコントローラ１６は、そのデータをキャッシュメモリ１４にキャッシュするとともに、ＣＰＵ１２にそのデータを提供する。以降、ＣＰＵ１２が同じアドレスのデータをアクセスすると、キャッシュコントローラ１６がキャッシュメモリ１４からキャッシュされたデータをＣＰＵ１２に供給する。キャッシュミスの場合は、ブリッジモジュール２０を経由して前述のようにデータが読み出される。
【００１７】
プロセッサモジュール１０およびブリッジモジュール２０は、本発明のキャッシュメモリ制御装置の一例であり、ブリッジモジュール２０のスケジューラ２２およびバッファメモリ２４は、本発明のプリフェッチ制御装置の一例である。
【００１８】
ＣＰＵ１２は、メモリモジュール４０にロードされたコンパイラを実行して、プログラムのソースコードをコンパイルし、オブジェクトコードを生成する。このオブジェクトコードの生成過程で、プリフェッチ命令が挿入される。
【００１９】
図２は、プログラムのコンパイル手順を説明するフローチャートである。コンパイラは、プログラムのソースコードを解析して中間コードに変換する（Ｓ１０）。次にコンパイラは、中間コードにもとづいてロード命令によりアクセスされるデータの内、プリフェッチすべきものを決定し、そのデータのアドレスを算出する（Ｓ１２）。次に、コンパイラは、そのロード命令の実行順序位置よりも前の位置に、そのデータのアドレスを引数として指定したプリフェッチ命令を挿入し、そのデータが実際に利用される時刻がプリフェッチ命令の挿入位置から何ステップ先であるかを示した利用時刻指定情報をプリフェッチ命令のもう一つの引数として付加する（Ｓ１４）。コンパイラは、こうして利用時刻指定情報付きのプリフェッチ命令（以下、拡張プリフェッチ命令と呼ぶ）が挿入された中間コードを最適化し（Ｓ１６）、オブジェクトコードを生成する（Ｓ１８）。なお、拡張プリフェッチ命令は、コンパイラによらずに、注意深くチューニングされたアセンブラプログラムによって挿入されてもよい。
【００２０】
図３（ａ）〜（ｄ）は、図２のコンパイル手順により拡張プリフェッチ命令が挿入されたプログラムの例を説明する図である。プログラム６０には、ロード命令（ＬＤ）、ストア命令（ＳＴ）、拡張プリフェッチ命令（ＰｒｅＦｅｔｃｈ）などのアクセスプロトコルが含まれる。図３（ａ）の例では、ロード命令６４、６６で利用されるデータｙｙｙ−０、ｙｙｙ−１を含むデータエリアｙｙｙをあらかじめキャッシュするための拡張プリフェッチ命令６２ａが、ロード命令６４の実行順序位置よりもｎステップ前に挿入されている。
【００２１】
拡張プリフェッチ命令６２ａの引数には、プリフェッチすべきデータエリアｙｙｙと、利用開始時刻ｎが指定される。利用開始時刻ｎにより、拡張プリフェッチ命令６２ａの挿入位置から数えてｎステップ先でデータエリアｙｙｙへのアクセスが始まることを知ることができる。しかし（ｎ＋１）ステップ以降に、データエリアｙｙｙへのアクセスがあるかどうかは不明である。一般に、配列データの場合にはデータエリアｙｙｙ内の連続したデータが一度にアクセスされるため、（ｎ＋１）ステップ以降にもデータエリアｙｙｙ内のデータが利用される可能性がある。したがって、この拡張プリフェッチ命令６２ａの利用開始時刻ｎから判断できることは、斜線で示したように、ｎステップ先以降にデータエリアｙｙｙへのアクセスがあるということだけである。
【００２２】
図３（ｂ）の例では、拡張プリフェッチ命令６２ｂの引数に、利用時刻指定情報として、プリフェッチされるデータエリアｙｙｙの利用開始時刻ｎと利用終了時刻ｍが指定される。データエリアｙｙｙは、拡張プリフェッチ命令６２ｂの挿入位置から数えてｎステップ後のロード命令６４で初めてアクセスされ、ｍステップ後のストア命令６８で最後にアクセスされる。すなわち、斜線で示した区間でのみデータエリアｙｙｙがアクセスされる。このようにデータエリアｙｙｙの利用開始時刻ｎと利用終了時刻ｍの両方を指定することにより、データエリアｙｙｙのキャッシュをロックすべき期間を明確にすることができる。
【００２３】
図３（ｃ）の例では、拡張プリフェッチ命令６２ｃの引数に、プリフェッチされるデータエリアｙｙｙの利用開始時刻ｎと優先度ｃが指定される。この優先度ｃは、複数のプリフェッチ命令が登録されている場合に、どのプリフェッチ命令を先に発行するかを決めるために利用される。また優先度ｃは、プリフェッチしたデータがキャッシュアウトされるときに、どのキャッシュデータを先にキャッシュアウトするかを決めるためにも利用される。
【００２４】
図３（ｄ）の例では、拡張プリフェッチ命令６２ｄの引数に、プリフェッチされるデータｙｙｙの利用時刻指定情報として、既に述べた利用開始時刻ｎと利用終了時刻ｍが指定され、さらに優先度ｃも指定される。
【００２５】
図４は、拡張プリフェッチ命令の発行によりキャッシュメモリ１４のキャッシュがロックされる様子を説明する図である。ここでは、図３（ｄ）の拡張プリフェッチ命令６２ｄを例に説明する。ＣＰＵ１２によりプログラム６０が実行され、プログラムカウンタＰＣが同図の位置まで到達すると、プリフェッチ命令６２ｄが発行される。ＣＰＵ１２は、プリフェッチ命令の引数に指定されたデータエリアｙｙｙ、利用開始時刻ｎ、利用終了時刻ｍ、優先度ｃ、およびプログラムカウンタＰＣの値ｐｃを用いて、スケジューラ２２にジャスト・イン・タイムプロトコルＬｏａｄｔｏＣａｃｈｅ（ｙｙｙ，ｐｃ，ｎ，ｍ，ｃ）を発行する。
【００２６】
ＣＰＵ１２が発行したジャスト・イン・タイムプロトコルを受け取ったスケジューラ２２は、キャッシュコントローラ１６に対して、現在のプログラムカウンタＰＣの値ｐｃから数えて（ｐｃ＋ｍ）ステップ先までデータエリアｙｙｙのキャッシュをロックする予約指示を行う。スケジューラ２２は、アクセス対象のＤＲＡＭやＩ／Ｏなどのリソースのレーテンシーやバンド幅などの静的な特性と、リソースのリクエストキューの動的な状態をもとに、プリフェッチ命令６２ｄの発行タイミングをスケジュールして、リソースのリクエストプロトコルキューに実プロトコルを設定する。スケジューラ２２は、実プロトコルが発行された時点で、データエリアｙｙｙのキャッシュのロックを開始する指示をキャッシュコントローラ１６に与える。キャッシュコントローラ１６は、ロックの開始指示を受け取った時点から予約指示により指定されたロック終了時点までの期間、データエリアｙｙｙのキャッシュをロックする。
【００２７】
図５は、図１で説明したブリッジモジュール２０を機能面から見た構成図である。プロトコルスロット生成部５０、コスト評価部５２、およびプロトコル発行部５４は、図１のスケジューラ２２に実現される機能構成であり、スケジュールリスト記憶部５６および通常プロトコルキュー記憶部５８は、図１のバッファメモリ２４に実現される機能構成である。
【００２８】
プロトコルスロット生成部５０は、ＣＰＵ１２からアクセスプロトコルを受け取る。アクセスプロトコルには、拡張プリフェッチ命令にもとづいたジャスト・イン・タイムプロトコルと、通常のロード命令やストア命令にもとづいた通常アクセスプロトコルとがある。
【００２９】
図６は、プロトコルスロット生成部５０によるプロトコルスロットの生成手順を説明するフローチャートである。まず、プロトコルスロット生成部５０は、ＣＰＵ１２から受け取ったアクセスプロトコルがジャスト・イン・タイムプロトコルかどうかを識別し（Ｓ２０）、ジャスト・イン・タイムプロトコルであれば（Ｓ２０のＹ）、拡張プリフェッチ命令においてプログラムカウンタＰＣの値ｐｃからｎステップ後と指定されていた利用時刻をスケジューラ２２におけるカウンタの単位時間に補正する（Ｓ２２）。次に、このジャスト・イン・タイムプロトコルによるアクセスでリソースが占有される時間を示したプロトコルスロットを生成する（Ｓ２４）。生成されたプロトコルスロットは、スケジュールリスト記憶部５６に格納されたジャスト・イン・タイムプロトコルのスケジュールリスト７０に登録される（Ｓ２６）。
【００３０】
ステップＳ２０において、ＣＰＵ１２から受け取ったアクセスプロトコルがジャスト・イン・タイムプロトコルでなければ（Ｓ２０のＮ）、プロトコルスロット生成部５０は、そのアクセスプロトコルを通常プロトコルとして処理し、リソース占有時間を示したプロトコルスロットを生成する（Ｓ２８）。生成されたプロトコルスロットは、通常プロトコルキュー記憶部５８に格納された通常プロトコルキュー９０に挿入される（Ｓ３０）。
【００３１】
図７は、図５のスケジュールリスト記憶部５６に格納されるジャスト・イン・タイムプロトコルのスケジュールリスト７０を説明する図である。スケジューラ２２のカウンタの単位時間に補正された時間を縦軸にとり、現時刻ｓｔにおけるスケジュールリスト７０のプロトコルスロットの登録状態が図示されている。スケジュールリスト７０は、スケジューラ２２のカウンタの最小単位時間で区切られており、斜線で示すように、現時刻ｓｔに対して、２単位時間後、４単位時間後、８単位時間後にジャスト・イン・タイムプロトコルのスロット７２ａ、７４、７６が格納されている。これは、これらのプロトコルスロット７２ａ、７４、７６によりプリフェッチされたデータの利用時刻が（ｓｔ＋２）、（ｓｔ＋４）、（ｓｔ＋８）であることを示している。もっとも、この図は、理解のために、各プロトコルスロットで指定された利用開始時刻に合わせて、プロトコルスロットの格納位置を模式的に示したものであり、実装上は、プロトコルスロットは、利用時刻ｓｃｔｉと優先度ｃｉの組をインデックスとしてスケジュールリスト７０に登録され、利用時刻ｓｃｔｉの早い順にソートされて同図のようにポインタでつないだリスト構造を形成する。
【００３２】
ジャスト・イン・タイムプロトコルを一般にｊｔｐ（ｓｃｔ，ｒｆｒｏｍ，ｐｔｆｒｏｍ，ｒｔｏ，ｐｔｔｏ，ｃ）と表記する。ここで第１引数ｓｃｔは利用時刻、第６引数ｃは優先度である。第２引数ｒｆｒｏｍはデータの転送元のリソース、第４引数ｒｔｏはデータの転送先のリソースである。第３引数ｐｔｆｒｏｍ、第５引数ｐｔｔｏはそれぞれデータの転送元、転送先のリソースの占有時間である。リソースの占有時間は、そのリソースのデータ転送速度やレーテンシーなどで決まる。たとえば、リソースとしてＤＲＡＭ、Ｉ／Ｏ、キャッシュメモリなどがあり、Ｉ／Ｏからキャッシュメモリへのデータ転送や、逆にキャッシュメモリからＩ／Ｏへのデータ転送をこの記述形式で表現することができる。
【００３３】
図７の例では、アクセス対象として４つのリソースｒ１〜ｒ４があり、ジャスト・イン・タイムプロトコルｊｔｐｉは転送元リソースｒ３、転送先リソースｒ１をそれぞれ占有時間ｐｔ３、ｐｔ１で占有して、データの転送を行うアクセスプロトコルであり、ｊｔｐｉ（ｓｃｔｉ，ｒ３，ｐｔ３，ｒ１，ｐｔ１，ｃｉ）と書ける。ジャスト・イン・タイムプロトコルｊｔｐｉのプロトコルスロット７２ａのデータ構造７２ｂは、同図のように、第１リソースｒ１の占有時間ｐｔ１、第３リソースｒ３の占有時間ｐｔ３を指定したものである。
【００３４】
ここで、４つのリソースｒ１〜ｒ４の内、第１リソースｒ１、第２リソースｒ２はスケジューラ２２のカウンタの最小時間単位で占有時間が計数されるが、第３リソースｒ３の占有時間は、２倍の長さの時間単位で、第４リソースｒ４の占有時間は、４倍の長さの時間単位で計数される。これは、リソースによってアクセス占有時間の最小単位が異なるからである。以下、説明の簡単のため、リソースごとのアクセス占有時間の最小単位にかかわらず、スケジューラ２２のカウンタの最小単位で占有時間を表現する。たとえば、ジャスト・イン・タイムプロトコルｊｔｐｉでは、第３リソースｒ３が第３リソースｒ３のアクセス占有時間の最小単位で１単位時間だけ占有されるが、これは、スケジューラ２２のカウンタの最小単位では、３単位時間に相当する。そこで、便宜上、第３リソースｒ３の占有時間ｐｔ３をスケジューラ２２のカウンタの最小単位で表現して、３単位時間とする。したがって、ジャスト・イン・タイムプロトコルｊｔｐｉはｊｔｐｉ（ｓｃｔｉ，ｒ３，３，ｒ１，２，ｃｉ）と書ける。ここで、転送先のリソースｒ１の占有開始時刻は、転送元のリソースｒ３の占有開始時刻よりも１単位だけ遅れているが、これは、転送元のリソースｒ３のアクセスが始まって１単位時間経過後でないと、転送先のリソースｒ１へのデータ転送が始まらないことを意味する。
【００３５】
図８は、図５の通常プロトコルキュー記憶部５８に格納される通常プロトコルキュー９０を説明する図である。通常プロトコルは、データのアクセスに先立ってあらかじめＣＰＵ１２から発行されるジャスト・イン・タイムプロトコルとは違い、データの実際のアクセスのタイミングでＣＰＵ１２から発行される。そこで、プロトコルスロット生成部５０は、通常プロトコルのスロットを、基本的には、通常プロトコルキュー９０の末尾にＣＰＵ１２から送られてきた順序で次々に挿入する。もっとも、プロトコルスロット生成部５０は、通常プロトコルキュー９０に登録されたプロトコルスロットをリソースの空き時間が生じないように順序を入れ替えて、最適化したり、優先度にもとづいて順序を変えることもできる。
【００３６】
通常プロトコルは一般にｎｐ（ｒｆｒｏｍ，ｐｔｆｒｏｍ，ｒｔｏ，ｐｔｔｏ，ｃ）と記述することができる。引数の定義は、ジャスト・イン・タイムプロトコルと同じである。第５引数の優先度ｃはオプションであり、使用しない場合もある。優先度ｃの利用方法はジャスト・イン・タイムプロトコルの場合と同じである。図５の例では、現時刻ｓｔにおいて、第ｉ番目から第（ｉ＋３）番目までの通常プロトコルｎｐｉ、ｎｐｉ＋１、ｎｐｉ＋２、およびｎｐｉ＋３のスロットが通常プロトコルキュー９０に登録されている。第ｉ番目から第（ｉ＋３）番目までの通常プロトコルはそれぞれｎｐｉ（ｒ１，６，ｒ２，６，ｃｉ）、ｎｐｉ＋１（ｒ３，３，ｒ４，６，ｃｉ＋１）、ｎｐｉ＋２（ｒ２，２，ｒ３，３，ｃｉ＋２）、ｎｐｉ＋３（ｒ４，６，ｒ３，３，ｃｉ＋３）と書ける。通常プロトコルキュー９０の先頭にある出力スロットにある通常プロトコルが順次取り出され、発行される。
【００３７】
図５の機能構成図を再び参照する。コスト評価部５２は、通常プロトコルキュー９０で待ち状態にある通常プロトコルの発行コストと、スケジュールリスト７０に登録されたジャスト・イン・タイムプロトコルの発行コストとを評価し、これらの発行コストを比較する。プロトコル発行部５４は、発行コストの小さい方のプロトコルを発行する。発行されたプロトコルは、リソースＩＤにもとづいて、Ｉ／Ｏに対する命令であれば、Ｉ／Ｏコントローラ２６に、ＤＲＡＭなどのメインメモリに対する命令であれば、メモリコントローラ２８に送られて実行される。
【００３８】
図９は、コスト評価部５２によるアクセスプロトコルの発行コストの評価手順を示すフローチャートである。図１０は、スケジュールリスト７０と通常プロトコルキュー９０のプロトコルスロットの登録状態を説明する図である。これらの図を参照して説明する。
【００３９】
コスト評価部５２は、通常プロトコル発行コストＮｐを算出する（Ｓ４０）。通常プロトコル発行コストＮｐは、一般には、通常プロトコルキュー９０の出力スロットにある通常プロトコルｎｐと現時刻ｓｔの関数であるが、ここでは、次式のように、出力スロットにある通常プロトコルｎｐが発行された場合に、時刻ｔにおいて転送元リソースｒｆｒｏｍが占有されることによるコストＲＣｆｒｏｍ（ｔ）と転送先リソースｒｔｏが占有されることによるＲＣｔｏ（ｔ）の線形和で与えられるとする。
Ｎｐ＝ｎｐ＿ｃｏｓｔ＿ｆｕｎｃ（ｎｐ，ｓｔ）＝ＲＣｆｒｏｍ（ｓｔ）＋ＲＣｔｏ（ｓｔ＋α）
ここで定数αは、転送元リソースの占有開始時刻と転送先リソースの占有開始時刻の時間差である。
【００４０】
図１０の通常プロトコルキュー９０の例では、出力スロットに通常プロトコルｎｐ１が存在する。現時刻ｓｔでこの通常プロトコルｎｐ１が発行されたとすると、現時刻ｓｔで転送元リソースｒ３へのアクセスが始まり、３単位時間だけ転送元リソースｒ３が占有される。このときの占有コストはＲＣ３（ｓｔ）で与えられる。一方、転送先リソースｒ２へのアクセスは２単位時間だけ遅れて始まり、１単位時間だけ転送先リソースｒ２が占有される。このときの占有コストはＲＣ２（ｓｔ＋２）で与えられる。したがって、通常プロトコル発行コストＮｐはＮｐ＝ＲＣ３（ｔ）＋ＲＣ２（ｔ＋２）により算出される。
【００４１】
次に、コスト評価部５２は、ジャスト・イン・タイムプロトコルの発行コストｊｔｐｃｏｓｔを算出する（Ｓ４２）。コスト評価部５２は、スケジュールリスト７０内に登録されているすべてのプロトコルスロットについて、発行コストｊｔｐｃｏｓｔの評価を行う。もっとも、現時刻ｓｔに最も近い利用時刻ｓｃｔをもつプロトコルスロットや、優先度ｃの最も高いプロトコルスロットについてのみ発行コストｊｔｐｃｏｓｔを評価してもよく、利用時刻ｓｃｔの近い順や優先度ｃの高い順に上位いくつかのプロトコルスロットについて発行コストｊｔｐｃｏｓｔを評価してもよい。図１０の例では、スケジュールリスト７０には、２つのジャスト・イン・タイムプロトコルｊｔｐ１（ｓｃｔ１，ｒ１，ｐｔ１，ｒ２，ｐｔ２，ｃ１）およびｊｔｐ２（ｓｃｔ２，ｒ２，ｐｔ２，ｒ４，ｐｔ４，ｃ２）のスロットが登録されており、コスト評価部５２は、それぞれのプロトコルスロットについて個別に発行コストｊｔｐｃｏｓｔ１およびｊｔｐｃｏｓｔ２を算出する。
【００４２】
ジャスト・イン・タイムプロトコルの発行コストｊｔｐｃｏｓｔは、いくつかのコスト要因を組み合わせて評価される。第１のコスト要因は、通常プロトコル発行遅延コストＬＣである。これは、ジャスト・イン・タイムプロトコルを発行した場合に、通常プロトコルキュー９０で待ち状態にある通常プロトコルの発行が遅延することによる単位時間当たりのコストである。この通常プロトコル発行遅延コストＬＣは、一般には、通常プロトコルキュー９０に格納されているすべての通常プロトコルの関数であるが、ここでは、通常プロトコルｎｐｉごとに計算される遅延コストＬＣ（ｎｐｉ）の線形和で与えられるとする。図１０の例では、現時刻ｓｔにおいて５つの通常プロトコルｎｐ１〜ｎｐ５が通常プロトコルキュー９０で待ち状態にあるから、通常プロトコル発行遅延コストＬＣは、次式で与えられる。
ＬＣ＝ＬＣｆｕｎｃ（ｎｐ１，ｎｐ２，ｎｐ３，ｎｐ４，ｎｐ５）＝ＬＣ（ｎｐ１）＋ＬＣ（ｎｐ２）＋ＬＣ（ｎｐ３）＋ＬＣ（ｎｐ４）＋ＬＣ（ｎｐ５）
ここで、遅延コストＬＣ（ｎｐｉ）は、通常プロトコルｎｐｉの発行が１単位時間だけ遅延した場合に生じるコストである。
【００４３】
通常プロトコルｎｐｉに優先度ｃｉが指定されている場合には、遅延コストをＬＣ（ｎｐｉ，ｃｉ）と表し、通常プロトコルｎｐｉごとの優先度ｃｉを反映した値にしてもよい。たとえば、優先度ｃｉの高い通常プロトコルｎｐｉについては、遅延コストＬＣ（ｎｐｉ，ｃｉ）を大きく評価する。
【００４４】
図１０の例で、第１のジャスト・イン・タイムプロトコルｊｔｐ１（ｓｃｔ１，ｒ１，ｐｔ１，ｒ２，ｐｔ２，ｃ１）を発行した場合、このプロトコルのスロット８２に示されるように、転送先リソースｒ２が現時刻ｓｔから５単位時間だけ占有されるため、通常プロトコルキュー９０の出力スロットにある通常プロトコルｎｐ１によるリソースｒ２の占有時間と重なりが生じる。そのため、ジャスト・イン・タイムプロトコルｊｔｐ１を実行するためには、通常プロトコルキュー９０の出力スロット８６を同図のようにｌｔｃ１時間、すなわち３単位時間だけ後方にシフトさせなければならない。出力スロット８６にある通常プロトコルｎｐ１が３単位時間分遅延することにより、通常プロトコルキュー９０で待ち状態にあるその他の通常プロトコルｎｐ２〜ｎｐ５についても全体として３単位時間分遅延することになる。したがって、全体として、ジャスト・イン・タイムプロトコルｊｔｐ１の発行により、通常プロトコル発行遅延コストＬＣに出力スロット８６の遅延時間ｌｔｃ１を乗じた値ＬＣ×ｌｔｃ１のコストが発生することになる。
【００４５】
第２のジャスト・イン・タイムプロトコルｊｔｐ２を発行した場合についても同様に、このプロトコルのスロット８４と通常プロトコルキュー９０内のプロトコルスロットによるリソースの占有時間の競合関係により、遅延時間ｌｔｃ２を求めることができる。一般に、ジャスト・イン・タイムプロトコルｊｔｐｉの発行による通常プロトコル発行遅延コストは、ＬＣ×ｌｔｃｉにより算出される。
【００４６】
ジャスト・イン・タイムプロトコルの発行コストｊｔｐｃｏｓｔの第２のコスト要因は、プリフェッチデータのキャッシュ滞留コストＣａｃｈｅＲＣである。これは、ジャスト・イン・タイムプロトコルを発行した場合に、プリフェッチされたデータがキャッシュメモリ１４に滞留することによる単位時間当たりのコストである。ジャスト・イン・タイムプロトコルｊｔｐｉによりプリフェッチされるデータの利用時刻ｓｃｔｉから現時刻ｓｔを差し引いた値ｃｔｉ＝（ｓｃｔｉ−ｓｔ）は、現時刻ｓｔでジャスト・イン・タイムプロトコルｊｔｐｉを発行した場合に、プリフェッチされたデータがキャッシュメモリ１４に滞留する時間を示している。したがって、単位時間当たりのキャッシュ滞留コストＣａｃｈｅＲＣに滞留時間ｃｔｉ＝（ｓｃｔｉ−ｓｔ）を乗じた値ＣａｃｈｅＲＣ×（ｓｃｔｉ−ｓｔ）が、現時刻ｓｔでのジャスト・イン・タイムプロトコルｊｔｐｉの発行によるキャッシュ滞留コストを与える。
【００４７】
第３のコスト要因は、ジャスト・イン・タイムプロトコルｊｔｐｉの発行が遅れることにより、アクセスしたいデータが利用時刻までにプリフェッチされないことによるリスクであり、ジャスト・イン・タイムプロトコルｊｔｐｉ、現時刻ｓｔの関数として、Ｔｉｍｅ＿Ｌｉｍｉｔ＿Ｆｕｎｃ（ｊｔｐｉ，ｓｔ）で与えられる。一例として、このリスクを次式のように定義する。
Ｔｉｍｅ＿Ｌｉｍｉｔ＿Ｆｕｎｃ（ｊｔｐｉ，ｓｔ）
＝｛ｓｃｔｉ−ｓｔ＜ｍａｘ（ｐｔｆｒｏｍ，ｐｔｔｏ）＋ａのとき、Ｔｉｍｅ＿Ｌｉｍｉｔ；それ以外のとき、０｝
【００４８】
プリフェッチしたデータのキャッシュ滞留時間（ｓｃｔｉ−ｓｔ）が、プリフェッチのために転送元リソースｒｆｒｏｍおよび転送先リソースｒｔｏが占有される時間ｐｔｆｒｏｍおよびｐｔｔｏのいずれか大きい方の値ｍａｘ（ｐｔｆｒｏｍ，ｐｔｔｏ）よりも小さい場合、利用時刻ｓｃｔｉまでにデータのプリフェッチを完了することができない。そこで、ｍａｘ（ｐｔｆｒｏｍ，ｐｔｔｏ）に余裕をもたせる意味で定数ａを加えた値と、キャッシュ滞留時間（ｓｃｔｉ−ｓｔ）とを比較して、キャッシュ滞留時間（ｓｃｔｉ−ｓｔ）の方が小さくなった場合には、正の定数Ｔｉｍｅ＿Ｌｉｍｉｔをリスクの値とし、キャッシュ滞留時間（ｓｃｔｉ−ｓｔ）の方が大きい間は、リスクの値を０とする。
【００４９】
現時刻ｓｔにおけるジャスト・イン・タイムプロトコルｊｔｐｉの発行コストｊｔｐｃｏｓｔｉは、以上の３つのコスト要因にもとづいて次のように算出される。
ｊｔｐｃｏｓｔｉ＝ｊｔｐ＿ｃｏｓｔ＿ｆｕｎｃ（ｓｔ，ｊｔｐｉ）
＝ＬＣ×ｌｔｃｉ＋（ｓｃｔｉ−ｓｔ）×ＣａｃｈｅＲＣ−Ｔｉｍｅ＿Ｌｉｍｉｔ＿Ｆｕｎｃ（ｊｔｐｉ，ｓｔ）
【００５０】
第３項Ｔｉｍｅ＿Ｌｉｍｉｔ＿Ｆｕｎｃ（ｊｔｐｉ，ｓｔ）は、プリフェッチが間に合わなくなる状況が近づくと、正の値をとり、第１項ＬＣ×ｌｔｃｉと第２項（ｓｃｔｉ−ｓｔ）×ＣａｃｈｅＲＣの和から差し引かれるので、ｊｔｐｃｏｓｔｉの値を全体として下げるように作用する。したがって、ジャスト・イン・タイムプロトコルが守れなくなりそうな状況では、ジャスト・イン・タイムプロトコルを実行することによるコストと、ジャスト・イン・タイムプロトコルを実行しないことによるリスクの間でバランスが取られる。
【００５１】
図９に戻り、プロトコル発行部５４は、現時刻ｓｔにおいて、ジャスト・イン・タイムプロトコルの発行コストｊｔｐｃｏｓｔが通常プロトコル発行コストＮｐよりも小さい場合（Ｓ４４のＹ）、ジャスト・イン・タイムプロトコルを発行し（Ｓ４６）、そうでない場合（Ｓ４４のＮ）、通常プロトコルを発行する（Ｓ４８）。いずれかのプロトコルが発行されると、ステップＳ４０に戻り、以降、その時点での新たなコスト計算がなされ、各時点でのコスト評価にもとづいて適切なプロトコルが選択されて発行される。
【００５２】
図１０の例では、スケジュールリスト７０に登録されている第１のジャスト・イン・タイムプロトコルｊｔｐ１の発行コストｊｔｐｃｏｓｔ１、第２のジャスト・イン・タイムプロトコルｊｔｐ２の発行コストｊｔｐｃｏｓｔ２、通常プロトコルキュー９０の出力スロットにある通常プロトコルｎｐ１の発行コストＮｐのうち、コストが最小であるプロトコルがプロトコル発行部５４により発行される。ここで、ジャスト・イン・タイムプロトコルの発行コストは各時刻で再計算しなければならないことに注意する。なぜなら、各時刻において、通常プロトコルキュー９０内のプロトコルの待ち状態が異なり、それにより、発行コストの第１項ＬＣ×ｌｔｃｉの値が変わるからである。また、第１、第２のジャスト・イン・タイムプロトコルｊｔｐ１、ｊｔｐ２の発行コストｊｔｐｃｏｓｔ１、ｊｔｐｃｏｓｔ２の大小関係についても、同じ理由で各時刻において変化する可能性があり、現時刻ｓｔに近い利用時刻ｓｃｔをもつジャスト・イン・タイムプロトコルの方が、発行コストが小さいとは限らない。
【００５３】
なお、ジャスト・イン・タイムプロトコルの発行コストｊｔｐｃｏｓｔｉは、３つのコスト要因の一部を用いて評価してもよい。たとえば、キャッシュ滞留コストのみで、次式のように評価してもよい。
ｊｔｐｃｏｓｔｉ＝（ｓｃｔｉ−ｓｔ）×ＣａｃｈｅＲＣ
また、これにプリフェッチが間に合わないリスクを組み合わせて、次式のように評価してもよい。
ｊｔｐｃｏｓｔｉ＝（ｓｃｔｉ−ｓｔ）×ＣａｃｈｅＲＣ−Ｔｉｍｅ＿Ｌｉｍｉｔ＿Ｆｕｎｃ（ｊｔｐｉ，ｓｔ）
これらの場合、通常プロトコルキュー９０のプロトコルスロットの状態とは無関係にジャスト・イン・タイムプロトコルの発行コストを評価できるため、コスト計算が簡単である。
【００５４】
以上説明したように、実施の形態によれば、プリフェッチ命令にプリフェッチデータの利用予定時刻を指定することにより、プリフェッチデータがキャッシュに滞留する時間を予想することができ、キャッシュ滞留コストを評価してプリフェッチ命令の発行タイミングを決めることが可能となる。また、リソース占有時間の競合関係に配慮してコスト評価を行うことで、他のアクセス命令の実行とのバランスをとりながら、プリフェッチ命令を発行することができる。これにより、プリフェッチ命令が無駄なく計画的に実行され、キャッシュの利用効率が向上する。
【００５５】
以上、本発明を実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００５６】
そのような変形例を説明する。上記の説明では、拡張プリフェッチ命令において、プリフェッチデータの利用開始時点や利用終了時点を拡張プリフェッチ命令の挿入位置から数えた相対的なステップ数で指定したが、絶対的な時間でプリフェッチデータの利用開始時刻および利用終了時刻を指定してもよい。
【００５７】
また、上記の説明では、ジャスト・イン・タイムプロトコルと通常プロトコルの両方の発行コストを求めて、発行コストの比較によりどちらのアクセスプロトコルを発行するかを決めたが、ジャスト・イン・タイムプロトコルのみの発行コストを求めて、その発行コストが所定の値以下であれば、ジャスト・イン・タイムプロトコルを発行することにしてもよい。
【００５８】
【発明の効果】
本発明によれば、キャッシュによるメモリアクセスのさらなる効率化を図ることができる。
【図面の簡単な説明】
【図１】実施の形態に係るプロセッサシステムの構成図である。
【図２】実施の形態に係るプログラムのコンパイル手順を説明するフローチャートである。
【図３】図３（ａ）〜（ｄ）は、図２のコンパイル手順により拡張プリフェッチ命令が挿入されたプログラムの例を説明する図である。
【図４】拡張プリフェッチ命令の発行により図１のキャッシュメモリのキャッシュがロックされる様子を説明する図である。
【図５】図１のブリッジモジュールを機能面から見た構成図である。
【図６】図５のプロトコルスロット生成部によるプロトコルスロットの生成手順を説明するフローチャートである。
【図７】図５のスケジュールリスト記憶部に格納されるジャスト・イン・タイムプロトコルのスケジュールリストを説明する図である。
【図８】図５の通常プロトコルキュー記憶部に格納される通常プロトコルキューを説明する図である。
【図９】図５のコスト評価部によるアクセスプロトコルの発行コストの評価手順を示すフローチャートである。
【図１０】スケジュールリストと通常プロトコルキューのプロトコルスロットの登録状態を説明する図である。
【符号の説明】
１０  プロセッサモジュール、  １２  ＣＰＵ、  １４  キャッシュメモリ、１６  キャッシュコントローラ、  ２０  ブリッジモジュール、  ２２  スケジューラ、  ２４  バッファメモリ、  ２６  Ｉ／Ｏコントローラ、  ２８  メモリコントローラ、  ３０  Ｉ／Ｏモジュール、  ３２  内部バス、  ３４  Ｉ／Ｏバス、  ３６  メモリバス、  ４０  メモリモジュール、  ５０  プロトコルスロット生成部、  ５２  コスト評価部、  ５４  プロトコル発行部、  ５６スケジュールリスト記憶部、  ５８  通常プロトコルキュー記憶部、  ７０  スケジュールリスト、  ９０  通常プロトコルキュー。
【図１】
2004348175.tif 000003
【図２】
2004348175.tif 000004
【図３】
2004348175.tif 000005
【図４】
2004348175.tif 000006
【図５】
2004348175.tif 000007
【図６】
2004348175.tif 000008
【図７】
2004348175.tif 000009
【図８】
2004348175.tif 000010
【図９】
2004348175.tif 000011
【図１０】
2004348175.tif 000012