(57)【特許請求の範囲】
【請求項１】
複数の処理装置と、
前記複数の処理装置に一対一に接続された複数のキャッシュと、
前記複数のキャッシュに接続され、前記複数のキャッシュ間のデータ転送を制御するコントローラと、
前記処理装置毎に自己のキャッシュ内のエントリ及び他のキャッシュの使用古さ順を示す第１の情報を記憶する情報メモリと
を有することを特徴とするキャッシュシステム。
【請求項２】
前記コントローラは、前記処理装置が要求したデータが、自己のキャッシュでミスし、他のキャッシュでヒットした場合に、前記第１の情報を基に前記自己のキャッシュのエントリ及び前記ヒットした他のキャッシュのエントリを交換することを特徴とする請求項１記載のキャッシュシステム。
【請求項３】
前記第１の情報は、前記処理装置毎に自己のキャッシュ内のエントリ及び複数の他のキャッシュがグループ化された一又は複数のエントリの使用古さ順を示す情報であることを特徴とする請求項１又は２記載のキャッシュシステム。
【請求項４】
前記情報メモリは、前記複数の処理装置間での自己のキャッシュに対する使用古さ順を示す第２の情報を記憶することを特徴とする請求項１〜３のいずれか１項に記載のキャッシュシステム。
【請求項５】
前記コントローラは、前記処理装置が要求したデータが、前記複数のキャッシュすべてでミスした場合、前記第２の情報を基に前記自己のキャッシュのエントリを他のキャッシュのエントリに移動し、主記憶装置又は前記複数のキャッシュより下位階層のキャッシュから読み出したデータを前記移動した自己のキャッシュのエントリに上書きすることを特徴とする請求項４記載のキャッシュシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュシステムに関する。
【背景技術】
【０００２】
コンピュータシステムにおいては一般に、主記憶とは別に小容量で高速なキャッシュメモリが設けられる。主記憶に記憶される情報の一部をキャッシュにコピーしておくことで、この情報をアクセスする場合には主記憶からではなくキャッシュから読み出すことで、高速な情報の読み出しが可能となる。
【０００３】
キャシュは複数のキャッシュラインを含み、主記憶からキャッシュへの情報のコピーはキャッシュライン単位で実行される。主記憶のメモリ空間はキャッシュライン単位で分割され、分割されたメモリ領域を順番にキャッシュラインに割当てておく。キャッシュの容量は主記憶の容量よりも小さいので、主記憶のメモリ領域を繰り返して同一のキャッシュラインに割当てることになる。
【０００４】
メモリ空間上のあるアドレスに最初のアクセスが実行されると、そのアドレスの情報（データやプログラム）をキャシュ内の対応するキャッシュラインにコピーする。同一アドレスに対して次のアクセスを実行する場合にはキャシュから直接に情報を読み出す。一般に、アドレスの全ビットのうちで、所定数の下位ビットがキャッシュのインデックスとなり、それより上位に位置する残りのビットがキャッシュのタグとなる。
【０００５】
データをアクセスする場合には、アクセス先を示すアドレス中のインデックス部分を用いて、キャッシュ中の対応するインデックスのタグを読み出す。読み出したタグと、アドレス中のタグ部分のビットパターンが一致するか否かを判断する。一致しない場合にはキャッシュミスとなる。一致する場合には、キャッシュヒットとなり、当該インデックスに対応するキャッシュデータ（１キャッシュライン分の所定ビット数のデータ）がアクセスされる。
【０００６】
各キャッシュラインに対して１つだけタグを設けたキャッシュの構成を、ダイレクトマッピング方式と呼ぶ。各キャッシュラインに対してＮ個のタグを設けたキャッシュの構成をＮウェイセットアソシアティブと呼ぶ。ダイレクトマッピング方式は１ウェイセットアソシアティブとみなすことができる。
【０００７】
キャッシュミスが発生した場合に、主記憶にアクセスすることによるペナルティーを軽減するために、キャッシュメモリを多階層化したシステムが用いられる。例えば、１次キャッシュと主記憶との間に、主記憶よりは高速にアクセスできる２次キャッシュを設けることにより、１次キャッシュにおいてキャッシュミスが発生した場合に、主記憶にアクセスが必要になる頻度を低くして、キャッシュミス・ペナルティーを軽減することができる。
【０００８】
従来、プロセッサにおいては動作周波数の向上やアーキテクチャの改良により処理速度を向上させてきた。しかし近年、周波数をこれ以上高くすることには技術的な限界が見え始めており、複数のプロセッサを用いたマルチプロセッサ構成により処理速度の向上を目指す動きが強くなっている。
【０００９】
複数のプロセッサが存在するシステムは、各々がキャッシュを有する既存のシングルプロセッサコアを複数個設け、それらを単純に繋げることで実現可能である。このような構成は、設計コストを低く抑えることができるが、キャッシュの使用効率やキャッシュの一貫性に関して問題がある。
【００１０】
下記の特許文献１には、各々が１つ以上のノードの組のうちのあるノード上に存在する複数個のキャッシュのバッファに記憶されるデータの置換を管理するための方法であって、前記１つ以上のノードの組の各ノードは、前記複数個のキャッシュのうちの１つ以上のキャッシュを含み、複数個のキャッシュは第１のキャッシュを含み、前記方法は、１つ以上の要因に基づいて前記第１のキャッシュから第１のバッファを置換のために選択するステップを含み、前記第１のバッファは、第１のデータ項目を記憶するために現在使用されており、前記１つ以上の要因は、前記複数個のキャッシュのうち少なくとも１つの他のキャッシュの状態、または前記複数個のキャッシュのうち前記少なくとも１つの他のキャッシュの構成、のいずれかを含み、さらに、前記第１のバッファに記憶された前記第１のデータ項目を第２のデータ項目と置換するステップを含む、方法が記載されている。
【００１１】
また、下記の特許文献２には、主記憶装置のデータの一部をブロック単位でコピーして格納し、新たなブロックの格納に際してリプレースすべきブロックをＬＲＵ方式で決定するバッファ記憶装置において、バッファ記憶装置のブロックを複数のブロックを複数のグループに分け、各グループ毎にＬＲＵ方式でリプレースブロックを決定する手段を設けるとともに、どのグループをリプレース対象とするかを指示するフラグビットを設け、かつこのフラグビットを三重化して設けて、読出し時には多数決をとるようにしたことを特徴とするバッファ記憶装置のＬＲＵ制御方式が記載されている。
【００１２】
また、下記の特許文献３には、ＣＰＵキャッシュを内蔵するＣＰＵとＣＰＵキャッシュ複製タグメモリを内蔵するＣＰＵ−ＳＣインタフェース制御部を備えた複数のプロセッサモジュールと、メインメモリとが、システムコネクション（ＳＣ）を介して結合されたマルチプロセッサシステムにおけるキャッシュ構成方法であって、前記ＣＰＵのＣＰＵキャッシュをセット数ｋ、ウェイ数ｗのセットアソシアティブとし、前記ＣＰＵ−ＳＣインタフェース制御部のＣＰＵキャッシュ複製タグメモリをセット数ｋ、ウェイ数ｗ＋αのセットアソシアティブとすることを特徴とするキャッシュ構成方法が記載されている。
【００１３】
【特許文献１】特表２００４−５１１８４０号公報
【特許文献２】特開昭５９−００３７７３号公報
【特許文献３】特開２００２−５５８８０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
本発明の目的は、複数の処理装置に一対一に複数のキャッシュを接続した場合に、複数のキャッシュ間で効率的にデータ転送を行うことができるキャッシュシステムを提供することである。
【課題を解決するための手段】
【００１５】
本発明のキャッシュシステムは、複数の処理装置と、前記複数の処理装置に一対一に接続された複数のキャッシュと、前記複数のキャッシュに接続され、前記複数のキャッシュ間のデータ転送を制御するコントローラと、前記処理装置毎に自己のキャッシュ内のエントリ及び他のキャッシュの使用古さ順を示す第１の情報を記憶する情報メモリとを有することを特徴とする。
【発明の効果】
【００１６】
第１の情報を用いることにより、複数のキャッシュ間で効率的にデータ転送を行うことができ、トラフィックの増大を防止することができる。
【発明を実施するための最良の形態】
【００１７】
図１４は、共有分散キャッシュシステムの構成例を示す図である。この共有分散キャッシュシステムは、複数のコア（プロセッサ：処理装置）１０１〜１０３、複数のコア１０１〜１０３に一対一に対応する複数のキャッシュ（キャッシュメモリ）１１１〜１１３、キャッシュ１１１〜１１３に接続されるキャッシュ間接続コントローラ（ＩＣＣ）１２０、及びメインメモリ１３０を含む。コア１０１〜１０３はそれぞれ、自己に直接に接続されるキャッシュ（自コアキャッシュ）１１１〜１１３を１次キャッシュとしてアクセス可能である。この共有分散キャッシュシステムでは、さらに、他のコアのキャッシュ（他コアキャッシュ）を２次キャッシュとしてアクセス可能なように構成される。すなわち、例えばコア１０１から見たときに、キャッシュ１１１を１次キャッシュとしてアクセス可能であるとともに、さらにキャッシュ１１２及び１１３を２次キャッシュとしてアクセス可能なように構成される。このような２次キャッシュをアクセスする経路は、キャッシュ間接続コントローラ１２０を介して提供される。キャッシュ間接続コントローラ１２０は、ＬＲＵ情報１４００を有する。ＬＲＵはLeast Recent Usedの意味であり、ＬＲＵ情報は最も長いこと使用されていないものを特定する情報である。具体的には、複数のエントリに対するＬＲＵ情報は、それら複数のエントリの使用古さ順（最も長いこと使用されていない順）を示す情報である。
【００１８】
例えば、コア１０１は、自コアキャッシュ１１１にロード要求し、キャッシュヒットすれば、自コアキャッシュ１１１からデータを読み出す。キャッシュミスすれば、２次キャッシュ１１２又は１１３にアクセスする。例えば、２次キャッシュ１１２でキャッシュヒットすれば、処理１４１１のように、１次キャッシュ１１１と２次キャッシュ１１２との間でキャッシュラインのデータ交換処理を行う。２次キャッシュ１１２及び１１３でキャッシュミスした場合には、処理１４１２によりメインメモリ１３０のデータがキャッシュライン分、１次キャッシュ１１１にコピーされると共に、そのデータがコア１０１に出力される。また、その際、処理１４１３により、１次キャッシュ１１１から追い出されたキャッシュラインは、２次キャッシュ１１２に移動される。
【００１９】
他コアキャッシュ１１２又は１１３にヒットした時、ヒットしたエントリのＬＲＵ情報１４００が最新でない場合は必ず交換処理１４１１を行う。しかし、この場合、あまり利用しないエントリのときでも交換処理１４１１が発生し、トラフィックが増加してしまう。これにより、システムの動作が低下してしまうため、トラフィックを減少させる必要がある。
【００２０】
また、コア１０１〜１０３の数が増加した場合に、より多くの他コアキャッシュを下位階層キャッシュとして利用するため、ＬＲＵ情報１４００のビット数が増加してしまう。したがって、ＬＲＵ情報１４００のビット数増加を防止する対策が望まれる。
【００２１】
図１５は、他の共有分散キャッシュシステムの構成例を示す図である。以下、図１５が図１４と異なる点を説明する。ＬＲＵ情報１５００は、図１４のＬＲＵ情報１４００に対応するものである。第１のＬＲＵ情報１５０１は、キャッシュ１１１のエントリａ，ｂ，ｃの最古順を示し、「０」が最古、「２」が最新を示す。第１のＬＲＵ情報１５０２は、キャッシュ１１２のエントリａ，ｂ，ｃの最古順を示す。第１のＬＲＵ情報１５０３は、キャッシュ１１３のエントリａ，ｂ，ｃの最古順を示す。第１のＬＲＵ情報１５０１〜１５０３を２項関係方式によりエンコードすると、それぞれ３ビットになる。第２のＬＲＵ情報１５０９は、３個のキャッシュ１１１〜１１３全体でのエントリの最古順を示す。第２のＬＲＵ情報１５０９を順序関係方式によりエンコードすると、１８ビットになる。したがって、ＬＲＵ情報１５００は、３＋３＋３＋１８＝２７ビットになる。これにより、全コアのキャッシュ１１１〜１１３のキャッシュラインを大きな１つのキャッシュと見て、完全な最古関係を保持することができる。
【００２２】
図１６は、図１５の共有分散キャッシュシステムにおけるキャッシュエントリ追い出し処理を示すフローチャートである。複数のコア１０１〜１０３の何れか１つのコアが、自己に直接に接続されたキャッシュ（自コアキャッシュ）へアクセス要求を発行し、まず自コアでキャッシュミスし、さらにその下位のキャッシュでもキャッシュミスし、メインメモリ１３０からデータを読み出して自コアにアロケートする必要が生じた時点で、図１６のフローチャートの動作が実行される。なおここで、図１６のフローチャートの動作が読み出すデータの読み出し元は、必ずしもメインメモリ１３０である必要はない。キャッシュ間接続コントローラ１２０は、キャッシュ１１１〜１１３を優先順位に応じてアクセスすることでキャッシュを階層化しているが、その階層構造のキャッシュの下に、キャッシュとは別の管理単位として管理されているメモリが読み出し元となる。階層構造のキャッシュの下に直ぐにメインメモリ１３０が位置されているのであれば、データの読み出し先はメインメモリ１３０となる。以下では、メインメモリ１３０の場合を例にとって説明する。
【００２３】
ステップＳ１１で、コア１０１〜１０３のうちの１つがメインメモリ１３０にアクセスするために、アクセス先のアドレス（例えば読み出し先のアドレス）をキャッシュ間接続コントローラ１２０に送信する。ステップＳ１２で、第２のＬＲＵ情報１５０９を参照し、アクセス先に対応するインデックスのエントリのうちで、キャッシュ１１１〜１１３全体で最古のエントリを探索する。
【００２４】
ステップＳ１３で、全体で最古のエントリが自コアキャッシュ（アクセス要求を出したコアに対応するキャッシュ）にあるか否かを判定する。全体で最古のエントリが自コアキャッシュに存在する場合には、ステップＳ１４において、第１のＬＲＵ情報１５０１〜１５０３及び第２のＬＲＵ情報１５０９を更新する。すなわち、自コアキャッシュで最古のエントリが最新のエントリとなるように第１のＬＲＵ情報１５０１〜１５０３を更新するとともに、全体で最古のエントリが最新のエントリとなるように第２のＬＲＵ情報１５０９を更新する。その後、ステップＳ１７で、メインメモリ１３０から読み出したデータを自コアキャッシュ内の最古エントリ（ＬＲＵ更新により最新エントリに更新されたエントリ）に上書きする。
【００２５】
全体で最古のエントリが自コアキャッシュに存在しないとステップＳ１３で判定された場合には、ステップＳ１５において、第１のＬＲＵ情報１５０１〜１５０３及び第２のＬＲＵ情報１５０９を更新する。すなわち、自コアキャッシュで最古のエントリが最新のエントリとなるように自コアキャッシュの第１のＬＲＵ情報を更新するとともに、自コアキャッシュから追い出されたエントリ（追い出しエントリ）の移動先のキャッシュにおける最古のエントリ（全体で最古のエントリ）が追い出しエントリの古い順に一致するように移動先キャッシュの第１のＬＲＵ情報を更新する。また第２のＬＲＵ情報１５０９については、全体で最古のエントリが追い出しエントリの古い順に一致する順番のエントリとなり、かつ自コアキャッシュで最古のエントリが最新のエントリとなるように更新する。
【００２６】
その後ステップＳ１６で、自コアキャッシュで最古のエントリを全体で最古のエントリに転送する（移動する）。最後にステップＳ１７で、メインメモリ１３０から読み出したデータを自コアキャッシュ内の最古エントリ（ＬＲＵ更新により最新エントリに更新されたエントリ）に上書きする。
【００２７】
しかし、図１４のシステムの交換動作判定方式では、そのトラフィックが大きくなりシステムの動作を低下させる可能性があるという問題がある。また、図１５のシステムのＬＲＵ符号化方式では、一般性はあるが、共有分散キャッシュ特有の性質を十分に利用していない。また、コアが増加してきた場合に、より多くの他コアキャッシュを下位階層キャッシュとして利用するためには他コアキャッシュの増加に対するＬＲＵ情報のビット数増加を抑える方式が必要である。以下、本発明の実施形態では、上記の課題を解決するための手段を説明する。
【００２８】
図１は、本発明の実施形態による共有分散キャッシュシステムの構成例を示す図である。この共有分散キャッシュシステムは、３個のコア（プロセッサ：処理装置）１０１〜１０３、３個のコア１０１〜１０３に一対一に対応する３個の３ウェイ１次キャッシュ１１１〜１１３、キャッシュ１１１〜１１３に接続されるキャッシュ間接続コントローラ（ＩＣＣ）１２０、及びメインメモリ（又は２次キャッシュ）１３０を含む。コア１０１〜１０３はそれぞれ、自己に直接に接続されるキャッシュ（自コアキャッシュ）を上位階層キャッシュとしてアクセス可能である。この共有分散キャッシュシステムでは、さらに、他のコアのキャッシュ（他コアキャッシュ）を下位階層キャッシュとしてアクセス可能なように構成される。すなわち、例えばコア１０１から見たときに、キャッシュ１１１を上位階層キャッシュとしてアクセス可能であるとともに、さらに他コアキャッシュ１１２及び１１３を下位階層キャッシュとしてアクセス可能なように構成される。このような下位階層キャッシュをアクセスする経路は、キャッシュ間接続コントローラ１２０を介して提供される。
【００２９】
キャッシュ間接続コントローラ１２０は、第１のＬＲＵ情報１２１〜１２３及び第２のＬＲＵ情報１２９を記憶する情報メモリを有する。情報メモリは、キャッシュ間接続コントローラ１２０の外にあってもよい。第１のＬＲＵ情報１２１は、キャッシュ１１１のエントリａ，ｂ，ｃ及び他コアキャッシュ１１２及び１１３のグループｘの最古順を示し、「０」が最古、「２」が最新を示す。すなわち、第１のＬＲＵ情報１２１は、自己のキャッシュ１１１の３個のエントリａ，ｂ，ｃに、ｎ個（＝１個）の他コアキャッシュグループｘを追加したＬＲＵ情報である。
【００３０】
図２は、図１の第１のＬＲＵ情報１２１〜１２３及び第２のＬＲＵ情報１２９の詳細を示す図である。第１のＬＲＵ情報１２２は、第１のＬＲＵ情報１２１と同様に、キャッシュ１１２のエントリａ，ｂ，ｃ及び他コアキャッシュ１１１及び１１３のグループｘの最古順を示す。第１のＬＲＵ情報１２３も、第１のＬＲＵ情報１２１と同様に、キャッシュ１１３のエントリａ，ｂ，ｃ及び他コアキャッシュ１１１及び１１２のグループｘの最古順を示す。第１のＬＲＵ情報１２１〜１２３を２項関係方式によりエンコードすると、それぞれ６ビットになる。
【００３１】
コア１０１はコアＡであり、キャッシュ１１１はキャッシュＡである。コア１０２はコアＢであり、キャッシュ１１２はキャッシュＢである。コア１０３はコアＣであり、キャッシュ１１３はキャッシュＣである。
【００３２】
第２のＬＲＵ情報１２９は、３個のコア１０１〜１０３間での自己のキャッシュ１１１〜１１３に対する使用古さ順を示し、ＡがキャッシュＡ（１１１）のＬＲＵ情報、ＢがキャッシュＢ（１１２）のＬＲＵ情報、ＣがキャッシュＣ（１１３）のＬＲＵ情報である。第２のＬＲＵ情報１２９を２項関係方式によりエンコードすると、３ビットになる。したがって、ＬＲＵ情報１２１〜１２３、１２９の合計は、６＋６＋６＋３＝２１ビットになり、図１５のシステムのビット数より少なくなる。第１のＬＲＵ情報１２１〜１２３の情報メモリは、各キャッシュ１１１〜１１３のローカルなＬＲＵ情報に、他コアキャッシュグループが１ウェイ増えたとみて、各キャッシュ毎に第１のＬＲＵ情報１２１〜１２３を保持する。
【００３３】
図３は、本発明の実施形態による共有分散キャッシュシステムの他の構成例を示す図である。以下、図３が図１と異なる点を説明する。この共有分散キャッシュシステムは、６個のコア１０１〜１０６、６個のコア１０１〜１０６に一対一に対応する６個の１次キャッシュ１１１〜１１６、キャッシュ１１１〜１１６に接続されるキャッシュ間接続コントローラ（ＩＣＣ）１２０、及びメインメモリ（又は２次キャッシュ）１３０を含む。キャッシュ１１１〜１１４及び１１６は３ウェイであり、キャッシュ１１５は２ウェイである。コア１０１〜１０６はそれぞれ、自コアキャッシュ１１１〜１１６を上位階層キャッシュとしてアクセス可能である。この共有分散キャッシュシステムでは、さらに、他コアキャッシュを下位階層キャッシュとしてアクセス可能なように構成される。すなわち、例えばコア１０１から見たときに、キャッシュ１１１を上位階層キャッシュとしてアクセス可能であるとともに、さらに他コアキャッシュ１１２及び１１３のグループｘ、他コアキャッシュ１１４及び１１５のグループｙ、他コアキャッシュ１１６のグループｚを下位階層キャッシュとしてアクセス可能なように構成される。
【００３４】
キャッシュ間接続コントローラ１２０は、第１のＬＲＵ情報１２１〜１２６及び第２のＬＲＵ情報１２９を記憶する情報メモリを有する。第１のＬＲＵ情報１２１は、キャッシュ１１１のエントリａ，ｂ，ｃ、他コアキャッシュ１１２及び１１３のグループｘ、他コアキャッシュ１１４及び１１５のグループｙ、他コアキャッシュ１１６グループｚの最古順を示し、「０」が最古、「５」が最新を示す。すなわち、第１のＬＲＵ情報１２１は、自己のキャッシュ１１１の３個のエントリａ，ｂ，ｃに、ｎ個（＝３個）の他コアキャッシュグループｘ，ｙ，ｚを追加したＬＲＵ情報である。
【００３５】
図４は、図３の第１のＬＲＵ情報１２１〜１２６及び第２のＬＲＵ情報１２９の詳細を示す図である。第１のＬＲＵ情報１２２は、第１のＬＲＵ情報１２１と同様に、キャッシュ１１２のエントリａ，ｂ，ｃ、ｎ個（＝３個）の他コアキャッシュ１１１及び１１３のグループｘ、他コアキャッシュ１１４及び１１５のグループｙ、他コアキャッシュ１１６のグループｚの最古順を示す。第１のＬＲＵ情報１２３は、キャッシュ１１３のエントリａ，ｂ，ｃ、ｎ個（＝３個）の他コアキャッシュ１１１及び１１２のグループｘ、他コアキャッシュ１１４及び１１５のグループｙ、他コアキャッシュ１１６のグループｚの最古順を示す。第１のＬＲＵ情報１２４は、キャッシュ１１４のエントリａ，ｂ，ｃ、ｎ個（＝２個）の他コアキャッシュ１１１及び１１２のグループｘ、他コアキャッシュ１１３、１１５及び１１６のグループｙの最古順を示す。第１のＬＲＵ情報１２５は、キャッシュ１１５の２個のエントリａ，ｂ、ｎ個（＝３個）の他コアキャッシュ１１１及び１１２のグループｘ、他コアキャッシュ１１３及び１１４のグループｙ、他コアキャッシュ１１６のグループｚの最古順を示す。第１のＬＲＵ情報１２６は、キャッシュ１１６のエントリａ，ｂ，ｃ、ｎ個（＝３個）の他コアキャッシュ１１１及び１１２のグループｘ、他コアキャッシュ１１３及び１１４のグループｙ、他コアキャッシュ１１５のグループｚの最古順を示す。グループの組み合わせは、任意に決めることができる。
【００３６】
第１のＬＲＵ情報１２１〜１２３，１２６を２項関係方式によりエンコードすると、それぞれ１５ビットになる。第１のＬＲＵ情報１２４は、２個の他コアキャッシュグループｘ及びｙの情報を有するので、２項関係方式によりエンコードすると１０ビットになる。第１のＬＲＵ情報１２５は、キャッシュ１１５の２個のエントリａ及びｂの情報を有するので、２項関係方式によりエンコードすると１０ビットになる。
【００３７】
コア１０１はコアＡであり、キャッシュ１１１はキャッシュＡである。コア１０２はコアＢであり、キャッシュ１１２はキャッシュＢである。コア１０３はコアＣであり、キャッシュ１１３はキャッシュＣである。コア１０４はコアＤであり、キャッシュ１１４はキャッシュＤである。コア１０５はコアＥであり、キャッシュ１１５はキャッシュＥである。コア１０６はコアＦであり、キャッシュ１１６はキャッシュＦである。
【００３８】
第２のＬＲＵ情報１２９は、６個のコア１０１〜１０６間での自己のキャッシュ１１１〜１１６に対する使用古さ順を示し、ＡがキャッシュＡ（１１１）のＬＲＵ情報、ＢがキャッシュＢ（１１２）のＬＲＵ情報、ＣがキャッシュＣ（１１３）のＬＲＵ情報、ＤがキャッシュＤ（１１４）のＬＲＵ情報、ＥがキャッシュＥ（１１５）のＬＲＵ情報、ＦがキャッシュＦ（１１６）のＬＲＵ情報である。第２のＬＲＵ情報１２９を２項関係方式によりエンコードすると、１５ビットになる。したがって、ＬＲＵ情報１２１〜１２６、１２９の合計は、１５＋１５＋１５＋１０＋１０＋１５＋１５＝９５ビットになり、コア数が多いときにはビット数を少なくできる効果が大きい。
【００３９】
図５は、本実施形態による共有分散キャッシュシステムにおけるデータロードアクセス動作を示すフローチャートである。以下、図１のシステムを例に説明する。ステップＳ１において、まず、複数のコア１０１〜１０３の何れか１つのコアが、自己に直接に接続されたキャッシュ（自コアキャッシュ）へロード要求を発行する。
【００４０】
ステップＳ２において、ロード要求を受け取ったキャッシュは、要求対象のデータがキャッシュ内に存在するか否か、すなわちキャッシュヒットであるか否かを判定する。キャッシュヒットである場合には、ステップＳ３において、自コアキャッシュから要求対象のデータを読み出して、ロード要求を発行したコアにデータを返送する。
【００４１】
ステップＳ２においてキャッシュミスである場合には、ステップＳ４に進む。このステップＳ４において、キャッシュミスが検出されたキャッシュの下に、下位階層キャッシュが存在するか否かを判定する。例えばステップＳ２においてキャッシュミスが検出されてステップＳ４に進んだ場合には、キャッシュミスが検出されたキャッシュはキャッシュ１１１〜１１３の何れか１つであるので、この場合、他の２つのキャッシュが下位階層キャッシュとして存在する。下位階層キャッシュが存在する場合には、ステップＳ５に進む。
【００４２】
ステップＳ５において、キャッシュ階層が１つ下の他コアキャッシュにアクセスする。ステップＳ６において、アクセス要求を受け取ったキャッシュは、要求対象のデータがキャッシュ内に存在するか否か、すなわちキャッシュヒットであるか否かを判定する。キャッシュミスである場合には、ステップＳ４に戻り、上記の処理を繰り返す。
【００４３】
ステップＳ６においてキャッシュヒットである場合には、ステップＳ７に進む。このステップＳ７において、キャッシュデータの交換処理を行う。すなわち、キャッシュヒットしたキャッシュからアクセス対象のキャッシュライン（アクセス対象のデータ）を自コアキャッシュに移動し、コアへデータを返送する。この際に、キャッシュラインの自コアキャッシュへの移動に伴い、自コアキャッシュから追い出されるキャッシュラインを他コアに移動する。ステップＳ７の詳細は、後に図６を参照しながら説明する。
【００４４】
またステップＳ４において、下位階層キャッシュが存在しないと判定された場合には、ステップＳ８に進む。例えばステップＳ６においてキャッシュミスが検出されてステップＳ４に進んだ際に、このキャッシュミスが検出されたキャッシュが既に最下層のキャッシュであった場合、その下層にはメインメモリ１３０しか存在しない。このような場合には、ステップＳ８で、メインメモリ１３０から要求対象のデータを読み出し、自コアキャッシュにアロケート（１キャッシュライン分の要求対象のデータを自コアキャッシュにコピー）するとともに、ロード要求を発行したコアにデータを返送する。またこの動作に伴い自コアキャッシュから追い出されたキャッシュラインは、例えば下位階層キャッシュに移動される。ステップＳ８の詳細は、後に図１０を参照しながら説明する。
【００４５】
上記の動作フローにおいて、ステップＳ７はキャッシュとキャッシュとの間のデータ転送に関連する動作であり、ステップＳ８はメインメモリ１３０とキャッシュとの間のデータ転送に関連する動作である。
【００４６】
図６は、図５のステップＳ７の交換処理を示すフローチャートである。まず、ステップＡ１では、図５のステップＳ６の判断により、下位階層キャッシュとして利用可能な他コアキャッシュにヒットしたと判断される。
【００４７】
次に、ステップＡ２では、キャッシュ間接続コントローラ１２０は判定処理を行う。すなわち、ヒットした他コアキャッシュが所属するグループの自コアローカルの第１のＬＲＵ情報が最新であり、かつ、ヒットした他コアキャッシュの第１のＬＲＵ情報のエントリが最新でないことの条件を満たすか否かを判定する。条件を満たす場合にはステップＡ４に進み、条件を満たさない場合にはステップＡ７に進む。
【００４８】
ステップＡ４では、キャッシュ間接続コントローラ１２０は自コアキャッシュ及び他コアキャッシュ間で交換処理を行う。すなわち、自コアキャッシュの最古エントリと他コアキャッシュのヒットしたエントリを交換する。
【００４９】
次に、ステップＡ５では、キャッシュ間接続コントローラ１２０はＬＲＵ更新処理を行う。すなわち、自コアの第１のＬＲＵ情報については自コアキャッシュの交換されたエントリを最新に更新し、他コアの第１のＬＲＵ情報については他コアキャッシュの交換されたエントリを最古に更新し、第２のＬＲＵ情報については自コアキャッシュが最新となるように更新する。その後、ステップＡ６に進み、処理を終了する。
【００５０】
ステップＡ７では、自コアはキャッシュ間接続コントローラ１２０を介して参照処理を行う。すなわち、他コアキャッシュのヒットしたエントリを直接参照する（読み出す）。
【００５１】
次に、ステップＡ３では、キャッシュ間接続コントローラ１２０はＬＲＵ更新処理を行う。すなわち、自コアの第１のＬＲＵ情報についてはヒットした他コアキャッシュが所属するグループを最新に更新し、他コアの第１のＬＲＵ情報についてはヒットした他コアキャッシュのエントリが最新であれば２番目に新しいものと交換するように更新し、第２のＬＲＵ情報についてはヒットした他コアキャッシュが最新となるように更新する。その後、ステップＡ６に進み、処理を終了する。
【００５２】
図７〜図９は、図１及び図２のシステムにおける図６の交換処理の例を示す図である。図７は、初期状態を示す。第１のＬＲＵ情報１２１〜１２３及び第２のＬＲＵ情報１２９は、０が最古であり、値が大きくなるほど新しいことを示す。
【００５３】
まず、ステップＡ１において、自コアＡ（１０１）から他コアＢ（１０２）のキャッシュＢ（１１２）のエントリｃにヒットした場合を説明する。
【００５４】
次に、ステップＡ２では、ヒットした他コアキャッシュＢ（１１２）が所属するグループｘの自コアローカルの第１のＬＲＵ情報１２１が１であり、最新でないので、ステップＡ７に進む。ステップＡ７では、他コアキャッシュＢ（１１２）のヒットしたエントリｃを直接参照する。
【００５５】
次に、ステップＡ３では、図８に示すように、自コアＡ（１０１）の第１のＬＲＵ情報１２１についてはヒットした他コアキャッシュＢ（１１２）が所属するグループｘを最新（値「３」）に更新し、他コアＢ（１０２）の第１のＬＲＵ情報１２２についてはヒットした他コアキャッシュＢ（１１２）のエントリｃが最新（図７の値「３」）であるので、２番目に新しいエントリｘと交換するように更新し、第２のＬＲＵ情報１２９についてはヒットした他コアキャッシュＢ（１１２）が最新となるように更新する。その後、ステップＡ６に進み、処理を終了する。
【００５６】
次に、ステップＡ１において、再度、自コアＡ（１０１）から他コアＢ（１０２）のキャッシュＢ（１１２）のエントリｃにヒットした場合を説明する。
【００５７】
次に、ステップＡ２では、ヒットした他コアキャッシュＢ（１１２）が所属するグループｘの自コアローカルの第１のＬＲＵ情報１２１が最新（値「３」）であり、かつ、ヒットした他コアキャッシュＢ（１１２）の第１のＬＲＵ情報１２２のエントリｃが最新でない（値「２」）ので、ステップＡ４に進む。ステップＡ４では、自コアキャッシュＡ（１１１）の最古エントリｂと他コアキャッシュＢ（１１２）のヒットしたエントリｃを交換する。
【００５８】
次に、ステップＡ５では、図９に示すように、自コアＡ（１０１）の第１のＬＲＵ情報１２１については自コアキャッシュＡ（１１１）の交換されたエントリｂを最新に更新し、他コアＢ（１０２）の第１のＬＲＵ情報１２２については他コアキャッシュＢ（１１２）の交換されたエントリｃを最古に更新し、第２のＬＲＵ情報１２９については自コアキャッシュＡ（１１１）が最新となるように更新する。その後、ステップＡ６に進み、処理を終了する。
【００５９】
以上のように、第１回目に他コアキャッシュＢのエントリｃにヒットした場合には、交換処理を行わず、第２回目に他コアキャッシュＢのエントリｃにヒットした場合に交換処理行うことにより、無駄な交換処理をなくし、トラフィックを減少させることができる。すなわち、自コアＡが連続してアクセスし、かつ、ヒットした他コアキャッシュＢで現在あまり使っていないエントリｃのみ交換することにより、効率的な交換処理を行うことができる。
【００６０】
次に、図３及び図４のシステムを例に交換処理を説明する。上記と同様に、第１回目は交換せず、第２回目は交換する場合の動作例を示す。
【００６１】
以下に、初期の第１及び第２のＬＲＵ情報を示す。第１及び第２のＬＲＵ情報は、古→新の順にエントリを示す。
コアＡの第１のＬＲＵ情報１２１：  ｂｘａｃｚｙ
コアＢの第１のＬＲＵ情報１２２：  ａｂｘｚｙｃ
コアＣの第１のＬＲＵ情報１２３：  ｂｘｃｚｙａ
コアＤの第１のＬＲＵ情報１２４：  ａｂｃｘｙ
コアＥの第１のＬＲＵ情報１２５：  ａｂｘｙｚ
コアＦの第１のＬＲＵ情報１２６：  ａｂｃｘｙｚ
第２のＬＲＵ情報１２９：  ＣＢＦＡＤＥ
【００６２】
まず、ステップＡ１では、コアＡからコアＢのキャッシュＢのエントリｃにヒットする。
ステップＡ２では、キャッシュＡのエントリｘが最新でないため交換しない。
ステップＡ７では、直接参照する。
ステップＡ３では、ＬＲＵ更新処理により、キャッシュＡのエントリｘを最新に、キャッシュＢのエントリｃを２番目に各々のコアＡ，コアＢに対応する第１のＬＲＵ情報を更新し、キャッシュＢが最新となるように第２のＬＲＵ情報１２９を更新する。
ステップＡ６で終了する。
【００６３】
以下に、更新後の第１及び第２のＬＲＵ情報を示す。第１及び第２のＬＲＵ情報は、古→新の順にエントリを示す。
コアＡの第１のＬＲＵ情報１２１：  ｂａｃｚｙｘ
コアＢの第１のＬＲＵ情報１２２：  ａｂｘｚｃｙ
コアＣの第１のＬＲＵ情報１２３：  ｂｘｃｚｙａ
コアＤの第１のＬＲＵ情報１２４：  ａｂｃｘｙ
コアＥの第１のＬＲＵ情報１２５：  ａｂｘｙｚ
コアＦの第１のＬＲＵ情報１２６：  ａｂｃｘｙｚ
第２のＬＲＵ情報１２９：  ＣＦＡＤＥＢ
【００６４】
次に、ステップＡ１では、再度、コアＡからコアＢのキャッシュＢのエントリｃにヒットする。
ステップＡ２では、キャッシュＡのエントリｘが最新であり、かつ、キャッシュＢのエントリｃが最新でないため交換する。
ステップＡ４では、キャッシュＡのエントリｂとキャッシュＢのエントリｃを交換する。
ステップＡ５では、ＬＲＵ更新処理により、キャッシュＡのエントリｂを最新に、キャッシュＢのエントリｃを最古に各々のコアＡ，コアＢに対応する第１のＬＲＵ情報を更新し、キャッシュＡが最新となるように第２のＬＲＵ情報１２９を更新する。
ステップＡ６で終了する。
【００６５】
以下に、更新後の第１及び第２のＬＲＵ情報を示す。第１及び第２のＬＲＵ情報は、古→新の順にエントリを示す。
コアＡの第１のＬＲＵ情報１２１：  ａｃｚｙｘｂ
コアＢの第１のＬＲＵ情報１２２：  ｃａｂｘｚｙ
コアＣの第１のＬＲＵ情報１２３：  ｂｘｃｚｙａ
コアＤの第１のＬＲＵ情報１２４：  ａｂｃｘｙ
コアＥの第１のＬＲＵ情報１２５：  ａｂｘｙｚ
コアＦの第１のＬＲＵ情報１２６：  ａｂｃｘｙｚ
第２のＬＲＵ情報１２９：  ＣＦＤＥＢＡ
【００６６】
以上のように、他コアキャッシュにヒットした場合の交換動作判定は、そのヒットエントリが自コアで頻繁に使われて、かつ、そのエントリを有している他コアが時間的に同時期に頻繁にアクセスしないという条件を満たすときに、交換処理を行うと判定する。
【００６７】
図１０は、図５のステップＳ８の追い出し処理を示すフローチャートである。まず、ステップＢ１では、図５のステップＳ４の判断により、下位階層キャッシュとして利用可能な他コアキャッシュに全てミスしたと判断される。
【００６８】
次に、ステップＢ２では、キャッシュ間接続コントローラ１２０は判定処理を行う。すなわち、第２のＬＲＵ情報を参照し、自コアが最近そのインデックスのエントリを最も使っていないコアでないことの条件を満たすか否かを判定する。条件を満たす場合にはステップＢ４に進み、条件を満たさない場合にはステップＢ７に進む。
【００６９】
ステップＢ４では、キャッシュ間接続コントローラ１２０は自コアキャッシュから他コアキャッシュへ追い出し処理を行う。すなわち、最近最も使われていない他コアキャッシュの最古エントリに自コアキャッシュの最古エントリ（他コアグループ用エントリを含まないものの中で最古エントリ）を移動する。
【００７０】
次に、ステップＢ５では、キャッシュ間接続コントローラ１２０はＬＲＵ更新処理を行う。すなわち、自コアの第１のＬＲＵ情報については自コアキャッシュの最古エントリを最新に更新し、他コアの第１のＬＲＵ情報については追い出し先の他コアキャッシュの最古エントリを最新に更新し、第２のＬＲＵ情報については自コアキャッシュが最新に、追い出し先の他コアキャッシュを２番目に新しいものとなるように更新する。その後、ステップＢ６に進む。
【００７１】
ステップＢ７では、キャッシュ間接続コントローラ１２０は破棄処理を行う。すなわち、自コアキャッシュの最古エントリを破棄する。具体的には、このステップでは何も処理せず、後のステップＢ６の上書き処理により自コアキャッシュの最古エントリが破棄される。
【００７２】
次に、ステップＢ３では、キャッシュ間接続コントローラ１２０はＬＲＵ更新処理を行う。すなわち、自コアの第１のＬＲＵ情報については自コアキャッシュの最古エントリを最新に更新し、第２のＬＲＵ情報については自コアキャッシュが最新になるように更新する。その後、ステップＢ６に進む。
【００７３】
ステップＢ６では、キャッシュ間接続コントローラ１２０は、自コアキャッシュの最古エントリ（ＬＲＵ情報更新後の最新エントリ）にメインメモリ１３０から読み出したデータを上書きし、自コアはそのデータを取得する。以上で、処理を終了する。
【００７４】
図１１〜図１３は、図１及び図２のシステムにおける図１０の追い出し処理の例を示す図である。図１１は、初期状態を示す。第１のＬＲＵ情報１２１〜１２３及び第２のＬＲＵ情報１２９は、０が最古であり、値が大きくなるほど新しいことを示す。
【００７５】
まず、ステップＢ１において、自コアＡ（１０１）のアクセスが全ての他コアキャッシュでミスした場合を説明する。
【００７６】
次に、ステップＢ２では、第２のＬＲＵ情報１２９を参照すると、自コアキャッシュＡ（１１１）が最近最も使っていないので、ステップＢ７を介してステップＢ３に進む。
【００７７】
ステップＢ３では、図１２に示すように、自コアＡ（１０１）の第１のＬＲＵ情報１２１については自コアキャッシュＡ（１１１）の最古エントリｂを最新に更新し、第２のＬＲＵ情報１２９については自コアキャッシュＡが最新になるように更新する。
【００７８】
次に、ステップＢ６では、自コアキャッシュＡ（１１１）の最古エントリ（ＬＲＵ情報更新後の最新エントリ）ｂにメインメモリ１３０から読み出したデータを上書きする。以上で処理を終了する。
【００７９】
次に、ステップＢ１において、再度、自コアＡ（１０１）のアクセスが全ての他コアキャッシュでミスした場合を説明する。
【００８０】
次に、ステップＢ２では、第２のＬＲＵ情報１２９を参照すると、他コアキャッシュＣ（１１３）が最近最も使っていないので、ステップＢ４に進む。
【００８１】
ステップＢ４では、最近最も使われていない他コアキャッシュＣ（１１３）の最古エントリｂに自コアキャッシュＡ（１１１）の最古エントリ（他コアグループ用エントリを含まないものの中で最古エントリ）ａを移動する。
【００８２】
次に、ステップＢ５では、図１３に示すように、自コアＡ（１０１）の第１のＬＲＵ情報１２１については自コアキャッシュＡ（１１１）の最古エントリａを最新に更新し、他コアＣ（１０３）の第１のＬＲＵ情報１２３については追い出し先の他コアキャッシュＣ（１１３）の最古エントリｂを最新に更新し、第２のＬＲＵ情報１２９については自コアキャッシュＡ（１１１）が最新に、追い出し先の他コアキャッシュＣ（１１３）を２番目に新しいものとなるように更新する。
【００８３】
次に、ステップＢ６では、自コアキャッシュＡ（１１１）の最古エントリ（ＬＲＵ情報更新後の最新エントリ）ａにメインメモリ１３０から読み出したデータを上書きする。以上で処理を終了する。
【００８４】
以上のように、第１回目に全ての他コアキャッシュでミスした場合には、追い出し処理を行わず、第２回目に全ての他コアキャッシュでミスした場合に追い出し処理行うことにより、無駄な追い出し処理をなくし、トラフィックを減少させることができる。すなわち、自コアＡが連続してキャッシュミスし、かつ、他コアキャッシュが最古であるときのみ追い出し処理することにより、効率的な追い出し処理を行うことができる。
【００８５】
次に、図３及び図４のシステムを例に追い出し処理を説明する。上記と同様に、第１回目は追い出しせず、第２回目は追い出しする場合の動作例を示す。
【００８６】
以下に、初期の第１及び第２のＬＲＵ情報を示す。第１及び第２のＬＲＵ情報は、古→新の順にエントリを示す。
コアＡの第１のＬＲＵ情報１２１：  ｂｘａｃｚｙ
コアＢの第１のＬＲＵ情報１２２：  ａｂｘｚｙｃ
コアＣの第１のＬＲＵ情報１２３：  ｂｘｃｚｙａ
コアＤの第１のＬＲＵ情報１２４：  ａｂｃｘｙ
コアＥの第１のＬＲＵ情報１２５：  ａｂｘｙｚ
コアＦの第１のＬＲＵ情報１２６：  ａｂｃｘｙｚ
第２のＬＲＵ情報１２９：  ＡＣＢＦＤＥ
【００８７】
まず、ステップＢ１では、コアＡのアクセスが全ての他コアキャッシュでミスする。
ステップＢ２では、第２のＬＲＵ情報１２９から、自コアＡが最近最もアクセスしていないため追い出ししない。
ステップＢ３では、ＬＲＵ更新処理により、キャッシュＡのエントリｂを最新に、コアＡに対応する第１のＬＲＵ情報を更新し、キャッシュＡが最新となるように第２のＬＲＵ情報１２９を更新する。
ステップＢ６では、キャッシュＡのエントリｂに上書きする。
【００８８】
以下に、更新後の第１及び第２のＬＲＵ情報を示す。第１及び第２のＬＲＵ情報は、古→新の順にエントリを示す。
コアＡの第１のＬＲＵ情報１２１：  ｘａｃｚｙｂ
コアＢの第１のＬＲＵ情報１２２：  ａｂｘｚｙｃ
コアＣの第１のＬＲＵ情報１２３：  ｂｘｃｚｙａ
コアＤの第１のＬＲＵ情報１２４：  ａｂｃｘｙ
コアＥの第１のＬＲＵ情報１２５：  ａｂｘｙｚ
コアＦの第１のＬＲＵ情報１２６：  ａｂｃｘｙｚ
第２のＬＲＵ情報１２９：  ＣＢＦＤＥＡ
【００８９】
次に、ステップＢ１では、再度、コアＡのアクセスが全ての他コアキャッシュでミスする。
ステップＢ２では、第２のＬＲＵ情報１２９から、他コアが最近最もアクセスしていないため追い出しが発生する。
ステップＢ４では、キャッシュＡのエントリｂとキャッシュＣのエントリｂを交換する。
ステップＢ５では、ＬＲＵ更新処理により、キャッシュＡのエントリｂを最新に、キャッシュＣのエントリｂを最新に各々のコアＡ，コアＣに対応する第１のＬＲＵ情報を更新し、キャッシュＡが最新に、キャッシュＣが2番目に最新になるように第２のＬＲＵ情報１２９を更新する。
ステップＢ６では、キャッシュＡのエントリｂに上書きする。
【００９０】
以下に、更新後の第１及び第２のＬＲＵ情報を示す。第１及び第２のＬＲＵ情報は、古→新の順にエントリを示す。
コアＡの第１のＬＲＵ情報１２１：  ｘａｃｚｙｂ
コアＢの第１のＬＲＵ情報１２２：  ｃａｂｘｚｙ
コアＣの第１のＬＲＵ情報１２３：  ｘｃｚｙａｂ
コアＤの第１のＬＲＵ情報１２４：  ａｂｃｘｙ
コアＥの第１のＬＲＵ情報１２５：  ａｂｘｙｚ
コアＦの第１のＬＲＵ情報１２６：  ａｂｃｘｙｚ
第２のＬＲＵ情報１２９：  ＢＦＤＥＣＡ
【００９１】
以上のように、追い出し動作判定は、第２のＬＲＵ情報１２９で最古のコアに追い出す。本実施形態では、第２のＬＲＵ情報１２９は最新のアクセスのみしか保持していないが、完全な最古順を保持しても構わない。最新のアクセスのみしか保持しない理由は、ビット数削減のためである。また、第２のＬＲＵ情報１２９の更新時に追い出し先コアを２番目に新しいものに更新して、追い出し先を持ち回りすることで、完全な最古順を保持した場合に比べた性能低下を抑えられる。
【００９２】
図１４のシステムのキャッシュライン交換トラフィックの発生確率は、（全キャッシュのウェイ数−１）／（全キャッシュのウェイ数）である。例えば、３ウェイ４コアの場合には１１／１２となる。自コアが頻繁にアクセスしないエントリでも、最新でない限り交換してしまうため、交換トラフィックが大きい。
【００９３】
これに対し、本実施形態のシステムのキャッシュライン交換トラフィックの発生確率は、（１／（全キャッシュのウェイ数＋ｎ））×（（キャッシュのウェイ数）／（キャッシュのウェイ数＋ｎ））である。例えば、３ウェイ４コア、ｎ＝１の場合には（１／４）×（３／４）＝３／１６となる。自コアが連続してアクセスし、かつ、ヒットした他コアキャッシュで現在あまり使っていないエントリのみ交換するので、交換トラフィックが小さくなる。
【００９４】
また、図１５のシステムのＬＲＵ情報は、（第１のＬＲＵ情報）＋（第２のＬＲＵ情報）により、以下のビット数となる。
３ウェイ４コア：  ３×４＋２×１２＝３６ビット
４ウェイ４コア：  ６×４＋２×１６＝５６ビット
３ウェイ８コア：  ３×８＋２×２４＝１０６ビット
４ウェイ８コア：  ６×８＋３×３２＝１４４ビット
【００９５】
これに対し、本実施形態のＬＲＵ情報は、（第１のＬＲＵ情報）＋（第２のＬＲＵ情報）により、以下のビット数となる。
３ウェイ４コア：  ６×４＋６＝３０ビット
４ウェイ４コア：  １０×４＋６＝４６ビット
３ウェイ８コア：  ６×８＋２８＝７６ビット
４ウェイ８コア：  １０×８＋２８＝１０８ビット
【００９６】
本実施形態は、ＬＲＵ情報のビット数を少なくすることができる。特に、コア数又はウェイ数が多くなった場合にビット数の減少効果が大きい。
【００９７】
以上のように、本実施形態のキャッシュシステムは、例えば図１に示すように、複数の処理装置（コア）１０１〜１０３と、前記複数の処理装置１０１〜１０３に一対一に接続された複数のキャッシュ１１１〜１１３と、前記複数のキャッシュ１１１〜１１３に接続され、前記複数のキャッシュ１１１〜１１３間のデータ転送を制御するコントローラ１２０と、前記処理装置毎に自己のキャッシュ内のエントリ及び他のキャッシュの使用古さ順を示す第１の情報１２１〜１２３を記憶する情報メモリとを有する。
【００９８】
例えば図６〜図９に示すように、前記コントローラ１２０は、前記処理装置１０１が要求したデータが、自己のキャッシュ１１１でミスし、他のキャッシュ１１２でヒットした場合に、前記第１の情報１２１を基に前記自己のキャッシュ１１１のエントリ及び前記ヒットした他のキャッシュ１１２のエントリを交換する。
【００９９】
図２に示すように、第１の情報１２１〜１２３は、前記処理装置１０１〜１０３毎に自己のキャッシュ内のエントリａ，ｂ，ｃ及び複数の他のキャッシュがグループ化された一のエントリｘの使用古さ順を示す情報である。また、図４に示すように、第１の情報１２１〜１２６は、前記処理装置１０１〜１０６毎に自己のキャッシュ内のエントリａ，ｂ，ｃ及び複数の他のキャッシュがグループ化された複数のエントリｘ，ｙ，ｚの使用古さ順を示す情報である。
【０１００】
例えば図６〜図９に示すように、前記コントローラ１２０は、前記処理装置１０１が要求したデータが、自己のキャッシュ１１１でミスし、他のキャッシュ１１２でヒットした場合、前記複数の他のキャッシュがグループ化されたエントリｘが最新であるときに、前記自己のキャッシュ１１１のエントリ及び前記ヒットした他のキャッシュ１１２のエントリを交換する。
【０１０１】
より具体的には、前記コントローラ１２０は、前記処理装置１０１が要求したデータが、自己のキャッシュ１１１でミスし、他のキャッシュ１１２でヒットした場合、前記複数の他のキャッシュがグループ化されたエントリｘが最新であり、かつ前記ヒットした他のキャッシュ１１２のエントリｃが最新でないときに、前記自己のキャッシュ１１１のエントリｂ及び前記ヒットした他のキャッシュ１１２のエントリｃを交換する。
【０１０２】
前記第１の情報１２１〜１２３は、前記処理装置１０１が要求したデータが、自己のキャッシュ１１１でミスし、他のキャッシュ１１２でヒットした場合、前記複数の他のキャッシュがグループ化されたエントリｘが最新でなく、又は前記ヒットした他のキャッシュ１１２のエントリｃが最新であるときに、前記ヒットした他のキャッシュ１１２に対応する処理装置１０２において前記ヒットした他のキャッシュ１１２のエントリｃが最新であるときには、そのエントリｃが２番目に新しい順番に更新され、２番目に新しいエントリｘが最新の順番に更新される。
【０１０３】
図２に示すように、前記情報メモリは、前記複数の処理装置１０１〜１０３間での自己のキャッシュに対する使用古さ順を示す第２の情報１２９を記憶する。
【０１０４】
例えば図１０〜図１３に示すように、前記コントローラ１２０は、前記処理装置１０１が要求したデータが、前記複数のキャッシュ１１１〜１１３すべてでミスした場合、前記第２の情報１２９を基に前記自己のキャッシュ１１１のエントリａを他のキャッシュ１２３のエントリｂに移動し、主記憶装置（メインメモリ）又は前記複数のキャッシュより下位階層のキャッシュ（２次キャッシュ）１３０から読み出したデータを前記移動した自己のキャッシュ１１１のエントリａに上書きする。
【０１０５】
より具体的には、前記コントローラ１２０は、前記処理装置１０１が要求したデータが、前記複数のキャッシュ１１１〜１１３すべてでミスした場合、前記要求した処理装置１０１が自己のキャッシュ１１１を最近最も使用していない処理装置でないときに、前記自己のキャッシュ１１１のエントリａを他のキャッシュ１１３のエントリｂに移動し、主記憶装置又は前記複数のキャッシュより下位階層のキャッシュ１３０から読み出したデータを前記移動した自己のキャッシュ１１１のエントリａに上書きする。
【０１０６】
なお、上記実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【０１０７】
本発明の実施形態は、例えば以下のように種々の適用が可能である。
【０１０８】
（付記１）
複数の処理装置と、
前記複数の処理装置に一対一に接続された複数のキャッシュと、
前記複数のキャッシュに接続され、前記複数のキャッシュ間のデータ転送を制御するコントローラと、
前記処理装置毎に自己のキャッシュ内のエントリ及び他のキャッシュの使用古さ順を示す第１の情報を記憶する情報メモリと
を有することを特徴とするキャッシュシステム。
（付記２）
前記コントローラは、前記処理装置が要求したデータが、自己のキャッシュでミスし、他のキャッシュでヒットした場合に、前記第１の情報を基に前記自己のキャッシュのエントリ及び前記ヒットした他のキャッシュのエントリを交換することを特徴とする付記１記載のキャッシュシステム。
（付記３）
前記第１の情報は、前記処理装置毎に自己のキャッシュ内のエントリ及び複数の他のキャッシュがグループ化された一又は複数のエントリの使用古さ順を示す情報であることを特徴とする付記１記載のキャッシュシステム。
（付記４）
前記コントローラは、前記処理装置が要求したデータが、自己のキャッシュでミスし、他のキャッシュでヒットした場合、前記複数の他のキャッシュがグループ化されたエントリが最新であるときに、前記自己のキャッシュのエントリ及び前記ヒットした他のキャッシュのエントリを交換することを特徴とする付記３記載のキャッシュシステム。
（付記５）
前記コントローラは、前記処理装置が要求したデータが、自己のキャッシュでミスし、他のキャッシュでヒットした場合、前記複数の他のキャッシュがグループ化されたエントリが最新であり、かつ前記ヒットした他のキャッシュのエントリが最新でないときに、前記自己のキャッシュのエントリ及び前記ヒットした他のキャッシュのエントリを交換することを特徴とする付記３記載のキャッシュシステム。
（付記６）
前記第１の情報は、前記処理装置が要求したデータが、自己のキャッシュでミスし、他のキャッシュでヒットした場合、前記複数の他のキャッシュがグループ化されたエントリが最新でなく、又は前記ヒットした他のキャッシュのエントリが最新であるときに、前記ヒットした他のキャッシュに対応する処理装置において前記ヒットした他のキャッシュのエントリが最新であるときには、そのエントリが２番目に新しい順番に更新され、２番目に新しいエントリが最新の順番に更新されることを特徴とする付記５記載のキャッシュシステム。
（付記７）
前記情報メモリは、前記複数の処理装置間での自己のキャッシュに対する使用古さ順を示す第２の情報を記憶することを特徴とする付記１記載のキャッシュシステム。
（付記８）
前記コントローラは、前記処理装置が要求したデータが、前記複数のキャッシュすべてでミスした場合、前記第２の情報を基に前記自己のキャッシュのエントリを他のキャッシュのエントリに移動し、主記憶装置又は前記複数のキャッシュより下位階層のキャッシュから読み出したデータを前記移動した自己のキャッシュのエントリに上書きすることを特徴とする付記７記載のキャッシュシステム。
（付記９）
前記コントローラは、前記処理装置が要求したデータが、前記複数のキャッシュすべてでミスした場合、前記要求した処理装置が自己のキャッシュを最近最も使用していない処理装置でないときに、前記自己のキャッシュのエントリを他のキャッシュのエントリに移動し、主記憶装置又は前記複数のキャッシュより下位階層のキャッシュから読み出したデータを前記移動した自己のキャッシュのエントリに上書きすることを特徴とする付記８記載のキャッシュシステム。
【図面の簡単な説明】
【０１０９】
【図１】本発明の実施形態による共有分散キャッシュシステムの構成例を示す図である。
【図２】図１の第１のＬＲＵ情報及び第２のＬＲＵ情報の詳細を示す図である。
【図３】本発明の実施形態による共有分散キャッシュシステムの他の構成例を示す図である。
【図４】図３の第１のＬＲＵ情報及び第２のＬＲＵ情報の詳細を示す図である。
【図５】本実施形態による共有分散キャッシュシステムにおけるデータロードアクセス動作を示すフローチャートである。
【図６】図５のステップＳ７の交換処理を示すフローチャートである。
【図７】図１及び図２のシステムにおける図６の交換処理の例を示す図である。
【図８】図１及び図２のシステムにおける図６の交換処理の例を示す図である。
【図９】図１及び図２のシステムにおける図６の交換処理の例を示す図である。
【図１０】図５のステップＳ８の追い出し処理を示すフローチャートである。
【図１１】図１及び図２のシステムにおける図１０の追い出し処理の例を示す図である。
【図１２】図１及び図２のシステムにおける図１０の追い出し処理の例を示す図である。
【図１３】図１及び図２のシステムにおける図１０の追い出し処理の例を示す図である。
【図１４】共有分散キャッシュシステムの構成例を示す図である。
【図１５】他の共有分散キャッシュシステムの構成例を示す図である。
【図１６】図１５の共有分散キャッシュシステムにおけるキャッシュエントリ追い出し処理を示すフローチャートである。
【符号の説明】
【０１１０】
１０１〜１０３  コア（処理装置）
１１１〜１１３  キャッシュ
１２０  キャッシュ間接続コントローラ
１２１〜１２３  第１のＬＲＵ情報
１２９  第２のＬＲＵ情報
１３０  メインメモリ
【図１】
0005045334.tif 000002
【図２】
0005045334.tif 000003
【図３】
0005045334.tif 000004
【図４】
0005045334.tif 000005
【図５】
0005045334.tif 000006
【図６】
0005045334.tif 000007
【図７】
0005045334.tif 000008
【図８】
0005045334.tif 000009
【図９】
0005045334.tif 000010
【図１０】
0005045334.tif 000011
【図１１】
0005045334.tif 000012
【図１２】
0005045334.tif 000013
【図１３】
0005045334.tif 000014
【図１４】
0005045334.tif 000015
【図１５】
0005045334.tif 000016
【図１６】
0005045334.tif 000017