(57)【特許請求の範囲】
【請求項１】
各セットが２つ以上のキャッシュウェイで構成されセット・アソシアティブ方式に基づいて動作し、キャッシュミスの発生時に置換ウェイにキャッシュブロックのデータを置換するキャッシュメモリにおいて、
メモリアクセス要求により特定されるキャッシュブロックの各キャッシュウェイに対応させて、前記メモリアクセス要求の要求元であるプロセス又は仮想マシンを識別する要求元ＩＤ情報を記憶する要求元ＩＤ情報記憶部と、
実行中のプロセスの切り替え時に退避されるコンテキストに含まれる最大ブロック数又は実行中の仮想マシンの情報が記録される仮想マシン構造体に含まれる最大ブロック数を、要求元毎に割り当てることができるキャッシュウェイの最大値として指定する最大ブロック数指定部と、
キャッシュミスの発生時に、前記メモリアクセス要求により特定されるキャッシュセット中のキャッシュブロックのうち、前記メモリアクセス要求に付加された要求元ＩＤ情報と同じ要求元ＩＤ情報を持つキャッシュブロックのブロック数と、前記メモリアクセス要求に付加された要求元ＩＤ情報により識別される要求元に対して指定された最大ブロック数とを比較する比較部と、
キャッシュミスの発生時に、前記比較部による比較結果に応じて、前記メモリアクセス要求により特定されるキャッシュセット中のキャッシュブロックのうち、前記メモリアクセス要求に付加された要求元ＩＤ情報以外の要求元ＩＤ情報が対応付けられているキャッシュブロックが格納されているキャッシュウェイか、前記メモリアクセス要求に付加された要求元ＩＤ情報と同じ要求元ＩＤ情報が対応付けられているキャッシュブロックが格納されているキャッシュウェイの何れかを、置換ウェイの候補である置換ウェイ候補に決定する置換ウェイ候補決定部と、
前記置換ウェイ候補から置換ウェイを選択する置換ウェイ選択部と、
前記メモリアクセス要求に対してキャッシュミスが発生した場合に、該メモリアクセス要求により特定されるキャッシュブロックの中の、選択された置換ウェイに対応して前記要求元ＩＤ情報記憶部に記憶されている要求元ＩＤ情報を、前記メモリアクセス要求に付加された要求元ＩＤ情報によって更新する要求元ＩＤ情報更新部と、
を含むことを特徴とするキャッシュメモリ。
【請求項２】
前記最大ブロック数指定部は、前記メモリアクセス要求を発行するプロセスのソフトウェアからの指示に基づいて、前記最大ブロック数を指定する、
ことを特徴とする請求項１に記載のキャッシュメモリ。
【請求項３】
前記最大ブロック数指定部は、前記要求元毎に前記キャッシュメモリにおけるキャッシュミスの回数を測定し、該キャッシュミスの回数に基づいて前記最大ブロック数を指定する、
ことを特徴とする請求項１に記載のキャッシュメモリ。
【請求項４】
前記最大ブロック数指定部は、前記メモリアクセス要求を発行する仮想マシンからの指示に基づいて、前記最大ブロック数を指定する、
ことを特徴とする請求項１に記載のキャッシュメモリ。
【請求項５】
前記最大ブロック数指定部は、前記要求元毎の最大ブロック数の合計数が前記キャッシュメモリにおけるキャッシュウェイ数よりも大きくなるように、前記要求元毎の最大ブロック数を設定可能とする、
ことを特徴とする請求項１乃至４の何れか１項に記載のキャッシュメモリ。
【請求項６】
前記要求元ＩＤ情報更新部は、前記メモリアクセス要求によってキャッシュヒットが発生したときに、前記メモリアクセス要求により特定される前記キャッシュブロックが格納されているキャッシュウェイに対応して前記要求元ＩＤ情報記憶部に記憶されている要求元ＩＤ情報を、前記メモリアクセス要求に付加された要求元ＩＤ情報によって更新する
ことを特徴とする請求項１乃至５の何れか１項に記載のキャッシュメモリ。
【請求項７】
前記メモリアクセス要求を発行する複数のプロセッサが複数のグループにグループ分けされ、
前記要求元は該グループ毎に定義され、
前記プロセッサが前記メモリアクセス要求を発行するときに、該プロセッサが属するグループに対応して定義されている要求元ＩＤ情報を該メモリアクセス要求に付与する、
ことを特徴とする請求項１乃至５の何れか１項に記載のキャッシュメモリ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ技術に関する。
【背景技術】
【０００２】
近年のプロセッサの動作周波数の向上により、相対的にメモリアクセス遅延時間が長くなり、メモリアクセスの遅延時間がシステム全体の性能を左右するに至っている。多くのプロセッサは、メモリアクセス遅延時間を隠蔽する目的で、キャッシュメモリと呼ぶ小容量の高速メモリを搭載している。
【０００３】
図１６に、セットアソシアティブキャッシュメモリ方式のキャッシュメモリの動作概要を示す。
キャッシュメモリ１６０１は、複数のセットで構成されており、各セットは、例えば＃１〜＃４の複数のキャッシュウェイ（以降、単に「ウェイ」と略すこともある）１６０２に分けて管理されている。即ち、図１６の例は、４ウェイのセットアソシアティブ方式のキャッシュメモリを示している。
【０００４】
また、各キャッシュウェイ１６０２は、＃１〜＃ｎの複数のキャッシュブロック（以降、単に「ブロック」と略すこともある）１６０３から構成されている。例えば、ｎ＝１０２４である。
【０００５】
各キャッシュブロック１６０３は、有効か否かを示す有効フラグ、タグ、及びデータから構成されている。データサイズは例えば、有効フラグが１ビット、タグが１５ビット、データが１２８バイトである。
【０００６】
キャッシュメモリ１６０１のデータサイズは、例えば、「キャッシュブロックのデータサイズ×キャッシュインデックス数×キャッシュウェイ数＝１２８バイト×１０２４インデックス×４ウェイ」で計算され、例えば、１０２４バイトを１キロバイトとして、５１２キロバイトである。
【０００７】
一方、プログラムによって指定されるメモリアクセスのためのアドレス１６０５は、３２ビットで指定され、下位から７ビットがキャッシュブロック内オフセット、１０ビットがインデックス、上位１５ビットがタグとして使用される。
【０００８】
以上の構成により、今、アドレス１６０５に対するデータ読出しが指定されると、アドレス１６０５内の１０ビットのインデックスが示すキャッシュセットが選択される。
その結果、＃１〜＃４の各キャッシュウェイ１６０２から、対応するインデックスの各キャッシュブロック１６０３（＃ｉ）が読み出され、それぞれ＃１〜＃４のコンパレータ１６０４に入力される。
【０００９】
＃１〜＃４のコンパレータ１６０４は、読み出された各キャッシュブロック１６０３（＃ｉ）内のタグ値と指定されたアドレス１６０５内のタグ値との一致／不一致を検出する。この結果、＃１〜＃４のうちタグ値の一致が検出されたコンパレータ１６０４において読み出されているキャッシュブロック１６０３（＃ｉ）が、キャッシュヒットしたということになり、タグ値の一致が検出されたウェイのデータが読み出される。これにより、主記憶メモリからの読出しよりも高速なデータ読出しが実現される。
【００１０】
どのコンパレータ１６０４においてもタグ値の一致が検出されなかった、又はタグ値の一致が検出されても有効フラグが対応するキャッシュブロックの無効を示していたら、キャッシュヒットにはならず、主記憶メモリ上のアドレス１６０５からデータが読み出される。
【００１１】
一方、アドレス１６０５に対するデータ書込みが指定されると、読出しの場合と同様に、アドレス１６０５内の１０ビットのインデックスとタグマッチ回路により、＃１〜＃ｎのブロック番号のうちの１つ＃ｉが指定される。
【００１２】
次に、キャッシュミス発生時には、図１７に示されるように、置換ウェイ選択回路１７０１が、＃１〜＃４の各キャッシュウェイ１６０２の指定されたブロック番号＃ｉに対応する４つのキャッシュブロック１６０３（＃ｉ）のうちの１つを選択し、４ビット値の選択信号を出力する。この場合、上記４つのキャッシュブロック１６０３（＃ｉ）のうち、未使用、言い換えるとタグが未指定のウェイ、又は有効フラグが無効を示しているウェイが選択される。どのウェイも使用中の場合には、所定のアルゴリズムによって決定したウェイが選択される。４ビットの選択信号は、＃１〜＃４の４つのウェイのうちの１つを選択するためのデータ信号である。選択信号の４ビットのうち値”１”が設定されているビット位置に対応するウェイが選択される。このようにして置換ウェイ選択回路１７０１から出力された選択信号に基づいて、指定されたブロック番号＃ｉに対して選択し得る＃１〜＃４の４つのウェイのうち、選択信号が示すウェイに対応するキャッシュブロック１６０３に、データが書き込まれる。
【００１３】
どのブロックも使用中の場合に、＃１〜＃４の４つのキャッシュウェイ１６０２のうちどれを選択するかは、例えばＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）アルゴリズムによって決定される。ＬＲＵアルゴリズムでは、使われてから最も長い時間が経っているキャッシュブロックのデータが選択され、選択されたデータが置換される（追い出される）。
【００１４】
上述の動作説明から理解されるように、アクセスするデータの範囲が広い場合に、複数のデータにおいてアドレス１６０５のインデックスの値が一致し、それらのデータでキャッシュの競合が発生する可能性がある。このような場合であっても、セットアソシアティブ方式のキャッシュメモリにおいては、インデックスによって＃１〜＃ｎのうち同じキャッシュセットが指定されたとしても、全てのウェイが使用されているとは限らないため、複数のウェイからキャッシュブロックを選択できる。このため、例えば図１６の４ウェイ構成のキャッシュメモリ１６０１では、同じインデックスを持つ最大で４つまでのデータに対応することができる。
【００１５】
ここで、近年では、マルチプロセス環境や仮想マシン利用環境の拡大により、複数のＣＰＵ（中央演算処理装置）や複数のコアプロセッサ、又は複数のスレッドが図１６及び図１７に示されるような構成を有するキャッシュメモリを共有して使用するというケースが多くなってきている。この場合に、共有されるキャッシュメモリの領域をどのように分割管理するかということが課題となる。
【００１６】
この課題を解決するために、いくつかの手法が提案されている。
第１の手法として、モディファイドＬＲＵリプレイスメントと呼ばれる技術が知られている。この技術では、キャッシュウェイ単位で、プロセスで共有されるキャッシュ領域が分割される。そして、システム上で動作する全プロセスの各々について、プロセスが使用しているキャッシュブロック数がカウントされる。キャッシュブロック置換時に、カウントしたキャッシュブロック数が指定したキャッシュブロック数を越えない場合には、他のプロセスが用いているキャッシュブロックが置換される。同一セット内に置換できるキャッシュブロックが存在しない場合には、ランダムに置換候補のキャッシュブロックが選択される。
【００１７】
第２の手法として、コラムキャッシングと呼ばれる技術が知られている。この技術では、キャッシュウェイ単位でプロセスで共有されるキャッシュ領域が分割される。そして、各プロセスは、置換候補となるウェイのビットベクトルを保有する。キャッシュウェイ置換時に、ビットベクトルで指定されたウェイから置換候補が選択される。
【００１８】
第３の手法では、共有されたキャッシュメモリを動的に区分する技術が知られている。この技術では、キャッシュメモリのタグ（図１６参照）にパーティションＩＤ（ＰＩＤ）が追加される。キャッシュメモリがアクセスされる場合に、常にアドレスと共にＰＩＤが提供される。アドレスと共に提供されたＰＩＤは、アドレスによって指定されるタグと共に読み出されたＰＩＤと比較される。キャッシュにデータが格納される際に、アドレスと共に提供されたＰＩＤと同一のＰＩＤをタグと共に持つキャッシュウェイが置換される。
【００１９】
第４の手法として、セットアソシアティブ方式のキャッシュメモリを構成するキャッシュウェイ毎に、処理ユニット識別情報と比較器を設ける方式が知られている。この技術では、キャッシュウェイが置換される際、対象セット内の処理ユニット識別情報がアクセスを発生させたユニットの識別情報と一致するブロック数が数えられ、数えられたブロック数と上限ブロック数とが比較される。数えられたブロック数が予め決められた上限ブロック数を越えるときには、アクセスを発生させたユニットの識別情報と同じ処理ユニット識別情報を持つウェイが置換される。
【００２０】
第５の手法として、キャッシュウェイ毎に属性記憶タグを備える技術が知られている。この技術では、属性記憶タグには、ウェイ置換を行ったときの更新時間情報や優先度情報が記憶される。これらの属性値に応じて、ウェイの置換候補が選択される。
【００２１】
下記先行技術文献は、キャッシュメモリに関連する技術を開示している。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】特開２０００−９００５９号公報
【特許文献２】特開２００１−２８２６１７号公報
【特許文献３】特開平６−１４９６７４号公報
【非特許文献】
【００２３】
【非特許文献１】G.E. Suh, S. Devadas, and L. Rudolph. A new memory monitoring scheme for memory-aware scheduling and partitioning. High-Performance Computer Architecture, 2002. Proceedings. Eighth International Symposium on, pages 117-128, 2-6 Feb. 2002.
【発明の概要】
【発明が解決しようとする課題】
【００２４】
しかし、上述した各手法は、以下に示されるような問題点を有している。
第１の手法では、全プロセスについて使用しているキャッシュブロック数を正しく把握する必要があるため、マルチプロセス環境においては実装することが困難である。
【００２５】
第２の手法では、マルチプロセス環境で、互いにビットベクトルが重ならないようにするための制御が必要となる。例えば、４ウェイセットアソシアティブ方式のキャッシュメモリにおいて、プロセスＡ及びプロセスＢのビットベクトルが共に‘１１００’である場合、何れのプロセスも２ウェイしか使用せず、残りの２ウェイは未使用状態となる。共有されるキャッシュメモリを最大限に利用するためには、最も良い組み合わせをオペレーティングシステムが認識してプロセススケジューリングしなればならない。
【００２６】
第３の手法では、タグに固定的にＰＩＤを割り当てるため、動的に分割状態を変更するためには、タグ情報を一括して書き換える必要があり大きなオーバヘッドを伴う。また、マルチプロセス環境等においてプロセスや仮想マシンごとに割り当てを変えることができない。
【００２７】
第４の手法では、処理ユニット識別情報は、物理的なプロセッサごとの判定しかできないため、プロセスや仮想マシンといった論理的なプログラム単位でのウェイ数制御を行うことができない。また、第４の手法では、処理ユニット識別情報の比較器がすべてのウェイに付随しているため、この技術を数ＭＢ以上の記憶容量を有するキャッシュメモリに適用しようとした場合、ハードウェア量が膨大となってしまう。更に、第４の手法では、処理ユニット識別情報が一致するウェイ数が予め決められたウェイ数に満たないときには、置換ウェイがセット内で格納可能なすべてのウェイの中から選択される。そのため、ＬＲＵ制御において、或る処理ユニットに割り当てられたウェイが最も古いデータとなり続けた場合に、ある処理ユニットに割り当てられるウェイ数が永久に１ウェイとなり、上限ブロック数に達しないことがある。加えて、第４の手法では、キャッシュヒット時についての開示がなく、ヒット情報をＬＲＵ情報に反映させることができない。
【００２８】
第５の手法では、ウェイごとに更新されたときの時間を記録しておくためのハードウェアやタイマ等の別ユニットも必要となるなど、ハードウェア追加が多い。また、第５の手法は、マルチプロセス環境に適用することができず、動的に割当て量を変更するために属性タグを書き換えるなどのオーバヘッドが大きい。
【００２９】
以上のように、上述した第１から第５の従来技術では、ハードウェア追加が多くて実装が困難となったり、マルチプロセス環境や仮想マシン利用環境において効率的な動作が困難であるという問題点がある。
【００３０】
そこで本発明は、少ないハードウェアコストで、マルチプロセス環境や仮想マシン利用環境にも適用可能なキャッシュメモリの分割管理技術を提供することを目的とする。
【課題を解決するための手段】
【００３１】
本発明の一態様は、各セットが２つ以上のキャッシュウェイで構成されセット・アソシアティブ方式に基づいて動作し、キャッシュミスの発生時に置換ウェイにキャッシュブロックのデータを置換するキャッシュメモリとして実現され、以下の構成を有する。
【００３２】
要求元ＩＤ情報記憶部は、メモリアクセス要求により特定されるキャッシュブロックの各キャッシュウェイに対応させて、メモリアクセス要求の要求元を識別する要求元ＩＤ情報を記憶する。
【００３３】
置換ウェイ候補決定部は、キャッシュミスの発生時に、メモリアクセス要求に付加された要求元ＩＤ情報と、メモリアクセス要求により特定されるキャッシュブロックに対応して要求元ＩＤ情報記憶部に記憶されている要求元ＩＤ情報とに基づいて、置換ウェイの候補である置換ウェイ候補を決定する。
【００３４】
置換ウェイ選択部は、置換ウェイ候補から置換ウェイを選択する。
要求元ＩＤ情報更新部は、メモリアクセス要求に対してキャッシュミスが発生した場合に、メモリアクセス要求により特定されるキャッシュブロックの中の、選択された置換ウェイに対応して要求元ＩＤ情報記憶部に記憶されている要求元ＩＤ情報を、メモリアクセス要求に付加された要求元ＩＤ情報によって更新する。
【発明の効果】
【００３５】
少ないハードウェアの追加で、プロセッサ単位、プロセス単位、スレッド単位、又は仮想マシン単位などの要求元単位に対応させて、キャッシュメモリ領域をウェイ単位で任意に分割することが可能となる。
【００３６】
この結果、キャッシュメモリの性能の最適化を行ったり、プロセス間や仮想マシン間のキャッシュメモリ上での競合をコントロールすることが可能となり、プロセッサの実効性能を向上させることが可能となる。
【図面の簡単な説明】
【００３７】
【図１】キャッシュメモリの実施形態の構成図である。
【図２】キャッシュメモリの実施形態のハードウェア構成図である。
【図３】実施形態の動作説明図（その１）である。
【図４】実施形態の動作説明図（その２）である。
【図５】実施形態の動作説明図（その３）である。
【図６】キャッシュメモリの実施形態が適用されるコンピュータシステムの構成例を示す図である。
【図７】置換ウェイ制御回路の第１の構成例を示す図である。
【図８】置換ウェイマスク生成回路の構成例を示す図である。
【図９】実施形態が適用されるオペレーティングシステムのプロセス構造体の例を示す図である。
【図１０】置換ウェイ制御回路の第２の構成例を示す図である。
【図１１】ヒットウェイ制御回路の構成例を示す図である。
【図１２】アプリケーションのソースコードから実行バイナリを生成する流れを示す図である。
【図１３】置換ウェイ制御回路の第３の構成例を示す図である。
【図１４】仮想マシンに対してキャッシュメモリを制御するためのデータ構造体の例を示す図である。
【図１５】仮想マシンに対するキャッシュメモリの制御動作の説明図である。
【図１６】キャッシュメモリの構成例を示す図である。
【図１７】置換ウェイ選択回路の説明図である。
【発明を実施するための形態】
【００３８】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。
図１は、キャッシュメモリの実施形態の構成図である。なお、図１の構成は一例であり、本発明は図１の構成に限定されるものではない。
【００３９】
本実施形態によるキャッシュメモリ１０１は、４ウェイのセット・アソシアティブ方式のキャッシュメモリとして実現される。
キャッシュメモリ１０１は、１０２（＃１）〜１０２（＃４）の複数のキャッシュウェイ１０２に分けて管理される。各キャッシュウェイ１０２は、１０３（＃１）〜１０３（＃ｎ）の複数のキャッシュブロック１０３を有する。例えば、ｎ＝１０２４である。
【００４０】
図１の実施形態においては、各キャッシュブロック１０３は、有効フラグ（１ビット）、タグ（１５ビット）、データ（１２８バイト）に加えて、コアＩＤ（要求元ＩＤ情報）を有する。コアＩＤは、１ビット又は２ビットで構成される。１ビットの場合は、コアＩＤの値は０か１の何れかの値を取り得る。２ビットの場合は、コアＩＤは、０〜２の３通り又は０〜３の４通りの値を取り得る。即ち、ブロックのデータサイズは１２８バイト、有効フラグ、タグ、コアＩＤを加えたサイズは、１ビット＋１５ビット＋１２８バイト＋１又は２ビットである。
【００４１】
キャッシュメモリ１０１のデータサイズは、「キャッシュブロックのデータサイズ×キャッシュインデックス数×キャッシュウェイ数＝１２８バイト×１０２４インデックス×４ウェイ」で計算され、例えば、１０２４バイトを１キロバイトとして、５１２キロバイトである。
【００４２】
一方、プログラムによって指定されるメモリアクセスのためのアドレス１０５は、３２ビットで指定され、下位から７ビットがキャッシュブロック内オフセット、１０ビットがインデックス、上位１５ビットがタグとして使用される。
【００４３】
以上の構成により、アドレス１０５に対するデータの読み出し又は書き込みのアクセスが指定されると、アドレス１０５内の１０ビットのインデックスで指定されたセットの中から、（＃１）〜（＃ｎ）のブロック番号のうちの１つが指定される。
【００４４】
その結果、１０２（＃１）〜１０２（＃４）の各キャッシュウェイ１０２から、指定された各キャッシュブロック１０３（＃ｉ）が読み出され、それぞれ１０４（＃１）〜１０４（＃４）のコンパレータ１０４に入力する。
【００４５】
１０４（＃１）〜１０４（＃４）のコンパレータ１０４は、読み出された各キャッシュブロック１０３（＃ｉ）内のタグ値と、指定されたアドレス１０５内のタグ値との一致／不一致を検出する。この結果、１０４（＃１）〜１０４（＃４）のうちタグ値の一致が検出されたコンパレータ１０４において読み出されているキャッシュブロック１０３（＃ｉ）が、キャッシュヒットしたということになり、キャッシュブロック１０３（＃ｉ）に対してデータが読み書きされる。
【００４６】
どのコンパレータ１０４においてもタグ値の一致が検出されなかった、又はタグ値の一致が検出されても有効フラグが無効を示していたら、キャッシュヒットにはならず、主記憶メモリ上のアドレス１０５がアクセスされる。
【００４７】
図２は、キャッシュメモリ１０１に関する図１の機能構成に対応するハードウェア構成を示す図である。
図１の各キャッシュブロック１０３を構成するデータ、タグ、及びコアＩＤは、図２ではそれぞれデータＲＡＭ２０１、タグＲＡＭ２０２、及びコアＩＤ・ＲＡＭ（要求元ＩＤ情報記憶部）２０３の３領域に分割して記憶される。データＲＡＭ２０１、タグＲＡＭ２０２、及びコアＩＤ・ＲＡＭ２０３は、それぞれ４つの領域に分割され、各ＲＡＭの各領域はそれぞれ、図１の１０２（＃１）〜１０２（＃４）のキャッシュウェイ１０２に対応する。なお、図２の例では、有効フラグは、タグＲＡＭ２０２にタグ値が記憶されているか否かで代用されているが、別途有効フラグ用のＲＡＭを設けてもよい。また、コアＩＤ・ＲＡＭ２０３は、タグＲＡＭ２０２と一体として実現されてもよい。
【００４８】
今、アドレス１０５に対するデータアクセスが指定されると、アドレス１０５内の１０ビットのインデックスにより、キャッシュセットが指定される。
その結果、タグＲＡＭ２０２内の１０２（＃１）〜１０２（＃４）の各キャッシュウェイ１０２から、タグ値が読み出され、それぞれ１０４（＃１）〜１０４（＃４）のコンパレータ１０４に入力する。
【００４９】
１０４（＃１）〜１０４（＃４）のコンパレータ１０４は、タグＲＡＭ２０２から読み出された各キャッシュウェイ１０２（＃１）〜１０２（＃４）に対応するキャッシュブロック１０３（＃ｉ）のタグ値と、指定されたアドレス１０５内のタグ値との一致／不一致を検出する。そして、キャッシュヒットが発生した場合、４つのコンパレータ１０４からは、タグ値の一致が検出されたコンパレータ１０４の出力のみが１となる、４ビットのヒットウェイ信号が出力される。
【００５０】
キャッシュヒットが発生した場合であってメモリアクセス要求が読出し要求の場合には、次のようなリード動作が実行される。即ち、データＲＡＭ２０１において、アドレス１０５内の１０ビットのインデックスにより指定されるキャッシュセット１０３（＃ｉ）から、１０２（＃１）〜１０２（＃４）の各キャッシュウェイ１０２に対応する４つのデータ値がセレクタ２０４に読み出される。また、コアＩＤ・ＲＡＭ２０３において、指定されたキャッシュセット１０３（＃ｉ）から、１０２（＃１）〜１０２（＃４）の各キャッシュウェイ１０２に対応する４つのコアＩＤ値がセレクタ２０５に読み出される。そして、セレクタ２０４及び２０５からは、タグ値の一致が検出されたコンパレータ１０４からのヒットウェイ信号によって、タグ値一致が検出されたコンパレータ１０４に対応するキャッシュウェイのキャッシュブロック１０３（＃ｉ）のデータ値及びコアＩＤが選択されて出力される。
【００５１】
キャッシュヒットが発生した場合であってメモリアクセス要求が書込み要求の場合には、データＲＡＭ２０１内の、アドレス１０５内の１０ビットのインデックスにより指定されるブロック番号＃ｉに対して、次のようなライト動作が実行される。即ち、１０２（＃１）〜１０２（＃４）のキャッシュウェイ１０２のうち、ヒットウェイ信号により指示されるキャッシュウェイのキャッシュブロック１０３（＃ｉ）に、メモリアクセス要求によって指定されるデータ及びコアＩＤが書き込まれる。
【００５２】
以上の構成を有するキャッシュメモリの実施形態の動作について、以下に説明する。
本実施形態によるキャッシュメモリ１０１は、マルチプロセッサシステムにおける、プロセッサ間で共有されているキャッシュメモリとして利用することができる。本実施形態によるキャッシュメモリ１０１は或いは、オンチップマルチプロセッサにおけるチップ上の、コアプロセッサ間で共有されるキャッシュメモリとして利用することができる。本実施形態によるキャッシュメモリ１０１はまた、マルチスレッドプロセッサにおいて、スレッド間で共有されるキャッシュメモリとして利用することもできる。このように、本実施形態によるキャッシュメモリ１０１はアクセスを行う「要求元ユニット」と、「要求元ユニット」が共有するキャッシュメモリという構成を持つ様々なコンピュータシステムに利用することができる。以降の説明では、簡単のため、キャッシュメモリ１０１へのアクセスの「要求元ユニット」をコア（ＣＯＲＥ）と呼ぶこととする。
【００５３】
本実施形態では、図３に示されるように、キャッシュメモリがキャッシュウェイ（セット内でのキャッシュウェイ）を単位として、各コアに分割して割り当てられる。このとき、コア毎に、データを格納することができるキャッシュセット内での上限ブロック数（＝使用できるウェイ数の制限値）を指定できる。上限ブロック数の指定には、例えば、専用レジスタを実装してもよいし、メモリアクセス命令に上限ブロック数を示す情報を付加してもよい。図３に示される例では、４ウェイのセットアソシアティブキャッシュメモリにおいて、ＣＰＵ＃０及びＣＰＵ＃１の各コア（ＣＰＵ）に対して、キャッシュセット内で指定できる上限のブロック数がそれぞれ２になるように、上限ブロック数が設定される。この結果、各コアからアクセスされるデータに対しては、セット内で２ウェイを上限としてキャッシュ動作が実行されることになる。
【００５４】
このとき、図１及び図２に示されるキャッシュメモリ１０１の実施形態では、キャッシュブロック１０３毎に、どのコアからのメモリアクセス要求によりデータが格納されたかを示すコアＩＤが、コアＩＤ・ＲＡＭ２０３に記憶されている。コアＩＤを格納するためのビット幅は、キャッシュメモリを共有するコア数を識別できるビット数でよい。例えば、コアＩＤは、コア数が２個の場合は１ビット、コア数が４個までなら２ビットとなる。このように、コアＩＤを格納するための追加ハードウェア資源（コアＩＤ・ＲＡＭ２０３又はそれと同等のＲＡＭ領域）は、例えばそれぞれ１２８バイトのサイズを有するキャッシュブロック１０３に対して、１又は２ビットと、極めて小さくて済む。
【００５５】
ここで、詳細については図７等で後述するが、キャッシュメモリ１０１におけるキャッシュウェイの置換を制御する制御回路は、メモリアクセスによりキャッシュミスが発生した場合に、以下のようにして置換ウェイを選択する。
【００５６】
ステップ１：アクセスアドレスから導出されたキャッシュセット内の４ウェイからなるキャッシュブロック１０３において、メモリアクセスの要求元コアＩＤと同じコアＩＤを持つキャッシュブロックの個数が、数え上げなどの方法により取得される。
【００５７】
ステップ２：要求元コアＩＤに対応するセット内上限ブロック数と、ステップ１で取得されたキャッシュブロックの個数とが比較される。
【００５８】
ステップ３：ステップ１で取得されたキャッシュブロック数がセット内上限ブロック数に満たない場合、要求元コアＩＤとは異なるコアＩＤを持つウェイが、置換ウェイ候補とされる。逆に、選択ブロック数≧上限ブロック数  である場合は、要求元コアＩＤを持つウェイがそのまま、置換ウェイ候補とされる。
【００５９】
ステップ４：置換ウェイ候補の中で、ＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）などの置換ポリシーに基づいて、置換されるべきウェイ、つまり置換ウェイが選択される。
【００６０】
一方、キャッシュウェイの置換を制御する制御回路は、メモリアクセスによりキャッシュヒットが発生した場合には、単にコアＩＤ・ＲＡＭ２０３（図２）内のコアＩＤを要求元のコアＩＤで書き換える、セット内上限ブロック数に関する比較処理は行わない制御処理を実行する。
【００６１】
この制御処理を実行することは、以下のような利点がある。第１の利点として、他のコアと共有しているデータが存在する場合には、互いにキャッシュメモリを共有し続けることができる。これによって、容量ミスを最小限に抑えることができる。第２の利点として、キャッシュヒットしたときのコアＩＤを記録しておくことによって、次回のアクセス時に記録したコアＩＤを履歴として使用できる。履歴を使用したアクセスとしては例えば、当該コアＩＤに対応するコアが、過去にアクセスしたデータの中からＬＲＵによって置換ウェイを選択するなどの動作を実現することができる。
【００６２】
他のコアＩＤを有するコアに割り当てられているウェイにキャッシュヒットした場合、メモリアクセスの要求元コアＩＤと同じコアＩＤを持つキャッシュウェイの個数が、一時的にセット内上限ブロック数を越えることがある。しかし、これは問題とならない。なぜなら、他のコアからのアクセスによって、セット内上限ブロック数を越えたコアＩＤを有するブロックが書き換えられることによって、各コアＩＤに割り当てられるセット内ブロック数は、いずれそれぞれが要求するブロック数に安定するからである。
【００６３】
更には、本実施形態では、コア毎に任意のセット内上限ブロック数を設定できる。システム動作中は、どのようにセット内上限ブロック数を設定しても、前述したステップ３の制御動作を実行される結果、各コアについてセット内上限ブロック数に近づくようにキャッシュサイズが動的に増減させることができるからである。例えば、図４に示されるように、４ウェイのキャッシュメモリが２つのコアで共有されていて、各コアのセット内上限ブロック数がそれぞれ「３」に設定されたとする。このとき、各コアは、４ウェイのうち２ウェイを互いに奪い合うが、前述したステップ３の制御動作により、上限ブロック数「３」を守りながらシステムは動作することができる。この特徴によって、マルチプロセス環境や複数仮想マシン環境において、各プロセス又は各仮想マシンがそれぞれ必要なブロック数を要求し、それを上限として置換ウェイが決定される。同時にスケジューリングされるプロセスが要求するブロック数の合計が、実装されているキャッシュメモリのウェイ数を超えていても、ウェイの取り合いになるだけで、キャッシュメモリへの割当てが不能になることによるシステム停止などの問題は発生しない。また、コラムキャッシング方式では、不適切なプロセススケジューリングで、複数プロセスが特定のウェイのキャッシュ領域を重複して使用し他のウェイのキャッシュ領域が未使用となってしまうといった、キャッシュ領域の非効率な利用が発生する可能性があった。本実施形態では、このような無駄は発生しない。
【００６４】
また、図５に示されるように、コアＩＤ毎に上限ブロック数を設定するだけでなく、いくつかのコアをグループとしてまとめ、グループごとに上限ブロック数を設定して動作させることも可能である。図５の例では、８ウェイセットアソシアティブ方式のキャッシュメモリにおいて、ＣＰＵ＃０からＣＰＵ＃２の３つのコア（ＣＰＵ）をグループ化したグループ＃０に対して上限ブロック数「６」が設定される。また、＃３のコアのみを含むグループ＃１に対する上限ブロック数として「２」が設定される。例えば、同じ処理を並列に実行するＣＰＵが複数個あった場合に、処理毎にグループ化を行うことにより、ＣＰＵ毎に個別に上限ブロック数を設定する必要がないため、上限ブロック数を指定するための資源の効率化が図れる。また、プログラムの簡略化も図れる。
【００６５】
以上のようにして、図１及び図２の構成を有するキャッシュメモリ１０１の実施形態においては、特定のコアに割り当てられるブロック数を簡単な条件判断で制限することができる。
【００６６】
図１及び図２に示されるキャッシュメモリ１０１における置換ウェイ制御の第１の実施例について、以下に説明する。
図６は、図１及び図２の構成を有するキャッシュメモリ１０１が適用されるコンピュータシステムの構成例を示す図である。
【００６７】
図６の構成例は、チップに、６０１（＃０）及び６０１（＃１）の２つのプロセッサコア６０１、キャッシュメモリ６０２（図１のキャッシュメモリ１０１に対応）、及びＭＡＣ（Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌｌｅｒ：メモリアクセスコントローラ）６０２が内蔵されている。キャッシュメモリ６０２は、５１２キロバイトで４ウェイセットアソシアティブ構成を有し、ウェイサイズは１２８バイトである。図６の構成例では、２つのプロセッサコア６０１間で１つのキャッシュメモリ６０２が共有され、各プロセッサコア６０１に対して、キャッシュメモリ６０２のセット内ウェイを、任意に分割して与えることが可能である。
【００６８】
各プロセッサコア６０１は、３３ビットのアドレスバス６０５と３２ビットのデータバス６０６によって、キャッシュメモリ６０２と接続されている。各プロセッサコア６０１は、メモリアクセスを行う際、アドレスバス上に、自コアに対応する１ビットのコアＩＤを、３２ビットのアドレスと共に送信する。キャッシュミスが発生した場合、プロセッサコア６０１のＭＡＣ６０２を通してメインメモリ６０４からデータを取得する。
【００６９】
図７は、図１又は図２の構成を有するキャッシュメモリ１０１における置換ウェイ制御回路の第１の構成例を示す図である。置換ウェイ制御回路は、置換コアＩＤ決定回路７１１及びその周辺回路群７１２〜７１６と、置換ウェイマスク生成回路７０３（置換ウェイ候補決定部）、及びＬＲＵ選択回路７０４（置換ウェイ選択部）とを有する。置換ウェイ制御回路は、キャッシュミスの発生時に、インデックスにより指定されたブロック番号に対応する＃１〜＃４の４つのキャッシュウェイ１０２のキャッシュブロック１０３のデータのうち、どのウェイが置換されるべきかを決定する。
【００７０】
ここで、図７に示されるキャッシュ制御部７１８（要求元ＩＤ情報更新部）は、図１又は図２に示されるどのコンパレータ１０４においてもタグ値の一致が検出されていない状態を検出することで、キャッシュミスを検出する。キャッシュ制御部７１８は、キャッシュミスが発生した場合に、ＬＲＵ選択回路７０４の出力を選択して、置換ウェイ制御回路の動作を有効とする。一方、キャッシュ制御部７１８は、キャッシュヒットが発生した場合には、ＬＲＵ選択回路７０４の出力は選択せず、後述するキャッシュヒット時の動作を実行する。
キャッシュメモリ１０１へのメモリアクセスがあった場合、置換ウェイ制御回路は以下のように動作する。
【００７１】
図７においてまず、メモリアクセス要求７０８中のアドレス１０５のインデックスにより、キャッシュブロック１０３（＃ｉ）が指定される。この結果、コアＩＤ・ＲＡＭ２０３から、指定されたキャッシュブロック１０３（＃ｉ）に設定されている、＃１〜＃４のキャッシュウェイに対応する４ビットのコアＩＤ７０１が読み出される。
【００７２】
また、メモリアクセス要求７０８には、キャッシュメモリ１０１におけるデータの置換状態を制御するための１ビットのコアＩＤ７０２が付加される。図７に示されるメモリアクセス要求７０８は、プログラム（ソフトウェア）に基づくものであるが、ハードウェアによるメモリアクセス要求についても同様に動作する。コアＩＤ７０２は例えば、メモリアクセス要求７０８が、図６に示されるプロセッサコア６０１（＃０）から発行された場合には“０”、プロセッサコア６０１（＃１）から発行された場合には“１”となる。
【００７３】
メモリアクセス要求７０８に付加されているコアＩＤ７０２は、置換コアＩＤ決定回路７１１で置換コアＩＤ７１７に変換されてから、置換ウェイ選択可能マスク生成回路７０３に入力する。
【００７４】
置換コアＩＤ決定回路７１１には、下記の２つのレジスタ（最大ブロック数指定部）が接続される。ここで、「コア０」とはプロセッサコア６０１（＃０）を意味し、「コア１」とはプロセッサコア６０１（＃１）を意味する。
・コア０用上限ブロック数レジスタ７１２
・コア１用上限ブロック数レジスタ７１３
【００７５】
また、置換コアＩＤ決定回路７１１（比較部）には、下記の２つの数え上げ回路（カウンタ回路）が接続される。
・コア０のブロック数のビット数え上げ回路７１４
・コア１のブロック数のビット数え上げ回路７１５
【００７６】
コア０用上限ブロック数レジスタ７１２及びコア１用上限ブロック数レジスタ７１３には、各キャッシュブロック１０３において、プロセッサコア６０１（＃０）及びプロセッサコア６０１（＃０）に対して設定することのできる上限ブロック数が設定される。これらのレジスタ値は、プロセッサコア６０１（図６参照）からの指示で適宜変更できる。
【００７７】
次に、コア０のブロック数のビット数え上げ回路７１４は、コアＩＤ・ＲＡＭ２０３から読み出されるコアＩＤの４ウェイに対応する４ビット値を、インバータ７１６を介して順次読み込み、値“１”の数をカウントする。この結果、ビット数え上げ回路７１４は、コアＩＤ・ＲＡＭ２０３から読み出される指定されたキャッシュブロック１０３（＃ｉ）に対応する４ウェイのコアＩＤのうち、値が“０”となっているコアＩＤの数を数え上げることになる。コア１のブロック数のビット数え上げ回路７１５は、コアＩＤ・ＲＡＭ２０３から読み出されるコアＩＤの４つのウェイに対応する４ビット値を順次読み込み、値“１”の数をカウントする。この結果、ビット数え上げ回路７１５は、コアＩＤ・ＲＡＭ２０３から読み出されるキャッシュブロック１０３（＃ｉ）に対応する４ウェイのコアＩＤのうち、値が“１”となっているコアＩＤの数を数え上げることになる。
【００７８】
各レジスタ７１２、７１３、及び各ビット数え上げ回路７１４、７１５は、例えばそれぞれ３ビットのデータを出力し、上限ブロック数として０から４上限ブロックまでの出力値をとる。
【００７９】
置換コアＩＤ決定回路７１１では、メモリアクセス要求７０８にコアＩＤ＝”０”が指定されている場合は、セレクタ７１１−１がレジスタ７１２の出力を、セレクタ７１１−２がビット数え上げ回路７１４の出力を選択し、比較器７１１−３に入力する。逆に、メモリアクセス要求７０８にコアＩＤ＝”１”が指定されている場合は、セレクタ７１１−１がレジスタ７１３の出力を、セレクタ７１１−２がビット数え上げ回路７１５の出力をそれぞれ選択し、比較器７１１−３に入力する。
【００８０】
この結果、比較器７１１−３は、メモリアクセス要求７０８にて指定されたコアＩＤ値に対応する上限ブロック数と、指定されたキャッシュブロック１０３（＃ｉ）においてそのコアＩＤ値を有するブロック数とを比較する。ここで、上限ブロック数は、何ウェイまで各プロセッサコアにコア対応するブロック数が増加してもよいか、という上限を与える情報である。前述したように、コアＩＤ値はプロセッサコア６０１を識別する情報である。従って、比較器７１１−３は、メモリアクセス要求７０８を発行したプロセッサコア６０１に設定されている上限ブロック数と、選択されたキャッシュブロック１０３（＃ｉ）においてメモリアクセス要求で指定されていたコアＩＤに対応するプロセッサコア６０１が使用しているブロック数とを比較することになる。
【００８１】
図７の例では、メモリアクセス要求７０８に付加されているコアＩＤの値が“１”である。このため、比較器７１１−３は、レジスタ７１３から読み出したプロセッサコア６０１（＃１）に設定されている上限ブロック数と、ビット数え上げ回路７１５から読み出したキャッシュブロック１０３（＃ｉ）においてプロセッサコア６０１（＃１）が使用しているブロック数とを比較する。
【００８２】
比較器７１１−３での比較の結果、指定されたコアＩＤに関して「現在のブロック数＜上限ブロック数」である場合には、まだ指定されたコアＩＤに対してブロック数を増やしてよいことを意味する。即ち、指定されたキャッシュブロック１０３（＃ｉ）において、メモリアクセス要求７０８を発行したプロセッサコア６０１に対応するブロック数を増やすことができる。このため、セレクタ７１１−５は、指定されたコアＩＤとは逆の値を有する置換コアＩＤ７１７を出力する。即ち、セレクタ７１１−５は、メモリアクセス要求７０８に付加されているコアＩＤ７０２をインバータ７１１−４で反転させた値を選択し、それを置換コアＩＤ７１７として出力する。
【００８３】
一方、比較器７１１−３での比較の結果、指定されたコアＩＤに関して「現在のブロック数≧上限ブロック数」である場合には、それ以上指定されたコアＩＤに対応するブロック数は増やせない。つまり、指定されたキャッシュブロック１０３（＃ｉ）において、メモリアクセス要求７０８を発行したプロセッサコア６０１に対応するブロック数は現在以上には増やせない。このため、セレクタ７１１−５は、指定されたコアＩＤ値が設定されている置換コアＩＤ７１７を出力する。即ち、セレクタ７１１−５は、メモリアクセス要求７０８に付加されているコアＩＤ７０２をそのまま選択し、それを置換コアＩＤ７１７として出力する。
【００８４】
図７の例では、比較器７１１−３でのコアＩＤ＝“１”に関する比較の結果、指定されたコアＩＤ＝“１”に関して「現在のブロック数＜上限ブロック数」である場合には、まだコアＩＤ＝“１”のブロック数を増やしてよいことを意味する。このため、セレクタ７１１−５は、メモリアクセス要求７０８に付加されているコアＩＤ＝“１”をインバータ７１１−４で反転させた値“０”を選択し、それを置換コアＩＤ７１７として出力する。
【００８５】
上述の置換コアＩＤ７１７は、置換ウェイ選択可能マスク生成回路７０３に入力する。
置換ウェイ選択可能マスク生成回路７０３には、指定されたキャッシュブロック１０３（＃ｉ）に対応するコアＩＤ・ＲＡＭ２０３から読み出された＃１〜＃４のキャッシュウェイ１０２に対応する４ビットのコアＩＤ７０１と、置換コアＩＤ７１７が入力する。
【００８６】
置換ウェイマスク生成回路７０３は、図８に示されるように、エクスクルーシブオア回路（ＸＯＲ）７０３−１とインバータ（ＩＮＶ）７０３−２とを有する。置換ウェイマスク生成回路７０３は、置換コアＩＤ決定回路７１１からの１ビットの置換コアＩＤ７１７と、コアＩＤ・ＲＡＭ２０３から読み出した４ビットのコアＩＤ７０１の各ビットとの間で、エクスクルーシブノア演算を実行する。この結果、置換ウェイマスク生成回路回路７０３に入力する置換コアＩＤ７１７の値が“０”の場合、置換ウェイマスク生成回路７０３は、置換コアＩＤ７１７のビット値“０”と同じコアＩＤ＝”０”を持つビット位置のみが値“１”となる、４ビットからなる置換ウェイ候補７０９を出力する。置換ウェイ候補７０９は４ビットの情報であり、各ビットは各キャッシュウェイに対応している。そして、置換ウェイ候補７０９の値“１”を有するビット位置に対応するキャッシュウェイ１０２が、メモリアクセス要求７０８によって置換されるべきウェイであることを指示している。
【００８７】
図７の例では、コアＩＤ・ＲＡＭ２０３から読み出された４ビットのコアＩＤ７０１“０００１”の各ビットと、置換コアＩＤ７１７“０”とのエクスクルーシブノア演算が実行される。この結果、置換ウェイマスク生成回路回路７０３から４ビットの置換ウェイ候補７０９：“１１１０”が出力される。
【００８８】
ＬＲＵ選択回路７０４は、置換ウェイ候補７０９において、値が“１”であるビット位置に対応するウェイのうちの何れか１つを、ＬＲＵアルゴリズムに従って選択する。そして、ＬＲＵ選択回路７０４は、選択されたウェイに対応するビット位置のみが“１”となる４ビットからなる置換ウェイ指示情報７１０を出力する。
【００８９】
図７の例では、ＬＲＵ選択回路７０４は、置換ウェイ候補７０９“１１１０”から置換ウェイ指示情報７１０“１０００”を出力する。
キャッシュ制御部７１８は、図１又は図２に示されるどのコンパレータ１０４においてもタグ値の一致が検出されていない状態を検出することでキャッシュミスを検出すると、ＬＲＵ選択回路７０４から出力された置換ウェイ指示情報７１０を入力する。そして、キャッシュ制御部７１８は、置換ウェイ指示情報７１０を、セレクタ７０５、７０６、及び７０７に入力し、各セレクタにおいて、置換ウェイ３１０の４ビットのデータのうち値が１となるビット位置に対応するウェイを選択させる。
【００９０】
即ち、セレクタ７０５は、メモリアクセス要求７０８に対応するデータを、データＲＡＭ２０１内の、置換ウェイ３１０の４ビットのデータのうち値が１となるビット位置に対応するウェイに出力する。また、セレクタ７０６は、メモリアクセス要求７０８に対応するタグを、タグＲＡＭ２０２内の、置換ウェイ３１０の４ビットのデータのうち値が１となるビット位置に対応するウェイに出力する。更に、セレクタ７０７は、メモリアクセス要求７０８に対応するコアＩＤを、コアＩＤ・ＲＡＭ２０３内の、置換ウェイ３１０の４ビットのデータのうち値が１となるビット位置に対応するウェイに出力する。
【００９１】
また、メモリアクセス要求７０８内のインデックスが、データＲＡＭ２０１、タグＲＡＭ２０２、及びコアＩＤ・ＲＡＭ２０３のブロック番号を指定する。
これらの動作の結果、データＲＡＭ２０１、タグＲＡＭ２０２、及びコアＩＤ・ＲＡＭ２０３にて、指定されたブロック番号の選択されたウェイのキャッシュブロック１０３に、データ、タグ、及びコアＩＤが書き込まれる。なお、データ、タグ及びコアＩＤが書き込まれた領域は、図７では塗りつぶして示す。
【００９２】
なお、データＲＡＭ２０１に書き込まれるデータは、メモリアクセス要求７０８が読出し要求の場合には、特には図示しない主記憶メモリ上のアドレス１０５に対応する記憶領域から読み出されたデータであり、メモリアクセス要求７０８が書込み要求の場合には、データＲＡＭ２０１に書き込まれるデータはメモリアクセス要求７０８に指定されている書込みデータである。
【００９３】
上記書込みのタイミングで、図７の例では、コアＩＤ・ＲＡＭ２０３における指定ブロック番号（＃ｉ）に対応する４ビットのコアＩＤは、“０００１”から“１００１”に更新される。即ち、いままでコアＩＤ＝”０”のコアに対応していたキャッシュウェイのキャッシュブロックのいずれかが置換され、コアＩＤ＝”１”のコアに対応するようになる。
【００９４】
図１１は、メモリアクセス要求７０８に対して図１又は図２の構成を有するキャッシュメモリ１０１においてキャッシュヒットが発生したときに、コアＩＤ・ＲＡＭ２０３内のキャッシュヒットが発生したキャッシュブロックのコアＩＤを制御するための、ヒットウェイ制御回路に関する実施形態の構成図である。
【００９５】
図１１のヒットウェイ更新回路１１０１は、例えば図７のキャッシュ制御部７１８内に設けられ、図２に示される４つのコンパレータ１０４から出力される４ビットのヒットウェイ信号１１０２が入力する。ヒットウェイ信号１１０２においては、＃１〜＃４のキャッシュウェイ１０２のうち、キャッシュヒットが発生したキャッシュウェイに対応するビット値のみが１となっている。図１１の例では、現在のコアＩＤ情報７０１として、コアＩＤ・ＲＡＭ２０３から「０００１」という４ビット値が読み出される。
【００９６】
ヒットウェイ更新回路１１０１は、指定されたキャッシュブロック１０３（＃ｉ）に対応する、コアＩＤ・ＲＡＭ２０３読み出された４ビットのコアＩＤ７０１（図７参照）に対して、次のような更新動作を実行する。
【００９７】
即ち、４ビットのコアＩＤ７０１のうち、ヒットウェイ信号１１０２のビット値が１となるキャッシュウェイに対応するコアＩＤ値を、メモリアクセス要求７０８に付加されているコアＩＤ７０２（図７参照）の値に更新する。そして、ヒットウェイ更新回路１１０１は、その結果得られる新コアＩＤ情報１１０３を、コアＩＤ・ＲＡＭ２０３内の現在のキャッシュブロック１０３（＃ｉ）に対応する位置に書き戻す。図１１の例では、「０１００」というヒットウェイ信号１１０２に対して、「０１０１」という新コアＩＤ情報１１０３が出力される。
【００９８】
このようにして、現在のキャッシュブロック１０３（＃ｉ）におけるキャッシュヒットが発生したコアＩＤ７０１は、常にメモリアクセス要求７０８で指定されたコアＩＤ７０２に一致するように更新され、処理の矛盾が発生しないように制御される。
【００９９】
以上説明した図７、図８、及び図１１の構成に基づく置換ウェイ制御の第１の実施例によって、図６に示したプロセッサコア６０１毎に、それぞれが共有しているキャッシュメモリ１０１上のキャッシュウェイを分割管理することが可能となる。
【０１００】
次に、図１及び図２に示されるキャッシュメモリ１０１における置換ウェイ制御の第２の実施例について、以下に説明する。
第２の実施例では、前述した図６に示されるコンピュータシステムの各プロセッサコア６０１は、メモリアクセスを行う際、アドレスバス上に、自コアに対応する１ビットのコアＩＤ及び３２ビットのアドレスに加えて、セット内上限ブロック数を指定する“way_limit_count”情報を送信する。
【０１０１】
図９は、置換ウェイ制御の第２の実施例においてプロセッサコア６０１で動作するオペレーティングシステムのプロセス構造体の例を示す図である。一般に、マルチプロセス環境をサポートするオペレーティングシステムは、各プロセスに関する情報を構造体としてまとめて管理している。構造体として管理される情報には、例えば、図９中のpid（プロセスＩＤ）やpriority（優先度）、(time_slice) タイムスライスなどがある。
【０１０２】
構造体の中に、実行中のプロセスをスイッチする場合に退避／復帰する値であるコンテキスト（*context）も含まれている。本実施形態では、この構造体の中に、プロセスのセット内上限ブロック数情報“way_limit_count”を追加する。オペレーティングシステムは、プロセッサコア６０１上で実行するプロセスを異なるプロセスに変更するとき、言い換えればコンテキストスイッチを行うときには、このセット内上限ブロック数情報を他のレジスタ値などと共に、変更後のプロセス実行状態から変更前のプロセス実行状態に復帰させる。
【０１０３】
図１０は、置換ウェイ制御の第２の実施例における置換ウェイ制御回路の部分の構成例を示す図である。
図１０において、図７に示される第１の構成例の場合と同じ処理を実行する部分は同じ番号が付されている。
【０１０４】
図１０の構成が図７の構成と異なる部分は、コア０用及びコア１用の各上限ブロック数レジスタ１００１及び１００２に、各プロセッサコア６０１からのメモリアクセス時に、アドレスバスによって指定される“way_limit_count”情報がセットされる点である。
【０１０５】
即ち、図６のプロセッサコア６０１（＃０）において実行するプログラムにおけるプロセス構造体の設定において、上限ブロック数レジスタ１００１にセットされるべき“way_limit_count”値が定義される。また、図６のプロセッサコア６０１（＃１）において実行するプログラムにおけるプロセス構造体の設定において、上限ブロック数レジスタ１００２にセットされるべき“way_limit_count”値が定義される。
【０１０６】
このように、置換ウェイ制御の第２の実施例では、各プロセッサコア６０１からのメモリアクセス毎に、図９に示されるプロセス構造体を用いてセット内上限ブロック数をセットすることにより、マルチプロセス環境においてプロセス単位でキャッシュウェイの分割割当てが可能となる。
【０１０７】
次に、図１及び図２に示されるキャッシュメモリ１０１における置換ウェイ制御の第３の実施例について、以下に説明する。
第３の実施例におけるコンピュータシステムの構成、プロセス構造体、及び置換ウェイ制御回路の構成は、上述した第２の実施例の場合（図６、図９、図１０）と同様である。
【０１０８】
第３の実施例は、コンパイラによってセット内上限ブロック数の指示を行うことができるソフトウェア構成例である。
図１２に、第３の実施例のソフトウェア構成例における、アプリケーションのソースコードから実行バイナリを生成する処理の流れを示す図である。
【０１０９】
アプリケーションのソースコード１２０１の例として、配列aと配列bの各配列要素を加算して配列cに代入するプログラムのソースコードが示されている。このプログラムでは、０〜９９９までの１０００個の各配列要素に対して加算演算が実行される。
【０１１０】
コンパイラは第１段階において（図１２の１２０２）、このプログラムのソースコードを解析して、２つのプロセッサコアで並列にプログラムを実行できるようにソースコードを分割することによりスレッド化を行う（図１２の１２０３）。このとき、スレッド化を行うと共に、ソースコード内に、各スレッドに割り当てるキャッシュブロック数を設定するコードが付加される（図１２の１２０３中の“set_max_block（）”）。これにより、各スレッドに均等に共有キャッシュウェイを割り当てることができる。
【０１１１】
コンパイラは第２段階において（図１２の１２０４）、ソースコード１２０３から、実行バイナリ１２０５として、プロセッサコア６０１（＃０）で実行可能な第１の実行バイナリとプロセッサコア６０１（＃１）で実行可能な第２の実行バイナリを生成する。
【０１１２】
これらの実行バイナリが図６に示される各プロセッサコア６０１にて実行された場合、各実行バイナリの実行開始時に各スレッド（＝各プロセッサコア６０１）に２ウェイずつの共有キャッシュウェイを割り当てる設定がなされた後、各スレッドの実行が開始される。
【０１１３】
以上のようにして、置換ウェイ制御の第３の実施例では、コンパイラによって各スレッドごとにキャッシュメモリ１０１を割り当てることによって、コンピュータシステムの全体性能を最適化させることが可能となる。
【０１１４】
次に、図１及び図２に示されるキャッシュメモリ１０１における置換ウェイ制御の第４の実施例について、以下に説明する。
第４の実施例におけるコンピュータシステムの構成は、前述した第１の実施例（図６）と同様である。
【０１１５】
図１３は、置換ウェイ制御の第４の実施例における置換ウェイ制御回路の部分の構成例を示す図である。
図１３において、図７に示される第１の構成例の場合と同じ処理を実行する部分は同じ番号が付されている。
【０１１６】
図１３の構成が図７の構成と異なる部分は、キャッシュメモリ１０１における各プロセッサコア６０１（コア０及びコア１）毎のキャッシュミス回数を保持する２つのレジスタ１３０１及び１３０２が設置される点である。
【０１１７】
図１３のキャッシュ制御部７１８は、各プロセッサコア６０１からメモリアクセス要求７０８が発行される毎に、図１又は図２に示されるどのコンパレータ１０４においてもタグ値の一致が検出されていない状態を検出することで、キャッシュミスを検出する。この時、メモリアクセス要求７０８内のコアＩＤ７０２の値が“０”、即ちメモリアクセス要求７０８が＃０のプロセッサコア６０１から発行された場合に、キャッシュ制御部７１８は、コア０キャッシュミス回数レジスタ１３０１の値を＋１する。逆に、メモリアクセス要求７０８内のコアＩＤ７０２の値が“１”、即ちメモリアクセス要求７０８が＃１のプロセッサコア６０１から発行された場合に、キャッシュ制御部７１８は、コア１キャッシュミス回数レジスタ１３０２の値を＋１する。
【０１１８】
このようにして、キャッシュミスを発生させたメモリアクセス要求７０８の回数が、メモリアクセス要求７０８を発行したプロセッサコア６０１毎にカウントされる。
なお、図１３の構成例では専用のレジスタ１３０１、１３０２が装備されているが、これらのレジスタは、一般的なプロセッサに実装されているハードウェアモニタリングカウンタで実現してもよい。
【０１１９】
上述の置換ウェイ制御回路内のキャッシュミス回数レジスタ１３０１、１３０２の各値は、オペレーティングシステムに実装されるウェイリミットスケジューラ（waylimit scheduler）１３０３によって参照される。
【０１２０】
ウェイリミットスケジューラ１３０３は、一定時間ごとにキャッシュミス回数レジスタ１３０１、１３０２の値を参照して、参照したキャッシュミス回数レジスタ１３０１、１３０２の値に基づいて、コア０用上限ブロック数レジスタ７１２及びコア１用上限ブロック数レジスタ７１３に割り当てられるプロセッサコア６０１（＃０）の上限ブロック数及びプロセッサコア６０１（＃１）の上限ブロック数を更新する。この結果、図６に示されるプロセッサコア６０１（＃０）とプロセッサコア６０１（＃１）に対する各キャッシュ割当てが変更される、言い換えれば各プロセッサにおいてキャッシュミスが発生する割合が変更されることになる。この制御処理において、様々なスケジューリングポリシーが考えられる。例えば、キャッシュミス回数レジスタの値を参照してコア０キャッシュミス回数＞コア１キャッシュミス回数となった場合に、プロセッサコア６０１（＃０）へのキャッシュ割当て量が増加させられるように制御することができる。具体的には、ウェイリミットスケジューラ１３０３は、ここに例示した条件を始めとする所定の条件が満たされる毎に、所定の規則に従って、図６のプロセッサコア６０１（＃０）及び６０１（＃１）にそれぞれ対応するプロセス構造体の設定において、上限ブロック数レジスタ１００１及び１００２にそれぞれセットされるべき各“way_limit_count”値を設定する。
【０１２１】
なお、キャッシュミス回数レジスタ１３０１、１３０２の値は例えば、一定時間毎、或いは各プロセッサコア６０１で実行されるスレッドが終了する毎にクリアされる。
以上のようにして、置換ウェイ制御の第４の実施例では、コアＩＤ（＝プロセッサコア）毎に、キャッシュメモリ１０１におけるキャッシュミスの回数が動的に計測され、その計測結果に基づいてキャッシュ割当てが最適化される。この結果、システム全体でのキャッシュミス回数をできる限り減少させることが可能となる。
【０１２２】
次に、図１及び図２に示されるキャッシュメモリ１０１における置換ウェイ制御の第５の実施例について、以下に説明する。
この第５の実施例におけるコンピュータシステムの構成は、前述した第２の実施例（図６、図９、図１０）と同様である。
【０１２３】
第５の実施例は、複数の仮想マシンに対して上限ブロック数を設定することができるシステム構成例である。
仮想マシンを実装するために、オペレーティングシステムと実ハードウェアの間にハイパーバイザーソフトウェア（以下、「ＨＶ」と略記する）がある。ＨＶは、仮想マシン情報を管理しており、実コアを仮想マシンに割り当てる機能を持つ。
【０１２４】
図１４は、第５の実施例においてＨＶが管理する仮想マシン構造体（vcpu構造体）の例を示す図である。
vcpu構造体は、仮想マシンのＩＤ（仮想ＣＰＵＩＤ）や、優先度、実行したタイムスライス数や、最大メモリ使用量、各種レジスタ値（vcpucontext*  から参照されるkernel stack、control registers*、cpu registers*等）などの、仮想マシンの状態を保持するための構造体である。第５の実施例では、このvcpu構造体内に、上限ブロック数として“way_limit_count”が追加される。
【０１２５】
図１５は、仮想マシンに対するキャッシュメモリの制御動作の説明図であり、ＨＶが実プロセッサコア（実コア）１５０２に対して仮想プロセッサコア（仮想コア）を割り当てる様子を示す説明図である。図１５の例では、仮想コア０の仮想プロセッサコア１５０１から仮想コア１の仮想プロセッサコア１５０１への切替えが実行される。ＨＶは、仮想コア０の状態を保持するvcpu構造体１５０３に、実コア１５０２上のレジスタやメモリ等に設定されていた各情報を退避した後、仮想コア１の状態を保持するvcpu構造体１５０４に退避されていた情報を実コア１５０２上の対応するレジスタやメモリに復帰している。
【０１２６】
第５の実施例では、復帰処理の際に、“way_limit_count”の値も退避・復帰させられる。復帰のときに、図１０の上限ブロック数レジスタ１００１や１００２に、復帰された“way_limit_count”の値がセットされることによって、切替え先の仮想マシンに上限ブロック数を設定できる。図１５の例では、仮想コア０の退避時に共有キャッシュであるキャッシュメモリ１０１に３ウェイが割り当てられることを示す情報“way_limit_count”値＝“３”が退避され、仮想コア１の復帰時に共有キャッシュであるキャッシュメモリ１０１に１ウェイが割り当てられることを示す情報“way_limit_count”値＝“１”が復帰させられる。
【０１２７】
このように、置換ウェイ制御の第５の実施例では、各仮想マシン毎にキャッシュメモリ１０１でのキャッシュブロックの使用量を制御するこが可能となる。
以上説明したように、開示した実施形態では、少ないハードウェアコストの追加で、キャッシュメモリ領域をウェイ単位で任意に分割することが可能となる。この結果、キャッシュメモリの性能の最適化を行ったり、プロセス間や仮想マシン間のキャッシュメモリ上での競合をコントロールすることが可能となり、プロセッサの実効性能を向上させることが可能となる。
【産業上の利用可能性】
【０１２８】
本発明は、例えば、高性能プロセッサにおけるプログラムの高速実行を目的とした、以下のような分野において有効である。
・プログラマ又はコンパイラによるキャッシュ性能最適化
・仮想マシン性能の最適化
・オペレーティングシステムによるプロセススケジューリングの最適化
本発明は、マルチプロセッサシステムにおけるプロセッサ間で共有されているキャッシュメモリに適用することもできるし、オンチップマルチプロセッサにおけるチップ上のコアプロセッサ間で共有されているキャッシュメモリにも利用することができる。また、マルチスレッドプロセッサにおいてスレッド間で共有されているキャッシュメモリにも利用することができる。
【符号の説明】
【０１２９】
１０１、６０２、１６０１  キャッシュメモリ
１０２、１６０２  キャッシュウェイ
１０３、１６０３  キャッシュブロック
１０４、１６０４  コンパレータ
１０５、１６０５  アドレス
２０１  データＲＡＭ
２０２  タグＲＡＭ
２０３  コアＩＤ・ＲＡＭ
２０４、２０５、７０５、７０６、７０７、７１１−１、７１１−２、７１１−５  セレクタ
６０１  プロセッサコア
６０３  ＭＡＣ（Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌｌｅｒ：メモリアクセスコントローラ）
６０４  メインメモリ
６０５  アドレスバス
６０６  データバス
７０１  コアＩＤ・ＲＡＭ２０３から読み出されるコアＩＤ
７０２  メモリアクセス要求７０８に付加されているコアＩＤ
７０３  置換ウェイマスク生成回路
７０３−１  エクスクルーシブオア回路（ＸＯＲ）
７０３−２、７１１−４、７１６  インバータ（ＩＮＶ）
７０４  ＬＲＵ選択回路
７０８  メモリアクセス要求
７０９  置換ウェイ候補
７１０  置換ウェイ指示情報
７１１  置換コアＩＤ決定回路
７１１−３  比較器
７１２、１００１  コア０上限ブロック数レジスタ
７１３、１００２  コア１上限ブロック数レジスタ
７１４、７１５  ビット数え上げ回路
７１７  置換コアＩＤ
７１８  キャッシュ制御部
１１０１  ヒットウェイ更新回路
１１０２  ヒットウェイ信号
１１０３  新コアＩＤ情報
１２０１  アプリケーションのソースコード
１２０２  コンパイラ（第１段階）
１２０３  ブロック数指示付きソースコード
１２０４  コンパイラ（第２段階）
１２０５  実行バイナリ
１３０１  コア０キャッシュミス回数レジスタ
１３０２  コア１キャッシュミス回数レジスタ
１３０３  ウェイリミットスケジューラ
１５０１  仮想コア０
１５０２  実コア
１５０３  仮想コア１
１７０１  置換ウェイ選択回路
【図３】
0005413001.tif 000002
【図５】
0005413001.tif 000003
【図６】
0005413001.tif 000004
【図１５】
0005413001.tif 000005
【図１７】
0005413001.tif 000006
【図１】
0005413001.tif 000007
【図２】
0005413001.tif 000008
【図４】
0005413001.tif 000009
【図７】
0005413001.tif 000010
【図８】
0005413001.tif 000011
【図９】
0005413001.tif 000012
【図１０】
0005413001.tif 000013
【図１１】
0005413001.tif 000014
【図１２】
0005413001.tif 000015
【図１３】
0005413001.tif 000016
【図１４】
0005413001.tif 000017
【図１６】
0005413001.tif 000018