(57)【要約】  ＦＰ２２は，処理を行う要求を保持する複数のエントリを有し，各エントリごとにデータ転送要求を一度行ったことを示す要求済みフラグを備える。ＦＰ−ＴＯＱ２３には，一番古い要求を保持するエントリを示す情報が保持される。データ転送要求抑止判定回路２５は，処理を行う要求の要求済みフラグとＦＰ−ＴＯＱ２３とをチェックし，処理を行う要求の対象となるデータの転送要求がすでに発行され，かつ処理を行う要求が保持されたエントリがＦＰ−ＴＯＱ２３で示されたエントリでなければ，該当データの転送要求を抑止する信号をデータ転送要求制御回路２７に送る。データ転送要求制御回路２７は，一次キャッシュＲＡＭ２１でキャッシュミスが発生しても，転送要求を抑止する信号を受けた場合にはデータ転送要求を発行しない。これにより，キャッシュ上のデータの不要な置換を防ぐ。
2008155833.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュメモリと，
前記キャッシュメモリに対するアクセス要求を保持する複数のエントリを有するフェッチポートと，
前記フェッチポートのエントリのうち最も古いアクセス要求を保持するエントリを示す情報を保持するキューレジスタと，
前記フェッチポートの各エントリに保持されたアクセス要求から，次に処理を行うアクセス要求を選択するエントリ選択回路と，
前記エントリ選択回路が選択したアクセス要求に係るデータが前記キャッシュメモリに存在するか否かを判定するキャッシュミス判定回路と，
前記アクセス要求に係るデータが前記キャッシュメモリに存在しない場合に，そのデータの前記キャッシュメモリへの転送を外部に要求するデータ転送要求制御回路と，
前記フェッチポートの各エントリごとに，前記データ転送要求制御回路によりデータ転送要求済みであるか否かを記憶する要求済みフラグと，
前記エントリ選択回路が選択したアクセス要求を保持するフェッチポートのエントリの前記要求済みフラグがデータ転送要求済みであることを示し，かつそのエントリが前記キューレジスタが保持するエントリと異なる場合に，前記データ転送要求制御回路に前記アクセス要求に伴うデータ転送要求を抑止する信号を送信するデータ転送要求抑止判定回路とを備える
ことを特徴とするキャッシュメモリ制御装置。
【請求項２】
前記キャッシュミス判定回路が前記アクセス要求に係るデータが前記キャッシュメモリに存在しないと判定し，かつ前記データ転送要求抑止判定回路がそのアクセス要求を保持するフェッチポートのエントリの前記要求済みフラグがデータ転送要求済みであり，そのエントリが前記キューレジスタが保持するエントリと同じであると判定した場合に，前記データ転送要求制御回路によるデータ転送の再要求が発行された回数を，前記キャッシュメモリにおけるデータ格納位置を示すキャッシュインデックスごとに計測する回数計測回路を備える
ことを特徴とする請求項１記載のキャッシュメモリ制御装置。
【請求項３】
前記回数計測回路は，前記アクセス要求がロード命令である場合とストア命令である場合とを区別して，前記データ転送の再要求が発行された回数を計測する
ことを特徴とする請求項２記載のキャッシュメモリ制御装置。
【請求項４】
キャッシュメモリに対するアクセス要求を，複数のエントリを有するフェッチポートのエントリに保持し，アクセス要求に係るデータの転送を制御するキャッシュメモリ制御方法であって，
前記フェッチポートのエントリのうち最も古いアクセス要求を保持するエントリを示す情報を記憶するステップと，
前記フェッチポートのエントリごとに設けられた，前記キャッシュメモリへのデータの転送を外部に要求したか否かを示す要求済みフラグを，外部へのデータ転送の要求時に設定するステップと，
処理対象となったアクセス要求を保持するフェッチポートのエントリの前記要求済みフラグがデータ転送要求済みであることを示し，かつそのエントリが最も古いアクセス要求を保持するエントリではない場合に，そのアクセス要求に対してキャッシュミスが発生しても，そのアクセス要求に伴うデータ転送要求を抑止し，一度データ転送要求を行ったエントリに保持されたアクセス要求の処理によるデータ転送の再要求は，そのエントリがフェッチポートの全エントリの中で最も古くなるまでは行わないように制御するステップとを有する
ことを特徴とするキャッシュメモリ制御方法。
【請求項５】
キャッシュミスの発生時に，アクセス要求を保持するフェッチポートのエントリの前記要求済みフラグがデータ転送要求済みであることを示していても，そのエントリが最も古いアクセス要求を保持するエントリであるために，データ転送の再要求が発行された場合に，その再要求の発行回数を前記キャッシュメモリにおけるデータ格納位置を示すキャッシュインデックスごとに計測するステップをさらに有する
ことを特徴とする請求項４記載のキャッシュメモリ制御方法。
【請求項６】
前記再要求の発行回数を，前記アクセス要求がロード命令である場合とストア命令である場合とを区別して計測する
ことを特徴とする請求項５記載のキャッシュメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，メモリアクセスをアウトオブオーダーで処理するプロセッサのキャッシュ制御に関するものであり，特に，キャッシュに登録されたデータのスラッシングにより処理速度が低下するのを防ぐキャッシュメモリ制御方法に関するものである。
【背景技術】
【０００２】
メモリアクセスをアウトオブオーダーで処理するプロセッサでは，キャッシュ制御部は，命令制御部からのメモリアクセスの要求を，その要求の順序によらず順不同で処理することが可能である。【０００３】
図１６，図１７は，一次キャッシュ制御部におけるデータの参照，登録，置換の例を説明する図である。図１６，図１７に示す例において，一次キャッシュ制御部２００の一次キャッシュＲＡＭ２１０は，ｗａｙ−０，ｗａｙ−１の２つのｗａｙからなるセットアソシエイティブ（set associative ）方式で構成される。【０００４】
一次キャッシュ制御部２００は，命令制御部１００からメモリアクセスの命令が要求されると，複数エントリからなるＦＰ（Fetch Port）２２０に，その要求を一旦保持する。図１６（Ａ）では，メモリアクセスの命令として，ロード命令が発行された場合の例を示している。【０００５】
一次キャッシュ制御部２００は，ＦＰ２２０に保持された要求の仮想アドレスの一部をキャッシュインデックスとして用いて，一次キャッシュＲＡＭ２１０の該当ラインを参照する。また同時に，アドレス変換により，仮想アドレスに対応する物理アドレスを確定させる（図１６（Ａ）参照）。【０００６】
一次キャッシュ制御部２００は，一次キャッシュＲＡＭ２１０の参照ラインに登録されたデータの物理アドレスが仮想アドレスから変換された物理アドレスと一致しなければ，または一次キャッシュＲＡＭ２１０の参照ラインに登録されたデータが無効（Ｉｎｖａｌｉｄ）であれば，二次キャッシュ制御部３００に対して仮想アドレスから変換された物理アドレスが示すデータの転送を要求する。ここでは，一次キャッシュＲＡＭ２１０において，ｗａｙ−０，ｗａｙ−１の参照ラインのデータが共に有効（Ｖａｌｉｄ）であるが，どちらも仮想アドレスから変換された物理アドレス−Ａと一致しないので，二次キャッシュ制御部３００に対してデータ転送要求を発行する（図１６（Ａ）参照）。【０００７】
このとき，一次キャッシュＲＡＭ２１０の参照ラインに登録されたデータがｗａｙ−０，ｗａｙ−１共に有効（Ｖａｌｉｄ）なデータである場合には，置換制御部２９０により，いずれかのｗａｙを置換対象として選び，選ばれたｗａｙの参照ラインに登録されたデータを，一次キャッシュＲＡＭ２１０から二次キャッシュ制御部３００に吐き出すか，無効化（Ｉｎｖａｌｉｄ）する。以下では，図１６（Ｂ）に示すように，ｗａｙ−０が置換対象として選ばれ，ｗａｙ−０の参照ラインに登録されたデータが無効化（Ｉｎｖａｌｉｄ）されたものとして説明する。【０００８】
一次キャッシュ制御部２００は，二次キャッシュ制御部３００から転送されてきたデータとそのデータの物理アドレスとを，選ばれたｗａｙに登録する。ここでは，転送されてきたデータと物理アドレス−Ａとがｗａｙ−０に登録される（図１７（Ａ）参照）。【０００９】
一次キャッシュ制御部２００は，ＦＰ２２０に保持されているメモリアクセスの命令を再実行する。ここでは，ＦＰ２２０に保持されているロード命令を再実行し，一次キャッシュＲＡＭ２１０の該当ラインを参照すると，この時点では物理アドレスが一致する有効なデータがｗａｙ−０に存在するので，そのデータを命令制御部１００に送り，ＦＰ２２０を開放し，処理を完了する（図１７（Ｂ）参照）。【００１０】
なお，キャッシュメモリの制御に関する先行技術が記載された文献として，例えば特許文献１などがある。特許文献１には，ロード命令とストア命令とがアウトオブオーダーで実行されるプロセッサにおいて，命令のスループットを増加させる技術が記載されている。
【特許文献１】特開２０００−２５９４１２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従来，物理アドレスが異なるが，キャッシュインデックスが同一となる複数のメモリアクセスの命令を処理する際に，それぞれの命令がキャッシュ上のデータを参照する前に，置換処理によりその対象データを互いにキャッシュから追い出しあい，命令が完了しないケースがあるという問題がある。以下では，この問題点を具体例で説明する。【００１２】
図１８〜図２４は，一次キャッシュ制御部における処理の問題点を説明する図である。一次キャッシュ制御部２００の一次キャッシュＲＡＭ２１０が，ｗａｙ−０，ｗａｙ−１の２つのｗａｙからなるセットアソシエイティブ（set associative ）方式で構成される場合の例に従って，上記問題点を説明する。【００１３】
図１８に示すように，３つのメモリアクセス要求が，命令制御部１００から一次キャッシュ制御部２００に対して発行されたとする。ここでは，便宜上，３つのメモリアクセス要求を，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃと表記する。３つのメモリアクセス要求は，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃの順に発行され，それぞれが同一のキャッシュインデックスであるが，物理アドレスが異なるものとする。各要求ｌｏａｄ−Ａ，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃは，一旦，一次キャッシュ制御部２００のＦＰ２２０のエントリ０，１，２に，それぞれ順に保持される（図１８（Ａ）参照）。なお，図において，メモリアクセス要求の左側に表記された数字がＦＰ２００の各エントリを示す番号である。【００１４】
一次キャッシュ制御部２００は，可能であればアウトオブオーダーで要求を処理する機能を持つ。これにより，例えば最も古い要求であるｌｏａｄ−Ａの処理より先に，ｌｏａｄ−Ｂの処理を行うために一次キャッシュＲＡＭ２１０にアクセスしたとする。このとき，ｌｏａｄ−Ｂの対象データが一次キャッシュＲＡＭ２１０に存在しなければ，二次キャッシュ制御部３００に対してデータ転送を要求する（図１８（Ａ）参照）。【００１５】
その後，二次キャッシュ制御部３００からデータが転送され，一次キャッシュＲＡＭ２１０のｗａｙ−０に登録される（図１８（Ｂ）参照）。データ転送要求からデータが登録されるまでの間は，同一キャッシュインデックスの処理が一時期に一つずつしか実行できないため，ｌｏａｄ−Ａ，ｌｏａｄ−Ｃの処理はＦＰ２２０で待機となる。【００１６】
ｌｏａｄ−Ｂに対するデータ登録が完了した後，ｌｏａｄ−Ａの処理やｌｏａｄ−Ｂの再処理より先に，ｌｏａｄ−Ｃの処理を行うために一次キャッシュＲＡＭ２１０にアクセスしたとする。このとき，ｌｏａｄ−Ｃの対象データが一次キャッシュＲＡＭ２１０に存在しなければ，二次キャッシュ制御部３００に対してデータ転送を要求する（図１９（Ａ）参照）。【００１７】
その後，二次キャッシュ制御部３００からデータが転送され，一次キャッシュＲＡＭ２１０のｗａｙ−１に登録される（図１９（Ｂ）参照）。データ転送要求からデータが登録されるまでの間は，同一キャッシュインデックスの処理が一時期に一つずつしか実行できないため，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂの処理はＦＰ２２０で待機となる。【００１８】
ｌｏａｄ−Ｃに対するデータ登録が完了した後，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃの再処理より先に，ｌｏａｄ−Ａの処理を行うために一次キャッシュＲＡＭ２１０にアクセスしたとする。このとき，ｌｏａｄ−Ａの対象データが一次キャッシュＲＡＭ２１０に存在しないので，二次キャッシュ制御部３００に対してデータ転送を要求する（図２０（Ａ）参照）。【００１９】
同時に，ｗａｙ−０，ｗａｙ−１には共に有効なデータが存在するため，置換制御部２９０により，ｗａｙ−０を置換対象とし，ｗａｙ−０にあるｌｏａｄ−Ｂの対象データを無効化（Ｉｎｖａｌｉｄ）する（図２０（Ｂ）参照）。【００２０】
その後，二次キャッシュ制御部３００からデータが転送され，一次キャッシュＲＡＭ２１０のｗａｙ−０に登録される（図２１（Ａ）参照）。データ転送要求からデータが登録されるまでの間は，同一キャッシュインデックスの処理が一時期に一つずつしか実行できないため，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃの処理はＦＰ２２０で待機となる。【００２１】
ｌｏａｄ−Ａに対するデータ登録が完了した後，ｌｏａｄ−Ａ，ｌｏａｄ−Ｃの再処理より先に，ｌｏａｄ−Ｂの処理を行うために一次キャッシュＲＡＭ２１０にアクセスしたとする。このとき，以前にｗａｙ−０に登録されていたｌｏａｄ−Ｂの対象データはｌｏａｄ−Ａの対象データに置換されてしまっているため，再度二次キャッシュ制御部３００に対してデータ転送を要求する（図２１（Ｂ）参照）。【００２２】
同時に，ｗａｙ−０，ｗａｙ−１には共に有効なデータが存在するため，置換制御部２９０により，ｗａｙ−１を置換対象とし，ｗａｙ−１にあるｌｏａｄ−Ｃの対象データを無効化（Ｉｎｖａｌｉｄ）する（図２２（Ａ）参照）。【００２３】
その後，二次キャッシュ制御部３００からデータが転送され，一次キャッシュＲＡＭ２１０のｗａｙ−１に登録される（図２２（Ｂ）参照）。データ転送要求からデータが登録されるまでの間は，同一キャッシュインデックスの処理が一時期に一つずつしか実行できないため，ｌｏａｄ−Ａ，ｌｏａｄ−Ｃの処理はＦＰ２２０で待機となる。【００２４】
ｌｏａｄ−Ｂに対するデータ登録が完了した後，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂの再処理より先に，ｌｏａｄ−Ｃの処理を行うために一次キャッシュＲＡＭ２１０にアクセスしたとする。このとき，以前にｗａｙ−１に登録されていたｌｏａｄ−Ｃの対象データはｌｏａｄ−Ｂの対象データに置換されてしまっているため，再度二次キャッシュ制御部３００に対してデータ転送を要求する（図２３（Ａ）参照）。【００２５】
同時に，ｗａｙ−０，ｗａｙ−１には共に有効なデータが存在するため，置換制御部２９０により，ｗａｙ−０を置換対象とし，ｗａｙ−０にあるｌｏａｄ−Ａの対象データを無効化（Ｉｎｖａｌｉｄ）する（図２３（Ｂ）参照）。【００２６】
その後，二次キャッシュ制御部３００からデータが転送され，一次キャッシュＲＡＭ２１０のｗａｙ−０に登録される（図２４参照）。データ転送要求からデータが登録されるまでの間は，同一キャッシュインデックスの処理が一時期に一つずつしか実行できないため，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂの処理はＦＰ２２０で待機となる。【００２７】
以降，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃ，... という順で一連の処理が循環すると，命令の実行が完了しないことになる。【００２８】
本発明は，上記の問題点の解決を図り，同一のキャッシュインデックスで物理アドレスが異なる複数のメモリアクセスの命令によって発生するキャッシュ上のデータの不要な置換を防ぐ技術を提供することを目的とする。
【課題を解決するための手段】
【００２９】
本発明は，上記課題を解決するため，データ転送要求を一度行ったことを示すフラグをＦＰの各エントリごとに用意し，また最も古い要求が保持されたエントリを示す情報を用意し，一度データ転送要求を行ったエントリに保持された要求の処理によるデータ転送の再要求はそのエントリがＦＰの全エントリの中で最も古くなるまでは行わないとすることで，処理を行う要求の対象データが置換され続けることを防ぐことを特徴とする。【００３０】
具体的には，本発明は，キャッシュメモリと，前記キャッシュメモリに対するアクセス要求を保持する複数のエントリを有するフェッチポートと，前記フェッチポートのエントリのうち最も古いアクセス要求を保持するエントリを示す情報を保持するキューレジスタと，前記フェッチポートの各エントリに保持されたアクセス要求から，次に処理を行うアクセス要求を選択するエントリ選択回路と，前記エントリ選択回路が選択したアクセス要求に係るデータが前記キャッシュメモリに存在するか否かを判定するキャッシュミス判定回路と，前記アクセス要求に係るデータが前記キャッシュメモリに存在しない場合に，そのデータの前記キャッシュメモリへの転送を外部に要求するデータ転送要求制御回路と，前記フェッチポートの各エントリごとに，前記データ転送要求制御回路によりデータ転送要求済みであるか否かを記憶する要求済みフラグと，前記エントリ選択回路が選択したアクセス要求を保持するフェッチポートのエントリの前記要求済みフラグがデータ転送要求済みであることを示し，かつそのエントリが前記キューレジスタが保持するエントリと異なる場合に，前記データ転送要求制御回路に前記アクセス要求に伴うデータ転送要求を抑止する信号を送信するデータ転送要求抑止判定回路とを備えることを特徴とする。【００３１】
以上の構成により，メモリアクセスをアウトオブオーダーで処理するプロセッサのキャッシュ制御において，ある命令のアクセス対象のデータ域をキャッシュに登録した後，その命令がキャッシュアクセスするまでの間に，他データ域をアクセスする他命令のキャッシュアクセスにより，該当データ域が置換され，該当データ域の登録を再要求する，という処理が繰り返されることを防ぐことができる。【００３２】
また，本発明は，さらに前記キャッシュミス判定回路が前記アクセス要求に係るデータが前記キャッシュメモリに存在しないと判定し，かつ前記データ転送要求抑止判定回路がそのアクセス要求を保持するフェッチポートのエントリの前記要求済みフラグがデータ転送要求済みであり，そのエントリが前記キューレジスタが保持するエントリと同じであると判定した場合に，前記データ転送要求制御回路によるデータ転送の再要求が発行された回数を，前記キャッシュメモリにおけるデータ格納位置を示すキャッシュインデックスごとに計測する回数計測回路を備えることを特徴とする。【００３３】
以上の構成により，特定のキャッシュエントリを，複数の要求の対象となるデータで置換し合うことを回避した回数を計測し，これをプログラムのチューニングの参考情報として利用してプログラムを設計することが可能となる。
【発明の効果】
【００３４】
本発明によって，アウトオブオーダー処理をするプロセッサのキャッシュ制御において，キャッシュ上のデータの不要な置換を防ぐことにより，性能向上を図ることが可能となる。
【図面の簡単な説明】
【００３５】
【図１】本実施の形態によるプロセッサの構成例を示す図である。
【図２】本実施の形態による一次キャッシュ制御部の構成例を示す図である。
【図３】ＦＰのエントリが保持する情報の構成要素の例を示す図である。
【図４】本実施の形態によるデータ転送要求の処理フローチャートである。
【図５】本実施の形態による一次キャッシュ制御部の処理例を説明する図である。
【図６】本実施の形態による一次キャッシュ制御部の処理例を説明する図である。
【図７】本実施の形態による一次キャッシュ制御部の処理例を説明する図である。
【図８】本実施の形態による一次キャッシュ制御部の処理例を説明する図である。
【図９】本実施の形態による一次キャッシュ制御部の処理例を説明する図である。
【図１０】本実施の形態による一次キャッシュ制御部の処理例を説明する図である。
【図１１】本実施の形態による一次キャッシュ制御部の処理例を説明する図である。
【図１２】本実施の形態による一次キャッシュ制御部の処理例を説明する図である。
【図１３】本実施の形態による一次キャッシュ制御部の構成例を示す図である。
【図１４】本実施の形態によるデータ転送要求の処理フローチャートである。
【図１５】本実施の形態によるデータ転送要求の処理フローチャートである。
【図１６】一次キャッシュ制御部におけるデータの参照，登録，置換の例を説明する図である。
【図１７】一次キャッシュ制御部におけるデータの参照，登録，置換の例を説明する図である。
【図１８】一次キャッシュ制御部における処理の問題点を説明する図である。
【図１９】一次キャッシュ制御部における処理の問題点を説明する図である。
【図２０】一次キャッシュ制御部における処理の問題点を説明する図である。
【図２１】一次キャッシュ制御部における処理の問題点を説明する図である。
【図２２】一次キャッシュ制御部における処理の問題点を説明する図である。
【図２３】一次キャッシュ制御部における処理の問題点を説明する図である。
【図２４】一次キャッシュ制御部における処理の問題点を説明する図である。
【符号の説明】
【００３６】
１  ＣＰＵ
９  システム制御バス
１０  命令制御部（演算制御部）
２０  一次キャッシュ制御部
２１  一次キャッシュＲＡＭ
２２  ＦＰ
２３  ＦＰ−ＴＯＱ
２４  エントリ選択回路
２５  データ転送要求抑止判定回路
２６  キャッシュミス判定回路
２７  データ転送要求制御回路
２８  回数計測回路
２９  置換制御部
３０  二次キャッシュ制御部
３１  二次キャッシュＲＡＭ
【発明を実施するための最良の形態】
【００３７】
以下，本実施の形態について，図を用いて説明する。【００３８】
図１は，本実施の形態によるプロセッサの構成例を示す図である。ＣＰＵ１は，命令制御部（演算制御部）１０，一次キャッシュ制御部２０，二次キャッシュ制御部３０を備え，システム制御バス９で外部の記憶装置等に接続される。一次キャッシュ制御部２０は，容量は少ないがアクセスが速い一次キャッシュＲＡＭ２１を備える。二次キャッシュ制御部３０は，一次キャッシュＲＡＭ２１と比較して容量は大きいがアクセスが遅い二次キャッシュＲＡＭ３１を備える。【００３９】
命令制御部（演算制御部）１０がロード命令，ストア命令等の要求を一次キャッシュ制御部２０に発行すると，一次キャッシュ制御部２０は，一次キャッシュＲＡＭ２１に命令制御部（演算制御部）１０からの要求の対象となるデータが存在するかを確認し，存在すればそのデータを命令制御部（演算制御部）１０に返す。命令制御部（演算制御部）１０からの要求の対象となるデータが存在しなければ，二次キャッシュ制御部３０に該当データの転送を要求する。【００４０】
二次キャッシュ制御部３０は，一次キャッシュ制御部２０からデータ転送の要求を受けると，二次キャッシュＲＡＭ３１に一次キャッシュ制御部２０から要求されたデータが存在するかを確認し，存在すればそのデータを一次キャッシュ制御部２０に返す。一次キャッシュ制御部から要求されたデータが存在しなければ，システム制御バス９を介して外部の記憶装置に該当データの転送を要求する。【００４１】
図２は，本実施の形態による一次キャッシュ制御部の構成例を示す図である。一次キャッシュ制御部２０は，一次キャッシュＲＡＭ２１，ＦＰ（Fetch Port）２２，ＦＰ−ＴＯＱ（Fetch Port Top Of Queue ）２３，エントリ選択回路２４，データ転送要求抑止判定回路２５，キャッシュミス判定回路２６，データ転送要求制御回路２７を備える。【００４２】
ＦＰ２２は，命令制御部（演算制御部）１０から受けた要求を保持する複数のエントリを有する。ＦＰ２２の各エントリには，そのエントリに保持された要求の対象となるデータの二次キャッシュ制御部３０への転送要求が発生したか否かを示す要求済みフラグが設けられている。ＦＰ−ＴＯＱ２３は，ＦＰ２２のエントリのうち，一番古い要求を保持するエントリが記録されるレジスタである。【００４３】
エントリ選択回路２４は，ＦＰ２２の各エントリに保持された要求から，次に処理を行う要求を選択する。【００４４】
データ転送要求抑止判定回路２５は，処理を行う要求の要求済みフラグと，ＦＰ−ＴＯＱ２３とをチェックし，処理を行う要求の対象となるデータの転送要求がすでに発行され，かつ処理を行う要求が保持されたエントリがＦＰ−ＴＯＱ２３で示されたエントリでなければ，該当データの転送要求を抑止する信号をデータ転送要求制御回路２７に送る。このデータ転送要求抑止判定回路２５は，例えば排他的論理和回路などによる比較回路，ＮＡＮＤ回路などの論理回路によって構成することができる。【００４５】
キャッシュミス判定回路２６は，処理を行う要求の対象となるデータが一次キャッシュＲＡＭ２１に存在するか否かを判定する。存在しない場合にはキャッシュミスとなり，その旨をデータ転送要求制御回路２７に通知する。【００４６】
データ転送要求制御回路２７は，キャッシュミスが発生時に，二次キャッシュ制御部３０に対して該当データの転送要求を送る。ただし，データ転送要求抑止判定回路２５から転送要求を抑止する信号を受けた場合には，キャッシュミスが発生してもデータ転送要求を発行しない。【００４７】
図３は，ＦＰのエントリが保持する情報の構成要素の例を示す図である。図３の例は，ＦＰ２２のエントリが保持する情報のうち，特に本発明に関連する部分の構成について抜粋したものである。ＦＰ２２の各エントリは，ロード命令，ストア命令などの命令の種別を示す命令コード（ｏｐｃｏｄｅ），その命令の対象となるデータのアドレス（ａｄｄｒｅｓｓ），上述の要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）の情報を保持する。【００４８】
図４は，本実施の形態によるデータ転送要求の処理フローチャートである。図４のフローチャートにおいて，ＦＰ−ｎ（ｎ＝０，１，２，... ）は，ＦＰ２２の各エントリを示し，ｎ（ｎ＝０，１，２，... ）は，便宜上エントリに割り当てられた番号を示す。また，要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）は，１が要求済みであることを示し，０が未要求であることを示すものとする。【００４９】
ＦＰ−ｎのエントリに保持された要求が処理を行う要求として選択されると（ステップＳ１０），その要求に示されたアドレスで一次キャッシュＲＡＭ２１にアクセスする（ステップＳ１１）。このとき，キャッシュミスが発生しなければ（ステップＳ１２），二次キャッシュ制御部３０へのデータ転送要求は発行しない。【００５０】
キャッシュミスが発生したときに（ステップＳ１２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号であれば（ステップＳ１３），二次キャッシュ制御部３０に該当データの転送要求を発行する（ステップＳ１５）。【００５１】
キャッシュミスが発生したときに（ステップＳ１２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号でなくても（ステップＳ１３），そのエントリの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が０（すなわち未要求）であれば（ステップＳ１４），二次キャッシュ制御部３０に該当データの転送要求を発行する（ステップＳ１５）。【００５２】
キャッシュミスが発生しても（ステップＳ１２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号でなく（ステップＳ１３），かつそのエントリの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１（すなわち要求済み）であれば（ステップＳ１４），二次キャッシュ制御部３０にデータ転送要求を発行しない。【００５３】
図５〜図１２は，本実施の形態による一次キャッシュ制御部の処理例を説明する図である。ここでは，図５〜図１２を用いて，本実施の形態による一次キャッシュ制御部２０による処理のより具体的な例を説明する。図５〜図１２に示す例において，一次キャッシュ制御部２０の一次キャッシュＲＡＭ２１は，ｗａｙ−０，ｗａｙ−１の２つのｗａｙからなるセットアソシエイティブ（set associative ）方式で構成される。【００５４】
図５（Ａ）に示すように，３つのメモリアクセス要求が，命令制御部（演算制御部）１０から一次キャッシュ制御部２０に対して発行されたとする。ここでは，便宜上，３つのメモリアクセス要求を，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃと表記する。３つのメモリアクセス要求は，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃの順に発行され，それぞれが同一のキャッシュインデックスであるが，物理アドレスが異なるものとする。各要求ｌｏａｄ−Ａ，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃは，一旦，一次キャッシュ制御部２０のＦＰ２２のエントリ０，１，２に，それぞれ順に保持される（図５（Ａ）参照）。【００５５】
なお，図において，メモリアクセス要求の左側に表記された数字がＦＰ２２の各エントリを示す番号である。以下では，ＦＰ２２の各エントリを，ＦＰ−ｎ（ｎ＝０，１，２，... ）と表記する。【００５６】
ここで，一番古い要求が保持されたエントリは，ｌｏａｄ−Ａが保持されたＦＰ−０であるので，ＦＴ−ＴＯＱ２３は，０を示している。【００５７】
一次キャッシュ制御部２０は，可能であればアウトオブオーダーで要求を処理する機能を持つ。これにより，例えば最も古い要求であるｌｏａｄ−Ａの処理より先に，ｌｏａｄ−Ｂの処理を行うために一次キャッシュＲＡＭ２１にアクセスしたとする。このとき，ｌｏａｄ−Ｂの対象データが一次キャッシュＲＡＭ２１に存在しなければ，二次キャッシュ制御部３０に対してデータ転送を要求する（図５（Ａ）参照）。このとき，ｌｏａｄ−Ｂが保持されているエントリＦＰ−１の要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）を１にセットする。【００５８】
その後，二次キャッシュ制御部３０からデータが転送され，一次キャッシュＲＡＭ２１のｗａｙ−０に登録される（図５（Ｂ）参照）。データ転送要求からデータが登録されるまでの間は，同一キャッシュインデックスの処理が一時期に一つずつしか実行できないため，ｌｏａｄ−Ａ，ｌｏａｄ−Ｃの処理はＦＰ２２で待機となる。【００５９】
ｌｏａｄ−Ｂに対するデータ登録が完了した後，ｌｏａｄ−Ａの処理やｌｏａｄ−Ｂの再処理より先に，ｌｏａｄ−Ｃの処理を行うために一次キャッシュＲＡＭ２１にアクセスしたとする。このとき，ｌｏａｄ−Ｃの対象データが一次キャッシュＲＡＭ２１に存在しなければ，二次キャッシュ制御部３０に対してデータ転送を要求する（図６（Ａ）参照）。このとき，ｌｏａｄ−Ｃが保持されているエントリＦＰ−２の要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）を１にセットする。【００６０】
その後，二次キャッシュ制御部３０からデータが転送され，一次キャッシュＲＡＭ２１のｗａｙ−１に登録される（図６（Ｂ）参照）。データ転送要求からデータが登録されるまでの間は，同一キャッシュインデックスの処理が一時期に一つずつしか実行できないため，ｌｏａｄ−Ａ，ｌｏａｄ−Ｂの処理はＦＰ２２で待機となる。【００６１】
ｌｏａｄ−Ｃに対するデータ登録が完了した後，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃの再処理より先に，ｌｏａｄ−Ａの処理を行うために一次キャッシュＲＡＭ２１にアクセスしたとする。このとき，ｌｏａｄ−Ａの対象データが一次キャッシュＲＡＭ２１に存在しないので，二次キャッシュ制御部３０に対してデータ転送を要求する（図７（Ａ）参照）。このとき，ｌｏａｄ−Ａが保持されているエントリＦＰ−０の要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）を１にセットする。【００６２】
同時に，ｗａｙ−０，ｗａｙ−１には共に有効なデータが存在するため，置換制御部２９により，ｗａｙ−０を置換対象とし，ｗａｙ−０にあるｌｏａｄ−Ｂの対象データを無効化（Ｉｎｖａｌｉｄ）する（図７（Ｂ）参照）。【００６３】
その後，二次キャッシュ制御部３０からデータが転送され，一次キャッシュＲＡＭ２１のｗａｙ−０に登録される（図８（Ａ）参照）。データ転送要求からデータが登録されるまでの間は，同一キャッシュインデックスの処理が一時期に一つずつしか実行できないため，ｌｏａｄ−Ｂ，ｌｏａｄ−Ｃの処理はＦＰ２２で待機となる。【００６４】
ｌｏａｄ−Ａに対するデータ登録が完了した後，ｌｏａｄ−Ａ，ｌｏａｄ−Ｃの再処理より先に，ｌｏａｄ−Ｂの処理を行うために一次キャッシュＲＡＭ２１にアクセスしたとする。このとき，以前にｗａｙ−０に登録されていたｌｏａｄ−Ｂの対象データはｌｏａｄ−Ａの対象データに置換されてしまっているため，ｌｏａｄ−Ｂの対象データは一次キャッシュＲＡＭ２１に存在しない。しかし，ｌｏａｄ−Ｂが保持されているエントリＦＰ−１の要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１であり，かつエントリＦＰ−１はＦＰ−ＴＯＱで示されたエントリではないため，データ転送要求を行わない（図８（Ｂ）参照）。【００６５】
続けて，ｌｏａｄ−Ａの再処理より先に，ｌｏａｄ−Ｃの処理を行うために一次キャッシュＲＡＭ２１にアクセスしたとする。このとき，ｌｏａｄ−Ｃの対象データは一次キャッシュＲＡＭ２１のｗａｙ−１に存在するため，該当データを命令制御部（演算制御部）１０に送り，エントリＦＰ−２の処理を完了する（図９（Ａ）参照）。【００６６】
続けて，ｌｏａｄ−Ａの処理を行うために一次キャッシュＲＡＭ２１にアクセスしたとする。このとき，ｌｏａｄ−Ａの対象データは一次キャッシュＲＡＭ２１のｗａｙ−０に存在するため，該当データを命令制御部（演算制御部）１０に送り，エントリＦＰ−０の処理を完了する（図９（Ｂ）参照）。このとき，ＦＰ−ＴＯＱ２３が示すエントリをエントリＦＰ−１に更新する。【００６７】
続けて，ｌｏａｄ−Ｂの処理を行うために一次キャッシュＲＡＭ２１にアクセスしたとする。このとき，以前にｗａｙ−０に登録されていたｌｏａｄ−Ｂの対象データはｌｏａｄ−Ａの対象データに置換されてしまっているため，ｌｏａｄ−Ｂの対象データは一次キャッシュＲＡＭ２１に存在しない。ｌｏａｄ−Ｂが保持されているエントリＦＰ−１の要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１であるが，エントリＦＰ−１はＦＰ−ＴＯＱで示されたエントリであるため，要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）を無視して二次キャッシュ制御部３０に対してデータ転送を要求する（図１０（Ａ）参照）。【００６８】
同時に，ｗａｙ−０，ｗａｙ−１には共に有効なデータが存在するため，置換制御部２９により，ｗａｙ−１を置換対象とし，ｗａｙ−１にあるｌｏａｄ−Ｃの対象データを無効化（Ｉｎｖａｌｉｄ）する（図１０（Ｂ）参照）。【００６９】
その後，二次キャッシュ制御部３０からデータが転送され，一次キャッシュＲＡＭ２１のｗａｙ−１に登録される（図１１（Ａ）参照）。【００７０】
ｌｏａｄ−Ｂの再処理を行うために一次キャッシュＲＡＭ２１にアクセスする。このとき，ｌｏａｄ−Ｂの対象データは一次キャッシュＲＡＭ２１のｗａｙ−１に存在するため，該当データを命令制御部（演算制御部）１０に送り，エントリＦＰ−１の処理を完了する（図１１（Ｂ）参照）。【００７１】
このように，ＦＰ２２の中でＦＰ−ＴＯＱ２３に示された一番古いエントリに保持された要求処理になるまで，同じ要求の対象データの転送要求を２回以上しないとすることで，参照するデータがキャッシュ上で置換され続けて命令が完了しないという状態を回避できる（図１２参照）。【００７２】
次に，ある同一キャッシュインデックスで複数の要求の対象となる異なるデータが示される場合に，複数の要求の対象となるデータで置換し合うことを回避した回数を計測する機構を設けた実施の形態を説明する。この機構は，性能評価やプログラムのチューニングなどに利用するためのものである。【００７３】
図１３は，本実施の形態による一次キャッシュ制御部の構成例を示す図である。一次キャッシュ制御部２０は，一次キャッシュＲＡＭ２１，ＦＰ（Fetch Port）２２，ＦＰ−ＴＯＱ（Fetch Port Top Of Queue ）２３，エントリ選択回路２４，データ転送要求抑止判定回路２５，キャッシュミス判定回路２６，データ転送要求制御回路２７，回数計測回路２８を備える。【００７４】
一次キャッシュＲＡＭ２１，ＦＰ（Fetch Port）２２，ＦＰ−ＴＯＱ（Fetch Port Top Of Queue ）２３，エントリ選択回路２４，データ転送要求抑止判定回路２５，キャッシュミス判定回路２６，データ転送要求制御回路２７については，図２で説明したものと同様であるため，説明を省略する。【００７５】
回数計測回路２８は，キャッシュミスの発生時に，処理を行う要求の対象となるデータの転送要求がすでに発行されていても，処理を行う要求が保持されたエントリがＦＰ−ＴＯＱ２３で示されたエントリであるために，データ転送の再要求が発行された回数をキャッシュインデックスごとに計測する。【００７６】
なお，この回数計測回路２８が保持する回数情報は，外部からのアクセス回路（図示省略）によって読み出すことができ，またリセットによる初期化もできるように構成されている。【００７７】
図１４は，本実施の形態によるデータ転送要求の処理フローチャートである。図１４のフローチャートでは，二次キャッシュ制御部３０に転送要求が発行されたときに，処理を行っている要求が保持されたエントリの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１（すなわち要求済み）であれば，処理を行っている要求が過去に一回データ転送要求が発行された要求であっても，ＦＰ−ＴＯＱ２３に示されたエントリに保持された要求であるためにデータ転送の再要求が行われたことを示すため，該当キャッシュインデックスのカウンタを加算する。【００７８】
図１４のフローチャートにおいて，ＦＰ−ｎ（ｎ＝０，１，２，... ）は，ＦＰ２２の各エントリを示し，ｎ（ｎ＝０，１，２，... ）は，便宜上エントリに割り当てられた番号を示す。また，要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）は，１が要求済みであることを示し，０が未要求であることを示すものとする。【００７９】
ＦＰ−ｎのエントリに保持された要求が処理を行う要求として選択されると（ステップＳ２０），その要求に示されたアドレスで一次キャッシュＲＡＭ２１にアクセスする（ステップＳ２１）。このとき，キャッシュミスが発生しなければ（ステップＳ２２），二次キャッシュ制御部３０へのデータ転送要求は発行しない。【００８０】
キャッシュミスが発生したときに（ステップＳ２２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号であれば（ステップＳ２３），二次キャッシュ制御部３０に該当データの転送要求を発行する（ステップＳ２５）。【００８１】
キャッシュミスが発生したときに（ステップＳ２２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号でなくても（ステップＳ２３），そのエントリの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が０（すなわち未要求）であれば（ステップＳ２４），二次キャッシュ制御部３０に該当データの転送要求を発行する（ステップＳ２５）。【００８２】
キャッシュミスが発生しても（ステップＳ２２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号でなく（ステップＳ２３），かつそのエントリの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１（すなわち要求済み）であれば（ステップＳ２４），二次キャッシュ制御部３０にデータ転送要求を発行しない。【００８３】
二次キャッシュ制御部３０に該当データの転送要求が発行されたときに（ステップＳ２５），エントリＦＰ−ｎの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１（すなわち要求済み）であれば（ステップＳ２６），該当キャッシュインデックスのカウンタを１加算する（ステップＳ２７）。エントリＦＰ−ｎの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が０（すなわち未要求）であれば（ステップＳ２６），そのエントリに保持された要求についての初めてのデータ転送要求であるため，該当キャッシュインデックスのカウンタを操作しない。【００８４】
図１５は，本実施の形態によるデータ転送要求の処理フローチャートである。図１５のフローチャートに示す処理では，ロード命令用のカウンタとストア命令用のカウンタとを別に用意し，処理を行っている要求がロード命令かストア命令かによって操作するカウンタを変更することで，置換原因となった命令種別を把握することが可能となる。【００８５】
図１５のフローチャートにおいて，ＦＰ−ｎ（ｎ＝０，１，２，... ）は，ＦＰ２２の各エントリを示し，ｎ（ｎ＝０，１，２，... ）は，便宜上エントリに割り当てられた番号をしめす。また，要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）は，１が要求済みであることを示し，０が未要求であることを示すものとする。【００８６】
ＦＰ−ｎのエントリに保持された要求が処理を行う要求として選択されると（ステップＳ３０），その要求に示されたアドレスで一次キャッシュＲＡＭ２１にアクセスする（ステップＳ３１）。このとき，キャッシュミスが発生しなければ（ステップＳ３２），二次キャッシュ制御部３０へのデータ転送要求は発行しない。【００８７】
キャッシュミスが発生したときに（ステップＳ３２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号であれば（ステップＳ３３），二次キャッシュ制御部３０に該当データの転送要求を発行する（ステップＳ３５）。【００８８】
キャッシュミスが発生したときに（ステップＳ３２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号でなくても（ステップＳ３３），そのエントリの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が０（すなわち未要求）であれば（ステップＳ３４），二次キャッシュ制御部３０に該当データの転送要求を発行する（ステップＳ３５）。【００８９】
キャッシュミスが発生しても（ステップＳ３２），ＦＰ−ＴＯＱ２３で示されたエントリの番号が処理を行う要求が保持されたエントリの番号でなく（ステップＳ３３），かつそのエントリの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１（すなわち要求済み）であれば（ステップＳ３４），二次キャッシュ制御部３０にデータ転送要求を発行しない。【００９０】
二次キャッシュ制御部３０に該当データの転送要求が発行されたときに（ステップＳ３５），エントリＦＰ−ｎの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１（すなわち要求済み）であり（ステップＳ３６），処理を行っている要求がロード命令であれば（ステップＳ３７），該当キャッシュインデックスのロード命令用カウンタを１加算する（ステップＳ３８）。【００９１】
二次キャッシュ制御部３０に該当データの転送要求が発行されたときに（ステップＳ３５），エントリＦＰ−ｎの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が１（すなわち要求済み）であり（ステップＳ３６），処理を行っている要求がロード命令でなければ（ステップＳ３７），すなわちストア命令であれば，該当キャッシュインデックスのストア命令用カウンタを１加算する（ステップＳ３９）。【００９２】
二次キャッシュ制御部３０に該当データの転送要求が発行されたときに（ステップＳ３５），エントリＦＰ−ｎの要求済みフラグ（ｒｅｑ−ｔａｋｅｎ）が０（すなわち未要求）であれば（ステップＳ３６），そのエントリに保持された要求についての初めてのデータ転送要求であるため，該当キャッシュインデックスのカウンタを操作しない。【００９３】
このように，ある同一キャッシュインデックスで複数の要求の対象となる異なるデータが示される場合に，複数の要求の対象となるデータで置換し合うことを回避した回数を計測し，これをプログラムのチューニングの参考情報として利用してプログラム設計を行うことができる。キャッシュインデックスをずらしたプログラムを設計することで，プログラムの性能向上を図ることが可能となる。【００９４】
以上，本実施の形態について説明したが，本発明はこれに限るものではない。例えば，本実施の形態では一次キャッシュ制御部２０から二次キャッシュ制御部３０へのデータ転送要求の制御についての例を説明したが，二次キャッシュを持たないプロセッサまたはシステムでも同様に本発明を実施することができ，キャッシュ制御部から他の記憶手段へのデータ転送要求の制御であれば，本実施の形態の適用が可能である。
【産業上の利用可能性】
【００９５】
本発明は，情報処理装置に用いられる技術に関するものであり，特にキャッシュを有する電算機において利用される技術である。
【図１】
2008155833.tif 000003
【図２】
2008155833.tif 000004
【図３】
2008155833.tif 000005
【図４】
2008155833.tif 000006
【図５】
2008155833.tif 000007
【図６】
2008155833.tif 000008
【図７】
2008155833.tif 000009
【図８】
2008155833.tif 000010
【図９】
2008155833.tif 000011
【図１０】
2008155833.tif 000012
【図１１】
2008155833.tif 000013
【図１２】
2008155833.tif 000014
【図１３】
2008155833.tif 000015
【図１４】
2008155833.tif 000016
【図１５】
2008155833.tif 000017
【図１６】
2008155833.tif 000018
【図１７】
2008155833.tif 000019
【図１８】
2008155833.tif 000020
【図１９】
2008155833.tif 000021
【図２０】
2008155833.tif 000022
【図２１】
2008155833.tif 000023
【図２２】
2008155833.tif 000024
【図２３】
2008155833.tif 000025
【図２４】
2008155833.tif 000026
【国際調査報告】
2008155833.tif 000027
2008155833.tif 000028