演算処理装置および演算処理装置の制御方法
【課題】キャッシュメモリを実装した演算処理装置およびキャッシュメモリ制御装置において、プロセスＩＤに対応してキャッシュメモリ領域をブロック単位で任意に分割可能として、プロセッサの実効性能を向上することを可能とする。
【解決手段】各セット１０３のキャッシュブロック１０２毎に物理プロセスＩＤ（ＰＰＩＤ）が記憶されるとともに、＃１から＃ｎの各インデックス値毎に、各ＰＰＩＤ値に対するＭＡＸ ＷＡＹ数１０５が記憶される。或るインデックス値における或るＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５は、そのインデックス値において記憶可能なそのＰＰＩＤ値を有するキャッシュブロック１０２の最大数を示す。各インデックス値毎に、各ＰＰＩＤ値のＭＡＸ ＷＡＹ数１０５が守られるように、キャッシュミス時のウェイ数の制御が実施される。
【解決手段】各セット１０３のキャッシュブロック１０２毎に物理プロセスＩＤ（ＰＰＩＤ）が記憶されるとともに、＃１から＃ｎの各インデックス値毎に、各ＰＰＩＤ値に対するＭＡＸ ＷＡＹ数１０５が記憶される。或るインデックス値における或るＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５は、そのインデックス値において記憶可能なそのＰＰＩＤ値を有するキャッシュブロック１０２の最大数を示す。各インデックス値毎に、各ＰＰＩＤ値のＭＡＸ ＷＡＹ数１０５が守られるように、キャッシュミス時のウェイ数の制御が実施される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置および演算処理装置の制御方法に関する。
【背景技術】
【０００２】
近年のプロセッサの動作周波数の向上により、相対的にプロセッサ内部からメインメモリに対するメモリアクセスの遅延時間が長くなり、メモリアクセスの遅延時間がシステム全体の性能を左右するに至っている。多くのプロセッサは、メモリアクセス遅延時間を隠蔽する目的で、キャッシュメモリと呼ぶ小容量の高速メモリを搭載している。
【０００３】
キャッシュメモリは、データを複数のキャッシュライン（もしくは単に「ライン」）またはキャッシュブロック（もしくは単に「ブロック」））と呼ばれる単位で管理する。プロセッサからデータのアクセス要求があった時に、そのデータがキャッシュ内のいずれかのラインに存在しているか否かを高速に検索する必要がある。
【０００４】
このためキャッシュメモリを分割して検索等の処理を行なうことが行われる。
プロセッサが実行するオペレーティングシステム(Operating System；ＯＳ)によって共有キャッシュ領域を分割管理する手法として従来、Modified LRU Replacement方式と呼ばれる第１の従来技術が知られている。この第１の従来技術では、システム上で動作する全プロセスについて、プロセスが使用しているキャッシュブロック数がカウントされる。
【０００５】
また、キャッシュブロック内のタグ（キャッシュタグ）にプロセッサが実行するプロセスを識別するプロセスＩＤを記憶し、プロセスＩＤによってキャッシュフラッシュを制御する第２の従来技術が知られている。
【０００６】
さらに、キャッシュタグ内にプロセスＩＤを記録して、キャッシュアクセス時に要求元プロセスＩＤとキャッシュタグ内のプロセスＩＤとを比較することで、キャッシュフラッシュを制御する第３の従来技術が知られている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平３−２３５１４３号公報
【特許文献２】特許２７００１４８号公報
【非特許文献】
【０００８】
【非特許文献１】Suh, G.E. and Devadas, S. and Rudolph, L.,"A new memory monitoring scheme for memory-aware scheduling and partitioning",High-Performance Computer Architecture, 2002. Proceedings. Eighth International Symposium on, pp.117--128.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、第１の従来技術では、使用中のキャッシュブロック数を、全プロセスについて正しく把握するような機構が必要となって、ハードウェア規模が増大してしまう。また、マルチプロセス環境においてはその効率的な動作の観点から問題があった。
【００１０】
また、第２の従来技術では、各キャッシュタグにプロセスＩＤを固定的に割り当てるのみである。このため、キャッシュメモリ中でのプロセスＩＤ間の全体的なサイズ割当てを変更するためには、全キャッシュタグの書換えが必要となってしまうという問題点を有していた。
【００１１】
さらに、第３の従来技術も、キャッシュメモリ中でのプロセスＩＤ間の全体的なサイズ割当てを変更するような機構は備えていないという問題点を有していた。
このため、キャッシュメモリのより効率的な動作が望まれていた。
【００１２】
本発明の１つの側面では、プロセスＩＤに対応してキャッシュメモリ領域をブロック単位で任意に分割可能として、プロセッサの実効性能を向上することを可能とすることにある。
【課題を解決するための手段】
【００１３】
態様の一例では、複数の命令を含むプロセスを実行するとともに、インデックス情報とタグ情報を含むメモリアクセス要求を発行する命令制御部と、タグと、メモリアクセス要求に対応するデータと、命令制御部が実行するプロセスを識別するプロセス識別子を保持するブロックを、複数のインデックス各々に対応して有するキャッシュウェイを複数備えたキャッシュメモリ部と、受信したメモリアクセス要求に含まれるインデックス情報をデコードし、デコードしたインデックス情報に対応するブロックを選択するインデックスデコード部と、受信したメモリアクセス要求に含まれるタグ情報とインデックスデコード部が選択したブロックに含まれるタグを比較し、タグ情報とタグが一致する場合にはインデックスデコード部が選択したブロックに含まれるデータを出力する比較部と、プロセス識別子毎に設定された最大キャッシュウェイ数情報に基づき、キャッシュメモリ部のインデックス毎に、プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数を決定する制御部とを有するように構成する。
【発明の効果】
【００１４】
キャッシュメモリ領域をキャッシュブロック単位で任意に分割し、各プロセスに適切なキャッシュブロック数を割り当てることが可能となる。これにより、キャッシュメモリをリソースとして管理し、プロセススケジューリングを最適化することが可能となり、プロセッサの実効性能を向上させることが可能となる。
【図面の簡単な説明】
【００１５】
【図１】キャッシュメモリの実施形態のブロック図である。
【図２】ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数のテーブルのデータ構成例を示す図である。
【図３】キャッシュメモリの分割例を示す図である。
【図４】キャッシュミス発生時のリプレース動作を示す説明図である。
【図５】ハッシュユニットを示す図である。
【図６】プロセスＩＤマップユニットを示す図である。
【図７】キャッシュタグ部のハードウェア構成例を示す図（その１）である。
【図８】キャッシュタグ部のハードウェア構成例を示す図（その２）である。
【図９】ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数に基づいてＭＡＸ ＷＡＹ数を決定する処理を示すフローチャートである。
【図１０】ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数に基づいてＭＡＸ ＷＡＹ数を決定する処理を示すプログラム擬似コードである。
【図１１】置換ウェイ制御回路のハードウェア構成例を示す図である。
【図１２】ＭＡＸ ＷＡＹ数更新機構を示す図である。
【図１３】ハッシュユニットのハードウェア構成例を示す図である。
【図１４】ハッシュユニットの動作説明図（その１）である。
【図１５】ハッシュユニットの動作説明図（その２）である。
【図１６】プロセスＩＤマップユニットのハードウェア構成例を示す図である。
【図１７】ＰＰＩＤ書込み機構を示す図である。
【図１８】本実施形態のキャッシュメモリシステムを備えるプロセッサシステムの構成例を示す図である。
【図１９】同時にスケジューリングされる各プロセスが要求するウェイ数の合計が、実装されているキャッシュメモリのウェイ数を超えている場合の動作例を示す説明図である。
【図２０】時間と優先度でキャッシュブロックをスケジュールする動作を示すフローチャートである。
【発明を実施するための形態】
【００１６】
プロセッサの実効性能の向上のためには、キャッシュメモリの高速動作が必要である。
データがキャッシュメモリ内のいずれかのラインに存在しているか否かを高速検索するため、各キャッシュセット（以下、単にセットと略記）を構成するキャッシュブロックは、有効か否かを示す有効フラグ、タグ、及びデータから構成されている。キャッシュブロックのサイズは例えば、有効フラグが１ビット、タグが１５ビット、データが１２８バイトである。ここで、キャッシュセットとは、分割されたキャッシュメモリの領域をいい、各キャッシュセットは複数のキャッシュブロックを含む。
【００１７】
一方、プログラムによって指定されるメモリアクセスのための例えば３２ビットのアドレスは例えば、下位から７ビットがキャッシュライン内オフセット、１０ビットがインデックス、上位１５ビットがタグとして使用される。
【００１８】
アドレスに対するデータ読出しが要求されると、アドレス内のインデックスアドレスが示すセットが選択される。さらに、選択されたセット内の各キャッシュブロックに対応する形で記憶されているタグがアドレス内のタグと一致するか否かが判定され、タグが一致する場合にはキャッシュヒットが検出され、タグが一致しない場合にはキャッシュミスが検出される。
【００１９】
このとき、セット内に複数ウェイのキャッシュブロック（データとタグの組）を持てば、同じインデックス値を有するエントリでも上位アドレス値（タグ値）が異なる複数のデータを格納することが可能となる。このようなキャッシュメモリのデータ格納方式はセット・アソシアティブ(Set Associative)方式と呼ばれる。メモリのアドレス空間より小さい空間となっているキャッシュのアドレス空間をセット（集合）に分割し、例えば要求アドレスをそのセットの数で割った余りの数をインデックスとすればセットの数はインデックス数に対応する。各セット（インデックス）は複数のブロックを含むが、インデックスの指定によって同時に出力されるブロック数がウェイ数である。１ラインがｎ個のタグにより構成されるｎ個のブロックを同時に出力する場合、ｎウエイセット・アソシアティブ(n-way Set Associative)方式と呼ぶ。
【００２０】
書き込まれるデータのサイズがインデックスで指定可能なアドレスの範囲よりも大きい場合に、複数のデータにおいてアドレスの一部分であるインデックスの値が一致し、それらのデータがキャッシュラインを奪い合う競合が発生する可能性がある。このような場合であっても、セット・アソシアティブ方式のキャッシュメモリにおいては、インデックスが同じラインが指定されたとしても、キャッシュラインの競合を発生することなく複数のウェイからキャッシュブロックを選択できる。例えば４ウェイ構成のキャッシュメモリでは、同じインデックスを持つ最大で４つまでのデータに対応することができる。
【００２１】
指定されたラインのどのウェイのキャッシュブロックにおいてもタグの一致が検出されなかった、またはタグの一致が検出されたキャッシュブロックの有効フラグが無効を示していたら、キャッシュミスとなり、メインメモリ（主記憶装置）からアクセス対象のデータが読み出される。キャッシュミスの発生時には、指定されたセット上から未使用のウェイが選択されて、そのウェイのキャッシュブロックにメインメモリから読み出されたデータが新たに保持される。これにより、保持されたデータが次回アクセス時にキャッシュヒットし、メインメモリへのアクセスが不要となるため、高速なアクセスが実行される。キャッシュミス時にどのウェイも使用中の場合には、例えばＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）と呼ばれるアルゴリズムによって、使用中のウェイから１つが選択されて、そのウェイのキャッシュブロックのデータが置換される。ＬＲＵアルゴリズムでは、使われてから最も長い時間が経っているキャッシュブロックのデータがメインメモリに追い出されるとともに、メインメモリから読み出されたデータに置換される。
セット・アソシアティブ方式のキャッシュメモリは以上のような構成を有す。
【００２２】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。
図１は、キャッシュメモリの実施形態のブロック図である。
本実施形態によるキャッシュメモリ１０１は、例えば４ウェイまたは８ウェイのセット・アソシアティブ方式のキャッシュメモリである。
キャッシュメモリ１０１は、データを＃１から＃ｎの複数行からなるセット１０３、および各セット１０３に属するキャッシュブロック１０２の単位で管理される。例えば、ｎ＝１０２４である。
【００２３】
図１の実施形態においては、各セット１０３を構成するキャッシュブロック１０２は、有効フラグ（例えば１ビット）、タグ（例えば１５ビット）、データ（例えば１２８バイト）に加えて、物理プロセスＩＤ（以下、「ＰＰＩＤ」と称する）を有する。ＰＰＩＤは、オペレーティングシステムが管理するプロセスＩＤ（以下、「ＰＩＤ」と称する）を、後述するプロセスＩＤマップユニットによって変換して得られるプロセス識別情報である。ＰＰＩＤは、例えば２ビットのデータであり、例えば０〜３の４つのＰＰＩＤ値を識別することができる。ＰＰＩＤを記憶することで、各キャッシュブロック１０２がどのプロセスに割り当てられているかを区別することができる。
【００２４】
キャッシュメモリ１０１のデータサイズ定義：は、「キャッシュブロック１０２のデータサイズ×キャッシュインデックス数×キャッシュウェイ数で計算され、例えば、１０２４バイトを１キロバイトとして、４ウェイのキャッシュメモリ１０１の場合、
（１２８バイト×１０２４インデックス×４ウェイ）÷１０２４＝５１２キロバイトである。
【００２５】
一方、プログラムによって指定されるメモリアクセスのためのアドレス１０７は、例えば３２ビットで指定され、下位から７ビットがキャッシュライン内オフセット、１０ビットがインデックス、上位１５ビットがタグとして使用される。
【００２６】
また、本実施形態では、プログラムを実行する場合にオペレーティングシステムから指定されるＰＩＤを、プロセスＩＤマップユニットによって変換して得られるＰＰＩＤが、キャッシュメモリ１０１に与えられる。
【００２７】
以上の構成により、アドレス１０７に対するデータの読み出し又は書き込みのアクセスが指定されると、アドレス１０７内の１０ビットのインデックスにより、セット１０３内の＃１〜＃ｎのキャッシュブロックのうちの１つが指定される。
【００２８】
その結果、＃１〜＃４の各キャッシュウェイ１０４から、セット１０３上の各キャッシュブロック１０２（＃ｉ）のタグ値が読み出され、それぞれ＃１〜＃４のコンパレータ１０６に入力する。
【００２９】
＃１〜＃４のコンパレータ１０６は、読み出された各キャッシュブロック１０２（＃ｉ）内のタグ値と、指定されたアドレス１０７内のタグ値との一致／不一致を検出する。この結果、＃１〜＃４のうちタグ値の一致が検出されたコンパレータ１０６において読み出されているキャッシュブロック１０２（＃ｉ）がキャッシュヒットとなり、そのキャッシュブロック１０２（＃ｉ）に対してデータが読み書きされる。
【００３０】
どのコンパレータ１０６でもタグ値の一致が検出されなかった、又はタグ値の一致が検出されたキャッシュブロック１０２（＃ｉ）の有効フラグが無効を示していたら、キャッシュミスとなり、メインメモリ上のアドレスがアクセスされる。キャッシュミスの発生時には、指定されたライン上から選択された未使用のウェイのキャッシュブロックにデータが新たに保持される。これにより、次回アクセス時にキャッシュヒットとなり、メインメモリへのアクセスが不要となるため、高速なアクセスが実行される。
【００３１】
キャッシュミス時にどのウェイも使用中の場合には、本実施形態では、以下に示されるような追い出し制御が実施される。
まず、本実施形態では、各セット１０３のキャッシュブロック１０２毎にＰＰＩＤが記憶されるとともに、＃１から＃ｎのインデックス値毎に、各ＰＰＩＤ値（例えば１〜４）に対するＭＡＸ ＷＡＹ数（最大ウェイ数）１０５が記憶される。或るインデックス値における或るＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５は、そのインデックス値において記憶可能なそのＰＰＩＤ値を有するキャッシュブロック１０２の最大数を示す。本実施形態では、各インデックス値毎に、各ＰＰＩＤ値のＭＡＸ ＷＡＹ数１０５が守られるように、追い出し制御が実施される。
【００３２】
各ＰＰＩＤ値毎のＭＡＸ ＷＡＹ数１０５の割合は、オペレーティングシステム（ＯＳ）が定めたＰＰＩＤ値毎のキャッシュブロック数に基づいて決定される。この場合、キャッシュメモリ１０１中でのＰＰＩＤ値間のサイズ割当て、すなわち各ＰＰＩＤが使用できるキャッシュメモリの領域のサイズを変更する場合には、各インデックス値へのアクセス発生時に、そのインデックス値の各ＰＰＩＤ値毎のＭＡＸ ＷＡＹ数１０５を順次変更する。キャッシュメモリ１０１を単純にＰＰＩＤ値によって分割すると、分割量を変更する場合にキャッシュメモリ１０１内の全キャッシュブロック１０２のＰＰＩＤ情報を書き換えなくてはいけないので更新オーバヘッドが大きくなる。これに対して、本実施形態では、一時期に全キャッシュブロック１０２の書換えを行わなくても、インデックス値単位で動的にＰＰＩＤ間のサイズ割当ての変更が可能となるため、情報の更新を最小限に抑えることにより、低オーバヘッドで分割量の変更を行うことが可能となる。
【００３３】
図２は、ＯＳが保有する、ＯＳが各ＰＰＩＤ値に与える最大キャッシュブロック数のテーブルのデータ構成例を示す図である。ＰＰＩＤ値がＰ1，Ｐ２，Ｐ３のとき、最大キャッシュブロック数は例えば、それぞれ６４,２１,１１である。さらに図３は、図２に示されるテーブル内容に従って本実施形態において実施されるキャッシュメモリ１０１の分割例を示す図である。この分割処理においては、キャッシュウェイ１０４の数が８ウェイである場合の例について示されている。キャッシュメモリのインデックス数は１０ビットもしくは１１ビットで表わされる数存在するが、ここでは説明を簡単にするため、インデックス方向には例として１６個のインデックスがあるものとして説明を行なう。インデックス値毎に、ＰＰＩＤ値（図３ではＰ１、Ｐ２、Ｐ３）毎のＭＡＸ ＷＡＹ数１０５が保持される。そして、キャッシュメモリ１０１全体で、各ＰＰＩＤ値に与えられるＭＡＸ ＷＡＹ数１０５が、図２のテーブルで設定されたＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数に等しくなるように、各インデックス値毎のＭＡＸ ＷＡＹ数１０５が設定される。
【００３４】
指定されたインデックス値において、或るＰＰＩＤ値を有するキャッシュブロック１０２についてキャッシュミスが発生したときには、次のような動作が実行される。すなわち、そのセット１０３上で、そのＰＰＩＤ値に関して既に配分済みのキャッシュウェイ数の合計と、そのＰＰＩＤ値に対応して記憶されているＭＡＸ ＷＡＹ数１０５とが比較される。配分済みのキャッシュウェイ数の合計がＭＡＸ ＷＡＹ数１０５に満たない場合は、以下の動作が実行される。すなわち、そのインデックス値上で、他のＰＰＩＤ値に対して配分済みのキャッシュブロック１０２の中で、配分済みのキャッシュウェイ数の合計が当該ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５を越えているキャッシュブロックの中から置換ブロックが選択される。
【００３５】
図４は、キャッシュミス発生時のキャッシュブロックのリプレース動作を示す説明図である。キャッシュミスが発生したとき、図４に示されるように、例として、ＰＰＩＤ値Ｐ１に４ブロック、Ｐ２に３ブロック、Ｐ３に１ブロックが割り当てられていたとする。ここで、Ｐ１についてキャッシュミスが発生したときには、Ｐ１はそのインデックス値上でのＭＡＸ ＷＡＹ数１０５を超えておらず、一方、Ｐ２がそのインデックス値上でのＭＡＸ ＷＡＹ数１０５を既に越えている。このため、ＰＰＩＤ値としてＰ２を有するキャッシュブロック１０２の中からリプレース候補が選択され、図４中の矢印のブロックのデータがメインメモリから読み出されたデータに置換され、ＰＰＩＤ値Ｐ１の要求するデータがロードされる。
【００３６】
このように、本実施形態では、キャッシュミスのアクセスが発生したタイミングで、各ＰＰＩＤに対するキャッシュサイズの割当てが動的に変更される。
キャッシュメモリ１０１における各ＰＰＩＤに対するキャッシュサイズの割当てを変更する場合は、ＭＡＸ ＷＡＹ数１０５のマップを変更するだけでよい。ＭＡＸ ＷＡＹ数１０５の指示は、キャッシュアクセス命令に付随させて行うことができる。従来技術では、キャッシュメモリ１０１内の全キャッシュブロック１０２のプロセスＩＤを書き換えることが必要であった。これに対して、本実施形態では、キャッシュアクセス命令に付随して随時各ＰＰＩＤに対するキャッシュサイズの割当を変化させることができる。なお、全てのインデックス値について、一括して書き換えてもよい。
【００３７】
また、同時にスケジューリングされる各プロセスが要求するウェイ数の合計が、実装されているキャッシュメモリ１０１のウェイ数を超えていても、ウェイの取り合いになるだけでシステム停止などの問題は発生しない。
【００３８】
図２のテーブル例の場合、ＰＰＩＤ値３に与えるキャッシュブロック数は１１である。このため、ＰＰＩＤ値３は、インデックス値の数（図３では１６インデックス）の全てに対して、キャッシュブロックを割り当てることができない。このため、図３に示されるキャッシュメモリ１０１の分割例において、次のようなインデックス方向の割り当て変更が必要となる。すなわち例えば、インデックス方向の先頭５インデックスの領域ではＰＰＩＤ値Ｐ３に対するＭＡＸ ＷＡＹ数１０５は０とされ、それ以後１１インデックスの領域でのみＰＰＩＤ値Ｐ３に対するＭＡＸ ＷＡＹ数１０５が１とされる。このため、ＰＰＩＤ値３に対応するキャッシュアクセスが発生した場合、命令アドレス中のインデックスによって、先頭５インデックスの領域が指定されないようにし、常に後側１１インデックスの領域が指定されるようにする必要がある。
【００３９】
この機能として、本実施形態では、図５に示されるハッシュ機構としてのアドレスハッシュユニット５０１が実装される。このハッシュ機構により、指定された命令アドレスをハッシュして得られるインデックスが、禁止された領域のインデックスを生成しないようにされる。
【００４０】
また、ＯＳが管理するプロセスＩＤは、例えば１６ビット以上の値を持つ。従って、１６ビット以上の値で示されるプロセスＩＤをキャッシュメモリ１０１中の各キャッシュブロック１０２に保持すると、ハードウェア追加量が大きくなる。そこで、本実施形態では、図６に示されるように、プロセスＩＤマップユニット６０１が実装される。このプロセスＩＤマップユニット６０１は、キャッシュアクセス命令を実行しているプロセスのプロセスＩＤを、キャッシュメモリ１０１のハードウェアが取扱い可能な物理プロセスＩＤ ＰＰＩＤにマップする。ＰＰＩＤは、例えば分割されたセット数を指定する２ビットの値を持てばよいため、例えば１６ビット以上の値で示されるプロセスＩＤを保持する場合よりも、キャッシュメモリ１０１のハードウェア量の増大を防ぐことができる。
【００４１】
以上のハードウェア機構により、ＯＳは、プロセッサをプロセス間の共有資源として時分割でスケジューリングして使用するのと同様に、キャッシュメモリ１０１をプロセス間の共有資源としてサイズと時間で自由にスケジューリング可能となる。
【００４２】
例えば、図２のテーブル例のように各ＰＰＩＤ値にキャッシュブロック数を割り当てた場合には、下記のようにキャッシュブロック数と当該キャッシュブロック数の使用期間を乗算した値が大きくなれば、優先度を下げる、もしくはキャッシュ割当てブロック数を減らすといったスケジューリングを行うことができる。
P1： 64 × 1000 マイクロ秒 = 64,000 → 例 : 優先度を下げる
P2： 21 × 500 マイクロ秒 = 10,500
P4： 11 × 2000 マイクロ秒 = 22,000
【００４３】
以上のように、本実施形態では、キャッシュメモリ領域をキャッシュブロック単位で任意に分割することができる。従って、共有キャッシュメモリをプロセッサが有する演算器等の演算リソースと同様にリソースとして管理し、プロセススケジューリングを最適化することが可能となり、プロセッサの実効性能を向上させることが可能となる。
【００４４】
図７および図８は、図１に示されるキャッシュメモリ１０１のブロック構成に対応するハードウェア構成例を示す図である。図７および図８において、図１の場合と同じ機能部分には同じ番号を付してある。
【００４５】
図１に示されるキャッシュブロック１０２は、例えば、データ部（キャッシュデータ部）とタグ部（キャッシュタグ部）が別々のＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）によって実装される。図７および図８の実装例では、キャッシュタグ部７０１において、各セット１０３を構成するキャッシュブロック１０２のタグ情報７０２としては、有効フラグ（１ビット）、タグ（１５ビット）、ＰＰＩＤ（２ビット）が記憶される。また、各インデックス値毎の各ＰＰＩＤ値に対するＭＡＸ ＷＡＹ数１０５も、キャッシュタグ部７０１内に保持される。
【００４６】
なお、タグ情報７０２とＭＡＸ ＷＡＹ数１０５は、さらに別々のＲＡＭに記憶されてもよい。
【００４７】
図７において、メモリアクセス要求によりキャッシュアクセスが発生すると、＃１〜＃４の各キャッシュウェイ１０４から、指定されたインデックス値上の各キャッシュブロック１０２（＃ｉ）のタグ値が読み出され、＃１〜＃４のコンパレータ１０６に入力する。この結果、図１で説明したように、＃１〜＃４のコンパレータ１０６のうち、要求元タグ値との一致を検出したコンパレータ１０６がタグ値を比較したキャッシュブロック１０２（＃ｉ）が、キャッシュヒットしたということになる。そして、キャッシュヒットが検出されたキャッシュブロック１０２（＃ｉ）に対してキャッシュデータ部（後述する図１８の１８０４を参照）上のデータが読み書きされる。
【００４８】
一方、図８において、メモリアクセス要求によりキャッシュアクセスが発生すると、＃１〜＃４の各キャッシュウェイ１０４から、指定されたインデックス値上の各キャッシュブロック１０２（＃ｉ）のＰＰＩＤ値が読み出され、＃１〜＃４のコンパレータ８０１に入力する。
【００４９】
＃１〜＃４のコンパレータ８０１は、読み出された各キャッシュブロック１０２（＃ｉ）内のＰＰＩＤ値と、要求元ＰＰＩＤの値との一致／不一致を検出する。要求元ＰＰＩＤは、キャッシュアクセス命令を実行しているプロセスのプロセスＩＤをプロセスＩＤマップユニット６０１（図６）で変換して得られる値である。この結果、キャッシュブロック１０２（＃ｉ）のＰＰＩＤ値が要求元ＰＰＩＤの値と一致するウェイのコンパレータ８０１の出力は例えば１、一致しないウェイのコンパレータ８０１の出力は例えば０となる。
【００５０】
従って、＃１〜＃４のコンパレータ８０１は、キャッシュブロック１０２（＃ｉ）のＰＰＩＤ値が要求元ＰＰＩＤの値と一致するウェイを示すビットマップを出力することになる。
【００５１】
本実施形態では、このビットマップに含まれる１の数を数え上げることにより、キャッシュミスが発生したインデックス値上で、キャッシュミスを発生させたＰＰＩＤ値に関して既に配分済みのキャッシュウェイ数の合計を算出することができる。そして、前述したように、そのインデックス値上で、キャッシュミスを発生させたＰＰＩＤ値に関して既に配分済みのキャッシュウェイ数の合計と、そのＰＰＩＤ値に対応して記憶されているＭＡＸ ＷＡＹ数１０５とが比較される。ＭＡＸ ＷＡＹ数１０５としては、図７または図８に示されるように、各インデックス毎に、図２または図３に示される各ＰＰＩＤ値Ｐ１，Ｐ２，Ｐ３に対応する値が、キャッシュタグ部７０１に記憶されている。図２，図３には示していないが、Ｐ４についても同様である。そして、上記Ｐ１，Ｐ２，Ｐ３，Ｐ４などに対応するＭＡＸ ＷＡＹ数１０５のうち、要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数が、配分済みのキャッシュウェイ数の合計との比較処理の対象とされる。そして、配分済みのキャッシュウェイ数の合計がＭＡＸ ＷＡＹ数１０５に満たない場合は、そのインデックス値上で、他のＰＰＩＤ値に対して配分済みのキャッシュブロック１０２の中で当該ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５を越えているものの中から置換ブロックが選択されることになる。
【００５２】
＃１〜＃４のコンパレータ８０１が出力するビットマップに対して置換ブロックを決定するための置換ウェイ制御回路のハードウェア構成については、図１１で後述する。
【００５３】
図９は、ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数のテーブル（図２）に基づいて、各インデックス値毎に各ＰＰＩＤ値に対するＭＡＸ ＷＡＹ数１０５（図３）を決定する処理を示す動作フローチャートである。この処理は例えば、図７、図８を含むキャッシュシステムを制御するプロセッサ（例えば後述するＣＰＵコア１８０２）が実行するＯＳの処理の一部である。
【００５４】
まず、図２のテーブル構成が参照され、最初のプロセスに割り当てるブロック数を、１ウェイあたりのインデックス方向のブロック数で除算した値をＣとする（ステップＳ９０１）。すなわち、Ｃは、キャッシュメモリ全体で当該プロセスに割り当てられるウェイ数である。
【００５５】
次に、当該プロセスに割り当てるブロック数を１ウェイあたりのブロック数で割った余りの値をＲとする（ステップＳ９０２）。
例えば図２の最初のＰＰＩＤ値Ｐ１のキャッシュブロック数は６４である。また、図３において、１ウェイあたりのインデックス方向のブロック数は１６ブロックである。従って、Ｃ＝６４／１６＝４、その除算の余りは０であるからＲ＝０となる。
【００５６】
次に、すべてのインデックスについてＭＡＸ ＷＡＹ数＝Ｃを設定する（ステップＳ９０３）。上述のＰＰＩＤ値Ｐ１の例では、ＭＡＸ ＷＡＹ数１０５＝４が設定される。
次に、初期値０から始まって前回のＲの値を順次累算することで、Ｒ個分のＭＡＸ ＷＡＹ数の増加処理を行う開始位置（ＭＡＸ ＷＡＹ数増加開始位置）を更新する（ステップＳ９０４）。続いて、ＭＡＸ ＷＡＹ数増加開始位置からＲ個のインデックス分だけ、ＭＡＸ ＷＡＹ数１０５を１ずつ増加する（ステップＳ９０５）。上述のＰＰＩＤ値Ｐ１の例では、Ｒ＝０であるため、ステップＳ９０５の増加処理は実行されず、また、ＭＡＸ ＷＡＹ数増加開始位置は、初期値０のままである。
【００５７】
次に、Ｃ＝０であるか否かを判定する（ステップＳ９０４）。
Ｃ＝０でなくステップＳ９０４の判定がＮＯならば、ステップＳ９０８に移行する。この結果、ＰＰＩＤ値Ｐ１に関するＭＡＸ ＷＡＹ数１０５は、図３に示されるように、すべてのインデックス値に対して４となる。
【００５８】
ステップＳ９０４の判定の後、図２のテーブル構成例に対応するデータ構成を参照して、次のプロセスがあるか否かが判定される（ステップＳ９０８）。
次のプロセスがありステップＳ９０８の判定がＹＥＳならば、ステップＳ９０１からの処理を繰り返す。
【００５９】
図２のテーブル構成例において、ＰＰＩＤ値Ｐ１の次にまだＰＰＩＤ値Ｐ２がある。このため、ステップＳ９０１、Ｓ９０２が再び実行される。図２のＰＰＩＤ値Ｐ２のキャッシュブロック数は２１であるため、Ｃ＝２１／１６＝１、その除算の余りは５であるからＲ＝５となる。
さらに、ステップＳ９０３が実行される。ＰＰＩＤ値Ｐ２の例では、ＭＡＸ ＷＡＹ数１０５＝１が設定される。
【００６０】
次に、ステップＳ９０４およびＳ９０５が実行される。ＰＰＩＤ値Ｐ２の例では、まず、ＭＡＸ ＷＡＹ数増加開始位置は、前記アクセスのＰ１におけるＲ＝０を使って、初期値０＋Ｒ＝０となる。そして、今回のＲ＝５であるため、ＭＡＸ ＷＡＹ数増加開始位置＝０からＲ＝５個分だけＭＡＸ ＷＡＹ数１０５が＋１される。この結果、ＰＰＩＤ値Ｐ２に関するＭＡＸ ＷＡＹ数１０５は、図３に示されるように、最初の５インデックス値に対して２、残りの１１インデックス値に対して１となる。
【００６１】
ステップＳ９０５の処理の後、ステップＳ９０６の判定がＮＯとなって、ステップＳ９０８が判定される。図２のテーブル構成例において、ＰＰＩＤ値Ｐ２の次にまだＰＰＩＤ値Ｐ３がある。このため、ステップＳ９０８の判定がＹＥＳとなり、ステップＳ９０１、Ｓ９０２が再び実行される。図２のＰＰＩＤ値Ｐ３のキャッシュブロック数は１１であるため、Ｃ＝１１／１６＝０、その除算の余りは１１であるからＲ＝１１となる。
【００６２】
さらに、ステップＳ９０３が実行される。ＰＰＩＤ値Ｐ３の例では、ＭＡＸ ＷＡＹ数１０５＝０が設定される。
【００６３】
次に、ステップＳ９０４およびＳ９０５が実行される。ＰＰＩＤ値Ｐ３の例では、まず、ＭＡＸ ＷＡＹ数増加開始位置は、前記アクセスのＰ２におけるＲ＝５が累算されて５となる。そして、今回のＲ＝１１であるため、ＭＡＸ ＷＡＹ数増加開始位置＝５からＲ＝１１個分だけＭＡＸ ＷＡＹ数１０５が＋１される。この結果、ＰＰＩＤ値Ｐ３に関するＭＡＸ ＷＡＹ数１０５は、図３に示されるように、最初の５インデックス値に対して０、残りの１１インデックス値に対して１となる。
【００６４】
次に、Ｃ＝０であるからステップＳ９０６の判定がＹＥＳとなって、ステップＳ９０７が実行される。
ここでは、ＰＰＩＤ値Ｐ３について、図５のアドレスハッシュユニット５０１を動作させるためのハッシュ有効化レジスタ（後述する図１３の１３０２のＰ３の行を参照）をセットする。
【００６５】
ステップＳ９０７の処理の後、図２のテーブル構成例において、ＰＰＩＤ値Ｐ３の次にはもうＰＰＩＤ値がない。このため、ステップＳ９０８の判定がＮＯとなって、図９のフローチャートによるＭＡＸ ＷＡＹ数１０５の決定処理を終了する。なお、ＰＰＩＤ値Ｐ４がある場合には、さらにＰ４についても同様の処理が繰り返される。
【００６６】
以上説明したフローチャートにより、ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数のテーブル（図２）に基づき、各インデックス値毎に各ＰＰＩＤ値に対するＭＡＸ ＷＡＹ数１０５（図３）を適切に決定可能となる。
【００６７】
図１０は、図９のフローチャートの処理をプログラム処理として実行した場合のプログラム擬似コードである。各プログラムステップの左には、図９の対応する処理のステップ番号を付してある。
【００６８】
まず、各変数NP,NB,C,B,R,Oが以下のように定義される。
NP : Number of Processes プロセス数
NB : Number of Blocks per way １ウェイあたりのブロック数
C[p] : プロセスpに割り当てるウェイ数
B[p] : プロセスpに割り当てるブロック数
R[p] : プロセスpにおいて１ウェイ分に満たないブロック数
O[p] : ＭＡＸ ＷＡＹ数増加開始位置
【００６９】
まず、図２のテーブル構成から参照される各プロセスｐについて、プロセスｐに割り当てるブロック数B[p]を、１ウェイあたりのインデックス方向のブロック数で除算することにより、プロセスpに割り当てるウェイ数C[p]を算出する（ステップＳ９０１）。
【００７０】
次に、プロセスｐに割り当てるブロック数B[p]を、１ウェイあたりのインデックス方向のブロック数で除算した余りとして、プロセスpにおいて１ウェイ分に満たないブロック数R[p]を算出する（ステップＳ９０２）。
【００７１】
次に、ＭＡＸ ＷＡＹ数増加開始位置O[p]=ｓとする（ステップＳ９０４）。また、s=s+R[p]として更新する（ステップＳ９０５）。
次に、プロセスｐについて、C[p]=0であるならば（ステップＳ９０６）、set_reg_hashval(p)関数を呼び出し、図５のアドレスハッシュユニット５０１を動作させるためのハッシュ有効化レジスタ（後述する図１３の１３０２を参照）をセットする（ステップＳ９０７）。
【００７２】
以上の動作が図２のテーブル構成から参照される全プロセスについて実行される。この結果、各プロセスｐ毎に、プロセスpに割り当てるウェイ数C[p]、プロセスpにおいて１ウェイ分に満たないブロック数R[p]、およびＭＡＸ ＷＡＹ数増加開始位置O[p]が算出される。
【００７３】
これらの値を使って、まず、各プロセスｐ毎に、キャッシュタグ部７０１内のすべてのインデックスについて、ＭＡＸ ＷＡＹ数＝C[p]を設定するＳＴＯＲＥ命令（後述する図１２参照）が実行される。
【００７４】
次に、各プロセスｐ毎に、キャッシュタグ部７０１内のＭＡＸ ＷＡＹ数増加開始位置からR[p]個のインデックス分だけ、ＭＡＸ ＷＡＹ数＝C[p]+1を設定するＳＴＯＲＥ命令（後述する図１２参照）が実行される。
【００７５】
以上のプログラム処理により、図９のフローチャートに対応するＭＡＸ ＷＡＹ数１０５の決定処理が実行される。
図１１は、図８の＃１〜＃４のコンパレータ８０１が出力するビットマップに対して置換ブロックを決定するための置換ウェイ制御回路のハードウェア構成例を示す図である。置換ウェイ制御回路は、ビット数え上げ器１１０１と置換ウェイ候補決定回路１１０２と置換ウェイマスク生成回路１１０３とから構成される。
【００７６】
ＰＰＩＤマッチしたビットマスク１１０８は、図８の＃１〜＃４のコンパレータ８０１の出力である。また、ＭＡＸ ＷＡＹ数１０５は、キャッシュタグ部７０１（図８参照）において、現在のキャッシュアクセスのインデクス値に対応して読み出される各ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５である。
【００７７】
まず、ビット数え上げ器１１０１は、ビットマスク１１０８のビットのうち１となっているビットを数え上げる。この結果、現在のキャッシュアクセスを発生させたＰＩＤに対応するＰＰＩＤ（要求元ＰＰＩＤ）に現在割り当てられているキャッシュウェイ数の合計が算出される。
【００７８】
次に、選択回路１１０４が、各ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５のうち、要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数１０５を選択して出力する。
比較器１１０５は、ビット数え上げ器１１０１が出力する要求元ＰＰＩＤに現在割り当てられているキャッシュウェイ数と、選択回路１１０４が出力する要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数１０５とを比較する。
【００７９】
比較器１１０５が比較した結果、要求元ＰＰＩＤに現在割り当てられているキャッシュウェイ数の合計が要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数１０５に満たない場合には、選択回路１１０７は次のように動作する。すなわち、選択回路１１０７は、ビットマスク１１０８の各ビットをインバータ１１０６で反転して得られるビットマスクを選択し、置換ウェイ候補を示すビットマスク１１０９として出力する。これにより、現在のキャッシュアクセスに対応するセット１０３上で、要求元ＰＰＩＤ値以外の他のＰＰＩＤ値に対して配分済みのキャッシュブロック１０が存在するウェイが、置換ウェイ候補とされる。
【００８０】
一方、比較器１１０５が比較した結果、要求元ＰＰＩＤに現在割り当てられているキャッシュウェイ数の合計が要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数１０５に達している場合には、選択回路１１０７は次のように動作する。すなわち、選択回路１１０７は、ビットマスク１１０８をそのまま選択し、置換ウェイ候補を示すビットマスク１１０９として出力する。これにより、現在のキャッシュアクセスに対応するセット１０３上で、要求元ＰＰＩＤ値に対して配分済みのキャッシュブロック１０が存在するウェイが、置換ウェイ候補とされる。
【００８１】
置換ウェイマスク生成回路１１０３は、置換ウェイ候補を示すビットマスク１１０９が示す置換ウェイ候補から、置換ウェイを選択し、置換ウェイを示す置換ウェイマスクを生成して出力する。より具体的には、ビットマスク１１０９が要求元ＰＰＩＤ以外のＰＰＩＤを置換ウェイ候補として示しているときには、置換ウェイマスク生成回路１１０３は、次のように動作する。すなわち、置換ウェイマスク生成回路１１０３は、キャッシュアクセスに対応するセット１０３上で、他のＰＰＩＤ値に対し配分済みのキャッシュブロック１０２の中で、配分済みのキャッシュウェイ数の合計が当該ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５を越えているキャッシュブロックが選択される。そして、選択されたキャッシュブロックのウェイに対応するビット位置のみが１となる、４ビットからなる置換ウェイマスクを生成する。ビットマスク１１０９が要求元ＰＰＩＤを置換ウェイ候補として示しているときには、置換ウェイマスク生成回路１１０３は、例えばＬＲＵアルゴリズムによって、最も長い期間アクセスなされなかったウェイから選択された置換ウェイのみが１となる４ビットからなる置換ウェイマスクを生成する。
【００８２】
キャッシュミスしたメモリアクセス要求に対応するデータはキャッシュデータ部に、また、タグおよびＰＰＩＤはキャッシュタグ部７０１（図７参照）内の、置換ウェイマスクの４ビットのデータのうち値が１となるビット位置に対応するウェイに出力される。また、メモリアクセス要求内のインデックスが、キャッシュデータ部、キャッシュタグ部７０１のセット１０３を指定する。
【００８３】
これにより、キャッシュデータ部およびキャッシュタグ部７０１において、指定されたセット１０３の選択されたウェイのキャッシュブロック１０２に、データ、タグ、およびＰＰＩＤが書き込まれる。
【００８４】
なお、キャッシュデータ部に書き込まれるデータは、メモリアクセス要求が読出し要求の場合には、図示しないメインメモリ上の対応するアドレスから読み出されたデータである。また、メモリアクセス要求が書込み要求の場合には、当該書込み要求に指定されている書込みデータである。
【００８５】
図１２は、各インデックス値のＭＡＸ ＷＡＹ数１０５を更新するためのＭＡＸ ＷＡＹ数更新機構を示す実施例を説明する図である。
ＭＡＸ ＷＡＹ保持部１２０１には、プロセッサの命令制御部（例えば後述する図１８の１８０６）からアドレスを指定してＭＡＸ ＷＡＹ数１０５の更新値を書き込むことができる。
【００８６】
このとき、命令制御部は、ＭＡＸ ＷＡＹ数１０５を更新するためのＳＴＯＲＥ命令が指定する物理アドレスは、例えば、５２ビットの物理アドレス空間を有するとする。
上記のＳＴＯＲＥ命令が指定する物理アドレスは、ＭＡＸ ＷＡＹ数保持部１２０１内のアドレスマップユニット１２０２によって、キャッシュのインデックス数に等しいアドレス空間を有するＲＡＭ１２０３上の該当する記憶領域をアクセス可能なアドレスとして、例えば「０ｘ００Ｃ」に変換される。すなわちアドレスマップユニット１２０２は例えば、指定されたアドレス「０ｘ１０００００００００００Ｃ」から上位のアドレス情報「０ｘ１０００００００００」を削除して、アドレスを「０ｘ００Ｃ」に変換する処理を実行する。そして、この変換されたアドレスによって指定されるＲＡＭ１２０３内の記憶領域、例えば「０ｘ００Ｃ」に、ＳＴＯＲＥ命令によって４バイトのデータ、例えば「０ｘ０４０２０１０１」が書き込まれる。そして例えば、この４バイトのデータのうち、最上位の１バイト「０４」が、図２または図３に示されるＰＰＩＤ＝Ｐ１に対応するＭＡＸ ＷＡＹ数１０５＝４を指定する。また、次の上位１バイト「０２」が、同じくＰＰＩＤ＝Ｐ２に対応するＭＡＸ ＷＡＹ数１０５＝２を指定する。同様に、次の上位１バイト「０１」が、同じくＰＰＩＤ＝Ｐ３に対応するＭＡＸ ＷＡＹ数１０５＝１を指定する。そして、最下位の１バイト「０１」が、図２や図３では図示しないが、ＰＰＩＤ＝Ｐ４に対応するＭＡＸ ＷＡＹ数１０５＝１を指定する。この１つのＳＴＯＲＥ命令によって書き込まれる４バイト１組のデータが、図７または図８に示される１つのインデックス値上のＰ１〜Ｐ４に対応する１組のＭＡＸ ＷＡＹ数１０５となる。
【００８７】
このように、ＲＡＭ１２０３上のデータは、４バイトを１組として管理されるため、ＲＡＭ１２０３を更新するために命令制御部によって指定される物理アドレスは、４バイトおきに指定されることになる。例えば、「０ｘ１００００００００００００」の次は「０ｘ１０００００００００００４」のごとくである。
【００８８】
なお、図８等で前述したように、キャッシュアクセス時には、例えば、メモリアクセスのためのアドレス１０７内のインデックスの値によって、キャッシュタグ部７０１が、キャッシュメモリ１０１に含まれるＲＡＭ１２０３上の該当する記憶領域にアクセスする。
【００８９】
前述したように、キャッシュメモリ１０１のＰＰＩＤ値毎の容量割当てを変更する場合は、ＭＡＸ ＷＡＹ数１０５を保持するキャッシュタグ部７０１内のＲＡＭ１２０３内での各インデックス値毎のＭＡＸ ＷＡＹ数１０５の割当てを変更すればよい。この場合に、上述のＳＴＯＲＥ命令によるＭＡＸ ＷＡＹ数１０５の更新指示は、キャッシュアクセス命令に付随させて行ってもよいし、全インデックス値について一括して実行されてもよい。
【００９０】
以上説明した図１２のＭＡＸ ＷＡＹ数更新処理は、例えば後述する図１８に示されるキャッシュシステム１８０１内のキャッシュメモリ制御部１８０５が、ＣＰＵコア１８０２内の命令制御部１８０６からの指示に従って実行する。
【００９１】
図１３は、図５のアドレスハッシュユニット５０１のハードウェア構成例を示す図である。
ハッシュ有効化レジスタ１３０２は、ＰＰＩＤ値毎に、有効ビット、インデックス数、およびオフセットインデックス数を記憶する。有効ビットとしては、例えば、ハッシュ処理を実行する場合に有効を示す値１を、実行しない場合に無効を示す値０がセットされる。インデックス数としては、１ウェイ分に満たない分のインデックス増加処理を行うブロック数R[p]がセットされる。オフセットインデックス数としては、上記増加処理の実行を開始するインデックス位置＝ＭＡＸ ＷＡＹ数増加開始位置Ｏ［ｐ］がセットされる。
【００９２】
図９及び図１０で前述したように、プロセスｐについて、Ｃ［ｐ］＝０であるならば、set_reg_hashval(p)関数が呼び出されて、ハッシュ有効化レジスタ１３０２へのセットが実行される。
【００９３】
次に、図１３において、選択回路１３０３は、ハッシュ有効化レジスタ１３０２上の要求元ＰＰＩＤ値と一致するＰＰＩＤ値に対応するエントリから、有効ビット、インデックス数、およびオフセットインデックス数を読み出して、モジュロ演算器１３０１に与える。要求元ＰＰＩＤ値は、キャッシュアクセス命令を実行しているプロセスのプロセスＩＤを、プロセスＩＤマップユニット６０１（図６）で変換して得られる値である。
【００９４】
モジュロ演算器１３０１には、選択回路１３０３から要求元ＰＰＩＤに対応する有効ビット、インデックス数、オフセットインデックス数が入力するほか、キャッシュアクセス命令によって指定されるアドレス１０７の上位ビット部分が入力する。
【００９５】
モジュロ演算器１３０１は、有効ビットがセットされているアドレス１０７の上位ビット部分をインデックス数で割った余りにオフセットインデックス数を加えた値を計算する。計算結果は、キャッシュタグ部７０１（図７）およびキャッシュデータ部（後述する図１８の１８０４を参照）に、新たなインデックスとして出力される。
【００９６】
モジュロ演算器１３０１は、もし有効ビットがセットされていなければ、アドレス１０７のインデックスをそのまま、キャッシュタグ部７０１（図７）およびキャッシュデータ部（後述する図１８の１８０４を参照）に、新たなインデックスとして出力する。
【００９７】
以上の構成を有するアドレスハッシュユニット５０１の具体的な動作について、図１４および図１５の動作説明図と、前述した図２、図３を用いて説明する。
ここで、図７および図８に示されるキャッシュタグ部７０１のハードウェア構成においては、キャッシュタグ部７０１の具体的なサイズは例えば次のようになる。すなわち、プログラムで指定される３２ビットのアドレス１０７において、下位７ビットでキャッシュライン内オフセットが指定され、その上位１０ビットでインデックス、さらにその上位１５ビットでタグが指定される例が示されている。従って、この例の場合は、１０ビットのインデックスによって指定されるセット１０３のライン数ｎは２の１０乗＝１０２４であるが、キャッシュタグ部７０１のサイズはこれに限定されるものではなく、システムごとに適切なその他のサイズ値を採用することができる。システムごとに適切なその他のサイズ値を採用する場合には、アドレス１０７も適切なビット幅を採用できる。
【００９８】
図１４および図１５では、理解を容易にするために、アドレス１０７が１６ビット、キャッシュライン内オフセットが７ビット、インデックスが４ビット、タグが５ビットである場合の例について説明する。この例の場合、セット１０３のライン数ｎは、図３のインデックス方向の行数として示されるように、２の４乗＝１６となる。
【００９９】
図１３のハッシュ有効化レジスタ１３０２において、図３に示されているＰＰＩＤ値がＰ１，Ｐ２，Ｐ３と、これらＰ１，Ｐ２，Ｐ３以外のＰ−ＯＴＨＥＲＳの場合に、Ｃ＝０となるケースは、ＰＰＩＤ値＝Ｐ３のときで、全ブロック数はインデックス方向のインデックス数１６に満たない。このためＰ３のインデックス数としては、１ウェイ分に満たない分のブロック数Ｒ[Ｐ３]＝５（図１０参照）がセットされる。オフセットインデックス数としては、上記増加処理の実行を開始するインデックス位置＝ＭＡＸ ＷＡＹ数増加開始位置Ｏ［ｐ］がセットされる。例えば図３において、Ｐ３のケースの場合、Ｒ[Ｐ２]＝５、すなわちＣ＝０となる直前のプロセスＰ２において図９のＳ９０２で計算された当該プロセスＰ２に割り当るブロック数１５を１ウェイあたりのブロック数１０で割った余りＲ[Ｐ２]＝５に等しい値５が、Ｏ［Ｐ３］としてセットされる。
【０１００】
図９及び図１０で前述したように、プロセスｐについて、Ｃ［ｐ］＝０であるならば、set_reg_hashval(p)関数が呼び出されて、ハッシュ有効化レジスタ１３０２へのセットが実行される。
【０１０１】
すなわち、ＰＰＩＤ値＝Ｐ３について、Ｃ［Ｐ３］＝０となるため、ハッシュ有効化レジスタ１３０２のＰ３に対応するエントリに、以下の値がセットされる。すなわち、図１４に示されるように、有効ビット＝１、インデックス数＝Ｒ［Ｐ３］＝１１、オフセットインデックス数＝ Ｒ[Ｐ２]＝５がセットされる。その他のＰＰＩＤ値Ｐ１，Ｐ２等については、Ｃ［ｐ］＝０とならないため、ハッシュ有効化レジスタ１３０２の各ＰＰＩＤ値Ｐ１，Ｐ２に対応するエントリの内容は、図１４に示されるように、共に各値が０のクリア状態となる。
【０１０２】
ここで、図１４に示されるように、要求元ＰＰＩＤ値として「３」が入力したとする。この結果、選択回路１３０３が、ハッシュ有効化レジスタ１３０２上の要求元ＰＰＩＤ値と一致するＰＰＩＤ値＝Ｐ３に対応するエントリから、有効ビット＝１、インデックス数＝１１、およびオフセットインデックス数＝５を読み出す。そして、選択回路１３０３は、それらの数値データをモジュロ演算器１３０１に与える。モジュロ演算器１３０１は、上述のようにもし有効ビットが１にセットされていれば、アドレス１０７のタグ＋インデックスの上位９ビットのビット値をインデックス数＝１１で割った余りにオフセットインデックス数＝５を加算し、その加算結果を新たなインデックスとして出力する。
【０１０３】
ここで例えば、要求元ＰＰＩＤ値＝３で、アドレス１０７として、下記のアドレスがそれぞれ入力した場合を考える。
０ｘＤ１５２
０ｘＤ１Ｄ２
０ｘＤ２５２
０ｘＤ２Ｄ２
０ｘＤ３５２
０ｘＤ３Ｄ２
０ｘＤ４５２
０ｘＤ４Ｄ２
０ｘＤ５５２
０ｘＤ５Ｄ２
０ｘＤ６５２
０ｘＤ６Ｄ２
０ｘＤ７５２
【０１０４】
図１４では、アドレス１０７として「０ｘＤ５５２」が入力された場合が示されている。
これらの場合、上位９ビットのビット値および各々に対応する１０進値は、それぞれ以下のようになる。
１１０１０００１０＝４１８
１１０１０００１１＝４１９
１１０１００１００＝４２０
１１０１００１０１＝４２１
１１０１００１１０＝４２２
１１０１００１１１＝４２３
１１０１０１０００＝４２４
１１０１０１００１＝４２５
１１０１０１０１０＝４２６
１１０１０１０１１＝４２７
１１０１０１１００＝４２８
１１０１０１１０１＝４２９
１１０１０１１１０＝４３０
【０１０５】
図１４では、アドレス１０７「０ｘＤ５５２」における上位ビット９ビットが、「１１０１０１０１０」で、１０進表現は「４２６」であることが示されている。
【０１０６】
モジュロ演算器１３０１は、上記各上位９ビット値に対して、それぞれ以下のようにして、インデックス数＝１１で割った余りにオフセットインデックス数＝５を加算し、その加算結果を新たなインデックスとして出力する。
４１８÷１１＝３８余り０、余り０＋オフセットインデックス数５＝５
４１９÷１１＝３８余り１、余り１＋オフセットインデックス数５＝６
４２０÷１１＝３８余り２、余り２＋オフセットインデックス数５＝７
４２１÷１１＝３８余り３、余り３＋オフセットインデックス数５＝８
４２２÷１１＝３８余り４、余り４＋オフセットインデックス数５＝９
４２３÷１１＝３８余り５、余り５＋オフセットインデックス数５＝１０
４２４÷１１＝３８余り６、余り６＋オフセットインデックス数５＝１１
４２５÷１１＝３８余り７、余り７＋オフセットインデックス数５＝１２
４２６÷１１＝３８余り８、余り８＋オフセットインデックス数５＝１３
４２７÷１１＝３８余り９、余り９＋オフセットインデックス数５＝１４
４２８÷１１＝３８余り１０、余り１０＋オフセットインデックス数５＝１５
４２９÷１１＝３９余り０、余り０＋オフセットインデックス数５＝５
４３０÷１１＝３９余り１、余り１＋オフセットインデックス数５＝６
【０１０７】
図１４では、上位ビット９ビット値＝１１０１０１０１０（１０進値＝４２６）をインデックス数１１で割った余りが８であり、その余りにオフセットインデックス数５を加算することにより、新たなインデックスの値１３が得られることが示されている。
【０１０８】
以上の具体例により、図３のＰ３の１１個のブロックを順にアクセスすることができることがわかる。すなわち、新たなインデックスの値は、０〜１５までの全インデックス範囲のうち、５から１５までの範囲（Ｐ３）に収まる。すなわち、ＰＰＩＤ値Ｐ３に対応する命令が実行されるときに、アドレス１０７のインデックスは、図３のインデックス方向の全域で指定される可能性がある。これに対して、モジュロ演算器１３０１は、インデックスの値が５から１５までの１１個のインデックス範囲のみが指定されるように、マッピングを行うことができる。
【０１０９】
一方、図１５に示されるように、要求元ＰＰＩＤ値として「１」（または「２」）が入力したとする。この結果、選択回路１３０３が、ハッシュ有効化レジスタ１３０２上の要求元ＰＰＩＤ値と一致するＰＰＩＤ値＝Ｐ１（またはＰ２）に対応するエントリから、有効ビット＝０、インデックス数＝０、およびオフセットインデックス数＝０を読み出す。そして、選択回路１３０３は、それらの数値データをモジュロ演算器１３０１に与える。モジュロ演算器１３０１は、上述のようにもし有効ビットが１にセットされていなければ、以下のように動作する。すなわち、アドレス１０７中の４ビットのインデックスをそのまま、キャッシュタグ部７０１（図７）およびキャッシュデータ部（後述する図１６の１６０４を参照）に、新たなインデックスとして出力する。
【０１１０】
ここで例えば、要求元ＰＰＩＤ値＝１で、アドレス１０７として、前述と同様の「０ｘＤ１５２」から「０ｘＤ７５２」までのアドレスが入力したとする。
図１５では、アドレス１０７として「０ｘＤ５５２」が入力された場合が示されている。
【０１１１】
これらの場合、アドレス１０７中のインデックスおよび各々に対応する１０進値は、それぞれ以下のようになる。
００１０＝２
００１１＝３
０１００＝４
０１０１＝５
０１１０＝６
０１１１＝７
１０００＝８
１００１＝９
１０１０＝１０
１０１１＝１１
１１００＝１２
１１０１＝１３
１１１０＝１４
モジュロ演算器１３０１は、上記各４ビットのインデックスをそのまま、新たなインデックスとして出力する。
【０１１２】
図１５では、アドレス１０７中のインデックス「１０１０」（１０進数で１０）がそのまま、新たなインデックスとして出力されることが示されている。
以上の具体例により、図３のＰＰＩＤ値＝Ｐ１またはＰ２については、０〜１５までの全インデックス範囲をインデックスとして指定できることがわかる。
【０１１３】
このようにして、或るプロセスｐについて、図２のテーブルによって指定されるブロック数が１ウェイ分に満たない場合には、次のような制御が実行される。すなわち、ＭＡＸ ＷＡＹ数増加開始位置Ｏ［Ｐ］から、プロセスｐについて割り当て可能な１ウェイ分に満たないブロック数Ｒ［ｐ］に対応するインデックス範囲でのみインデックス指定がされるように、新たなインデックスがマッピングされる。
【０１１４】
ここで、図９または図１０のステップＳ９０７によってハッシュ有効化レジスタ１３０２の内容を更新するときには、次のようなアドレス指定を行うことができる。すなわち、図１２のＭＡＸ ＷＡＹ数１０５の更新処理の場合と同様に、メインメモリ等へのメモリアクセス時には使用されないような特定のアドレス空間にマップされた領域を介して、ハッシュ有効化レジスタ１３０２に対する読み書きを実行できる。
【０１１５】
以上説明した図１３のアドレスハッシュユニット５０１の構成により、指定された命令アドレス１０７のインデックスをハッシュして得られるインデックスが、禁止された領域のインデックスを生成しないように制御することが可能となる。
【０１１６】
図１６は、図６のプロセスＩＤマップユニット６０１のハードウェア構成例を示す図である。
プロセスＩＤマップユニット６０１は、ＯＳが管理するＰＩＤと、キャッシュメモリ１０１のハードウェアが取扱い可能な物理プロセスＩＤであるＰＰＩＤの変換を行う。
【０１１７】
プロセスＩＤマップユニット６０１は、変換のマップを格納するとともに検索が可能な連想メモリ１６０１で構成されている。なお、プロセスＩＤマップユニット６０１は、レジスタで構成されてもよい。要求元ＰＩＤの値をキーとして連想メモリ１６０１の検索を行い、マッチしたＰＰＩＤの値を出力する。
【０１１８】
連想メモリ１６０１に格納する値は、図１２のＭＡＸ ＷＡＹ数１０５の更新処理の場合と同様に、メインメモリ等へのメモリアクセス時には使用されないような特定のアドレス空間にマップされた領域を介して読み書きできる。
【０１１９】
図１７は、ＰＰＩＤ書込み機構を示す図である。
図１６に示されるプロセスＩＤマップユニット６０１から出力される要求元ＰＰＩＤの値で、キャッシュタグ部７０１（図７）内のキャッシュブロック１０２の更新が行われる。このときキャッシュブロック１０２をアクセスするインデックスは、図１３に示されるアドレスハッシュユニット５０１から出力された値を用いる。
【０１２０】
図１８は、本実施形態のキャッシュメモリシステムを備える演算処理装置としてのプロセッサの構成例を示す図である。
キャッシュシステム１８０１は、図７に示したキャッシュタグ部７０１（ＭＡＸ ＷＡＹ数保持部１２０１を含む）、図５および図１３に示したアドレスハッシュユニット５０１、図６および図１６に示したプロセスＩＤマップユニット６０１を備える。また、キャッシュシステム１８０１は、キャッシュデータを保持するキャッシュデータ部１８０４およびキャッシュタグ部７０１およびキャッシュデータ部１８０４へのキャッシュアクセスを制御するキャッシュメモリ制御部１８０５を備える。
【０１２１】
キャッシュメモリ制御部１８０５は、＃１〜＃４のＣＰＵコア１８０２内の命令制御部１８０６から発行されるメモリアクセス命令をデコードして、メインメモリ１８０３に対するアクセスかキャッシュデータ部１８０４へのアクセスであるかを判断する。
【０１２２】
キャッシュメモリ制御部１８０５は、デコードの結果、メモリアクセス命令がキャッシュデータ部１８０４へのアクセスである場合には、キャッシュタグ部７０１およびキャッシュデータ部１８０４に対して、メモリアクセス命令に含まれるアドレス１０７（図１、図７等参照）を発行する。このアドレス１０７は、アドレスハッシュユニット５０１で処理された後に、キャッシュタグ部７０１およびキャッシュデータ部１８０４に出力する。
【０１２３】
また、キャッシュメモリ制御部１８０５は、メモリアクセス命令がキャッシュデータ部１８０４へのアクセスである場合には、メモリアクセス命令が実行されるＰＩＤをプロセスＩＤマップユニット６０１に出力する。プロセスＩＤマップユニット６０１は、ＰＩＤをＰＰＩＤに変換し、キャッシュタグ部７０１に要求元ＰＰＩＤとして出力する。
【０１２４】
キャッシュメモリ制御部１８０５は、図１１および図１２に示したハードウェア機構を含み、前述した置換ウェイの制御やＭＡＸ ＷＡＹ数１０５の更新制御等を実行する。
キャッシュシステム１８０１においてキャッシュミスが発生した場合には、メインメモリ１８０３からデータが読み出されるとともに、キャッシュメモリ制御部１８０５内の図１１のハードウェア構成によって生成される置換ウェイマスクに対応する置換ウェイのキャッシュブロック１０２に、そのデータが記憶される。これにより、次回アクセス時にキャッシュヒットとなり、高速なアクセスが実行される。
【０１２５】
また、キャッシュメモリ制御部１８０５は、命令制御部１８０６から、ＭＡＸ ＷＡＹ数１０５の更新を指示するＳＴＯＲＥ命令が発行されている場合には（図１２参照）、次のような動作を実行する。すなわち、キャッシュメモリ制御部１８０５は、ＭＡＸ ＷＡＹ数１０５を保持するキャッシュタグ部７０１内のＲＡＭ１２０３（図１２）内の、上記ＳＴＯＲＥ命令で指定される物理アドレスに対して、ＳＴＯＲＥ命令で指定される４バイトのデータを書き込む。これにより、該当するインデックス値上の各ＰＰＩＤ値（Ｐ１，Ｐ２，Ｐ３，Ｐ４）毎のＭＡＸ ＷＡＹ数１０５が更新される。ＳＴＯＲＥ命令によるＭＡＸ ＷＡＹ数１０５の更新指示は、命令制御部１８０６からの指示により、キャッシュアクセスを発生させるメモリアクセス命令によるメモリアクセスがなされた場合に付随させて行ってもよいし、全インデックス値について一括して実行されてもよい。
【０１２６】
図１９は、本実施形態において、同時にスケジューリングされる各プロセスが要求するウェイ数の合計が、実装されているキャッシュメモリのウェイ数を超えている場合の動作例を示す説明図である。
【０１２７】
この動作例において、まず、ＰＰＩＤ値Ｐ１、ＰＰＩＤ値Ｐ２、ＰＰＩＤ値Ｐ３の各ＰＰＩＤ値に対するＭＡＸウェイ数の設定値を例えば、５、５、３とする。
まず、ＰＰＩＤ値Ｐ３のプロセスに含まれるＬＯＡＤ命令実行によりキャッシュミスが発生する（ステップＳ１７０１）。Ｐ３のブロック数＝１は、Ｐ３のＭＡＸ ＷＡＹ数＝３よりも小さいため、他のＰＰＩＤ値のウェイ、図１９の例ではＰＰＩＤ値Ｐ２のウェイを置換する。
【０１２８】
さらに、ＰＰＩＤ値Ｐ３のプロセスに含まれるＬＯＡＤ命令実行によりキャッシュミスが発生する（ステップＳ１７０２）。Ｐ３のブロック数＝２は、Ｐ３のＭＡＸ ＷＡＹ数＝３よりも小さいため、さらに他のＰＰＩＤ値のウェイ、図１９の例ではＰＰＩＤ値Ｐ１のウェイを置換する。
【０１２９】
このようにして、ＰＰＩＤ値Ｐ３に割り当てられているブロック数は、最初１ブロックしかないが、ＰＰＩＤ値Ｐ３のプロセスに含まれるメモリアクセス要求があるとＭＡＸ ＷＡＹ数＝３まで他のＰＰＩＤのブロックを置換することにより増加する。
【０１３０】
さらに、ＰＰＩＤ値Ｐ３のプロセスに含まれるＬＯＡＤ命令実行によりキャッシュミスが発生したものとする（ステップＳ１７０３）。Ｐ３のブロック数＝３は、Ｐ３のＭＡＸ ＷＡＹ数＝３以下であるため、自ＰＰＩＤであるＰＰＩＤ値Ｐ３に対応するウェイを置換する。
【０１３１】
このように、ＭＡＸ ＷＡＹ数以上のＰＰＩＤ値Ｐ３の要求があっても、ＰＰＩＤ値Ｐ３に対するキャッシュブロック数はＭＡＸ ＷＡＹ数以上には増えない。
次に、ＰＰＩＤ値Ｐ２のプロセスに含まれるＬＯＡＤ命令実行によりキャッシュミスが発生したものとする（ステップＳ１７０４）。Ｐ２のブロック数＝１は、Ｐ２のＭＡＸ ＷＡＹ数＝５よりも小さいため、ＰＰＩＤ値Ｐ１のウェイを置換する。
【０１３２】
その後、ＰＰＩＤ値Ｐ１のプロセスに含まれるメモリアクセス要求があり、同様にしてＭＡＸ ＷＡＹ数＝５まで増加する（ステップＳ１７０５、Ｓ１７０６・・・）。このように、ＭＡＸ ＷＡＹ数に近づくように各ＰＰＩＤ値に対応するブロック数が変化することで、実装されているウェイ数を超えるＭＡＸ ＷＡＹ数を設定した場合でも問題なくキャッシュ分割を行うことが可能となる。
【０１３３】
図２０は、時間と優先度でキャッシュブロックをスケジュールする動作を示すフローチャートである。
このフローチャートの処理は、一定時間（例えば１０マイクロ秒）毎に実行される。
【０１３４】
まず、キャッシュブロックを割り当てている各プロセス毎に、キャッシュブロック割当て数 [blocks]とプロセス割当て時間 [us]の積Ａを計算する（ステップＳ２００１）。
次に、Ａ＞Ｔとなるプロセスが存在するか否かが判定される（ステップＳ２００２）。ここで、Ｔは、システム依存の定数（しきい値）とする。
【０１３５】
Ａ＞Ｔとなるプロセスが存在しステップＳ２００２の判定がＹＥＳならば、プロセス実行優先度が下げられて（ステップＳ２００３）、今回の処理を終了する。
Ａ＞Ｔとなるプロセスが存在せずステップＳ２００２の判定がＮＯならば、何もせずに今回の処理を終了する。
【０１３６】
上述した実施形態において、ＭＡＸ ＷＡＹ数は、キャッシュタグ部内に設けるようにしたが、ＯＳの管理下で制御されるような構成が採用されてもよい。
【符号の説明】
【０１３７】
１０１ キャッシュメモリ
１０２ キャッシュブロック
１０３ キャッシュライン
１０４ キャッシュウェイ
１０５ ＭＡＸ ＷＡＹ数
１０６，８０１ コンパレータ
１０７ アドレス
５０１ アドレスハッシュユニット
６０１ プロセスＩＤマップユニット
７０１ キャッシュタグ部
７０２ タグ情報
１１０１ ビット数え上げ器
１１０２ 置換ウェイ候補決定回路
１１０３ 置換ウェイマスク生成回路
１１０４，１１０７，１３０３ 選択回路
１１０５ 比較器
１１０６ インバータ
１１０８ ＰＰＩＤマッチしたビットマスク
１１０９ 置換ウェイ候補を示すビットマスク
１２０１ ＭＡＸ ＷＡＹ数１０５保持部
１２０２ アドレスマップユニット
１２０３ ＲＡＭ
１３０１ モジュロ演算器
１３０２ ハッシュ有効化レジスタ
１６０１ 連想メモリ
１８０１ キャッシュシステム
１８０２ ＣＰＵコア
１８０３ メインメモリ
１８０４ キャッシュデータ部
１８０５ キャッシュメモリ制御部
１８０６ 命令制御部
【技術分野】
【０００１】
本発明は、演算処理装置および演算処理装置の制御方法に関する。
【背景技術】
【０００２】
近年のプロセッサの動作周波数の向上により、相対的にプロセッサ内部からメインメモリに対するメモリアクセスの遅延時間が長くなり、メモリアクセスの遅延時間がシステム全体の性能を左右するに至っている。多くのプロセッサは、メモリアクセス遅延時間を隠蔽する目的で、キャッシュメモリと呼ぶ小容量の高速メモリを搭載している。
【０００３】
キャッシュメモリは、データを複数のキャッシュライン（もしくは単に「ライン」）またはキャッシュブロック（もしくは単に「ブロック」））と呼ばれる単位で管理する。プロセッサからデータのアクセス要求があった時に、そのデータがキャッシュ内のいずれかのラインに存在しているか否かを高速に検索する必要がある。
【０００４】
このためキャッシュメモリを分割して検索等の処理を行なうことが行われる。
プロセッサが実行するオペレーティングシステム(Operating System；ＯＳ)によって共有キャッシュ領域を分割管理する手法として従来、Modified LRU Replacement方式と呼ばれる第１の従来技術が知られている。この第１の従来技術では、システム上で動作する全プロセスについて、プロセスが使用しているキャッシュブロック数がカウントされる。
【０００５】
また、キャッシュブロック内のタグ（キャッシュタグ）にプロセッサが実行するプロセスを識別するプロセスＩＤを記憶し、プロセスＩＤによってキャッシュフラッシュを制御する第２の従来技術が知られている。
【０００６】
さらに、キャッシュタグ内にプロセスＩＤを記録して、キャッシュアクセス時に要求元プロセスＩＤとキャッシュタグ内のプロセスＩＤとを比較することで、キャッシュフラッシュを制御する第３の従来技術が知られている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平３−２３５１４３号公報
【特許文献２】特許２７００１４８号公報
【非特許文献】
【０００８】
【非特許文献１】Suh, G.E. and Devadas, S. and Rudolph, L.,"A new memory monitoring scheme for memory-aware scheduling and partitioning",High-Performance Computer Architecture, 2002. Proceedings. Eighth International Symposium on, pp.117--128.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、第１の従来技術では、使用中のキャッシュブロック数を、全プロセスについて正しく把握するような機構が必要となって、ハードウェア規模が増大してしまう。また、マルチプロセス環境においてはその効率的な動作の観点から問題があった。
【００１０】
また、第２の従来技術では、各キャッシュタグにプロセスＩＤを固定的に割り当てるのみである。このため、キャッシュメモリ中でのプロセスＩＤ間の全体的なサイズ割当てを変更するためには、全キャッシュタグの書換えが必要となってしまうという問題点を有していた。
【００１１】
さらに、第３の従来技術も、キャッシュメモリ中でのプロセスＩＤ間の全体的なサイズ割当てを変更するような機構は備えていないという問題点を有していた。
このため、キャッシュメモリのより効率的な動作が望まれていた。
【００１２】
本発明の１つの側面では、プロセスＩＤに対応してキャッシュメモリ領域をブロック単位で任意に分割可能として、プロセッサの実効性能を向上することを可能とすることにある。
【課題を解決するための手段】
【００１３】
態様の一例では、複数の命令を含むプロセスを実行するとともに、インデックス情報とタグ情報を含むメモリアクセス要求を発行する命令制御部と、タグと、メモリアクセス要求に対応するデータと、命令制御部が実行するプロセスを識別するプロセス識別子を保持するブロックを、複数のインデックス各々に対応して有するキャッシュウェイを複数備えたキャッシュメモリ部と、受信したメモリアクセス要求に含まれるインデックス情報をデコードし、デコードしたインデックス情報に対応するブロックを選択するインデックスデコード部と、受信したメモリアクセス要求に含まれるタグ情報とインデックスデコード部が選択したブロックに含まれるタグを比較し、タグ情報とタグが一致する場合にはインデックスデコード部が選択したブロックに含まれるデータを出力する比較部と、プロセス識別子毎に設定された最大キャッシュウェイ数情報に基づき、キャッシュメモリ部のインデックス毎に、プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数を決定する制御部とを有するように構成する。
【発明の効果】
【００１４】
キャッシュメモリ領域をキャッシュブロック単位で任意に分割し、各プロセスに適切なキャッシュブロック数を割り当てることが可能となる。これにより、キャッシュメモリをリソースとして管理し、プロセススケジューリングを最適化することが可能となり、プロセッサの実効性能を向上させることが可能となる。
【図面の簡単な説明】
【００１５】
【図１】キャッシュメモリの実施形態のブロック図である。
【図２】ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数のテーブルのデータ構成例を示す図である。
【図３】キャッシュメモリの分割例を示す図である。
【図４】キャッシュミス発生時のリプレース動作を示す説明図である。
【図５】ハッシュユニットを示す図である。
【図６】プロセスＩＤマップユニットを示す図である。
【図７】キャッシュタグ部のハードウェア構成例を示す図（その１）である。
【図８】キャッシュタグ部のハードウェア構成例を示す図（その２）である。
【図９】ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数に基づいてＭＡＸ ＷＡＹ数を決定する処理を示すフローチャートである。
【図１０】ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数に基づいてＭＡＸ ＷＡＹ数を決定する処理を示すプログラム擬似コードである。
【図１１】置換ウェイ制御回路のハードウェア構成例を示す図である。
【図１２】ＭＡＸ ＷＡＹ数更新機構を示す図である。
【図１３】ハッシュユニットのハードウェア構成例を示す図である。
【図１４】ハッシュユニットの動作説明図（その１）である。
【図１５】ハッシュユニットの動作説明図（その２）である。
【図１６】プロセスＩＤマップユニットのハードウェア構成例を示す図である。
【図１７】ＰＰＩＤ書込み機構を示す図である。
【図１８】本実施形態のキャッシュメモリシステムを備えるプロセッサシステムの構成例を示す図である。
【図１９】同時にスケジューリングされる各プロセスが要求するウェイ数の合計が、実装されているキャッシュメモリのウェイ数を超えている場合の動作例を示す説明図である。
【図２０】時間と優先度でキャッシュブロックをスケジュールする動作を示すフローチャートである。
【発明を実施するための形態】
【００１６】
プロセッサの実効性能の向上のためには、キャッシュメモリの高速動作が必要である。
データがキャッシュメモリ内のいずれかのラインに存在しているか否かを高速検索するため、各キャッシュセット（以下、単にセットと略記）を構成するキャッシュブロックは、有効か否かを示す有効フラグ、タグ、及びデータから構成されている。キャッシュブロックのサイズは例えば、有効フラグが１ビット、タグが１５ビット、データが１２８バイトである。ここで、キャッシュセットとは、分割されたキャッシュメモリの領域をいい、各キャッシュセットは複数のキャッシュブロックを含む。
【００１７】
一方、プログラムによって指定されるメモリアクセスのための例えば３２ビットのアドレスは例えば、下位から７ビットがキャッシュライン内オフセット、１０ビットがインデックス、上位１５ビットがタグとして使用される。
【００１８】
アドレスに対するデータ読出しが要求されると、アドレス内のインデックスアドレスが示すセットが選択される。さらに、選択されたセット内の各キャッシュブロックに対応する形で記憶されているタグがアドレス内のタグと一致するか否かが判定され、タグが一致する場合にはキャッシュヒットが検出され、タグが一致しない場合にはキャッシュミスが検出される。
【００１９】
このとき、セット内に複数ウェイのキャッシュブロック（データとタグの組）を持てば、同じインデックス値を有するエントリでも上位アドレス値（タグ値）が異なる複数のデータを格納することが可能となる。このようなキャッシュメモリのデータ格納方式はセット・アソシアティブ(Set Associative)方式と呼ばれる。メモリのアドレス空間より小さい空間となっているキャッシュのアドレス空間をセット（集合）に分割し、例えば要求アドレスをそのセットの数で割った余りの数をインデックスとすればセットの数はインデックス数に対応する。各セット（インデックス）は複数のブロックを含むが、インデックスの指定によって同時に出力されるブロック数がウェイ数である。１ラインがｎ個のタグにより構成されるｎ個のブロックを同時に出力する場合、ｎウエイセット・アソシアティブ(n-way Set Associative)方式と呼ぶ。
【００２０】
書き込まれるデータのサイズがインデックスで指定可能なアドレスの範囲よりも大きい場合に、複数のデータにおいてアドレスの一部分であるインデックスの値が一致し、それらのデータがキャッシュラインを奪い合う競合が発生する可能性がある。このような場合であっても、セット・アソシアティブ方式のキャッシュメモリにおいては、インデックスが同じラインが指定されたとしても、キャッシュラインの競合を発生することなく複数のウェイからキャッシュブロックを選択できる。例えば４ウェイ構成のキャッシュメモリでは、同じインデックスを持つ最大で４つまでのデータに対応することができる。
【００２１】
指定されたラインのどのウェイのキャッシュブロックにおいてもタグの一致が検出されなかった、またはタグの一致が検出されたキャッシュブロックの有効フラグが無効を示していたら、キャッシュミスとなり、メインメモリ（主記憶装置）からアクセス対象のデータが読み出される。キャッシュミスの発生時には、指定されたセット上から未使用のウェイが選択されて、そのウェイのキャッシュブロックにメインメモリから読み出されたデータが新たに保持される。これにより、保持されたデータが次回アクセス時にキャッシュヒットし、メインメモリへのアクセスが不要となるため、高速なアクセスが実行される。キャッシュミス時にどのウェイも使用中の場合には、例えばＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）と呼ばれるアルゴリズムによって、使用中のウェイから１つが選択されて、そのウェイのキャッシュブロックのデータが置換される。ＬＲＵアルゴリズムでは、使われてから最も長い時間が経っているキャッシュブロックのデータがメインメモリに追い出されるとともに、メインメモリから読み出されたデータに置換される。
セット・アソシアティブ方式のキャッシュメモリは以上のような構成を有す。
【００２２】
以下、本発明を実施するための形態について図面を参照しながら詳細に説明する。
図１は、キャッシュメモリの実施形態のブロック図である。
本実施形態によるキャッシュメモリ１０１は、例えば４ウェイまたは８ウェイのセット・アソシアティブ方式のキャッシュメモリである。
キャッシュメモリ１０１は、データを＃１から＃ｎの複数行からなるセット１０３、および各セット１０３に属するキャッシュブロック１０２の単位で管理される。例えば、ｎ＝１０２４である。
【００２３】
図１の実施形態においては、各セット１０３を構成するキャッシュブロック１０２は、有効フラグ（例えば１ビット）、タグ（例えば１５ビット）、データ（例えば１２８バイト）に加えて、物理プロセスＩＤ（以下、「ＰＰＩＤ」と称する）を有する。ＰＰＩＤは、オペレーティングシステムが管理するプロセスＩＤ（以下、「ＰＩＤ」と称する）を、後述するプロセスＩＤマップユニットによって変換して得られるプロセス識別情報である。ＰＰＩＤは、例えば２ビットのデータであり、例えば０〜３の４つのＰＰＩＤ値を識別することができる。ＰＰＩＤを記憶することで、各キャッシュブロック１０２がどのプロセスに割り当てられているかを区別することができる。
【００２４】
キャッシュメモリ１０１のデータサイズ定義：は、「キャッシュブロック１０２のデータサイズ×キャッシュインデックス数×キャッシュウェイ数で計算され、例えば、１０２４バイトを１キロバイトとして、４ウェイのキャッシュメモリ１０１の場合、
（１２８バイト×１０２４インデックス×４ウェイ）÷１０２４＝５１２キロバイトである。
【００２５】
一方、プログラムによって指定されるメモリアクセスのためのアドレス１０７は、例えば３２ビットで指定され、下位から７ビットがキャッシュライン内オフセット、１０ビットがインデックス、上位１５ビットがタグとして使用される。
【００２６】
また、本実施形態では、プログラムを実行する場合にオペレーティングシステムから指定されるＰＩＤを、プロセスＩＤマップユニットによって変換して得られるＰＰＩＤが、キャッシュメモリ１０１に与えられる。
【００２７】
以上の構成により、アドレス１０７に対するデータの読み出し又は書き込みのアクセスが指定されると、アドレス１０７内の１０ビットのインデックスにより、セット１０３内の＃１〜＃ｎのキャッシュブロックのうちの１つが指定される。
【００２８】
その結果、＃１〜＃４の各キャッシュウェイ１０４から、セット１０３上の各キャッシュブロック１０２（＃ｉ）のタグ値が読み出され、それぞれ＃１〜＃４のコンパレータ１０６に入力する。
【００２９】
＃１〜＃４のコンパレータ１０６は、読み出された各キャッシュブロック１０２（＃ｉ）内のタグ値と、指定されたアドレス１０７内のタグ値との一致／不一致を検出する。この結果、＃１〜＃４のうちタグ値の一致が検出されたコンパレータ１０６において読み出されているキャッシュブロック１０２（＃ｉ）がキャッシュヒットとなり、そのキャッシュブロック１０２（＃ｉ）に対してデータが読み書きされる。
【００３０】
どのコンパレータ１０６でもタグ値の一致が検出されなかった、又はタグ値の一致が検出されたキャッシュブロック１０２（＃ｉ）の有効フラグが無効を示していたら、キャッシュミスとなり、メインメモリ上のアドレスがアクセスされる。キャッシュミスの発生時には、指定されたライン上から選択された未使用のウェイのキャッシュブロックにデータが新たに保持される。これにより、次回アクセス時にキャッシュヒットとなり、メインメモリへのアクセスが不要となるため、高速なアクセスが実行される。
【００３１】
キャッシュミス時にどのウェイも使用中の場合には、本実施形態では、以下に示されるような追い出し制御が実施される。
まず、本実施形態では、各セット１０３のキャッシュブロック１０２毎にＰＰＩＤが記憶されるとともに、＃１から＃ｎのインデックス値毎に、各ＰＰＩＤ値（例えば１〜４）に対するＭＡＸ ＷＡＹ数（最大ウェイ数）１０５が記憶される。或るインデックス値における或るＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５は、そのインデックス値において記憶可能なそのＰＰＩＤ値を有するキャッシュブロック１０２の最大数を示す。本実施形態では、各インデックス値毎に、各ＰＰＩＤ値のＭＡＸ ＷＡＹ数１０５が守られるように、追い出し制御が実施される。
【００３２】
各ＰＰＩＤ値毎のＭＡＸ ＷＡＹ数１０５の割合は、オペレーティングシステム（ＯＳ）が定めたＰＰＩＤ値毎のキャッシュブロック数に基づいて決定される。この場合、キャッシュメモリ１０１中でのＰＰＩＤ値間のサイズ割当て、すなわち各ＰＰＩＤが使用できるキャッシュメモリの領域のサイズを変更する場合には、各インデックス値へのアクセス発生時に、そのインデックス値の各ＰＰＩＤ値毎のＭＡＸ ＷＡＹ数１０５を順次変更する。キャッシュメモリ１０１を単純にＰＰＩＤ値によって分割すると、分割量を変更する場合にキャッシュメモリ１０１内の全キャッシュブロック１０２のＰＰＩＤ情報を書き換えなくてはいけないので更新オーバヘッドが大きくなる。これに対して、本実施形態では、一時期に全キャッシュブロック１０２の書換えを行わなくても、インデックス値単位で動的にＰＰＩＤ間のサイズ割当ての変更が可能となるため、情報の更新を最小限に抑えることにより、低オーバヘッドで分割量の変更を行うことが可能となる。
【００３３】
図２は、ＯＳが保有する、ＯＳが各ＰＰＩＤ値に与える最大キャッシュブロック数のテーブルのデータ構成例を示す図である。ＰＰＩＤ値がＰ1，Ｐ２，Ｐ３のとき、最大キャッシュブロック数は例えば、それぞれ６４,２１,１１である。さらに図３は、図２に示されるテーブル内容に従って本実施形態において実施されるキャッシュメモリ１０１の分割例を示す図である。この分割処理においては、キャッシュウェイ１０４の数が８ウェイである場合の例について示されている。キャッシュメモリのインデックス数は１０ビットもしくは１１ビットで表わされる数存在するが、ここでは説明を簡単にするため、インデックス方向には例として１６個のインデックスがあるものとして説明を行なう。インデックス値毎に、ＰＰＩＤ値（図３ではＰ１、Ｐ２、Ｐ３）毎のＭＡＸ ＷＡＹ数１０５が保持される。そして、キャッシュメモリ１０１全体で、各ＰＰＩＤ値に与えられるＭＡＸ ＷＡＹ数１０５が、図２のテーブルで設定されたＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数に等しくなるように、各インデックス値毎のＭＡＸ ＷＡＹ数１０５が設定される。
【００３４】
指定されたインデックス値において、或るＰＰＩＤ値を有するキャッシュブロック１０２についてキャッシュミスが発生したときには、次のような動作が実行される。すなわち、そのセット１０３上で、そのＰＰＩＤ値に関して既に配分済みのキャッシュウェイ数の合計と、そのＰＰＩＤ値に対応して記憶されているＭＡＸ ＷＡＹ数１０５とが比較される。配分済みのキャッシュウェイ数の合計がＭＡＸ ＷＡＹ数１０５に満たない場合は、以下の動作が実行される。すなわち、そのインデックス値上で、他のＰＰＩＤ値に対して配分済みのキャッシュブロック１０２の中で、配分済みのキャッシュウェイ数の合計が当該ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５を越えているキャッシュブロックの中から置換ブロックが選択される。
【００３５】
図４は、キャッシュミス発生時のキャッシュブロックのリプレース動作を示す説明図である。キャッシュミスが発生したとき、図４に示されるように、例として、ＰＰＩＤ値Ｐ１に４ブロック、Ｐ２に３ブロック、Ｐ３に１ブロックが割り当てられていたとする。ここで、Ｐ１についてキャッシュミスが発生したときには、Ｐ１はそのインデックス値上でのＭＡＸ ＷＡＹ数１０５を超えておらず、一方、Ｐ２がそのインデックス値上でのＭＡＸ ＷＡＹ数１０５を既に越えている。このため、ＰＰＩＤ値としてＰ２を有するキャッシュブロック１０２の中からリプレース候補が選択され、図４中の矢印のブロックのデータがメインメモリから読み出されたデータに置換され、ＰＰＩＤ値Ｐ１の要求するデータがロードされる。
【００３６】
このように、本実施形態では、キャッシュミスのアクセスが発生したタイミングで、各ＰＰＩＤに対するキャッシュサイズの割当てが動的に変更される。
キャッシュメモリ１０１における各ＰＰＩＤに対するキャッシュサイズの割当てを変更する場合は、ＭＡＸ ＷＡＹ数１０５のマップを変更するだけでよい。ＭＡＸ ＷＡＹ数１０５の指示は、キャッシュアクセス命令に付随させて行うことができる。従来技術では、キャッシュメモリ１０１内の全キャッシュブロック１０２のプロセスＩＤを書き換えることが必要であった。これに対して、本実施形態では、キャッシュアクセス命令に付随して随時各ＰＰＩＤに対するキャッシュサイズの割当を変化させることができる。なお、全てのインデックス値について、一括して書き換えてもよい。
【００３７】
また、同時にスケジューリングされる各プロセスが要求するウェイ数の合計が、実装されているキャッシュメモリ１０１のウェイ数を超えていても、ウェイの取り合いになるだけでシステム停止などの問題は発生しない。
【００３８】
図２のテーブル例の場合、ＰＰＩＤ値３に与えるキャッシュブロック数は１１である。このため、ＰＰＩＤ値３は、インデックス値の数（図３では１６インデックス）の全てに対して、キャッシュブロックを割り当てることができない。このため、図３に示されるキャッシュメモリ１０１の分割例において、次のようなインデックス方向の割り当て変更が必要となる。すなわち例えば、インデックス方向の先頭５インデックスの領域ではＰＰＩＤ値Ｐ３に対するＭＡＸ ＷＡＹ数１０５は０とされ、それ以後１１インデックスの領域でのみＰＰＩＤ値Ｐ３に対するＭＡＸ ＷＡＹ数１０５が１とされる。このため、ＰＰＩＤ値３に対応するキャッシュアクセスが発生した場合、命令アドレス中のインデックスによって、先頭５インデックスの領域が指定されないようにし、常に後側１１インデックスの領域が指定されるようにする必要がある。
【００３９】
この機能として、本実施形態では、図５に示されるハッシュ機構としてのアドレスハッシュユニット５０１が実装される。このハッシュ機構により、指定された命令アドレスをハッシュして得られるインデックスが、禁止された領域のインデックスを生成しないようにされる。
【００４０】
また、ＯＳが管理するプロセスＩＤは、例えば１６ビット以上の値を持つ。従って、１６ビット以上の値で示されるプロセスＩＤをキャッシュメモリ１０１中の各キャッシュブロック１０２に保持すると、ハードウェア追加量が大きくなる。そこで、本実施形態では、図６に示されるように、プロセスＩＤマップユニット６０１が実装される。このプロセスＩＤマップユニット６０１は、キャッシュアクセス命令を実行しているプロセスのプロセスＩＤを、キャッシュメモリ１０１のハードウェアが取扱い可能な物理プロセスＩＤ ＰＰＩＤにマップする。ＰＰＩＤは、例えば分割されたセット数を指定する２ビットの値を持てばよいため、例えば１６ビット以上の値で示されるプロセスＩＤを保持する場合よりも、キャッシュメモリ１０１のハードウェア量の増大を防ぐことができる。
【００４１】
以上のハードウェア機構により、ＯＳは、プロセッサをプロセス間の共有資源として時分割でスケジューリングして使用するのと同様に、キャッシュメモリ１０１をプロセス間の共有資源としてサイズと時間で自由にスケジューリング可能となる。
【００４２】
例えば、図２のテーブル例のように各ＰＰＩＤ値にキャッシュブロック数を割り当てた場合には、下記のようにキャッシュブロック数と当該キャッシュブロック数の使用期間を乗算した値が大きくなれば、優先度を下げる、もしくはキャッシュ割当てブロック数を減らすといったスケジューリングを行うことができる。
P1： 64 × 1000 マイクロ秒 = 64,000 → 例 : 優先度を下げる
P2： 21 × 500 マイクロ秒 = 10,500
P4： 11 × 2000 マイクロ秒 = 22,000
【００４３】
以上のように、本実施形態では、キャッシュメモリ領域をキャッシュブロック単位で任意に分割することができる。従って、共有キャッシュメモリをプロセッサが有する演算器等の演算リソースと同様にリソースとして管理し、プロセススケジューリングを最適化することが可能となり、プロセッサの実効性能を向上させることが可能となる。
【００４４】
図７および図８は、図１に示されるキャッシュメモリ１０１のブロック構成に対応するハードウェア構成例を示す図である。図７および図８において、図１の場合と同じ機能部分には同じ番号を付してある。
【００４５】
図１に示されるキャッシュブロック１０２は、例えば、データ部（キャッシュデータ部）とタグ部（キャッシュタグ部）が別々のＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）によって実装される。図７および図８の実装例では、キャッシュタグ部７０１において、各セット１０３を構成するキャッシュブロック１０２のタグ情報７０２としては、有効フラグ（１ビット）、タグ（１５ビット）、ＰＰＩＤ（２ビット）が記憶される。また、各インデックス値毎の各ＰＰＩＤ値に対するＭＡＸ ＷＡＹ数１０５も、キャッシュタグ部７０１内に保持される。
【００４６】
なお、タグ情報７０２とＭＡＸ ＷＡＹ数１０５は、さらに別々のＲＡＭに記憶されてもよい。
【００４７】
図７において、メモリアクセス要求によりキャッシュアクセスが発生すると、＃１〜＃４の各キャッシュウェイ１０４から、指定されたインデックス値上の各キャッシュブロック１０２（＃ｉ）のタグ値が読み出され、＃１〜＃４のコンパレータ１０６に入力する。この結果、図１で説明したように、＃１〜＃４のコンパレータ１０６のうち、要求元タグ値との一致を検出したコンパレータ１０６がタグ値を比較したキャッシュブロック１０２（＃ｉ）が、キャッシュヒットしたということになる。そして、キャッシュヒットが検出されたキャッシュブロック１０２（＃ｉ）に対してキャッシュデータ部（後述する図１８の１８０４を参照）上のデータが読み書きされる。
【００４８】
一方、図８において、メモリアクセス要求によりキャッシュアクセスが発生すると、＃１〜＃４の各キャッシュウェイ１０４から、指定されたインデックス値上の各キャッシュブロック１０２（＃ｉ）のＰＰＩＤ値が読み出され、＃１〜＃４のコンパレータ８０１に入力する。
【００４９】
＃１〜＃４のコンパレータ８０１は、読み出された各キャッシュブロック１０２（＃ｉ）内のＰＰＩＤ値と、要求元ＰＰＩＤの値との一致／不一致を検出する。要求元ＰＰＩＤは、キャッシュアクセス命令を実行しているプロセスのプロセスＩＤをプロセスＩＤマップユニット６０１（図６）で変換して得られる値である。この結果、キャッシュブロック１０２（＃ｉ）のＰＰＩＤ値が要求元ＰＰＩＤの値と一致するウェイのコンパレータ８０１の出力は例えば１、一致しないウェイのコンパレータ８０１の出力は例えば０となる。
【００５０】
従って、＃１〜＃４のコンパレータ８０１は、キャッシュブロック１０２（＃ｉ）のＰＰＩＤ値が要求元ＰＰＩＤの値と一致するウェイを示すビットマップを出力することになる。
【００５１】
本実施形態では、このビットマップに含まれる１の数を数え上げることにより、キャッシュミスが発生したインデックス値上で、キャッシュミスを発生させたＰＰＩＤ値に関して既に配分済みのキャッシュウェイ数の合計を算出することができる。そして、前述したように、そのインデックス値上で、キャッシュミスを発生させたＰＰＩＤ値に関して既に配分済みのキャッシュウェイ数の合計と、そのＰＰＩＤ値に対応して記憶されているＭＡＸ ＷＡＹ数１０５とが比較される。ＭＡＸ ＷＡＹ数１０５としては、図７または図８に示されるように、各インデックス毎に、図２または図３に示される各ＰＰＩＤ値Ｐ１，Ｐ２，Ｐ３に対応する値が、キャッシュタグ部７０１に記憶されている。図２，図３には示していないが、Ｐ４についても同様である。そして、上記Ｐ１，Ｐ２，Ｐ３，Ｐ４などに対応するＭＡＸ ＷＡＹ数１０５のうち、要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数が、配分済みのキャッシュウェイ数の合計との比較処理の対象とされる。そして、配分済みのキャッシュウェイ数の合計がＭＡＸ ＷＡＹ数１０５に満たない場合は、そのインデックス値上で、他のＰＰＩＤ値に対して配分済みのキャッシュブロック１０２の中で当該ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５を越えているものの中から置換ブロックが選択されることになる。
【００５２】
＃１〜＃４のコンパレータ８０１が出力するビットマップに対して置換ブロックを決定するための置換ウェイ制御回路のハードウェア構成については、図１１で後述する。
【００５３】
図９は、ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数のテーブル（図２）に基づいて、各インデックス値毎に各ＰＰＩＤ値に対するＭＡＸ ＷＡＹ数１０５（図３）を決定する処理を示す動作フローチャートである。この処理は例えば、図７、図８を含むキャッシュシステムを制御するプロセッサ（例えば後述するＣＰＵコア１８０２）が実行するＯＳの処理の一部である。
【００５４】
まず、図２のテーブル構成が参照され、最初のプロセスに割り当てるブロック数を、１ウェイあたりのインデックス方向のブロック数で除算した値をＣとする（ステップＳ９０１）。すなわち、Ｃは、キャッシュメモリ全体で当該プロセスに割り当てられるウェイ数である。
【００５５】
次に、当該プロセスに割り当てるブロック数を１ウェイあたりのブロック数で割った余りの値をＲとする（ステップＳ９０２）。
例えば図２の最初のＰＰＩＤ値Ｐ１のキャッシュブロック数は６４である。また、図３において、１ウェイあたりのインデックス方向のブロック数は１６ブロックである。従って、Ｃ＝６４／１６＝４、その除算の余りは０であるからＲ＝０となる。
【００５６】
次に、すべてのインデックスについてＭＡＸ ＷＡＹ数＝Ｃを設定する（ステップＳ９０３）。上述のＰＰＩＤ値Ｐ１の例では、ＭＡＸ ＷＡＹ数１０５＝４が設定される。
次に、初期値０から始まって前回のＲの値を順次累算することで、Ｒ個分のＭＡＸ ＷＡＹ数の増加処理を行う開始位置（ＭＡＸ ＷＡＹ数増加開始位置）を更新する（ステップＳ９０４）。続いて、ＭＡＸ ＷＡＹ数増加開始位置からＲ個のインデックス分だけ、ＭＡＸ ＷＡＹ数１０５を１ずつ増加する（ステップＳ９０５）。上述のＰＰＩＤ値Ｐ１の例では、Ｒ＝０であるため、ステップＳ９０５の増加処理は実行されず、また、ＭＡＸ ＷＡＹ数増加開始位置は、初期値０のままである。
【００５７】
次に、Ｃ＝０であるか否かを判定する（ステップＳ９０４）。
Ｃ＝０でなくステップＳ９０４の判定がＮＯならば、ステップＳ９０８に移行する。この結果、ＰＰＩＤ値Ｐ１に関するＭＡＸ ＷＡＹ数１０５は、図３に示されるように、すべてのインデックス値に対して４となる。
【００５８】
ステップＳ９０４の判定の後、図２のテーブル構成例に対応するデータ構成を参照して、次のプロセスがあるか否かが判定される（ステップＳ９０８）。
次のプロセスがありステップＳ９０８の判定がＹＥＳならば、ステップＳ９０１からの処理を繰り返す。
【００５９】
図２のテーブル構成例において、ＰＰＩＤ値Ｐ１の次にまだＰＰＩＤ値Ｐ２がある。このため、ステップＳ９０１、Ｓ９０２が再び実行される。図２のＰＰＩＤ値Ｐ２のキャッシュブロック数は２１であるため、Ｃ＝２１／１６＝１、その除算の余りは５であるからＲ＝５となる。
さらに、ステップＳ９０３が実行される。ＰＰＩＤ値Ｐ２の例では、ＭＡＸ ＷＡＹ数１０５＝１が設定される。
【００６０】
次に、ステップＳ９０４およびＳ９０５が実行される。ＰＰＩＤ値Ｐ２の例では、まず、ＭＡＸ ＷＡＹ数増加開始位置は、前記アクセスのＰ１におけるＲ＝０を使って、初期値０＋Ｒ＝０となる。そして、今回のＲ＝５であるため、ＭＡＸ ＷＡＹ数増加開始位置＝０からＲ＝５個分だけＭＡＸ ＷＡＹ数１０５が＋１される。この結果、ＰＰＩＤ値Ｐ２に関するＭＡＸ ＷＡＹ数１０５は、図３に示されるように、最初の５インデックス値に対して２、残りの１１インデックス値に対して１となる。
【００６１】
ステップＳ９０５の処理の後、ステップＳ９０６の判定がＮＯとなって、ステップＳ９０８が判定される。図２のテーブル構成例において、ＰＰＩＤ値Ｐ２の次にまだＰＰＩＤ値Ｐ３がある。このため、ステップＳ９０８の判定がＹＥＳとなり、ステップＳ９０１、Ｓ９０２が再び実行される。図２のＰＰＩＤ値Ｐ３のキャッシュブロック数は１１であるため、Ｃ＝１１／１６＝０、その除算の余りは１１であるからＲ＝１１となる。
【００６２】
さらに、ステップＳ９０３が実行される。ＰＰＩＤ値Ｐ３の例では、ＭＡＸ ＷＡＹ数１０５＝０が設定される。
【００６３】
次に、ステップＳ９０４およびＳ９０５が実行される。ＰＰＩＤ値Ｐ３の例では、まず、ＭＡＸ ＷＡＹ数増加開始位置は、前記アクセスのＰ２におけるＲ＝５が累算されて５となる。そして、今回のＲ＝１１であるため、ＭＡＸ ＷＡＹ数増加開始位置＝５からＲ＝１１個分だけＭＡＸ ＷＡＹ数１０５が＋１される。この結果、ＰＰＩＤ値Ｐ３に関するＭＡＸ ＷＡＹ数１０５は、図３に示されるように、最初の５インデックス値に対して０、残りの１１インデックス値に対して１となる。
【００６４】
次に、Ｃ＝０であるからステップＳ９０６の判定がＹＥＳとなって、ステップＳ９０７が実行される。
ここでは、ＰＰＩＤ値Ｐ３について、図５のアドレスハッシュユニット５０１を動作させるためのハッシュ有効化レジスタ（後述する図１３の１３０２のＰ３の行を参照）をセットする。
【００６５】
ステップＳ９０７の処理の後、図２のテーブル構成例において、ＰＰＩＤ値Ｐ３の次にはもうＰＰＩＤ値がない。このため、ステップＳ９０８の判定がＮＯとなって、図９のフローチャートによるＭＡＸ ＷＡＹ数１０５の決定処理を終了する。なお、ＰＰＩＤ値Ｐ４がある場合には、さらにＰ４についても同様の処理が繰り返される。
【００６６】
以上説明したフローチャートにより、ＯＳが各ＰＰＩＤ値に与えるキャッシュブロック数のテーブル（図２）に基づき、各インデックス値毎に各ＰＰＩＤ値に対するＭＡＸ ＷＡＹ数１０５（図３）を適切に決定可能となる。
【００６７】
図１０は、図９のフローチャートの処理をプログラム処理として実行した場合のプログラム擬似コードである。各プログラムステップの左には、図９の対応する処理のステップ番号を付してある。
【００６８】
まず、各変数NP,NB,C,B,R,Oが以下のように定義される。
NP : Number of Processes プロセス数
NB : Number of Blocks per way １ウェイあたりのブロック数
C[p] : プロセスpに割り当てるウェイ数
B[p] : プロセスpに割り当てるブロック数
R[p] : プロセスpにおいて１ウェイ分に満たないブロック数
O[p] : ＭＡＸ ＷＡＹ数増加開始位置
【００６９】
まず、図２のテーブル構成から参照される各プロセスｐについて、プロセスｐに割り当てるブロック数B[p]を、１ウェイあたりのインデックス方向のブロック数で除算することにより、プロセスpに割り当てるウェイ数C[p]を算出する（ステップＳ９０１）。
【００７０】
次に、プロセスｐに割り当てるブロック数B[p]を、１ウェイあたりのインデックス方向のブロック数で除算した余りとして、プロセスpにおいて１ウェイ分に満たないブロック数R[p]を算出する（ステップＳ９０２）。
【００７１】
次に、ＭＡＸ ＷＡＹ数増加開始位置O[p]=ｓとする（ステップＳ９０４）。また、s=s+R[p]として更新する（ステップＳ９０５）。
次に、プロセスｐについて、C[p]=0であるならば（ステップＳ９０６）、set_reg_hashval(p)関数を呼び出し、図５のアドレスハッシュユニット５０１を動作させるためのハッシュ有効化レジスタ（後述する図１３の１３０２を参照）をセットする（ステップＳ９０７）。
【００７２】
以上の動作が図２のテーブル構成から参照される全プロセスについて実行される。この結果、各プロセスｐ毎に、プロセスpに割り当てるウェイ数C[p]、プロセスpにおいて１ウェイ分に満たないブロック数R[p]、およびＭＡＸ ＷＡＹ数増加開始位置O[p]が算出される。
【００７３】
これらの値を使って、まず、各プロセスｐ毎に、キャッシュタグ部７０１内のすべてのインデックスについて、ＭＡＸ ＷＡＹ数＝C[p]を設定するＳＴＯＲＥ命令（後述する図１２参照）が実行される。
【００７４】
次に、各プロセスｐ毎に、キャッシュタグ部７０１内のＭＡＸ ＷＡＹ数増加開始位置からR[p]個のインデックス分だけ、ＭＡＸ ＷＡＹ数＝C[p]+1を設定するＳＴＯＲＥ命令（後述する図１２参照）が実行される。
【００７５】
以上のプログラム処理により、図９のフローチャートに対応するＭＡＸ ＷＡＹ数１０５の決定処理が実行される。
図１１は、図８の＃１〜＃４のコンパレータ８０１が出力するビットマップに対して置換ブロックを決定するための置換ウェイ制御回路のハードウェア構成例を示す図である。置換ウェイ制御回路は、ビット数え上げ器１１０１と置換ウェイ候補決定回路１１０２と置換ウェイマスク生成回路１１０３とから構成される。
【００７６】
ＰＰＩＤマッチしたビットマスク１１０８は、図８の＃１〜＃４のコンパレータ８０１の出力である。また、ＭＡＸ ＷＡＹ数１０５は、キャッシュタグ部７０１（図８参照）において、現在のキャッシュアクセスのインデクス値に対応して読み出される各ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５である。
【００７７】
まず、ビット数え上げ器１１０１は、ビットマスク１１０８のビットのうち１となっているビットを数え上げる。この結果、現在のキャッシュアクセスを発生させたＰＩＤに対応するＰＰＩＤ（要求元ＰＰＩＤ）に現在割り当てられているキャッシュウェイ数の合計が算出される。
【００７８】
次に、選択回路１１０４が、各ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５のうち、要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数１０５を選択して出力する。
比較器１１０５は、ビット数え上げ器１１０１が出力する要求元ＰＰＩＤに現在割り当てられているキャッシュウェイ数と、選択回路１１０４が出力する要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数１０５とを比較する。
【００７９】
比較器１１０５が比較した結果、要求元ＰＰＩＤに現在割り当てられているキャッシュウェイ数の合計が要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数１０５に満たない場合には、選択回路１１０７は次のように動作する。すなわち、選択回路１１０７は、ビットマスク１１０８の各ビットをインバータ１１０６で反転して得られるビットマスクを選択し、置換ウェイ候補を示すビットマスク１１０９として出力する。これにより、現在のキャッシュアクセスに対応するセット１０３上で、要求元ＰＰＩＤ値以外の他のＰＰＩＤ値に対して配分済みのキャッシュブロック１０が存在するウェイが、置換ウェイ候補とされる。
【００８０】
一方、比較器１１０５が比較した結果、要求元ＰＰＩＤに現在割り当てられているキャッシュウェイ数の合計が要求元ＰＰＩＤに対応するＭＡＸ ＷＡＹ数１０５に達している場合には、選択回路１１０７は次のように動作する。すなわち、選択回路１１０７は、ビットマスク１１０８をそのまま選択し、置換ウェイ候補を示すビットマスク１１０９として出力する。これにより、現在のキャッシュアクセスに対応するセット１０３上で、要求元ＰＰＩＤ値に対して配分済みのキャッシュブロック１０が存在するウェイが、置換ウェイ候補とされる。
【００８１】
置換ウェイマスク生成回路１１０３は、置換ウェイ候補を示すビットマスク１１０９が示す置換ウェイ候補から、置換ウェイを選択し、置換ウェイを示す置換ウェイマスクを生成して出力する。より具体的には、ビットマスク１１０９が要求元ＰＰＩＤ以外のＰＰＩＤを置換ウェイ候補として示しているときには、置換ウェイマスク生成回路１１０３は、次のように動作する。すなわち、置換ウェイマスク生成回路１１０３は、キャッシュアクセスに対応するセット１０３上で、他のＰＰＩＤ値に対し配分済みのキャッシュブロック１０２の中で、配分済みのキャッシュウェイ数の合計が当該ＰＰＩＤ値に対応するＭＡＸ ＷＡＹ数１０５を越えているキャッシュブロックが選択される。そして、選択されたキャッシュブロックのウェイに対応するビット位置のみが１となる、４ビットからなる置換ウェイマスクを生成する。ビットマスク１１０９が要求元ＰＰＩＤを置換ウェイ候補として示しているときには、置換ウェイマスク生成回路１１０３は、例えばＬＲＵアルゴリズムによって、最も長い期間アクセスなされなかったウェイから選択された置換ウェイのみが１となる４ビットからなる置換ウェイマスクを生成する。
【００８２】
キャッシュミスしたメモリアクセス要求に対応するデータはキャッシュデータ部に、また、タグおよびＰＰＩＤはキャッシュタグ部７０１（図７参照）内の、置換ウェイマスクの４ビットのデータのうち値が１となるビット位置に対応するウェイに出力される。また、メモリアクセス要求内のインデックスが、キャッシュデータ部、キャッシュタグ部７０１のセット１０３を指定する。
【００８３】
これにより、キャッシュデータ部およびキャッシュタグ部７０１において、指定されたセット１０３の選択されたウェイのキャッシュブロック１０２に、データ、タグ、およびＰＰＩＤが書き込まれる。
【００８４】
なお、キャッシュデータ部に書き込まれるデータは、メモリアクセス要求が読出し要求の場合には、図示しないメインメモリ上の対応するアドレスから読み出されたデータである。また、メモリアクセス要求が書込み要求の場合には、当該書込み要求に指定されている書込みデータである。
【００８５】
図１２は、各インデックス値のＭＡＸ ＷＡＹ数１０５を更新するためのＭＡＸ ＷＡＹ数更新機構を示す実施例を説明する図である。
ＭＡＸ ＷＡＹ保持部１２０１には、プロセッサの命令制御部（例えば後述する図１８の１８０６）からアドレスを指定してＭＡＸ ＷＡＹ数１０５の更新値を書き込むことができる。
【００８６】
このとき、命令制御部は、ＭＡＸ ＷＡＹ数１０５を更新するためのＳＴＯＲＥ命令が指定する物理アドレスは、例えば、５２ビットの物理アドレス空間を有するとする。
上記のＳＴＯＲＥ命令が指定する物理アドレスは、ＭＡＸ ＷＡＹ数保持部１２０１内のアドレスマップユニット１２０２によって、キャッシュのインデックス数に等しいアドレス空間を有するＲＡＭ１２０３上の該当する記憶領域をアクセス可能なアドレスとして、例えば「０ｘ００Ｃ」に変換される。すなわちアドレスマップユニット１２０２は例えば、指定されたアドレス「０ｘ１０００００００００００Ｃ」から上位のアドレス情報「０ｘ１０００００００００」を削除して、アドレスを「０ｘ００Ｃ」に変換する処理を実行する。そして、この変換されたアドレスによって指定されるＲＡＭ１２０３内の記憶領域、例えば「０ｘ００Ｃ」に、ＳＴＯＲＥ命令によって４バイトのデータ、例えば「０ｘ０４０２０１０１」が書き込まれる。そして例えば、この４バイトのデータのうち、最上位の１バイト「０４」が、図２または図３に示されるＰＰＩＤ＝Ｐ１に対応するＭＡＸ ＷＡＹ数１０５＝４を指定する。また、次の上位１バイト「０２」が、同じくＰＰＩＤ＝Ｐ２に対応するＭＡＸ ＷＡＹ数１０５＝２を指定する。同様に、次の上位１バイト「０１」が、同じくＰＰＩＤ＝Ｐ３に対応するＭＡＸ ＷＡＹ数１０５＝１を指定する。そして、最下位の１バイト「０１」が、図２や図３では図示しないが、ＰＰＩＤ＝Ｐ４に対応するＭＡＸ ＷＡＹ数１０５＝１を指定する。この１つのＳＴＯＲＥ命令によって書き込まれる４バイト１組のデータが、図７または図８に示される１つのインデックス値上のＰ１〜Ｐ４に対応する１組のＭＡＸ ＷＡＹ数１０５となる。
【００８７】
このように、ＲＡＭ１２０３上のデータは、４バイトを１組として管理されるため、ＲＡＭ１２０３を更新するために命令制御部によって指定される物理アドレスは、４バイトおきに指定されることになる。例えば、「０ｘ１００００００００００００」の次は「０ｘ１０００００００００００４」のごとくである。
【００８８】
なお、図８等で前述したように、キャッシュアクセス時には、例えば、メモリアクセスのためのアドレス１０７内のインデックスの値によって、キャッシュタグ部７０１が、キャッシュメモリ１０１に含まれるＲＡＭ１２０３上の該当する記憶領域にアクセスする。
【００８９】
前述したように、キャッシュメモリ１０１のＰＰＩＤ値毎の容量割当てを変更する場合は、ＭＡＸ ＷＡＹ数１０５を保持するキャッシュタグ部７０１内のＲＡＭ１２０３内での各インデックス値毎のＭＡＸ ＷＡＹ数１０５の割当てを変更すればよい。この場合に、上述のＳＴＯＲＥ命令によるＭＡＸ ＷＡＹ数１０５の更新指示は、キャッシュアクセス命令に付随させて行ってもよいし、全インデックス値について一括して実行されてもよい。
【００９０】
以上説明した図１２のＭＡＸ ＷＡＹ数更新処理は、例えば後述する図１８に示されるキャッシュシステム１８０１内のキャッシュメモリ制御部１８０５が、ＣＰＵコア１８０２内の命令制御部１８０６からの指示に従って実行する。
【００９１】
図１３は、図５のアドレスハッシュユニット５０１のハードウェア構成例を示す図である。
ハッシュ有効化レジスタ１３０２は、ＰＰＩＤ値毎に、有効ビット、インデックス数、およびオフセットインデックス数を記憶する。有効ビットとしては、例えば、ハッシュ処理を実行する場合に有効を示す値１を、実行しない場合に無効を示す値０がセットされる。インデックス数としては、１ウェイ分に満たない分のインデックス増加処理を行うブロック数R[p]がセットされる。オフセットインデックス数としては、上記増加処理の実行を開始するインデックス位置＝ＭＡＸ ＷＡＹ数増加開始位置Ｏ［ｐ］がセットされる。
【００９２】
図９及び図１０で前述したように、プロセスｐについて、Ｃ［ｐ］＝０であるならば、set_reg_hashval(p)関数が呼び出されて、ハッシュ有効化レジスタ１３０２へのセットが実行される。
【００９３】
次に、図１３において、選択回路１３０３は、ハッシュ有効化レジスタ１３０２上の要求元ＰＰＩＤ値と一致するＰＰＩＤ値に対応するエントリから、有効ビット、インデックス数、およびオフセットインデックス数を読み出して、モジュロ演算器１３０１に与える。要求元ＰＰＩＤ値は、キャッシュアクセス命令を実行しているプロセスのプロセスＩＤを、プロセスＩＤマップユニット６０１（図６）で変換して得られる値である。
【００９４】
モジュロ演算器１３０１には、選択回路１３０３から要求元ＰＰＩＤに対応する有効ビット、インデックス数、オフセットインデックス数が入力するほか、キャッシュアクセス命令によって指定されるアドレス１０７の上位ビット部分が入力する。
【００９５】
モジュロ演算器１３０１は、有効ビットがセットされているアドレス１０７の上位ビット部分をインデックス数で割った余りにオフセットインデックス数を加えた値を計算する。計算結果は、キャッシュタグ部７０１（図７）およびキャッシュデータ部（後述する図１８の１８０４を参照）に、新たなインデックスとして出力される。
【００９６】
モジュロ演算器１３０１は、もし有効ビットがセットされていなければ、アドレス１０７のインデックスをそのまま、キャッシュタグ部７０１（図７）およびキャッシュデータ部（後述する図１８の１８０４を参照）に、新たなインデックスとして出力する。
【００９７】
以上の構成を有するアドレスハッシュユニット５０１の具体的な動作について、図１４および図１５の動作説明図と、前述した図２、図３を用いて説明する。
ここで、図７および図８に示されるキャッシュタグ部７０１のハードウェア構成においては、キャッシュタグ部７０１の具体的なサイズは例えば次のようになる。すなわち、プログラムで指定される３２ビットのアドレス１０７において、下位７ビットでキャッシュライン内オフセットが指定され、その上位１０ビットでインデックス、さらにその上位１５ビットでタグが指定される例が示されている。従って、この例の場合は、１０ビットのインデックスによって指定されるセット１０３のライン数ｎは２の１０乗＝１０２４であるが、キャッシュタグ部７０１のサイズはこれに限定されるものではなく、システムごとに適切なその他のサイズ値を採用することができる。システムごとに適切なその他のサイズ値を採用する場合には、アドレス１０７も適切なビット幅を採用できる。
【００９８】
図１４および図１５では、理解を容易にするために、アドレス１０７が１６ビット、キャッシュライン内オフセットが７ビット、インデックスが４ビット、タグが５ビットである場合の例について説明する。この例の場合、セット１０３のライン数ｎは、図３のインデックス方向の行数として示されるように、２の４乗＝１６となる。
【００９９】
図１３のハッシュ有効化レジスタ１３０２において、図３に示されているＰＰＩＤ値がＰ１，Ｐ２，Ｐ３と、これらＰ１，Ｐ２，Ｐ３以外のＰ−ＯＴＨＥＲＳの場合に、Ｃ＝０となるケースは、ＰＰＩＤ値＝Ｐ３のときで、全ブロック数はインデックス方向のインデックス数１６に満たない。このためＰ３のインデックス数としては、１ウェイ分に満たない分のブロック数Ｒ[Ｐ３]＝５（図１０参照）がセットされる。オフセットインデックス数としては、上記増加処理の実行を開始するインデックス位置＝ＭＡＸ ＷＡＹ数増加開始位置Ｏ［ｐ］がセットされる。例えば図３において、Ｐ３のケースの場合、Ｒ[Ｐ２]＝５、すなわちＣ＝０となる直前のプロセスＰ２において図９のＳ９０２で計算された当該プロセスＰ２に割り当るブロック数１５を１ウェイあたりのブロック数１０で割った余りＲ[Ｐ２]＝５に等しい値５が、Ｏ［Ｐ３］としてセットされる。
【０１００】
図９及び図１０で前述したように、プロセスｐについて、Ｃ［ｐ］＝０であるならば、set_reg_hashval(p)関数が呼び出されて、ハッシュ有効化レジスタ１３０２へのセットが実行される。
【０１０１】
すなわち、ＰＰＩＤ値＝Ｐ３について、Ｃ［Ｐ３］＝０となるため、ハッシュ有効化レジスタ１３０２のＰ３に対応するエントリに、以下の値がセットされる。すなわち、図１４に示されるように、有効ビット＝１、インデックス数＝Ｒ［Ｐ３］＝１１、オフセットインデックス数＝ Ｒ[Ｐ２]＝５がセットされる。その他のＰＰＩＤ値Ｐ１，Ｐ２等については、Ｃ［ｐ］＝０とならないため、ハッシュ有効化レジスタ１３０２の各ＰＰＩＤ値Ｐ１，Ｐ２に対応するエントリの内容は、図１４に示されるように、共に各値が０のクリア状態となる。
【０１０２】
ここで、図１４に示されるように、要求元ＰＰＩＤ値として「３」が入力したとする。この結果、選択回路１３０３が、ハッシュ有効化レジスタ１３０２上の要求元ＰＰＩＤ値と一致するＰＰＩＤ値＝Ｐ３に対応するエントリから、有効ビット＝１、インデックス数＝１１、およびオフセットインデックス数＝５を読み出す。そして、選択回路１３０３は、それらの数値データをモジュロ演算器１３０１に与える。モジュロ演算器１３０１は、上述のようにもし有効ビットが１にセットされていれば、アドレス１０７のタグ＋インデックスの上位９ビットのビット値をインデックス数＝１１で割った余りにオフセットインデックス数＝５を加算し、その加算結果を新たなインデックスとして出力する。
【０１０３】
ここで例えば、要求元ＰＰＩＤ値＝３で、アドレス１０７として、下記のアドレスがそれぞれ入力した場合を考える。
０ｘＤ１５２
０ｘＤ１Ｄ２
０ｘＤ２５２
０ｘＤ２Ｄ２
０ｘＤ３５２
０ｘＤ３Ｄ２
０ｘＤ４５２
０ｘＤ４Ｄ２
０ｘＤ５５２
０ｘＤ５Ｄ２
０ｘＤ６５２
０ｘＤ６Ｄ２
０ｘＤ７５２
【０１０４】
図１４では、アドレス１０７として「０ｘＤ５５２」が入力された場合が示されている。
これらの場合、上位９ビットのビット値および各々に対応する１０進値は、それぞれ以下のようになる。
１１０１０００１０＝４１８
１１０１０００１１＝４１９
１１０１００１００＝４２０
１１０１００１０１＝４２１
１１０１００１１０＝４２２
１１０１００１１１＝４２３
１１０１０１０００＝４２４
１１０１０１００１＝４２５
１１０１０１０１０＝４２６
１１０１０１０１１＝４２７
１１０１０１１００＝４２８
１１０１０１１０１＝４２９
１１０１０１１１０＝４３０
【０１０５】
図１４では、アドレス１０７「０ｘＤ５５２」における上位ビット９ビットが、「１１０１０１０１０」で、１０進表現は「４２６」であることが示されている。
【０１０６】
モジュロ演算器１３０１は、上記各上位９ビット値に対して、それぞれ以下のようにして、インデックス数＝１１で割った余りにオフセットインデックス数＝５を加算し、その加算結果を新たなインデックスとして出力する。
４１８÷１１＝３８余り０、余り０＋オフセットインデックス数５＝５
４１９÷１１＝３８余り１、余り１＋オフセットインデックス数５＝６
４２０÷１１＝３８余り２、余り２＋オフセットインデックス数５＝７
４２１÷１１＝３８余り３、余り３＋オフセットインデックス数５＝８
４２２÷１１＝３８余り４、余り４＋オフセットインデックス数５＝９
４２３÷１１＝３８余り５、余り５＋オフセットインデックス数５＝１０
４２４÷１１＝３８余り６、余り６＋オフセットインデックス数５＝１１
４２５÷１１＝３８余り７、余り７＋オフセットインデックス数５＝１２
４２６÷１１＝３８余り８、余り８＋オフセットインデックス数５＝１３
４２７÷１１＝３８余り９、余り９＋オフセットインデックス数５＝１４
４２８÷１１＝３８余り１０、余り１０＋オフセットインデックス数５＝１５
４２９÷１１＝３９余り０、余り０＋オフセットインデックス数５＝５
４３０÷１１＝３９余り１、余り１＋オフセットインデックス数５＝６
【０１０７】
図１４では、上位ビット９ビット値＝１１０１０１０１０（１０進値＝４２６）をインデックス数１１で割った余りが８であり、その余りにオフセットインデックス数５を加算することにより、新たなインデックスの値１３が得られることが示されている。
【０１０８】
以上の具体例により、図３のＰ３の１１個のブロックを順にアクセスすることができることがわかる。すなわち、新たなインデックスの値は、０〜１５までの全インデックス範囲のうち、５から１５までの範囲（Ｐ３）に収まる。すなわち、ＰＰＩＤ値Ｐ３に対応する命令が実行されるときに、アドレス１０７のインデックスは、図３のインデックス方向の全域で指定される可能性がある。これに対して、モジュロ演算器１３０１は、インデックスの値が５から１５までの１１個のインデックス範囲のみが指定されるように、マッピングを行うことができる。
【０１０９】
一方、図１５に示されるように、要求元ＰＰＩＤ値として「１」（または「２」）が入力したとする。この結果、選択回路１３０３が、ハッシュ有効化レジスタ１３０２上の要求元ＰＰＩＤ値と一致するＰＰＩＤ値＝Ｐ１（またはＰ２）に対応するエントリから、有効ビット＝０、インデックス数＝０、およびオフセットインデックス数＝０を読み出す。そして、選択回路１３０３は、それらの数値データをモジュロ演算器１３０１に与える。モジュロ演算器１３０１は、上述のようにもし有効ビットが１にセットされていなければ、以下のように動作する。すなわち、アドレス１０７中の４ビットのインデックスをそのまま、キャッシュタグ部７０１（図７）およびキャッシュデータ部（後述する図１６の１６０４を参照）に、新たなインデックスとして出力する。
【０１１０】
ここで例えば、要求元ＰＰＩＤ値＝１で、アドレス１０７として、前述と同様の「０ｘＤ１５２」から「０ｘＤ７５２」までのアドレスが入力したとする。
図１５では、アドレス１０７として「０ｘＤ５５２」が入力された場合が示されている。
【０１１１】
これらの場合、アドレス１０７中のインデックスおよび各々に対応する１０進値は、それぞれ以下のようになる。
００１０＝２
００１１＝３
０１００＝４
０１０１＝５
０１１０＝６
０１１１＝７
１０００＝８
１００１＝９
１０１０＝１０
１０１１＝１１
１１００＝１２
１１０１＝１３
１１１０＝１４
モジュロ演算器１３０１は、上記各４ビットのインデックスをそのまま、新たなインデックスとして出力する。
【０１１２】
図１５では、アドレス１０７中のインデックス「１０１０」（１０進数で１０）がそのまま、新たなインデックスとして出力されることが示されている。
以上の具体例により、図３のＰＰＩＤ値＝Ｐ１またはＰ２については、０〜１５までの全インデックス範囲をインデックスとして指定できることがわかる。
【０１１３】
このようにして、或るプロセスｐについて、図２のテーブルによって指定されるブロック数が１ウェイ分に満たない場合には、次のような制御が実行される。すなわち、ＭＡＸ ＷＡＹ数増加開始位置Ｏ［Ｐ］から、プロセスｐについて割り当て可能な１ウェイ分に満たないブロック数Ｒ［ｐ］に対応するインデックス範囲でのみインデックス指定がされるように、新たなインデックスがマッピングされる。
【０１１４】
ここで、図９または図１０のステップＳ９０７によってハッシュ有効化レジスタ１３０２の内容を更新するときには、次のようなアドレス指定を行うことができる。すなわち、図１２のＭＡＸ ＷＡＹ数１０５の更新処理の場合と同様に、メインメモリ等へのメモリアクセス時には使用されないような特定のアドレス空間にマップされた領域を介して、ハッシュ有効化レジスタ１３０２に対する読み書きを実行できる。
【０１１５】
以上説明した図１３のアドレスハッシュユニット５０１の構成により、指定された命令アドレス１０７のインデックスをハッシュして得られるインデックスが、禁止された領域のインデックスを生成しないように制御することが可能となる。
【０１１６】
図１６は、図６のプロセスＩＤマップユニット６０１のハードウェア構成例を示す図である。
プロセスＩＤマップユニット６０１は、ＯＳが管理するＰＩＤと、キャッシュメモリ１０１のハードウェアが取扱い可能な物理プロセスＩＤであるＰＰＩＤの変換を行う。
【０１１７】
プロセスＩＤマップユニット６０１は、変換のマップを格納するとともに検索が可能な連想メモリ１６０１で構成されている。なお、プロセスＩＤマップユニット６０１は、レジスタで構成されてもよい。要求元ＰＩＤの値をキーとして連想メモリ１６０１の検索を行い、マッチしたＰＰＩＤの値を出力する。
【０１１８】
連想メモリ１６０１に格納する値は、図１２のＭＡＸ ＷＡＹ数１０５の更新処理の場合と同様に、メインメモリ等へのメモリアクセス時には使用されないような特定のアドレス空間にマップされた領域を介して読み書きできる。
【０１１９】
図１７は、ＰＰＩＤ書込み機構を示す図である。
図１６に示されるプロセスＩＤマップユニット６０１から出力される要求元ＰＰＩＤの値で、キャッシュタグ部７０１（図７）内のキャッシュブロック１０２の更新が行われる。このときキャッシュブロック１０２をアクセスするインデックスは、図１３に示されるアドレスハッシュユニット５０１から出力された値を用いる。
【０１２０】
図１８は、本実施形態のキャッシュメモリシステムを備える演算処理装置としてのプロセッサの構成例を示す図である。
キャッシュシステム１８０１は、図７に示したキャッシュタグ部７０１（ＭＡＸ ＷＡＹ数保持部１２０１を含む）、図５および図１３に示したアドレスハッシュユニット５０１、図６および図１６に示したプロセスＩＤマップユニット６０１を備える。また、キャッシュシステム１８０１は、キャッシュデータを保持するキャッシュデータ部１８０４およびキャッシュタグ部７０１およびキャッシュデータ部１８０４へのキャッシュアクセスを制御するキャッシュメモリ制御部１８０５を備える。
【０１２１】
キャッシュメモリ制御部１８０５は、＃１〜＃４のＣＰＵコア１８０２内の命令制御部１８０６から発行されるメモリアクセス命令をデコードして、メインメモリ１８０３に対するアクセスかキャッシュデータ部１８０４へのアクセスであるかを判断する。
【０１２２】
キャッシュメモリ制御部１８０５は、デコードの結果、メモリアクセス命令がキャッシュデータ部１８０４へのアクセスである場合には、キャッシュタグ部７０１およびキャッシュデータ部１８０４に対して、メモリアクセス命令に含まれるアドレス１０７（図１、図７等参照）を発行する。このアドレス１０７は、アドレスハッシュユニット５０１で処理された後に、キャッシュタグ部７０１およびキャッシュデータ部１８０４に出力する。
【０１２３】
また、キャッシュメモリ制御部１８０５は、メモリアクセス命令がキャッシュデータ部１８０４へのアクセスである場合には、メモリアクセス命令が実行されるＰＩＤをプロセスＩＤマップユニット６０１に出力する。プロセスＩＤマップユニット６０１は、ＰＩＤをＰＰＩＤに変換し、キャッシュタグ部７０１に要求元ＰＰＩＤとして出力する。
【０１２４】
キャッシュメモリ制御部１８０５は、図１１および図１２に示したハードウェア機構を含み、前述した置換ウェイの制御やＭＡＸ ＷＡＹ数１０５の更新制御等を実行する。
キャッシュシステム１８０１においてキャッシュミスが発生した場合には、メインメモリ１８０３からデータが読み出されるとともに、キャッシュメモリ制御部１８０５内の図１１のハードウェア構成によって生成される置換ウェイマスクに対応する置換ウェイのキャッシュブロック１０２に、そのデータが記憶される。これにより、次回アクセス時にキャッシュヒットとなり、高速なアクセスが実行される。
【０１２５】
また、キャッシュメモリ制御部１８０５は、命令制御部１８０６から、ＭＡＸ ＷＡＹ数１０５の更新を指示するＳＴＯＲＥ命令が発行されている場合には（図１２参照）、次のような動作を実行する。すなわち、キャッシュメモリ制御部１８０５は、ＭＡＸ ＷＡＹ数１０５を保持するキャッシュタグ部７０１内のＲＡＭ１２０３（図１２）内の、上記ＳＴＯＲＥ命令で指定される物理アドレスに対して、ＳＴＯＲＥ命令で指定される４バイトのデータを書き込む。これにより、該当するインデックス値上の各ＰＰＩＤ値（Ｐ１，Ｐ２，Ｐ３，Ｐ４）毎のＭＡＸ ＷＡＹ数１０５が更新される。ＳＴＯＲＥ命令によるＭＡＸ ＷＡＹ数１０５の更新指示は、命令制御部１８０６からの指示により、キャッシュアクセスを発生させるメモリアクセス命令によるメモリアクセスがなされた場合に付随させて行ってもよいし、全インデックス値について一括して実行されてもよい。
【０１２６】
図１９は、本実施形態において、同時にスケジューリングされる各プロセスが要求するウェイ数の合計が、実装されているキャッシュメモリのウェイ数を超えている場合の動作例を示す説明図である。
【０１２７】
この動作例において、まず、ＰＰＩＤ値Ｐ１、ＰＰＩＤ値Ｐ２、ＰＰＩＤ値Ｐ３の各ＰＰＩＤ値に対するＭＡＸウェイ数の設定値を例えば、５、５、３とする。
まず、ＰＰＩＤ値Ｐ３のプロセスに含まれるＬＯＡＤ命令実行によりキャッシュミスが発生する（ステップＳ１７０１）。Ｐ３のブロック数＝１は、Ｐ３のＭＡＸ ＷＡＹ数＝３よりも小さいため、他のＰＰＩＤ値のウェイ、図１９の例ではＰＰＩＤ値Ｐ２のウェイを置換する。
【０１２８】
さらに、ＰＰＩＤ値Ｐ３のプロセスに含まれるＬＯＡＤ命令実行によりキャッシュミスが発生する（ステップＳ１７０２）。Ｐ３のブロック数＝２は、Ｐ３のＭＡＸ ＷＡＹ数＝３よりも小さいため、さらに他のＰＰＩＤ値のウェイ、図１９の例ではＰＰＩＤ値Ｐ１のウェイを置換する。
【０１２９】
このようにして、ＰＰＩＤ値Ｐ３に割り当てられているブロック数は、最初１ブロックしかないが、ＰＰＩＤ値Ｐ３のプロセスに含まれるメモリアクセス要求があるとＭＡＸ ＷＡＹ数＝３まで他のＰＰＩＤのブロックを置換することにより増加する。
【０１３０】
さらに、ＰＰＩＤ値Ｐ３のプロセスに含まれるＬＯＡＤ命令実行によりキャッシュミスが発生したものとする（ステップＳ１７０３）。Ｐ３のブロック数＝３は、Ｐ３のＭＡＸ ＷＡＹ数＝３以下であるため、自ＰＰＩＤであるＰＰＩＤ値Ｐ３に対応するウェイを置換する。
【０１３１】
このように、ＭＡＸ ＷＡＹ数以上のＰＰＩＤ値Ｐ３の要求があっても、ＰＰＩＤ値Ｐ３に対するキャッシュブロック数はＭＡＸ ＷＡＹ数以上には増えない。
次に、ＰＰＩＤ値Ｐ２のプロセスに含まれるＬＯＡＤ命令実行によりキャッシュミスが発生したものとする（ステップＳ１７０４）。Ｐ２のブロック数＝１は、Ｐ２のＭＡＸ ＷＡＹ数＝５よりも小さいため、ＰＰＩＤ値Ｐ１のウェイを置換する。
【０１３２】
その後、ＰＰＩＤ値Ｐ１のプロセスに含まれるメモリアクセス要求があり、同様にしてＭＡＸ ＷＡＹ数＝５まで増加する（ステップＳ１７０５、Ｓ１７０６・・・）。このように、ＭＡＸ ＷＡＹ数に近づくように各ＰＰＩＤ値に対応するブロック数が変化することで、実装されているウェイ数を超えるＭＡＸ ＷＡＹ数を設定した場合でも問題なくキャッシュ分割を行うことが可能となる。
【０１３３】
図２０は、時間と優先度でキャッシュブロックをスケジュールする動作を示すフローチャートである。
このフローチャートの処理は、一定時間（例えば１０マイクロ秒）毎に実行される。
【０１３４】
まず、キャッシュブロックを割り当てている各プロセス毎に、キャッシュブロック割当て数 [blocks]とプロセス割当て時間 [us]の積Ａを計算する（ステップＳ２００１）。
次に、Ａ＞Ｔとなるプロセスが存在するか否かが判定される（ステップＳ２００２）。ここで、Ｔは、システム依存の定数（しきい値）とする。
【０１３５】
Ａ＞Ｔとなるプロセスが存在しステップＳ２００２の判定がＹＥＳならば、プロセス実行優先度が下げられて（ステップＳ２００３）、今回の処理を終了する。
Ａ＞Ｔとなるプロセスが存在せずステップＳ２００２の判定がＮＯならば、何もせずに今回の処理を終了する。
【０１３６】
上述した実施形態において、ＭＡＸ ＷＡＹ数は、キャッシュタグ部内に設けるようにしたが、ＯＳの管理下で制御されるような構成が採用されてもよい。
【符号の説明】
【０１３７】
１０１ キャッシュメモリ
１０２ キャッシュブロック
１０３ キャッシュライン
１０４ キャッシュウェイ
１０５ ＭＡＸ ＷＡＹ数
１０６，８０１ コンパレータ
１０７ アドレス
５０１ アドレスハッシュユニット
６０１ プロセスＩＤマップユニット
７０１ キャッシュタグ部
７０２ タグ情報
１１０１ ビット数え上げ器
１１０２ 置換ウェイ候補決定回路
１１０３ 置換ウェイマスク生成回路
１１０４，１１０７，１３０３ 選択回路
１１０５ 比較器
１１０６ インバータ
１１０８ ＰＰＩＤマッチしたビットマスク
１１０９ 置換ウェイ候補を示すビットマスク
１２０１ ＭＡＸ ＷＡＹ数１０５保持部
１２０２ アドレスマップユニット
１２０３ ＲＡＭ
１３０１ モジュロ演算器
１３０２ ハッシュ有効化レジスタ
１６０１ 連想メモリ
１８０１ キャッシュシステム
１８０２ ＣＰＵコア
１８０３ メインメモリ
１８０４ キャッシュデータ部
１８０５ キャッシュメモリ制御部
１８０６ 命令制御部
【特許請求の範囲】
【請求項１】
複数の命令を含むプロセスを実行するとともに、インデックス情報とタグ情報を含むメモリアクセス要求を発行する命令制御部と、
タグと、前記メモリアクセス要求に対応するデータと、前記命令制御部が実行するプロセスを識別するプロセス識別子を保持するブロックを、複数のインデックス各々に対応して有するキャッシュウェイを複数備えたキャッシュメモリ部と、
受信したメモリアクセス要求に含まれるインデックス情報をデコードし、前記デコードしたインデックス情報に対応するブロックを選択するインデックスデコード部と、
受信したメモリアクセス要求に含まれるタグ情報と前記インデックスデコード部が選択したブロックに含まれるタグを比較し、前記タグ情報と前記タグが一致する場合には前記インデックスデコード部が選択したブロックに含まれるデータを出力する比較部と、
前記プロセス識別子毎に設定された最大キャッシュウェイ数情報に基づき、前記キャッシュメモリ部のインデックス毎に、前記プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数を決定する制御部と、
を有することを特徴とする演算処理装置。
【請求項２】
前記命令制御部は、制御プログラムを実行して、プロセス識別子毎に設定された最大キャッシュウェイ数情報に基づき、前記キャッシュメモリ部のインデックス毎に、前記プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数を決定することを特徴とする請求項１記載の演算処理装置。
【請求項３】
前記演算処理装置において、
前記比較部による比較の結果、前記タグ情報に一致するタグが選択したブロックに存在せずキャッシュミスが発生した場合、前記キャッシュメモリ部は、前記演算処理装置に接続されたメインメモリから読み出した前記メモリアクセス要求に対応するデータを、設定された最大キャッシュウェイ数情報を超えて使用しているプロセスが使用中のブロックのいずれかが保持するデータと置換することを特徴とする請求項１又は２記載の演算処理装置。
【請求項４】
前記制御部は、
プロセス識別子毎に、各プロセス識別子に割り当てる最大ブロック数を、１つのキャッシュウェイあたりのブロック数で除算して、各プロセス識別子に割り当てるキャッシュウェイ数を算出し、
プロセス識別子毎に、各プロセス識別子に割り当てる最大ブロック数を、１つのキャッシュウェイあたりのブロック数で除算した剰余を算出して、各プロセス識別子における１キャッシュウェイ分に満たないキャッシュウェイ数を算出し、
プロセス識別子毎に、前記キャッシュメモリ部内のすべてのインデックスについて、前記各プロセス識別子に割り当てるキャッシュウェイ数を前記各プロセス識別子に対応する最大キャッシュウェイ数として設定し、
プロセス識別子毎に、前記算出した各プロセス識別子における１キャッシュウェイ分に満たないブロック数のインデックス分だけ、前記各プロセス識別子に対応する最大キャッシュウェイ数を加算し、
前記加算後の最大キャッシュウェイ数を、前記各プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数として決定することを特徴とする請求項１記載の演算処理装置。
【請求項５】
前記比較部による比較の結果、前記タグ情報に一致するタグが選択したブロックに存在せずキャッシュミスが発生した場合、前記メモリアクセス要求を発生させたプロセスを識別する要求元プロセス識別子と、前記メモリアクセス要求により特定されるインデックスの各キャッシュウェイに対応して前記キャッシュメモリ部に保持されているプロセス識別子と、前記メモリアクセス要求により特定されるインデックスに対応して決定される前記プロセス識別子毎の最大キャッシュウェイ数とに基づいて、前記メモリアクセス要求に対応するインデックスにおいて前記要求元プロセス識別子に対応するプロセスへの前記キャッシュメモリ部の領域の割当てを行なうキャッシュメモリ制御部を有することを特徴とする請求項４記載の演算処理装置。
【請求項６】
前記キャッシュメモリ制御部は、
前記比較部による比較の結果、前記タグ情報に一致するタグが選択したブロックに存在せずキャッシュミスが発生した場合、前記メモリアクセス要求に含まれるインデックスの各キャッシュウェイに対応して前記キャッシュメモリ部に保持されている各プロセス識別子が前記要求元プロセス識別子と一致するか否かを値１または０で示すビットマスクを生成するマスク生成部と、
前記生成されたビットマスクの「１」または「０」の数を計数する計数部と、
前記計数部が計数した値の数が前記要求元プロセス識別子に対応する最大キャッシュウェイ数に満たない場合には、前記マスク生成部が出力するビットマスクの各ビットを反転たビットマスクを出力し、前記計数部が計数した所定値の数が前記要求元プロセス識別子に対応する最大キャッシュウェイ数に達している場合には、前記マスク生成部が出力したビットマスクを出力するビットマスク選択部と、
前記ビットマスク選択部が出力したビットマスクに基づき、前記複数のキャッシュウェイから置換するキャッシュウェイを決定する置換ウェイ決定部を備えることを特徴とする請求項５記載の演算処理装置。
【請求項７】
プロセス識別子に割り当てるキャッシュウェイ数が０である場合、前記メモリアクセス要求に含まれる要求アドレスに含まれる部分アドレス情報を、前記プロセス識別子における１キャッシュウェイ分に満たないブロック数で除算した剰余に前記所定のインデックス開始位置を加えた値を、前記インデックスデコード部の出力とし、プロセス識別子に割り当てるキャッシュウェイ数が０でない場合、前記要求アドレスに含まれるインデックス情報を前記インデックスデコード部の出力とするアドレスハッシュ生成部を備えることを特徴とする請求項４記載の演算処理装置。
【請求項８】
前記キャッシュメモリ部は、前記最大キャッシュウェイ数を前記複数のインデックス毎および前記プロセス識別子毎に記憶するメモリを備え、
前記制御部は、前記メモリアクセス要求では使用されないアドレスを指定して、前記最大キャッシュウェイ数の更新を指示し、
前記キャッシュメモリ部は、前記制御部が指定する前記アドレスを前記メモリのアドレス空間のアドレスに変換して、前記プロセス識別子に対応する最大キャッシュウェイ数を更新することを特徴とする請求項４に記載の演算処理装置。
【請求項９】
前記プロセス識別子は、前記命令制御部が実行するプロセスを複数の種類にグループ化したときの該各グループを識別し、 前記命令制御部が実行するプロセスの実プロセスＩＤと前記プロセス識別子との対応関係を保持する連想メモリを備え、
前記命令制御部が実行するプロセスの実プロセスＩＤをキーとして前記連想メモリ部を検索して、前記実プロセスＩＤに対応するプロセス識別子を取得して、前記キャッシュメモリ制御部に出力するプロセスＩＤマップ部を備えることを特徴とする請求項１記載の演算処理装置。
【請求項１０】
タグと、データと、実行対象のプロセスに対応するプロセス識別子を保持するブロックとを複数のインデックスに対応して有するキャッシュウェイを複数備えたキャッシュメモリ部を有する演算処理装置の制御方法において、
前記演算処理装置が有する命令制御部が、複数の命令を含むプロセスを実行するとともに、インデックス情報とタグ情報を含む、前記データに対するメモリアクセス要求を発行し、
前記演算処理装置が有するインデックスデコード部が、受信したメモリアクセス要求に含まれるインデックス情報をデコードし、前記デコードしたインデックス情報に対応するブロックを選択し、
前記演算処理装置が有する比較部が、受信したメモリアクセス要求に含まれるタグ情報と前記インデックスデコード部が選択したブロックに含まれるタグを比較するとともに、前記タグ情報と前記タグが一致する場合には前記インデックスデコード部が選択したブロックに含まれるデータを出力し、
前記演算処理装置が有する制御部が、前記プロセス識別子毎に設定された最大キャッシュウェイ数情報に基づき、前記キャッシュメモリ部のインデックス毎に、前記プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数を決定することを特徴とする演算処理装置の制御方法。
【請求項１】
複数の命令を含むプロセスを実行するとともに、インデックス情報とタグ情報を含むメモリアクセス要求を発行する命令制御部と、
タグと、前記メモリアクセス要求に対応するデータと、前記命令制御部が実行するプロセスを識別するプロセス識別子を保持するブロックを、複数のインデックス各々に対応して有するキャッシュウェイを複数備えたキャッシュメモリ部と、
受信したメモリアクセス要求に含まれるインデックス情報をデコードし、前記デコードしたインデックス情報に対応するブロックを選択するインデックスデコード部と、
受信したメモリアクセス要求に含まれるタグ情報と前記インデックスデコード部が選択したブロックに含まれるタグを比較し、前記タグ情報と前記タグが一致する場合には前記インデックスデコード部が選択したブロックに含まれるデータを出力する比較部と、
前記プロセス識別子毎に設定された最大キャッシュウェイ数情報に基づき、前記キャッシュメモリ部のインデックス毎に、前記プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数を決定する制御部と、
を有することを特徴とする演算処理装置。
【請求項２】
前記命令制御部は、制御プログラムを実行して、プロセス識別子毎に設定された最大キャッシュウェイ数情報に基づき、前記キャッシュメモリ部のインデックス毎に、前記プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数を決定することを特徴とする請求項１記載の演算処理装置。
【請求項３】
前記演算処理装置において、
前記比較部による比較の結果、前記タグ情報に一致するタグが選択したブロックに存在せずキャッシュミスが発生した場合、前記キャッシュメモリ部は、前記演算処理装置に接続されたメインメモリから読み出した前記メモリアクセス要求に対応するデータを、設定された最大キャッシュウェイ数情報を超えて使用しているプロセスが使用中のブロックのいずれかが保持するデータと置換することを特徴とする請求項１又は２記載の演算処理装置。
【請求項４】
前記制御部は、
プロセス識別子毎に、各プロセス識別子に割り当てる最大ブロック数を、１つのキャッシュウェイあたりのブロック数で除算して、各プロセス識別子に割り当てるキャッシュウェイ数を算出し、
プロセス識別子毎に、各プロセス識別子に割り当てる最大ブロック数を、１つのキャッシュウェイあたりのブロック数で除算した剰余を算出して、各プロセス識別子における１キャッシュウェイ分に満たないキャッシュウェイ数を算出し、
プロセス識別子毎に、前記キャッシュメモリ部内のすべてのインデックスについて、前記各プロセス識別子に割り当てるキャッシュウェイ数を前記各プロセス識別子に対応する最大キャッシュウェイ数として設定し、
プロセス識別子毎に、前記算出した各プロセス識別子における１キャッシュウェイ分に満たないブロック数のインデックス分だけ、前記各プロセス識別子に対応する最大キャッシュウェイ数を加算し、
前記加算後の最大キャッシュウェイ数を、前記各プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数として決定することを特徴とする請求項１記載の演算処理装置。
【請求項５】
前記比較部による比較の結果、前記タグ情報に一致するタグが選択したブロックに存在せずキャッシュミスが発生した場合、前記メモリアクセス要求を発生させたプロセスを識別する要求元プロセス識別子と、前記メモリアクセス要求により特定されるインデックスの各キャッシュウェイに対応して前記キャッシュメモリ部に保持されているプロセス識別子と、前記メモリアクセス要求により特定されるインデックスに対応して決定される前記プロセス識別子毎の最大キャッシュウェイ数とに基づいて、前記メモリアクセス要求に対応するインデックスにおいて前記要求元プロセス識別子に対応するプロセスへの前記キャッシュメモリ部の領域の割当てを行なうキャッシュメモリ制御部を有することを特徴とする請求項４記載の演算処理装置。
【請求項６】
前記キャッシュメモリ制御部は、
前記比較部による比較の結果、前記タグ情報に一致するタグが選択したブロックに存在せずキャッシュミスが発生した場合、前記メモリアクセス要求に含まれるインデックスの各キャッシュウェイに対応して前記キャッシュメモリ部に保持されている各プロセス識別子が前記要求元プロセス識別子と一致するか否かを値１または０で示すビットマスクを生成するマスク生成部と、
前記生成されたビットマスクの「１」または「０」の数を計数する計数部と、
前記計数部が計数した値の数が前記要求元プロセス識別子に対応する最大キャッシュウェイ数に満たない場合には、前記マスク生成部が出力するビットマスクの各ビットを反転たビットマスクを出力し、前記計数部が計数した所定値の数が前記要求元プロセス識別子に対応する最大キャッシュウェイ数に達している場合には、前記マスク生成部が出力したビットマスクを出力するビットマスク選択部と、
前記ビットマスク選択部が出力したビットマスクに基づき、前記複数のキャッシュウェイから置換するキャッシュウェイを決定する置換ウェイ決定部を備えることを特徴とする請求項５記載の演算処理装置。
【請求項７】
プロセス識別子に割り当てるキャッシュウェイ数が０である場合、前記メモリアクセス要求に含まれる要求アドレスに含まれる部分アドレス情報を、前記プロセス識別子における１キャッシュウェイ分に満たないブロック数で除算した剰余に前記所定のインデックス開始位置を加えた値を、前記インデックスデコード部の出力とし、プロセス識別子に割り当てるキャッシュウェイ数が０でない場合、前記要求アドレスに含まれるインデックス情報を前記インデックスデコード部の出力とするアドレスハッシュ生成部を備えることを特徴とする請求項４記載の演算処理装置。
【請求項８】
前記キャッシュメモリ部は、前記最大キャッシュウェイ数を前記複数のインデックス毎および前記プロセス識別子毎に記憶するメモリを備え、
前記制御部は、前記メモリアクセス要求では使用されないアドレスを指定して、前記最大キャッシュウェイ数の更新を指示し、
前記キャッシュメモリ部は、前記制御部が指定する前記アドレスを前記メモリのアドレス空間のアドレスに変換して、前記プロセス識別子に対応する最大キャッシュウェイ数を更新することを特徴とする請求項４に記載の演算処理装置。
【請求項９】
前記プロセス識別子は、前記命令制御部が実行するプロセスを複数の種類にグループ化したときの該各グループを識別し、 前記命令制御部が実行するプロセスの実プロセスＩＤと前記プロセス識別子との対応関係を保持する連想メモリを備え、
前記命令制御部が実行するプロセスの実プロセスＩＤをキーとして前記連想メモリ部を検索して、前記実プロセスＩＤに対応するプロセス識別子を取得して、前記キャッシュメモリ制御部に出力するプロセスＩＤマップ部を備えることを特徴とする請求項１記載の演算処理装置。
【請求項１０】
タグと、データと、実行対象のプロセスに対応するプロセス識別子を保持するブロックとを複数のインデックスに対応して有するキャッシュウェイを複数備えたキャッシュメモリ部を有する演算処理装置の制御方法において、
前記演算処理装置が有する命令制御部が、複数の命令を含むプロセスを実行するとともに、インデックス情報とタグ情報を含む、前記データに対するメモリアクセス要求を発行し、
前記演算処理装置が有するインデックスデコード部が、受信したメモリアクセス要求に含まれるインデックス情報をデコードし、前記デコードしたインデックス情報に対応するブロックを選択し、
前記演算処理装置が有する比較部が、受信したメモリアクセス要求に含まれるタグ情報と前記インデックスデコード部が選択したブロックに含まれるタグを比較するとともに、前記タグ情報と前記タグが一致する場合には前記インデックスデコード部が選択したブロックに含まれるデータを出力し、
前記演算処理装置が有する制御部が、前記プロセス識別子毎に設定された最大キャッシュウェイ数情報に基づき、前記キャッシュメモリ部のインデックス毎に、前記プロセス識別子で識別されるプロセスが使用するキャッシュウェイ数を決定することを特徴とする演算処理装置の制御方法。
【図２】
【図９】
【図１０】
【図１１】
【図１３】
【図１４】
【図１５】
【図１６】
【図１８】
【図２０】
【図１】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１２】
【図１７】
【図１９】
【図９】
【図１０】
【図１１】
【図１３】
【図１４】
【図１５】
【図１６】
【図１８】
【図２０】
【図１】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１２】
【図１７】
【図１９】
【公開番号】特開２０１２−２０３７２９（Ｐ２０１２−２０３７２９Ａ）
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願番号】特願２０１１−６８８６１（Ｐ２０１１−６８８６１）
【出願日】平成２３年３月２５日（２０１１．３．２５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年１０月２２日（２０１２．１０．２２）
【国際特許分類】
【出願日】平成２３年３月２５日（２０１１．３．２５）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]