(57)【要約】  ＣＡＴＢ（Ｃｏｎｓｔａｎｔ  Ａｃｃｅｓｓ  Ｔｉｍｅ  Ｂｏｕｎｄｅｄ）キャッシュにおいて、該キャッシュのライン数より少ない該キャッシュの第１の個数の未割当てラインをピンドデータのために確保し、前記キャッシュにデータをピンドデータとして挿入する必要がある場合、ピンドデータ用に確保された前記ラインからあるラインを選択し、前記データを該ラインに格納し、該ラインを前記ＣＡＴＢキャッシュの検索グループに挿入する。
2007500398.tif 000002
【特許請求の範囲】
【請求項１】
ＣＡＴＢ（Ｃｏｎｓｔａｎｔ  Ａｃｃｅｓｓ  Ｔｉｍｅ  Ｂｏｕｎｄｅｄ）キャッシュにおける方法であって、
該キャッシュのライン数より少ない該キャッシュの第１の個数の未割当てラインをピンドデータのために確保するステップと、
前記キャッシュにデータをピンドデータとして挿入する必要がある場合、ピンドデータ用に確保された前記ラインからあるラインを選択し、前記データを該ラインに格納し、該ラインを前記ＣＡＴＢキャッシュの検索グループに挿入するステップと、
から構成されることを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
前記キャッシュの各ラインは、不揮発性メモリに格納されることを特徴とする方法。
【請求項３】
請求項２記載の方法であって、さらに、
復元の第１段階において、前記キャッシュの各ラインに対し、該ラインが割り当てられているか判断し、該ラインが割当て済みの場合、該ラインを前記キャッシュの検索グループに挿入し、該ラインが未割当ての場合、該ラインをフリーライン群に挿入し、
復元の第２段階において、各検索グループに対し、該検索グループのピンドラインの個数を判断し、前記フリーライン群からの少なくとも１つのラインを少なくとも１つのピンドラインを有する各検索グループに追加することによって、
前記キャッシュへの電力ロスに続く電力アップにより前記キャッシュの構成を復元するステップを有することを特徴とする方法。
【請求項４】
請求項３記載の方法であって、
前記キャッシュは、プロセッサベースシステムのディスクキャッシュであることを特徴とする方法。
【請求項５】
請求項１記載の方法であって、
前記ラインを前記キャッシュの検索グループに挿入するステップはさらに、該ラインが割当て済みであることを示し、該ラインがピンドであることを示し、該ラインのタグを用いて該ラインを前記キャッシュの検索グループにマッピングすることを特徴とする方法。
【請求項６】
請求項５記載の方法であって、
前記ＣＡＴＢキャッシュは、群連想キャッシュとして実現され、
前記キャッシュの各検索グループは、前記キャッシュのある群であり、
前記ラインを前記キャッシュの検索グループに挿入するステップはさらに、前記データのアドレスを前記ラインのタグとして利用し、前記タグを前記キャッシュのある群にマッピングするため、前記タグと前記キャッシュ内の群の個数（Ｎ）との間で法演算（タグ（ＭＯＤ）Ｎ）を実行し、前記ラインのタグに基づき検索を実行し、前記ラインを前記群を表す動的データ構造に挿入する、
ことを特徴とする方法。
【請求項７】
請求項６記載の方法であって、
前記ラインがピンドであることを示すステップはさらに、前記ラインがピンドであることを示すため、前記ラインに係るメタデータを変更することを特徴とする方法。
【請求項８】
自然数Ｎに対し、Ｎウェイ群連想不揮発性ディスクキャッシュにおける方法であって、
ピンドデータ用に所定数のラインを確保し、該ラインをピンドデータ用のライン群に構成するステップと、
前記キャッシュの残りのラインを前記キャッシュのＮ個の群を表すため、ほぼ同一サイズのＮ個の動的データ構造に配分するステップと、
前記キャッシュにデータをピンドデータとして挿入する場合、前記データを前記ピンドデータ用のライン群からのあるラインに挿入し、前記ラインに係るメタデータを変更することにより、前記ラインを割当て済みにマークし、前記ラインに係るタグに基づくマッピングを用いて前記ラインが属する群を決定し、前記ラインを前記ピンドデータ用のライン群から削除し、前記ラインを前記群に追加するステップと、
から構成されることを特徴とする方法。
【請求項９】
請求項８記載の方法であって、さらに、
復元の第１段階において、前記キャッシュの各ラインに対し、該ラインが割当て済みか判断し、該ラインが割当て済みの場合、該ラインに係るタグに基づくマッピングを用いて、該ラインを前記キャッシュのある群に挿入し、該ラインが未割当ての場合、該ラインを未割当てライン群に挿入し、
復元の第２段階において、前記キャッシュの各群に対し、該群の各ラインに係るメタデータを用いて、該群のピンドライン数を決定し、各群の非ピンドライン数がほぼ同一となるように、前記未割当てライン群から少なくとも１つのピンドラインを有する各群に１以上のラインを移動させることにより、
前記キャッシュへの電力ロスに続く電力アップに対し前記キャッシュの構成を復元するステップを有することを特徴とする方法。
【請求項１０】
不揮発性メモリにより実現されるＮウェイ群連想キャッシュと、
ピンドデータ用のライン群を格納するための前記不揮発性メモリのピンドデータ部分と、
ピンドデータを前記ピンドデータ用のライン群からのあるラインに挿入し、該ラインに係るメタデータを変更することにより、該ラインを割当て済みにマークし、該ラインに係るタグに基づくマッピングを用いて、該ラインが属する群を判断し、前記ピンドデータ用のライン群から前記ラインを削除し、該ラインを前記群に追加するピンドデータ挿入モジュールと、
から構成されることを特徴とする装置。
【請求項１１】
請求項１０記載の装置であって、さらに、
前記キャッシュに電力を供給する電源と、
復元の第１段階において、前記キャッシュの各ラインに対し、該ラインが割当て済みか判断し、該ラインが割当て済みの場合、該ラインに係るタグに基づくマッピングを用いて、該ラインを前記キャッシュのある群に挿入し、該ラインが未割当ての場合、該ラインを未割当てライン群に挿入し、
復元の第２段階において、前記キャッシュの各群に対し、該群の各ラインに係るメタデータを用いて、該群のピンドライン数を決定し、各群の非ピンドライン数がほぼ同一となるように、前記未割当てライン群から少なくとも１つのピンドラインを有する各群に１以上のラインを移動させることにより、
前記電源から前記キャッシュへの電力ロスに続く電力アップに対し前記キャッシュの構成を復元する復元モジュールと、
を有することを特徴とする装置。
【請求項１２】
プロセッサと、
前記プロセッサに通信可能に接続されるディスクと、
前記プロセッサに通信可能に接続される不揮発性バッテリバックアップＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）により実現されるＮウェイ群連想キャッシュと、
ピンドデータ用のライン群を格納するための前記不揮発性フラッシュメモリのピンドデータ部分と、
ピンドデータを前記ピンドデータ用のライン群からのあるラインに挿入し、該ラインに係るメタデータを変更することにより、該ラインを割当て済みにマークし、該ラインに係るタグに基づくマッピングを用いて、該ラインが属する群を判断し、前記ピンドデータ用のライン群から前記ラインを削除し、該ラインを前記群に追加するピンドデータ挿入モジュールと、
から構成されることを特徴とするシステム。
【請求項１３】
マシーンによるアクセス時に、前記マシーンに請求項１記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項１４】
請求項１３記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項２記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項１５】
請求項１４記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項３記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項１６】
請求項１５記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項４記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項１７】
請求項１３記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項５記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項１８】
請求項１７記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項６記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項１９】
請求項１８記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項７記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項２０】
マシーンによるアクセス時に、前記マシーンに請求項８記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項２１】
請求項２０記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項９記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項２２】
ＣＡＴＢ（Ｃｏｎｓｔａｎｔ  Ａｃｃｅｓｓ  Ｔｉｍｅ  Ｂｏｕｎｄｅｄ）キャッシュにおける方法であって、
要素を動的に挿入及び削除する機能により前記ＣＡＴＢキャッシュの検索グループを初期化するステップと、
要素を前記ＣＡＴＢの検索グループに動的に挿入するステップと、
から構成されることを特徴とする方法。
【請求項２３】
請求項２２記載の方法であって、さらに、
要素の第１識別子を受け付けるステップと、
前記第１識別子を用いて前記ＣＡＴＢキャッシュの検索グループの第２識別子を計算するステップと、
前記第１識別子に一致する要素を配置するため、前記検索グループを探索するステップと、
を有することを特徴とする方法。
【請求項２４】
請求項２３記載の方法であって、
前記検索グループは、リンクリストとして実現されることを特徴とする方法。
【請求項２５】
マシーンによるアクセス時に、前記マシーンに請求項２２記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項２６】
請求項２５記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項２３記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【請求項２７】
請求項２５記載のマシーン可読媒体であって、さらに、マシーンによるアクセス時に、前記マシーンに請求項２４記載の方法を実行させるデータを格納することを特徴とするマシーン可読媒体。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［背景］
キャッシュ処理は、小さく高速な記憶装置を用いて、より大きな低速の記憶装置に格納されているデータへのアクセスを高速化する周知の技術である。キャッシュ処理の典型的な応用は、ディスクアクセス技術に見出される。ハードディスクドライブ上のデータにアクセスするプロセッサベースシステムは、例えば、ドライブよりアクセス時間の短いソリッドステートメモリにより実現されるキャッシュが、ドライブとプロセッサの間に介在される場合には、パフォーマンスの向上を実現するかもしれない。当業者には周知のように、このようなキャッシュは、システムによりアクセスされるディスクからのデータにより占有され、同一データへの以降のアクセスはディスクの代わりにキャッシュに対して行われ、これにより、パフォーマンスを高速化することができる。キャッシュ処理を利用することにより、例えば、キャッシュへのデータ書き込み時などのメイン記憶装置とのキャッシュコンシスタンシの要求などのシステム構成に対する制約と共に、キャッシュにはないデータ要素にデータアクセスがなされ、そして当該キャッシュがたまたまフル状態であったとき、キャッシュのどの部分が置き換えられるべきか（キャッシュ置換方針）などを指示するパフォーマンスベースの制約が課される。
【０００２】
キャッシュ、具体的にはディスクキャッシュのための周知の構成は、Ｎウェイ群連想キャッシュ（Ｎ−ｗａｙ  ｓｅｔ  ａｓｓｏｃｉａｔｉｖｅ  ｃａｃｈｅ）である（ただし、Ｎはある非ゼロの自然数である）。このような構成では、キャッシュは、各アレイが一群を表すＮアレイのキャッシュラインとして実現されてもよい。ここで、各群は構成要素としてデータ要素のみを有するか、あるいは単に容易に計算されるマッピング関数に基づき当該群にマッピングされるアドレスを有するディスクからの要素を有する。従って、ディスクキャッシュの場合、ディスク上の任意の要素は、例えば、ディスク上の要素のアドレス、すなわち、それのタグのキャッシュ内の群の個数Ｎにより法（ｍｏｄｕｌｕｓ）を実行する（タグ  ＭＯＤ  Ｎ）ことにより得られる整数値、すなわち、当該要素をある群に一意的にマッピングする数を取得することにより、キャッシュ内のある群に迅速にマッピングすることが可能である。他の多数の方法が、あるラインをキャッシュ内のある群にマッピングするのに利用可能であり、群のインデックスを取得するため、タグ又はラインに係る任意の他の一意的なビット群をビットシフトし、タグ又は他の一意的な識別子とマスクとの論理ＡＮＤを実行し、当業者には周知であるように、群番号を導出するため、タグ又は他の一意的識別子とマスクとのＸＯＲ演算を実行することを含み、主張される主題は上記方法の１以上の何れにも限定されるものではない。
【０００３】
群連想キャッシュに要素を配置するため、システムは、ディスク上のデータのアドレスを利用して、当該要素が配置される群を計算し、その後、典型的な実現形態では、一致が検出されるまで、あるいは、当該要素が当該群にはないと判断されるまで、当該群を表すアレイを検索する。
【０００４】
同様のキャッシュ実現形態は、連想群の代わりにハッシュテーブルを用いてキャッシュを構成する。このようなキャッシュでは、再び要素は通常は等しいサイズを有する固定サイズアレイに構成される。しかしながら本例では、ハッシュ関数を用いて、要素が配置されているアレイを計算する。ハッシュ関数への入力は、要素のタグに基づくものとしてもよく、その後、関数は当該要素を特定のハッシュバケット（ｈａｓｈ  ｂｕｃｋｅｔ）にマッピングする。ハッシュ関数及びそれのデータアクセスのための利用及びキャッシュ構成は周知であり、ここでは詳細については説明されない。
【０００５】
本出願の主題の説明を簡単化するため、ＣＡＴＢ（Ｃｏｎｓｔａｎｔ  Ａｃｃｅｓｓ  Ｔｉｍｅ  Ｂｏｕｎｄｅｄ）という用語が、上述の群連想及びハッシュテーブルに基づくキャッシュを含むキャッシュ構成を説明するのに導入される。従来技術によるＣＡＴＢの主要な特徴は、各アレイがタグなどのキャッシュ要素のある一意的特徴に基づき一定時間でアドレス可能な、一般に等しいサイズを有する固定サイズのアレイにＣＡＴＢキャッシュが構成されるということである。ＣＡＴＢキャッシュの他の構成は、当業者に容易に明らかとなるかもしれない。一般に、要素をＣＡＴＢキャッシュに配置するためのアクセス時間は、一定時間に限定されるか、あるいは、少なくともトータルのキャッシュサイズから独立である。なぜなら、アレイを特定する時間は一定であり、各アレイは固定されたサイズを有し、このため、アレイ内の検索は一定時間に限定されるためである。用語の統一のため、「検索グループ」という用語は、要素をマッピングすることにより特定されるアレイ（すなわち、ハッシュテーブルベースキャッシュのハッシュブラケット又は群連想キャッシュ内の群）を表すのに用いられる。
【０００６】
ＣＡＴＢキャッシュの各要素、すなわち、キャッシュライン１２０は、システムによりアクセスされている低速の記憶装置からの実データと、管理用にキャッシュ管理システムにより使用されるメタデータと呼ばれる他のデータの両方を含む。メタデータは、ラインの当該データのアドレス又は一意的識別子であるタグと、当該ラインが使用中（割当て済み）であるか、あるいは未使用（未割当て）であるか示すためのビット又はフラグと共に、他の用途のため確保されているビットを含む、当該ラインの状態に関する他のデータを含むものであってもよい。
【０００７】
システムが動作している限り、キャッシュのあるラインが頻繁にアクセスされるオペレーティングシステムコードを含むラインのため、キャッシュ内に常時留まることが効果的であるかもしれない。このようなキャッシュラインは、キャッシュ内で可能性として無限に保持され、通常のキャッシュ置換方針の対象から除外され、「ピンド（ｐｉｎｎｅｄ）」と呼ばれる。キャッシュ管理システムは、キャッシュに入力される新たなデータの格納のため、新たなキャッシュラインに対する要求が与えられると、キャッシュから当該ラインを削除することはない。このような実現形態のラインは、当該ラインがピンドであるか示すメタデータ内のフラグを有するようにしてもよい。
【０００８】
しかしながら、ピン処理に関しては問題点がある。既知であって、ここでは詳細には説明されない理由としては、ほぼ等しいサイズの群を有するＣＡＴＢキャッシュは、一様でない群サイズのものより良好に機能する可能性がある。群連想キャッシュの群など、ＣＡＴＢキャッシュの検索グループの１以上のラインがピンドデータにより占有されると、非ピンドデータによるキャッシュ処理用の検索グループの効果的なサイズは、ピンドラインの個数だけ減少する。システムが当該検索グループにマッピングされるデータ要素にアクセスしようとする場合、それのパフォーマンスは、非ピンド要素を有する他の検索グループの要素にアクセスする場合のそれのパフォーマンスに対して低下するかもしれない。この現象は、ホットスポット生成と呼ばれ、ピンドラインを有するキャッシュの設計者に問題を与えている。
［詳細な説明］
請求される主題の一実施例では、ＣＡＴＢキャッシュの一タイプである群連想キャッシュを実現するため、動的データ構造が利用されている。図１に示されるように、このような実現形態では、キャッシュの各群はリンクリスト１００として実現される。このリストは、２つの実現形態においてシングル又はダブルリンクリストであってもよい。各群はキャッシュライン１２０を有し、各キャッシュラインは１４０により示されるようなメタデータとデータの両方を有する。本実現形態のキャッシュから要素を削除、アクセス及び挿入することは、キャッシュラインのタグを用いて群の識別子を計算し、当該群に対応するリンクリストを探索することにより実現されてもよい。同一のタグを有するラインが検出された場合、当該要素はキャッシュ内に存在し、検出されなかった場合、当該要素はキャッシュ内には存在しない。
【０００９】
このタイプのキャッシュ実現形態では、キャッシュの各群のすべてが同一サイズを有することが可能であるが、リンクリストからある群を表すキャッシュラインを削除し、それを他のリンクリストにリンクさせることにより、あるいは逆に、当該リストと異なるリンクリストから群を表すキャッシュラインを削除し、それをある群に追加することによって、要素を群に追加したり、又は削除したりすることが可能であるかもしれない。従ってこのキャッシュ実現形態では、各群は異なるサイズを有するものであってもよい。
【００１０】
図６に示されるようなプロセッサベースシステムは、請求される主題の一実施例を実現する。図６は、バスシステム６４０を介しメモリ６６０、ディスク及びディスク６８０とディスクキャッシュ６００を有するキャッシュシステムに接続されるプロセッサ６２０を示す。本実現形態では、ディスクキャッシュ６００は、揮発性又は不揮発性メモリにより実現されてもよい。プロセッサはプログラムとアクセスデータを実行し、ディスク６８０に対するデータの読み書きを実行し、その後ディスクキャッシュ６００にキャッシュ処理されるようにしてもよい。もちろん、図６のシステムは単なる典型例である。プロセッサ数、バス構成、メモリ構成並びにディスク数及びタイプに関する変形を含むプロセッサベースシステムの他の多くの変形が可能である。さらに、請求される主題は、特にプロセッサベースシステムに限定されず、請求項に記載されるような一般的なキャッシュに拡張されてもよい。
【００１１】
上述の実施例及び請求される主題の他の実施例では、不揮発性メモリユニットを用いて、図１を参照して説明されたようなデータ構造を利用した図６に示されるようなものであって、図２に示されるようなピンドデータのために確保されたキャッシュ部分を有するディスクキャッシュが実現されてもよい。図では、フリーピンドライン２４０と呼ばれる割り当てされていないキャッシュラインの一部が、ピンドデータによる利用のため確保されている。残りのキャッシュライン２６０は、群連想キャッシュに対し同様にしてＮ個の群２００に割り当てられる。
【００１２】
請求される主題による他の実施例では、キャッシュは上述の実施例と異なって、揮発性ストアにより実現されてもよい。当該キャッシュは、ネットワークデータ又はデータベースキャッシュなどのディスクキャッシュ以外の用途のキャッシュとして供されるようにしてもよい。
【００１３】
キャッシュの各群を構成するのに用いられる実際のデータ構造は、請求される主題の実施例において異なるものとされてもよい。例えば、キャッシュの各群は、図示されるように、正確に等しいサイズを有するものでなくともよい。
【００１４】
上述の実施例は、説明の簡単化のため、Ｎウェイ群連想キャッシュに限定され、一般には当該キャッシュの動的な実現形態を説明する。しかしながら、リスト又は他の動的データ構造を用いて、同様の方法により任意のタイプのＣＡＴＢキャッシュを動的なものにするようにしてもよい。従って、ハッシュテーブルベースＣＡＴＢキャッシュが、各ハッシュバケットのアレイの代わりに、あるタイプのリンクリストなどの動的構造を用いて同様に実現されるようにしてもよい。請求される主題の他の実施例では、他のＣＡＴＢキャッシュにおいて、検索回数がキャッシュの要素の総数に依存せず、各検索グループがサイズに関して動的に可変である限り、異なる基本的検索方法が利用されてもよい。
【００１５】
さらに、「要素」、「格納要素」、「エントリ」などの他の用語を用いて、請求される主題による実施例がとり得る多くの可能な形態を示すために説明され、請求される主題を説明された実施例のみに限定することを意図したものではない。
【００１６】
図３は、その動作中における上述の請求される主題による実施例において実現される群連想キャッシュのスナップショットを示す。当該動作時点において、いくつかのピンドライン３８０がキャッシュに追加された。ピンドラインが追加されると、フリーピンドラインがフリーピンドリスト３００から削除され、ピンドラインのデータを格納するのに使用される。各ピンドラインがキャッシュに追加されると、それのタグが挿入されるべき群の３２０の１つを選択するのに用いられる。当該群にピンドラインが追加された後、ピンドラインが挿入された群の非ピンドライン３４０の個数が挿入前と同一であり、群における非ピンドラインの個数が均衡を保っていることが観察されるかもしれない。動作が進行すると、フリーピンドライン３６０の個数は減少されてもよい。
【００１７】
キャッシュに追加されたピンドデータの動作が、さらに図４のフローチャートに示される。新たなピンドデータがキャッシュに追加されると、キャッシュ管理システムは、フリーピンドリストからラインを消去し（４００）、ピンドデータをラインに格納し（４２０）、当該ラインが挿入されるべき群を計算し（４４０）、ラインを選択された群に追加する（４６０）。
【００１８】
上記と同様に、請求される主題を実現するキャッシュの動作に関する当該説明は限定的なものではない。他の多くの実施例が可能である。一例として、リンクリスト以外のデータ構造を用いて、ピンドデータに利用可能なキャッシュラインを格納するようにしてもよい。本実施例では、各群における非ピンドラインは等しく存在しているようであるが、他の実施例では、キャッシュの各群における非ピンドラインの個数が正確に等しく維持されなくてもよい。さらなる他の実施例では、ピンドデータに割り当てられるラインの個数は、キャッシュ動作中に動的に可変するようにしてもよい。上記と同様に、当該動作は他のＣＡＴＢキャッシュに容易に一般化されてもよい。上記他の実施例は、請求される主題による実施例がとり得る多数の可能な形態を示すのに説明され、請求される主題を説明された実施例のみに限定することを意図したものではない。
【００１９】
請求される主題による実施例の実現形態では、ピンドラインの確保されているリストを有する群連想キャッシュは、不揮発性メモリ、すなわち、システムが偶然にもシャットダウンされたり、あるいは停電し、これにより、キャッシュへの電力ロスが発生した場合など、装置への外部電力がシャットダウンした後、それのデータインテグリティを保つ装置により実現されてもよい。一実施例では、これはディスクキャッシュとして不揮発性メモリにより実現されるキャッシュを含む。このような実現形態では、電力復帰後、電力ダウンイベントに続くキャッシュの状態を復元することが可能であるかもしれない。ピンドデータのキャッシュラインの確保されているグループの追加は、このような復元に影響を及ぼすものではない。図５は、上記特性を有する実現形態における復元を達せ得するのに用いられるプロセスのフローチャートである。
【００２０】
図５において、復元プロセスは、不揮発性キャッシュの各ラインを調べる。調べるべきラインが存在する限り（５００）、当該プロセスは次のラインを調べる（５１０）。当該ラインが割り当てられている、すなわち、有効なキャッシュデータを有することを状態情報が示すメタデータを有する場合、ラインのタグから群の識別子を計算することにより特定される群に当該ラインは挿入される（５４０）。ラインが割り当てられていない場合、それは何れかの方法により未割当てライン群に追加されてもよい（５３０）。すべてのラインが処理されると、復元はそれの最初の段階で形成された各群を調べる。未処理群が存在する限り（５５０）、次の未処理群が調べられる。ラインがピンドデータを有することを示すメタデータを有する群の各ラインについて、当該復元手順は、未割当てライン群からのラインを当該群に追加し、すべての群における未割当てラインの均衡された個数を維持する（５７０，５８０）。残った何れかのラインが、当該ライン群に返される（５９０）。
【００２１】
上記復元プロセスに関する請求される主題による他の多くの実施例が可能である。例えば、一部の実施例では、再構成プロセスにより生成される群が正確に均衡していなくてもよい。あるいは、割当て済みのラインを群に割り当てるプロセスは異なるものであってもよい。上記他の実施例は、請求される主題による実施例がとり得る多数の可能な形態を示すのに説明され、請求される主題を説明された実施例にのみ限定することを意図したものではない。
【００２２】
請求される主題による実施例は、各種ステップを含む。これらの実施例のステップは、ハードウェア装置により実行されてもよいし、あるいは、マシーンにより実行可能な命令によりプログラムされた汎用又は特定用途向けプロセッサ又はロジック回路に各ステップを実行されるのに利用される命令により実現されてもよい。あるいは、各ステップはハードウェアとソフトウェアの組み合わせにより実行されてもよい。請求される主題による実施例は、マシーンによるアクセス時に、マシーンに請求される主題によるプロセスを実行させるデータを格納したマシーン可読媒体を有するコンピュータプログラムプロダクトとして与えられてもよい。このマシーン可読媒体は、以下に限定するものではないが、フロッピー（登録商標）ディスケット、光ディスク、ＤＶＤ−ＲＯＭディスク、ＤＶＤ−ＲＡＭディスク、ＤＶＤ−ＲＷディスク、ＤＶＤ＋ＲＷディスク、ＣＤ−Ｒディスク、ＣＤ−ＲＷディスク、ＣＤ−ＲＯＭディスク、光磁気ディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気又は光カード、フラッシュメモリ、あるいは電子命令を格納するのに適した他のタイプのメディア／マシーン可読媒体を含むものであってもよい。さらに、請求される主題の実施例はまた、コンピュータプログラムプロダクトとしてダウンロードされてもよく、当該プログラムは、通信リンク（モデム、ネットワーク接続など）を介しキャリア波又は他の伝搬媒体により実現されるデータ信号によりリモートコンピュータから要求元のコンピュータに転送されてもよい。
【００２３】
上記多数の方法がそれらの最も基本的な形態により説明されたが、各ステップはこれらの方法の何れかに対しては追加又は削除可能であり、請求される主題の基本的範囲から逸脱することなく記述されるメッセージの何れかに対し追加又は削除することができる。さらなる多数の変更及び調整が可能であるということは、当業者には明らかであろう。上記実施例は、本発明を限定するのでなく、それを説明するために与えられている。請求される主題の範囲は、上記具体例によってではなく、以下の請求項によってのみ決定されるべきである。
【図面の簡単な説明】
【００２４】
【図１】図１は、Ｎウェイ群連想キャッシュを実現するのに利用可能な動的データ構造を示す。
【図２】図２は、請求される主題の実施例によるピンドデータがキャッシュに追加されていないとき、ピンドデータ用に確保されたキャッシュの一部を有するＮウェイ群連想キャッシュを実現するデータ構造の状態を示す。
【図３】図３は、請求される主題の実施例におけるキャッシュへのピンドキャッシュラインの挿入後の図２からのデータ構造の状態を示す。
【図４】図４は、請求される主題の実施例におけるピンドデータをキャッシュに挿入するのにとられるアクションのフローチャートを示す。
【図５】図５は、請求される主題の実施例による不揮発性実現形態における電力ダウンイベントに続くキャッシュを再構成するのにとられるアクションのフローチャートを示す。
【図６】図６は、請求される主題の実施例によるプロセッサベースシステムを示す。
【図１】
2007500398.tif 000003
【図２】
2007500398.tif 000004
【図３】
2007500398.tif 000005
【図４】
2007500398.tif 000006
【図５】
2007500398.tif 000007
【図６】
2007500398.tif 000008
【国際調査報告】
2007500398.tif 000009
2007500398.tif 000010