(57)【要約】  メモリアクセス制御装置５００は、複数の要求に係る情報を格納し、これらの要求を並列実行するためのＭＩＢ５３０バッファを有する。このメモリアクセス制御装置５００にメモリアクセス要求が行われた場合、ＭＩＢ５３０は、メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹをリプレイスＷＡＹ選択部５４０へ出力する。そして、リプレイスＷＡＹ選択部５４０は、ＭＩＢ５３０より出力されたＷＡＹを除外して、メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択する。
2007088591.tif 000002
【特許請求の範囲】
【請求項１】
複数の要求に係る情報を格納し、これらの要求を並列実行するためのバッファを有し、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置であって、
当該のメモリアクセス制御装置にメモリアクセス要求が行われた場合に、該メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹを出力する処理状況出力手段と、
前記処理状況出力手段により出力されたＷＡＹを除外して、前記メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択するリプレイスＷＡＹ選択手段と、
前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記リプレイスＷＡＹ選択手段により選択されたＷＡＹに前記データブロックが格納されるように制御する制御手段と
を備えたことを特徴とするメモリアクセス制御装置。
【請求項２】
前記リプレイスアルゴリズムは、ＬＲＵアルゴリズムであることを特徴とする請求項１に記載のメモリアクセス制御装置。
【請求項３】
前記制御手段は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記処理状況出力手段により出力されたＷＡＹが使用可能な全てのＷＡＹを含むならば、該メモリアクセス要求をリトライさせることを特徴とする請求項１に記載のメモリアクセス制御装置。
【請求項４】
前記制御手段は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットした場合に、ヒットしたＷＡＹが前記処理状況出力手段により出力されたＷＡＹに含まれるならば、該メモリアクセス要求をリトライさせることを特徴とする請求項１に記載のメモリアクセス制御装置。
【請求項５】
複数の要求に係る情報を格納し、これらの要求を並列実行するためのバッファを有し、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置におけるメモリアクセス制御方法であって、
当該のメモリアクセス制御装置にメモリアクセス要求が行われた場合に、該メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹを出力する処理状況出力工程と、
前記処理状況出力工程により出力されたＷＡＹを除外して、前記メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択するリプレイスＷＡＹ選択工程と、
前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記リプレイスＷＡＹ選択工程により選択されたＷＡＹに前記データブロックが格納されるように制御する制御工程と
を含んだことを特徴とするメモリアクセス制御方法。
【請求項６】
前記リプレイスアルゴリズムは、ＬＲＵアルゴリズムであることを特徴とする請求項５に記載のメモリアクセス制御方法。
【請求項７】
前記制御工程は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記処理状況出力工程により出力されたＷＡＹが使用可能な全てのＷＡＹを含むならば、該メモリアクセス要求をリトライさせることを特徴とする請求項５に記載のメモリアクセス制御方法。
【請求項８】
前記制御工程は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットした場合に、ヒットしたＷＡＹが前記処理状況出力工程により出力されたＷＡＹに含まれるならば、該メモリアクセス要求をリトライさせることを特徴とする請求項５に記載のメモリアクセス制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置およびメモリアクセス制御方法に関し、特に、予期しないタイミングでのキャッシュの消失を防止しつつ、リトライの発生を最小限に抑制し、キャッシュのヒット率を高く保つことができるメモリアクセス制御装置およびメモリアクセス制御方法に関する。
【背景技術】
【０００２】
メモリアクセス制御装置にて用いられるキャッシュ制御方式の一つにセットアソシアティブ方式がある。セットアソシアティブ方式は、データブロックのアドレスの一部をインデックスとしてセットを選択し、セットに含まれるＷＡＹのいずれかにデータブロックを格納する方式である。ＷＡＹは、セットごとに複数存在し、例えば、４ＷＡＹセットアソシアティブ方式の場合、セットごとに４つのＷＡＹが存在する。【０００３】
セットアソシアティブ方式では、全てのデータブロックをキャッシュに格納することができないため、メモリアクセス制御装置は、キャッシュの内容を適宜置き換えながら、アクセスされる可能性の高いデータブロックをキャッシュに保持する。キャッシュの内容を置き換えるためのアルゴリズムは、リプレイスアルゴリズムと呼ばれ、キャッシュのヒット率を高めるための非常に重要な要素となっている。【０００４】
ところで、ＣＰＵ（Central  Processing  Unit）からのロード／ストア要求は、キャッシュにヒットするか否かによって処理に要する時間が大きく異なる。ＣＰＵからの要求がキャッシュミスし、主記憶へのアクセスが必要になった場合、キャッシュにヒットした場合の１００倍以上の処理時間が必要となる。このように極端に処理時間の異なる処理を効率よく実行するため、メモリアクセス制御装置は、ムーブインバッファ（Move  In  Buffer、以下「ＭＩＢ」という）を備え、主記憶へのアクセスのような処理時間の長い処理の実行をここで管理する。【０００５】
ＭＩＢは、複数のエントリを有し、エントリごとに処理対象のデータブロックのアドレスやＷＡＹ等の情報を記憶する。そして、各エントリに記憶された情報に基づいて処理の実行と監視を行い、処理が完了するとその処理に対応するエントリを解放する。このように複数の要求の並列実行を可能にするＭＩＢを備えることにより、メモリアクセス制御装置は、主記憶へのアクセスのようなレイテンシの大きい処理の実行が完了することを待つことなく、他の処理を実行することができる。【０００６】
ただし、ＭＩＢを利用する場合、ＷＡＹの選択に注意が必要となる。例えば、セット１に対応するデータブロックＸを主記憶からロードする処理をＭＩＢにて行っており、このデータブロックＸは、ＷＡＹ０にキャッシュされることになっているものとする。ここで、セット１に対応するデータブロックＹをストアする別の処理においてＷＡＹ０がキャッシュ先として選択されると、データブロックＹをキャッシュに格納した直後にＭＩＢによるロード処理によってＷＡＹ０が上書きされ、データブロックＹがキャッシュから失われる可能性がある。【０００７】
この場合、ＷＡＹ０の上書きに先立って、データブロックＹは主記憶に書き出されるため、データそのものの消失は発生しないが、キャッシュの消失により、キャッシュのヒット率の低下を招くことになる。また、１次キャッシュ／２次キャッシュのように階層化されたキャッシュシステムの下位のキャッシュにてこのようなキャッシュの消失が発生すると、上位のキャッシュが保持するデータブロックは下位のキャッシュも必ず保持していなければならないという包含関係が崩れる恐れもある。【０００８】
そこで、従来のメモリアクセス制御装置においては、ＭＩＢにて処理中のデータブロックと同一セットのデータブロックに対するロード／ストア要求があった場合、要求をリトライさせ、ＭＩＢの処理が完了するまで要求の実行を遅延させることよってキャッシュの消失を回避する方式がとられていた。また、この方式に代えて、特許文献１に記載されているように、ＭＩＢにて同一セットかつ同一ＷＡＹのデータブロックの処理が行われている場合は、その件数分だけずらしてＷＡＹを選択する方式を用いることも可能である。【０００９】
【特許文献１】特開２００１−５１８９９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、要求の実行を遅延させる従来の方式は、実装が容易である反面、同一セットに使用可能なＷＡＹが存在する場合でも要求がリトライされてしまい、性能の低下を招くという問題がある。また、特許文献１に記載された方式も、リプレイスアルゴリズムによって選択されたＷＡＹとは別のＷＡＹを選択することになるため、キャッシュのヒット率の低下を招くという問題がある。【００１１】
本発明は、上記に鑑みてなされたものであって、ＭＩＢの動作による予期しないタイミングでのキャッシュの消失を防止しつつ、リトライの発生を最小限に抑制し、キャッシュのヒット率を高く保つことができるメモリアクセス制御装置およびメモリアクセス制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するために、本発明は、複数の要求に係る情報を格納し、これらの要求を並列実行するためのバッファを有し、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置であって、当該のメモリアクセス制御装置にメモリアクセス要求が行われた場合に、該メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹを出力する処理状況出力手段と、前記処理状況出力手段により出力されたＷＡＹを除外して、前記メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択するリプレイスＷＡＹ選択手段と、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記リプレイスＷＡＹ選択手段により選択されたＷＡＹに前記データブロックが格納されるように制御する制御手段とを備えたことを特徴とする。【００１３】
また、本発明は、複数の要求に係る情報を格納し、これらの要求を並列実行するためのバッファを有し、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置におけるメモリアクセス制御方法であって、当該のメモリアクセス制御装置にメモリアクセス要求が行われた場合に、該メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹを出力する処理状況出力工程と、前記処理状況出力工程により出力されたＷＡＹを除外して、前記メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択するリプレイスＷＡＹ選択工程と、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記リプレイスＷＡＹ選択工程により選択されたＷＡＹに前記データブロックが格納されるように制御する制御工程とを含んだことを特徴とする。【００１４】
これらの発明によれば、先行して実行されている要求に割り当てられているＷＡＹを除外して、新規の要求に割り当てるＷＡＹをリプレイスアルゴリズムに基づいて選択するように構成したので、キャッシュが予期しないタイミングで消失することを防止しつつ、キャッシュのヒット率を高く保つことができる。【００１５】
また、本発明は、上記の発明において、前記リプレイスアルゴリズムは、ＬＲＵ（Least  Recently  Used）アルゴリズムであることを特徴とする。【００１６】
この発明によれば、リプレイスアルゴリズムとしてＬＲＵアルゴリズムを利用するように構成したので、キャッシュのヒット率を高めることができる。【００１７】
また、本発明は、上記の発明において、前記制御手段は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記処理状況出力手段により出力されたＷＡＹが使用可能な全てのＷＡＹを含むならば、該メモリアクセス要求をリトライさせることを特徴とする。【００１８】
また、本発明は、上記の発明において、前記制御工程は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記処理状況出力工程により出力されたＷＡＹが使用可能な全てのＷＡＹを含むならば、該メモリアクセス要求をリトライさせることを特徴とする。【００１９】
これらの発明によれば、要求の処理対象のデータブロックがキャッシュにヒットしなかった場合、全てのＷＡＹが使用不可能なときのみ要求をリトライさせるように構成したので、リトライによる性能の低下を最小限に抑えることができる。【００２０】
また、本発明は、上記の発明において、前記制御手段は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットした場合に、ヒットしたＷＡＹが前記処理状況出力手段により出力されたＷＡＹに含まれるならば、該メモリアクセス要求をリトライさせることを特徴とする。【００２１】
また、本発明は、上記の発明において、前記制御工程は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットした場合に、ヒットしたＷＡＹが前記処理状況出力工程により出力されたＷＡＹに含まれるならば、該メモリアクセス要求をリトライさせることを特徴とする。【００２２】
これらの発明によれば、要求の処理対象のデータブロックがキャッシュにヒットした場合、ヒットしたＷＡＹが先行して実行されている要求に割り当てられているＷＡＹに含まれるときは要求をリトライさせるように構成したので、キャッシュが予期しないタイミングで消失することを防止することができる。
【発明の効果】
【００２３】
本発明によれば、先行して実行されている要求に割り当てられているＷＡＹを除外して、新規の要求に割り当てるＷＡＹをリプレイスアルゴリズムに基づいて選択するように構成したので、キャッシュが予期しないタイミングで消失することを防止しつつ、キャッシュのヒット率を高く保つことができるという効果を奏する。【００２４】
また、本発明によれば、リプレイスアルゴリズムとしてＬＲＵアルゴリズムを利用するように構成したので、キャッシュのヒット率を高めることができるという効果を奏する。【００２５】
また、本発明によれば、要求の処理対象のデータブロックがキャッシュにヒットしなかった場合、全てのＷＡＹが使用不可能なときのみ要求をリトライさせるように構成したので、リトライによる性能の低下を最小限に抑えることができるという効果を奏する。【００２６】
また、本発明によれば、要求の処理対象のデータブロックがキャッシュにヒットした場合、ヒットしたＷＡＹが先行して実行されている要求に割り当てられているＷＡＹに含まれるときは要求をリトライさせるように構成したので、キャッシュが予期しないタイミングで消失することを防止することができるという効果を奏する。
【図面の簡単な説明】
【００２７】
【図１】図１は、本実施例に係るメモリアクセス制御装置の構成を示す機能ブロック図である。
【図２】図２は、ＭＩＢの構成を示す機能ブロック図である。
【図３】図３は、リプレイスＷＡＹ選択部の構成を示す機能ブロック図である。
【図４】図４は、ＷＡＹ選択部の構成の一例を示す回路概略図である。
【図５】図５は、ＷＡＹ使用判定部の構成の一例を示す回路概略図である。
【図６】図６は、図１に示したメモリアクセス制御装置の処理手順を示すフローチャートである。
【図７】図７は、従来のメモリアクセス制御装置の構成を示す機能ブロック図である。
【図８】図８は、ヒット判定部の構成を示す機能ブロック図である。
【図９】図９は、ＭＩＢの構成を示す機能ブロック図である。
【図１０】図１０は、リプレイスＷＡＹ選択部の構成を示す機能ブロック図である。
【図１１】図１１は、図７に示したメモリアクセス制御装置の処理手順を示すフローチャートである。
【符号の説明】
【００２８】
１１〜１３  ＯＲ回路
１４  ＡＮＤ回路
２１、２２  ＡＮＤ回路
２３    ＯＲ回路
１００    ＣＰＵ
２００〜２０３  メモリアクセス制御装置
２１０    ポート
２２０    ヒット判定部
２２１    タグメモリ
２２２    タグ比較部
２３０    ＭＩＢ
２３１ａ  レジスタ
２３１ｂ  インデックス比較部
２３２    処理状況出力部
２４０    リプレイスＷＡＹ選択部
２４１    ＬＲＵ−ＲＡＭ
２４２    ＷＡＹ選択部
２５０    制御部
３００    キャッシュメモリ
４００    主記憶
５００〜５０３  メモリアクセス制御装置
５１０    ポート
５２０    ヒット判定部
５３０    ＭＩＢ
５３１ａ  レジスタ
５３１ｂ  インデックス比較部
５３１ｃ  デコーダ
５３１ｄ  処理対象ＷＡＹ出力部
５３２    処理状況出力部
５４０    リプレイスＷＡＹ選択部
５４１    ＬＲＵ−ＲＡＭ
５４２    ＷＡＹ選択部
５４３    ＷＡＹ使用判定部
５５０    制御部
【発明を実施するための最良の形態】
【００２９】
以下に、本発明にかかるメモリアクセス制御装置およびメモリアクセス制御方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００３０】
まず、ＭＩＢの処理が完了するまで要求の実行を遅延させる従来のメモリアクセス制御方式について説明する。図７は、従来のメモリアクセス制御装置の構成を示す機能ブロック図である。同図に示すように、メモリアクセス制御装置２００は、ＣＰＵ１００、キャッシュメモリ３００および主記憶４００と接続された構成をとる。【００３１】
ＣＰＵ１００は、各種処理を実行する演算装置であり、主記憶４００に対するデータのロード／ストア要求をメモリアクセス制御装置２００に対して発行し、その結果を受信する。なお、キャッシュが階層化されている場合は、ＣＰＵ１００とメモリアクセス制御装置２００の間に他のメモリアクセス制御装置が介在する場合もある。【００３２】
キャッシュメモリ３００は、高速なアクセスが可能なＳＲＡＭ（Static  Random  Access  Memory）等のメモリであり、主記憶４００のデータの一部のコピーを保持することによってデータアクセスの速度を向上させる。キャッシュメモリ３００へのデータの格納は、データブロック単位で行われ、データブロックの格納位置は、セットとＷＡＹの組合せによって特定される。主記憶４００は、ＣＰＵ１００が各種処理を実行するために必要なプログラムやデータが展開されるメモリである。【００３３】
メモリアクセス制御装置２００は、ＣＰＵ１００のロード／ストア要求を効率よく実行することができるようにキャッシュメモリ３００および主記憶４００へのアクセスを制御する装置である。メモリアクセス制御装置２００は、キャッシュの制御にセットアソシアティブ方式を用いる。【００３４】
また、プロセッサごとにキャッシュを備えるマルチプロセッサシステムの場合、メモリアクセス制御装置２００は、メモリアクセス制御装置２０１〜メモリアクセス制御装置２０３等の他のメモリアクセス制御装置とも接続される。【００３５】
図７に示すように、メモリアクセス制御装置２００は、ポート２１０と、ヒット判定部２２０と、ＭＩＢ２３０と、リプレイスＷＡＹ選択部２４０と、制御部２５０とを有する。以下、新たな要求にＷＡＹを割り当てるまでの処理に注目して、各処理部の詳細を説明する。【００３６】
ポート２１０は、ＣＰＵ１００から送られた要求を一時的に保持する装置である。ここに保持された要求は、所定の優先順位で読み出されて制御部２５０に送信される。そして、これと同時に、読み出された要求の処理対象のデータブロックのアドレス（以下「要求アドレス」という）がヒット判定部２２０、ＭＩＢ２３０およびリプレイスＷＡＹ選択部２４０に送信される。【００３７】
ヒット判定部２２０は、ポート２１０から送信された要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されているか否かを判定する処理部である。ヒット判定部２２０の構成を図８に示す。同図に示すように、ヒット判定部２２０は、タグメモリ２２１と、タグ比較部２２２とを有し、ポート２１０から要求アドレスが送信されると、そのインデックスをタグメモリ２２１に入力し、そのタグをタグ比較部２２２に入力する。【００３８】
ここで、要求アドレスについて説明しておく。要求アドレスは、タグとインデックスとオフセットに分かれる。オフセットは、要求アドレスの下位ビットであり、データブロック内の位置を指定するための部分である。タグとインデックスは、データブロックを識別する部分であり、このうちのインデックスの部分を使用してデータブロックをキャッシュのどのセットに格納するかが決定される。【００３９】
タグメモリ２２１は、キャッシュメモリ３００に格納されているデータブロックに関する管理情報を記憶する装置である。ここでいう管理情報とは、具体的には、データブロックのアドレスのタグと、更新が行われているか否かといったステートと、各種制御フラグ等である。管理情報は、対応するデータブロックがキャッシュメモリ３００に格納されている位置と同じ位置に格納される。すなわち、あるデータブロックがキャッシュメモリ３００のセット１のＷＡＹ０に格納されている場合、その管理情報はタグメモリ２２１のセット１のＷＡＹ０に格納される。【００４０】
タグメモリ２２１は、要求アドレスのインデックスが入力されると、そのインデックスに対応するセットを選択し、選択したセットに含まれる各ＷＡＹの管理情報をタグ比較部２２２へ送信する。【００４１】
タグ比較部２２２は、要求アドレスのタグが入力されると、入力されたタグとタグメモリ２２１から送信された管理情報とを比較して、要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されているか否かを判定する。具体的には、タグメモリ２２１から送信された管理情報に入力されたタグと同一のタグを有する情報があれば、その管理情報に対応するＷＡＹにデータブロックがキャッシュされていると判定する。【００４２】
そして、タグ比較部２２２は、要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されていると判定した場合は、ＨＩＴ信号をＯＮにし、さらにデータブロックが格納されているＷＡＹに対応するＨＩＴ−ＷＡＹ信号をＯＮにする。一方、要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されていないと判定した場合は、ＭＩＳＳ信号をＯＮにする。これらの信号は、制御部２５０に出力される。【００４３】
ＭＩＢ２３０は、主記憶４００との間でのデータブロックの転送処理のような時間のかかる処理の実行を管理する処理部である。ＭＩＢ２３０の構成を図９に示す。同図に示すように、ＭＩＢ２３０は、ＭＩＢ０〜ＭＩＢｍの複数のエントリと、処理状況出力部２３２とを有し、ポート２１０から要求アドレスが送信されると、そのインデックスを各エントリに入力する。【００４４】
各エントリは、レジスタ２３１ａと、インデックス比較部２３１ｂとを備え、自身に割り振られた処理の実行を管理する。レジスタ２３１ａは、割り振られた処理に関する情報を記憶する装置であり、当該のエントリに処理が割り振られているか否かを示すＶビットと、割り振られた処理の要求アドレスを示すタグ、インデックスおよびオフセットと、処理に割り当てられたＷＡＹと、各種制御フラグ等を記憶する。【００４５】
インデックス比較部２３１ｂは、要求アドレスのインデックスが入力されると、当該のエントリのレジスタ２３１ａのＶビットとインデックスを取得し、Ｖビットが立っており、かつ、入力されたインデックスと取得したインデックスが一致した場合に出力する信号をＯＮにする。【００４６】
そして、処理状況出力部２３２は、こうして各エントリのインデックス比較部２３１ｂから出力された信号の論理和をとってＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号として出力する。すなわち、ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号は、要求アドレスと同一のインデックスを有するデータブロックがＭＩＢ２３０にて処理対象となっている場合にＯＮとなる。この信号は、制御部２５０に出力される。【００４７】
リプレイスＷＡＹ選択部２４０は、ポート２１０から送信された要求アドレスに対応するデータブロックを格納すべきＷＡＹを選択する処理部である。リプレイスＷＡＹ選択部２４０の構成を図１０に示す。同図に示すように、リプレイスＷＡＹ選択部２４０は、ＬＲＵ−ＲＡＭ２４１と、ＷＡＹ選択部２４２とを有し、ポート２１０から要求アドレスが送信されると、そのインデックスをＬＲＵ−ＲＡＭ２４１に入力する。【００４８】
ＬＲＵ−ＲＡＭ２４１は、キャッシュメモリ３００が最後にアクセスされた時間をセットごとかつＷＡＹごとに記憶する装置である。そして、ＬＲＵ−ＲＡＭ２４１は、要求アドレスのインデックスが入力されると、そのインデックスに対応するセットを選択し、選択したセットに含まれる各ＷＡＹが最後にアクセスされた時間をＷＡＹ選択部２４２へ出力する。【００４９】
ＷＡＹ選択部２４２は、各ＷＡＹが最後にアクセスされた時間が入力されると、アクセスされた時間が最も古いＷＡＹを選択し、そのＷＡＹに対応するＲＰＬ−ＷＡＹ信号をＯＮにする。このとき、ＷＡＹ選択部２４２は、入力される縮退情報を参照し、固定故障等により使用不可とされているＷＡＹを選択対象から除外する。ＲＰＬ−ＷＡＹ信号は、制御部２５０に出力される。【００５０】
制御部２５０は、ポート２１０から送信された要求に対応する各種制御を実行する制御部である。制御部２５０は、ポート２１０から要求を受信すると共に、上述の処理の結果としてヒット判定部２２０、ＭＩＢ２３０およびリプレイスＷＡＹ選択部２４０から出力される各種信号の入力も受ける。そして、これらの信号の状態に応じて、要求への対処を変更する。【００５１】
具体的には、ＭＩＢ２３０から入力されたＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号がＯＮの場合は、要求をポート２１０に差し戻してリトライさせる。ＭＩＢ２３０にて要求アドレスと同一インデックスのデータブロックの処理が行われている場合、ポート２１０から送信された要求によりキャッシュメモリ３００に格納されたデータブロックが予期しないタイミングで上書きされて、キャッシュから消失してしまう可能性があるためである。【００５２】
ＭＩＢ２３０から入力されたＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号がＯＦＦの場合、制御部２５０は、要求の処理対象のデータブロックを格納するためのＷＡＹを選択し、選択したＷＡＹを要求に割り当てて要求内容に応じた処理を実行する。【００５３】
具体的には、ヒット判定部２２０から入力されたＨＩＴ信号がＯＮの場合は、ヒット判定部２２０から入力されたＨＩＴ−ＷＡＹ信号が示すＷＡＹ、すなわち、要求アドレスがタグメモリ２２１にヒットしたＷＡＹ（以下「ヒットＷＡＹ」という）を要求に割り当てて処理を実行する。【００５４】
また、ヒット判定部２２０から入力されたＭＩＳＳ信号がＯＮの場合は、リプレイスＷＡＹ選択部２４０から入力されたＲＰＬ−ＷＡＹ信号が示すＷＡＹ、すなわち、リプレイスアルゴリズムによって書き換えに最も適していると判定されたＷＡＹ（以下「リプレイスＷＡＹ」という）を要求に割り当てて処理を実行する。【００５５】
次に、図７に示したメモリアクセス制御装置２００の処理手順について説明する。図１１は、図７に示したメモリアクセス制御装置２００の処理手順を示すフローチャートである。同図は、制御部２５０が要求を受信した後、使用するＷＡＹを選択するまでの処理手順を示している。【００５６】
ポート２１０から送信された要求は、制御部２５０に受信される（ステップＳ１０１）。これと平行して、ポート２１０から送信された要求アドレスは、ヒット判定部２２０と、ＭＩＢ２３０と、リプレイスＷＡＹ選択部２４０とに受信される。【００５７】
要求アドレスを受信したヒット判定部２２０は、タグメモリ２２１を検索し、要求アドレスに対応するデータブロックがキャッシュに存在するか否かを調べ、その結果を制御部２５０へ出力する（ステップＳ１０２）。要求アドレスを受信したＭＩＢ２３０は、要求アドレスと同一のインデックスを有するデータブロックを処理対象とする処理が実行中であるか否かを調べ、その結果を制御部２５０へ出力する（ステップＳ１０３）。【００５８】
また、要求アドレスを受信したリプレイスＷＡＹ選択部２４０は、要求アドレスに対応するセットに属するＷＡＹの中で最も置き換えに適しているＷＡＹをリプレイスアルゴリズムに基づいて選択し、その結果を制御部２５０へ出力する（ステップＳ１０４）。【００５９】
そして、制御部２５０は、ＭＩＢ２３０からの入力により、要求アドレスと同一のインデックスを有するデータブロックを処理対象とする処理がＭＩＢ２３０にて実行中であることが分かった場合は（ステップＳ１０５肯定）、要求をポート２１０へ差し戻してリトライさせる。【００６０】
一方、要求アドレスと同一のインデックスを有するデータブロックを処理対象とする処理がＭＩＢ２３０にて実行中でないことが分かった場合は（ステップＳ１０５否定）、要求内容に応じた処理を実行する。【００６１】
このとき、タグメモリ２２１の検索により、要求アドレスに対応するデータブロックがキャッシュされていることが判明した場合は（ステップＳ１０６肯定）、ヒット判定部２２０から入力されたヒットＷＡＹをキャッシュの格納場所として要求に割り当てる（ステップＳ１０７）。また、要求アドレスに対応するデータブロックがキャッシュされていないことが判明した場合は（ステップＳ１０６否定）、リプレイスＷＡＹ選択部２４０から入力されたリプレイスＷＡＹをキャッシュの格納場所として要求に割り当てる（ステップＳ１０８）。【００６２】
このように、従来のメモリアクセス制御方式では、ＭＩＢ２３０による上書きによってキャッシュメモリ３００に格納されたデータブロックが予期しないタイミングで消失することを回避するため、要求アドレスと同一のインデックスのデータブロックを処理対象とする処理がＭＩＢ２３０にて実行中の場合は要求をリトライさせている。【００６３】
しかし、要求アドレスと同一のインデックスのデータブロックを処理対象とする処理がＭＩＢ２３０にて実行中であっても、この処理に割り当てられているＷＡＹと異なるＷＡＹを新たな要求に割り当てれば予期しないキャッシュの消失が発生することはない。すなわち、従来のメモリアクセス制御方式では、必要以上に要求のリトライが行われており、その分だけ性能の低下が生じている。【００６４】
次に、本実施例に係るメモリアクセス制御装置について説明する。図１は、本実施例に係るメモリアクセス制御装置の構成を示す機能ブロック図である。同図に示すように、メモリアクセス制御装置５００は、ＣＰＵ１００、キャッシュメモリ３００および主記憶４００と接続された構成をとる。ＣＰＵ１００、キャッシュメモリ３００および主記憶４００については、既に説明済みであるので、ここでは説明を省略する。【００６５】
メモリアクセス制御装置５００は、ＣＰＵ１００のロード／ストア要求を効率よく実行することができるようにキャッシュメモリ３００および主記憶４００へのアクセスを制御する装置である。メモリアクセス制御装置５００は、キャッシュの制御にセットアソシアティブ方式を用いる。なお、メモリアクセス制御装置５００は、ＣＰＵ１００、キャッシュメモリ３００もしくは主記憶４００と一体の装置として構成することもできる。【００６６】
また、プロセッサごとにキャッシュを備えるマルチプロセッサシステムの場合、メモリアクセス制御装置５００は、メモリアクセス制御装置５０１〜メモリアクセス制御装置５０３等の他のメモリアクセス制御装置とも接続される。【００６７】
図１に示すように、メモリアクセス制御装置５００は、ポート５１０と、ヒット判定部５２０と、ＭＩＢ５３０と、リプレイスＷＡＹ選択部５４０と、制御部５５０とを有する。以下、新たな要求にＷＡＹを割り当てるまでの処理に注目して、各処理部の詳細を説明する。【００６８】
ポート５１０は、ＣＰＵ１００から送られた要求を一時的に保持する装置である。ここに保持された要求は、所定の優先順位で読み出されて制御部５５０に送信される。そして、これと同時に、要求アドレスがヒット判定部５２０、ＭＩＢ５３０およびリプレイスＷＡＹ選択部５４０に送信される。【００６９】
ヒット判定部５２０は、ポート５１０から送信された要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されているか否かを判定する処理部である。ヒット判定部５２０の構成は、図８に示したヒット判定部２２０の構成と同様であるが、ＨＩＴ−ＷＡＹ信号を制御部５５０のみでなく、リプレイスＷＡＹ選択部５４０へも出力する。【００７０】
ＭＩＢ５３０は、主記憶４００との間でのデータブロックの転送処理のような時間のかかる処理の実行を管理する処理部である。ＭＩＢ５３０の構成を図２に示す。同図に示すように、ＭＩＢ５３０は、ＭＩＢ０〜ＭＩＢｍの複数のエントリと、処理状況出力部５３２とを有し、ポート５１０から要求アドレスが送信されると、そのインデックスを各エントリに入力する。【００７１】
各エントリは、レジスタ５３１ａと、インデックス比較部５３１ｂと、デコーダ５３１ｃと、処理対象ＷＡＹ出力部５３１ｄとを備える。レジスタ５３１ａおよびインデックス比較部５３１ｂは、それぞれ、図９に示したレジスタ２３１ａおよびインデックス比較部２３１ｂと同様の装置である。【００７２】
デコーダ５３１ｃは、レジスタ５３１ａに設定されているＷＡＹに対応する信号をＯＮにして処理対象ＷＡＹ出力部５３１ｄに出力する回路である。処理対象ＷＡＹ出力部５３１ｄは、インデックス比較部５３１ｂから出力された信号がＯＮである場合に、デコーダ５３１ｃから出力された信号を処理状況出力部５３２へ転送する処理部である。【００７３】
処理状況出力部５３２は、各エントリのインデックス比較部５３１ｂから出力された信号の論理和をとってＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号として出力する処理部である。また、処理状況出力部５３２は、各エントリの処理対象ＷＡＹ出力部５３１ｄから転送された信号の論理和をＷＡＹごとにとってＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ＿ＷＡＹ信号として出力する。【００７４】
すなわち、ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号は、要求アドレスと同一のインデックスを有するデータブロックを処理対象とする処理がＭＩＢ５３０にて実行中である場合にＯＮとなる。また、ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ＿ＷＡＹ信号は、要求アドレスと同一のインデックスを有するデータブロックを処理対象とする処理がＭＩＢ５３０にて実行中である場合に、処理に割り当てられているＷＡＹに対応する信号がＯＮになる。ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号は、制御部５５０に出力され、ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ＿ＷＡＹ信号は、リプレイスＷＡＹ選択部５４０に出力される。【００７５】
リプレイスＷＡＹ選択部５４０は、ポート５１０から送信された要求アドレスに対応するデータブロックを格納すべきＷＡＹを選択する処理部である。リプレイスＷＡＹ選択部５４０の構成を図３に示す。同図に示すように、リプレイスＷＡＹ選択部５４０は、ＬＲＵ−ＲＡＭ５４１と、ＷＡＹ選択部５４２と、ＷＡＹ使用判定部５４３とを有し、ポート５１０から要求アドレスが送信されると、そのインデックスをＬＲＵ−ＲＡＭ５４１に入力する。【００７６】
ＬＲＵ−ＲＡＭ５４１は、図１０に示したＬＲＵ−ＲＡＭ２４１と同様の装置であり、要求アドレスのインデックスが入力されると、そのインデックスに対応するセットを選択し、選択したセットに含まれる各ＷＡＹが最後にアクセスされた時間をＷＡＹ選択部５４２へ出力する。【００７７】
ＷＡＹ選択部５４２は、各ＷＡＹが最後にアクセスされた時間が入力されると、アクセスされた時間が最も古いＷＡＹを選択し、そのＷＡＹに対応するＲＰＬ−ＷＡＹ信号をＯＮにする。このとき、ＷＡＹ選択部５４２は、入力された縮退情報とＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ＿ＷＡＹ信号の論理和をＷＡＹごとにとったＤＩＳＡＢＬＥ＿ＷＡＹ信号を参照し、固定故障等により使用不可とされているＷＡＹとＭＩＢ５３０にて実行中の処理に割り当てられているＷＡＹを選択対象から除外する。ＲＰＬ−ＷＡＹ信号は、制御部５５０に出力される。【００７８】
上記のように最後にアクセスされてから最も時間が経過しているＷＡＹをリプレイスＷＡＹとして選択するリプレイスアルゴリズムをＬＲＵアルゴリズムといい、非常に高いキャッシュのヒット率を実現することができる。上記のリプレイスＷＡＹ選択部５４０の構成によれば、ＭＩＢ５３０にて実行中の処理に割り当てられているＷＡＹを除外してＬＲＵアルゴリズムに基づいてリプレイスＷＡＹの選択を行っているので、予期しないキャッシュの消失の回避をキャッシュのヒット率を高く保ったまま実現することができる。【００７９】
また、上記のリプレイスＷＡＹ選択部５４０の構成によれば、従来より固定故障等により縮退されたＷＡＹを除外していた仕組みを拡張することによって、ＭＩＢ５３０にて実行中の処理に割り当てられているＷＡＹを除外する機能を容易に実現することができる。【００８０】
なお、キャッシュメモリ３００が最後にアクセスされた時間をＬＲＵ−ＲＡＭ５４１にて記憶するのではなく、ヒット判定部５２０のタグメモリにて記憶するように構成することもできる。また、リプレイスアルゴリズムとして、ＬＲＵアルゴリズムに代えて他のアルゴリズムを採用することもできる。【００８１】
ＷＡＹ選択部５４２の構成の一例を図４に示す。同図は、ＷＡＹ選択部５４２においてＷＡＹ０がリプレイスＷＡＹとなるか否かを判定する部分の回路概略図である。【００８２】
ＯＲ回路１１の出力は、ＷＡＹ１が選択対象外であるか、ＷＡＹ１の最終アクセス時間がＷＡＹ０の最終アクセス時間よりも新しい場合、すなわち、ＷＡＹ１がリプレイスＷＡＹとして適していない場合にＯＮとなる。同様に、ＯＲ回路１２の出力は、ＷＡＹ２がリプレイスＷＡＹとして適していない場合にＯＮとなり、ＯＲ回路１３の出力は、ＷＡＹ３がリプレイスＷＡＹとして適していない場合にＯＮとなる。【００８３】
そして、ＡＮＤ回路１４の出力は、ＯＲ回路１１〜１３の出力が全てＯＮであり、ＷＡＹ０が選択対象外でない場合にＯＮとなる。ＷＡＹ選択部５４２には、これと同様の回路がＷＡＹ数分だけ存在する。【００８４】
ＷＡＹ使用判定部５４３は、ＷＡＹが使用可能であるか否かを判定する処理部である。ＷＡＹ使用判定部５４３は、ＤＩＳＡＢＬＥ＿ＷＡＹ信号を参照し、全てのＷＡＹが選択対象外である場合には、選択可能なリプレイスＷＡＹが存在しないことを示すＲＰＬ−ＷＡＹ＿ＮＯＴ＿ＦＯＵＮＤ信号をＯＮにする。【００８５】
また、ヒット判定部５２０から入力されたＨＩＴ−ＷＡＹ信号と、ＤＩＳＡＢＬＥ＿ＷＡＹ信号を照合し、ＨＩＴ−ＷＡＹ信号に対応するＷＡＹが選択対象外である場合には、ＨＩＴ＿ＷＡＹ＿ＩＮ＿ＵＳＥ信号をＯＮにする。【００８６】
要求アドレスがヒット判定部５２０にていずれかのＷＡＹにヒットした場合、単にキャッシュメモリ３００上のデータブロックの読み書きを行うだけであれば、既に割り当てられている領域の操作を行うに過ぎないので、ＭＩＢ５３０で進行中の処理を考慮せずに要求を実行することもできる。【００８７】
しかしながら、要求を実行するために、ＭＩＢ５３０のエントリを取得する必要がある場合には、新たにＭＩＢ５３０のエントリに登録する処理に割り当てるＷＡＹが、既にＭＩＢ５３０のエントリに登録済みの処理に割り当てられているＷＡＹと重複していると、先に完了した処理のキャッシュが後に完了した処理によって予期しないタイミングで上書きされ、キャッシュが消失する可能性がある。【００８８】
ＨＩＴ＿ＷＡＹ＿ＩＮ＿ＵＳＥ信号は、かかるキャッシュの消失を回避するために制御部５５０によって使用される。要求アドレスがヒット判定部５２０にていずれかのＷＡＹにヒットした場合にＭＩＢ５３０のエントリを取得することが必要になるのは、例えば、プロセッサごとにキャッシュを備えるマルチプロセッサシステムにおいて他のキャッシュのデータブロックを無効化する必要が生じた場合等である。【００８９】
ＷＡＹ使用判定部５４３の構成の一例を図５に示す。ＡＮＤ回路２１の出力は、ＲＰＬ−ＷＡＹ＿ＮＯＴ＿ＦＯＵＮＤ信号であり、全てのＷＡＹが選択対象外である場合にＯＮとなる。ＡＮＤ回路２２は、要求アドレスがヒット判定部５２０にていずれかのＷＡＹにヒットし、そのＷＡＹが選択対象外である場合に、そのＷＡＹに対応する出力をＯＮにする。ＯＲ回路２３の出力は、ＨＩＴ＿ＷＡＹ＿ＩＮ＿ＵＳＥ信号であり、ＡＮＤ回路２２が出力するいずれかの信号がＯＮの場合にＯＮとなる。【００９０】
制御部５５０は、ポート５１０から送信された要求に対応する各種制御を実行する制御部である。制御部５５０は、ポート５１０から要求を受信すると共に、上述の処理の結果としてヒット判定部５２０、ＭＩＢ５３０およびリプレイスＷＡＹ選択部５４０から出力される各種信号の入力も受ける。そして、これらの信号の状態に応じて、要求への対処を変更する。【００９１】
具体的には、ヒット判定部５２０から入力されたＭＩＳＳ信号がＯＮの場合、すなわち、要求アドレスがキャッシュにヒットしなかった場合は、リプレイスＷＡＹ選択部５４０から入力されたＲＰＬ−ＷＡＹ＿ＮＯＴ＿ＦＯＵＮＤ信号がＯＮであれば、全てのＷＡＹが選択対象外であるため、要求をポート５１０に差し戻してリトライさせる。ＲＰＬ−ＷＡＹ＿ＮＯＴ＿ＦＯＵＮＤ信号がＯＦＦであれば、リプレイスＷＡＹ選択部５４０から入力されたＲＰＬ−ＷＡＹ信号が示すリプレイスＷＡＹを要求に割り当てて処理を実行する。【００９２】
また、ヒット判定部５２０から入力されたＨＩＴ信号がＯＮの場合、すなわち、要求アドレスがキャッシュにヒットした場合は、ＭＩＢ５３０のエントリの取得が必要であり、かつ、リプレイスＷＡＹ選択部５４０から入力されたＨＩＴ−ＷＡＹ＿ＩＮ＿ＵＳＥ信号がＯＮであれば、キャッシュの消失を回避するため、要求をポート５１０に差し戻してリトライさせる。ＭＩＢ５３０のエントリの取得が不要であるか、ＨＩＴ−ＷＡＹ＿ＩＮ＿ＵＳＥ信号がＯＦＦであれば、ヒット判定部５２０から入力されたＨＩＴ−ＷＡＹ信号が示すヒットＷＡＹを使用して処理を実行する。【００９３】
なお、ＨＩＴ−ＷＡＹ＿ＩＮ＿ＵＳＥ信号がＯＮの場合は、キャッシュが短時間で消失する可能性があり、これによりキャッシュのヒット率を低下する恐れがあるので、ＭＩＢ５３０のエントリの取得が必要であるか否かにかかわらず要求をリトライさせることとしてもよい。【００９４】
次に、図１に示したメモリアクセス制御装置５００の処理手順について説明する。図６は、図１に示したメモリアクセス制御装置５００の処理手順を示すフローチャートである。同図は、制御部５５０が要求を受信した後、使用するＷＡＹを選択するまでの処理手順を示している。【００９５】
ポート５１０から送信された要求は、制御部５５０に受信される（ステップＳ２０１）。これと平行して、ポート５１０から送信された要求アドレスは、ヒット判定部５２０と、ＭＩＢ５３０と、リプレイスＷＡＹ選択部５４０とに受信される。【００９６】
要求アドレスを受信したヒット判定部５２０は、タグメモリを検索し、要求アドレスと同一のデータブロックが存在するか否かを調べ、その結果を制御部５５０とリプレイスＷＡＹ選択部５４０へ出力する（ステップＳ２０２）。要求アドレスを受信したＭＩＢ５３０は、要求アドレスと同一のインデックスを有するデータブロックを処理中のエントリの処理対象ＷＡＹを取得し、取得結果をリプレイスＷＡＹ選択部５４０へ出力する（ステップＳ２０３）。【００９７】
そして、要求アドレスを受信したリプレイスＷＡＹ選択部５４０は、ＭＩＢ５３０から通知された処理対象ＷＡＹを除外して、要求アドレスに対応するセットに属するＷＡＹの中で最も置き換えに適しているＷＡＹをリプレイスアルゴリズムによって選択し、その結果を制御部５５０へ出力する（ステップＳ２０４）。また、ヒット判定部５２０から通知されたヒットＷＡＹが処理対象ＷＡＹに含まれるか否かを調べて、その結果も制御部５５０へ出力する（ステップＳ２０５）。【００９８】
そして、制御部５５０は、要求アドレスがヒット判定部５２０のタグメモリにヒットした場合は（ステップＳ２０６肯定）、ＭＩＢ５３０のエントリの取得が必要であり（ステップＳ２０７肯定）、ヒットＷＡＹが処理対象ＷＡＹに含まれていれば（ステップＳ２０８肯定）、要求をポート５１０へ差し戻してリトライさせる。ＭＩＢ５３０のエントリの取得が必要ないか（ステップＳ２０７否定）、ヒットＷＡＹが処理対象ＷＡＹに含まれていなければ（ステップＳ２０８否定）、ヒット判定部５２０から入力されたヒットＷＡＹをキャッシュの格納場所として処理を実行する（ステップＳ２０９）。【００９９】
また、要求アドレスがヒット判定部５２０のタグメモリにヒットしなかった場合は（ステップＳ２０６否定）、全てのＷＡＹがＭＩＢ５３０の処理対象ＷＡＹとなっていれば（ステップＳ２１０肯定）、要求をポート５１０へ差し戻してリトライさせる。さもなければ（ステップＳ２１０否定）、リプレイスＷＡＹ選択部５４０から入力されたリプレイスＷＡＹをキャッシュの格納場所として処理を実行する（ステップＳ２１１）。【０１００】
このように、本実施例にかかるメモリアクセス制御方式では、ＭＩＢ５３０で進行中の処理で使用対象となっているＷＡＹを除外してリプレイスＷＡＹを選択し、全てのＷＡＹが使用対象となっている場合にのみ要求をリトライさせるように構成したので、リトライによる性能の低下を最小限に抑えることができる。また、リプレイスＷＡＹの選択が、常にリプレイスアルゴリズムに基づいて行われるように構成したので、キャッシュのヒット率を高く保つことができる。
【産業上の利用可能性】
【０１０１】
以上のように、本発明にかかるメモリアクセス制御装置およびメモリアクセス制御方法は、ＭＩＢの動作による予期しないタイミングでのキャッシュの防止に有用であり、特に、リトライの発生を最小限に抑制し、キャッシュのヒット率を高く保つことが必要な場合に適している。
【図１】
2007088591.tif 000003
【図２】
2007088591.tif 000004
【図３】
2007088591.tif 000005
【図４】
2007088591.tif 000006
【図５】
2007088591.tif 000007
【図６】
2007088591.tif 000008
【図７】
2007088591.tif 000009
【図８】
2007088591.tif 000010
【図９】
2007088591.tif 000011
【図１０】
2007088591.tif 000012
【図１１】
2007088591.tif 000013
【手続補正書】
【提出日】平成21年1月13日(2009.1.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の要求に係る情報を格納し、これらの要求を並列実行するためのバッファを有し、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置であって、
当該のメモリアクセス制御装置にメモリアクセス要求が行われた場合に、該メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹを出力する処理状況出力手段と、
前記処理状況出力手段により出力されたＷＡＹを除外して、前記メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択するリプレイスＷＡＹ選択手段と、
前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記リプレイスＷＡＹ選択手段により選択されたＷＡＹに前記データブロックが格納されるように制御する制御手段と
を備え、
前記制御手段は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットした場合に、ヒットしたＷＡＹが前記処理状況出力手段により出力されたＷＡＹに含まれるならば（ただし、前記処理状況出力手段によって選択された要求のうち、前記ヒットしたＷＡＹを割り当てられている要求の対象であるデータブロックと、前記メモリアクセス要求の処理対象であるデータブロックとが同一である場合を除く）、該メモリアクセス要求をリトライさせることを特徴とするメモリアクセス制御装置。
【請求項２】
前記リプレイスアルゴリズムは、ＬＲＵアルゴリズムであることを特徴とする請求項１に記載のメモリアクセス制御装置。
【請求項３】
前記制御手段は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記処理状況出力手段により出力されたＷＡＹが使用可能な全てのＷＡＹを含むならば、該メモリアクセス要求をリトライさせることを特徴とする請求項１に記載のメモリアクセス制御装置。
【請求項４】
複数の要求に係る情報を格納し、これらの要求を並列実行するためのバッファを有し、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置におけるメモリアクセス制御方法であって、
当該のメモリアクセス制御装置にメモリアクセス要求が行われた場合に、該メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹを出力する処理状況出力工程と、
前記処理状況出力工程により出力されたＷＡＹを除外して、前記メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択するリプレイスＷＡＹ選択工程と、
前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記リプレイスＷＡＹ選択工程により選択されたＷＡＹに前記データブロックが格納されるように制御する制御工程と
を含み、
前記制御工程は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットした場合に、ヒットしたＷＡＹが前記処理状況出力工程により出力されたＷＡＹに含まれるならば（ただし、前記処理状況出力工程によって選択された要求のうち、前記ヒットしたＷＡＹを割り当てられている要求の対象であるデータブロックと、前記メモリアクセス要求の処理対象であるデータブロックとが同一である場合を除く）、該メモリアクセス要求をリトライさせることを特徴とするメモリアクセス制御方法。
【請求項５】
前記リプレイスアルゴリズムは、ＬＲＵアルゴリズムであることを特徴とする請求項４に記載のメモリアクセス制御方法。
【請求項６】
前記制御工程は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記処理状況出力工程により出力されたＷＡＹが使用可能な全てのＷＡＹを含むならば、該メモリアクセス要求をリトライさせることを特徴とする請求項４に記載のメモリアクセス制御方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置およびメモリアクセス制御方法に関し、特に、予期しないタイミングでのキャッシュの消失を防止しつつ、リトライの発生を最小限に抑制し、キャッシュのヒット率を高く保つことができるメモリアクセス制御装置およびメモリアクセス制御方法に関する。
【背景技術】
【０００２】
メモリアクセス制御装置にて用いられるキャッシュ制御方式の一つにセットアソシアティブ方式がある。セットアソシアティブ方式は、データブロックのアドレスの一部をインデックスとしてセットを選択し、セットに含まれるＷＡＹのいずれかにデータブロックを格納する方式である。ＷＡＹは、セットごとに複数存在し、例えば、４ＷＡＹセットアソシアティブ方式の場合、セットごとに４つのＷＡＹが存在する。
【０００３】
セットアソシアティブ方式では、全てのデータブロックをキャッシュに格納することができないため、メモリアクセス制御装置は、キャッシュの内容を適宜置き換えながら、アクセスされる可能性の高いデータブロックをキャッシュに保持する。キャッシュの内容を置き換えるためのアルゴリズムは、リプレイスアルゴリズムと呼ばれ、キャッシュのヒット率を高めるための非常に重要な要素となっている。
【０００４】
ところで、ＣＰＵ（Central  Processing  Unit）からのロード／ストア要求は、キャッシュにヒットするか否かによって処理に要する時間が大きく異なる。ＣＰＵからの要求がキャッシュミスし、主記憶へのアクセスが必要になった場合、キャッシュにヒットした場合の１００倍以上の処理時間が必要となる。このように極端に処理時間の異なる処理を効率よく実行するため、メモリアクセス制御装置は、ムーブインバッファ（Move  In  Buffer、以下「ＭＩＢ」という）を備え、主記憶へのアクセスのような処理時間の長い処理の実行をここで管理する。
【０００５】
ＭＩＢは、複数のエントリを有し、エントリごとに処理対象のデータブロックのアドレスやＷＡＹ等の情報を記憶する。そして、各エントリに記憶された情報に基づいて処理の実行と監視を行い、処理が完了するとその処理に対応するエントリを解放する。このように複数の要求の並列実行を可能にするＭＩＢを備えることにより、メモリアクセス制御装置は、主記憶へのアクセスのようなレイテンシの大きい処理の実行が完了することを待つことなく、他の処理を実行することができる。
【０００６】
ただし、ＭＩＢを利用する場合、ＷＡＹの選択に注意が必要となる。例えば、セット１に対応するデータブロックＸを主記憶からロードする処理をＭＩＢにて行っており、このデータブロックＸは、ＷＡＹ０にキャッシュされることになっているものとする。ここで、セット１に対応するデータブロックＹをストアする別の処理においてＷＡＹ０がキャッシュ先として選択されると、データブロックＹをキャッシュに格納した直後にＭＩＢによるロード処理によってＷＡＹ０が上書きされ、データブロックＹがキャッシュから失われる可能性がある。
【０００７】
この場合、ＷＡＹ０の上書きに先立って、データブロックＹは主記憶に書き出されるため、データそのものの消失は発生しないが、キャッシュの消失により、キャッシュのヒット率の低下を招くことになる。また、１次キャッシュ／２次キャッシュのように階層化されたキャッシュシステムの下位のキャッシュにてこのようなキャッシュの消失が発生すると、上位のキャッシュが保持するデータブロックは下位のキャッシュも必ず保持していなければならないという包含関係が崩れる恐れもある。
【０００８】
そこで、従来のメモリアクセス制御装置においては、ＭＩＢにて処理中のデータブロックと同一セットのデータブロックに対するロード／ストア要求があった場合、要求をリトライさせ、ＭＩＢの処理が完了するまで要求の実行を遅延させることよってキャッシュの消失を回避する方式がとられていた。また、この方式に代えて、特許文献１に記載されているように、ＭＩＢにて同一セットかつ同一ＷＡＹのデータブロックの処理が行われている場合は、その件数分だけずらしてＷＡＹを選択する方式を用いることも可能である。
【０００９】
【特許文献１】特開２００１−５１８９９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、要求の実行を遅延させる従来の方式は、実装が容易である反面、同一セットに使用可能なＷＡＹが存在する場合でも要求がリトライされてしまい、性能の低下を招くという問題がある。また、特許文献１に記載された方式も、リプレイスアルゴリズムによって選択されたＷＡＹとは別のＷＡＹを選択することになるため、キャッシュのヒット率の低下を招くという問題がある。
【００１１】
本発明は、上記に鑑みてなされたものであって、ＭＩＢの動作による予期しないタイミングでのキャッシュの消失を防止しつつ、リトライの発生を最小限に抑制し、キャッシュのヒット率を高く保つことができるメモリアクセス制御装置およびメモリアクセス制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するために、本発明は、複数の要求に係る情報を格納し、これらの要求を並列実行するためのバッファを有し、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置であって、当該のメモリアクセス制御装置にメモリアクセス要求が行われた場合に、該メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹを出力する処理状況出力手段と、前記処理状況出力手段により出力されたＷＡＹを除外して、前記メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択するリプレイスＷＡＹ選択手段と、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記リプレイスＷＡＹ選択手段により選択されたＷＡＹに前記データブロックが格納されるように制御する制御手段とを備えたことを特徴とする。
【００１３】
また、本発明は、複数の要求に係る情報を格納し、これらの要求を並列実行するためのバッファを有し、セットアソシアティブ方式でキャッシュ制御を行うメモリアクセス制御装置におけるメモリアクセス制御方法であって、当該のメモリアクセス制御装置にメモリアクセス要求が行われた場合に、該メモリアクセス要求の処理対象のデータブロックと同一セットのデータブロックを処理対象とする要求を前記バッファより選択し、選択された要求に割り当てられているＷＡＹを出力する処理状況出力工程と、前記処理状況出力工程により出力されたＷＡＹを除外して、前記メモリアクセス要求に割り当てるＷＡＹを所定のリプレイスアルゴリズムに基づいて選択するリプレイスＷＡＹ選択工程と、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記リプレイスＷＡＹ選択工程により選択されたＷＡＹに前記データブロックが格納されるように制御する制御工程とを含んだことを特徴とする。
【００１４】
これらの発明によれば、先行して実行されている要求に割り当てられているＷＡＹを除外して、新規の要求に割り当てるＷＡＹをリプレイスアルゴリズムに基づいて選択するように構成したので、キャッシュが予期しないタイミングで消失することを防止しつつ、キャッシュのヒット率を高く保つことができる。
【００１５】
また、本発明は、上記の発明において、前記リプレイスアルゴリズムは、ＬＲＵ（Least  Recently  Used）アルゴリズムであることを特徴とする。
【００１６】
この発明によれば、リプレイスアルゴリズムとしてＬＲＵアルゴリズムを利用するように構成したので、キャッシュのヒット率を高めることができる。
【００１７】
また、本発明は、上記の発明において、前記制御手段は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記処理状況出力手段により出力されたＷＡＹが使用可能な全てのＷＡＹを含むならば、該メモリアクセス要求をリトライさせることを特徴とする。
【００１８】
また、本発明は、上記の発明において、前記制御工程は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットしなかった場合に、前記処理状況出力工程により出力されたＷＡＹが使用可能な全てのＷＡＹを含むならば、該メモリアクセス要求をリトライさせることを特徴とする。
【００１９】
これらの発明によれば、要求の処理対象のデータブロックがキャッシュにヒットしなかった場合、全てのＷＡＹが使用不可能なときのみ要求をリトライさせるように構成したので、リトライによる性能の低下を最小限に抑えることができる。
【００２０】
また、本発明は、上記の発明において、前記制御手段は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットした場合に、ヒットしたＷＡＹが前記処理状況出力手段により出力されたＷＡＹに含まれるならば、該メモリアクセス要求をリトライさせることを特徴とする。
【００２１】
また、本発明は、上記の発明において、前記制御工程は、前記メモリアクセス要求の処理対象のデータブロックがキャッシュにヒットした場合に、ヒットしたＷＡＹが前記処理状況出力工程により出力されたＷＡＹに含まれるならば、該メモリアクセス要求をリトライさせることを特徴とする。
【００２２】
これらの発明によれば、要求の処理対象のデータブロックがキャッシュにヒットした場合、ヒットしたＷＡＹが先行して実行されている要求に割り当てられているＷＡＹに含まれるときは要求をリトライさせるように構成したので、キャッシュが予期しないタイミングで消失することを防止することができる。
【発明の効果】
【００２３】
本発明によれば、先行して実行されている要求に割り当てられているＷＡＹを除外して、新規の要求に割り当てるＷＡＹをリプレイスアルゴリズムに基づいて選択するように構成したので、キャッシュが予期しないタイミングで消失することを防止しつつ、キャッシュのヒット率を高く保つことができるという効果を奏する。
【００２４】
また、本発明によれば、リプレイスアルゴリズムとしてＬＲＵアルゴリズムを利用するように構成したので、キャッシュのヒット率を高めることができるという効果を奏する。
【００２５】
また、本発明によれば、要求の処理対象のデータブロックがキャッシュにヒットしなかった場合、全てのＷＡＹが使用不可能なときのみ要求をリトライさせるように構成したので、リトライによる性能の低下を最小限に抑えることができるという効果を奏する。
【００２６】
また、本発明によれば、要求の処理対象のデータブロックがキャッシュにヒットした場合、ヒットしたＷＡＹが先行して実行されている要求に割り当てられているＷＡＹに含まれるときは要求をリトライさせるように構成したので、キャッシュが予期しないタイミングで消失することを防止することができるという効果を奏する。
【発明を実施するための最良の形態】
【００２７】
以下に、本発明にかかるメモリアクセス制御装置およびメモリアクセス制御方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００２８】
まず、ＭＩＢの処理が完了するまで要求の実行を遅延させる従来のメモリアクセス制御方式について説明する。図７は、従来のメモリアクセス制御装置の構成を示す機能ブロック図である。同図に示すように、メモリアクセス制御装置２００は、ＣＰＵ１００、キャッシュメモリ３００および主記憶４００と接続された構成をとる。
【００２９】
ＣＰＵ１００は、各種処理を実行する演算装置であり、主記憶４００に対するデータのロード／ストア要求をメモリアクセス制御装置２００に対して発行し、その結果を受信する。なお、キャッシュが階層化されている場合は、ＣＰＵ１００とメモリアクセス制御装置２００の間に他のメモリアクセス制御装置が介在する場合もある。
【００３０】
キャッシュメモリ３００は、高速なアクセスが可能なＳＲＡＭ（Static  Random  Access  Memory）等のメモリであり、主記憶４００のデータの一部のコピーを保持することによってデータアクセスの速度を向上させる。キャッシュメモリ３００へのデータの格納は、データブロック単位で行われ、データブロックの格納位置は、セットとＷＡＹの組合せによって特定される。主記憶４００は、ＣＰＵ１００が各種処理を実行するために必要なプログラムやデータが展開されるメモリである。
【００３１】
メモリアクセス制御装置２００は、ＣＰＵ１００のロード／ストア要求を効率よく実行することができるようにキャッシュメモリ３００および主記憶４００へのアクセスを制御する装置である。メモリアクセス制御装置２００は、キャッシュの制御にセットアソシアティブ方式を用いる。
【００３２】
また、プロセッサごとにキャッシュを備えるマルチプロセッサシステムの場合、メモリアクセス制御装置２００は、メモリアクセス制御装置２０１〜メモリアクセス制御装置２０３等の他のメモリアクセス制御装置とも接続される。
【００３３】
図７に示すように、メモリアクセス制御装置２００は、ポート２１０と、ヒット判定部２２０と、ＭＩＢ２３０と、リプレイスＷＡＹ選択部２４０と、制御部２５０とを有する。以下、新たな要求にＷＡＹを割り当てるまでの処理に注目して、各処理部の詳細を説明する。
【００３４】
ポート２１０は、ＣＰＵ１００から送られた要求を一時的に保持する装置である。ここに保持された要求は、所定の優先順位で読み出されて制御部２５０に送信される。そして、これと同時に、読み出された要求の処理対象のデータブロックのアドレス（以下「要求アドレス」という）がヒット判定部２２０、ＭＩＢ２３０およびリプレイスＷＡＹ選択部２４０に送信される。
【００３５】
ヒット判定部２２０は、ポート２１０から送信された要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されているか否かを判定する処理部である。ヒット判定部２２０の構成を図８に示す。同図に示すように、ヒット判定部２２０は、タグメモリ２２１と、タグ比較部２２２とを有し、ポート２１０から要求アドレスが送信されると、そのインデックスをタグメモリ２２１に入力し、そのタグをタグ比較部２２２に入力する。
【００３６】
ここで、要求アドレスについて説明しておく。要求アドレスは、タグとインデックスとオフセットに分かれる。オフセットは、要求アドレスの下位ビットであり、データブロック内の位置を指定するための部分である。タグとインデックスは、データブロックを識別する部分であり、このうちのインデックスの部分を使用してデータブロックをキャッシュのどのセットに格納するかが決定される。
【００３７】
タグメモリ２２１は、キャッシュメモリ３００に格納されているデータブロックに関する管理情報を記憶する装置である。ここでいう管理情報とは、具体的には、データブロックのアドレスのタグと、更新が行われているか否かといったステートと、各種制御フラグ等である。管理情報は、対応するデータブロックがキャッシュメモリ３００に格納されている位置と同じ位置に格納される。すなわち、あるデータブロックがキャッシュメモリ３００のセット１のＷＡＹ０に格納されている場合、その管理情報はタグメモリ２２１のセット１のＷＡＹ０に格納される。
【００３８】
タグメモリ２２１は、要求アドレスのインデックスが入力されると、そのインデックスに対応するセットを選択し、選択したセットに含まれる各ＷＡＹの管理情報をタグ比較部２２２へ送信する。
【００３９】
タグ比較部２２２は、要求アドレスのタグが入力されると、入力されたタグとタグメモリ２２１から送信された管理情報とを比較して、要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されているか否かを判定する。具体的には、タグメモリ２２１から送信された管理情報に入力されたタグと同一のタグを有する情報があれば、その管理情報に対応するＷＡＹにデータブロックがキャッシュされていると判定する。
【００４０】
そして、タグ比較部２２２は、要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されていると判定した場合は、ＨＩＴ信号をＯＮにし、さらにデータブロックが格納されているＷＡＹに対応するＨＩＴ−ＷＡＹ信号をＯＮにする。一方、要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されていないと判定した場合は、ＭＩＳＳ信号をＯＮにする。これらの信号は、制御部２５０に出力される。
【００４１】
ＭＩＢ２３０は、主記憶４００との間でのデータブロックの転送処理のような時間のかかる処理の実行を管理する処理部である。ＭＩＢ２３０の構成を図９に示す。同図に示すように、ＭＩＢ２３０は、ＭＩＢ０〜ＭＩＢｍの複数のエントリと、処理状況出力部２３２とを有し、ポート２１０から要求アドレスが送信されると、そのインデックスを各エントリに入力する。
【００４２】
各エントリは、レジスタ２３１ａと、インデックス比較部２３１ｂとを備え、自身に割り振られた処理の実行を管理する。レジスタ２３１ａは、割り振られた処理に関する情報を記憶する装置であり、当該のエントリに処理が割り振られているか否かを示すＶビットと、割り振られた処理の要求アドレスを示すタグ、インデックスおよびオフセットと、処理に割り当てられたＷＡＹと、各種制御フラグ等を記憶する。
【００４３】
インデックス比較部２３１ｂは、要求アドレスのインデックスが入力されると、当該のエントリのレジスタ２３１ａのＶビットとインデックスを取得し、Ｖビットが立っており、かつ、入力されたインデックスと取得したインデックスが一致した場合に出力する信号をＯＮにする。
【００４４】
そして、処理状況出力部２３２は、こうして各エントリのインデックス比較部２３１ｂから出力された信号の論理和をとってＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号として出力する。すなわち、ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号は、要求アドレスと同一のインデックスを有するデータブロックがＭＩＢ２３０にて処理対象となっている場合にＯＮとなる。この信号は、制御部２５０に出力される。
【００４５】
リプレイスＷＡＹ選択部２４０は、ポート２１０から送信された要求アドレスに対応するデータブロックを格納すべきＷＡＹを選択する処理部である。リプレイスＷＡＹ選択部２４０の構成を図１０に示す。同図に示すように、リプレイスＷＡＹ選択部２４０は、ＬＲＵ−ＲＡＭ２４１と、ＷＡＹ選択部２４２とを有し、ポート２１０から要求アドレスが送信されると、そのインデックスをＬＲＵ−ＲＡＭ２４１に入力する。
【００４６】
ＬＲＵ−ＲＡＭ２４１は、キャッシュメモリ３００が最後にアクセスされた時間をセットごとかつＷＡＹごとに記憶する装置である。そして、ＬＲＵ−ＲＡＭ２４１は、要求アドレスのインデックスが入力されると、そのインデックスに対応するセットを選択し、選択したセットに含まれる各ＷＡＹが最後にアクセスされた時間をＷＡＹ選択部２４２へ出力する。
【００４７】
ＷＡＹ選択部２４２は、各ＷＡＹが最後にアクセスされた時間が入力されると、アクセスされた時間が最も古いＷＡＹを選択し、そのＷＡＹに対応するＲＰＬ−ＷＡＹ信号をＯＮにする。このとき、ＷＡＹ選択部２４２は、入力される縮退情報を参照し、固定故障等により使用不可とされているＷＡＹを選択対象から除外する。ＲＰＬ−ＷＡＹ信号は、制御部２５０に出力される。
【００４８】
制御部２５０は、ポート２１０から送信された要求に対応する各種制御を実行する制御部である。制御部２５０は、ポート２１０から要求を受信すると共に、上述の処理の結果としてヒット判定部２２０、ＭＩＢ２３０およびリプレイスＷＡＹ選択部２４０から出力される各種信号の入力も受ける。そして、これらの信号の状態に応じて、要求への対処を変更する。
【００４９】
具体的には、ＭＩＢ２３０から入力されたＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号がＯＮの場合は、要求をポート２１０に差し戻してリトライさせる。ＭＩＢ２３０にて要求アドレスと同一インデックスのデータブロックの処理が行われている場合、ポート２１０から送信された要求によりキャッシュメモリ３００に格納されたデータブロックが予期しないタイミングで上書きされて、キャッシュから消失してしまう可能性があるためである。
【００５０】
ＭＩＢ２３０から入力されたＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号がＯＦＦの場合、制御部２５０は、要求の処理対象のデータブロックを格納するためのＷＡＹを選択し、選択したＷＡＹを要求に割り当てて要求内容に応じた処理を実行する。
【００５１】
具体的には、ヒット判定部２２０から入力されたＨＩＴ信号がＯＮの場合は、ヒット判定部２２０から入力されたＨＩＴ−ＷＡＹ信号が示すＷＡＹ、すなわち、要求アドレスがタグメモリ２２１にヒットしたＷＡＹ（以下「ヒットＷＡＹ」という）を要求に割り当てて処理を実行する。
【００５２】
また、ヒット判定部２２０から入力されたＭＩＳＳ信号がＯＮの場合は、リプレイスＷＡＹ選択部２４０から入力されたＲＰＬ−ＷＡＹ信号が示すＷＡＹ、すなわち、リプレイスアルゴリズムによって書き換えに最も適していると判定されたＷＡＹ（以下「リプレイスＷＡＹ」という）を要求に割り当てて処理を実行する。
【００５３】
次に、図７に示したメモリアクセス制御装置２００の処理手順について説明する。図１１は、図７に示したメモリアクセス制御装置２００の処理手順を示すフローチャートである。同図は、制御部２５０が要求を受信した後、使用するＷＡＹを選択するまでの処理手順を示している。
【００５４】
ポート２１０から送信された要求は、制御部２５０に受信される（ステップＳ１０１）。これと平行して、ポート２１０から送信された要求アドレスは、ヒット判定部２２０と、ＭＩＢ２３０と、リプレイスＷＡＹ選択部２４０とに受信される。
【００５５】
要求アドレスを受信したヒット判定部２２０は、タグメモリ２２１を検索し、要求アドレスに対応するデータブロックがキャッシュに存在するか否かを調べ、その結果を制御部２５０へ出力する（ステップＳ１０２）。要求アドレスを受信したＭＩＢ２３０は、要求アドレスと同一のインデックスを有するデータブロックを処理対象とする処理が実行中であるか否かを調べ、その結果を制御部２５０へ出力する（ステップＳ１０３）。
【００５６】
また、要求アドレスを受信したリプレイスＷＡＹ選択部２４０は、要求アドレスに対応するセットに属するＷＡＹの中で最も置き換えに適しているＷＡＹをリプレイスアルゴリズムに基づいて選択し、その結果を制御部２５０へ出力する（ステップＳ１０４）。
【００５７】
そして、制御部２５０は、ＭＩＢ２３０からの入力により、要求アドレスと同一のインデックスを有するデータブロックを処理対象とする処理がＭＩＢ２３０にて実行中であることが分かった場合は（ステップＳ１０５肯定）、要求をポート２１０へ差し戻してリトライさせる。
【００５８】
一方、要求アドレスと同一のインデックスを有するデータブロックを処理対象とする処理がＭＩＢ２３０にて実行中でないことが分かった場合は（ステップＳ１０５否定）、要求内容に応じた処理を実行する。
【００５９】
このとき、タグメモリ２２１の検索により、要求アドレスに対応するデータブロックがキャッシュされていることが判明した場合は（ステップＳ１０６肯定）、ヒット判定部２２０から入力されたヒットＷＡＹをキャッシュの格納場所として要求に割り当てる（ステップＳ１０７）。また、要求アドレスに対応するデータブロックがキャッシュされていないことが判明した場合は（ステップＳ１０６否定）、リプレイスＷＡＹ選択部２４０から入力されたリプレイスＷＡＹをキャッシュの格納場所として要求に割り当てる（ステップＳ１０８）。
【００６０】
このように、従来のメモリアクセス制御方式では、ＭＩＢ２３０による上書きによってキャッシュメモリ３００に格納されたデータブロックが予期しないタイミングで消失することを回避するため、要求アドレスと同一のインデックスのデータブロックを処理対象とする処理がＭＩＢ２３０にて実行中の場合は要求をリトライさせている。
【００６１】
しかし、要求アドレスと同一のインデックスのデータブロックを処理対象とする処理がＭＩＢ２３０にて実行中であっても、この処理に割り当てられているＷＡＹと異なるＷＡＹを新たな要求に割り当てれば予期しないキャッシュの消失が発生することはない。すなわち、従来のメモリアクセス制御方式では、必要以上に要求のリトライが行われており、その分だけ性能の低下が生じている。
【００６２】
次に、本実施例に係るメモリアクセス制御装置について説明する。図１は、本実施例に係るメモリアクセス制御装置の構成を示す機能ブロック図である。同図に示すように、メモリアクセス制御装置５００は、ＣＰＵ１００、キャッシュメモリ３００および主記憶４００と接続された構成をとる。ＣＰＵ１００、キャッシュメモリ３００および主記憶４００については、既に説明済みであるので、ここでは説明を省略する。
【００６３】
メモリアクセス制御装置５００は、ＣＰＵ１００のロード／ストア要求を効率よく実行することができるようにキャッシュメモリ３００および主記憶４００へのアクセスを制御する装置である。メモリアクセス制御装置５００は、キャッシュの制御にセットアソシアティブ方式を用いる。なお、メモリアクセス制御装置５００は、ＣＰＵ１００、キャッシュメモリ３００もしくは主記憶４００と一体の装置として構成することもできる。
【００６４】
また、プロセッサごとにキャッシュを備えるマルチプロセッサシステムの場合、メモリアクセス制御装置５００は、メモリアクセス制御装置５０１〜メモリアクセス制御装置５０３等の他のメモリアクセス制御装置とも接続される。
【００６５】
図１に示すように、メモリアクセス制御装置５００は、ポート５１０と、ヒット判定部５２０と、ＭＩＢ５３０と、リプレイスＷＡＹ選択部５４０と、制御部５５０とを有する。以下、新たな要求にＷＡＹを割り当てるまでの処理に注目して、各処理部の詳細を説明する。
【００６６】
ポート５１０は、ＣＰＵ１００から送られた要求を一時的に保持する装置である。ここに保持された要求は、所定の優先順位で読み出されて制御部５５０に送信される。そして、これと同時に、要求アドレスがヒット判定部５２０、ＭＩＢ５３０およびリプレイスＷＡＹ選択部５４０に送信される。
【００６７】
ヒット判定部５２０は、ポート５１０から送信された要求アドレスに対応するデータブロックがキャッシュメモリ３００に格納されているか否かを判定する処理部である。ヒット判定部５２０の構成は、図８に示したヒット判定部２２０の構成と同様であるが、ＨＩＴ−ＷＡＹ信号を制御部５５０のみでなく、リプレイスＷＡＹ選択部５４０へも出力する。
【００６８】
ＭＩＢ５３０は、主記憶４００との間でのデータブロックの転送処理のような時間のかかる処理の実行を管理する処理部である。ＭＩＢ５３０の構成を図２に示す。同図に示すように、ＭＩＢ５３０は、ＭＩＢ０〜ＭＩＢｍの複数のエントリと、処理状況出力部５３２とを有し、ポート５１０から要求アドレスが送信されると、そのインデックスを各エントリに入力する。
【００６９】
各エントリは、レジスタ５３１ａと、インデックス比較部５３１ｂと、デコーダ５３１ｃと、処理対象ＷＡＹ出力部５３１ｄとを備える。レジスタ５３１ａおよびインデックス比較部５３１ｂは、それぞれ、図９に示したレジスタ２３１ａおよびインデックス比較部２３１ｂと同様の装置である。
【００７０】
デコーダ５３１ｃは、レジスタ５３１ａに設定されているＷＡＹに対応する信号をＯＮにして処理対象ＷＡＹ出力部５３１ｄに出力する回路である。処理対象ＷＡＹ出力部５３１ｄは、インデックス比較部５３１ｂから出力された信号がＯＮである場合に、デコーダ５３１ｃから出力された信号を処理状況出力部５３２へ転送する処理部である。
【００７１】
処理状況出力部５３２は、各エントリのインデックス比較部５３１ｂから出力された信号の論理和をとってＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号として出力する処理部である。また、処理状況出力部５３２は、各エントリの処理対象ＷＡＹ出力部５３１ｄから転送された信号の論理和をＷＡＹごとにとってＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ＿ＷＡＹ信号として出力する。
【００７２】
すなわち、ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ信号は、要求アドレスと同一のインデックスを
有するデータブロックを処理対象とする処理がＭＩＢ５３０にて実行中である場合にＯＮ
となる。また、ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ＿ＷＡＹ信号は、要求アドレスと同一のイン
デックスを有するデータブロックを処理対象とする処理がＭＩＢ５３０にて実行中である
場合に、処理に割り当てられているＷＡＹに対応する信号がＯＮになる。ＭＩＢ＿ＩＮＤ
ＥＸ＿ＭＣＨ信号は、制御部５５０に出力され、ＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ＿ＷＡＹ信
号は、リプレイスＷＡＹ選択部５４０に出力される。
【００７３】
リプレイスＷＡＹ選択部５４０は、ポート５１０から送信された要求アドレスに対応するデータブロックを格納すべきＷＡＹを選択する処理部である。リプレイスＷＡＹ選択部５４０の構成を図３に示す。同図に示すように、リプレイスＷＡＹ選択部５４０は、ＬＲＵ−ＲＡＭ５４１と、ＷＡＹ選択部５４２と、ＷＡＹ使用判定部５４３とを有し、ポート５１０から要求アドレスが送信されると、そのインデックスをＬＲＵ−ＲＡＭ５４１に入力する。
【００７４】
ＬＲＵ−ＲＡＭ５４１は、図１０に示したＬＲＵ−ＲＡＭ２４１と同様の装置であり、要求アドレスのインデックスが入力されると、そのインデックスに対応するセットを選択し、選択したセットに含まれる各ＷＡＹが最後にアクセスされた時間をＷＡＹ選択部５４２へ出力する。
【００７５】
ＷＡＹ選択部５４２は、各ＷＡＹが最後にアクセスされた時間が入力されると、アクセスされた時間が最も古いＷＡＹを選択し、そのＷＡＹに対応するＲＰＬ−ＷＡＹ信号をＯＮにする。このとき、ＷＡＹ選択部５４２は、入力された縮退情報とＭＩＢ＿ＩＮＤＥＸ＿ＭＣＨ＿ＷＡＹ信号の論理和をＷＡＹごとにとったＤＩＳＡＢＬＥ＿ＷＡＹ信号を参照し、固定故障等により使用不可とされているＷＡＹとＭＩＢ５３０にて実行中の処理に割り当てられているＷＡＹを選択対象から除外する。ＲＰＬ−ＷＡＹ信号は、制御部５５０に出力される。
【００７６】
上記のように最後にアクセスされてから最も時間が経過しているＷＡＹをリプレイスＷＡＹとして選択するリプレイスアルゴリズムをＬＲＵアルゴリズムといい、非常に高いキャッシュのヒット率を実現することができる。上記のリプレイスＷＡＹ選択部５４０の構成によれば、ＭＩＢ５３０にて実行中の処理に割り当てられているＷＡＹを除外してＬＲＵアルゴリズムに基づいてリプレイスＷＡＹの選択を行っているので、予期しないキャッシュの消失の回避をキャッシュのヒット率を高く保ったまま実現することができる。
【００７７】
また、上記のリプレイスＷＡＹ選択部５４０の構成によれば、従来より固定故障等により縮退されたＷＡＹを除外していた仕組みを拡張することによって、ＭＩＢ５３０にて実行中の処理に割り当てられているＷＡＹを除外する機能を容易に実現することができる。
【００７８】
なお、キャッシュメモリ３００が最後にアクセスされた時間をＬＲＵ−ＲＡＭ５４１にて記憶するのではなく、ヒット判定部５２０のタグメモリにて記憶するように構成することもできる。また、リプレイスアルゴリズムとして、ＬＲＵアルゴリズムに代えて他のアルゴリズムを採用することもできる。
【００７９】
ＷＡＹ選択部５４２の構成の一例を図４に示す。同図は、ＷＡＹ選択部５４２においてＷＡＹ０がリプレイスＷＡＹとなるか否かを判定する部分の回路概略図である。
【００８０】
ＯＲ回路１１の出力は、ＷＡＹ１が選択対象外であるか、ＷＡＹ１の最終アクセス時間がＷＡＹ０の最終アクセス時間よりも新しい場合、すなわち、ＷＡＹ１がリプレイスＷＡＹとして適していない場合にＯＮとなる。同様に、ＯＲ回路１２の出力は、ＷＡＹ２がリプレイスＷＡＹとして適していない場合にＯＮとなり、ＯＲ回路１３の出力は、ＷＡＹ３がリプレイスＷＡＹとして適していない場合にＯＮとなる。
【００８１】
そして、ＡＮＤ回路１４の出力は、ＯＲ回路１１〜１３の出力が全てＯＮであり、ＷＡＹ０が選択対象外でない場合にＯＮとなる。ＷＡＹ選択部５４２には、これと同様の回路がＷＡＹ数分だけ存在する。
【００８２】
ＷＡＹ使用判定部５４３は、ＷＡＹが使用可能であるか否かを判定する処理部である。ＷＡＹ使用判定部５４３は、ＤＩＳＡＢＬＥ＿ＷＡＹ信号を参照し、全てのＷＡＹが選択対象外である場合には、選択可能なリプレイスＷＡＹが存在しないことを示すＲＰＬ−ＷＡＹ＿ＮＯＴ＿ＦＯＵＮＤ信号をＯＮにする。
【００８３】
また、ヒット判定部５２０から入力されたＨＩＴ−ＷＡＹ信号と、ＤＩＳＡＢＬＥ＿ＷＡＹ信号を照合し、ＨＩＴ−ＷＡＹ信号に対応するＷＡＹが選択対象外である場合には、ＨＩＴ＿ＷＡＹ＿ＩＮ＿ＵＳＥ信号をＯＮにする。
【００８４】
要求アドレスがヒット判定部５２０にていずれかのＷＡＹにヒットした場合、単にキャッシュメモリ３００上のデータブロックの読み書きを行うだけであれば、既に割り当てられている領域の操作を行うに過ぎないので、ＭＩＢ５３０で進行中の処理を考慮せずに要求を実行することもできる。
【００８５】
しかしながら、要求を実行するために、ＭＩＢ５３０のエントリを取得する必要がある場合には、新たにＭＩＢ５３０のエントリに登録する処理に割り当てるＷＡＹが、既にＭＩＢ５３０のエントリに登録済みの処理に割り当てられているＷＡＹと重複していると、先に完了した処理のキャッシュが後に完了した処理によって予期しないタイミングで上書きされ、キャッシュが消失する可能性がある。
【００８６】
ＨＩＴ＿ＷＡＹ＿ＩＮ＿ＵＳＥ信号は、かかるキャッシュの消失を回避するために制御部５５０によって使用される。要求アドレスがヒット判定部５２０にていずれかのＷＡＹにヒットした場合にＭＩＢ５３０のエントリを取得することが必要になるのは、例えば、プロセッサごとにキャッシュを備えるマルチプロセッサシステムにおいて他のキャッシュのデータブロックを無効化する必要が生じた場合等である。
【００８７】
ＷＡＹ使用判定部５４３の構成の一例を図５に示す。ＡＮＤ回路２１の出力は、ＲＰＬ−ＷＡＹ＿ＮＯＴ＿ＦＯＵＮＤ信号であり、全てのＷＡＹが選択対象外である場合にＯＮとなる。ＡＮＤ回路２２は、要求アドレスがヒット判定部５２０にていずれかのＷＡＹにヒットし、そのＷＡＹが選択対象外である場合に、そのＷＡＹに対応する出力をＯＮにする。ＯＲ回路２３の出力は、ＨＩＴ＿ＷＡＹ＿ＩＮ＿ＵＳＥ信号であり、ＡＮＤ回路２２が出力するいずれかの信号がＯＮの場合にＯＮとなる。
【００８８】
制御部５５０は、ポート５１０から送信された要求に対応する各種制御を実行する制御部である。制御部５５０は、ポート５１０から要求を受信すると共に、上述の処理の結果としてヒット判定部５２０、ＭＩＢ５３０およびリプレイスＷＡＹ選択部５４０から出力される各種信号の入力も受ける。そして、これらの信号の状態に応じて、要求への対処を変更する。
【００８９】
具体的には、ヒット判定部５２０から入力されたＭＩＳＳ信号がＯＮの場合、すなわち、要求アドレスがキャッシュにヒットしなかった場合は、リプレイスＷＡＹ選択部５４０から入力されたＲＰＬ−ＷＡＹ＿ＮＯＴ＿ＦＯＵＮＤ信号がＯＮであれば、全てのＷＡＹが選択対象外であるため、要求をポート５１０に差し戻してリトライさせる。ＲＰＬ−ＷＡＹ＿ＮＯＴ＿ＦＯＵＮＤ信号がＯＦＦであれば、リプレイスＷＡＹ選択部５４０から入力されたＲＰＬ−ＷＡＹ信号が示すリプレイスＷＡＹを要求に割り当てて処理を実行する。
【００９０】
また、ヒット判定部５２０から入力されたＨＩＴ信号がＯＮの場合、すなわち、要求アドレスがキャッシュにヒットした場合は、ＭＩＢ５３０のエントリの取得が必要であり、かつ、リプレイスＷＡＹ選択部５４０から入力されたＨＩＴ−ＷＡＹ＿ＩＮ＿ＵＳＥ信号がＯＮであれば、キャッシュの消失を回避するため、要求をポート５１０に差し戻してリトライさせる。ＭＩＢ５３０のエントリの取得が不要であるか、ＨＩＴ−ＷＡＹ＿ＩＮ＿ＵＳＥ信号がＯＦＦであれば、ヒット判定部５２０から入力されたＨＩＴ−ＷＡＹ信号が示すヒットＷＡＹを使用して処理を実行する。
【００９１】
なお、ＨＩＴ−ＷＡＹ＿ＩＮ＿ＵＳＥ信号がＯＮの場合は、キャッシュが短時間で消失する可能性があり、これによりキャッシュのヒット率を低下する恐れがあるので、ＭＩＢ５３０のエントリの取得が必要であるか否かにかかわらず要求をリトライさせることとしてもよい。
【００９２】
次に、図１に示したメモリアクセス制御装置５００の処理手順について説明する。図６は、図１に示したメモリアクセス制御装置５００の処理手順を示すフローチャートである。同図は、制御部５５０が要求を受信した後、使用するＷＡＹを選択するまでの処理手順を示している。
【００９３】
ポート５１０から送信された要求は、制御部５５０に受信される（ステップＳ２０１）。これと平行して、ポート５１０から送信された要求アドレスは、ヒット判定部５２０と、ＭＩＢ５３０と、リプレイスＷＡＹ選択部５４０とに受信される。
【００９４】
要求アドレスを受信したヒット判定部５２０は、タグメモリを検索し、要求アドレスと同一のデータブロックが存在するか否かを調べ、その結果を制御部５５０とリプレイスＷＡＹ選択部５４０へ出力する（ステップＳ２０２）。要求アドレスを受信したＭＩＢ５３０は、要求アドレスと同一のインデックスを有するデータブロックを処理中のエントリの処理対象ＷＡＹを取得し、取得結果をリプレイスＷＡＹ選択部５４０へ出力する（ステップＳ２０３）。
【００９５】
そして、要求アドレスを受信したリプレイスＷＡＹ選択部５４０は、ＭＩＢ５３０から通知された処理対象ＷＡＹを除外して、要求アドレスに対応するセットに属するＷＡＹの中で最も置き換えに適しているＷＡＹをリプレイスアルゴリズムによって選択し、その結果を制御部５５０へ出力する（ステップＳ２０４）。また、ヒット判定部５２０から通知されたヒットＷＡＹが処理対象ＷＡＹに含まれるか否かを調べて、その結果も制御部５５０へ出力する（ステップＳ２０５）。
【００９６】
そして、制御部５５０は、要求アドレスがヒット判定部５２０のタグメモリにヒットした場合は（ステップＳ２０６肯定）、ＭＩＢ５３０のエントリの取得が必要であり（ステップＳ２０７肯定）、ヒットＷＡＹが処理対象ＷＡＹに含まれていれば（ステップＳ２０８肯定）、要求をポート５１０へ差し戻してリトライさせる。ＭＩＢ５３０のエントリの取得が必要ないか（ステップＳ２０７否定）、ヒットＷＡＹが処理対象ＷＡＹに含まれていなければ（ステップＳ２０８否定）、ヒット判定部５２０から入力されたヒットＷＡＹをキャッシュの格納場所として処理を実行する（ステップＳ２０９）。
【００９７】
また、要求アドレスがヒット判定部５２０のタグメモリにヒットしなかった場合は（ステップＳ２０６否定）、全てのＷＡＹがＭＩＢ５３０の処理対象ＷＡＹとなっていれば（ステップＳ２１０肯定）、要求をポート５１０へ差し戻してリトライさせる。さもなければ（ステップＳ２１０否定）、リプレイスＷＡＹ選択部５４０から入力されたリプレイスＷＡＹをキャッシュの格納場所として処理を実行する（ステップＳ２１１）。
【００９８】
このように、本実施例にかかるメモリアクセス制御方式では、ＭＩＢ５３０で進行中の処理で使用対象となっているＷＡＹを除外してリプレイスＷＡＹを選択し、全てのＷＡＹが使用対象となっている場合にのみ要求をリトライさせるように構成したので、リトライによる性能の低下を最小限に抑えることができる。また、リプレイスＷＡＹの選択が、常にリプレイスアルゴリズムに基づいて行われるように構成したので、キャッシュのヒット率を高く保つことができる。
【産業上の利用可能性】
【００９９】
以上のように、本発明にかかるメモリアクセス制御装置およびメモリアクセス制御方法は、ＭＩＢの動作による予期しないタイミングでのキャッシュの防止に有用であり、特に、リトライの発生を最小限に抑制し、キャッシュのヒット率を高く保つことが必要な場合に適している。
【図面の簡単な説明】
【０１００】
【図１】図１は、本実施例に係るメモリアクセス制御装置の構成を示す機能ブロック図である。
【図２】図２は、ＭＩＢの構成を示す機能ブロック図である。
【図３】図３は、リプレイスＷＡＹ選択部の構成を示す機能ブロック図である。
【図４】図４は、ＷＡＹ選択部の構成の一例を示す回路概略図である。
【図５】図５は、ＷＡＹ使用判定部の構成の一例を示す回路概略図である。
【図６】図６は、図１に示したメモリアクセス制御装置の処理手順を示すフローチャートである。
【図７】図７は、従来のメモリアクセス制御装置の構成を示す機能ブロック図である。
【図８】図８は、ヒット判定部の構成を示す機能ブロック図である。
【図９】図９は、ＭＩＢの構成を示す機能ブロック図である。
【図１０】図１０は、リプレイスＷＡＹ選択部の構成を示す機能ブロック図である。
【図１１】図１１は、図７に示したメモリアクセス制御装置の処理手順を示すフローチャートである。
【符号の説明】
【０１０１】
１１〜１３  ＯＲ回路
１４  ＡＮＤ回路
２１、２２  ＡＮＤ回路
２３    ＯＲ回路
１００    ＣＰＵ
２００〜２０３  メモリアクセス制御装置
２１０    ポート
２２０    ヒット判定部
２２１    タグメモリ
２２２    タグ比較部
２３０    ＭＩＢ
２３１ａ  レジスタ
２３１ｂ  インデックス比較部
２３２    処理状況出力部
２４０    リプレイスＷＡＹ選択部
２４１    ＬＲＵ−ＲＡＭ
２４２    ＷＡＹ選択部
２５０    制御部
３００    キャッシュメモリ
４００    主記憶
５００〜５０３  メモリアクセス制御装置
５１０    ポート
５２０    ヒット判定部
５３０    ＭＩＢ
５３１ａ  レジスタ
５３１ｂ  インデックス比較部
５３１ｃ  デコーダ
５３１ｄ  処理対象ＷＡＹ出力部
５３２    処理状況出力部
５４０    リプレイスＷＡＹ選択部
５４１    ＬＲＵ−ＲＡＭ
５４２    ＷＡＹ選択部
５４３    ＷＡＹ使用判定部
５５０    制御部
【国際調査報告】
2007088591.tif 000014
2007088591.tif 000015
2007088591.tif 000016
2007088591.tif 000017