(57)【特許請求の範囲】
【請求項１】
プロセッサから受付けた、ディレクトリを読み出すロード要求とディレクトリを書き換えるストア要求とを交互にパイプラインに投入する投入部と、
前記投入部によって投入されたロード要求を受付け、第２のキャッシュメモリ及び前記第２のキャッシュメモリに比して高速で読み書きされる第１のキャッシュメモリを検索してロード要求されたディレクトリが存在するか否かを判定する第１の検索部と、
前記第１の検索部によって、ロード要求されたディレクトリが前記第１のキャッシュメモリまたは前記第２のキャッシュメモリに存在すると判定された場合、前記ディレクトリをキャッシュメモリから読み出す読み出し部と、
前記投入部によって投入されたストア要求を受付け、前記第１のキャッシュメモリを検索してストア要求されたディレクトリが存在するか否かを判定する第２の検索部と、
前記第２の検索部によって、前記ディレクトリが前記第１のキャッシュメモリに存在すると判定された場合、前記第１のキャッシュメモリ内のディレクトリを書き換える書き換え部と
を有することを特徴とするキャッシュ制御装置。
【請求項２】
前記投入部は、前記第２の検索部によって、ストア要求されたディレクトリが前記第１のキャッシュメモリに存在しないと判定された場合、前記ストア要求をロード要求としてパイプラインに再投入し、
前記第１の検索部は、前記投入部によって再投入されたロード要求を受付け、前記第２のキャッシュメモリを検索してロード要求されたディレクトリが存在するか否かを判定することを特徴とする請求項１に記載のキャッシュ制御装置。
【請求項３】
前記読み出し部は、前記第１の検索部によって、前記ディレクトリが前記第１のキャッシュメモリ及び前記第２のキャッシュメモリに存在しないと判定された場合、メインメモリからロード要求されたディレクトリを読み出すことを特徴とする請求項１に記載のキャッシュ制御装置。
【請求項４】
前記第１の検索部または前記第２の検索部によって、前記ディレクトリが前記第１のキャッシュメモリに存在しないと判定された場合、前記読み出し部によって読み出されたディレクトリを前記第１のキャッシュメモリに格納する格納部を更に有することを特徴とする請求項３に記載のキャッシュ制御装置。
【請求項５】
前記投入部は、前記第２の検索部によって、ストア要求されたディレクトリが前記第１のキャッシュメモリに存在しないと判定された場合、前記格納部によって前記ディレクトリが前記第１のキャッシュメモリに格納された後に、前記ストア要求をパイプラインに再投入することを特徴とする請求項４に記載のキャッシュ制御装置。
【請求項６】
前記第１の検索部によって、前記ディレクトリが前記第１のキャッシュメモリに存在しないと判定された場合、前記第１のキャッシュメモリに空きエントリがあるか否かを判定する判定部と、
前記判定部によって、前記第１のキャッシュメモリに空きエントリがないと判定された場合、前記第１のキャッシュメモリからエントリを一つ選択し、選択したエントリを前記第２のキャッシュメモリに書き移す書き移し部と
を更に有することを特徴とする請求項１〜５のいずれか一つに記載のキャッシュ制御装置。
【請求項７】
前記第１の検索部によって、前記ディレクトリが前記第１のキャッシュメモリに存在しないと判定された場合、前記第１のキャッシュメモリに空きエントリがあるか否かを判定する判定部と、
前記判定部によって、前記第１のキャッシュメモリに空きエントリがないと判定された場合、前記第１のキャッシュメモリからエントリを一つ選択し、選択したエントリを前記第２のキャッシュメモリに書き移す書き移し部と、
前記読み出し部により前記第２のキャッシュメモリから読み出されたディレクトリが、前記格納部によって前記第１のキャッシュメモリに格納された場合、前記第２のキャッシュメモリに格納されているディレクトリを消去する消去部と
を更に有することを特徴とする請求項４に記載のキャッシュ制御装置。
【請求項８】
キャッシュ制御装置が、
プロセッサから受付けたディレクトリを読み出すロード要求とディレクトリを書き換えるストア要求とを交互にパイプラインに投入し、
ロード要求が投入された場合、第２のキャッシュメモリ及び前記第２のキャッシュメモリに比して高速で読み書きされる第１のキャッシュメモリを検索してロード要求されたディレクトリが存在するか否かを判定し、前記ロード要求されたディレクトリが存在すると判定した場合に前記ディレクトリを読み出す一方、ストア要求が投入された場合には前記第１のキャッシュメモリを検索してストア要求されたディレクトリが存在するか否かを判定し、ストア要求されたディレクトリが前記第１のキャッシュメモリに存在すると判定した場合に前記ディレクトリを書き換える
処理を実行することを特徴とするパイプライン制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ制御装置及びパイプライン制御方法に関する。
【背景技術】
【０００２】
従来、コンピュータシステムにおいて、複数のＣＰＵ（Central  Processing  Unit）が主記憶装置を共有する場合がある。また、各ＣＰＵは、処理を高速化するために、主記憶装置が有するデータやプログラムの一部をキャッシュメモリに一時的に保持する。このように、主記憶装置を共有する複数のＣＰＵがキャッシュを保持する場合、キャッシュ間のデータの不一致という問題が生じる。【０００３】
このようなことから、コンピュータシステムでは、例えば、主記憶装置の各ブロックの状態に関する情報を保持するタグであるディレクトリを用いることでキャッシュ間のデータの一貫性が維持される。【０００４】
また、ＣＰＵは、キャッシュに保持するディレクトリを読み出してデータの読み出し先を特定し、データを更新した場合には、ディレクトリを書き換える。一般的に大容量のキャッシュＲＡＭ（Random  Access  Memory）は、１サイクルではリードまたはライトのどちらか一方を実行するシングルポートＲＡＭである。【０００５】
このため、コンピュータシステムは、例えば、パイプラインへの投入のタイミングを時分割し、ＲＡＭのリードとライトとを交互に制御する。そして、キャッシュＲＡＭのライトサイクルをディレクトリの更新専用とし、ロード要求とストア要求とを区別せずにリードサイクルでパイプラインに投入する。なお、ここでは、キャッシュＲＡＭの読み出し・書き込み動作をリード・ライトと呼称し、ディレクトリの読み出し・書き込み操作をロード・ストアと呼称する。【０００６】
このように、キャッシュ制御装置は、ロード要求やストア要求のパイプラインへの投入を容易に制御可能であるが、ロード要求、ストア要求のいずれもキャッシュＲＡＭのリードサイクルのみでしかパイプラインに投入できない。したがって、リードサイクル及びライトサイクルの両方でパイプラインへ投入する場合に比べてスループットが半分になってしまう。このようなことから、スループットを向上させる技術としてキャッシュを多階層にする方法が知られている。【０００７】
図１１を用いて、キャッシュを多階層にすることでスループットを向上させる従来の技術について説明する。図１１は、キャッシュを多階層にすることでスループットを向上させる従来の技術を示す図である。図１１に示すように、この技術では、１サイクルでリードとライトとを同時に実行可能な小容量で高速の２ポートＲＡＭ（以降、高速キャッシュ８０１と記す）と上述したシングルポートＲＡＭ（以降、低速キャッシュ８０２と記す）とを有する。そして、キャッシュ制御装置は、リードサイクル及びライトサイクルの両方でロード要求、ストア要求を受付けてパイプラインへ投入し、高速キャッシュ８０１と低速キャッシュ８０２とを同時に検索する。【０００８】
例えば、キャッシュ制御装置は、ルーティングコントローラ８０４からロード要求を受付けた場合、高速キャッシュ８０１と低速キャッシュ８０２とを同時に検索する（Ｓ９０１、Ｓ９０２）。キャッシュ制御装置は、高速キャッシュ８０１にディレクトリが存在すれば、高速キャッシュ８０１からディレクトリを読み出してルーティングコントローラ８０４に出力する（Ｓ９０３）。【０００９】
また、キャッシュ制御装置は、高速キャッシュ８０１にディレクトリが存在しない場合、低速キャッシュ８０２または主記憶装置８０３からディレクトリを読み出して（Ｓ９０４、Ｓ９０５）、ルーティングコントローラ８０４に出力する（Ｓ９０６）。このように、要求がキャッシュＲＡＭのリードサイクルのみでの投入ではなく、常時パイプライン投入が可能となるため、スループットが向上する。【００１０】
また、キャッシュ制御装置は、ストア要求を受付けた場合には、高速キャッシュ８０１などから一度読み出したディレクトリを更新してから、再度、高速キャッシュ８０１へ書き戻すという動作を実行する（Ｓ９０７）。【００１１】
例えば、キャッシュ制御装置は、高速キャッシュ８０１にディレクトリが存在しなかった場合、低速キャッシュ８０２または主記憶装置８０３から読み出したディレクトリを高速キャッシュ８０１に格納する（Ｓ９０８）。また、この場合に高速キャッシュ８０１に空きエントリがなければ、キャッシュ制御装置は、高速キャッシュ８０１のエントリを選択し（Ｓ９０９）、選択したエントリを低速キャッシュ８０２へ移動させるリプレースを実行する（Ｓ９１０）。このため、キャッシュ制御装置は、連続してリプレースを実行することを想定し、リプレース用のバッファ８０５を有している。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２０１０−１７０２９２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上述した従来の技術では、リプレースを実行するとスループットの低下を抑制することができない。【００１４】
例えば、低速キャッシュ８０２では、１サイクルに読み出しまたは書き込みのどちらか一方のみが実行されるので、キャッシュ制御装置によってリプレースが実行される場合、ロード要求またはストア要求がリプレース処理と競合することになる。このため、キャッシュ制御装置は、ロード要求またはストア要求をパイプラインに投入するのを抑止した上で、リプレースを実行することになる。【００１５】
すなわち、キャッシュ制御装置は、リプレースを実行するたびにロード要求またはストア要求のパイプライン投入を抑止する。このため、キャッシュ制御装置は、リプレースを多く実行すると、ロード要求またはストア要求のパイプライン投入の抑止も多くなるので、スループットが向上しない場合がある。【００１６】
１つの側面では、リプレースを実行してもスループットの低下を抑制することができるキャッシュ制御装置及びパイプライン制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１７】
第１の案ではキャッシュ制御装置は、プロセッサから受付けたディレクトリを読み出すロード要求とディレクトリを書き換えるストア要求とを交互にパイプラインに投入する。また、キャッシュ制御装置は、投入されたロード要求を受付け、第２のキャッシュメモリ及び第２のキャッシュメモリに比して高速で読み書きされる第１のキャッシュメモリを検索してロード要求されたディレクトリが存在するか否かを判定する。そして、キャッシュ制御装置は、ロード要求されたディレクトリが第１のキャッシュメモリまたは第２のキャッシュメモリに存在すると判定した場合、ディレクトリをキャッシュメモリから読み出す。また、キャッシュ制御装置は、投入されたストア要求を受付け、第１のキャッシュメモリを検索してストア要求されたディレクトリが存在するか否かを判定する。そして、キャッシュ制御装置は、ディレクトリが第１のキャッシュメモリに存在すると判定した場合、第１のキャッシュメモリ内のディレクトリを書き換える。
【発明の効果】
【００１８】
リプレースを実行してもスループットの低下を抑制することができる。
【図面の簡単な説明】
【００１９】
【図１】図１は、実施例１に係るキャッシュ制御装置を含んだコンピュータシステムの構成を示すブロック図である。
【図２】図２は、キャッシュ制御装置の構成を示すブロック図である。
【図３】図３は、ロード要求を受付けた場合のキャッシュ制御装置の処理動作を示す図である。
【図４】図４は、ストア要求を受付けた場合のキャッシュ制御装置の処理動作を示す図である。
【図５】図５は、ロード要求を受付けた場合のキャッシュ制御装置による処理の処理手順を示すフローチャートである。
【図６】図６は、ストア要求を受付けた場合のキャッシュ制御装置による処理の処理手順を示すフローチャートである。
【図７】図７は、従来技術に係るキャッシュ制御装置におけるパイプライン投入を示すタイムチャートである。
【図８】図８は、従来技術に係るキャッシュ制御装置におけるパイプライン投入を示すタイムチャートの別例である。
【図９】図９は、実施例１に係るキャッシュ制御装置におけるパイプライン投入を示すタイムチャートである。
【図１０】図１０は、実施例１に係るキャッシュ制御装置におけるパイプライン投入を示すタイムチャートの別例である。
【図１１】図１１は、キャッシュを多階層にすることでスループットを向上させる従来の技術を示す図である。
【発明を実施するための形態】
【００２０】
以下に、本願の開示するキャッシュ制御装置及びパイプライン制御方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。そして、各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００２１】
実施例１では、図１から図１０を用いて、実施例１に係るキャッシュ制御装置を含んだコンピュータシステムの構成、処理動作、処理手順、効果などについて説明する。【００２２】
［実施例１に係るキャッシュ制御装置を含んだコンピュータシステムの構成］
図１は、実施例１に係るキャッシュ制御装置を含んだコンピュータシステムの構成を示すブロック図である。図１に示すように、コンピュータシステム１は、メインメモリ２と、メインメモリ３と、ＣＰＵ（Central  Processing  Unit）４と、ＣＰＵ５と、ＣＰＵ６と、ＣＰＵ７と、ノードコントローラ１０と、ノードコントローラ２０とを有する。なお、コンピュータシステム１が有するＣＰＵやメモリの数はあくまで例示であり、これに限定されるものではない。【００２３】
メインメモリ２及び３は、ＣＰＵ４〜７が利用するデータやプログラムを一時記憶する記憶装置である。なお、メインメモリ２は、例えばＤＲＡＭ（Dynamic  Random  Access  Memory）である。ＣＰＵ４〜７は、各種演算を実行する演算装置である。【００２４】
ノードコントローラ１０は、ＣＰＵ４〜５の要求に従って、メインメモリ２とＬ１キャッシュ１１、及びＬ２キャッシュ１２の間でデータの入出力を制御する制御装置である。ノードコントローラ１０は、Ｌ１（Level１）キャッシュ１１、Ｌ２（Level２）キャッシュ１２、ルーティングコントローラ１３、キャッシュ制御装置１４を有する。【００２５】
Ｌ１キャッシュ１１は、ＣＰＵ４とＣＰＵ５とが共用するキャッシュメモリであり、メインメモリ２または３に格納されているデータやディレクトリのうち頻繁に利用されるデータを一時的に記憶するキャッシュメモリである。Ｌ１キャッシュ１１は、例えばＳＲＡＭ（Static  Random  Access  Memory）であり、後述するＬ２キャッシュ１２と比較してデータを読み書きする速度は高速であるが、記憶容量は少ない。なお、ここでいうディレクトリとは、メインメモリ２または３の各ブロックの状態を記録する。例えば、ディレクトリは、該当ブロックのコピーをどのキャッシュメモリが保持しているか、また、このキャッシュが書込まれているか否かを示す情報などを含む。【００２６】
Ｌ２キャッシュ１２は、ＣＰＵ４とＣＰＵ５とが共用するキャッシュメモリであり、メインメモリ２または３に格納されているデータのうち利用したデータやディレクトリを一時的に記憶するキャッシュメモリである。Ｌ２キャッシュ１２は、例えばＳＲＡＭであり、Ｌ１キャッシュ１１と比較して記憶容量は大きいが、データを読み書きする速度は低速である。【００２７】
また、Ｌ１キャッシュ１１とＬ２キャッシュ１２とは階層的に使用されるわけではない。具体的には、メインメモリ２に格納されたデータやディレクトリのうち最近使用したものがＬ１キャッシュ１１に格納され、Ｌ１キャッシュ１１では使用されなくなったものがＬ２キャッシュ１２に格納される。【００２８】
ルーティングコントローラ１３は、ＣＰＵ４〜７の要求に従って、メインメモリ２とＬ１キャッシュ１１及びＬ２キャッシュ１２の間でデータの入出力を制御する。例えば、ルーティングコントローラ１３は、ＣＰＵ４から受付けたロード要求をキャッシュ制御装置１４に送信する。そして、ルーティングコントローラ１３は、キャッシュ制御装置１４からロード要求に対する応答を受付ける。また、ルーティングコントローラ１３は、ＣＰＵ４から受付けたストア要求をキャッシュ制御装置１４に送信する。【００２９】
キャッシュ制御装置１４は、ルーティングコントローラ１３から受付けたデータの読み出しや書込み、ディレクトリの読み出しや書込みを制御する。図２を用いてキャッシュ制御装置１４の構成を説明する。【００３０】
図２は、キャッシュ制御装置の構成を示すブロック図である。図２に示すように、キャッシュ制御装置１４は、データ制御部１００とディレクトリ制御部２００とを有する。【００３１】
データ制御部１００は、ルーティングコントローラ１３から受付けたデータの読み出しや書込みを制御する。例えば、データ制御部１００は、ルーティングコントローラ１３から読み出しを受付けたデータをＬ１キャッシュ１１から読み出す。そして、データ制御部１００は、読み出したデータをルーティングコントローラ１３に出力する。【００３２】
ディレクトリ制御部２００は、ルーティングコントローラ１３から受付けたディレクトリの読み出しや書込みを制御する。ディレクトリ制御部２００は、投入部２１０、第１の検索部２２０、第２の検索部２３０、読み出し部２４０、書き換え部２５０、格納部２６０、判定部２７０、書き移し部２８０、消去部２９０を有する。【００３３】
投入部２１０は、ルーティングコントローラ１３から受付けた要求がロード要求であるかストア要求であるかを判定する。そして、投入部２１０は、ルーティングコントローラ１３から受付けたディレクトリを読み出すロード要求とディレクトリを書き換えるストア要求とを交互にパイプラインに投入する。例えば、投入部２１０は、Ｌ１キャッシュ１１、Ｌ２キャッシュ１２のリードサイクルでロード要求をパイプラインに投入し、ライトサイクルでストア要求をパイプラインに投入する。【００３４】
一例を挙げると、投入部２１０は、ストア要求、ロード要求、ロード要求の順で受付けた場合、ライトサイクルでストア要求をパイプラインに投入し、次いでリードサイクルでロード要求をパイプラインに投入する。そして、次のライトサイクルでは処理を実行せず、その次のリードサイクルでロード要求をパイプラインに投入する。言い換えると、投入部２１０は、パイプライン処理を実行して、受付けたロード要求を第１の検索部２２０に出力し、受付けたストア要求を第２の検索部２３０に出力する。【００３５】
また、投入部２１０は、第２の検索部２３０によって、ストア要求されたディレクトリが、Ｌ１キャッシュ１１に存在しないと判定された場合、ストア要求をロード要求としてパイプラインに再投入する。【００３６】
また、投入部２１０は、第２の検索部２３０によって、Ｌ１キャッシュ１１に存在しないと判定されたディレクトリのストア要求を、以下の場合にパイプラインに再投入する。すなわち、投入部２１０は、格納部２６０によって、受付けたディレクトリがＬ１キャッシュ１１に格納された後に、ストア要求をパイプラインに再投入する。【００３７】
第１の検索部２２０は、投入部２１０によって投入されたディレクトリのロード要求を受付け、Ｌ１キャッシュ１１とＬ２キャッシュ１２とを検索して受付けたディレクトリが存在するか否かを判定する。【００３８】
第１の検索部２２０は、受付けたディレクトリがＬ１キャッシュ１１に存在すると判定した場合、読み出し部２４０にＬ１キャッシュ１１に受付けたディレクトリが存在することを通知する。【００３９】
また、第１の検索部２２０は、受付けたディレクトリがＬ１キャッシュ１１に存在せず、Ｌ２キャッシュ１２に存在すると判定した場合、読み出し部２４０にＬ２キャッシュ１２に受付けたディレクトリが存在することを通知する。【００４０】
また、第１の検索部２２０は、Ｌ２キャッシュ１２にも受付けたディレクトリが存在しないと判定した場合、読み出し部２４０にＬ１キャッシュ１１及びＬ２キャッシュ１２に受付けたディレクトリが存在しないことを通知する。【００４１】
また、第１の検索部２２０は、投入部２１０によって、再投入されたロード要求を受付け、Ｌ２キャッシュ１２を検索して受付けたディレクトリが存在するか否かを判定する。第１の検索部２２０は、受付けたディレクトリがＬ２キャッシュ１２に存在すると判定した場合、読み出し部２４０にＬ２キャッシュ１２に受付けたディレクトリが存在することを通知する。【００４２】
また、第１の検索部２２０は、受付けたディレクトリがＬ１キャッシュ１１に存在しないと判定した場合、受付けたディレクトリがＬ１キャッシュ１１に存在しないことを格納部２６０と判定部２７０とに通知する。【００４３】
第２の検索部２３０は、投入部２１０によって投入されたディレクトリのストア要求を受付け、Ｌ１キャッシュ１１を検索して受付けたディレクトリが存在するか否かを判定する。そして、第２の検索部２３０は、受付けたディレクトリがＬ１キャッシュ１１に存在すると判定した場合、受付けたディレクトリがＬ１キャッシュ１１に存在することを書き換え部２５０に通知する。【００４４】
また、第２の検索部２３０は、受付けたディレクトリがＬ１キャッシュ１１に存在しないと判定した場合、受付けたディレクトリがＬ１キャッシュ１１に存在しないことを投入部２１０と格納部２６０とに通知する。【００４５】
また、第２の検索部２３０は、投入部２１０によって再投入されたストア要求を受付け、Ｌ１キャッシュ１１を検索して、受付けたディレクトリが存在するか否かを判定する。そして、第２の検索部２３０は、受付けたディレクトリがＬ１キャッシュ１１に存在すると判定した場合、受付けたディレクトリがＬ１キャッシュ１１に存在することを書き換え部２５０に通知する。【００４６】
読み出し部２４０は、受付けたディレクトリが第１の検索部２２０によってＬ１キャッシュ１１またはＬ２キャッシュ１２に存在することを通知された場合、ディレクトリを読み出す。そして、読み出し部２４０は、Ｌ１キャッシュ１１またはＬ２キャッシュ１２から読み出したディレクトリをルーティングコントローラ１３に出力する。【００４７】
また、読み出し部２４０は、第１の検索部２２０によって、受付けたディレクトリがＬ１キャッシュ１１及びＬ２キャッシュ１２に存在しないことを通知された場合、受付けたディレクトリをメインメモリ２から読み出す。【００４８】
書き換え部２５０は、第２の検索部２３０によって、受付けたディレクトリがＬ１キャッシュ１１に存在することを通知された場合、Ｌ１キャッシュ１１に存在するディレクトリを書き換える。【００４９】
格納部２６０は、受付けたディレクトリがＬ１キャッシュ１１に存在しないことを第１の検索部２２０または第２の検索部２３０から通知された場合、読み出し部２４０によって読み出されたディレクトリをＬ１キャッシュ１１に格納する。例えば、格納部２６０は、読み出し部２４０によりＬ２キャッシュ１２またはメインメモリ２から読み出されたディレクトリをＬ１キャッシュ１１に格納する。【００５０】
ただし、格納部２６０は、以下の通知を受付けた場合に、読み出し部２４０によって読み出されたディレクトリをＬ１キャッシュ１１に格納する。例えば、格納部２６０は、Ｌ１キャッシュ１１に空きエントリがあることを判定部２７０から通知された場合に、ディレクトリをＬ１キャッシュ１１に格納する。また、格納部２６０は、選択したエントリをＬ１キャッシュ１１からＬ２キャッシュ１２へ書き移したことを書き移し部２８０から通知された場合に、ディレクトリをＬ１キャッシュ１１に格納する。【００５１】
また、この場合、格納部２６０は、読み出し部２４０によりＬ２キャッシュ１２またはメインメモリ２から読み出されたディレクトリをＬ１キャッシュ１１に格納したことを投入部２１０及び消去部２９０に通知する。【００５２】
判定部２７０は、第１の検索部２２０によって、ディレクトリがＬ１キャッシュ１１に存在しないことを通知された場合、Ｌ１キャッシュ１１に空きエントリがあるか否かを判定する。そして、判定部２７０は、Ｌ１キャッシュ１１に空きエントリがないと判定した場合、Ｌ１キャッシュ１１に空きエントリがないことを書き移し部２８０に通知する。一方、判定部２７０は、Ｌ１キャッシュ１１に空きエントリがあると判定した場合、Ｌ１キャッシュ１１に空きエントリがあることを格納部２６０に通知する。【００５３】
書き移し部２８０は、判定部２７０によって、Ｌ１キャッシュ１１に空きエントリがないことを通知された場合、エントリを例えばＬＲＵ（Least  Recently  Used）アルゴリズムで選択する。そして、書き移し部２８０は、選択したエントリをＬ１キャッシュ１１からＬ２キャッシュ１２へ書き移す。言い換えると、書き移し部２８０は、選択したエントリをＬ１キャッシュ１１からＬ２キャッシュ１２へリプレースする。この場合、書き移し部２８０は、Ｌ２キャッシュ１２への書き移しをライトサイクルのみで実行する。このライトサイクルはリプレース専用であるため、後続のロード要求やストア要求を抑止しない。【００５４】
また、書き移し部２８０は、選択したエントリをＬ１キャッシュ１１からＬ２キャッシュ１２へ書き移したことを格納部２６０に通知する。【００５５】
消去部２９０は、読み出し部２４０によりＬ２キャッシュ１２から読み出されたディレクトリが、格納部２６０によってＬ１キャッシュ１１に格納された場合、Ｌ２キャッシュ１２に格納されているディレクトリを消去する。【００５６】
図１に戻り、ノードコントローラ２０は、ＣＰＵ６〜７の要求に従って、メインメモリ３とＬ１キャッシュ２１、及びＬ２キャッシュ２２の間でデータの入出力を制御する制御装置である。ノードコントローラ２０は、Ｌ１キャッシュ２１、Ｌ２キャッシュ２２、ルーティングコントローラ２３、キャッシュ制御装置２４を有する。なお、Ｌ１キャッシュ２１の構成はＬ１キャッシュ１１の構成と同様である。また、Ｌ２キャッシュ２２の構成はＬ２キャッシュ１２の構成と同様である。また、ルーティングコントローラ２３の構成は、ルーティングコントローラ１３の構成と同様である。また、キャッシュ制御装置２４の構成は、キャッシュ制御装置１４の構成と同様である。【００５７】
［実施例１に係るキャッシュ制御装置による処理動作］
次に図３及び図４を用いて、実施例１に係るキャッシュ制御装置１４による処理動作を説明する。ここでは、図３を用いてロード要求を受付けた場合のキャッシュ制御装置１４の処理動作を説明し、図４を用いてストア要求を受付けた場合のキャッシュ制御装置１４の処理動作を説明する。【００５８】
（ロード要求）
図３は、ロード要求を受付けた場合のキャッシュ制御装置の処理動作を示す図である。図３に示すように、キャッシュ制御装置１４は、ルーティングコントローラ１３からディレクトリのロード要求を受付けた場合、Ｌ１キャッシュ１１を検索し、該当するディレクトリが存在するか否かを判定する（Ｓ１）。また、キャッシュ制御装置１４は、Ｌ１キャッシュ１１を検索するのとほぼ同時にＬ２キャッシュ１２を検索し、該当するディレクトリが存在するか否かを判定する（Ｓ２）。【００５９】
ここで、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に該当するディレクトリが存在すると判定した場合、該当するディレクトリを読み出して、ルーティングコントローラ１３に出力する（Ｓ３）。【００６０】
一方、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に該当するディレクトリが存在せず、Ｌ２キャッシュ１２に該当するディレクトリが存在すると判定した場合、以下の処理を実行する。すなわち、キャッシュ制御装置１４は、Ｌ２キャッシュ１２からディレクトリを読み出し（Ｓ４）、ルーティングコントローラ１３に出力する（Ｓ６）。ここで、キャッシュ制御装置１４は、Ｌ２キャッシュ１２にも該当するディレクトリが存在しないと判定した場合、メインメモリ２からディレクトリを読み出して（Ｓ５）、ルーティングコントローラ１３に出力する（Ｓ６）。【００６１】
そして、キャッシュ制御装置１４は、Ｌ２キャッシュ１２またはメインメモリ２から読み出したディレクトリをＬ１キャッシュ１１に格納する（Ｓ７）。ここで、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に空きエントリがないと判定した場合、例えばＬＲＵアルゴリズムで選択したエントリをＬ２キャッシュ１２に移動させる（Ｓ８）。【００６２】
（ストア要求）
図４は、ストア要求を受付けた場合のキャッシュ制御装置の処理動作を示す図である。図４に示すように、キャッシュ制御装置１４は、ルーティングコントローラ１３からディレクトリのストア要求を受付けた場合、Ｌ１キャッシュ１１を検索し、該当するディレクトリが存在するか否かを判定する（Ｓ１１）。ここで、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に該当するディレクトリが存在すると判定した場合、該当するディレクトリを読み出して（Ｓ１２）、更新する（Ｓ１３）。【００６３】
一方、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に該当するディレクトリが存在しないと判定した場合、ロード要求としてＬ２キャッシュ１２を検索する（Ｓ１４）。そして、キャッシュ制御装置１４は、Ｌ２キャッシュ１２に該当するディレクトリが存在すると判定した場合、該当するディレクトリを読み出して、Ｌ１キャッシュ１１に格納する（Ｓ１５）。ここで、キャッシュ制御装置１４は、Ｌ２キャッシュ１２にも該当するディレクトリが存在しないと判定した場合、メインメモリ２からディレクトリを読み出して（Ｓ１６）、Ｌ１キャッシュ１１に格納する（Ｓ１５）。【００６４】
また、Ｌ２キャッシュ１２やメインメモリ２から読み出したディレクトリをＬ１キャッシュ１１に格納する場合、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に空きエントリがないと判定した場合、以下の処理を実行する。すなわち、キャッシュ制御装置１４は、例えばＬＲＵアルゴリズムで選択したエントリをＬ２キャッシュ１２に移動させる（Ｓ１７）。【００６５】
［実施例１に係るキャッシュ制御装置による処理の処理手順］
次に図５及び図６を用いて、実施例１に係るキャッシュ制御装置１４による処理の処理手順を説明する。ここでは、図５を用いてロード要求を受付けた場合のキャッシュ制御装置１４による処理の処理手順を説明し、図６を用いてストア要求を受付けた場合のキャッシュ制御装置による処理の処理手順を説明する。【００６６】
（ロード要求処理）
図５は、ロード要求を受付けた場合のキャッシュ制御装置１４による処理の処理手順を示すフローチャートである。例えば、キャッシュ制御装置１４は、ルーティングコントローラ１３からロード要求を受付けたことを契機に以下の処理を実行する。【００６７】
図５に示すように、キャッシュ制御装置１４は、Ｌ１キャッシュ１１を検索し（ステップＳ１０１）、該当するディレクトリが存在するか否かを判定する（ステップＳ１０２）。ここで、キャッシュ制御装置１４は、該当するディレクトリがＬ１キャッシュ１１に存在すると判定した場合（ステップＳ１０２、Ｙｅｓ）、以下の処理を実行する。すなわち、キャッシュ制御装置１４は、Ｌ１キャッシュ１１のディレクトリを読み出して、ルーティングコントローラ１３に出力し（ステップＳ１０３）、処理を終了する。【００６８】
一方、キャッシュ制御装置１４は、該当するディレクトリがＬ１キャッシュ１１に存在しないと判定した場合（ステップＳ１０２、Ｎｏ）、Ｌ２キャッシュ１２を検索する（ステップＳ１０４）。そして、キャッシュ制御装置１４は、該当するディレクトリがＬ２キャッシュ１２に存在するか否かを判定する（ステップＳ１０５）。【００６９】
ここで、キャッシュ制御装置１４は、該当するディレクトリがＬ２キャッシュ１２に存在すると判定した場合（ステップＳ１０５、Ｙｅｓ）、該当するディレクトリを読み出してルーティングコントローラ１３に出力する（ステップＳ１０６）。一方、キャッシュ制御装置１４は、該当するディレクトリがＬ２キャッシュ１２に存在しないと判定した場合（ステップＳ１０５、Ｎｏ）、該当するディレクトリをメインメモリ２から読み出してルーティングコントローラ１３に出力する（ステップＳ１０７）。【００７０】
続いて、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に空きエントリがあるか否かを判定する（ステップＳ１０８）。ここで、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に空きエントリがないと判定した場合（ステップＳ１０８、Ｎｏ）、Ｌ１キャッシュから選択したエントリをＬ２キャッシュ１２に移動させ（ステップＳ１０９）、ステップＳ１１０に移行する。一方、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に空きエントリがあると判定した場合（ステップＳ１０８、Ｙｅｓ）、ステップＳ１１０に移行する。【００７１】
キャッシュ制御装置１４は、読み出したディレクトリをＬ１キャッシュ１１に格納し（ステップＳ１１０）、処理を終了する。【００７２】
（ストア要求処理）
図６は、ストア要求を受付けた場合のキャッシュ制御装置による処理の処理手順を示すフローチャートである。例えば、キャッシュ制御装置１４は、ルーティングコントローラ１３からストア要求を受付けたことを契機に以下の処理を実行する。【００７３】
図６に示すように、キャッシュ制御装置１４は、Ｌ１キャッシュ１１を検索し（ステップＳ２０１）、該当するディレクトリが存在するか否かを判定する（ステップＳ２０２）。ここで、キャッシュ制御装置１４は、該当するディレクトリがＬ１キャッシュ１１に存在すると判定した場合（ステップＳ２０２、Ｙｅｓ）、以下の処理を実行する。すなわち、キャッシュ制御装置１４は、Ｌ１キャッシュ１１のディレクトリを読み出して、読み出したディレクトリを更新し（ステップＳ２０３）、処理を終了する。【００７４】
一方、キャッシュ制御装置１４は、該当するディレクトリがＬ１キャッシュ１１に存在しないと判定した場合（ステップＳ２０２、Ｎｏ）、再びロード要求として投入し（ステップＳ２０４）、Ｌ２キャッシュ１２を検索する（ステップＳ２０５）。そして、キャッシュ制御装置１４は、該当するディレクトリがＬ２キャッシュ１２に存在するか否かを判定する（ステップＳ２０６）。【００７５】
ここで、キャッシュ制御装置１４は、該当するディレクトリがＬ２キャッシュ１２に存在すると判定した場合（ステップＳ２０６、Ｙｅｓ）、該当するディレクトリを読み出す（ステップＳ２０７）。一方、キャッシュ制御装置１４は、該当するディレクトリがＬ２キャッシュ１２に存在しないと判定した場合（ステップＳ２０６、Ｎｏ）、該当するディレクトリをメインメモリ２から読み出す（ステップＳ２０８）。【００７６】
続いて、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に空きエントリがあるか否かを判定する（ステップＳ２０９）。ここで、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に空きエントリがないと判定した場合（ステップＳ２０９、Ｎｏ）、Ｌ１キャッシュ１１から選択したエントリをＬ２キャッシュ１２に移動させ（ステップＳ２１０）、ステップＳ２１１に移行する。一方、キャッシュ制御装置１４は、Ｌ１キャッシュ１１に空きエントリがあると判定した場合（ステップＳ２０９、Ｙｅｓ）、ステップＳ２１１に移行する。【００７７】
キャッシュ制御装置１４は、読み出したディレクトリをＬ１キャッシュ１１に格納し（ステップＳ２１１）、ステップＳ２０１に戻り、再度ストア要求を投入する。【００７８】
［実施例１に係るキャッシュ制御装置による効果］
次に、図７から図１０を用いて、実施例１に係るキャッシュ制御装置１４による効果を説明する。ここでは、図７及び図８を用いて従来技術に係るパイプラインへの投入タイミングを説明し、図９及び図１０を用いて実施例１に係るキャッシュ制御装置１４によるパイプラインへの投入タイミングを説明する。【００７９】
図７は、従来技術に係るキャッシュ制御装置におけるパイプライン投入を示すタイムチャートである。図７に示すように、従来技術に係るキャッシュ制御装置は、ロード要求、ストア要求、ロード要求、ストア要求、ロード要求、ロード要求、ストア要求、ロード要求の順で、５回のロード要求と３回のストア要求とを受付ける。ここで、従来技術に係るキャッシュ制御装置は、サイクル１からサイクル８で受付けた要求をパイプラインに投入する。【００８０】
次に、従来技術に係るキャッシュ制御装置において、ロード要求とストア要求とでミスが生じた場合のタイミングを説明する。図８は、従来技術に係るキャッシュ制御装置におけるパイプライン投入を示すタイムチャートの別例である。ロード５回とストア３回の要求があり、そのうち、ロード３回とストア１回がＬ１キャッシュでミスをし、全てリプレースが実行されるものとする。【００８１】
例えば、図８に示すように、Ｌ１キャッシュのＲｅａｄのタイミングでは、１番目に受付けたロード要求、４番目に受付けたストア要求、５番目に受付けたロード要求、６番目に受付けたロード要求がミスとなる。【００８２】
従来技術に係るキャッシュ制御装置は、１番目に受付けたロード要求、４番目に受付けたストア要求、５番目に受付けたロード要求、６番目に受付けたロード要求のディレクトリをＬ１キャッシュに書込むために、Ｌ２キャッシュへリプレースを実行する。この結果、サイクル４、サイクル８、サイクル９、サイクル１０では、従来技術に係るキャッシュ制御装置は、要求をパイプラインへ投入できなくなる。【００８３】
図９は、実施例１に係るキャッシュ制御装置１４におけるパイプライン投入を示すタイムチャートである。図９に示すように、実施例１に係るキャッシュ制御装置１４は、ロード要求、ストア要求、ロード要求、ストア要求、ロード要求、ロード要求、ストア要求、ロード要求の順で、５回のロード要求と３回のストア要求とを受付ける。ここで、実施例１に係るキャッシュ制御装置１４は、５番目に受付けたロード要求の後に、ロード要求を続けて受付けるので、１サイクル分タイミングをずらして６番目のロード要求をパイプラインに投入することになる。この結果、実施例１に係るキャッシュ制御装置１４は、サイクル１からサイクル９で受付けた要求をパイプラインに投入する。【００８４】
図１０は、実施例１に係るキャッシュ制御装置１４におけるパイプライン投入を示すタイムチャートの別例である。ロード５回とストア３回の要求があり、そのうち、ロード３回とストア１回がＬ２キャッシュでミスをし、全てリプレースが実行されるものとする。【００８５】
例えば、図１０に示すように、Ｌ１キャッシュのＲｅａｄのタイミングでは、１番目に受付けたロード要求、４番目に受付けたストア要求、５番目に受付けたロード要求、６番目に受付けたロード要求がミスとなる。【００８６】
実施例１に係るキャッシュ制御装置１４は、１番目に受付けたロード要求、４番目に受付けたストア要求、５番目に受付けたロード要求、６番目に受付けたロード要求のディレクトリをＬ１キャッシュに書込むために、Ｌ２キャッシュへリプレースを実行する。ここで、実施例１に係るキャッシュ制御装置１４は、ロード要求とストア要求とを交互にパイプラインに投入し、Ｌ２キャッシュのＷｒｉｔｅタイミングでリプレースを実行するので、続くロード要求とストア要求とを止めることなく処理できる。なお、４番目に受付けたストア要求がミスとなったので、ロード要求として再投入するサイクルと、ストア要として再投入するサイクルの分遅れが生じることになる。【００８７】
このように図８と図１０とでは、パイプラインに投入されるロード要求及びストア要求において、どちらも、ロード５回とストア３回の要求があり、そのうち、ロード３回とストア１回がＬ１キャッシュでミスをし、全てリプレースが起こる等しい条件である。【００８８】
８番目の要求をパイプラインへ投入するタイミングで従来技術に係るキャッシュ制御装置と実施例１に係るキャッシュ制御装置１４とを比較する。図８では、８番目の要求を投入するサイクルが、図７で示したサイクル８からサイクル１３まで５サイクル分遅れている。これは、４回のリプレースと１回の再ストア投入による、計５サイクル分の要求が抑止されたことが原因となっている。【００８９】
これに対して、図１０では、８番目の要求を投入するサイクルが、図９で示したサイクル９からサイクル１１までの２サイクル分の遅れで済んでいる。このサイクルの遅れは、ストア要求のミスによって生じた１回の再ロード要求と１回の再ストア要求による要求の抑止のみに起因する。すなわち、実施例１に係るキャッシュ制御装置１４は、ロード要求のミスによるリプレースの影響を受けず、サイクルの遅れをストア要求のミスによって生じた計２サイクル分に留めることができる。【００９０】
このように、キャッシュ制御装置１４は、リプレースを実行した場合でも、ロード要求のパイプラインへの投入を止めることなく処理ができる。この結果、キャッシュ制御装置１４は、スループットを高めることができる。また、リプレースの頻度が高く、ストア要求のヒット率が高い場合ほど、実施例１に係るキャッシュ制御装置１４は、従来技術に係るキャッシュ制御装置よりもスループットを高めることができる。【００９１】
また、ディレクトリの特性から、ストア要求のヒット率は、高速キャッシュのサイズとはほとんど関係なく１００％に近いものとなる。そして、リプレースの頻度は、高速キャッシュのサイズが小さいほど高くなる。すなわち、実施例１に係るキャッシュ制御装置１４は、従来技術に係るキャッシュ制御装置よりもスループットを高めることに加えて、レイテンシも短縮することができる。
【実施例２】
【００９２】
ところで、本発明は、上述した実施例以外にも、種々の異なる形態にて実施されてよい。そこで、実施例２では、本発明に含まれる他の実施例について説明する。【００９３】
（システム構成等）
本実施例において説明した各処理のうち自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともできる。あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上記文章中や図面中で示した処理手順、制御手順、具体的名称については、特記する場合を除いて任意に変更することができる。【００９４】
また、図示した記憶部が格納する情報は一例に過ぎず、必ずしも図示のごとく情報が格納される必要はない。【００９５】
また、各種の負荷や使用状況などに応じて、各実施例において説明した各処理の各ステップでの処理の順番を変更してもよい。【００９６】
また、図示した各構成部は、機能概念的なものであり、必ずしも物理的に図示のごとく構成されていることを要しない。例えば、キャッシュ制御装置１４では、第１の検索部２２０と第２の検索部２３０とが統合されてもよい。
【符号の説明】
【００９７】
１  コンピュータシステム
２、３  メインメモリ
４、５、６、７  ＣＰＵ
１０、２０  ノードコントローラ
１１、２１  Ｌ１キャッシュ
１２、２２  Ｌ２キャッシュ
１３、２３  ルーティングコントローラ
１４、２４  キャッシュ制御装置
１００  データ制御部
２００  ディレクトリ制御部
２１０  投入部
２２０  第１の検索部
２３０  第２の検索部
２４０  読み出し部
２５０  書き換え部
２６０  格納部
２７０  判定部
２８０  書き移し部
２９０  消去部
【図１】
0005637312.tif 000002
【図２】
0005637312.tif 000003
【図３】
0005637312.tif 000004
【図４】
0005637312.tif 000005
【図５】
0005637312.tif 000006
【図６】
0005637312.tif 000007
【図７】
0005637312.tif 000008
【図８】
0005637312.tif 000009
【図９】
0005637312.tif 000010
【図１０】
0005637312.tif 000011
【図１１】
0005637312.tif 000012