(57)【要約】  格納システムに対するアクセスの空間分布を定量化して、格納システムの格納アドレスに対する参照の空間局所性を決定するための、コンピュータ格納媒体に符号化されたコンピュータプログラムを含む方法、システム、および、装置が記載されている。一態様では、データ処理装置により実行される方法であって、データ格納システムに対する空間分布の測値を、データ格納システムに対する複数の別個のアクセス群に基づいて決定する段階と、決定された空間分布の測値に基づいてデータ格納システムで利用するキャッシュポリシーを調節する段階とを備える方法が開示される。【選択図】図２Ａ
2013520756.tif 000002
【特許請求の範囲】
【請求項１】
データ処理装置により実行される方法であって、
データ格納システムに対するアクセスの空間分布の測値を、前記データ格納システムに対する複数の別個のアクセス群に基づいて決定する段階と、
決定された前記空間分布の測値に基づいて前記データ格納システムで利用するキャッシュポリシーを調節する段階と
を備える方法。
【請求項２】
前記データ格納システムに対する前記複数の別個のアクセス群を、前記データ格納システムに対するそれぞれ異なる参照アクセスに基づいて識別する段階を備える請求項１に記載の方法。
【請求項３】
前記データ格納システムに対する前記複数の別個のアクセス群を識別する段階は、
前記データ格納システムに対する前記それぞれ異なる参照アクセスを、乱数生成に基づいて決定する段階を有する請求項２に記載の方法。
【請求項４】
前記データ格納システムに対する前記複数の別個のアクセス群を、前記データ格納システムに対する１つの同じ参照アクセスに基づいて識別する段階を有する請求項１に記載の方法。
【請求項５】
前記データ格納システムに対する前記複数の別個のアクセス群を識別する段階は、
前記データ格納システムに対する２つの別個のアクセス群を、２つの異なる空間範囲に基づいて識別する段階を有する請求項４に記載の方法。
【請求項６】
前記空間分布の測値を決定する段階は、
前記２つの別個の群のうちの１つに対応する第１数を、前記２つの別個の群のうち別の群に対応する第２数と比較する段階を有し、
前記キャッシュポリシーを調節する段階は、
前記第１数と前記第２数との比較に基づいて、前記データ格納システムのそれぞれ異なる領域からデータを選択的にプリフェッチする段階を有する、請求項５に記載の方法。
【請求項７】
前記キャッシュポリシーを調節する段階は、
前記データ格納システムからプリフェッチするデータの量を修正する段階を有する請求項１に記載の方法。
【請求項８】
前記データ格納システムは、格納媒体を含む個々の格納デバイスである請求項１に記載の方法。
【請求項９】
格納システムであって、
格納媒体と、
キャッシュデバイスと、
前記格納媒体と前記キャッシュデバイスとに通信可能に連結されて、コンピュータシステムのプロセッサまたはメモリとインタフェースするコントローラと
を備え、
前記コントローラはさらに、
前記格納システムに関連する特定の数量のアドレス参照を受信して、
受信した前記特定の数量のアドレス参照に少なくとも一部基づいて、前記格納システムのアドレスに対する参照の空間分布を決定して、
決定された前記空間分布と、前に決定されていた空間分布とを、前記格納システムの空間局所性メトリックに統合して、
データのキャッシュで利用するために前記空間局所性メトリックを前記格納媒体から前記キャッシュデバイスに出力する、格納システム。
【請求項１０】
前記キャッシュデバイスはキャッシュメモリを有する請求項９に記載の格納システム。
【請求項１１】
前記キャッシュデバイスはさらにデバイスコントローラを有する請求項１０に記載の格納システム。
【請求項１２】
前記空間分布の決定を行うべく、前記コントローラはさらに、前記空間分布の前にされていた決定と、前記空間分布の決定との間で、ランダムなアドレス参照数量を省く、請求項９に記載の格納システム。
【請求項１３】
前記空間局所性メトリックは、前記決定された空間分布と、前記前に決定されていた空間分布との重み付け合計を含む請求項９に記載の格納システム。
【請求項１４】
前記コントローラはさらに、
前記格納システムのアドレスに対する、前記格納システムの所定のブロックオフセットに対応している参照を受信して、
前記キャッシュデバイス内の、受信された前記アドレス参照に対するキャッシュミスを検知して、
前記キャッシュミスを検知すると、前記空間局所性の現在の値に従って、前記キャッシュデバイスにキャッシュするために、前記格納システムの前記所定のブロックオフセットに関するデータを選択する、請求項９に記載の格納システム。
【請求項１５】
前記キャッシュデバイスにキャッシュするために選択された前記データは、
（ｉ）前記空間局所性メトリックの前記現在の値が、第１の値と、前記第１の値より大きい第２の値との間にある場合には、前記所定のブロックオフセットの隣の連続メモリからの前記特定の量のデータを含み、
（ｉｉ）前記空間局所性メトリックの前記現在の値が前記第２の値より大きい場合には、前記所定のブロックオフセットの隣の連続メモリからの前記特定のデータ量を超えるデータを含み、
（ｉｉｉ）前記空間局所性メトリックの前記現在の値が、前記第１の値未満である場合には、前記所定のブロックオフセットの隣の連続メモリからの前記特定のデータ量未満のデータを含む、請求項１４に記載の格納システム。
【請求項１６】
前記キャッシュデバイスにキャッシュするために選択された前記データは、前記空間局所性メトリックの前記現在の値が前記第１の値未満である場合にはゼロである請求項１５に記載の格納システム。
【請求項１７】
前記キャッシュデバイスにキャッシュするために選択された前記データは、前記空間局所性メトリックの前記現在の値が前記第２の値より大きい場合に、前記所定のブロックオフセットの隣の連続メモリから前記特定のデータ量の２倍のデータを含む請求項１５に記載の格納システム。
【請求項１８】
前記格納システムにおいて決定された空間分布は、前記受信した特定の数量のアドレス参照の第１のアドレス参照のブロックオフセットから第１の距離の範囲内にある、前記受信した特定の数量のアドレス参照の第１の部分を含む請求項１４に記載の格納システム。
【請求項１９】
前記格納システムにおいて決定された空間分布は、前記受信した特定の数量のアドレス参照の前記第１のアドレス参照のブロックオフセットから第２の距離の範囲内にある、前記受信した特定の数量のアドレス参照の第２の部分をさらに含み、
前記第２の距離は前記第１の距離より長くして、決定された前記空間分布が、前記第１の部分の、前記第１の距離に対する比率を表す前記空間分布の短距離成分と、前記第２の部分の、前記第２の距離に対する比率を表す前記空間分布の長距離成分とを含むようにして、
前記空間局所性メトリックは、前記空間分布の短距離成分および長距離成分にそれぞれ対応する短距離空間局所性メトリックと長距離空間局所性メトリックとを含む、請求項１８に記載の格納システム。
【請求項２０】
前記キャッシュデバイスにキャッシュするために選択された前記データは、
（ｉ）前記短距離空間局所性メトリックの現在の値が、前記長距離空間局所性メトリックの現在の値より大きい場合には、前記所定のブロックオフセットから前記第１の距離未満の位置にあるアドレスに対応しており、
（ｉｉ）前記短距離空間局所性メトリックの現在の値が、前記長距離空間局所性メトリックと略等しい場合には、前記所定のブロックオフセットから前記第２の距離未満の位置にあるアドレスに対応しており、
（ｉｉｉ）前記短距離空間局所性メトリックの現在の値が、前記長距離空間局所性メトリックより小さい場合には、前記所定のブロックオフセットから前記第２の距離と前記第１の距離との間の位置にあるアドレスに対応している、請求項１９に記載の格納システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、データ格納デバイスへのアクセスの空間分布に基づく格納デバイスのキャッシュに係る。
【０００２】
本願は、２０１０年２月２４日に提出された「オペおよびそのキャッシュへの適用をサンプリングすることで、ブロックデバイスの空間的局所性を定量化する方法：Quantifying Spatial Locality on a Block Device by Sampling Ops and its Application on Cache」なる名称の米国特許出願第６１／３０７，７８９号明細書の恩恵を米国特許法３５巻１１９条（ｅ）項に基づいて請求しており、この内容全体をここに参照として組み込む。
【背景技術】
【０００３】
格納デバイスの例には、ハードディスクドライブと光ディスクドライブとが含まれる。格納デバイスは通常、回転する格納媒体上のブロックにデータを格納する。ブロックサイズは、キロバイト（ＫＢ）を単位として計測される場合が多い。例えば格納媒体は、磁気ディスク、光ディスク等を含んでよい。従って格納デバイスは通常半導体メモリよりもアクセス時間が遅くなる。この結果、半導体メモリからのほうが格納媒体からよりもデータの読み出しが速くできる。
【０００４】
多くの格納デバイスが、キャッシュメモリと称される半導体メモリを含み、ホストから繰り返し要求されるデータ、または、ホストが要求する可能性のあるデータを格納している。格納デバイスは通常、データのキャッシュメモリへの格納を制御するキャッシュコントローラを含んでいる。例えばホストが読み出しコマンドを発行するとき、キャッシュコントローラは先ず、要求されているデータがキャッシュメモリに存在しているかを判断する。この判断結果が否定的であった場合には、キャッシュミスとなり、データを格納媒体から取得して、ホストに転送する。キャッシュコントローラはデータをキャッシュメモリにキャッシュすることができる。
【０００５】
ホストが同じデータを再度要求して、データがキャッシュメモリに格納されていれば（つまりキャッシュヒットとなる）、キャッシュメモリからホストへと出力される。ホストは、データをキャッシュメモリからのほうが、格納媒体からよりも速く受信することができる。加えて、ホストが要求したデータに基づいて、ホストが要求する可能性のある他の関連データもキャッシュすることができる。しかし、キャッシュメモリのサイズには限りがある。従ってキャッシュ可能なデータ量にも限りがある。この結果、キャッシュコントローラは、キャッシュメモリは選択的にデータを削除していくことになる。例えば、ホストが一定の期間要求しなかったデータを、キャッシュメモリから削除する、といったことができる。また、ホストがキャッシュメモリに格納されているデータとは異なるデータをホストが要求した場合にもデータの削除を行ってよい。キャッシュメモリのデータを選択的に削除することで、ホストが利用する可能性の高いデータをキャッシュしておくことができる。
【発明の概要】
【０００６】
本明細書は、格納システムへのアクセスの空間分布を定量化して、格納システム内の格納アドレスへの参照の空間局所性を決定するための技術を記載する。アドレスは、格納位置とも称され、特定の格納デバイスのある位置の物理アドレスのことであってよく、あるいは、アドレスは、位置を仮想ボリュームにした論理アドレスであってもよい。格納システム上のアドレスに対する参照は、格納システムにアクセスして、アクセスされたアドレスに格納されているデータの読み出し処理または書き込み処理を行うことに係る。概して、格納システムは、個々の格納デバイス（ハードドライブ）のほかにも、格納デバイス（例えば、ＲＡＩＤ（redundant array of independent disks）、ＮＡＳ（network attached device）、ＳＡＮ（storage area network））の組み合わせを含む。これら格納デバイスの組み合わせにおける空間局所性は、複数の物理デバイスにわたる論理デバイス（ブロックデバイス）にも対応していてよい。
【０００７】
概して本明細書に記載されている主題の一態様は、データ格納システムへの複数の明らかなアクセス群に基づき、データ格納デバイスへのアクセスの空間分布の測値を決定する動作を含む、データ処理装置が実行する方法に実装されてよい。方法はさらに、決定された空間分布の測値に基づいて、データ格納システムについて利用されるキャッシュポリシーを調節することも含む。
【０００８】
これらおよびその他の実装例には、以下の特徴のうち１以上を含んでよい。方法には、データ格納システムへの異なる参照アクセスに基づいてデータ格納システムへの別個のアクセス群を識別することが含まれてよい。データ格納システムへの別個のアクセス群の識別には、乱数生成に基づいてデータ格納システムへのそれぞれ異なる参照アクセスを判断することが含まれてよい。キャッシュポリシーの調節には、データ格納システムからデータのプリフェッチ量を修正することが含まれてよい。
【０００９】
方法はさらに、データ格納システムへの同じ参照アクセスに基づいてデータ格納システムへの別個のアクセス群を識別することが含まれてよい。データ格納システムへの別個のアクセス群の識別には、２つの異なる空間範囲に基づいてデータ格納システムへの２つの別個のアクセス群を識別することが含まれてよい。さらに、空間分布の測値の決定には、第１数を第２数と比較することが含まれてよい。第１数は、２つの別個の群の一方と対応していてよく、第２数は、２つの別個の群の他方と対応していてよい。さらに、キャッシュポリシーの調節には、第１数を第２数と比較することに基づいて、データ格納システムのそれぞれ異なる領域からデータを選択的にプリフェッチすることが含まれる。
【００１０】
この態様の他の実装例には、対応するシステム、装置、および、方法の動作を実行するよう構成されておりコンピュータ格納デバイスに符号化されているコンピュータプログラムが含まれる。
【００１１】
別の態様としては、記載されている主題はさらに、格納媒体、キャッシュデバイス、よび、媒体およびキャッシュデバイスに通信可能に連結されているコントローラを含む格納システムに実装することができる。コントローラは、コンピュータシステムのプロセッサまたはメモリとインタフェースすることができる。さらに、コントローラは、格納システムと関連付けられている特定された数量のアドレス参照を受け取る。コントローラはさらに、受信した特定された数量のアドレス参照に少なくとも一部基づいて、格納システムへのアドレスの参照の空間分布を決定して、決定された空間分布を、前に決定された空間分布と組み合わせて、格納システムの空間局所性メトリックにすることができる。さらにコントローラは、データのキャッシュに利用される空間局所性メトリックを、格納媒体からキャッシュデバイスへ出力してよい。
【００１２】
これらおよびその他の実装例には、以下の特徴の１以上が含まれてよい。一部の実装例では、キャッシュデバイスはキャッシュメモリを含むことができる。一部の実装例では、キャッシュデバイスはさらにデバイスコントローラを含むことができる。
【００１３】
空間分布の決定を行うために、コントローラはさらに、前の空間分布の決定と、空間分布の決定との間で、ランダムに一定数量のアドレス参照を削除することができる。さらに、空間局所性メトリックは、決定された空間分布と、前に決定された空間分布の間の重み付けされた合計を含むことができる。加えて、コントローラはさらに、格納システムのアドレスへの参照を受信して、受信したアドレス参照を、格納システム上の、所与のブロックオフセットに対応させる。加えてコントローラは、キャッシュデバイスにおける受信したアドレス参照のキャッシュミスを検知して、キャッシュミスを検知すると、格納システムの所与のブロックオフセットに関するデータを、空間局所性メトリックの現在の値に基づいてキャッシュデバイスにキャッシュするよう選択する。
【００１４】
一部の他の実施形態では、キャッシュデバイスにキャッシュするために選択されたデータは、（ｉ）空間局所性メトリックの現在の値が、第１の値と、第１の値より大きい第２の値との間にある場合には、所定のブロックオフセットの隣の連続メモリからの特定の量のデータを含み、（ｉｉ）空間局所性メトリックの現在の値が第２の値より大きい場合には、所定のブロックオフセットの隣の連続メモリからの特定のデータ量を超えるデータを含み、（ｉｉｉ）空間局所性メトリックの現在の値が、第１の値未満である場合には、所定のブロックオフセットの隣の連続メモリからの特定のデータ量未満のデータを含んでよい。一例では、キャッシュデバイスにキャッシュするために選択されたデータは、空間局所性メトリックの現在の値が第１の値未満である場合にはゼロであってもよい。別の例では、キャッシュデバイスにキャッシュするために選択されたデータは、空間局所性メトリックの現在の値が第２の値より大きい場合に、所定のブロックオフセットの隣の連続メモリから特定のデータ量の２倍のデータを含んでもよい。
【００１５】
一部の他の実施形態では、格納システムで決定された空間分布は、受信した特定数量のアドレス参照のうちの第１のアドレス参照のブロックオフセットから第１の距離の範囲内にある、第１の部分を含むことができる。加えて、格納システムで決定された空間分布はさらに、受信した特定数量のアドレス参照のうちの第１のアドレス参照のブロックオフセットから第２の距離の範囲内にある、第２の部分を含むことができる。第２の距離は第１の距離より長く、決定された空間分布が、第１の部分の第１の短いほうの距離に対する比率を表す、空間分布の短距離成分、および、第２の部分の第２の長いほうの距離に対する比率を表す、空間分布の長距離成分を含む。さらに、空間局所性メトリックは、空間分布の短距離成分および長距離成分にそれぞれ対応する短距離空間局所性メトリックと長距離空間局所性メトリックとを含んでもよい。さらに、キャッシュデバイスにキャッシュするために選択されたデータは、（ｉ）短距離空間局所性メトリックの現在の値が、長距離空間局所性メトリックの現在の値より大きい場合には、所定のブロックオフセットから第１の距離未満の位置にあるアドレスに対応しており、（ｉｉ）短距離空間局所性メトリックの現在の値が、長距離空間局所性メトリックと略等しい場合には、所定のブロックオフセットから第２の距離未満の位置にあるアドレスに対応しており、（ｉｉｉ）短距離空間局所性メトリックの現在の値が、長距離空間局所性メトリックより小さい場合には、所定のブロックオフセットから第２の距離と第１の距離との間の位置にあるアドレスに対応していてもよい。
【００１６】
この態様の他の実装例には、対応するシステム、装置、および、方法の動作を実行するよう構成されておりコンピュータ格納デバイスに符号化されているコンピュータプログラムが含まれる。
【００１７】
本明細書に記載する主題の特定の実装例は、１以上の以下の利点を実現することができる。本明細書に開示するシステムおよび技術では、格納システムの空間分布の現在のパターンに従って、最適なデータキャッシュ量を決定することができる。加えて、記載される技術を利用することで、現在の空間局所性パターンに基づいて、格納システムのどの領域からデータをプリフェッチするかを識別することができるようになる。
【００１８】
１以上の実施形態の詳細を、添付図面及び以下の記載で説明する。他の特徴及び利点は、記載、図面を読めば明らかであり、請求項を形成する。
【図面の簡単な説明】
【００１９】
【図１Ａ】格納システムに対応する空間局所性メトリックを例示する。
【図１Ｂ】格納システムに対応する空間局所性メトリックを例示する。
【図１Ｃ】格納システムに対応する空間局所性メトリックを例示する。
【図１Ｄ】格納システムに対応する空間局所性メトリックを例示する。
【図１Ｅ】格納システムに対応する空間局所性メトリックを例示する。
【図１Ｆ】格納システムに対応する空間局所性メトリックを例示する。
【図１Ｇ】格納システムに対応する空間局所性メトリックを例示する。
【図１Ｈ】格納システムに対応する空間局所性メトリックを例示する。
【００２０】
【図２Ａ】格納システムの空間局所性のメトリックに基づいて格納システムの１以上の格納デバイスに格納されているデータをキャッシュするシステムの例の各側面を示す。
【図２Ｂ】格納システムの空間局所性のメトリックに基づいて格納システムの１以上の格納デバイスに格納されているデータをキャッシュするシステムの例の各側面を示す。
【図２Ｃ】格納システムの空間局所性のメトリックに基づいて格納システムの１以上の格納デバイスに格納されているデータをキャッシュするシステムの例の各側面を示す。
【００２１】
【図３】格納システムの空間局所性メトリックの更新方法の一例を示す。
【００２２】
【図４Ａ】格納システムの空間局所性メトリックの現在の値に従って格納システムに格納されているデータをキャッシュする方法の一例の各側面を示す。
【図４Ｂ】格納システムの空間局所性メトリックの現在の値に従って格納システムに格納されているデータをキャッシュする方法の一例の各側面を示す。
【００２３】
【図５Ａ】格納システムの別の空間局所性メトリックの現在の値に従って格納システムに格納されているデータをキャッシュする方法の別の例の各側面を示す。
【図５Ｂ】格納システムの別の空間局所性メトリックの現在の値に従って格納システムに格納されているデータをキャッシュする方法の別の例の各側面を示す。
【００２４】
【図６Ａ】データ格納システムに対するアクセスの空間分布の測値に基づいて、データ格納システムで利用されるキャッシュポリシーを調節する方法の一例の各側面を示す。
【図６Ｂ】データ格納システムに対するアクセスの空間分布の測値に基づいて、データ格納システムで利用されるキャッシュポリシーを調節する方法の一例の各側面を示す。
【図６Ｃ】データ格納システムに対するアクセスの空間分布の測値に基づいて、データ格納システムで利用されるキャッシュポリシーを調節する方法の一例の各側面を示す。
【図６Ｄ】データ格納システムに対するアクセスの空間分布の測値に基づいて、データ格納システムで利用されるキャッシュポリシーを調節する方法の一例の各側面を示す。
【００２５】
図面間の同様の参照符号は同様の部材を示す。
【発明を実施するための形態】
【００２６】
小型であるが高速のランダムアクセスまたは固体（例えばフラッシュ）メモリを活用して格納システム（例えば、ハードドライブ等の個々の格納デバイスまたは格納デバイスの組み合わせ）にキャッシュする方法が非常に普及してきている。殆どのキャッシュシステムは、アクセスを目的としてホストがブロックを参照したときにキャッシュミスが生じた場合、データのブロックをキャッシュするが、キャッシュメモリには参照されたブロックを発見することはできない。しかし、ホストはキャッシュされたブロックを必ずしも利用しない。この結果、キャッシュミスの発生のみに基づいてブロックをキャッシュすると、ホストが二度と利用しないかもしれないブロックでキャッシュメモリを埋めていくことになってしまい、ホストが繰り返し利用する可能性のある他のデータのキャッシュに利用できるキャッシュメモリ量が減っていく。しかし、ホスト（例えばＭｉｃｒｏｓｏｆｔ  Ｅｘｃｈａｎｇｅ、ＳＱＬ  Ｓｅｒｖｅｒ、Ｏｒａｃｌｅ等）側で実行されているアプリケーションでは、仮想ボリュームに、各アプリケーション固有でありうる時間および／または空間アクセスパターンを体験させることができる。従って、格納システムのアドレスへの参照に比較的高い時間および／または空間の局所性があると、キャッシュの効果が高くなる。
【００２７】
格納システムのアドレスへの参照の時間局所性は、単位時間あたりに参照される格納システムのアドレス数を示しており、言い換えると、時間局所性は、格納システムのアドレスへの参照速度を表してもいる。さらに、時間局所性は、格納システムで、または格納システムの１以上の領域についてモニタが可能なので、格納システムにおけるアドレスへの参照の速度のモニタ結果に基づきキャッシュアルゴリズムを実装することができる。
【００２８】
格納システムのアドレスへの参照の空間局所性は、単位アドレス空間ごとに参照される格納システムのアドレス数を示しており、言い換えると、空間局所性は、格納システムのアドレスへの参照の空間密度を表している。例えば格納システムの特定のアドレスを参照する場合を例にとると、空間局所性は、付近のメモリ位置が将来参照される確率を表している。本明細書では、格納システムのアドレスへの参照の空間局所性という用語は、格納システムへのアクセスの空間分布と言い換えてもよい概念として利用されることに留意されたい。さらに、空間局所性も、格納システムで、または格納システムの１以上の領域についてモニタが可能なので、格納システムにおけるアドレスへの参照の空間密度のモニタ結果に基づいてキャッシュアルゴリズムを実装することができる。以上のことから、例えば空間局所性が高い場合に、格納システムのブロックのキャッシュに、キャッシュメモリが提供する限られた空間を最適利用することができることがわかる。
【００２９】
格納システムへのアクセスの空間分布の複数の表現法は、図１Ａから図１Ｈを参照して明細書内で後述する。さらに、格納システムへのアクセスの空間分布を計測する様々な技術については、図３および図６Ａから図６Ｄを参照して後述する。さらに、格納システムへのアクセスの空間分布の計測に従って、格納システムに格納されているデータをキャッシュする技術については、図４Ａから図４Ｂおよび図５Ａから図５Ｂを参照して説明する。これら技術は、図２Ａから図２Ｃを参照して説明するシステムで実装することができる。
【００３０】
図１Ａの表１は、格納システム１４０に対応する空間局所性メトリック１１０の一例を示している。空間局所性メトリック１１０は、格納システム１４０へのアクセスの空間分布の測値であり、格納システムの空間局所性１５０の測値ということもできる。空間局所性１５０の値（サンプルと称される場合もある）は、格納システム１４０のアドレスへの「ｍ」個の参照のシーケンスを利用して、格納システム１４０上のアドレス空間の「Ａ１」というサイズについて決定することができる。図１Ｂは、空間局所性１５０の値を決定するために利用される参照（読み出し／書き込み）処理に対応するブロックオフセット「Ｘｎ」と格納システム１４０の一部とを示す。図１Ｂに示すように、サイズ「Ａ１」のアドレス空間は、（Ｘｎ−１／２Ａ１）から（Ｘｎ＋１／２Ａ１）までの、ブロックオフセット「Ｘｎ」を中心とするアドレス区間である。典型的な格納システム１４０のブロックサイズは４ＫＢであるが、サイズ「Ａ１」は、例えば６４ＫＢ、１２８ＫＢ、２５６ＫＢ、または５１２ＫＢであってもよい。一部の実装例では、格納システム１４０上のアドレスへの「ｍ」個の参照シーケンスは、ブロックオフセット「Ｘｎ」に対応する参照処理に続く「ｍ」個の連続処理に対応している。「ｍ」の値は、例えばｍ＝１５といったように予め設定することもできる。
【００３１】
空間局所性１５０は、初期値を０（ゼロ）とすることができる。続いて、「ｍ」個の参照シーケンスに対応するアドレスが、ブロックオフセット「Ｘｎ」から±１／２Ａ１の距離にあるか、という「ｍ」個の決定を行い、空間局所性１５０の値を、「ｍ」個の決定のうち、各肯定的な決断について１増分してよい。例えば、「ｍ」個の参照のシーケンスのうち「ｋ」個の参照が、参照処理に対応するブロックオフセット「Ｘｎ」を中心とするサイズ「Ａ１」のアドレス空間内のアドレスに対応する場合、空間局所性１５０に、「ｋ」の整数値を与える（ここで０≦ｋ≦ｍ）。別の例としては、空間局所性１５０を正規化して、分数値「ｋ／ｍ」としてもよい（ここで０≦ｋ／ｍ≦１）。空間局所性１５０を正規化した値を利用すると、例えば格納システム１４０のアドレスへの参照についてそれぞれ異なる数（例えば「ｍ１」「ｍ２」…）のシーケンスを利用して決定した空間局所性１５０の値同士を比較することができるようになる。「ｍ」の値の他の例としては、５、１０、１５、２０、３０、５０、１００…等が挙げられる。加えて、前述した例における空間局所性１５０の例はサイズが無次元（dimensionless）であることに留意されたい。
【００３２】
空間局所性１５０の値が上述したようにして求まると、空間局所性１５０について決定した値と、空間局所性メトリックについて前に計算した値との間で重み付け平均を計算して、空間局所性メトリック１１０のインスタントバリュー（instant value）とすることができる。例えば空間局所性メトリック１１０のインスタントバリューは、以下のように計算することができる。
ＳＡ１（インスタントバリュー）＝β×ｓ（Ａ１，ｍ；ｎ）＋（１−β）×ＳＡ１（前の値）  （１）
ＳＡ１（インスタントバリュー）、ＳＡ１（前の値）という表記はそれぞれ、空間局所性メトリック１１０のインスタントバリューと前の値とを表している。（Ａ１，ｍ；ｎ）という表記は、格納システム１４０のアドレス空間のサイズ「Ａ１」について、ブロックオフセット「Ｘｎ」に対応する処理に次いで「ｍ」個の参照シーケンスを利用して決定されている空間局所性１５０の値を表している。重み付け係数「β」は、空間局所性メトリック１１０の現在の値の計算における、空間局所性メトリックの履歴のもつ影響の尺度を示している。
【００３３】
一部の実装例では、空間局所性メトリック１１０のインスタントバリューは、重み付け「β」が小さい値であるとき（例えばβ＜０．１５）、空間局所性メトリックの履歴の影響が大きい。しかし、重み「β」が大きい値のときには（例えばβ＞０．８５）、空間局所性メトリック１１０のインスタントバリューに対する空間局所性メトリックの履歴の影響は小さい。後者の場合、空間局所性メトリック１１０のインスタントバリューに大きな影響力を有するのは、いま決定された空間局所性１５０の値である。
【００３４】
空間局所性１５０の後続する値も前述したような方法で、ブロックオフセット「Ｘｎ＋１」に対応する別の処理と、他の参照処理に後続する「ｍ」個の処理の別のシーケンスを参照して、決定される。他の処理は、例えば、本明細書で後述するように、時間、処理数、または無作為の要因に基づいて決定することができる。他の参照処理と関連するブロックオフセット「Ｘｎ＋１」を図１Ｂに示す。例えば、他の「ｍ」個の参照のシーケンスに対応するアドレスが、他の参照処理に対応するブロックオフセット「Ｘｎ＋１」から±１／２Ａ１の距離にあるかを判断するための、「ｍ」個の決定がなされ、空間局所性１５０の値を、「ｍ」個の決定のうち、各肯定的な決断について１増分してよい。さらに、空間局所性メトリック１１０の後続するインスタントバリューＳＡ１（インスタントバリュー）を、空間局所性メトリック１１０について前に計算したインスタントバリューを、空間局所性メトリック１１０の前の値ＳＡ１（前の値）として利用して、ブロックオフセット「Ｘｎ＋１」に対応する処理に関する格納システム１４０上のアドレス空間のサイズ「Ａ１」について決定された空間局所性１５０の値ｓ（Ａ１、ｍ；ｎ＋１）を利用して、式（１）に従って計算する。
【００３５】
空間局所性メトリック１１０のインスタントバリューと前の値とは、互いに関連しあっているし、また、式（１）に従う空間局所性１５０の値にも関連しており、前述した量を決定する際のシステマチックな誤りは、伝播して、式（１）の計算の精度に影響を及ぼすことが考えられる。しかし、周期的な性質を持つアーチファクトの影響をこのようにして低減させることができることから、空間局所性メトリック１１０の計算の精度は、空間局所性１５０の連続する決定間で、ランダムな数の処理を省くことにより改善することができる。従って、ランダムな「ｒ」個の数の処理を、ブロックオフセット「Ｘｎ」に対応する参照処理に関する「ｍ」の処理のシーケンスにおける最終の「ｍ番目」の処理の後であって、ブロックオフセット「Ｘｎ＋１」に対応する他の参照処理の前に、省くことができる。乱数「ｒ」は、０とＮとの間の数であってよく、ここでＮは、空間局所性１５０の値の連続する決定の間で省くことができる処理の最大数に相当する。例えば「Ｎ」は、Ｎ＝１０に予め設定することができる。一部の実装例では、連続する参照処理間で省かれる処理の数を、時間区間に基づいて決定してもよい。例えば、ソフトウェア／ファームウェアで予め設定することができる値の時間区間で処理を省くことができる。別の例では、ソフトウェア／ファームウェアで予め設定可能な最小時間区間と最大時間区間との間で、ランダムに生成される値の時間区間の処理を省くことができる。後者の場合には、最小時間区間と最大時間区間をソフトウェア／ファームウェアで予め設定することができる。
【００３６】
図１Ａおよび図１Ｂとの関連で記載したように、空間局所性１５０は、メモリサイズ「Ａ１」のために決定された格納システム１４０上のアドレスに対する参照の空間密度を表している。しかし、アドレスへの参照の複数の空間密度は、複数の異なるメモリサイズ「Ａ１」「Ａ２」「Ａ３」…それぞれの空間局所性１５０の各成分を決定することで、格納システム１４０についてモニタすることができる。例えば、それぞれが空間局所性１５０の短距離、中距離、よび長距離成分に対応している、以下の不等式Ａ１＜Ａ２＜Ａ３を満たす異なるメモリサイズを選択することができる（例えば、Ａ１値が６４ＫＢであり、Ａ２値が１２８ＫＢであり、Ａ３値が２５６ＫＢであり、Ａ４値が５１２ＫＢである、といった具合である）。
【００３７】
図１Ｃの表２は、格納システム１４０に対応する空間局所性メトリック１１２および１１４の例を含んでいる。短距離の空間局所性メトリック１１２は、空間局所性１５０の短距離成分に関連しており、長距離の空間局所性メトリック１１４は、空間局所性１５０の長距離成分に関連している。空間局所性１５０の短距離成分が、メモリサイズ「Ａ１」に対して決定され、空間局所性１５０の長距離成分が、メモリサイズ「Ａ１」より大きいメモリサイズ「Ａ２」に対して決定される（つまりＡ１＜Ａ２）ことは、図１Ａから図１Ｂを参照して行った上述の開示と同様である。例えば、空間局所性１５０の短距離成分および長距離成分の値は、格納システム１４０のアドレスに対する「ｍ」個の参照のシーケンスを利用して決定することができる。図１Ｄは、格納システム１４０のアドレス空間のサイズ「Ａ１」および「Ａ２」サイズそれぞれについて、空間局所性１５０の短距離成分および長距離成分の値を決定するために利用される参照処理に対応するブロックオフセット「Ｘｎ」および格納システム１４０の一部を示す。図１Ｄに示すように、小さなほうのサイズ「Ａ１」を持つアドレス空間は、（Ｘｎ−１／２Ａ１）から（Ｘｎ＋１／２Ａ１）までのブロックオフセット「Ｘｎ」を中心とする格納システム１４０のある部分にわたり、大きなほうのサイズ「Ａ２」を持つ別のアドレス空間は、（Ｘｎ−１／２Ａ２）から（Ｘｎ＋１／２Ａ２）までのブロックオフセット「Ｘｎ」を中心とする格納システム１４０の別の部分にわたっている。例えばサイズ「Ａ１」は、６４ＫＢであってよく、サイズ「Ａ２」が１２８ＫＢであってよい。他の空間局所性メトリックは、縦楕円として表され、空間局所性１５０の他の成分にそれぞれ対応していてよい。空間局所性のこのような他の成分は、例えば超短距離成分（メモリサイズＡ＜＜「Ａ１」について定義する）、中間距離成分（メモリサイズ「Ａ１」＜Ａ＜「Ａ２」について定義する）、超長距離成分（メモリサイズＡ＞＞「Ａ１２」について決定する）であってよい。
【００３８】
空間局所性１５０の短距離成分および長距離成分の値は、０（ゼロ）に初期化されている。ついで、ある「ｍ」個の決定を、「ｍ」個の参照のシーケンスに対応するアドレスが、参照処理に対応するブロックオフセット「Ｘｎ」から±１／２Ａ１の距離の範囲内にあるかを判断して行い、別の「ｍ」個の決定を、「ｍ」個の参照のシーケンスに対応するアドレスが、参照処理に対応するブロックオフセット「Ｘｎ」から±１／２Ａ２の距離の範囲内にあるかを判断して行う。空間局所性１５０の短距離成分の値は、「ｍ」個の決定のうち、各肯定的な決定について1増分してよく、空間局所性１５０の長距離成分の値は、別の「ｍ」個の決定のうち、各肯定的な決定について１増分してよい。
【００３９】
例えば、「ｍ」個の参照のシーケンスの中の「ｕ」個の参照が、参照処理に対応するブロックオフセット「Ｘｎ」を中心とするサイズ「Ａ１」のアドレス空間以内にあるアドレスに対応している場合、空間局所性１５０の短距離成分が、「ｕ／Ａ１」の値を有し（０≦ｕ≦ｍ）、「ｍ」個の参照のシーケンスの中の「ｖ」個の参照が、参照処理に対応するブロックオフセット「Ｘｎ」を中心とするサイズ「Ａ２」のアドレス空間以内にあるアドレスに対応している場合、空間局所性１５０の長距離成分が、「ｖ／Ａ２」の値を有する（０≦ｖ≦ｍ）。空間局所性１５０の短距離成分および長距離成分は、１／（メモリサイズ）のサイズを有しており、例えば１／ＫＢと表すことができる点に留意されたい。さらに、空間局所性１５０の短距離成分および長距離成分を、それぞれメモリサイズ「Ａ１」および「Ａ２」に対するカウント「ｕ」および「ｖ」の比率として表すことで、短距離および長距離空間局所性１５０の値間で比較をすることができるようになる。
【００４０】
別の例では、空間局所性１５０の短距離成分が、「ｕ／ｍ／Ａ１」の値を有し（０≦ｕ／ｍ≦１）、空間局所性１５０の長距離成分が、「ｖ／ｍ／Ａ２」の値を有する（０≦ｖ／ｍ≦１）。正規化されたカウント「ｕ／ｍ」「ｖ／ｍ」を利用して、空間局所性１５０の短距離成分および長距離成分を表すことで、格納システム１４０のアドレスに対して異なる処理数（例えば「ｍ１」「ｍ２」）を有するシーケンスを利用して決定された空間局所性の短距離成分と、格納システム１４０のアドレスに対して異なる処理数（例えば「ｍ１」「ｍ２」）を有するシーケンスを利用して決定された空間局所性の長距離成分とを、短距離成分および長距離成分の各対について比較することができるようになる。
【００４１】
空間局所性１５０の短距離成分および長距離成分の値が上述したようにして決定されると、短距離空間局所性メトリック１１２および長距離空間局所性メトリック１１４のインスタントバリューをそれぞれ計算することができる。例えば、短距離空間局所性メトリック１１２のインスタントバリューは、空間局所性１５０の短距離成分の決定された値と、式（１）に従って前に計算された短距離空間局所性メトリックの値との間の重み付けされた平均値として計算される。式（１）を現在の文脈で考えると、ＳＡ１（インスタントバリュー）およびＳＡ１（前の値）という表記はそれぞれ、短距離空間局所性メトリック１１２のインスタントバリューと前の値とをそれぞれ表しており、ｓ（Ａ１，ｍ；ｎ）という表記は、ブロックオフセット「Ｘｎ」に対応する処理に関して、ブロックオフセット「Ｘｎ」に対応する処理の後の「ｍ」個の参照シーケンスを利用して決定された空間局所性１５０の短距離成分の値を表している。同様に、長距離空間局所性メトリック１１４のインスタントバリューは、空間局所性１５０の長距離成分の決定された値と、式（２）に従って前に計算された長距離空間局所性メトリックの値との間の重み付けされた平均値として計算される。具体的には以下のようになる。
ＳＡ２（インスタントバリュー）＝β×ｓ（Ａ２，ｍ；ｎ）＋（１−β）×ＳＡ２（前の値）  （２）
ＳＡ２（インスタントバリュー）、ＳＡ２（前の値）という表記はそれぞれ、空間局所性メトリック１１０のインスタントバリューと前の値とを表している。ｓ（Ａ２，ｍ；ｎ）という表記は、格納システム１４０のアドレス空間のサイズ「Ａ２」について、ブロックオフセット「Ｘｎ」に対応する処理に次ぐ「ｍ」個の参照シーケンスを利用して決定されている空間局所性１５０のインスタントバリューを表している。
【００４２】
後続する空間局所性１５０の短距離成分および長距離成分の値も、前述したような方法で、ブロックオフセット「Ｘｎ＋１」に対応する別の処理と、他の参照処理に後続する別の「ｍ」個の処理のシーケンスとを参照して、決定される。例えば、他の「ｍ」個の参照のシーケンスに対応するアドレスが、他の参照処理に対応するブロックオフセット「Ｘｎ＋１」から±１／２Ａ１の距離にあるかを判断するための、「ｍ」個の決定がなされ、他の「ｍ」個の参照のシーケンスに対応するアドレスが、他の参照処理に対応するブロックオフセット「Ｘｎ＋１」から±１／２Ａ２の距離にあるかを判断するための、別の「ｍ」個の決定がなされる。空間局所性１５０の短距離成分の値を、「ｍ」個の決定のうち、各肯定的な決断について１増分してよく、空間局所性１５０の長距離成分の値を、「ｍ」個の決定のうち、各肯定的な決断について１増分してよい。さらに、短距離空間局所性メトリック１１２の後続するインスタントバリューＳＡ１（インスタントバリュー）を、短距離空間局所性メトリック１１２の前に計算したインスタントバリューを、短距離空間局所性メトリック１１２の前の値ＳＡ１（前の値）として利用して、ブロックオフセット「Ｘｎ＋１」に対応する処理に関して決定された空間局所性１５０の短距離成分の値ｓ（Ａ１、ｍ；ｎ＋１）を利用して、式（１）に従って計算する。さらに、長距離空間局所性メトリック１１４の後続するインスタントバリューＳＡ２（インスタントバリュー）を、長距離空間局所性メトリック１１４の前に計算したインスタントバリューを、長距離空間局所性メトリック１１４の前の値ＳＡ２（前の値）として利用して、ブロックオフセット「Ｘｎ＋１」に対応する処理に関して決定された空間局所性１５０の長距離成分の値ｓ（Ａ２、ｍ；ｎ＋１）を利用して、式（２）に従って計算する。
【００４３】
図１Ａから図１Ｄを参照して上述した空間局所性メトリック１１０、１１２、および１１４は、格納システム１４０全体のアドレスへの、または、格納システム１４０の特定の領域のアドレスへの参照の空間パターンを特徴づけるために利用することができる。しかし、格納システムへのアクセスは、経験的な観察の結果、格納システムの領域ごとに異なる空間局所性を呈することが分かっている。この観察に基づいて、格納システムを、格納システム１４０の各部分またはサブセクションを表す複数の（固定長または可変長の）領域Ｒ１、Ｒ２、…に分けて、格納システム１４０の各領域の空間局所性１５０を見極めるために、これら領域を別々にモニタすることができる。このようにすることで、より高い空間局所性を持つ領域内のブロックを、より低い空間局所性の領域内のブロックよりも優先的にキャッシュすることができ、および／または、キャッシュメモリにより長い期間保持しておくことができるようになる。
【００４４】
図１Ｅの表３は、格納システム１４０の領域ＲｉおよびＲｊそれぞれの空間局所性メトリックの例をそれぞれ示している。領域Ｒｉ１２０の空間局所性メトリックは、格納システムの領域Ｒｉの空間局所性と関連付けられており、領域Ｒｊ１３０の空間局所性メトリックは、格納システムの領域Ｒｊの空間局所性と関連付けられている。他の空間局所性メトリックは（楕円で表されるが）、それぞれ格納システム１４０のＲ１、Ｒ２、…、ＲＮ領域といった他の領域に対応している。領域Ｒｉ、Ｒｊの空間局所性は、図１Ａから図１Ｂを参照して説明した上述の開示同様の方法で決定することができる。例えば、領域Ｒｉの空間局所性の値は、格納システム１４０の領域Ｒｉのアドレスに対する「ｍ」個の参照のシーケンスを利用して決定することができる。さらに、領域Ｒｊの空間局所性の値は、格納システム１４０の領域Ｒｊのアドレスに対する別の「ｍ」個の参照のシーケンスを利用して決定することができる。
【００４５】
図１Ｆは、格納システム１４０の領域Ｒｉのアドレス空間のサイズ「Ａ１」について領域Ｒｉの空間局所性の値を決定するために利用される参照処理に対応する領域Ｒｉのブロックオフセット「Ｘａ，ｉ」および格納システム１４０の部分を示す。サイズ「Ａ１」を持つアドレス空間は、（Ｘａ，ｉ−１／２Ａ１）から（Ｘａ，ｉ＋１／２Ａ１）までのブロックオフセット「Ｘａ，ｉ」を中心とする格納システム１４０の領域Ｒｉの部分にわたっている。図１Ｆにはさらに、格納システム１４０の領域Ｒｊのアドレス空間のサイズ「Ａ１」について領域Ｒｊの空間局所性の値を決定するために利用される別の参照処理に対応する領域Ｒｊのブロックオフセット「Ｘｂ，ｊ」も示されている。サイズ「Ａ１」を持つアドレス空間は、（Ｘｂ，ｊ−１／２Ａ１）から（Ｘｂ，ｊ＋１／２Ａ１）までのブロックオフセット「Ｘｂ，ｊ」を中心とする格納システム１４０の領域Ｒｉの部分にわたっている。
【００４６】
空間局所性ＲｉおよびＲｊの値は、０（ゼロ）に初期化することができる。続いて、格納システム１４０の領域Ｒｉの「ｍ」個のアドレスのシーケンスに対応するアドレスが、参照処理に対応するブロックオフセット「Ｘａ，ｉ」から±１／２Ａ１の距離にあるか、という「ｍ」個の決定を行い、「ｍ」個の決定のセットのうちの各肯定的な決断について領域Ｒｉの空間局所性の値を１増分してよい。さらに、格納システム１４０の領域Ｒｊの他の「ｍ」個のアドレスのシーケンスに対応するアドレスが、他の参照処理に対応するブロックオフセット「Ｘｂ，ｊ」から±１／２Ａ１の距離にあるか、という「ｍ」個の決定を行い、「ｍ」個の決定のセットのうちの各肯定的な決断について領域Ｒｊの空間局所性の値を１増分してよい。
【００４７】
例えば、格納システム１４０の領域Ｒｉのアドレスに対する「ｍ」個の参照のシーケンスのうち、「ｕ」個の参照が、参照処理に対応するブロックオフセット「Ｘａ，ｉ」を中心とするサイズ「Ａ１」のアドレス空間内のアドレスに対応している場合、領域Ｒｉの空間局所性が「ｕ」という整数値を有することになり（ここで０≦ｕ≦ｍ）、格納システム１４０の領域Ｒｊのアドレスに対する他の「ｍ」個の参照のシーケンスのうち、「ｖ」個の参照が、他の参照処理に対応するブロックオフセット「Ｘｂ，ｊ」を中心とするサイズ「Ａ１」のアドレス空間内のアドレスに対応している場合、領域Ｒｉの空間局所性が「ｖ」という整数値を有することになる（ここで０≦ｖ≦ｍ）。別の例としては、領域Ｒｉの空間局所性は正規化され、「ｕ／ｍ」の分数値を有し（０≦ｕ／ｍ≦１）、領域Ｒｊの空間局所性は正規化され、「ｖ／ｍ」の分数値を有する（０≦ｖ／ｍ≦１）。領域Ｒｉ、Ｒｊの正規化された値を利用することで、格納システム１４０の領域Ｒｉ、Ｒｊのアドレスに対する参照の異なる数（例えば「ｍ１」「ｍ２」、…）を有するシーケンスを利用して決定された領域Ｒｉ、Ｒｊそれぞれの空間局所性を比較することができるようになる。
【００４８】
領域Ｒｉの空間局所性の値が上述したようにして決定された場合には、領域Ｒｉ１２０の空間局所性メトリックのインスタントバリューを、領域Ｒｉの空間局所性の決定された値と、領域Ｒｉの空間局所性メトリックの前に計算された値との間の重み付け平均として計算する。例えば、領域Ｒｉ１２０の空間局所性メトリックのインスタントバリューは、以下のようにして計算することができる。
ＳＡ１（インスタントバリュー｜ｉ）＝β×ｓ（Ａ１，ｍ；ａ｜ｉ）＋（１−β）×ＳＡ１（前の値｜ｉ）  （３）
ＳＡ１（インスタントバリュー｜ｉ）およびＳＡ１（前の値｜ｉ）という表記は、領域Ｒｉ１２０の空間局所性メトリックのインスタントバリューおよび前の値をそれぞれ表している。ｓ（Ａ１，ｍ；ａ｜ｉ）という表記は、ブロックオフセット「Ｘａ，ｉ」に対応する処理を参照して、且つ、ブロックオフセット「Ｘａ，ｉ」に対応する処理の後の「ｍ」個のシーケンスを利用して、格納システム１４０の領域Ｒｉのアドレス空間のサイズ「Ａ１」について決定される領域Ｒｉの空間局所性の値を表している。さらに、領域Ｒｊの空間局所性の値が上述したようにして決定された場合には、領域Ｒｊ１３０の空間局所性メトリックのインスタントバリューを、領域Ｒｊの空間局所性の決定された値と、領域Ｒｊの空間局所性メトリックの前に計算された値との間の重み付け平均として計算する。例えば、領域Ｒｊ１３０の空間局所性メトリックのインスタントバリューは、以下のようにして計算することができる。
ＳＡ１（インスタントバリュー｜ｊ）＝β×ｓ（Ａ１，ｍ；ｂ｜ｊ）＋（１−β）×ＳＡ１（前の値｜ｊ）  （４）
ＳＡ１（インスタントバリュー｜ｊ）およびＳＡ１（前の値｜ｊ）という表記は、領域Ｒｊ１３０の空間局所性メトリックのインスタントバリューおよび前の値をそれぞれ表している。ｓ（Ａ１，ｍ；ｂ｜ｊ）という表記は、ブロックオフセット「Ｘｂ，ｊ」に対応する処理を参照して、且つ、ブロックオフセット「Ｘｂ，ｊ」に対応する処理の後の「ｍ」個のシーケンスを利用して、格納システム１４０の領域Ｒｉのアドレス空間のサイズ「Ａ１」について決定される領域Ｒｉの空間局所性の値を表している。
【００４９】
領域Ｒｉの空間局所性の後続の値も、前述したような方法で、ブロックオフセット「Ｘａ＋１、ｉ」に対応する別の処理と（図１Ｆには不図示）、他の参照処理に後続する「ｍ」個の処理の別のシーケンスを参照して、決定される。例えば、「ｍ」個の参照の他のシーケンスに対応するアドレスが、他の参照処理に対応するブロックオフセット「Ｘａ＋１、ｉ」から±１／２Ａ１の距離にあるかを判断するための、「ｍ」個の決定がなされ、領域Ｒｉの空間局所性の値を、「ｍ」個の決定のうち、各肯定的な決断について１増分してよい。さらに、領域Ｒｉ１２０の空間局所性メトリックの後続のインスタントバリューＳＡ１（インスタントバリュー｜ｉ）を、式（３）に従って、前に計算した領域Ｒｉ１２０の空間局所性メトリックのインスタントバリューを、領域ｉ１２０の空間局所性メトリックの前の値ＳＡ１（前の値｜ｉ）として利用して、且つ、ブロックオフセット「Ｘａ＋１、ｉ」に対応する処理を参照して格納システム１４０の領域Ｒｉのアドレス空間のサイズ「Ａ１」について決定された領域Ｒｉの空間局所性の値ｓ（Ａ１，ｍ；ａ＋１｜ｉ）を利用して計算する。
【００５０】
加えて、領域Ｒｊの空間局所性の後続する値も、前述したような方法で、ブロックオフセット「Ｘｂ＋１、ｉ」に対応する別の処理と（図１Ｆには不図示）、他の参照処理に後続する「ｍ」個の処理の別のシーケンスを参照して、決定される。例えば、「ｍ」個の参照の他のシーケンスに対応する他のアドレスが、他の参照処理に対応するブロックオフセット「Ｘｂ＋１、ｊ」から±１／２Ａ１の距離にあるかを判断するための、「ｍ」個の決定がなされ、領域Ｒｊの空間局所性の値を、「ｍ」個の決定のうち、各肯定的な決断について１増分してよい。さらに、領域Ｒｊ１３０の空間局所性メトリックの後続するインスタントバリューＳＡ１（インスタントバリュー｜ｊ）を、式（４）に従って、領域Ｒｊ１３０の空間局所性メトリックの前に計算したインスタントバリューを、領域ｉ１３０の空間局所性メトリックの前の値ＳＡ１（前の値｜ｊ）として利用して、且つ、ブロックオフセット「Ｘｂ＋１、ｊ」に対応する処理を参照して格納システム１４０の領域Ｒｊのアドレス空間のサイズ「Ａ１」について決定された領域Ｒｊの空間局所性の値ｓ（Ａ１，ｍ；ｂ＋１｜ｊ）を利用して計算する。
【００５１】
さらに、図１Ｃ−図１Ｆを参照して上述した空間局所性メトリック１１２、１１４、１２０、および１３０を組み合わせて、例えば以下で図１Ｈを参照して説明するように格納システム１４０の複数の領域のそれぞれについての短距離および長距離空間局所性メトリックを計算することもできる。さらには図４Ａから図４Ｂおよび図５Ａから図５Ｂを参照して後述するように格納システム１４０の個々の領域の短距離および長距離メトリックのインスタントバリューに従って幾つもキャッシュアルゴリズムを実装することができる。
【００５２】
図１Ｇの表４は、格納システム１４０の領域ＲｉおよびＲｊそれぞれの短距離および長距離空間局所性メトリックの例を示している。領域Ｒｉ１２２の短距離空間局所性メトリックは、領域Ｒｉの空間局所性の短距離成分に関連しており、領域ｊ１３２の短距離空間局所性メトリックは、領域Ｒｊの空間局所性の短距離成分に関連している。領域Ｒｉ１２４の長距離空間局所性メトリックは、領域Ｒｉの空間局所性の長距離成分に関連しており、領域ｊ１３４長距離空間局所性メトリックは、領域Ｒｊの空間局所性の長距離成分に関連している。格納システム１４０の所定の領域の縦楕円は、表２を参照して上述した他の空間局所性メトリックに対応している。空間局所性１５０の所定の成分の横楕円は、表３を参照して上述した格納システム１４０の他の領域に対応している。
【００５３】
領域Ｒｉ１２２の短距離局所性メトリックは、式（３）に基づいて計算することができ、ＳＡ１（インスタントバリュー｜ｉ）およびＳＡ１（前の値｜ｉ）という表記は、領域Ｒｉ１２２の短距離空間局所性メトリックのインスタントバリューおよび前の値をそれぞれ表しており、ｓ（Ａ１，ｍ；ａ｜ｉ）という表記は、ブロックオフセット「Ｘａ，ｉ」に対応する処理を参照して、且つ、ブロックオフセット「Ｘａ，ｉ」に対応する処理の後の「ｍ」個のシーケンスを利用して、格納システム１４０の領域Ｒｉのアドレス空間のサイズ「Ａ１」について決定される領域Ｒｉの空間局所性の短距離成分の値を表している。（ブロックオフセット「Ｘａ，ｉ」は図１Ｈに示されている。）さらに、領域Ｒｉの空間局所性の短距離成分は、格納システム１４０の領域Ｒｉについて、図１Ｃおよび図１Ｄを参照して上述した方法同様の方法で、決定することができる。領域Ｒｊ１３２の短距離局所性メトリックは、式（４）に基づいて計算することができ、ＳＡ１（インスタントバリュー｜ｉ）およびＳＡ１（前の値｜ｉ）という表記は、領域Ｒｊ１３２の空間局所性メトリックのインスタントバリューおよび前の値をそれぞれ表しており、ｓ（Ａ１，ｍ；ｂ｜ｊ）という表記は、ブロックオフセット「Ｘｂ，ｊ」に対応する処理を参照して、且つ、ブロックオフセット「Ｘｂ，ｊ」に対応する処理の後の別の「ｍ」個のシーケンスを利用して、格納システム１４０の領域Ｒｊのアドレス空間のサイズ「Ａ１」について決定される領域Ｒｊの空間局所性の短距離成分の値を表している。（ブロックオフセット「Ｘｂ，ｊ」は図１Ｈに示されている。）さらに、領域Ｒｊの空間局所性の短距離成分は、格納システム１４０の領域Ｒｊについて、図１Ｃおよび図１Ｄを参照して上述した方法同様の方法で、決定することができる。
【００５４】
領域Ｒｉ１２４の長距離局所性メトリックは、以下のようにして計算することができる。
ＳＡ２（インスタントバリュー｜ｉ）＝β×ｓ（Ａ２，ｍ；ａ｜ｉ）＋（１−β）×ＳＡ２（前の値｜ｉ）  （５）
ＳＡ２（インスタントバリュー｜ｉ）およびＳＡ２（前の値｜ｉ）という表記は、領域Ｒｉ１２４の長距離空間局所性メトリックのインスタントバリューおよび前の値をそれぞれ表している。ｓ（Ａ２，ｍ；ａ｜ｉ）という表記は、ブロックオフセット「Ｘａ，ｉ」に対応する処理を参照して、且つ、ブロックオフセット「Ｘａ，ｉ」に対応する処理の後の「ｍ」個のシーケンスを利用して、格納システム１４０の領域Ｒｉのアドレス空間のサイズ「Ａ２」について決定される領域Ｒｉの空間局所性の長距離成分の値を表している。さらに、領域Ｒｉの空間局所性の長距離成分は、格納システム１４０の領域Ｒｉについて、図１Ｃおよび図１Ｄを参照して上述した方法同様の方法で、決定することができる。領域Ｒｊ１３４の長距離局所性メトリックは、以下のようにして計算することができる。
ＳＡ２（インスタントバリュー｜ｊ）＝β×ｓ（Ａ２，ｍ；ｂ｜ｊ）＋（１−β）×ＳＡ２（前の値｜ｊ）  （６）
ＳＡ２（インスタントバリュー｜ｊ）およびＳＡ２（前の値｜ｊ）という表記は、領域Ｒｊ１３４の長距離空間局所性メトリックのインスタントバリューおよび前の値をそれぞれ表している。ｓ（Ａ２，ｍ；ｂ｜ｊ）という表記は、ブロックオフセット「Ｘｂ，ｊ」に対応する処理を参照して、且つ、ブロックオフセット「Ｘｂ，ｊ」に対応する処理の後の別の「ｍ」個のシーケンスを利用して、格納システム１４０の領域Ｒｊのアドレス空間のサイズ「Ａ２」について決定される領域Ｒｊの空間局所性の長距離成分の値を表している。さらに、領域Ｒｊの空間局所性の長距離成分は、格納システム１４０の領域Ｒｊについて、図１Ｃおよび図１Ｄを参照して上述した方法同様の方法で、決定することができる。
【００５５】
図２Ａは、格納システムの空間局所性のメトリックに基づいて格納システム２００の１以上のデバイスに格納されているデータをキャッシュするシステムの一例を示す。空間局所性メトリックは、図１Ａから図１Ｈを参照して上述した１以上のメトリック１１０、１１２、１１４、１２０、１２２、１２４、１３０、１３２、および１３４のいずれかであってよい。格納システム２００は、ホストシステム２０１／２０１'の外部にあってもこの一部であってもよい。一部の実装例では、格納システム２００は、１以上の格納デバイス２２０、キャッシュデバイス２３０、および、１以上の格納デバイス２２０と、または、キャッシュデバイス２３０と、複数の通信経路２０、４０、５０、および７０を介して通信可能に連結された通信コントローラ２１０を含む。１以上の格納デバイス２２０は、個々の格納デバイス（例えばハードドライブ）であってもよいし、格納デバイス（例えばＲＡＩＤ、ＮＡＳ、およびＳＡＮ）の組み合わせであってもよい。
【００５６】
一部の実装例では、コントローラ２１０は、格納システム２００の外部にあってもよい。さらにコントローラ２１０は、ホストシステム２０１／２０１'のメモリシステム２０６および／またはプロセッサ２０２と、通信経路１０を介してインタフェースするよう構成されている。さらなる通信経路３０および６０を、格納システム２００とメモリシステム２０６（および／またはプロセッサ２０２）との間に構築することもできる。図２Ｂは、キャッシュメモリ２３４'を含むキャッシュデバイス２３０'の実装の第１の例を示す。この第１の実装例では、格納システム２００のキャッシュ機能（キャッシュヒットおよびキャッシミスを生成することを含む）が、コントローラ２１０により実行される。図２Ｃは、デバイスコントローラ２３８のキャッシュメモリ２３４''を含むキャッシュデバイス２３０''の実装の第２の例を示す。この第２の実装では、格納システム２００のキャッシュ機能（キャッシュヒットおよびキャッシミスを生成することを含む）が、キャッシュデバイス２３０''のデバイスコントローラ２３８により実行される。
【００５７】
コントローラ２１０は、特定用途向け集積回路（ＡＳＩＣ）、電子回路、プロセッサ（共有、専用、またはグループ）、および／または、１以上のソフトウェアまたはファームウェアプログラムを実行するメモリ（共有、専用、またはグループ）、統合論理回路、および／または、記載した機能を提供する他の適切なコンポーネントの一部であってもよいし、これを含んでも良い。例えばコントローラ２１０は、格納システム２００の空間局所性メトリックを生成および更新するよう構成されている。
【００５８】
コントローラ２１０は、メモリシステム２０６から（通信経路１０経由で）、格納システム２００の特定数量「ｍ」のアドレス参照を受信することができる。例えば、アドレス参照の数量「ｍ」は、プログラムにより指定することも可能である。さらに量「ｍ」は、格納デバイス２２０のタイプ、ホストシステム２０１／２０１'が実行しているアプリケーションのタイプ等に基づいて変更することができる。例えば量「ｍ」は、格納システム２００のアドレスへの１５個の参照に等しくなるよう設定することができる。他の「ｍ」の値の例には、５、１０、１５、２０、３０、５０、１００、…等が含まれる。
【００５９】
さらにコントローラ２１０は、格納システム２００の空間局所性を、連続したアドレス参照の第１のアドレス参照のブロックオフセット「Ｘｎ」から第１の距離の範囲内にある連続したアドレス参照について受信した特定数量「ｍ」の一部として決定してよい。格納システム２００の空間局所性の決定は、図２Ａから図２Ｃを参照して本明細書で上述したようにして実行することができる。さらに格納システム２００の空間局所性の決定の一環として、コントローラ２１０は、空間局所性の前の決定と、空間局所性の現在の決定との間で、ランダムなアドレス参照数量を省くこともできる。周期性のアーチファクトが導入するシステマチックなエラーは、このようにランダムにサンプリングすることで低減することができる。従って、格納システム２００の空間局所性の精度を上げることができる。乱数生成は、例えば予め定められたシードとモジュロ演算子とを利用するもののような、擬似数生成であってもよいし、あるいは、宇宙背景放射を検知するためのセンサ等のランダムな入力源に基づくもののような、真の乱数生成であってもよい。
【００６０】
加えて、コントローラ２１０は、決定される空間局所性を、前に決定された空間局所性と組み合わせて、格納システム２００の空間局所性メトリックを形成するよう構成されている。格納システム２００の空間局所性メトリックの複数の例を、図２Ａから図２Ｃを参照して上述してきた。例えば、図２Ａおよび図２Ｂを参照して上述したように、特定のメモリサイズに対応する空間局所性メトリックを格納システム２００に対して計算することができる。別の例としては、上述したように、それぞれ大小のメモリサイズに対応する短期、長期空間局所性メトリックを、格納システム２００全体について計算することもできる。また別の例としては、上述したように、特定のメモリサイズに対応する空間局所性メトリックを、格納システム２００の各領域について計算することもできる。さらには上述したように、それぞれ大小のメモリサイズに対応する短期、長期空間局所性メトリックを、格納システム２００の複数の領域それぞれについて計算することもできる。前述した空間局所性メトリックのそれぞれは、式１から式６に従って決定された空間局所性および前に決定された空間局所性との重み付けを加えた合計を含む。
【００６１】
コントローラ２１０は、計算された空間局所性メトリックのうち１以上を利用することができ、空間局所性メトリックの１以上を（通信経路５０を通じて）デバイスコントローラ２２４に提供して、１以上の格納デバイス２２０からキャッシュデバイス２３０に（通信経路７０を介して）データをキャッシュすることができる。空間局所性メトリックの現在の値に基づく様々なキャッシュ技術を、図５Ａから図５Ｂ、および、図６Ａから図６Ｂを参照して後述する。
【００６２】
コントローラ２１０は、さらに、メモリシステム２０６から（通信経路１０を介して）格納システム２００のアドレスへの参照を受信するよう構成されている。受信したアドレス参照は、格納システム２００の所定のブロックオフセット（Ｘ）に格納されているデータに対応していてよい。コントローラ２１０は、受信した参照をキャッシュデバイス２３０に（通信経路２０経由で）中継することができる。参照されるデータがキャッシュデバイス２３０にキャッシュされている場合には、キャッシュヒットを生成して、キャッシュデバイス２３０から（通信経路３０経由で）メモリシステム２０６に、参照データを提供することができる。一部の実装例では、通信経路３０が、逆方向の経路２０および１０に対応している。他方、参照されるデータがキャッシュデバイス２３０にキャッシュされていない場合には、キャッシュミスを生成して、参照データをメモリシステム２０６に、１以上の格納デバイス２２０から（通信経路６０を通じて）提供することができる。一部の実装例では、通信経路６０は、逆方向の経路５０および１０に対応している。コントローラ２１０はさらに、キャッシュデバイス２３０で受信したアドレス参照についてのキャッシュミスを（通信経路４０経由で）検知することができる。一部の実装例では、通信経路４０は、逆方向にされた経路２０に対応している。キャッシュミスを検知すると、コントローラ２１０はさらに、格納システム２００のあるブロックオフセット「Ｘ」に関するデータを（通信経路７０を介して）選択して、図５Ａから図５Ｂ、および図６Ａから図６Ｂを参照して後述する空間局所性メトリックの現在の値に従ってキャッシュデバイス２３０にキャッシュするよう構成されている。一部の実装例では、通信経路７０は、逆方向の経路５０および４０に対応している。
【００６３】
図３は、格納システムの空間局所性メトリックを生成して更新する方法３００の一例を示している。方法３００は、コントローラ２１０、キャッシュデバイス２３０、およびプロセッサ２０２（図２Ａを参照して上述した）の１以上を含むデータ処理装置により実行することができる。
【００６４】
３６０で、更新された空間局所性メトリックを出力して、キャッシュメモリにキャッシュするべき格納システムのデータを特定する。空間局所性メトリックは、データ処理装置が、後述するように少なくとも側面３１０−３５０を周期的に実行することで更新される。３６０に従って更新することができる空間局所性メトリックの例は、図２Ａから図２Ｃを参照して上述した。
【００６５】
３１０で、格納システムのアドレス参照を受信する。受信したアドレス参照が、特定数量のアドレス参照を含むアドレス参照シーケンスの最初のアドレスであると判断された場合、このシーケンスの最初のアドレスのブロックオフセットを記録する（３２０）。シーケンス内の特定の数量のアドレス参照は、「ｍ」で表し、例えばｍ＝１５に予め設定されている。しかし、シーケンス内の特定の数量のアドレス参照「ｍ」は、ソフトウェア／ファームウェアによる修正が可能である。
【００６６】
受信したアドレス参照がシーケンスで後続しているアドレス参照であると決定されると、後続するアドレス参照が、シーケンスの最初のアドレスについて記録されているブロックオフセットから一定の距離以内にあるかを判断することができる（３３０で）。アドレス空間の特定の距離は、「Ａ１」として示され、Ａ１＝６４ＫＢ、１２８ＫＢ、２５６ＫＢ等であってよい。判断の結果が肯定的である場合には（つまり、後続するアドレス参照が、シーケンスの最初のアドレスについて記録されているブロックオフセットから特定の距離「Ａ１」の範囲内にある場合）、シーケンスの最初のアドレスについて記録されているブロックオフセットから特定の距離「Ａ１」の範囲内にあるアドレス参照のカウントを増分する。カウントは「ｋ」と表し、整数値０≦ｋ≦ｍをとってよい。
【００６７】
３４０で、格納システムの空間局所性を、カウント「ｋ」およびシーケンス内の特定された数量「ｍ」のアドレス参照に基づいて得る。一部の実装例では、空間局所性を得ることには、シーケンスの最初のアドレスについて記録されているブロックオフセットから特定の距離の範囲内にあるシーケンス内のアドレス参照のカウントの分数「ｋ／ｍ」を決定することが含まれる。決定された分数は、不等式０≦ｋ／ｍ≦１を満たす。このようにして正規化された空間局所性の値は、参照のそれぞれ異なる数量「ｍ１」、「ｍ２」、…を有するアドレス参照の各シーケンスに基づいて決定される空間局所性「ｋ１／ｍ１」、「ｋ２／ｍ２」、…を比較するために利用することができる。例えば、ある格納システムに対する第１の空間局所性を、この格納システムのアドレスに対する１２個の参照を有する第１のシーケンスを利用することで、４であると決定することができる。後で、この格納システムに対する第２の空間局所性を、この格納システムのアドレスに対する３０個の参照を有する第２のシーケンスを利用することで、６であると決定することができる。またさらに後で、この格納システムに対する第３の空間局所性を、この格納システムのアドレスに対する６個の参照を有する第３のシーケンスを利用することで、３であると決定することができる。第１、第２、第３の空間局所性の元の値（raw value）を比較することが難しくなった場合には、正規化された値を利用すると、第３の空間局所性が３／６＝０．５０であり、第１の空間局所性４／１２＝０．３３より大きく、後者が第２の空間局所性６／３０＝０．２０より大きい、と簡単に判断することができる。
【００６８】
さらに、受信したアドレス参照は、受信したアドレス参照が、「ｍ」個のアドレス参照の前のシーケンスの中の最終（ｍ番目の）アドレス参照、および、後続する「ｍ」個のアドレス参照のうちの最初の（１番目の）アドレス参照の間のランダムなアドレス参照の数量「ｒ」のいずれかであると決定された場合には、空間局所性を取得しないようにすることであってもよい。乱数「ｒ」は、不等式０≦ｒ≦Ｎを満たすように選択される（Ｎは空間局所性を得ない最大処理数としてソフトウェア／ファームウェアで予め設定されてよい）。例えばｍ＝２０でありＮ＝１０である場合、先ず格納システムのアドレスの最初の２０個の参照を利用して空間局所性を取得して、次の４個の参照（２１−２３）は空間局所性の取得に利用せず、次の２０個の参照（２４−４３）は利用して、次の７個の参照（４４−５０）は利用せずに、次の２０個の参照（５１−７０）を利用して、次の１０個の参照（７１−８０）を利用せずに、次の２０個の参照（８１−１００）を利用して、次の２個の参照（１０１−１０２）は利用せずに、次の２０個の参照（１０３−１２２）を利用して、ゼロ個の参照を省いて、次の２０個の参照（１２３−１４２）を利用して、次の７個の参照（１４３−１４９）を利用せずに、といったように処理を行う。この例では、格納システムの空間局所性の連続する決定の間で乱数４、７、１０、２、０、７、…、（０と１０の間）の処理が省かれた。上述したランダムなサンプリングは、周期的に生じるアーチファクトの効果を低減することで、空間局所性メトリックの精度を高める効果を果たす。
【００６９】
３５０で、格納システムの空間局所性メトリックを、取得した空間局所性を、前に得た空間局所性と組み合わせて空間局所性メトリックにすることに少なくとも一部基づいて更新する。組み合わせには、取得した空間局所性を、前に得た空間局所性と、式１から式６のうち所定の１以上に従って重み付け合計することを含む。重みは、β（０＜β≦１）で表され、空間局所性メトリックの過去の値により空間局所性メトリックのインスタントバリューのバイアスを示すために選択することができる。例えば、０（ゼロ）に近い重みβは、空間局所性メトリックでは、過去の値の影響が大きくて、インスタントバリューが空間局所性メトリックに対して持つ貢献は小さいことを示している。別の例として、１に近い重みβは、空間局所性のインスタントバリューが空間局所性メトリックに対する影響が大きいことを示しており、過去の値は、空間局所性メトリックに対して小さな影響しか持たないことを示している。実際のところ、重みβ＝１のとき、過去の値は、空間局所性メトリックの値の計算には影響を及ぼさない。後者の場合には、格納システムの空間局所性メトリックは、格納システムの空間局所性と等しい。
【００７０】
３７０で、受信したアドレス参照のキャッシュミスを検知する。受信するアドレス参照は、格納システムにおける、あるブロックオフセットに対応している。３８０で、キャッシュミスの検知に呼応して、空間局所性メトリックの現在の値に従ってこのブロックオフセットに関するデータを選択的に決定して、選択的に決定されたデータをキャッシュメモリにキャッシュする。
【００７１】
図４Ａは、格納システムの空間局所性メトリックの現在の値に従って格納システムに格納されるデータをキャッシュする方法４００の一例の各側面を示す。方法４００は、３７０でキャッシュミスを検知することに呼応してデータをキャッシュする方法３００と組み合わせることができる。方法４００はさらに、図２Ａを参照して記載したコントローラ２１０、キャッシュデバイス２３０、およびプロセッサ２０２の１以上を含むデータ処理装置により実行することができる。加えて、方法４００は、図２Ａから図２Ｃを参照して上述した空間局所性メトリックのいずれにも適用することができる。
【００７２】
３７０で、格納システムのアドレスについて受信された参照についてのキャッシュミスを検知する。図４Ｂは、このキャッシュミスに対応する格納システム２４０のアドレスに関するブロックオフセット「Ｘ」を示す。
【００７３】
キャッシュミスを検知すると、空間局所性メトリックの見積もりは、４１０で、第１の値と、第１の値より大きい第２の値との間の空間局所性メトリックの現在の値となる。空間局所性メトリックのこの値の範囲は、ソフトウェア／ファームウェアで、例えば空間局所性メトリックの過去の値の２５パーセントから７５パーセントの範囲といった特定の区間に対応するよう特定することができる。別の例では、空間局所性値の特定の区間を、過去の値の５パーセントから９５パーセントの間に特定することができる。一部の実装例では、過去の値を格納システムで保持してもよい。一部の実装例では、過去の値は、格納システムの外部に（例えばホストシステム２０１／２０１'に）保持することができる。空間局所性のＮ個の過去の計測値（例えばＮ＝２５０）のうちｋ番目のパーセント（例えばｋ＝２５）を計算するために、Ｎ個の過去の計測値の最小の値から最大の値を先ずソートする。ｋ番目のパーセントは、ソートされたＮ個の計測値のうちのｋ＊Ｎ／１００番目にあたる値に相当する。この場合、空間局所性メトリックの過去の値の２５パーセントが、２００個のソートされた空間局所性の計測値の５０番目（２５＊２００／１００）の空間局所性計測値の値に相当する。同様に、空間局所性メトリックの過去の値の５パーセントは、２００個のソートされた空間局所性の計測値の１０番目（５＊２００／１００）の空間局所性計測値の値に相当する。他のパーセントの値も、このようにして計算され、例えば、４１０での見積もりとの関連で記載される特定の区間の上限および下限の設定に利用することができる。
【００７４】
４２０で、４１０の見積もり結果に応じて、あるブロックオフセット「Ｘ」に隣接する連続メモリから特定のデータ量を含むように、キャッシュメモリにキャッシュするデータを選択的に決定する。特定のデータ量は、図４Ｂの「Δ」で表されている。一部の実装例では、特定のデータ量「Δ」は、格納システム２４０の空間局所性を決定するために利用されるメモリサイズ「Ａ１」に関していてよい。例えば、特定のデータ量「Δ」は、メモリサイズ「Ａ１」の倍数であったり、これに等しかったり、これの分数であってよい。例えば、「Ｘ」に対応するキャッシュミスを検知して、空間局所性メトリックのインスタントバリューが過去の値の５−９５パーセントの間にあると見積もられると、空間局所性メトリックが、メモリサイズＡ１＝６４ＫＢに基づいて決定され、キャッシュされるべきデータ量が、Δ＝Ａ１＝６４ＫＢとなるよう選択的に決定され、キャッシュされるデータは、メモリ区間（Ｘ−３２ＫＢ、Ｘ＋３２ＫＢ）から選択される。
【００７５】
キャッシュミスを検知すると、４３０の空間局所性メトリックの見積もり結果は、第２の値より空間局所性メトリックの現在の値が大きい、となる。空間局所性メトリックのこの大きなインスタントバリューは、ブロックオフセット「Ｘ」に隣接するアドレスが（これは、キャッシュミスに対応する格納システム２４０のアドレスに関連付けられている）、近い将来参照される（つまり後続する「ｍ」個の読み書き処理中に参照される）確率が高いことを示す。
【００７６】
４４０では、４３０の見積もり結果に応じて、ブロックオフセット「Ｘ」に隣接する連続メモリからの特定のデータ量「Δ」以上のデータを、キャッシュメモリにキャッシュするデータが含むよう、選択的に決定する。一部の実装例では、空間局所性メトリックの現在の値が第２の値より大きい場合、キャッシュメモリへのキャッシュ用に選択的に決定するデータは、ブロックオフセット「Ｘ」に隣接する連続メモリからの特定の量のデータ「Δ」の二倍を含む（図４Ｂ参照）。例えば、「Ｘ」に対応するキャッシュミスを検知して、空間局所性メトリックのインスタントバリューが、過去の値の９５パーセントより大きく見積もられた場合、特定の量のデータΔ＝６４ＫＢとなり、キャッシュするデータ量は、２Δ＝１２８ＫＢとして選択的に決定され、キャッシュされるデータはメモリ区間（Ｘ−６４ＫＢ、Ｘ＋６４ＫＢ）から選択される。
【００７７】
キャッシュミスを検知すると、空間局所性メトリックの見積もりは４５０で、第１の値より空間局所性メトリックの現在の値が小さい、となる。空間局所性メトリックのインスタントバリューがこのように小さいということは、ブロックオフセット「Ｘ」に隣接するアドレスが（これは、キャッシュミスに対応する格納システム２４０のアドレスに関連付けられている）、近い将来参照される（つまり、「ｍ」個の読み書き処理中に参照される）確率が低いことを示す。
【００７８】
４６０で、キャッシュメモリにキャッシュするデータを、４５０の見積もり結果に応じて、ブロックオフセット「Ｘ」に隣接する連続メモリからの特定のデータ量「Δ」未満のデータを含むように選択的に決定する。一部の実装例では、空間局所性メトリックの現在の値が第１の値より小さい場合、キャッシュメモリへのキャッシュ用に選択的に決定するデータは０となる。例えば、「Ｘ」に対応するキャッシュミスを検知して、空間局所性メトリックのインスタントバリューが、過去の値の５パーセントより小さく見積もられた場合、特定の量のデータΔ＝６４ＫＢとなり、キャッシュするデータ量を、選択的に０（ゼロ）に選択する。
【００７９】
図５Ａは、格納システムの短期および長期空間局所性メトリックのそれぞれの現在の値に従って格納システムに格納されるデータをキャッシュする別の方法５００の例の各側面を示す。３７０でキャッシュミスを検知すると、方法５００を、データをキャッシュする方法３００と組み合わせることができる。方法５００は、さらに、図２Ａを参照して上述したコントローラ２１０、キャッシュデバイス２３０、およびプロセッサ２０２のうち１以上を含むデータ処理装置により実行することもできる。
【００８０】
上述したように、空間局所性の短距離成分は、特定のメモリサイズ「Ａ１」で、シーケンスの最初のアドレスのブロックオフセット「Ｘｎ」を中心とする特定のメモリサイズ「Ａ１」の区間内の「ｍ」個のアドレス参照のシーケンス内の「ｋ１」カウントを除算した、アドレス参照の分数「ｋ１／ｍ」として決定することができる。空間局所性の長距離成分は、別の他の特定のメモリサイズ「Ａ２」（Ａ１＜Ａ２）で、シーケンスの最初のアドレスのブロックオフセット「Ｘｎ」を中心とする別の特定のメモリサイズ「Ａ２」の区間内の「ｍ」個のアドレス参照のシーケンス内の「ｋ２」カウントを除算した、アドレス参照の分数「ｋ２／ｍ」として決定することができる。
【００８１】
一部の実装例では、空間局所性の短距離成分は、シーケンスの最初のアドレスのブロックオフセット「Ｘｎ」を中心とする特定のメモリサイズ「Ａ１」の区間内の「ｍ」個のアドレス参照のシーケンス内の「ｋ１」カウントとして決定することができ、空間局所性の長短距離成分は、シーケンスの最初のアドレスのブロックオフセット「Ｘｎ」を中心とする特定のメモリサイズ「Ａ１」の区間内ではなくて、シーケンスの最初のアドレスのブロックオフセット「Ｘｎ」を中心とする別の特定のメモリサイズ「Ａ２」の区間内の「ｍ」個のアドレス参照のシーケンス内の別の「ｋ２」カウントとして、決定することができる。
【００８２】
さらに、短距離空間局所性メトリックＳＡ１は、式１、３、または４の空間局所性ｓ（Ａ１、ｍ；ｎ）について決定される短距離成分に関しており、長距離空間局所性メトリックＳＡ２は、式２、５、または６の空間局所性ｓ（Ａ２、ｍ；ｎ）について決定される短距離成分に関している。
【００８３】
図５Ａに戻ると３７０で、格納システムのアドレスについて受信した参照におけるキャッシュミスを検知する。図５Ｂは、キャッシュミスに対応する格納システム２４０のアドレスに関連するブロックオフセット「Ｘ」を示す。加えて、図５Ｂは、ブロックオフセット「Ｘ」を中心とするメモリサイズＡ１の区間と、ブロックオフセット「Ｘ」を中心とする別のメモリサイズＡ２の区間を示しており、メモリサイズＡ１およびＡ２は、格納システム２４０の短距離および長距離空間局所性メトリックそれぞれに対応している。
【００８４】
キャッシュミスを検知すると、短距離および長距離空間局所性メトリックの見積もりは、５１０で、長距離空間局所性の現在の値よりも、短距離空間局所メトリックの現在の値が大きい、となる。このように、短距離空間局所メトリックインスタントバリューが大きいということは、ブロックオフセット「Ｘ」を中心とするメモリサイズＡ１の区間内のアドレスへの参照の空間密度が大きいことを示しており、逆に、長距離空間局所メトリックインスタントバリューが小さい場合には、ブロックオフセット「Ｘ」を中心とするメモリサイズＡ２の区間内のアドレスへの参照の空間密度が小さいことを示している。メモリサイズＡ１の区間および他のメモリサイズＡ２の区間は、共通の中心Ｘを有しているので、見積もり５１０の結果では、端部（Ｘ−１／２Ａ２、Ｘ−１／２Ａ１）と端部（Ｘ＋１／２Ａ１、Ｘ＋１／２Ａ２）との間のアドレスの参照数は、他のメモリサイズＡ２の区間の中央部分（Ｘ−１／２Ａ１、Ｘ＋１／２Ａ１）のアドレスの参照数より必ず小さくなるはずである。
【００８５】
この結果５２０で、キャッシュメモリへのキャッシュ用のデータは、ブロックオフセット「Ｘ」を中心とするメモリサイズＡ１を有する区間内のアドレスを有するように選択される。図４Ａおよび図４Ｂを参照して上述したように、プリフェッチされたデータの量は、メトリックを決めるときに利用されたサイズ（例えばＡ１）と同じであってよいが、同じではなくてもよい。例えば、「Ｘ」に対応するキャッシュミスを検知して、短距離空間局所性メトリックのインスタントバリューが、長距離空間局所性メトリックのインスタントバリューより大きく見積もられ、且つ、短距離空間局所性メトリックに対応するメモリＡ１＝６４ＫＢである場合、キャッシュするデータは、メモリ区間（Ｘ−３２ＫＢ、Ｋ＋３２ＫＢ）から選択される。
【００８６】
さらにキャッシュミスを検知すると、短距離および長距離空間局所性メトリックの５３０における見積もりは、短距離空間局所メトリックの現在の値が、長距離空間局所性の現在の値と略等しい、となる。空間局所メトリック同士が略等しい場合というのは、２つのメトリックの値が、メトリックの計測において生じるノイズ以下である場合に生じる（例えばノイズは、計測繰り返しによって生じる）。短距離空間局所性メトリックおよび長距離空間局所性メトリックが実質的に等しい、ということは、ブロックオフセット「Ｘ」を中心とするメモリサイズ区間Ａ１の範囲内のアドレスへの参照の空間密度が、ブロックオフセット「Ｘ」を中心とするメモリサイズの他の区間Ａ２の範囲内のアドレスへの参照の空間密度と、実質的に等しいことを示している。メモリサイズＡ１の区間および他のメモリサイズＡ２の区間は、共通の中心Ｘを有しているために、見積もり５３０の結果では、端部（Ｘ−１／２Ａ２、Ｘ−１／２Ａ１）と端部（Ｘ＋１／２Ａ１、Ｘ＋１／２Ａ２）との間のアドレスの参照数は、他のメモリサイズＡ２の区間の中心部分（Ｘ−１／２Ａ１、Ｘ＋１／２Ａ１）内のアドレスの参照数より必ず小さくなるはずである。
【００８７】
この結果５４０で、キャッシュメモリにキャッシュするデータは、ブロックオフセット「Ｘ」を中心とするメモリサイズＡ２を有する区間内のいずれかのアドレスを有するように選択される。例えば、「Ｘ」に対応するキャッシュミスを検知して、短距離空間局所性メトリックのインスタントバリューが、長距離空間局所性メトリックのインスタントバリューに略等しいと見積もられ、さらに、長距離局所性メトリックに対応するメモリサイズが、Ａ２＝１２８ＫＢである場合に、キャッシュするデータをメモリ区間（Ｘ−６４ＫＢ，Ｘ＋６４ＫＢ）から選択される。
【００８８】
さらに、キャッシュミスを検知すると、短距離および長距離空間局所性メトリックの５５０における見積もりは、長距離空間局所性の現在の値よりも、短距離空間局所メトリックの現在の値のほうが小さい、となる。短距離空間局所メトリックインスタントバリューが小さいということは、ブロックオフセット「Ｘ」を中心とするメモリサイズＡ１の区間内のアドレスへの参照の空間密度が大きいことを示しており、一方で、長距離空間局所メトリックのインスタントバリューが大きいということは、ブロックオフセット「Ｘ」を中心とするメモリサイズＡ２の区間内のアドレスへの参照の空間密度が小さいことを示している。メモリサイズＡ１の区間および他のメモリサイズＡ２の区間は、共通の中心Ｘを有しているために、見積もり５５０の結果では、端部（Ｘ−１／２Ａ２、Ｘ−１／２Ａ１）と端部（Ｘ＋１／２Ａ１、Ｘ＋１／２Ａ２）との間のアドレスの参照数は、他のメモリサイズＡ２の区間の（Ｘ−１／２Ａ１、Ｘ＋１／２Ａ１）内のアドレスの参照数より必ず小さくなるはずである。
【００８９】
この結果５６０で、キャッシュメモリにキャッシュするデータは、ブロックオフセット「Ｘ」を中心とするメモリサイズＡ２の他の区間の端部（Ｘ−１／２Ａ２、Ｘ−１／２Ａ１）と端部（Ｘ＋１／２Ａ１、Ｘ＋１／２Ａ２）との間のアドレスを有するように選択される。例えば、「Ｘ」に対応するキャッシュミスを検知して、短距離空間局所性メトリックのインスタントバリューが、長距離空間局所性メトリックのインスタントバリューより短いと見積もられ、且つ、短距離局所性メトリックおよび長距離局所性メトリックに対応するメモリサイズがそれぞれ、Ａ１＝６４ＫＢ、Ａ２＝１２８ＫＢである場合に、キャッシュするデータは、メモリ区間（Ｘ−６４ＫＢ，Ｘ−３２ＫＢ）および（Ｘ＋３２ＫＢ，Ｘ＋６４ＫＢ）から選択される。
【００９０】
図６Ａは、格納データシステムに格納されているデータをキャッシュする方法６００の別の例を示す。方法６００は、例えばシステム２００において、（ｉ）キャッシュミスを検知してプリフェッチされるデータ量を決定して、（ｉｉ）検知したキャッシュミスに関するアドレス位置に対して、決定した量をプリフェッチする格納システムの領域を選択するために実装することができる。
【００９１】
６３０で、データ格納システムへのアクセスの空間分布の測値を、（コントローラ２１０により）、データ格納システムへの別個の複数の群のアクセスに基づいて決定する。６３０で実行される空間分布の測値の決定の実装の一例を、以下に、図６Ｄを参照して記載する。さらに、図１Ａから図１Ｈが、空間分布の表現を示す例示である。例えば、空間分布は、格納システムのアドレスへの参照の１以上の空間局所性（例えば１５０）により表すことができ、空間分布の測値は、１以上の空間局所性にそれぞれ対応している空間局所性メトリック（例えば１１０）によって表すことができる。
【００９２】
６４０で、データ格納システムに利用するキャッシュポリシーを、（例えばコントローラ２１０によって）、空間分布について決定された測値に基づいて調節する。６４０で実行したキャッシュポリシーの調節の実装例については、図６Ｃおよび図６Ｄを参照して以下で説明する。
【００９３】
図６Ｂは、方法６００の所定の側面を示す。６１０で、データ格納システムへの異なる参照アクセスに基づいて、データ格納システムへの別個のアクセス群を識別する（コントローラ２１０により）。例えば、別個のアクセス群は、データ格納システムのアドレスへの２以上の参照シーケンスに基づいて識別することができ、各シーケンスの第１の参照が、それぞれ前のシーケンス（例えば、図１Ｂおよび図１Ｄに示す格納媒体１４０のＸｎ、Ｘｎ＋１，…）の第１の参照に関連付けられたアドレスとは異なるようにされている。このようにして識別された別個のアクセス群は、例えば、２以上のシーケンスＸｎ、Ｘｎ＋１，…それぞれの第１の参照の回数に対応する計測回数の倍数（multiple measurement times）で空間分布の測値を決定するために利用することができる。
【００９４】
データ格納システムへの異なる参照アクセスに基づいてデータ格納システムへの別個のアクセス群を識別することは、６１２で、（例えばコントローラ２１０によって）、乱数生成に基づいてデータ格納システムへの異なる参照アクセスを決定することを含んでよい。例えば、前述したデータ格納システムのアドレスへの２以上の参照シーケンスは、各シーケンスＸｎ、Ｘｎ＋１，…の第１の参照が、前のシーケンスの最後の参照の後で乱数の参照が終わると識別されるようにすることができる。このようなランダムなサンプリングによって、前述した複数の計測時間において計測された空間分布の計測精度を上げることができるようになる。
【００９５】
図６Ｃは、方法６００の別の所定の側面を示す。特に、６４０で行われるキャッシュポリシーの調節には、６４２で、（コントローラ２１０によって）図４Ｂに示すようにデータ格納システムからプリフェッチされるデータ量を修正することが含まれてよい。例えば、空間分布（例えば１１０）の測値が所定の閾値を超えていると、所定の量のデータ（例えば２Δ）を、キャッシュミスを生成した参照に関するアドレス「Ｘ」に隣接したデータ格納システムの領域からキャッシュする。しかし、空間分布（例えば１１０）の測値が所定の閾値を超えていない場合には、別の所定の量のデータ（例えばΔ）を同じ領域からキャッシュする。
【００９６】
図６Ｄは、方法６００の別の所定の側面を示す。６２０で、データ格納システムへの別個のアクセス群を、（例えばコントローラ２１０により）図１Ｄに示すように、例えば格納媒体１４０のアドレスＸｎに対応するものと同じ参照アクセスに基づいて識別する。一部の実装例では、別個のアクセス群は、データ格納システム１４０のアドレスＸｎと関連する第１の参照を有するデータ格納システムのアドレスへの参照シーケンスに基づいて識別することができる。このようにして識別された別個のアクセス群は、例えば、（アドレスＸｎに関連付けられている）第１の参照の時間に対応する計測時間の空間分布（例えば１１２、１１４）のそれぞれの空間成分の測値を決定するために利用することができる。空間分布（例えば１１２、１１４）の空間成分は、（例えばコントローラ２１０によって）、シーケンスの第１の参照に対応するアドレスに対するそれぞれの距離に基づいて（例えば、図１Ｄに示すアドレスＸｎの周りの距離Ａ１およびＡ２を参照）決定することができる。
【００９７】
一部の実装例では、図１Ａを参照して詳述したように、別個のアクセス群を、データ格納システムのアドレスへの２以上の参照シーケンスに基づいて（コントローラ２１０により）識別することができ、これら２以上のシーケンスの各々が、（ｉ）データ格納システムのアドレスに関連する（例えばアドレスＸｎに関連する）共通の第１の参照と、（ｉｉ）異なる数の参照Ｎ１およびＮ２とを有している。２以上のシーケンスに基づいて識別した別個のアクセス群はそれぞれ、例えば、第１の参照に対応する（例えばアドレスＸｎに関連付けられている）計測時間の空間分布の時間成分それぞれの測値の決定に利用することができる。時間成分は、２以上の参照シーケンスに対応するそれぞれ異なる数の参照Ｎ１およびＮ２に基づいて決定することができる。
【００９８】
データ格納システムへの別個のアクセス群は、（コントローラ２１０により）、２以上の異なる空間範囲に基づいて（例えば図１Ｄに示すアドレスＸｎの周りの距離Ａ１およびＡ２）、データ格納システムへの２つの別個のアクセス群を識別することを含む（６２２で）。例えば、２つのアクセス群を、データ格納システムのアドレスＸｎに関する第１の参照を有する参照シーケンスに基づいて識別することができる。このようにして識別した２つのアクセス群は、例えば、第１の参照の時間に対応する計測時間（例えばアドレスＸｎに関連している）の短距離および長距離空間局所性（例えば１１２、１１４）を決定するために利用することができる。短距離および長距離空間局所性メトリック（例えば１１２、１１４）は、（例えばコントローラ２１０により）、シーケンスの第１の参照と関連するアドレスに対するそれぞれ短距離および長距離に基づいて（例えば、図１Ｄに示すアドレスＸｎの周りの距離Ａ１およびＡ２を参照）決定することができる。
【００９９】
６３０で行われる空間分布の測値の決定は、６３２で、（例えばコントローラ２１０により）第１数を第２数と比較することを含み、この第１数は２つの別個の群のうちの１つに対応しており、第２数が、２つの別個の群のうちの別の群に対応している。一部の実装例では、６２２で決定された短距離および長距離空間局所性メトリック（例えば１１２、１１４）を比較して、例えばデータ格納システムのアドレス（例えばＸ）に関するキャッシュミスが検知された時点におけるデータ格納システムへのアクセスの現在の空間分布に関する情報を取得することができる。
【０１００】
６４０で行われるキャッシュポリシーの調節には、６４４で、第１数と第２数との比較に基づいてデータ格納システム（例えば図５Ｂに示すようなもの）のそれぞれ異なる領域からデータを（例えばコントローラ２１０により）選択的にプリフェッチすることが含まれてよい。一部の実装例では、キャッシュミスを検知すると、例えば（コントローラ２１０等により）データを、検知されたキャッシュミスＸに関連するアドレスに関して選択された領域から、短距離および長距離空間局所性メトリックの現在の値同士（例えば１１２、１１４）の比較に基づいて、プリフェッチするためのアドレス空間を選択することによって、キャッシュポリシーの調節を行ってよい。
【０１０１】
幾つかの実施形態を記載してきたが、様々な変形例も可能である。記載した主題は、本明細書に記載した機能的な処理も含み、記載してきた処理を１以上のデータ処理装置に実行させることの出来るプログラム（例えば、メモリデバイス、格納デバイス、機械可読格納基板、その他の物理的、機械可読媒体、またはこれらの１以上の組み合わせを含むコンピュータ可読媒体に符号化されるプログラム）を潜在的に含む電子回路、コンピュータハードウェア、ファームウェア、ソフトウェア、これらの組み合わせ（例えば、本明細書で開示した構造手段、その構造的な均等物）での実装が可能である。
【０１０２】
「データ処理装置」という用語は、例えばプログラム可能プロセッサ、コンピュータ、または複数のプロセッサまたはコンピュータを含む、データを処理する全ての装置、デバイス、及び機械を含む概念である。装置は、ハードウェアに加えて、対象となるコンピュータプログラムに実行環境を提供するコード（例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはこれらの１以上の組み合わせ）を含むことができる。
【０１０３】
プログラム（さらにはコンピュータプログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコード）は、コンパイラ型言語、またはインタープリタ型言語、宣言型言語または手続き型言語等の所定のプログラミング言語の形態であってよく、独立型プログラム、モジュール、コンポーネント、サブルーチン、その他、コンピュータ環境での利用に適したその他のユニット等の所定の形態で利用することができる。プログラムは必ずしもファイルシステムのファイルに対応していなくてもよい。プログラムは、他のプログラムまたはデータ（例えば、マークアップ言語文書に格納される１以上のスクリプト）を保持するファイルの一部として格納することもできるし、対象となるプログラムに特化した単一のファイルに格納することもできるし、複数の調節されたファイル（例えば、１以上のモジュール、サブプログラム、またはコードの部分を格納するファイル）に格納することもできる。プログラムは、１つのサイトに配置されてもよいし、または複数のサイトに分散され通信ネットワークで接続されていてよい１つまたは複数のコンピュータで実行することができる。
【０１０４】
本明細書は特定の詳細を含むが、これらは特定の明細書に固有の特徴を説明したにすぎず、特許請求の範囲を限定するものとして捉えられるべきではない。本明細書で記載する、特定の実施形態で説明される特定の特徴は、単一の実施形態で組み合わせて実装されてもよい。逆に、単一の実施形態で説明された様々な特徴を、複数の実施形態で別個に、または適宜サブコンビネーションとして実装してもよい。さらに、上述した特徴は、組み合わせて時刻されると記載されていたり、最初はそのように請求されていたとしても、請求される組み合わせの１以上の特徴を、場合によっては取り除いたり、請求されている組み合わせを、サブコンビネーションとしたり、サブコンビネーションの変形例としたりすることもできる。
【０１０５】
同様に、図面において処理は特定の順序で示されているが、これは、これらの処理が示されている特定の順序で、または順番で実行される、という限定の明示として捉えられるべきではなく、さらには、所望の結果を生じるために全ての処理を実行せねばならない、という限定の明示として捉えられるべきでもない。場合によっては、マルチタスクとしたり、並行処理したりすると功を奏する場合もある。さらに、実施形態で説明した様々なシステムコンポーネントを分離することは、全ての実施系知アにおいてこの分離が必要であるとの明示として捉えられるべきでもない。
【０１０６】
他の実施形態であっても、以下の特許請求項の範囲内に含まれる場合がある。
【図１Ａ】
2013520756.tif 000003
【図１Ｂ】
2013520756.tif 000004
【図１Ｃ】
2013520756.tif 000005
【図１Ｄ】
2013520756.tif 000006
【図１Ｅ】
2013520756.tif 000007
【図１Ｆ】
2013520756.tif 000008
【図１Ｇ】
2013520756.tif 000009
【図１Ｈ】
2013520756.tif 000010
【図２Ａ】
2013520756.tif 000011
【図２Ｂ】
2013520756.tif 000012
【図２Ｃ】
2013520756.tif 000013
【図３】
2013520756.tif 000014
【図４Ａ】
2013520756.tif 000015
【図４Ｂ】
2013520756.tif 000016
【図５Ａ】
2013520756.tif 000017
【図５Ｂ】
2013520756.tif 000018
【図６Ａ】
2013520756.tif 000019
【図６Ｂ】
2013520756.tif 000020
【図６Ｃ】
2013520756.tif 000021
【図６Ｄ】
2013520756.tif 000022
【国際調査報告】
2013520756.tif 000023
2013520756.tif 000024