(57)【要約】      （修正有）【課題】デデュープ可能なメモリキャッシュ及びそのための動作方法を提供する。【解決手段】デデュープ可能なキャッシュは、デデュープ可能なリードキャッシュ及び非デデュープ可能なライトバッファを含むキャッシュメモリ３０５と、デデュープ可能なリードキャッシュを利用してデータのリード及びライトを管理し、デデュープ可能なリードキャッシュへのライト要請が成功したか否かを示すライト状態信号を伝送するデデュープエンジン４０５と、キャッシュコントローラ３１０と、を備える。キャッシュコントローラは、キャッシュヒット／ミスチェックロジックと、アドレスがデデュープ可能なリードキャッシュで発見場合にキャッシュメモリの第１データにアクセスするヒットブロックと、アドレスがデデュープ可能なリードキャッシュで発見されない場合、バックエンド大容量メモリにアクセスするミスブロックと、ヒストリーストレージと、を含む。【選択図】図４
2019128949.tif 000002
【特許請求の範囲】
【請求項１】
デデュープ可能な（ｄｅｄｕｐａｂｌｅ）リードキャッシュ及び非デデュープ可能な（ｎｏｎ−ｄｅｄｕｐａｂｌｅ）ライトバッファを含むキャッシュメモリと、
前記デデュープ可能なリードキャッシュを利用してデータのリード及びライトを管理し、前記デデュープ可能なリードキャッシュへのライト要請が成功したか否かを示すライト状態信号を伝送するデデュープエンジンと、
キャッシュコントローラと、を備え、
前記キャッシュコントローラは、
要請に含まれるアドレスが前記デデュープ可能なリードキャッシュで発見されるか否かをチェックするキャッシュヒット／ミスチェックロジックと、
前記アドレスが前記デデュープ可能なリードキャッシュで発見されることを前記キャッシュヒット／ミスチェックロジックが示す場合、前記キャッシュメモリの第１データにアクセスするヒットブロックと、
前記アドレスが前記デデュープ可能なリードキャッシュで発見されないことを前記キャッシュヒット／ミスチェックロジックが示す場合、バックエンド大容量メモリの第２データにアクセスするミスブロックと、
前記デデュープ可能なリードキャッシュの前記第１データへのアクセスに関する情報を格納するヒストリーストレージと、を含むことを特徴とするデデュープ可能なキャッシュ。
【請求項２】
前記デデュープ可能なリードキャッシュは、前記デデュープ可能なリードキャッシュに物理的に適合するものよりもより多くのキャッシュラインを格納することをシミュレーションすることを特徴とする請求項１に記載のデデュープ可能なキャッシュ。
【請求項３】
前記キャッシュメモリは、前記デデュープ可能なリードキャッシュのキャッシュラインに関する情報を格納するメタデータ領域を更に含むことを特徴とする請求項１に記載のデデュープ可能なキャッシュ。
【請求項４】
前記キャッシュコントローラは、データをライトするための第１ライト要請をプロセッサから受信し、前記非デデュープ可能なライトバッファに前記データを格納し、
前記ヒットブロックは、前記デデュープ可能なリードキャッシュのキャッシュラインが前記第１ライト要請によって修正される場合、前記キャッシュラインを無効化させるように前記デデュープエンジンに第２ライト要請を伝送することを特徴とする請求項１に記載のデデュープ可能なキャッシュ。
【請求項５】
前記第２ライト要請は、前記デデュープ可能なリードキャッシュの前記キャッシュラインに０の値をライトする要請を含むことを特徴とする請求項４に記載のデデュープ可能なキャッシュ。
【請求項６】
前記キャッシュコントローラは、前記キャッシュメモリのメタデータ領域に前記キャッシュラインが有効でないとしてマークすることを特徴とする請求項４に記載のデデュープ可能なキャッシュ。
【請求項７】
前記ヒットブロックは、前記第２ライト要請に応答する前記デデュープエンジンから非確認応答（ＮＡＫ）信号を受信して前記デデュープ可能なリードキャッシュから第２キャッシュラインを除去し、前記デデュープ可能なリードキャッシュから前記第２キャッシュラインを除去した後に前記デデュープエンジンに前記第２ライト要請を再び伝送することを特徴とする請求項４に記載のデデュープ可能なキャッシュ。
【請求項８】
前記キャッシュコントローラは、データをリードするためのリード要請をプロセッサから受信して前記プロセッサに前記データを伝送し、
前記ミスブロックは、前記バックエンド大容量メモリから前記データをリトリーブし、前記デデュープ可能なリードキャッシュに前記データをライトするために前記デデュープエンジンにライト要請を伝送することを特徴とする請求項１に記載のデデュープ可能なキャッシュ。
【請求項９】
前記ミスブロックは、前記ライト要請に応答する前記デデュープエンジンから非確認応答（ＮＡＫ）信号を受信して前記デデュープ可能なリードキャッシュからキャッシュラインを除去し、前記デデュープ可能なリードキャッシュから前記キャッシュラインを除去した後に前記デデュープエンジンに前記ライト要請を再び伝送することを特徴とする請求項８に記載のデデュープ可能なキャッシュ。
【請求項１０】
キャッシュコントローラの動作方法であって、
データをライトするためのライト要請を受信するステップと、
前記データがデデュープ可能な（ｄｅｄｕｐａｂｌｅ）リードキャッシュのキャッシュラインに存在すると判定するステップと、
前記デデュープ可能なリードキャッシュの前記キャッシュラインを無効化するステップと、
前記データを非デデュープ可能な（ｎｏｎ−ｄｅｄｕｐａｂｌｅ）ライトバッファに格納するステップと、を有し、
前記デデュープ可能なリードキャッシュは、キャッシュメモリの第１領域であり、
前記キャッシュメモリは、第２領域として前記非デデュープ可能なライトバッファを含むことを特徴とする方法。
【請求項１１】
前記デデュープ可能なリードキャッシュの前記キャッシュラインを無効化するステップは、
前記キャッシュメモリのメタデータ領域に前記キャッシュラインが有効でないとしてマークするステップと、
デデュープエンジンを介して前記キャッシュラインに０の値をライトするステップと、を含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記デデュープ可能なリードキャッシュの前記キャッシュラインを無効化するステップは、前記デデュープエンジンからライト状態信号の確認応答（ＡＣＫ）を受信するステップと、を更に含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記デデュープ可能なリードキャッシュの前記キャッシュラインを無効化するステップは、
前記デデュープエンジンからライト状態信号の非確認応答（ＮＡＫ）を受信するステップと、
前記デデュープ可能なリードキャッシュから除去する第２キャッシュラインを選択するステップと、
前記第２キャッシュラインを無効化するステップと、
前記デデュープエンジンを介して前記第２キャッシュラインに０の値をライトするステップと、を更に含むことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記データを非デデュープ可能なライトバッファに格納するステップは、前記データが前記デデュープ可能なリードキャッシュの前記キャッシュラインに存在するか否かに拘らず、前記データを前記非デデュープ可能なライトバッファに格納するステップと、を含むことを特徴とする請求項１０に記載の方法。
【請求項１５】
キャッシュコントローラの動作方法であって、
データをリードするためのリード要請を受信するステップと、
前記データがデデュープ可能な（ｄｅｄｕｐａｂｌｅ）リードキャッシュの複数のキャッシュラインに存在しないと判定するステップと、
バックエンド大容量メモリから前記データをリードするステップと、
前記デデュープ可能なリードキャッシュの第１キャッシュラインを選択するステップと、
前記データを前記第１キャッシュラインにライトすることを試みるためにデデュープエンジンに前記データを提供するステップと、
前記リード要請に応答して前記データを伝送するステップと、を有し、
前記デデュープ可能なリードキャッシュは、キャッシュメモリの第１領域であり、
前記キャッシュメモリは、第２領域として非デデュープ可能な（ｎｏｎ−ｄｅｄｕｐａｂｌｅ）ライトバッファを含むことを特徴とする方法。
【請求項１６】
前記デデュープ可能なリードキャッシュの第１キャッシュラインを選択するステップは、前記デデュープ可能なリードキャッシュから現在データを格納していない前記第１キャッシュラインを選択するステップを含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
前記デデュープ可能なリードキャッシュの第１キャッシュラインを選択するステップは、
前記キャッシュメモリのメタデータ領域からのデデュープ可能なリードキャッシュメタデータ及びヒストリーデータに応答して、前記デデュープ可能なリードキャッシュから除去するために現在有効なデータを格納している前記第１キャッシュラインを選択するステップと、
前記第１キャッシュラインを無効化するステップと、を含むことを特徴とする請求項１５に記載の方法。
【請求項１８】
前記第１キャッシュラインを無効化するステップは、
前記キャッシュメモリの前記メタデータ領域に前記第１キャッシュラインを有効でないとしてマークするステップと、
前記デデュープエンジンを介して前記第１キャッシュラインに０の値をライトするステップと、を含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
前記データを前記第１キャッシュラインにライトすることを試みるためにデデュープエンジンに前記データを提供するステップは、前記デデュープエンジンからライト状態信号の確認応答（ＡＣＫ）を受信するステップを含むことを特徴とする請求項１５に記載の方法。
【請求項２０】
前記データを前記第１キャッシュラインにライトすることを試みるためにデデュープエンジンに前記データを提供するステップは、
前記デデュープエンジンからライト状態信号の非確認応答（ＮＡＫ）を受信するステップと、
前記キャッシュメモリのメタデータ領域からのデデュープ可能なリードキャッシュメタデータ及びヒストリーデータに応答して、前記デデュープ可能なリードキャッシュから除去するために現在有効なデータを格納している第２キャッシュラインを選択するステップと、
前記第２キャッシュラインを無効化するステップと、
前記データを前記選択された第２キャッシュラインにライトすることを試みるために前記デデュープエンジンに前記データを提供するステップと、を含むことを特徴とする請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データキャッシングに関し、より詳細には、デデュープ可能なメモリキャッシュ及びそのための動作方法に関する。
【背景技術】
【０００２】
デデュープ（重複排除：Ｄｅ−ｄｕｐｌｉｃａｔｉｏｎ）可能な（ｄｅｄｕｐａｂｌｅ）メモリは、システムにおいて「利用可能な」メモリを増加させる方式を提供する。重複データを検出して一つのデータのコピーを格納することにより、重複データのコピーを格納するために用いられるストレージは、他のデータを格納するために用いられる。特に、同じデータ値へのアクセスを要請する多様なアプリケーションは、たとえ要請が他のアドレスを利用していたとしても、全てが同じ物理アドレスに連結される。二個、三個、又はより多くの論理アドレスが同じ物理アドレスにマッピングされることから、追加的データのコピーに必要な可能性があるストレージは、他のデータを格納するために用いられ、メモリが物理的に格納可能なものよりもより多くの全体のデータを格納するように見せる。
【０００３】
しかし、デデュープ可能なメモリも自体的な問題をもたらす。どのアドレスが同じデータを示すのかを管理することは難しく、リード（ｒｅａｄ）及びライト（ｗｒｉｔｅ）のようなデータアクセスが他の形態のストレージに比して遅い可能性がある。相対的にアクセスの遅いデータを利用する場合（ハードディスクドライブのような）、必ずしも大きな困難性があるわけではないが、より速いストレージデバイスに適用される場合、このような遅延は相当な制約になる。ストレージデバイスが一般的に速く動作する程、データ重複の全体的な影響は更に大きくなる。例えば、ダイナミックランダムアクセスメモリ（ＤＲＡＭ：Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）のアクセスは、ソリッドステートディスク（ＳＳＤ：Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｉｓｋ）又は他の形態のフラッシュメモリよりもデータ重複に関連する遅延に対してはるかに敏感になり、これはハードディスクドライブよりも遅延に対してより敏感である。
【０００４】
キャッシュにおいて、デデュープ可能なメモリを利用する方式は、バックエンド（ｂａｃｋｅｎｄ）メモリのデータに対するアクセス速度を高くするために必要な可能性がある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第９１１６８１２号明細書
【特許文献２】米国特許第９３０４９１４号明細書
【特許文献３】米国特許第９３９０１１６号明細書
【特許文献４】米国特許第９４０１９６７号明細書
【特許文献５】米国特許出願公開第２０１５／００７４３３９号明細書
【特許文献６】米国特許出願公開第２０１６／０２２４５８８号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、上記従来の問題点に鑑みてなされたものであって、本発明の目的は、デデュープ可能なメモリを利用するキャッシュ及びそのための動作方法を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するためになされた本発明の一態様によるデデュープ可能なキャッシュは、デデュープ可能な（ｄｅｄｕｐａｂｌｅ）リードキャッシュ（ｃａｃｈｅ）及び非デデュープ可能な（ｎｏｎ−ｄｅｄｕｐａｂｌｅ）ライトバッファ（ｂｕｆｆｅｒ）を含むキャッシュメモリと、前記デデュープ可能なリードキャッシュを利用してデータのリード及びライトを管理し、前記デデュープ可能なリードキャッシュへのライト要請が成功したか否かを示すライト状態信号を伝送するデデュープエンジンと、キャッシュコントローラと、を備え、前記キャッシュコントローラは、要請に含まれるアドレスが前記デデュープ可能なリードキャッシュで発見されるか否かをチェックするキャッシュヒット（ｈｉｔ）／ミス（ｍｉｓｓ）チェックロジックと、前記アドレスが前記デデュープ可能なリードキャッシュで発見されることを前記キャッシュヒット／ミスチェックロジックが示す場合、前記キャッシュメモリの第１データにアクセスするヒットブロックと、前記アドレスが前記デデュープ可能なリードキャッシュで発見されることを前記キャッシュヒット／ミスチェックロジックが示す場合、バックエンド（ｂａｃｋｅｎｄ）大容量メモリの第２データにアクセスするミスブロックと、前記デデュープ可能なリードキャッシュの前記第１データへのアクセスに関する情報を格納するヒストリー（ｈｉｓｔｏｒｙ）ストレージと、を含む。
【０００８】
上記目的を達成するためになされた本発明の一態様によるキャッシュコントローラの動作方法は、データをライト（ｗｒｉｔｅ）するためのライト要請を受信するステップと、前記データがデデュープ可能な（ｄｅｄｕｐａｂｌｅ）リードキャッシュのキャッシュラインに存在すると判断するステップと、前記デデュープ可能なリードキャッシュの前記キャッシュラインを無効化するステップと、前記データを非デデュープ可能な（ｎｏｎ−ｄｅｄｕｐａｂｌｅ）ライトバッファに格納するステップと、を有し、前記デデュープ可能なリードキャッシュは、キャッシュメモリの第１領域であり、前記キャッシュメモリは、第２領域として前記非デデュープ可能なライトバッファを含む。
【０００９】
上記目的を達成するためになされた本発明の他の態様によるキャッシュコントローラの動作方法は、データをリード（ｒｅａｄ）するためのリード要請を受信するステップと、前記データがデデュープ可能な（ｄｅｄｕｐａｂｌｅ）リードキャッシュの複数のキャッシュラインに存在しないと判断するステップと、バックエンド大容量メモリから前記データをリードするステップと、前記デデュープ可能なリードキャッシュの第１キャッシュラインを選択するステップと、前記データを前記第１キャッシュラインにライトすることを試みるためにデデュープエンジンに前記データを提供するステップと、前記リード要請に応答して前記データを伝送するステップと、を有し、前記デデュープ可能なリードキャッシュは、キャッシュメモリの第１領域であり、前記キャッシュメモリは、第２領域として非デデュープ可能なライトバッファを含む。
【発明の効果】
【００１０】
本発明のキャッシュによれば、より多くのデータを同じ物理的な大きさのメモリに格納することができる。
【００１１】
また、本発明のキャッシュによれば、デデュープ可能なメモリへのライト固有の遅延を防止することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態によるデデュープ可能なキャッシュを使用するマシンを示す図である。
【図２】図１のマシンの追加的な詳細事項を示す図である。
【図３】図１のデデュープキャッシュの例示的なレイアウトを示す図である。
【図４】デデュープエンジンを有する図１のデデュープキャッシュを示す図である。
【図５】図３及び図４のキャッシュコントローラの詳細事項を示す図である。
【図６Ａ】本発明の一実施形態による図１のデデュープキャッシュがライト要請を処理する例示的な手順のフローチャートである。
【図６Ｂ】本発明の一実施形態による図１のデデュープキャッシュがライト要請を処理する例示的な手順のフローチャートである。
【図７】本発明の一実施形態による図１のデデュープキャッシュが図３のデデュープ可能なリードキャッシュのキャッシュラインを無効化するための例示的な手順のフローチャートである。
【図８Ａ】本発明の一実施形態による図１のデデュープキャッシュがリード要請を処理する例示的な手順のフローチャートである。
【図８Ｂ】本発明の一実施形態による図１のデデュープキャッシュがリード要請を処理する例示的な手順のフローチャートである。
【図８Ｃ】本発明の一実施形態による図１のデデュープキャッシュがリード要請を処理する例示的な手順のフローチャートである。
【発明を実施するための形態】
【００１３】
以下、本発を実施するための形態の具体例を、図面を参照しながら詳細に説明する。後述する詳細な説明で、発明の完璧な理解を可能にするために、多様な特定の詳細事項を記載する。しかし、本技術分野における通常の技術者がこのような特定の詳細事項なしに発明を実施することは自明である。他の場合において、よく知られている方法、手順、構成要素、回路、そしてネットワークは実施形態を不必要に曖昧にしないために詳細に説明しない。
【００１４】
第１、第２などの用語は、本明細書で多様な要素を説明するために使用されるとしても、このような要素は、これらの用語によって限定されないことが理解される。これらの用語は、一つの要素を他の要素と区別するために使用される。例えば、本発明の権利範囲を逸脱せずに、第１モジュールは、第２モジュールと称され、第２モジュールは、第１モジュールと称される。
【００１５】
本明細書において、発明の詳細な説明で使用する用語は、単に特定の実施形態を説明するための目的であり、本発明を制限しようとする意図ではない。発明の説明及び請求項で使用するように、文脈が明らかに他のことを示していない限り、単数形の用語は複数形を含むように意図する。本明細書で「及び／又は」という用語は、列挙された項目に関連する一つ以上の可能な組み合わせを全て示すものと理解される。「含む（ｃｏｍｐｒｉｓｅｓ）」及び／又は「含む（ｃｏｍｐｒｉｓｉｎｇ）」という用語は、本明細書で使用する場合、記述する特徴、整数、ステップ、動作、要素、及び／又は構成要素の存在を明示するものと理解される。しかし、一つ以上の他の特徴、整数、ステップ、動作、要素、構成要素、及び／又はそれらのグループの追加又は存在を排除するものではない。図面の構成要素及び特徴は、必ずしも縮尺に合わせて描かれていない。
【００１６】
デデュープダイナミックランダムアクセスメモリ（ＤＲＡＭ）は、所定のＤＲＡＭユニット内で向上した論理的容量を提供するが、一般のＤＲＡＭの動作よりも一般的に遅い。この遅いパフォーマンスにより、デデュープＤＲＡＭを一般のＤＲＡＭキャッシュとしてすることは使用できない。
【００１７】
このような懸念を解決するために、デデュープＤＲＡＭキャッシュのメモリを、デデュープ可能なＤＲＡＭリード（ｒｅａｄ）キャッシュ、及び非デデュープ可能な（言い換えると、デデュープ不可能な）ライト（ｗｒｉｔｅ）バッファに分ける。デデュープＤＲＡＭへのライトは遅いため、既存のＤＲＡＭがライトバッファ（ＷＢ）に用いられる。リード要請は、デデュープ可能なリードキャッシュ（ＲＣ）から（殆ど）提供されるが、ライトは通常のＤＲＡＭライトバッファ（ＷＢ）によって提供される。
【００１８】
例えば、物理的なＤＲＡＭが８ギガバイト（ＧＢ）である場合、物理的なＤＲＡＭは４ＧＢの物理的デデュープＤＲＡＭ  ＲＣ（リードキャッシュ）（総８ＧＢの仮想容量を提供する）及び４ＧＢの物理的なＤＲＡＭのＷＢ（ライトバッファ）に分割される。デデュープエンジンは、単にデデュープＤＲＡＭのＲＣによって利用される特定の４ＧＢの範囲についてデデュープメカニズム（ｍｅｃｈａｎｉｓｍ）を動作させる。
【００１９】
しかし、デデュープＤＲＡＭがリードキャッシュとして使用されるとしても、ライトはデデュープＤＲＡＭに相変わらず影響を与える。例えば、ホスト（ｈｏｓｔ）からの６４バイト（Ｂ）のアップデートは、デデュープＤＲＡＭのＲＣに格納されたデータに影響を与えるか（ライトヒット（ｈｉｔ））、或いはデータが現在のデデュープＤＲＡＭ  ＲＣにない場合（リードミス（ｍｉｓｓ））、バックエンド大容量のメモリからの２キロバイト（ＫＢ）が必要になる。デデュープＤＲＡＭのＲＣにライトする状況を解決するために、新たなＷＲ＿Ｓｔａｔｕｓ信号が用いられる。即ち、ライトが成功した場合、デデュープエンジンはＡＣＫ（確認応答、又は肯定応答）を返し、そうでない場合、デデュープエンジンはＮＡＫ（非確認応答、又は否定応答）を返す。キャッシュコントローラがＮＡＫを受信すると、キャッシュコントローラは、キャッシュフィル（ｃａｃｈｅ  ｆｉｌｌ）をキャンセル（ｃａｎｃｅｌ）する（即ち、２ＫＢフィル（ｆｉｌｌ）はキャッシュされない）。
【００２０】
従って、デデュープＤＲＡＭのＲＣライトヒット処理のために、デデュープＤＲＡＭキャッシュは、キャッシュライン（ｃａｃｈｅ  ｌｉｎｅ）が有効でないようにＲＣのメタデータ（ｍｅｔａｄａｔａ）をアップデートし、６４Ｂの０（キャッシュラインを有効しないようにする）をデデュープエンジンにライトする（これはデデュープＤＲＡＭのＲＣをガーベージコレクション（ｇａｒｂａｇｅ  ｃｏｌｌｅｃｔｉｏｎ）することに関連付ける）。このような処理が完了した後、デデュープＤＲＡＭキャッシュは、デデュープＤＲＡＭのＲＣライトヒットがなかったかのように進行する（即ち、デデュープＤＲＡＭキャッシュは、デデュープＤＲＡＭのＲＣライトミスがあったかのように進行する）。
【００２１】
デデュープＤＲＡＭのＲＣフィル（ｆｉｌｌ）を処理するために、デデュープＤＲＡＭキャッシュは、デデュープＤＲＡＭのＲＣから削除されるキャッシュラインを選択するためにヒストリー及びＲＣメタデータをリードする。選択されたキャッシュラインが有効なデータを含む場合、デデュープＤＲＡＭキャッシュは、キャッシュラインを無効としてマークするためにＲＣのメタデータをアップデートし、キャッシュラインが有効でないように２ＫＢの０をデデュープエンジンにライトする。そして（選択されたキャッシュラインが有効でない場合）、デデュープＤＲＡＭキャッシュはデデュープエンジンに新たなキャッシュラインのデータをライトし、デデュープエンジンはＷＲ＿Ｓｔａｔｕｓ信号を返す。デデュープエンジンがＡＣＫを返すと、デデュープＤＲＡＭキャッシュはキャッシュラインを有効としてマークするためにＲＣのメタデータをアップデートする。そうでない場合、デデュープエンジンがＮＡＫを返すと、デデュープＤＲＡＭキャッシュは、デデュープＤＲＡＭのＲＣにデータをライトするための要請をドロップ（ｄｒｏｐ）する。
【００２２】
上述した本発明は、デデュープ可能なメモリを使用して潜在的に低いライトパフォーマンスの問題を解決するために有効的である。しかし、デデュープ可能なメモリの使用は他の問題を引き起こす。即ち、それはライト動作が保証されないということである。例えば、デデュープＤＲＡＭのＲＣフィル動作が遂行されないが、デデュープＤＲＡＭのＲＣの全てのキャッシュラインは有効なデータを格納するものと仮定する。無効化のために選択されたキャッシュラインがデデュープされたデータを示す場合、即ちキャッシュラインによって示されたデータが他のキャッシュラインによって示される場合、キャッシュラインを無効化することは任意の物理的メモリを確保しないはずである。或いは、データが他のキャッシュラインによって使用されている場合、デデュープＲＣのライトヒット時、デデュープエンジンがキャッシュラインを０で上書きすることができない。このようなライト完了の保証不足の問題に対する二つの解決策がある。即ち、ライトが保証されないことを受け入れるか、又はライト動作の完了を保証するためにライト動作を再び試みることである。
【００２３】
ライト動作を再び試みることを達成するために、ライト再試みが遂行される。ライトが失敗した場合、即ちデデュープエンジンが試みられたライトからＮＡＫ信号を返す場合、他のキャッシュラインが無効化のために選択され（デデュープＤＲＡＭキャッシュの具現に応じてライトバック（ｗｒｉｔｅｂａｃｋ）が含まれる）、ライトが再び試みられる。
【００２４】
他のキャッシュラインを無効化すると、デデュープエンジンはデデュープＤＲＡＭのＲＣへのライト動作を完了するため、ライト再試みが成功する。しかし、ライト再試みの部分として、無効のために選択されたキャッシュラインもまたデデュープの対象データを指し示す場合、ライト再試みが再び失敗する。従って、キャッシュラインを無効化してライトを再び試みるプロセスは、所望の何回かが繰り返し遂行される。一般的に、再試みのプロセスに対する終了条件は、成功的なライト（デデュープエンジンからのＡＣＫ信号により示されるように）、一セットの全てのキャッシュラインの排除、又は予め決定された数のライト再試みである。全てのキャッシュラインが排除されるか、又は予め決められた数のライト再試みの中の一つが発生した場合、デデュープＤＲＡＭキャッシュは、所望のライト動作を成功的に完了せずに、単にプロセッサに結果を返すだけでよい。
【００２５】
図１は、本発明の一実施形態によるデデュープキャッシュを使用するマシン（ｍａｃｈｉｎｅ）を示す図である。図１には、マシン１０５を示す。マシン１０５は、プロセッサ１１０を含む。プロセッサ１１０は、任意の多様なプロセッサである。例えば、プロセッサ１１０は、インテルジーオン（Ｉｎｔｅｌ  Ｘｅｏｎ（登録商標））、セレロン（Ｃｅｌｅｒｏｎ（登録商標））、アイテニアム（Ｉｔａｎｉｕｍ（登録商標））、又はアトム（Ａｔｏｍ（登録商標））プロセッサ、エーエムディーオプテロン（ＡＭＤ  Ｏｐｔｅｒｏｎ（登録商標））プロセッサ、アーム（ＡＲＭ（登録商標））プロセッサなどである。図１は、マシン１０５内に、一つのプロセッサ１１０を示しているが、マシン１０５は、任意の数のプロセッサを含み、それぞれのプロセッサは、シングルコア又はマルチコアプロセッサであり、任意の所望の組み合わせで混合される。プロセッサ１１０は、デバイスドライバ（ｄｒｉｖｅｒ）１１５を実行し、デバイスドライバ１１５は、ストレージデバイス１２０へのアクセスをサポートする。他のデバイスドライバは、マシン１０５の他の構成要素へのアクセスをサポートする。
【００２６】
マシン１０５は、メモリコントローラ１２５を含み、メモリコントローラ１２５は、メインメモリ１３０へのアクセスを管理するために使用される。メモリ１３０は、フラッシュメモリ、Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＤＲＡＭ）、Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＳＲＡＭ）、Ｐｅｒｓｉｓｔｅｎｔ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＰＲＡＭ）、Ｆｅｒｒｏｅｌｅｃｔｒｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＦｅＲＡＭ）、Ｎｏｎ−Ｖｏｌａｔｉｌｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＮＶＲＡＭ）、Ｍａｇｎｅｔｏｒｅｓｉｓｔｉｖｅ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＭＲＡＭ）などのように、任意の多様なメモリである。メモリ１３０は、他のメモリタイプの任意の所望の組み合わせである。マシン１０５は、以下に説明するようにデデュープキャッシュ１３５を更に含む。
【００２７】
図１は、サーバ（サーバは、スタンドアロン（ｓｔａｎｄａｌｏｎｅ）又はラック（ｒａｃｋ）サーバの可能性あり）としてマシン１０５を図示するが、本発明の実施例は、制限なしに任意の所望のタイプのマシン１０５を含む。例えば、マシン１０５は、デスクトップ又はラップトップコンピュータ、或いは本発明の実施例から得られる任意の他のデバイスに代替される。マシン１０５は、特化された携帯コンピューティングデバイス、タブレットコンピュータ、スマートフォン、及び他のコンピューティングデバイスを含む。
【００２８】
図２は、図１のマシン１０５の追加の詳細事項を示す図である。図２において、一般的に、マシン１０５は一つ以上のプロセッサ１１０を含み、プロセッサ１１０はメモリコントローラ１２５及びクロック２０５を含み、クロック２０５はマシン１０５の構成要素の動作を調整するために利用される。プロセッサ１１０はメモリ１３０に連結され、メモリ１３０は、例としてＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、ＲＯＭ（ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、又は他の保存メディアを含む。プロセッサ１１０はストレージデバイス１２０及びネットワークコネクタ（ｃｏｎｎｅｃｔｏｒ）２１０に連結され、ネットワークコネクタ２１０は、例えば、イーサネット（登録商標）（Ｅｔｈｅｒｎｅｔ（登録商標））コネクタ又は無線コネクタである。プロセッサ１１０はバス２１５に連結され、バス２１５には、他の構成要素の中のユーザーインターフェース２２０及び入出力（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）エンジン２２５を利用して管理される入出力ポートが付着される。
【００２９】
図３は、図１のデデュープキャッシュ１３５の例示的なレイアウトを示す図である。図３において、デデュープキャッシュ１３５は、４つの一般的な構成要素に分割される。即ち、ＤＲＡＭ３０５、キャッシュコントローラ３１０、ホスト層（ｌａｙｅｒ）３１５、メディア層３２０である。ＤＲＡＭ３０５は、デデュープキャッシュ１３５に対して、実際のメモリとして動作し、三つの領域に分割される。即ち、デデュープ可能なリードキャッシュ３２５、非デデュープ可能なライトバッファ３３０、メタデータ領域３３５である。デデュープ可能なリードキャッシュ３２５は、プロセッサ１１０によって、デデュープキャッシュ１３５からリードされるデータを格納するためのデデュープメモリとして使用される。非デデュープ可能なライトバッファ３３０は、プロセッサ１１０からライトされるデータを格納するための従来の（即ち、非デデュープ）メモリとして使用される。メタデータ領域３３５は、デデュープ可能なリードキャッシュ３２５及び非デデュープ可能なライトバッファ３３０のキャッシュライン（ｃａｃｈｅ  ｌｉｎｅｓ）に関する情報を格納する。例えば、メタデータ領域３３５は、どのようなキャッシュラインが有効であるか否か、及びどのようなキャッシュラインがバックエンド大容量メモリ１３０にライトするためにバッファリング（ｂｕｆｆｅｒｉｎｇ）されるかを格納する。図３には、デデュープエンジンを示していないが、デデュープエンジンは、デデュープ可能なリードキャッシュ３２５に対する実際のデータのライトを管理する。即ち、デデュープエンジンは、図４を参照して以下で説明される。デデュープ可能なリードキャッシュ３２５、非デデュープ可能なライトバッファ３３０、及びメタデータ領域３３５は、ＤＲＡＭ３０５の任意の所望の割合を含む。例えば、ＤＲＡＭ３０５が合計８ギガバイト（ＧＢ）を含む場合、デデュープ可能なリードキャッシュ３２５お及び非デデュープ可能なライトバッファ３３０は、約４ＧＢのストレージをそれぞれ含む（メタデータ領域３３５は、相対的にＤＲＡＭ３０５の少ない量を要求する）。予想されるデデュープ率を考慮すると、デデュープ可能なリードキャッシュ３２５は、物理容量よりも大きな容量をシミュレーションする。例えば、デデュープ可能なリードキャッシュ３２５が、４ＧＢの物理メモリを含み、２．０のターゲットデデュープ率を有する場合、デデュープ可能なリードキャッシュ３２５は、８ＧＢの仮想メモリをシミュレーションする。デデュープキャッシュ１３５は、デデュープ可能なリードキャッシュ３２５の仮想容量だけキャッシュラインをサポートし、これはデデュープ可能なリードキャッシュ３２５の物理的な容量でサポート可能なキャッシュラインの数を超える。
【００３０】
図３は、デデュープ可能なリードキャッシュ３２５及び非デデュープ可能なライトバッファ３３０の両方を含むＤＲＡＭ３０５を図示してデデュープ可能なリードキャッシュ３２５及び非デデュープ可能なライトバッファ３３０の異なる機能を提供するが、一部の機能は重複する。例えば、本発明のいくつかの実施例において、非デデュープ可能なライトバッファ３３０は、プロセッサ１１０からライトされたデータを格納するが（そして最終的には、バックエンド大容量メモリ１３０にライトされる可能性あり）、非デデュープ可能なライトバッファ３３０は、「リードキャッシュ」として動作し（但し、デデュープ対象ではないとしても）、非デデュープ可能なライトバッファ３３０からデータがリードされる。従って、非デデュープ可能なライトバッファ３３０は、バックエンド大容量メモリ１３０にライトされるデータのための「一時的な（ｔｒａｎｓｉｅｎｔ）」ストレージ以上と見なされる。このような本発明の実施例において、特定のキャッシュラインに対してデデュープ可能なリードキャッシュ３２５をチェックすることへの任意の言及は、非デデュープ可能なライトバッファ３３０からのキャッシュラインのチェック及びデデュープ可能なリードキャッシュ３２５又は非デデュープライトバッファ３３０から適切にデータをリードすることで理解され、非デデュープ可能なライトバッファ３３０が一杯になるか非デデュープ可能なライトバッファ３３０のキャッシュラインが新たなキャッシュラインのためのスペースを作るために無効化される場合にのみ、データはバックエンド大容量メモリ１３０にライトされる。このような本発明の実施例において、データがデデュープ可能なリードキャッシュ３２５又は非デデュープ可能なライトバッファ３３０に格納されない場合にのみ、バックエンド大容量メモリ１３０は、要請されたデータに対してアクセスされる。
【００３１】
キャッシュコントローラ３１０は、デデュープキャッシュ１３５の背後から「頭脳」としての役割を担い、キャッシュコントローラ３１０は、どのようなデータがライトされるか又はリードされるかを管理して、無効化又はライトに対するキャッシュラインを選択するなどの役割を担う。キャッシュコントローラ３１０は、プロセッサ１１０と相互作用（即ち、プロセッサ１１０からの要請／データを受信してプロセッサ１１０にデータを送信）するためにホストレイヤー３１５を利用し、メモリ１３０（図３の「バックエンド大容量メモリ」と表示する）と相互作用するためにメディアレイヤー３２０を利用する。メモリ１３０は、デデュープキャッシュ１３５を含むモジュールの一部であるか、又はデデュープキャッシュ１３５から分離される（そして通信経路を介して通信される）。
【００３２】
図３に示したように、キャッシュコントローラ３１０、ホストレイヤー３１５、及びメディアレイヤー３２０は、ＦＰＧＡ（ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ｇａｔｅ  ａｒｒａｙ）を利用して具現される。しかし、本発明の実施例は、他のハードウェア設計（ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ  ＰＲＯＭ）、又はＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  ＰＲＯＭ）のような変形メモリ、或いは特別に設計された回路）及びソフトウェア設計を含む任意の所望の具現をサポートする。なお、図３は、単一のＦＰＧＡを用いて具現されたキャッシュコントローラ３１０、ホストレイヤー３１５、及びメディアレイヤー３２０を図示するが、本発明の実施例は、ネットワークの相互連結のような通信経路を使用して連結された、複数分割された構成要素を利用する具現をサポートする。
【００３３】
図４は、デデュープエンジンを有する図１のデデュープキャッシュ１３５を示す図である。図４において、ＤＲＡＭ３０５、キャッシュコントローラ３１０、ホストレイヤー３１５、及びメディアレイヤー３２０は、図３に示した構成要素と同じであり、メモリコントローラ１２５は、図１のメモリコントローラ１２５と同じである。しかし、図４は、その他に、デデュープエンジン４０５及びネットワークインターコネクト（ｉｎｔｅｒｃｏｎｎｅｃｔ）４１０を示す。ネットワークインターコネクト４１０は、ＤＲＡＭ３０５、キャッシュコントローラ３１０、及びデデュープエンジン４０５との間に通信を提供する。デデュープエンジン４０５は、デデュープメモリ（図３のデデュープ可能なリードキャッシュ３２５のような）を含むＤＲＡＭ３０５の部分からのデータのリードとＤＲＡＭ３０５の部分へのデータのライトを管理する（デデュープメモリを含まないＤＲＡＭ３０５の部分は、デデュープエンジン４０５を用いずに、直接にアクセスされる）。
【００３４】
上述したように、デデュープエンジン４０５は、デデュープメモリを管理する。このため、デデュープエンジン４０５は、デデュープエンジン４０５がデデュープを遂行するように指示する信号（図４の「Ｄｅｄｕｐ」と表示された信号）及びアクセスのためのアドレスと、使用のためのデータを明示するリード／ライトコマンド（図４の「ＲＤ／ＷＲ」と表示された信号）をサポートする。しかし、デデュープエンジン４０５は、またライト状態信号（図４の「ＷＲ＿Ｓｔａｔｕｓ」と表示された信号）を提供する。ライト状態信号は、特定のライト動作が成功であるか否かを示すことに利用される。ライト状態信号の利用については、図５を参照して、以下で更に説明する。
【００３５】
図５は、図３及び図４のキャッシュコントローラ３１０の詳細事項を示す図である。図５において、キャッシュコントローラ３１０は、リスクマネージャ５０５、キャッシュヒット／ミスチェック５１０、ヒットブロック５１５、ミスブロック５２０、及びヒストリーストレージ５２５を含む。図１のデデュープキャッシュ１３５によって、図１のプロセッサ１１０からのデータ要請を受信する場合、リスクマネージャ５０５は、データの従属性が正しく処理されるようにするために、リード後ライト及びライト後リードのようなコマンドの多様な順序を追跡する。例えば、キャッシュコントローラ３１０が、図３の非デデュープ可能なライトバッファ３３０に格納されたデータをライトする要請を受信し、図１のバックエンド大容量メモリ１３０にライトされる前に、そのデータをリードする要請を受信した場合、リスクマネージャ５０５は、図３の非デデュープ可能なライトバッファ３３０からのデータにアクセスするリード要請を伝達する。キャッシュヒット／ミスチェック５１０は、アクセスされる特定のアドレスが、図１のデデュープキャッシュ１３５から見つけ出されるか否かを判定する。これらの判定は、図３のメタデータ領域３３５にアクセスすることによって行われることから、キャッシュヒット／ミスチェック５１０は、図３のメタデータ領域３３５にアクセスするために、リード／ライト信号に従ってリード要請を伝送する。
【００３６】
キャッシュヒット／ミスチェック５１０が、特定の要請が既に図１のデデュープキャッシュ１３５に有るアドレスにアクセスするか否かを判定する場合、制御は適切にヒットブロック５１５又はミスブロック５２０に伝達される。ヒットブロック５１５は、図１のデデュープキャッシュ１３５に格納された現在のキャッシュラインにアクセスするために利用される。ミスブロック５２０は、図３のバックエンド大容量メモリ１３０からのデータにアクセスするために利用される。ヒットブロック５１５及びミスブロック５２０は、図３のＤＲＡＭ３０５に存在するデータにアクセスするためのリード／ライト信号に応じてリード及び／又はライト要請を伝送する。なお、ミスブロック５２０は、図４のデデュープエンジン４０５からライト状態の信号を受信する。最後に、ヒストリーストレージ５２５は、図１のデデュープキャッシュ１３５に有るキャッシュラインへのアクセスヒストリーに関する情報を判定するために利用される（例えば、適切な場合、キャッシュラインを除外することを選択するために）。また、図５に示したネットワークインターコネクトのように、多様なネットワークインターコネクトは、キャッシュコントローラ３１０の多様なエレメント間の通信をサポートする。
【００３７】
図３のデデュープキャッシュ１３５及びキャッシュコントローラ３１０のハードウェアを説明することで、図３のデデュープキャッシュ１３５の動作が説明される。図１のデデュープキャッシュ１３５が、図１のプロセッサ１１０からの要請を受信する場合、二つのタイプの要請及び二つの可能なキャッシュの結果がある。即ち、要請はリード又はライト要請であり、問題のデータは、キャッシュヒット又はキャッシュミスを引き起こす。従って、合計４つの発生可能な場合が存在し、それぞれの場合を以下で説明する。
【００３８】
≪リード要請、キャッシュヒット≫
【００３９】
図１のプロセッサ１１０がリード要請を発行し、データが現在の図３のデデュープ可能なリードキャッシュ３２５に格納されている場合、図５のキャッシュヒット／ミスチェック５１０は、図３のメタデータ領域３３５をリードした後に、この場合を判定する。問題のデータが現在の図３のデデュープ可能なリードキャッシュ３２５に存在していることから、制御は図５のヒットブロック５１５に伝達され、ヒットブロック５１５は、データが図３のデデュープ可能なリードキャッシュ３２５からリードされることを要請するリード要請を、図４のデデュープエンジン４０５に伝送する。図４のデデュープエンジン４０５はデータを図５のヒットブロック５１５に返し、ヒットブロック５１５はホストレイヤー３１５を介して図１のプロセッサ１１０にデータを返す。
【００４０】
≪リード要請、キャッシュミス≫
【００４１】
図１のプロセッサ１１０がリード要請を発行し、データが現在の図３のデデュープ可能なリードキャッシュ３２５に格納されていない場合、図５のキャッシュヒット／ミスチェック５１０は、図３のメタデータ領域３３５をリードした後に、この場合を判定する。問題のデータが現在の図３のデデュープ可能なリードキャッシュ３２５に存在していないことから、制御はミスブロック５２０に伝達され、ミスブロック５２０は、図３のメディアレイヤー３２０を介して図３のバックエンド大容量メモリ１３０からのデータを要請する。
【００４２】
データがリードされると、図５のミスブロック５２０は、図３のデデュープ可能なリードキャッシュ３２５に現在有効なデータを格納していないキャッシュラインが存在するか否かを判定する。図３のデデュープ可能なリードキャッシュ３２５に現在有効なデータを格納していない利用可能なキャッシュラインが存在する場合、図５のミスブロック５２０は、データを格納するためにそのようなキャッシュラインを選択する。そうでない場合、図５のミスブロック５２０は、図３のデデュープ可能なリードキャッシュ３２５から除去するための有効なデータを含むキャッシュラインを選択する。この選択プロセスは、図５のヒストリーストレージ５２５からのデータを利用し、除去するためのキャッシュラインを選択することに任意の所望のアルゴリズムを使用する。即ち、ＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）又はＬＦＵ（Ｌｅａｓｔ  Ｆｒｅｑｕｅｎｔｌｙ  Ｕｓｅｄ）は、除去するためのキャッシュラインを選択するために使用されるよく知られているアルゴリズムの例である。
【００４３】
図３のデデュープ可能なリードキャッシュ３２５からキャッシュラインを除去するために、図５のミスブロック５２０は、キャッシュラインが有効でないとしてマークすることを図３のメタデータ領域３３５にライトするために、図３のＤＲＡＭ３０５にライト動作を伝送する。ミスブロック５２０は、図３のデデュープ可能なリードキャッシュ３２５に実際のデータを上書きするために、図４のデデュープエンジン４０５にライト動作を伝送する。例えば、キャッシュラインを満たす（ｆｉｌｌ）ための十分な０（ｚｅｒｏ）の値をライトする。
【００４４】
キャッシュラインが除去されてデータが無効化されると、キャッシュラインが最初から利用可能であったように、キャッシュラインは自由にデータを受信する。従って、図５のミスブロック５２０は、データ（図１のバックエンド大容量メモリ１３０から先にリードされた）を、図３のデデュープ可能なリードキャッシュ３２５にライトするために、図４のデデュープエンジン４０５にライト動作を伝送する。図３のキャッシュコントローラ３１０は、図３のホストレイヤー３１５を介して図１のプロセッサ１１０にデータを返す。
【００４５】
≪ライト要請、キャッシュヒット≫
【００４６】
図１のプロセッサ１１０がライト要請を発行し、データが現在図３のデデュープ可能なリードキャッシュ３２５に格納されている場合、図５のキャッシュヒット／ミスチェック５１０は、図３のメタデータ領域３３５をリードした後に、この場合を判定する。問題のデータが現在図３のデデュープ可能なリードキャッシュ３２５に存在することから、制御はヒットブロック５１５に伝達される。
【００４７】
図３のデデュープ可能なリードキャッシュ３２５は、現在の交替されるデータを格納するため、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインのデータも処理しなければならない。新たなデータが、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインにライトされるが、デデュープメモリにデータをライトすることは、相対的に遅い動作である（そして、図１のバックエンド大容量メモリ１３０に格納されたデータは、いずれの場合でもアップデートされる必要がある）。従って、図３のデデュープ可能なリードキャッシュ３２５にデータをライトする代わりに、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインは無効化される。この方式で、データがプロセッサ１１０によって後でリードされると、新たな値は、図３の非デデュープ可能なライトバッファ３３０（依然としてそこに存在する場合）又は図１のバックエンド大容量メモリ１３０（上記「リード要請、キャッシュミス」と表示した場合で説明したように）からリトリーブ（ｒｅｔｒｉｅｖｅ）される。
【００４８】
図３のデデュープ可能なリードキャッシュ３２５からキャッシュラインを無効化するために、図５のヒットブロック５１５は、キャッシュラインを有効でないとしてマークすることを図３のメタデータ領域３３５にライトするために、図３のＤＲＡＭ３０５にライト動作を伝送する。ヒットブロック５１５は、図３のデデュープ可能なリードキャッシュ３２５に実際のデータを上書きするために、図４のデデュープエンジン４０５にライト動作を伝送する。例えば、キャッシュラインを満たす（ｆｉｌｌ）ための十分な０の値をライトする。
【００４９】
データが図３のデデュープ可能なリードキャッシュ３２５から無効化されると、図５のヒットブロック５１５は、図３の非デデュープ可能なライトバッファ３３０にデータをライトする。図３の非デデュープ可能なライトバッファ３３０が、デデュープメモリを使用しないため、図３の非デデュープ可能なライトバッファ３３０にデータをライトすることは、図３のデデュープ可能なリードキャッシュ３２５にデータをライトするよりも速い。その後、例えば図３の非デデュープ可能なライトバッファ３３０の両方が満た（ｆｉｌｌ）されると、適切な時間に、データは図３のメディアレイヤー３２０を介して図３の非デデュープ可能なライトバッファ３３０から図３のバックエンド大容量メモリ１３０にフラッシュ（ｆｌｕｓｈ）される。
【００５０】
≪ライト要請、キャッシュミス≫
【００５１】
図１のプロセッサ１１０がライト要請を発行し、データが現在図３のデデュープ可能なリードキャッシュ３２５に格納されていない場合、図５のキャッシュヒット／ミスチェック５１０は、図３のメタデータ領域３３５をリードした後、この場合を判定する。問題のデータが図３のデデュープ可能なリードキャッシュ３２５に存在していないことから、制御はミスブロック５２０に伝達される。
【００５２】
図５のミスブロック５２０は、図３の非デデュープ可能なライトバッファ３３０にデータをライトする。その後、例えば図３の非デデュープ可能なライトバッファ３３０の両方が満た（ｆｉｌｌ）されると、適切な時間で、データは図３のメディアレイヤー３２０を介して図３の非デデュープ可能なライトバッファ３３０から図３のバックエンド大容量メモリ１３０にフラッシュ（ｆｌｕｓｈ）される。
【００５３】
上記の説明は、全体的なパフォーマンスを向上させるために、キャッシュからどのようにしてデデュープ可能なメモリが利用されるかを示している。しかし、デデュープ可能なメモリの使用は、特にリード要請、キャッシュミス、ライト要請、及びキャッシュヒットの場合を引き起こす可能性のある他の問題を発生させる。このような二つの場合において、データは図３のデデュープ可能なリードキャッシュ３２５にライトされる。問題は、図３のデデュープ可能なリードキャッシュ３２５が物理的容量よりも大きな容量をシミュレーションするという事実から生じる。キャッシュラインが利用可能だとしても、図３のデデュープ可能なリードキャッシュ３２５の物理的メモリが全て満た（ｆｉｌｌ）され、このような場合、データは成功的に図３のデデュープ可能なリードキャッシュ３２５にライトされない可能性がある。なお、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインを無効化することは、任意の物理的メモリを確保していない可能性がある。例えば、無効化のために選択されたキャッシュラインが、他のキャッシュラインによって参照されているデータを参照する場合、選択されたキャッシュラインの無効化は、実際にはデータを図３のデデュープ可能なリードキャッシュ３２５の物理的メモリから解放しない。これらの問題は、ライト保証の欠如として説明される。
【００５４】
一つの解決策は、図３のデデュープ可能なリードキャッシュ３２５のライトが失敗することを単に許容することである。このような解決策は、少なくともリード要請、キャッシュミスの場合に合理的である。即ち、最悪の場合に、図１のバックエンド大容量メモリ１３０からのアクセスを要請し（少なくともデータが、図３のデデュープ可能なリードキャッシュ３２５に、実際にキャッシュされるまで）、少なくともデータが図３のデデュープ可能なリードキャッシュ３２５に実際にキャッシュされるまで、データは実際にキャッシュされない。そしてライト要請、キャッシュヒットの場合でも、同じデータにアクセスする全てのキャッシュラインを無効化する方法（図３のデデュープ可能なリードキャッシュ３２５から無効なデータ（ｓｔａｌｅ  ｄａｔａ）にアクセスするキャッシュラインへのアクセスを防ぐために）がある場合に解決策が受け入れられるが、他の解決策が存在する。
【００５５】
他の解決策は、データが成功的に図３のデデュープリードキャッシュ３２５にライトされるまで（又は再試みの臨界回数に到達するまで）、複数のキャッシュラインを無効化することである。図３のデデュープ可能なリードキャッシュ３２５にデータをライトすることを試みた後、図４のデデュープエンジン４０５がライト状態信号のＮＡＫを返した場合、図３のキャッシュコントローラ３１０（図５のヒットブロック５１５又は図５のミスブロック５２０を介して）は、無効化のための図３のデデュープ可能なリードキャッシュ３２５からのキャッシュラインを選択する。選択されたキャッシュラインが無効化された後、図３のキャッシュコントローラ３１０（再び、図５のヒットブロック５１５又は図５のミスブロック５２０を介して）は、図３のデデュープ可能なリードキャッシュ３２５に、元のライトを再び試みる。このようなプロセスは、図３のデデュープ可能なリードキャッシュ３２５にライトが成功するか（ライト状態信号のＡＣＫによって示されるように）又は再試みの臨界回数が発生するまでに必要なだけ反復される。
【００５６】
図６Ａ及び図６Ｂは、本発明の一実施形態による図１のデデュープキャッシュ１３５がライト要請を処理する例示的な手順のフローチャートである。図６Ａにおいて、６０５ステップで、図３のキャッシュコントローラ３１０は、図１のプロセッサ１１０からライト要請を受信する。６１０ステップで、図５のキャッシュヒット／ミスチェック５１０は、図３のデデュープ可能なリードキャッシュ３２５が上書きされるデータを含むキャッシュラインを含むか否かを判定する。そうでない場合、６１５ステップで、図５のミスブロック５２０は、図３の非デデュープ可能なライトバッファ３３０にライト要請からのデータを格納する。６２０ステップで、図３のキャッシュコントローラ３１０は、図３の非デデュープ可能なライトバッファ３３０から図１のバックエンド大容量メモリ１３０にデータをフラッシュする。そして６２５ステップで、図３のキャッシュコントローラ３１０は、図３の非デデュープ可能なライトバッファ３３０からのデータを削除する。
【００５７】
一方、６１０ステップで、図３のデデュープ可能なリードキャッシュ３２５がライト要請によって上書きされたデータを含むキャッシュラインを含む場合、６３０ステップで（図６Ｂ）、図５のヒットブロック５１５は、キャッシュラインを無効化する（図３のメタデータ領域３３５にキャッシュラインを有効でないとしてマークし、図４のデデュープエンジン４０５を介してキャッシュラインに０の値をライトすることにより）。６３５ステップで、図５のヒットブロック５１５は、図４のデデュープエンジン４０５が確認応答（ＡＣＫ）又は非確認応答（ＮＡＫ）信号に応答するか否かを判定する。図４のデデュープエンジン４０５がＡＣＫ信号を返した場合、処理は、ライト要請を完了するために図６Ａの６１５ステップに続く。図４のデデュープエンジン４０５がＮＡＫ信号を返した場合、６４０ステップで、図５のヒットブロック５１５は、再試みの最大回数に達したか否かを判定する。再試みの最大回数に達していない場合、６４５ステップで、図５のヒットブロック５１５は、無効化のために他のキャッシュラインを選択し、処理は、新たに選択されたキャッシュラインを無効化するために、６３０ステップに戻る。そうでない場合、６５０ステップで、ヒットブロック５１５（そして、図３のキャッシュコントローラ３１０）は、図３のデデュープ可能なリードキャッシュ３２５からのデータを削除する問題があったとして報告し、その後、処理は終了する。
【００５８】
図７は、本発明の一実施形態による図１のデデュープキャッシュ１３５が図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインを無効化するための例示的な手順のフローチャートである。図７において、７０５ステップで、図３のキャッシュコントローラ３１０は、図３のメタデータ領域３３５にキャッシュラインを有効でないとしてマークする（適切な値を図３のメタデータ領域３３５にライトすることにより）。７１０ステップで、図３のキャッシュコントローラ３１０は、無効なデータがＤＲＡＭのスペースを占有しないように、問題のキャッシュラインのデータに０の値をライトするために図４のデデュープエンジン４０５にライト要請を伝送する。
【００５９】
図８Ａ〜図８Ｃは、本発明の一実施形態による図１のデデュープキャッシュ１３５がリード要請を処理する例示的な手順のフローチャートである。図８Ａにおいて、８０５ステップで、図３のキャッシュコントローラ３１０は、図１のバックエンド大容量メモリ１３０（又は図３のＤＲＡＭ３０５にデータが格納される場合、図３のＤＲＡＭ３０５）からデータをリードするためのリード要請を受信する。８１０ステップで、図５のキャッシュヒット／ミスチェック５１０は、要請されたデータが、図３のデデュープ可能なリードキャッシュ３２５で検出されるか否かをチェックする。要請されたデータが、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインで発見された場合、８１５ステップで、図５のヒットブロック５１５は、要請されたデータを、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインからリードするために図４のデデュープエンジン４０５にリード要請を伝送し、８２０ステップで、図３のキャッシュコントローラ３１０は、要請されたデータを、図１のプロセッサ１１０に再び伝送し、その後、処理は終了する。
【００６０】
要請されたデータは、図３のデデュープ可能なリードキャッシュ３２５又は非デデュープ可能なライトバッファ３３０のキャッシュラインで発見されない場合、８２５ステップで、図５のミスブロック５２０は、図１のバックエンド大容量メモリ１３０からデータをリードする。８３０ステップで、図５のミスブロック５２０は、データを格納するために図３のデデュープ可能なリードキャッシュ３２５からのキャッシュラインを選択する。選択されたキャッシュラインは、現在の有効なデータを格納していないキャッシュラインであるか、又は有効なデータを格納しているキャッシュライン（従って、先に無効化が必要である）である。８３５ステップで（図８Ｂ）、図５のミスブロック５２０は、選択されたキャッシュラインが有効なデータを含むか否かを判定する。選択されたキャッシュラインが有効なデータを含む場合、８４０ステップで、図５のミスブロック５２０は、上記の図７で記述した例示的な手順を用いて、キャッシュラインを無効化する。キャッシュラインが有効なデータを含んでいない場合、８４５ステップで、図５のミスブロック５２０は、図３のデデュープ可能なリードキャッシュ３２５の選択されたキャッシュラインに要請されたデータをライトするために、図４のデデュープエンジン４０５にライト要請を伝送する。即ち、８４５ステップで、図５のミスブロック５２０は、図３のデデュープ可能なリードキャッシュ３２５の選択されたキャッシュラインに要請されたデータをライトすることを試みるために、図４のデデュープエンジン４０５に要請されたデータを提供する。
【００６１】
８５０のステップで、図５のミスブロック５２０は、図４のデデュープエンジン４０５がライト要請に応答してＡＣＫ又はＮＡＫのいずれを返すかを判定する。図３のデデュープ可能なリードキャッシュ３２５が自由なキャッシュラインを有していても最大物理的容量に到達した可能性がある場合、図４のデデュープエンジン４０５は、８３５ステップで選択されたキャッシュラインが有効なデータを含んでいるか否かに拘らず、ＮＡＫを返す。図４のデデュープエンジン４０５がＡＣＫ信号を返した場合、ライトは成功したことを示す。即ち、８５５ステップで、図５のミスブロック５２０は、図３のメタデータ領域３３５にキャッシュラインを有効なデータを含んでいるとしてマークし、処理は、図１のプロセッサ１１０に要請されたデータを送り返すために図８Ａの８２０ステップに続く。
【００６２】
一方、図４のデデュープエンジン４０５がＮＡＫ信号を返した場合、図４のデデュープエンジン４０５は、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインにデータをライトすることができなかったことを示す。このような場合、８６０ステップで（図８Ｃ）、図５のミスブロック５２０は、再試みの最大回数に達したか否かを判定する。再試みの最大回数がまだ達していない場合、８６５ステップで、図５のミスブロック５２０は、無効化のための他のキャッシュラインを選択し、処理は、新たに選択されたキャッシュラインを無効化するために８４０ステップに戻る。そうでない場合、８７０ステップで、ミスブロック５２０（そして、図３のキャッシュコントローラ３１０）は、図３のデデュープ可能なリードキャッシュ３２５にデータをライトすることに問題が生じたと報告し、その後の処理は終了する。
【００６３】
図３を参照して上述したように、本発明のいくつかの実施例において、図３の非デデュープ可能なライトバッファ３３０は、図３のデデュープ可能なリードキャッシュ３２５と共に、既存のキャッシュとして動作する。このような本発明の実施例において、要請されたキャッシュラインのために図３のデデュープ可能なリードキャッシュ３２５をチェックするか又はアクセスすることは、同様に図３の非デデュープ可能なライトバッファ３３０をチェックするか又はアクセスすることを含むものと理解される。例えば、図８Ａにおいて、８１０ステップはデータを含むキャッシュラインのために図３のデデュープ可能なリードキャッシュ３２５及び図３の非デデュープ可能なライトバッファ３３０の両方をチェックするために修正され、８１５ステップは、実際にデータがどこで発見されるかに応じて、図３のデデュープ可能なリードキャッシュ３２５又は図３の非デデュープ可能なライトバッファ３３０のキャッシュラインからデータをリードすることで修正される。同様に、図８Ｃの８７０ステップにおいて、データが成功的に図３のデデュープ可能なリードキャッシュ３２５にライトされていない場合、データは代わりに、図３の非デデュープ可能なライトバッファ３３０にライトされる。或いは、例示のフローチャートは、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインに、先にデータをライトすることを試みるよりも、図３のデデュープ可能なリードキャッシュ３２５又は図３の非デデュープ可能なライトバッファ３３０からのデータがライトされるキャッシュラインを選択することで修正される。
【００６４】
図６Ａ〜図８Ｃにおいて、本発明のいくつかの実施例を示した。しかし、本技術分野における熟練した者は、ステップの順序を変えたり、ステップを省略したり、図面に示されていない関係を含むことにより、本発明の他の実施例が可能であることを認めるはずである。明示的に説明されるか又は説明されていないとしても、このようなフローチャートの全ての変形は、本発明の実施例として考慮される。
【００６５】
本発明の実施例は、先行技術よりもいくつかの技術的利点を提供する。先ず、図１のデデュープャッシュ１３５のデデュープ可能なメモリの使用は、より多くの（ユニークな）データが同一の物理的量のメモリに格納されるようにしながら（又は、同じ量のデータを格納するために、より少ないメモリスペースを使用しながら）、複数のコピーの同じデータが図３のキャッシュＤＲＡＭ３０５に格納されることを防ぐ。例えば、図３のデデュープ可能なリードキャッシュ３２５が二つの予想されたデデュープ率を有する４ＧＢのメモリを含む場合、図３のデデュープ可能なリードキャッシュ３２５は、理論的に８ＧＢの非デデュープ可能なキャッシュメモリに格納されるようなユニークなデータが格納される。二番目に、図３の非デデュープ可能なライトバッファ３３０を使用することにより、アプリケーションがデータをライトしている状況について（単にデータをリードする状況よりも）デデュープ可能なメモリへのライト固有の遅延が防止される。三番目に、保証されていない図３のデデュープ可能なリードキャッシュ３２５へのライトに対する懸念は、図３のデデュープ可能なリードキャッシュ３２５のキャッシュラインを無効化させた後のライトの再試みをサポートすることにより、減少する（図３のデデュープ可能なリードキャッシュ３２５へのライトがいくつかのキャッシュライン無効化の後にも成功しない可能性が依然として存在するが、このような発生の可能性は非常に低い）。
【００６６】
以下の内容は、本発明の特定の実施例が具現される適切なマシン又はマシンの簡略で一般的な説明を提供するためのものである。マシン又は複数のマシンは、他のマシンから受信された指示、バーチャルリアリティー（ＶＲ：  ｖｉｒｔｕａｌ  ｒｅａｌｉｔｙ）環境との相互作用、生体フィードバック、又は他の入力信号によるものだけではなく、キーボード、マウスなどのような従来の入力デバイスからの入力により、少なくともある程度は制御される。本明細書で使用するように、用語「マシン」は、単一のマシン、バーチャルマシン、マシンとの通信に連結されたシステム、複数のバーチャルマシン、又は共に動作するデバイスを包括的に含むことを意味する。例示的なマシンは、例えば自動車、電車、タクシーのような私的又は公的運送手段のような運送装置だけでなく、パーソナルコンピュータ、ワークステーション、サーバ、ポータブルコンピュータ、携帯デバイス、電話器、タブレットのようなコンピューティングデバイスを含む。
【００６７】
マシン又は複数のマシンは、プログラム可能な、又はプログラム可能でないロジックデバイス若しくはロジックアレイ、アプリケーション特定用途向け集積回路（ＡＳＩＣｓ：Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔｓ）、エンベデッドコンピュータ、スマートカードなどのようなエンベデッドコントローラを含む。マシン又は複数のマシンは、ネットワークインターフェース、モデム、又は他の通信連結を介して一つ以上のリモートマシンに一つ以上の連結を活用する。複数のマシンは、イントラネット、インターネット、ローカルエリアネットワーク、広域ネットワークなどのような物理的及び／又は論理的ネットワークを利用して相互連結される。通常の技術者は、ネットワーク通信が高周波（ＲＦ）、衛星、マイクロ波（ｍｉｃｒｏｗａｖｅ）、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）８０２．１１、ブルートゥース（登録商標）（Ｂｌｕｅｔｏｏｔｈ（登録商標））、光、赤外線、ケーブル、レーザーなどを含む多様な有線及び／又は無線の近距離又は遠距離キャリア及びプロトコル（ｐｒｏｔｏｃｏｌ）を活用することができることを理解するだろう。
【００６８】
本発明の実施例は、機能、手順、データ構造、アプリケーションプログラムなどを含む関連するデータのように、又は関連するデータを参照することにより説明される。関連するデータは、マシンによってアクセスされる場合、マシンがタスクを遂行するか、或いは抽象的データ型又は下位レベルのハードウェアコンテキスト（ｃｏｎｔｅｘｔｓ）を定義する。関連するデータは、例えばＲＡＭ、ＲＯＭなどの揮発性及び／又は不揮発性メモリ、又はハードドライブ、フロッピー（登録商標）ディスク、光学ストレージ、テープストレージ、メモリカード、デジタルビデオディスク、生物学的ストレージなどを含む他のストレージデバイス及び関連するストレージメディアに格納される。関連するデータは、パケット（ｐａｃｋｅｔｓ）、シリアルデータ、並列データ、伝播される信号などの形態で物理的及び／又は論理的ネットワークを含む伝送環境を通じて伝達され、圧縮又は暗号化された形態で用いられる。関連するデータは、分散環境で用いられ、マシンのアクセスのためにローカル（ｌｏｃａｌ）及び／又はリモートで格納される。
【００６９】
本発明の実施例は、一つ以上のプロセッサによって実行されるコマンドを含むタイプのマシンリード可能な非一時的な記録媒体を含む。コマンドは、本明細書で説明したように、本発明のエレメントを遂行するコマンドを含む。
【００７０】
上述した多様な方法の動作は、多様なハードウェア及び／又はソフトウェア構成（複数可）、回路（複数可）、及び／又はモジュール（複数可）のように、動作を遂行する適切な手段によって遂行される。ソフトウェアは、論理的な機能を遂行するための実行コマンドの順序リストを含み、シングル又はマルチコアプロセッサ、又はプロセッサを含むシステムのように、コマンドの実行システム、装置、又はデバイスによって、或いは連結されて使用されるための任意の「プロセッサ可読媒体」に含まれる。
【００７１】
本明細書で開示した実施例に関連して説明したステップ、方法のステップ又はアルゴリズム及び機能は、ハードウェアで、プロセッサによって実行されるソフトウェアモジュールで、又はその両方の組み合わせで直接に具現される。ソフトウェアで具現される場合、機能は、コンピュータ読み取り可能な記録媒体に一つ以上のコマンド又はコードとして格納又は伝送される。ソフトウェアモジュールは、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）、ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）、レジスタ、ハードディスク、リムーバブル（ｒｅｍｏｖａｂｌｅ）ディスク、ＣＤ−ＲＯＭ、又は知られている任意の他の形態の記憶媒体で有る。
【００７２】
上述した実施例を参照して、本発明の原理を説明したように、説明した実施例は、このような原理から逸脱せずに配置及び詳細事項において変形され、任意の方法で結合される。そして、上述した内容は、特定の実施例に焦点を合わせたとしても、他の構成が考慮される。特に、「本発明の一つの実施例によれば」のような表現又は本明細書で使用したこのような表現でも、このようなフレーズは、一般的に可能な実施例を参照するための意味であり、本発明を特定の実施例の構成に限定しようとするものではない。本明細書で使用したように、このような用語は、他の実施例に結合される同一又は他の実施例を参照する。
【００７３】
上述した実施例は、本発明を制限するものとして解釈されない。いくつかの実施例を説明したが、通常の技術者は、本発明の新たなティーチング（ｔｅａｃｈｉｎｇ）及び利点から逸脱しない実施例について多様な変形を容易にする。これにより、このような変形は、本発明の権利範囲に含まれるものとして意図される。
【００７４】
本発明の実施例は、制限なしで、次のようなステートメントに拡張される。
【００７５】
ステートメント１．本発明の一実施例によるデデュープ可能なキャッシュは、
デデュープ可能なリード（ｒｅａｄ）キャッシュ及び非デデュープ可能なライト（ｗｒｉｔｅ）バッファを含むキャッシュメモリと、デデュープ可能なリードキャッシュを利用してデータのリード（ｒｅａｄ）及びライト（ｗｒｉｔｅ）を管理し、デデュープ可能なリードキャッシュへのライト要請が成功したか否かを示すライト状態信号を伝送するデデュープエンジンと、キャッシュコントローラと、を備え、キャッシュコントローラは、要請に含まれるアドレスがデデュープ可能なリードキャッシュで発見されるか否かをチェックするキャッシュヒット／ミスチェックロジックと、アドレスがデデュープ可能なリードキャッシュで発見されることをキャッシュヒット／ミスチェックロジックが示す場合、キャッシュメモリの第１データにアクセスするヒットブロックと、アドレスがデデュープ可能なリードキャッシュで発見されないことをキャッシュヒット／ミスチェックロジックが示す場合、バックエンド大容量メモリの第２データにアクセスするミスブロックと、デデュープ可能なリードキャッシュの第１データへのアクセスに関する情報を格納するヒストリーストレージと、を含む。
【００７６】
ステートメント２．ステートメント１によるデデュープ可能なキャッシュにおいて、キャッシュコントローラは、デデュープ可能なリードキャッシュ及び非デデュープ可能なライトバッファにおけるデータの従属性を管理するリスクマネージャと、を更に含む。
【００７７】
ステートメント３．ステートメント１によるデデュープ可能なキャッシュにおいて、デデュープ可能なリードキャッシュは、デデュープ可能なリードキャッシュに物理的に適合するものよりもより多くのキャッシュラインを格納することをシミュレーションする。
【００７８】
ステートメント４．ステートメント１によるデデュープ可能なキャッシュにおいて、キャッシュメモリは、デデュープ可能なリードキャッシュのキャッシュラインに関する情報を格納するメタデータ領域を更に含む。
【００７９】
ステートメント５．ステートメント１によるデデュープ可能なキャッシュにおいて、キャッシュコントローラは、データをライトするための第１ライト要請をプロセッサから受信し、非デデュープ可能なライトバッファにデータを格納し、ヒットブロックは、デデュープ可能なリードキャッシュのキャッシュラインが第１ライト要請によって修正される場合、キャッシュラインを無効化させるようにデデュープエンジンに第２ライト要請を伝送する。
【００８０】
ステートメント６．ステートメント５によるデデュープ可能なキャッシュにおいて、第２ライト要請は、デデュープ可能なリードキャッシュのキャッシュラインに０の値をライトする要請を含む。
【００８１】
ステートメント７．ステートメント５によるデデュープ可能なキャッシュにおいて、キャッシュコントローラは、キャッシュメモリのメタデータ領域にキャッシュラインが有効でないとしてマークする。
【００８２】
ステートメント８．ステートメント５によるデデュープ可能なキャッシュにおいて、ヒットブロックは、第２ライト要請に応答するデデュープエンジンから非確認応答（ＮＡＫ）信号を受信してデデュープ可能なリードキャッシュから第２キャッシュラインを除去し、デデュープ可能なリードキャッシュから第２キャッシュラインを除去した後にデデュープエンジンに第２ライト要請を再び伝送する。
【００８３】
ステートメント９．ステートメント１によるデデュープ可能なキャッシュにおいて、キャッシュコントローラは、データをリードするためのリード要請をプロセッサから受信してプロセッサにデータを伝送し、ミスブロックは、バックエンド大容量メモリからデータをリトリーブ（ｒｅｔｒｉｅｖｅ）し、デデュープ可能なリードキャッシュにデータをライトするためにデデュープエンジンにライト要請を伝送する。
【００８４】
ステートメント１０．ステートメント９によるデデュープ可能なキャッシュにおいて、ミスブロックは、ライト要請に応答するデデュープエンジンから非確認応答（ＮＡＫ）信号を受信してデデュープ可能なリードキャッシュからキャッシュラインを除去し、デデュープ可能なリードキャッシュからキャッシュラインを除去した後にデデュープエンジンにライト要請を再び伝送する。
【００８５】
ステートメント１１．本発明の一実施形態によるキャッシュコントローラの動作方法は、データをライトするためのライト要請を受信するステップと、データがデデュープ可能なリードキャッシュのキャッシュラインに存在すると判定するステップと、デデュープ可能なリードキャッシュのキャッシュラインを無効化するステップと、データを非デデュープ可能なライトバッファに格納するステップと、を有し、デデュープ可能なリードキャッシュは、キャッシュメモリの第１領域であり、キャッシュメモリは、第２領域として非デデュープ可能なライトバッファを含む。
【００８６】
ステートメント１２．ステートメント１１による方法において、方法は、非デデュープ可能なライトバッファからバックエンド大容量メモリにデータをフラッシュ（ｆｌｕｓｈ）するステップと、非デデュープ可能なライトバッファからデータを削除するステップと、を更に含む。
【００８７】
ステートメント１３．ステートメント１１による方法において、デデュープ可能なリードキャッシュのキャッシュラインを無効化するステップは、キャッシュメモリのメタデータ領域にキャッシュラインが有効でないとしてマークするステップと、デデュープエンジンを介してキャッシュラインに０の値をライトするステップと、を含む。
【００８８】
ステートメント１４．ステートメント１３による方法において、デデュープ可能なリードキャッシュのキャッシュラインを無効化するステップは、デデュープエンジンからライト状態信号の確認応答（ＡＣＫ）を受信するステップと、を更に含む。
【００８９】
ステートメント１５．ステートメント１３による方法において、デデュープ可能なリードキャッシュのキャッシュラインを無効化するステップは、デデュープエンジンからライト状態信号の非確認応答（ＮＡＫ）を受信するステップと、デデュープ可能なリードキャッシュから除去する第２キャッシュラインを選択するステップと、第２キャッシュラインを無効化するステップと、デデュープエンジンを介して第２キャッシュラインに０の値をライトするステップと、を更に含む。
【００９０】
ステートメント１６．ステートメント１１による方法において、データを非デデュープ可能なライトバッファに格納するステップは、データがデデュープ可能なリードキャッシュのキャッシュラインに存在するか否かに拘らず、データを非デデュープ可能なライトバッファに格納するステップを含む。
【００９１】
ステートメント１７．本発明の他の実施形態によるキャッシュコントローラの動作方法は、データをリードするためのリード要請を受信するステップと、データがデデュープ可能なリードキャッシュの複数のキャッシュラインに存在しないと判定するステップと、バックエンド大容量メモリからデータをリードするステップと、デデュープ可能なリードキャッシュの第１キャッシュラインを選択するステップと、データを第１キャッシュラインにライトすることを試みるためにデデュープエンジンにデータを提供するステップと、リード要請に応答してデータを伝送するステップと、を有し、デデュープ可能なリードキャッシュは、キャッシュメモリの第１領域であり、キャッシュメモリは、第２領域として非デデュープ可能なライトバッファを含む。
【００９２】
ステートメント１８．ステートメント１７による方法において、デデュープ可能なリードキャッシュの第１キャッシュラインを選択するステップは、デデュープ可能なリードキャッシュから現在データを格納していない第１キャッシュラインを選択するステップを含む。
【００９３】
ステートメント１９．ステートメント１７による方法において、デデュープ可能なリードキャッシュの第１キャッシュラインを選択するステップは、キャッシュメモリのメタデータ領域からのデデュープ可能なリードキャッシュメタデータ及びヒストリーデータに応答して、デデュープ可能なリードキャッシュから除去するために現在有効なデータを格納している第１キャッシュラインを選択するステップと、第１キャッシュラインを無効化するステップと、を含む。
【００９４】
ステートメント２０．ステートメント１９による方法において、第１キャッシュラインを無効化するステップは、キャッシュメモリのメタデータ領域に第１キャッシュラインを有効でないとしてマークするステップと、デデュープエンジンを介して第１キャッシュラインに０の値をライトするステップと、を含む。
【００９５】
ステートメント２１．ステートメント１７による方法において、データを第１キャッシュラインにライトすることを試みるためにデデュープエンジンにデータを提供するステップは、デデュープエンジンからライト状態信号の確認応答（ＡＣＫ）を受信するステップを含む。
【００９６】
ステートメント２２．ステートメント１７による方法において、データを第１キャッシュラインにライトすることを試みるためにデデュープエンジンにデータを提供するステップは、デデュープエンジンからライト状態信号の非確認応答（ＮＡＫ）を受信するステップと、キャッシュメモリのメタデータ領域からのデデュープ可能なリードキャッシュメタデータ及びヒストリーデータに応答して、デデュープ可能なリードキャッシュから除去するために現在有効なデータを格納している第２キャッシュラインを選択するステップと、第２キャッシュラインを無効化するステップと、データを選択された第２キャッシュラインにライトすることを試みるためにデデュープエンジンにデータを提供するステップと、を含む。
【００９７】
ステートメント２３．本発明の一実施形態による非一時的記憶媒体は、格納されたコマンドを含み、コマンドがマシンによって実行される場合、コマンドは、データをライトするためのライト要請を受信し、データがデデュープ可能なリードキャッシュのキャッシュラインに存在すると判定し、デデュープ可能なリードキャッシュのキャッシュラインを無効化し、データを非デデュープ可能なライトバッファに格納することを惹起し、デデュープ可能なリードキャッシュは、キャッシュメモリの第１領域であり、キャッシュメモリは、第２領域として非デデュープ可能なライトバッファを含む。
【００９８】
ステートメント２４．ステートメント２３による非一時的記憶媒体において、コマンドは、非デデュープ可能なライトバッファからバックエンド大容量メモリにデータをフラッシュ（ｆｌｕｓｈ）し、非デデュープ可能なライトバッファからデータを削除することを惹起する。
【００９９】
ステートメント２５．ステートメント２３による非一時的記憶媒体において、デデュープ可能なリードキャッシュのキャッシュラインを無効化することは、キャッシュメモリのメタデータ領域にキャッシュラインが有効でないとしてマークし、デデュープエンジンを介してキャッシュラインに０の値をライトすることを含む。
【０１００】
ステートメント２６．ステートメント２５による非一時的記憶媒体において、デデュープ可能なリードキャッシュのキャッシュラインを無効化することは、デデュープエンジンからライト状態信号の確認応答（ＡＣＫ）を受信することを更に含む。
【０１０１】
ステートメント２７．ステートメント２５による非一時的記憶媒体において、デデュープ可能なリードキャッシュのキャッシュラインを無効化することは、デデュープエンジンからライト状態信号の非確認応答（ＮＡＫ）を受信し、デデュープ可能なリードキャッシュから除去する第２キャッシュラインを選択し、第２キャッシュラインを無効化し、デデュープエンジンを介して第２キャッシュラインに０の値をライトすることを更に含む。
【０１０２】
ステートメント２８．ステートメント２３による非一時的記憶媒体において、データを非デデュープ可能なライトバッファに格納することは、データがデデュープ可能なリードキャッシュのキャッシュラインに存在するか否かに拘らず、データを非デデュープ可能なライトバッファに格納することを含む。
【０１０３】
ステートメント２９．本発明の他の実施形態による非一時的記憶媒体は、格納されたコマンドを含み、コマンドがマシンによって実行される場合、コマンドは、データをリードするためのリード要請を受信し、データがデデュープ可能なリードキャッシュの複数のキャッシュラインに存在しないと判定し、バックエンド大容量メモリからデータをリードし、デデュープ可能なリードキャッシュの第１キャッシュラインを選択し、データを第１キャッシュラインにライトすることを試みるためにデデュープエンジンにデータを提供し、リード要請に応答してデータを伝送することを惹起し、デデュープ可能なリードキャッシュは、キャッシュメモリの第１領域であり、キャッシュメモリは、第２領域として非デデュープ可能なライトバッファと、を含む。
【０１０４】
ステートメント３０．ステートメント２９による非一時的記憶媒体において、デデュープ可能なリードキャッシュの第１キャッシュラインを選択することは、デデュープ可能なリードキャッシュから現在データを格納していない第１キャッシュラインを選択することを含む。
【０１０５】
ステートメント３１．ステートメント２９による非一時的記憶媒体において、デデュープ可能なリードキャッシュの第１キャッシュラインを選択することは、キャッシュメモリのメタデータ領域からのデデュープ可能なリードキャッシュメタデータ及びヒストリーデータに応答して、デデュープ可能なリードキャッシュから除去するために現在有効なデータを格納している第１キャッシュラインを選択し、第１キャッシュラインを無効化することを含む。
【０１０６】
ステートメント３２．ステートメント３１による非一時的記憶媒体において、第１キャッシュラインを無効化することは、キャッシュメモリのメタデータ領域に第１キャッシュラインを有効でないとしてマークし、デデュープエンジンを介して第１キャッシュラインに０の値をライトすることを含む。
【０１０７】
ステートメント３３．ステートメント２９による非一時的記憶媒体において、データを第１キャッシュラインにライトすることを試みるためにデデュープエンジンにデータを提供することは、デデュープエンジンからのライト状態信号の確認応答（ＡＣＫ）を受信することを含む。
【０１０８】
ステートメント３４．ステートメント２９による非一時的記憶媒体において、データを第１キャッシュラインにライトすることを試みるためにデデュープエンジンにデータを提供することは、デデュープエンジンからライト状態信号の非確認応答（ＮＡＫ）を受信し、キャッシュメモリのメタデータ領域からのデデュープ可能なリードキャッシュメタデータ及びヒストリーデータに応答して、デデュープ可能なリードキャッシュから除去するために現在有効なデータを格納している第２キャッシュラインを選択し、第２キャッシュラインを無効化し、データを選択された第２キャッシュラインにライトすることを試みるためにデデュープエンジンにデータを提供することを含む。
【０１０９】
以上、本発明の実施形態について図面を参照しながら詳細に説明したが、本発明は、上述の実施形態に限定されるものではなく、本発明の技術的範囲から逸脱しない範囲内で多様に変更実施することが可能である。
【産業上の利用可能性】
【０１１０】
本発明は、ライト遅延を防止できるデデュープ可能なメモリを用いるキャシングシステムに有用である。
【符号の説明】
【０１１１】
１０５    マシン
１１０    プロセッサ
１１５    デバイスドライバ
１２０    ストレージデバイス
１２５    メモリコントローラ
１３０    主メモリ（バックエンド大容量メモリ）
１３５    デデュープキャッシュ
２０５    クロック
２１０    ネットワークコネクタ
２１５    バス
２２０    ユーザーインターフェース
２２５    入出力エンジン
３０５    ＤＲＡＭ
３１０    キャッシュコントローラ
３１５    ホストレイヤー
３２０    メディアレイヤー
３２５    デデュープ可能なリードキャッシュ
３３０    非デデュープ可能なライトバッファ
３３５    メタデータ領域
４０５    デデュープエンジン
４１０    ネットワークインターコネクト
５０５    リスクマネージャ
５１０    キャッシュヒット／ミスチェック
５１５    ヒットブロック
５２０    ミスブロック
５２５    ヒストリーストレージ
【図１】
2019128949.tif 000003
【図２】
2019128949.tif 000004
【図３】
2019128949.tif 000005
【図４】
2019128949.tif 000006
【図５】
2019128949.tif 000007
【図６Ａ】
2019128949.tif 000008
【図６Ｂ】
2019128949.tif 000009
【図７】
2019128949.tif 000010
【図８Ａ】
2019128949.tif 000011
【図８Ｂ】
2019128949.tif 000012
【図８Ｃ】
2019128949.tif 000013