(57)【要約】      （修正有）【課題】プロセッサのキャッシュ階層からのラインの追い出しを必要とせずに、領域コヒーレンス配列（ＲＣＡ）から追い出されたラインを正確に追跡する方法およびシステムを提供する。【解決手段】ＲＣＡは、領域アドレス・タグ、領域コヒーレンス状態に関するビットのセット、およびプロセッサによりキャッシュされている領域ラインの数を追跡するライン・カウントから成る、領域エントリを含んだセット・アソシアティブ配列である。領域がＲＣＡから追い出され、追い出された領域からのラインがまだプロセッサのキャッシュにある（すなわち、領域のライン・カウントが非ゼロ）と、ＲＣＡライン・カウントが、対応するＲＶＨカウントに追加される。ＲＶＨカウントは、その後の、ＲＣＡからすでに追い出された領域のプロセッサ・キャッシュ追い出し／無効化に続いて、領域ライン・カウントの値だけデクリメントされる。【選択図】図２
2010027047.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのキャッシュを備えたキャッシュ階層を有するデータ処理システムにおいて、
領域コヒーレンス配列（ＲＣＡ）からのデータ領域の追い出しを開始するステップと、
前記データ領域に関連するライン・カウントを判断するステップと、
前記ＲＣＡからの前記データ領域の前記追い出し、および前記データ領域が非ゼロ・ライン・カウントを有することに応答して、前記ライン・カウントを、領域ビクティム・ハッシュ（ＲＶＨ）内の対応するカウント値（ＲＶＨカウント）に追加するステップであって、前記カウント値は、前記データ領域のアドレスによりインデックス付けされる、前記ステップと、
非ゼロ・カウントでインデックス付けされているデータ領域の外部スヌープ・リクエストを、前記ＲＶＨを介して解決するステップと、
を含む方法。
【請求項２】
非ゼロ・ライン・カウントを備え、次に追い出されるよう特定されている前記領域を、前記ＲＶＨ内の前記カウントの対応する更新が行われるまで前記ＲＣＡ内に維持するステップと、
キャッシュ・ヒットが生じ、ＲＶＨカウントが非ゼロであり、対応する存在ビットがゼロと等しく前記ＲＶＨカウントに対応するラインのセットが前記ＲＣＡ内に存在しないことを示すと、前記ラインのセットを前記ＲＣＡに移動するステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
前記ＲＶＨカウントは、ＲＶＨエントリにマップする複数領域から同時にキャッシュ可能な最大ライン数を表すのに十分大きく、
前記ＲＶＨは、下位領域アドレス・ビットによりインデックス付けされ、
ＲＶＨカウントは、合計である最大カウント値を有し、前記合計は、未解決リクエスト数と、複数のカウント値因数の積とを含む成分のセットの結果であり、
前記カウント値因数は、（ａ）領域内のライン数、（ｂ）プロセッサのキャッシュ階層における複数キャッシュの複数連想度と、包含的キャッシュ階層の最大連想度とのうちの１つ以上の合計、および（ｃ）前記ＲＣＡのインデックス範囲に対する前記キャッシュのインデックス範囲の比を含み、前記ＲＣＡインデックス範囲は１より大きい、
請求項１に記載の方法。
【請求項４】
前記キャッシュ階層からのラインの追い出し、および（ａ）前記領域が前記ＲＣＡ内に存在しないことまたは（ｂ）前記領域について、前記ＲＣＡのライン・カウントがゼロであることに応答して、前記キャッシュ階層から追い出されたライン数に基づく値だけ、前記ＲＶＨ内の対応するカウントをデクリメントするステップ
をさらに含む、請求項１に記載の方法。
【請求項５】
前記方法は、
対応する領域アドレスによりインデックス付けされている前記領域の前記スヌープ・リクエストを受け取るステップと、
前記リクエストされた領域アドレスによりインデックス付けされている前記ＲＶＨカウントが非ゼロであるか、または前記リクエストされた領域が非ゼロ・ライン・カウントと共に前記ＲＣＡ内に存在すると、前記リクエストされた領域が前記キャッシュ階層内に存在することを示すスヌープ応答を出すステップと、
前記リクエストされた領域アドレスによりインデックス付けされている前記ＲＶＨカウントがゼロであり、前記リクエストされた領域が前記ＲＣＡ内に存在しなければ、前記リクエストされた領域が前記キャッシュ階層内に存在しないことを示すスヌープ応答を生成するステップと、
をさらに含み、
前記ＲＶＨ内のエントリは、任意選択で、前記カウントが非ゼロであるかどうかを示すＮＺビットと、１つ以上のパリティ・ビットとを含んでおり、
前記ＮＺビットは、外部スヌープに関して高速アクセスを可能にする、
請求項１に記載の方法。
【請求項６】
前記システムのプロセッサのキャッシュ階層のフラッシュによって、パリティ違反に関係する１つ以上の問題を解決するステップと、
前記キャッシュ階層にラインが取り込まれるにつれ、前記ＲＶＨの状態を再構築するステップと、
データ保全性を高めるべく、ＲＶＨエントリに、または隣接する複数のＲＶＨエントリの複数グループに、誤り訂正符号（ＥＣＣ）ビットを組み込むステップと、
をさらに含む、請求項１に記載の方法。
【請求項７】
１つ以上のプロセッサと、
少なくとも１つのキャッシュを備えたキャッシュ階層を有するキャッシュ・サブシステムと、
領域コヒーレンス配列と、
領域コヒーレンス配列（ＲＣＡ）からのデータ領域の追い出しを開始するための論理と、
前記データ領域に関連するライン・カウントを判断するための論理と、
前記ＲＣＡからの前記データ領域の前記追い出し、および前記データ領域が非ゼロ・ライン・カウントを有することに応答して、前記ライン・カウントを、領域ビクティム・ハッシュ（ＲＶＨ）内の対応するカウント値（ＲＶＨカウント）に追加するための論理であって、前記カウント値は、前記データ領域のアドレスによりインデックス付けされる、前記論理と、
非ゼロ・カウントでインデックス付けされているデータ領域の外部スヌープ・リクエストを、前記ＲＶＨを介して解決するための論理と、
を含むデータ処理システム。
【請求項８】
非ゼロ・ライン・カウントを備え、次に追い出されるよう特定されている前記領域を、前記ＲＶＨ内の前記カウントの対応する更新が行われるまで前記ＲＣＡ内に維持し、
キャッシュ・ヒットが生じ、ＲＶＨカウントが非ゼロであり、対応する存在ビットがゼロと等しく前記ＲＶＨカウントに対応するラインのセットが前記ＲＣＡ内に存在しないことを示すと、前記ラインのセットを前記ＲＣＡへ移動するための論理
をさらに含む、請求項７に記載のデータ処理システム。
【請求項９】
前記ＲＶＨカウントは、ＲＶＨエントリにマップする複数領域から同時にキャッシュ可能な最大ライン数を表すのに十分大きく、
前記ＲＶＨは、下位領域アドレス・ビットによりインデックス付けされ、
ＲＶＨカウントは、合計である最大カウント値を有し、前記合計は、未解決リクエスト数と、複数のカウント値因数の積とを含む成分のセットの結果であり、
前記カウント値因数は、（ａ）領域内のライン数、（ｂ）プロセッサのキャッシュ階層における複数キャッシュの複数連想度と、包含的キャッシュ階層の最大連想度とのうちの１つ以上の合計、および（ｃ）前記ＲＣＡのインデックス範囲に対する前記キャッシュのインデックス範囲の比を含み、前記ＲＣＡインデックス範囲は１より大きい、
請求項７に記載のデータ処理システム。
【請求項１０】
前記キャッシュ階層からのラインの追い出し、および（ａ）前記領域が前記ＲＣＡ内に存在しないことまたは（ｂ）前記領域について、前記ＲＣＡのライン・カウントがゼロであることに応答して、前記キャッシュ階層から追い出されたライン数に基づく値だけ、前記ＲＶＨ内の対応するカウントをデクリメントするための論理
をさらに含む、請求項７に記載のデータ処理システム。
【請求項１１】
前記データ処理システムは、
対応する領域アドレスによりインデックス付けされている前記領域の前記スヌープ・リクエストを受け取り、
前記リクエストされた領域アドレスによりインデックス付けされている前記ＲＶＨカウントが非ゼロであるか、または前記リクエストされた領域が非ゼロ・ライン・カウントと共に前記ＲＣＡ内に存在すると、前記リクエストされた領域が前記キャッシュ階層内に存在することを示すスヌープ応答を出し、
前記リクエストされた領域アドレスによりインデックス付けされている前記ＲＶＨカウントがゼロであり、前記リクエストされた領域が前記ＲＣＡ内に存在しなければ、前記リクエストされた領域が前記キャッシュ階層内に存在しないことを示すスヌープ応答を生成するための論理
をさらに含み、
前記ＲＶＨ内のエントリは、任意選択で、前記カウントが非ゼロであるかどうかを示すＮＺビットと、１つ以上のパリティ・ビットとを含んでおり、
前記ＮＺビットは、外部スヌープに関して高速アクセスを可能にする、
請求項７に記載のデータ処理システム。
【請求項１２】
前記プロセッサのキャッシュ階層のフラッシュによって、パリティ違反に関係する１つ以上の問題を解決し、
前記キャッシュ階層にラインが取り込まれるにつれ、前記ＲＶＨの状態を再構築し、
データ保全性を高めるべく、ＲＶＨエントリに、または隣接する複数のＲＶＨエントリの複数グループに、誤り訂正符号（ＥＣＣ）ビットを組み込むための論理
をさらに含む、請求項７に記載のデータ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にデータ処理システムに関し、特に、クラスタ化された共有メモリ・マルチプロセッサ（ｃｌｕｓｔｅｒｅｄ  ｓｈａｒｅｄ−ｍｅｍｏｒｙ  ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ）に関する。特に本発明は、クラスタ化された共有メモリ・マルチプロセッサ・システムの効率的な領域コヒーレンス・プロトコル（ｒｅｇｉｏｎ  ｃｏｈｅｒｅｎｃｅ  ｐｒｏｔｏｃｏｌ）に関する。
【背景技術】
【０００２】
コンピュータ・システム内での全体的な帯域幅要件を軽減するために、多数の最新の共有メモリ・マイクロプロセッサ・システムはクラスタ化されている。複数のプロセッサが対称型マルチプロセッシング・ノード（ＳＭＰ（ｓｙｍｍｅｔｒｉｃ  ｍｕｌｔｉｐｒｏｃｅｓｓｉｎｇ）ノード）と呼ばれるグループに分割され、同じＳＭＰノード内のプロセッサが物理キャビネット、回路基板、マルチチップ・モジュール、またはチップを共有できるようになり、それによって、同じＳＭＰノードのプロセッサ間で、低遅延、高帯域の通信が可能となる。２段階のキャッシュ・コヒーレンス・プロトコルは、このクラスタ化構成を利用して、まず、プロセッサからのデータ・ラインに関するメモリ・リクエストをローカルＳＭＰノードへブロードキャストし、他のＳＭＰノードへは、必要な場合のみメモリ要求を送信する（例えば、最初のブロードキャストに対する応答から、リクエストされたラインがローカルＳＭＰノード上にキャッシュされていないと判断される場合）ことによって、全体的な帯域幅を節約している。この種の２段階のキャッシュ・コヒーレンス・プロトコルは、コンピュータ・システムの全体的な帯域幅要件を軽減するが、最終的に他のＳＭＰノードへブロードキャストされなければならないメモリ・リクエストには、リクエストされたラインに関してまずローカルＳＭＰノードを確認することによる遅延が生じ、コンピュータ・システムがより多くのＳＭＰノード帯域幅および電力を消費する原因となる。メモリ・リクエストを最初に、キャッシュ・データ発見の可能性が最も高い共有メモリコンピュータ・システムの適切な部分へ送信することが、パフォーマンス、拡張性、消費電力に関して重要である。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
領域コヒーレンス配列（Ｒｅｇｉｏｎ  Ｃｏｈｅｒｅｎｃｅ  Ａｒｒａｙｓ）の粗粒度コヒーレンス追跡（Ｃｏａｒｓｅ−Ｇｒａｉｎ  Ｃｏｈｅｒｅｎｃｅ  Ｔｒａｃｋｉｎｇ）は、ブロードキャストに基づく共有メモリ・マルチプロセッサ・システムにおけるメモリ・リクエストの不要なブロードキャストを回避し得る。しかし、領域コヒーレンス配列に関連する大きな課題は、正しく動作するためには、ラインをプロセッサのキャッシュ階層から追い出される（ｅｖｉｃｔｅｄ）必要があるということである。領域コヒーレンス配列は、プロセッサのキャッシュ階層中に、包含（ｉｎｃｌｕｓｉｏｎ）を維持しなければならない。したがって、別の領域の場所を空けるために領域が領域コヒーレンス配列から追い出されると、追い出された領域のラインは、プロセッサのキャッシュ階層から追い出される必要がある。
【０００４】
包含を目的としたキャッシュ・ラインの追い出しは、実装が非常に困難であり、パフォーマンスに悪影響をもたらし、キャッシュ・ヒット率を下げ、領域コヒーレンス配列の便益を相殺する。領域コヒーレンス配列は、置換のためにはラインがキャッシュされていない領域を好むと考えられるが、ライン追い出しの課題は依然として問題のままである。この問題は、領域コヒーレンス配列のサイズが縮小されると悪化する。したがって、一般的に、大きな領域コヒーレンス配列が要求される。
【０００５】
粗粒度コヒーレンス追跡の別の実装は、領域スカウト・フィルタ（Ｒｅｇｉｏｎ  Ｓｃｏｕｔ  Ｆｉｌｔｅｒｓ）である。領域スカウト・フィルタは、プロセッサのキャッシュ階層内のラインを追跡する、カウントの、タグ付きでないアドレス・インデックス付きハッシュ・テーブル（キャッシュ領域ハッシュ／ＣＲＨ：Ｃａｃｈｅｄ  Ｒｅｇｉｏｎ  Ｈａｓｈ）と、別の、プロセッサにより最近接触された非共有領域のアドレスのタグ付き配列（非共有領域テーブル／ＮＳＲＴ：Ｎｏｎ−Ｓｈａｒｅｄ  Ｒｅｇｉｏｎ  Ｔａｂｌｅ）とから成る。カウントが、エントリにハッシュするかもしれないすべてのキャッシュ・ラインを表すのに十分大きければ、カウントの、非タグ付きハッシュ・テーブルを使用することで、領域スカウト・フィルタは、ラインを追い出す必要なくキャッシュ階層中で包含を維持することができる。この利益は、正確さを犠牲にしてもたらされる。キャッシュ領域ハッシュのカウントは、そのエントリにハッシュするすべての領域からキャッシュされたラインすべての合計であり、非ゼロ・カウントは、プロセッサが、リクエストされた領域をキャッシュしてよいことを意味する。プロセッサがラインをキャッシュ階層に取り込み、対応するＣＲＨエントリ内のカウントをインクリメントすると、そのＣＲＨにマッピングしている領域はすべて、残りのシステムにより「共有されている」と見なされる。他のプロセッサは、それらの領域にあるラインに関して、リクエストをブロードキャストしなければならない。ＣＲＨが小さいほど、非ゼロ・カウントの割合は大きくなり、領域スカウト・フィルタの効果が下がる。領域スカウト・フィルタはカウントの多くがゼロの場合にのみ効果的であるため、実際のところ、領域スカウト・フィルタを効果的にするには、非常に大きなハッシュ・テーブルが必要である。
【課題を解決するための手段】
【０００６】
プロセッサのキャッシュ階層からのラインの追い出しを必要とすることなく、領域コヒーレンス配列（ＲＣＡ）から追い出されたラインを正確に追跡する方法およびシステムが開示される。ＲＣＡは、領域アドレス・タグ、領域コヒーレンス状態に関するビットのセット、およびプロセッサによりキャッシュされている領域ラインの数を追跡するためのライン・カウントから成る領域エントリを含む、セット・アソシアティブ配列である。ＲＣＡの追跡は、領域ビクティム・ハッシュ（ＲＶＨ：Ｒｅｇｉｏｎ  Ｖｉｃｔｉｍ  Ｈａｓｈ）により表される、カウントの非タグ付きハッシュ・テーブルにより容易になる。領域がＲＣＡから追い出されたとき、追い出しされた領域からのラインは、まだプロセッサのキャッシュに存在し（すなわち、領域のライン・カウントは非ゼロ）、ＲＣＡライン・カウントは、対応するＲＶＨカウントに追加される。ＲＶＨカウントは、すでにＲＣＡから追い出された領域が、後にプロセッサ・キャッシュから追い出し／無効化されるのに続いて、領域ライン・カウントの値だけデクリメントされる。
【０００７】
本発明の上記の、および追加の目的、特徴、利点が、以下の詳細な明細書で明らかとなる。
【図面の簡単な説明】
【０００８】
【図１】一実施形態によるデータ処理システムのブロック図表現である。
【図２】一実施形態による領域コヒーレンス配列（ＲＣＡ）および領域ビクティム・ハッシュ（ＲＶＨ）を示す。
【図３】一実施形態による、キャッシュされたラインに関連するＲＶＨカウントを判断するのに使用されるアルゴリズムを示す。
【図４】一実施形態による、外部プロセッサのリクエストへの応答を判断するプロセスを示す流れ図である。
【図５】一実施形態による、ＲＣＡからの領域の追い出しに基づきＲＶＨカウントを判断するプロセスを示す流れ図である。
【図６】一実施形態による、キャッシュ階層からのラインの追い出しに基づきＲＶＨカウントを判断するプロセスを示す流れ図である。
【発明を実施するための形態】
【０００９】
添付の図面と併せて読むと、本発明そのもの、ならびにその好ましい使用形態、さらなる目的および利点が、以下の実例となる実施形態の詳細な説明を参照することによって最もよく理解される。
【００１０】
実例となる実施形態は、プロセッサのキャッシュ階層からのラインの追い出しを要求することなく、領域コヒーレンス配列（ＲＣＡ）から追い出されたラインを正確に追跡する方法およびシステムを提供する。ＲＣＡは、領域アドレス・タグ、領域コヒーレンス状態に関するビットのセット、およびプロセッサによりキャッシュされている領域ラインの数を追跡するためのライン・カウントから成る領域エントリを含む、セット・アソシアティブ配列である。ＲＣＡの追跡は、領域ビクティム・ハッシュ（ＲＶＨ）により表されるカウントの非タグ付きハッシュ・テーブルにより容易になる。領域がＲＣＡから追い出されたとき、追い出された領域からのラインは、まだプロセッサのキャッシュにあり（すなわち、領域のライン・カウントは非ゼロ）、ＲＣＡライン・カウントは、対応するＲＶＨカウントに追加される。ＲＶＨカウントは、すでにＲＣＡから追い出された領域が、後にプロセッサ・キャッシュから追い出し／無効化されるのに続いて、領域ライン・カウントの値だけデクリメントされる。
【００１１】
本発明の例示的な実施形態の以下の詳細な説明には、当業者が本発明を実践できるよう、十分に詳しく、本発明が実践されるとよい具体的な例示的実施形態が記載される。当然のことながら、その他の実施形態が利用されてもよく、論理上、アーキテクチャ上、プログラム上、機構上、電気関係、およびその他の変更が、本発明の意図または範囲から逸脱することなく加えられ得る。したがって、以下の詳細な説明は、限定的な意味に取られるべきではなく、本発明の範囲は、添付の特許請求の範囲によってのみ定義される。
【００１２】
図面の説明の中では、同様の構成要素には、前の図面（単数または複数）のものと同じ名前および参照番号が与えられている。後の方の図面で、構成要素が異なる状況の中で利用される場合、または異なる機能性を備える構成要素が利用される場合、その構成要素には、図番を表現する、異なる先頭数字が与えられる（例えば、図１には１ｘｘ、さらに図２には２ｘｘ）。構成要素に指定される特定の数字は、単に説明に役立つよう与えられるものであり、発明に対する（構造上または機能上の）いかなる制限の意味を含むことも意図されていない。
【００１３】
当然のことながら、特定のコンポーネント、デバイスまたはパラメータ名、あるいはそれらすべての使用は、例でしかなく、本発明に対するいかなる制限の意味を含むことも意図されていない。したがって、本発明は、制限なく、本願明細書のコンポーネント／デバイス／パラメータの説明に利用される異なる名称／用語を用いて実現され得る。本願明細書で利用される各表現は、その表現が利用されている文脈を所与として、最も広く解釈されるべきである。
【００１４】
以下、図１を参照する。データ処理システム（および接続されているネットワーク）のブロック図表現が示されている。データ処理システム１００は、システム相互接続／バス１０２を介してシステム・メモリ１０６に接続された少なくとも１つのプロセッサまたは中央処理ユニット（ＣＰＵ：ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）１０１を備えている。さらに、データ処理システム１００は、ＣＰＵ１０１と、システム・バス１０２とに接続されたキャッシュ・コントローラ１１４を備えている。キャッシュ・コントローラ１１４は、システム・バス１０２に接続されているキャッシュ・サブシステム１０３へのアクセスを制御する。他の実装において、いくつかの可能な構成のうちの１つでは、キャッシュ・サブシステム１０３は、１つ以上のプロセッサ（ＣＰＵ１０１）と、システム・メモリ１０６との間に直接接続されていてもよい。さらに、オンチップ・プロセッサ・キャッシュ（例えばレベル１（Ｌ（Ｌｅｖｅｌ）１キャッシュ１０４））および１つ以上の下位レベルキャッシュ（例えばＬ２キャッシュ１０５）を含む、複数のレベルのキャッシュが提供されてもよい。さらに、キャッシュ・サブシステム１０３内には、領域コヒーレンス配列（ＲＣＡ）１０７および領域ビクティム・ハッシュ（ＲＶＨ）１０９が示されている。データ処理システム１００はさらに、ネットワーク・インターフェース・デバイス（ＮＩＤ：ｎｅｔｗｏｒｋ  ｉｎｔｅｒｆａｃｅ  ｄｅｖｉｃｅ）１２５と共に示されており、データ処理システム１００はこれを用いて、アクセス・ネットワーク１３０を介し１つ以上のリモート・プロセッサ１３３に接続している。
【００１５】
当業者には当然のことながら、図１に示されているハードウェアおよび基本構成は、異なるものでもよい。例えば、示されているハードウェアに加えて、またはその代わりに、その他のデバイス／コンポーネントが使用されてもよい。示されている例は、本発明に関してアーキテクチャの制限の意味を含むようには意図されていない。
【００１６】
説明される実施形態は、データ処理システム１００のコンポーネントを利用して実装されるいくつかの機能的特徴を提供する。具体的には、ＣＰＵ１０１およびキャッシュ・サブシステム１０３は、論理（例えばキャッシュ・コントローラ１１４）を利用して、種々の機能的特徴を提供する。これには、（ａ）プロセッサのキャッシュ階層からのライン追い出しを必要とすることなく、領域コヒーレンス配列（ＲＣＡ）から追い出されたラインを正確に追跡するための論理、および（ｂ）キャッシュ・メモリ・システム内の追い出されたライン追跡を容易にするために、領域ビクティム・ハッシュ（ＲＶＨ）の実装と、ＲＣＡとを組み合わせるための論理が含まれる。これらの機能的特徴、ならびにさらなる特徴／機能性は、以下、図２〜６の説明の中で記載される。
【００１７】
以下、図２を参照する。一実施形態による、領域コヒーレンス配列および領域ビクティム・ハッシュを含むキャッシュ要素が示されている。キャッシュ・コレクション（ｃａｃｈｅ  ｃｏｌｌｅｃｔｉｏｎ）２００は、領域コヒーレンス配列（ＲＣＡ）１０７および領域ビクティム・ハッシュ（ＲＶＨ）１０９を備える。ＲＶＨ１０９と共に、エントリ２０３として示されるエントリのコレクションが示されている。各エントリは、例えば、カウント２０５、ＮＺビット２０６およびパリティ（Ｐ：ｐａｒｉｔｙ）ビット２０７を含む、１つ以上のパラメータを備える。さらに、追い出しフロー２０４が示されている。
【００１８】
領域コヒーレンス配列（１０７）は、各プロセッサのキャッシュ階層（キャッシュ要素のセットを含む）にある、タグ付けされたセット・アソシアティブ配列である。各ＲＣＡエントリは、領域アドレス・タグ、領域コヒーレンス状態に関するビットのセット、およびプロセッサによりキャッシュされている領域からのライン数の追跡を保つためのライン・カウントから成る。任意選択で、ＲＣＡ１０７は、正確に領域内のどのラインがプロセッサによりキャッシュされているのかを追跡するために、ライン・カウントの代わりに、存在ビット（ｐｒｅｓｅｎｃｅ  ｂｉｔ）のセット（領域内の各ラインにつき１ビット）を利用してもよい。意図されるとおりに機能すれば、ＲＣＡ１０７は、キャッシュ階層中の包含を維持する。したがって、領域がＲＣＡ１０７から追い出されると、ラインはキャッシュ階層から追い出されてもよい。追い出された領域からのライン・カウントまたは存在ビットが非ゼロであれば、この領域からプロセッサによりキャッシュされているラインがあり、これは最終的に追い出されるか、または領域ビクティム・ハッシュ（ＲＶＨ）１０９など、キャッシュ階層内の別の構造によって表される。
【００１９】
ＲＶＨ１０９は、プロセッサのメモリ・システム（システム・メモリ１０６と、キャッシュ・サブシステム１０３のキャッシュ・コンポーネントとを備える）において領域コヒーレンス配列と共に用いられる、カウントの、タグ付きでないアドレス・インデックス付きハッシュ・テーブルである。ＲＶＨのカウント（２０５）は、ＲＣＡ１０７に対応するエントリがない、キャッシュ内のラインを表す。各カウントは、そのエントリに対応する、すべての追い出された領域からのライン・カウントの合計であってもよい。領域がＲＣＡ１０７から追い出され、追い出された領域からのラインがまだプロセッサのキャッシュにあると（すなわち、領域のライン・カウントが非ゼロ）、その領域のライン・カウントは、領域アドレスによりインデックス付けされるＲＶＨのカウント２０５に追加される。ＲＶＨ１０９は、個別の物理的構造であるか、ＲＣＡのビットにつき２のべき乗の数のＲＶＨカウントとしてＲＣＡ１０７と論理的に統合される。ＲＶＨ１０９は、一般的に、下位の領域アドレス・ビットによりインデックス付けされるが、個別の物理的構造として実装される場合はハッシュ関数が使用されてもよい。
【００２０】
カウント２０５に加え、ＲＶＨ１０９の各エントリは、任意選択で、カウントが非ゼロであるかどうかを指示するビット（ＮＺビット２０６）、および１つ以上のパリティ・ビット、Ｐビット２０７を含んでもよい。ＮＺビット２０６は、外部スヌープに関して高速アクセスを可能にする。実際には、外部スヌープはＲＶＨのカウント値を必要としないが、カウント２０５が非ゼロであるかどうかを判断するのに有用となる。効率性を高めるために、すべてのカウントを読み取りゼロ検出動作を実行する代わりに、外部スヌープに関してＮＺビット２０６が読み取られるとよい。
【００２１】
プロセッサ・キャッシュの追い出し／無効化に関して、対応する領域がＲＣＡ１０７内に存在していなければ（または領域は存在するがライン・カウントがゼロであることもある）、ＲＶＨ１０９内の対応するカウントは、追い出されたラインの数に基づく値だけデクリメントされる。あるいは、ＲＣＡ１０７は、ライン・カウントの代わりに存在ビットを利用して、プロセッサによりキャッシュされているラインの追跡を保ってもよい。したがって、ＲＶＨ１０９内の対応するカウントは、領域が存在していない（または領域が存在し、追い出し／無効化されたラインに対応する存在ビットが設定されていない）場合に、デクリメントされる。いずれにせよ、ＲＣＡ１０７において表されないキャッシュ・ラインが追い出し／無効化され、その結果ＲＶＨ１０９により表される。
【００２２】
ＲＶＨ１０９は、ＲＣＡ１０７から領域を追い出すことによって生じる、キャッシュ階層からのライン追い出しの必要性を、少量の追加ストレージを費やすことで取り除く。ＲＶＨ１０９内の各エントリは、カウント（および場合によっては他の２ビット）のみから成る。カウントは、そのエントリにマップするすべてのキャッシュ・ラインを表すのに十分大きければよい。小さなＲＶＨ（１０９）は、ＲＣＡ１０７のセットにつき１カウントと、領域コヒーレンス配列のセットにつき１〜２バイトのストレージとから成る。ストレージ割り当ては、非常に低いオーバーヘッドに相当する。ＲＣＡ１０７をＲＶＨ１０９と組み合わせることにより、プロセッサがラインをキャッシュしている領域の正確な追跡が可能になる。この正確な追跡は、タグ付きのアソシアティブ構造でのみ、包含のために複雑で悪影響となり得るキャッシュ追い出しをすることなく、可能である。
【００２３】
ＲＣＡ１０７およびＲＶＨ１０９の組み合わせは、追跡の正確さを増し、キャッシュ・データを表すのにハッシュ・テーブルのみを使用する領域スカウト・フィルタよりもよく機能する。包含のためのキャッシュ追い出しがなく、ＲＣＡ１０７は、よりよく機能し、より小さく効率的なサイズに縮小される。ＲＨＶが大きくなれば、要求されるＲＣＡは小さくなり、設計者が、最適なパフォーマンスのために２つのコンポーネント間でストレージを交換することができるようになる。
【００２４】
図３は、本発明の実施形態による、キャッシュされたラインに関連するＲＶＨカウントを判断するために使用されるアルゴリズムを示す。カウント・アルゴリズム３００は、（カウント）結果３０１および未解決リクエストの総計「ｏ」３０２を含む、カウント値パラメータのグループを含む。さらに、カウント・アルゴリズム３００には、領域内のライン数（３０３）と、プロセッサのキャッシュ階層内の複数キャッシュの複数連想度（ａｓｓｏｃｉａｔｉｖｉｔｉｅｓ）の合計（３０４）とが含まれる。さらに、領域コヒーレンス配列のインデックス範囲（ｉｎｄｅｘ  ｒａｎｇｅ）に対するキャッシュのインデックス範囲の比（３０５）、およびビットでのカウントのサイズ（３０６）が示されている。
【００２５】
下位領域アドレス・ビットによりインデックス付けされている領域ビクティム・ハッシュ（１０９）に関して、各カウント２０５は、未解決リクエストの数（３０２）と、次の数の積との合計である最大結果（３０１）を有する：領域内のライン数（３０３）、プロセッサのキャッシュ階層内の複数キャッシュの複数連想度の合計（３０４）（または包含的階層（ｉｎｃｌｕｓｉｖｅ  ｈｉｅｒａｒｃｈｉｅｓ）の最大連想度）、および領域コヒーレンス配列のインデックス範囲（１より大きい場合）に対するキャッシュのインデックス範囲の比（３０５）。ビットでのカウントのサイズ（３０６）は、２を底とする先の結果（３０１）の対数の天井関数をとることによって得られる。領域コヒーレンス配列１０７が、追い出されるべきキャッシュ済みラインのない領域を好めば、２を底とする対数をとる前に、領域コヒーレンス配列１０７の連想度が減じられてもよい。キャッシュされたラインを備える領域は、そのセットの中のその他の領域がすべて少なくとも１ラインキャッシュされている場合にのみ、追い出される。さらに、プロセッサのキャッシュ階層にラインが割り当てられている場合にのみ、領域コヒーレンス配列１０７において領域が割り当てられる。より複雑なハッシュ関数を備えた領域ビクティム・ハッシュ（１０９）では、キャッシュ階層内のすべてのラインを表すのに十分大きなカウントが必要かもしれない。
【００２６】
非ゼロ・ライン・カウント（または非ゼロ存在ビット）を備えた領域が領域コヒーレンス配列１０７から追い出されると、領域アドレスおよびライン・カウント（または存在ビット）が、キャッシュ・ラインを追い出す機構へ送られる代わりに、領域ビクティム・ハッシュ１０９へ送られる。ライン・カウント（または設定されている存在ビットの合計）は、領域ビクティム・ハッシュ１０９内のカウントに追加され、領域アドレスによりインデックス付けされ、ＮＺビットが設定される。ラインがキャッシュから追い出しまたは無効化されると、その領域に関し、領域コヒーレンス配列１０７内に、非ゼロ・ライン・カウントを備えた対応するエントリがなければ、領域ビクティム・ハッシュ・カウントはデクリメントされる。あるいは、非ゼロ存在ビットが、対応する領域の存在を示してもよい。領域ビクティム・ハッシュ・カウントがゼロにデクリメントされると、ＮＺビットがクリアされる。なお、領域ビクティム・ハッシュ・カウントに対するインクリメントはない。領域コヒーレンス配列１０７内に一致するエントリがないラインに対するプロセッサ・リクエストは、領域に関し新たなエントリを割り当てる。領域ビクティム・ハッシュ・カウントは、非ゼロ・ライン・カウントを備えた領域が領域コヒーレンス配列１０７から追い出されたときにのみ増やされる。さらに、領域ビクティム・ハッシュ・カウントは、ラインがキャッシュ階層から削除されたときにのみデクリメントされる。領域ビクティム・ハッシュ・カウントのアンダーフローも、オーバーフローも防止される。
【００２７】
ゼロ・ライン・カウント（またはすべてゼロの存在ビット）を備える領域が、領域コヒーレンス配列１０７から追い出されたときは、情報は領域ビクティム・ハッシュ１０９へ送られない。この領域からは、プロセッサによりキャッシュされているラインがないため、何も対応する領域ビクティム・ハッシュ・カウントに追加される必要がなく、ＮＺビットは変更されないままとなる。したがって、領域ビクティム・ハッシュ１０９は、プロセッサによりキャッシュされ、領域コヒーレンス配列１０７内にこの領域に対応するエントリの無いラインを表すのに使用される。
【００２８】
正確さに関して、領域コヒーレンス配列１０７から領域ビクティム・ハッシュ１０９への、非ゼロ・ライン・カウントの転送は、タイミング競合（ｔｉｍｉｎｇ  ｒａｃｅ）を避けるよう遂行される。転送がアトミック（ａｔｏｍｉｃ）であるか、または、領域ビクティム・ハッシュ・カウントが更新されるまで、領域が非ゼロ・ライン・カウント（または非ゼロ存在ビット）と共に領域コヒーレンス配列１０７内に維持される。したがって、領域の追い出し中に受け取られた外部リクエストによる、プロセッサは領域からラインをキャッシュしていないという誤った推察が起こらなくなる。
【００２９】
（１）非ゼロ・ライン・カウント（または非ゼロ存在ビット）を備えた領域が領域コヒーレンス配列から追い出される、（２）領域が領域ビクティム・ハッシュへ移動される、さらに（３）領域内のラインに関する後のプロセッサ・リクエストが領域コヒーレンス・配列内にエントリを再割り当てする、というまれなケースでは、その結果として、領域からのラインが両方の構造（ＲＣＡおよびＲＶＨ）に存在する。このケースでは、正確な動作を確保するために要求されるアクションはない。ラインは、どちらの構造でも正確に表されると考えられる。欠点は、（１）領域ビクティム・ハッシュ内のラインが原因で、領域ビクティム・ハッシュ内のそのエントリにマップする複数領域からのラインすべてが、他のプロセッサに共有されているように見えること（実際には領域コヒーレンス配列にもある、一領域からのラインのみがキャッシュされている）、および（２）領域ビクティム・ハッシュにより表されるラインが原因で、キャッシュされている１以上のラインがある一方で、領域が、領域コヒーレンス配列内にゼロ・ライン・カウント（またはゼロ存在ビット）を有する場合もあることである。これらの領域は、後からの領域コヒーレンス配列からの追い出しに、不適切に好まれることもある。存在ビットを利用する領域コヒーレンス配列のケースでは、キャッシュ・ヒットがあり、領域コヒーレンス配列内の、ラインに対応する存在ビットがゼロであれば、ラインが領域ビクティム・ハッシュから領域コヒーレンス配列に移動されるとよい。
【００３０】
パリティ違反に対しては、プロセッサのキャッシュ階層が、問題を修正するためにフラッシュされるとよい。ＲＶＨ１０９は、メタデータを含み、実際のプログラム・データは含まない。したがって、ＲＶＨ状態が破損すると、キャッシュ階層はフラッシュされるとよく、ＲＶＨ状態は、キャッシュがラインに取り込まれるにつれ再構築される。コスト削減手段として、誤り訂正符号（ＥＣＣ：Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  Ｃｏｄｅ）ビットが各ＲＶＨエントリまたは隣接した複数エントリの複数グループに組み込まれてもよい。
【００３１】
個別には、領域コヒーレンス配列の動作は概して変更されない。キャッシュされているラインがゼロの領域は、可能であれば依然として追い出しに好まれるとよい。結果として、領域ビクティム・ハッシュ・カウントは、可能であれる限りゼロのままであり、キャッシュされたラインを備える領域は、それらがより正確に追跡される領域コヒーレンス配列（領域コヒーレンス配列１０７のタグ付きアソシアティブ構造が原因で）に保たれる。
【００３２】
実例となる実施形態の実装と、従来の領域コヒーレンス配列の実装との主な違いを非包括的に列挙すると、（１）外部リクエストに応答して領域コヒーレンス配列により生成される領域スヌープ応答は、ここでは、領域ビクティム・ハッシュからの情報とビット単位ＯＲをとられること、および（２）領域コヒーレンス配列とキャッシュ階層との間に、包含のためにラインを追い出すようインターフェースが必要とされないことがある。これらの相違は、開示されている実施形態において、効率を高め、システムの複雑さを軽減する。
【００３３】
図４は、一実施形態による、ローカル・プロセッサで受け取られた外部リクエストの処理を示す流れ図である。マルチプロセッサ環境では外部プロセッサ・リクエスト（「スヌープ」と呼ばれることもある）が、ローカル・プロセッサにより受け取られることがある。外部スヌープがあると、領域ビクティム・ハッシュ１０９および領域コヒーレンス配列１０７は、領域スヌープ応答を得るために同時にアクセスされる。（ローカル）プロセッサは、（ａ）リクエストされた領域アドレスによりインデックス付けされている領域ビクティム・ハッシュ・カウントが非ゼロであるか、または（ｂ）リクエストされた領域が、非ゼロ・ライン・カウントと共に領域コヒーレンス配列内に存在すると、領域がキャッシュされていると応答する。領域が領域コヒーレンス配列１０７に存在しなくても、包含のためにキャッシュ・ラインを追い出さなくても、さらに、リクエストされた領域内の各ラインに関し他のプロセッサのキャッシュ階層を探索しなくても、正確な領域スヌープ応答が生成される。
【００３４】
カウントに加え、領域ビクティム・ハッシュ１０９の各エントリは、任意選択で、カウントが非ゼロかどうかを示すビット（ＮＺビット）、および１つ以上のパリティ・ビットを含むとよい。ＮＺビットは、外部スヌープに関し高速アクセスを可能にする。外部スヌープは、実際には領域ビクティム・ハッシュのカウント値を必要とせず、カウントが非ゼロかどうかを判断できれば十分である。効率を高めるために、外部スヌープに関しては、カウントをすべて読み込んでゼロ検出動作を遂行する代わりに、ＮＺビットが読み込まれるとよい。
【００３５】
領域ビクティム・ハッシュ１０９は、領域コヒーレンス配列１０７内に領域の対応するエントリが無い、プロセッサによりキャッシュされているラインを表すために使用される。したがって、正確さを確保するために、タイミング競合を回避するよう、非ゼロ・ライン・カウントの、領域コヒーレンス配列１０７から領域ビクティム・ハッシュ１０９への転送が完了される。転送はアトミックであるか、または、領域ビクティム・ハッシュ・カウントが更新されるまで、領域が、非ゼロ・ライン・カウント（または非ゼロ存在ビット）と共に領域コヒーレンス配列１０７に維持される。したがって、領域の追い出し中に受け取られた外部リクエストによる、プロセッサは領域からラインをキャッシュしていないという誤った推察が起こらなくなる。
【００３６】
外部リクエストに応答して、適切な領域スヌープ応答を生成するためにとられるアクションが、図４の流れ図に示されている。領域スヌープ応答は、領域アドレスによりインデックス付けされた領域ビクティム・ハッシュ・エントリが非ゼロであれば「キャッシュされている」または「共有されている」となる。領域ビクティム・ハッシュ・エントリがゼロであれば、領域コヒーレンス配列によって表されておらずプロセッサによりキャッシュされているラインはなく、スヌープ応答は、リクエストされた領域が非ゼロ・ライン・カウントと共に領域コヒーレンス配列内に存在するかどうかによって決まる。
【００３７】
図４のプロセスは、開始ブロック４０１で始まり、ブロック４０２に進む。そこで、外部プロセッサ・リクエストがローカル・プロセッサで受け取られる。ブロック４０３で、リクエストがＲＶＨ１０９およびＲＣＡ１０７の両方へ送られる。決定ブロック４０４で、データ処理システム１００／キャッシュ・コントローラ１１４が、ＲＶＨカウントが非ゼロであるかどうかを判断する。ブロック４０４で、キャッシュ・コントローラ１１４が、ＲＶＨカウントは非ゼロであると判断すると、プロセスはブロック４０５へ進む。そこで、キャッシュ・コントローラ１１４が、リクエストされた領域はキャッシュされていると示すことによって外部リクエストに応答する。ブロック４０４で、キャッシュ・コントローラ１１４が、ＲＶＨカウントがゼロであると判断すると、プロセスは決定ブロック４０６へ進む。そこでは、キャッシュ・コントローラ１１４が、ＲＣＡにキャッシュ・ヒットがあるかどうかを判断する。ブロック４０６で、キャッシュ・コントローラ１１４が、ＲＣＡ１０７にキャッシュ・ヒットがあると判断すると、プロセスは決定ブロック４０８へ進む。そこで、キャッシュ・コントローラ１１４は、ＲＣＡライン・カウントが非ゼロであるかどうかを判断する。ブロック４０６で、キャッシュ・コントローラ１１４が、ＲＣＡ１０７にキャッシュ・ミスがあると判断すると、プロセスはブロック４０７へ進む。そこで、キャッシュ・コントローラ１１４は、リクエストされた領域がキャッシュされていないと示すことによって外部リクエストに応答する。
【００３８】
ブロック４０８で、キャッシュ・コントローラ１１４が、ＲＣＡライン・カウントが非ゼロであると判断すると、プロセスはブロック４０５へ進む。ブロック４０８で、キャッシュ・コントローラ１１４が、ＲＣＡライン・カウントがゼロであると判断すると、プロセスはブロック４０７へ進む。プロセスはブロック４０９で終了する。
【００３９】
図５は、一実施形態による、ＲＣＡからの領域の追い出しに基づきＲＶＨカウントを判断するプロセスを示す流れ図である。図６は、一実施形態による、キャッシュ階層からのラインの追い出しに基づきＲＶＨカウントを判断するプロセスを示す流れ図である。図５、図６に示されている方法は、図１〜４に示されたコンポーネントを参照して説明され得るが、当然のことながら、それは便宜上にすぎず、その代わりとなるコンポーネントまたはその構成、あるいはその両方が、種々の方法を実装する際に採用可能である。したがって、本方法は、プロセッサ１０１およびデータ処理システム１００いずれか／両方の観点から説明される。
【００４０】
図５のプロセスは、開始ブロック５０１で始まり、ブロック５０２に進む。そこで、プロセッサは、領域コヒーレンス配列（ＲＣＡ）１０７内の特定の領域の追い出しを開始する。決定ブロック５０３で、キャッシュ・コントローラ１１４は、追い出された領域の（対応する）ＲＣＡライン・カウントが非ゼロであるかどうかを判断する。ブロック５０３で、キャッシュ・コントローラ１１４が、対応するＲＣＡライン・カウントがゼロであると判断すると、プロセスはブロック５０６で終了する。ブロック５０３で、キャッシュ・コントローラ１１４が、ＲＣＡライン・カウントが非ゼロであると判断すると、プロセスはブロック５０４へ進む。そこで、ＲＣＡ領域アドレスによりインデックス付けされたＲＶＨカウントが、ＲＣＡライン・カウントの値だけインクリメントされる。ブロック５０５で、ＮＺビットが設定される（非ゼロ値に）。プロセスはブロック５０６で終了する。
【００４１】
図６のプロセスは、開始ブロック５１１で始まり、ブロック５１２へ進む。そこで、プロセッサは、ライン（ＲＣＡからすでに追い出された）の特定セットの、キャッシュ階層からの追い出しを開始する。ラインは、他のデータ用の空き場所をつくるために、キャッシュ階層から追い出されてもよく、または、別のプロセッサがラインの排他的コピーをリクエストして、キャッシュからそのラインを無効化してもよい。ブロック５１３で、対応するＲＶＨカウントが、キャッシュから追い出されたライン数に基づく値だけデクリメントされる。決定ブロック５１４で、キャッシュ・コントローラ１１４が、ＲＶＨカウントがゼロ値にデクリメントされたかどうかを判断する。ブロック５１４で、キャッシュ・コントローラ１１４が、ＲＶＨカウントがゼロにデクリメントされたと判断すると、プロセスはブロック５１５へ進む。そこで、ＮＺビットがクリアされ、すなわちゼロに設定される。ブロック５１４で、キャッシュ・コントローラ１１４が、ＲＶＨカウントがゼロにデクリメントされていないと判断すると、プロセスはブロック５１６へ進み、そこでプロセスは終了する。
【００４２】
上記の流れ図では、コンピュータ可読媒体内のコンピュータ・プログラム製品として、または、コンピュータ可読コードがコンピューティング・デバイス上で実行されると一連のステップが遂行されるようにコンピュータ可読コードを含むコンピュータ・プログラム製品として、方法のうち１つ以上が具現化される。一部の実装では、本発明の意図および範囲から逸脱することなく、方法の特定のステップが、組み合わされるか、同時にもしくは異なる順序で遂行されるか、またはおそらくは省略される。したがって、本方法のステップは、特定の順番で説明および例示されているが、ステップの具体的な順番の使用は、本発明に対する制限の意味を含むよう意図されてはいない。本発明の意図または範囲から逸脱することなく、ステップの順番に関して変更が加えられてもよい。したがって、特定の順番の使用を限定的な意味にとってはならず、本発明の範囲は、添付の特許請求の範囲によってのみ定義される。
【００４３】
さらに、当然のことながら、本発明の実施形態におけるプロセスは、ソフトウェア、ファームウェアまたはハードウェアの任意の組み合わせを使用して実装されるとよい。ソフトウェアにおいて本発明を実践するための準備段階として、典型的には、プログラミング・コード（ソフトウェアであろうとファームウェアであろうと）が、固定（ハード）ドライブ、ディスケット、光ディスク、磁気テープ、ＲＯＭ、ＰＲＯＭなどの半導体メモリなど、１つ以上の機械可読ストレージ媒体に格納され、それによって、本発明に従った製造品（またはコンピュータ・プログラム製品）がつくられることになる。プログラム・コードを含んだ製造品は、ストレージ・デバイスからコードを直接実行すること、コードをストレージ・デバイスから、ハード・ディスク、ＲＡＭなどの別のストレージ・デバイスへコピーすること、または、コードを遠隔実行用に、デジタルおよびアナログ通信リンクなどの伝送タイプ媒体を使用して伝送することによって使用される。本発明の方法は、本発明によるコードを含んだ１つ以上の機械可読ストレージ・デバイスと、そこに含まれているコードを実行する適切な処理ハードウェアとを組み合わせることにより実践されるとよい。本発明を実践する装置は、本発明に従いコーディングされたプログラム（単数または複数）を含んでいるかまたはそれにネットワーク・アクセスすることができる、１つ以上の処理デバイスおよびストレージ・システムとすることができるであろう。
【００４４】
したがって、本発明の実例となる実施形態は、インストール（または実行）されるソフトウェアを備えた、完全に機能的なコンピュータ（サーバ）システムとの関連で記載されているが、本発明の実例となる実施形態のソフトウェアの態様はコンピュータ・プログラム製品として様々な形で配布可能であるということ、および本発明の実例となる実施形態は、配布を実際に実施するのに使用される媒体の特定のタイプに関わらず等しく当てはまるということが、当業者に分かるということが重要である。一例として、媒体のタイプの包括的でないリストには、フレキシブル・ディスク、サム・ドライブ、ハード・ディスク・ドライブ、ＣＤ  ＲＯＭ、ＤＶＤなどの記録可能タイプ（有形）媒体、およびデジタルおよびアナログの通信リンクなどの伝送タイプ媒体が含まれる。
【００４５】
本発明を、例示的な実施形態を参照して説明してきたが、当業者には当然のことながら、本発明の範囲から逸脱することなく、その構成要素に種々の変更が加えられ、等価物が代用されてもよい。さらに、本発明の本質的な範囲から逸脱せずに、本発明の教示に適応するよう、特定のシステム、デバイスまたはそのコンポーネントに多数の修正が加えられてもよい。したがって、本発明は、本発明を実施するために開示された特定の実施形態に限定されず、本発明は、添付の特許請求の範囲に入るすべての実施形態を含むものとする。さらに、第１、第２などの表現の使用は、いかなる順序または重要性も意味せず、正しくは、表現第１、第２などは、１つの構成要素を別のものと区別するために使用される。
【符号の説明】
【００４６】
１０７  領域コヒーレンス配列（ＲＣＡ）
１０９  領域ビクティム・ハッシュ（ＲＶＨ）
２０５  カウント
２０６  ＮＺビット
２０７  Ｐビット
２０３  エントリＡ、エントリ１６
【図１】
2010027047.tif 000003
【図２】
2010027047.tif 000004
【図３】
2010027047.tif 000005
【図４】
2010027047.tif 000006
【図５】
2010027047.tif 000007
【図６】
2010027047.tif 000008