【手続補正書】
【提出日】令和2年2月13日(2020.2.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のハッシュテーブル（Ｈａｓｈ  ｔａｂｌｅ）の各々が、ハッシュ関数に対応し、前記複数のハッシュテーブルの各々が、複数の物理的なハッシュバケット（Ｈａｓｈ  ｂｕｃｋｅｔ）を含み、各々の物理的なハッシュバケットは、複数のハッシュウェイ（Ｗａｙｓ）を含み、データブロックを格納する、前記複数のハッシュテーブルを識別する段階と、
複数の仮想バケット（Ｖｉｒｔｕａｌ  ｂｕｃｋｅｔ）の各々が、前記複数の物理的なハッシュバケットの中の一部を含み、前記複数の仮想バケットの中で他の仮想バケットと少なくとも１つの前記物理的なハッシュバケットを共有する、前記複数の仮想バケットを識別する段階と、
前記複数の仮想バケットの中で対応する１つの仮想バケットに割当てられて格納されたデータブロックを有する前記複数の物理的なハッシュバケットの各々を識別する段階と、
ハッシュ値（Ｈａｓｈ  ｖａｌｕｅ）を生成するために複数のハッシュ関数の中で対応するハッシュ関数にしたがってデータライン（Ｄａｔａ  ｌｉｎｅ）をハッシング（Ｈａｓｈｉｎｇ）する段階と、
対応するハッシュテーブルの前記複数の仮想バケットの中で対応する仮想バケットが前記ハッシュ値にしたがってデータブロックのための使用可能な空間を有するか否かを決定する段階と、
前記複数の仮想バケットの中で対応する仮想バケットが使用可能な空間を有しない場合、前記仮想バケットの中で対応する仮想バケットが前記データブロックのための空間を有するようになるまで前記複数の仮想バケットの中で対応する仮想バケットから前記仮想バケットの中で隣接する仮想バケットに順次データブロックを移動させる段階と、
前記複数の仮想バケットの中で対応する仮想バケットに前記データブロックを格納する段階と、を含むメモリの重複除去方法。
【請求項２】
前記データブロックに対応する１つ以上の検索アドレス（Ｌｏｏｋｕｐ  ａｄｄｒｅｓｓｅｓ）を変更するためにアドレス検索テーブルメモリをアップデートする段階をさらに含むことを特徴とする請求項１に記載のメモリの重複除去方法。
【請求項３】
前記複数のハッシュテーブルの各々は、参照カウントライン（Ｒｅｆｅｒｅｎｃｅ  ｃｏｕｎｔ  ｌｉｎｅ）、署名ライン（Ｓｉｇｎａｔｕｒｅ  ｌｉｎｅ）、及びホップワードライン（Ｈｏｐｗｏｒｄ  ｌｉｎｅ）をさらに含むことを特徴とする請求項１に記載のメモリの重複除去方法。
【請求項４】
前記仮想バケットに対応するデータブロックを含む前記物理的なハッシュバケットを示すためのホップワードベクトル（Ｈｏｐｗｏｒｄ  ｖｅｃｔｏｒ）を生成する段階をさらに含むことを特徴とする請求項３に記載のメモリの重複除去方法。
【請求項５】
前記ホップワードベクトルを生成する段階は、
前記複数の仮想バケットの各々に対し、前記複数の仮想バケットの中の各々の仮想バケットの前記複数の物理的なハッシュバケットの各々が前記複数の仮想バケットの中の各々の仮想バケットと連動されるデータブロックを含むか否かを示すために二進表示子（Ｂｉｎａｒｙ  ｉｎｄｉｃａｔｏｒ）を使用する段階を含むことを特徴とする請求項４に記載のメモリの重複除去方法  。
【請求項６】
前記複数の物理的なハッシュバケットの中でデータブロックを含むいずれの物理的なハッシュバケットが前記複数の仮想バケットの中でいずれの仮想バケットに対応するかを示すために物理的なハッシュバケット毎にｌｏｇ２（Ｈ）ビットで構成されるホップワード値を生成する段階をさらに含むことを特徴とする請求項３に記載のメモリの重複除去方法。
【請求項７】
前記ホップワード値を生成する段階は、前記複数の物理的なハッシュバケット及び仮想バケットの対と関連して表現される位置にデータブロックを含む前記複数の物理的なハッシュバケットの各々のための準アドレスで構成される２次元アレイを生成する段階を含むことを特徴とする請求項６に記載のメモリの重複除去方法。
【請求項８】
前記対応するハッシュテーブルは、揮発性メモリに格納されることを特徴とする請求項１に記載のメモリの重複除去方法。
【請求項９】
前記揮発性メモリは、ＤＲＡＭ（Ｄｙｎａｍｉｃ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）を含むことを特徴とする請求項８に記載のメモリの重複除去方法。
【請求項１０】
前記対応するハッシュテーブルをｌｏｇ２（Ｈ）ビットの仮想バケット利用値フィールド及び前記複数の仮想バケットの中の対応する仮想バケットのデータブロックの数と同一である値を含む物理的なラインＩＤ（ＰＬＩＤ）で索引（Ｉｎｄｅｘｉｎｇ）する段階をさらに含むことを特徴とする請求項１に記載のメモリの重複除去方法。
【請求項１１】
前記複数の仮想バケットの中で対応する仮想バケットに項目を書き込む場合、前記仮想バケット利用値フィールドを１増加させる段階をさらに含むことを特徴とする請求項１０に記載のメモリの重複除去方法。
【請求項１２】
対応する前記ハッシュテーブルが一杯に満たされた場合、バッファメモリに前記データブロックを格納する段階をさらに含むことを特徴とする請求項１に記載のメモリの重複除去方法。
【請求項１３】
メモリでデータブロックの重複を減少させる重複除去メモリのための重複除去ＤＲＡＭ（Ｄｙｎａｍｉｃ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）メモリモジュールにおいて、
重複除去されたデータブロックのみを格納し、複数のハッシュテーブルの各々が、複数の物理的なハッシュバケットを含み、各々の物理的なハッシュバケットが、複数のハッシュウェイ（Ｗａｙｓ）を含み、データブロックを格納するように構成され、前記重複除去ＤＲＡＭメモリモジュールに格納されたハッシュテーブルの３次元アレイを含む、ハッシュテーブルメモリと、
前記重複除去されたデータブロックに対応するアドレスを格納するためのアドレス検索テーブルメモリと、
前記重複除去ＤＲＡＭメモリモジュールが前記ハッシュテーブルメモリから前記データブロックを検索し、前記データブロックを伝送するようにする読出し要求、または前記重複除去ＤＲＡＲＭメモリモジュールが前記ハッシュテーブルメモリに前記データブロックを格納するようにする書込み要求を受信するプロセッサと、を含むことを特徴とする重複除去ＤＲＡＭメモリモジュール。
【請求項１４】
チップ上で重複除去を実行し、重複除去ＤＲＡＭメモリモジュールの論理的な容量を増加させ、ホストプロセッサのリソースの使用を低減し、重複除去ＤＲＡＭメモリモジュールへのメモリアクセス数を低減することによりメモリを重複除去する重複除去ＤＲＡＭメモリモジュールであって、
前記重複除去ＤＲＡＭメモリモジュールは、
重複除去されたデータブロックのみを格納するためのハッシュテーブルメモリと、
前記重複除去されたデータブロックに対応するアドレスを格納するためのアドレス検索テーブルメモリと、
前記重複除去ＤＲＡＭメモリモジュールが前記ハッシュテーブルメモリから前記データブロックを検索し、前記データブロックを伝送するようにする読出し要求、または前記重複除去ＤＲＡＲＭメモリモジュールが前記ハッシュテーブルメモリの前記データブロックを格納するようにする書込み要求を受信するプロセッサと、を含むことを特徴とする重複除去ＤＲＡＭメモリモジュール。
【請求項１５】
前記ハッシュテーブルメモリは、揮発性メモリに格納され、前記ハッシュテーブルメモリに格納される複数のハッシュテーブルの３次元アレイを含み、前記ハッシュテーブルの各々は、複数の物理的なハッシュバケットを含み、各々の物理的なハッシュバケットは、複数のハッシュウェイ（Ｗａｙｓ）を含み、前記重複除去されたデータブロックを格納するように構成されることを特徴とする請求項１４に記載の重複除去ＤＲＡＭメモリモジュール。
【請求項１６】
前記複数のハッシュテーブルの各々は、複数の仮想バケットをさらに含み、各々の仮想バケットは、２つ以上の前記物理的なハッシュバケットを含むことを特徴とする請求項１３又は１５に記載の重複除去ＤＲＡＭメモリモジュール。
【請求項１７】
前記複数のハッシュテーブルの中の対応するハッシュテーブル内で前記複数の仮想バケットの中の隣接する仮想バケットの間で前記重複除去されたデータブロックを移動させることを特徴とする請求項１６に記載の重複除去ＤＲＡＭメモリモジュール。
【請求項１８】
外部から提供される命令無しでデータ重複除去を実行することを特徴とする請求項１３又は１５に記載の重複除去ＤＲＡＭメモリモジュール。
【請求項１９】
前記ハッシュテーブルメモリが一杯に満たされた場合、データブロックを格納するためのバッファメモリをさらに含むことを特徴とする請求項１３又は１５に記載の重複除去ＤＲＡＭメモリモジュール。
【請求項２０】
重複除去ＤＲＡＭ（Ｄｙｎａｍｉｃ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）メモリモジュールにおいて、
複数のハッシュテーブルの各々が、複数の物理的なハッシュバケットを含み、各々の物理的なハッシュバケットが、複数のハッシュウェイ（Ｗａｙｓ）を含み、データブロックを格納するように構成され、前記重複除去ＤＲＡＭメモリモジュールに格納されたハッシュテーブルの３次元アレイと、
プロセッサと、
メモリと、を含み、
前記メモリは、命令を格納し、前記命令が前記プロセッサによって実行される時、前記メモリは、前記重複除去ＤＲＡＭメモリモジュールが前記複数のハッシュテーブルの中で対応するハッシュテーブル内の隣接する仮想バケットの間で事前に格納された重複除去されたデータブロックを移動させるようにし、前記仮想バケットの各々は、２つ以上の物理的なハッシュバケットを含むことを特徴とする重複除去ＤＲＡＭメモリモジュール。
【請求項２１】
前記メモリは、命令をさらに格納し、前記命令が前記プロセッサによって実行される時、前記メモリは、重複除去ＤＲＡＭメモリモジュールが仮想バケットの中で前記事前に格納された重複除去されたデータブロックが移動された１つの仮想バケットにインカミングデータを格納するようにすることを特徴とする請求項２０に記載の重複除去ＤＲＡＭメモリモジュール。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
本発明の実施形態による重複除去メモリのためにメモリでデータブロックの重複を減少させる重複除去ＤＲＡＭ（Ｄｙｎａｍｉｃ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）メモリモジュールが提供され、重複除去ＤＲＡＭメモリモジュールは、重複除去されたデータブロックのみを格納し、複数のハッシュテーブルの各々が、複数の物理的なハッシュバケットを含み、各々の物理的なハッシュバケットが、複数のハッシュウェイ（Ｗａｙｓ）を含み、データブロックを格納するように構成され、前記重複除去ＤＲＡＭメモリモジュールに格納されたハッシュテーブルの３次元アレイを含む、ハッシュテーブルメモリと、前記重複除去されたデータブロックに対応するアドレスを格納するためのアドレス検索テーブルメモリと、前記重複除去ＤＲＡＭメモリモジュールが前記ハッシュテーブルメモリから前記データブロックを検索し、前記データブロックを伝送するようにする読出し要求、または前記重複除去ＤＲＡＲＭメモリモジュールが前記ハッシュテーブルメモリに前記データブロックを格納するようにする書込み要求を受信するプロセッサと、を含むことを特徴とする。
また、本発明の実施形態による重複除去ＤＲＡＭメモリモジュールは、チップ上で重複除去を実行し、重複除去ＤＲＡＭメモリモジュールの論理的な容量を増加させ、ホストプロセッサのリソースの使用を低減し、重複除去ＤＲＡＭメモリモジュールへのメモリアクセス数を低減することによりメモリを重複除去する重複除去ＤＲＡＭメモリモジュールであって、前記重複除去ＤＲＡＭメモリモジュールは、重複除去されたデータブロックのみを格納するためのハッシュテーブルメモリと、前記重複除去されたデータブロックに対応するアドレスを格納するためのアドレス検索テーブルメモリと、前記重複除去ＤＲＡＭメモリモジュールが前記ハッシュテーブルメモリから前記データブロックを検索し、前記データブロックを伝送するようにする読出し要求、または前記重複除去ＤＲＡＲＭメモリモジュールが前記ハッシュテーブルメモリの前記データブロックを格納するようにする書込み要求を受信するプロセッサと、を含むことを特徴とする。