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