JP6921936B2 - Ｓｉｍｄエンジンを用いる汎用データ圧縮 - Google Patents

Description

本発明は、その幾つかの実施形態において、データ圧縮に関し、より具体的には、排他的ではないが、単一命令多重データ処理（single instruction multiple data、ＳＩＭＤ）エンジンを用いるデータ圧縮に関する。

データ圧縮は、データを格納する記憶空間及び／又はデータを転送するネットワーク帯域幅を削減するために、記憶及び／又は転送のデータ容量を削減するよう、複数のアプリケーションで広く使用される。

データ圧縮は、データの元の表現より少ないビットを用いてデータを符号化することを含む。データ圧縮は記憶及び／又はネットワーキング資源を有意に削減するが、追加処理及び／又は計算資源、例えば処理エンジン、メモリリソース、及び／又は処理時間を必要とし得る。多くのデータ圧縮方法、技術、及び／又はアルゴリズムが現在利用可能であり、それぞれ、圧縮率と必要処理リソースとの間のトレードオフを使用する。

本発明の第１の態様によると、入力データストリームを圧縮して圧縮出力データストリームを生成するシステムであって、ハッシュテーブルを格納するメモリであって、前記ハッシュテーブルは複数のハッシュエントリを含み、各ハッシュエントリは、入力データストリームの複数のデータアイテムのうちの続くデータアイテムの複数のサブセットのうちの関連サブセットのハッシュ値と、前記関連サブセットのメモリ位置へのポインタと、を含む、メモリと、前記メモリに結合されるプロセッサであって、
以下の動作：
処理済みサブセットのうちのサブセット毎に前記ハッシュ値を計算し、
各計算したハッシュ値の一致について前記ハッシュテーブルを検索し、
前記一致の結果に従い、前記ハッシュテーブルを更新し、
を実行し、その間、前記動作のうちの少なくとも１つの動作は、単一命令多重データ処理、ＳＩＭＤ、エンジンに、前記複数のサブセットのうちの連続サブセットのグループの各被処理サブセットについて、前記少なくとも１つの動作を同時実行するよう指示することにより実行され、
前記一致の結果及び前記一致の結果に依存する比較の比較結果に従い、前記圧縮出力データストリームを更新し、
前記複数の関連サブセットについて、前記計算、検索、及び更新を繰り返して、前記圧縮出力データストリームを生成する、よう適応されるプロセッサと、
を含むシステムが提供される。

本発明の第１の態様の第１の可能な実装形式では、複数の関連サブセットのこのような各サブセットは、ＳＩＭＤエンジンアーキテクチャに従い定められた所定数のデータアイテムを含む。

第１の態様の第１の実装形式のような又はそれに従う第１の態様による第２の可能な実装形式では、グループ内の被処理サブセットの数は、ＳＩＭＤエンジンアーキテクチャに従い設定される。

第１の態様の前述の実装形式のうちのいずれかのような又はそれに従う第１の態様による第３の可能な実装形式では、一致の結果は、各計算したハッシュ値のハッシュテーブル内に存在する既存ハッシュ値との一致を示す。

第１の態様の前述の実装形式のうちのいずれかのような又はそれに従う第１の態様による第４の可能な実装形式では、前記比較は、前記一致の結果が前記計算したハッシュ値の前記ハッシュテーブル内の一致するハッシュ値との一致を示す場合に、前記比較結果を生成するよう行われ、
前記比較は、前記計算したハッシュ値を有する前記処理済みサブセットの前記データアイテムと、前記一致するハッシュエントリ内の前記ポインタにより指される前記関連サブセットの前記データアイテムとの間の比較を含む。

第１の態様の前述の実装形式のうちのいずれかのような又はそれに従う第１の態様による第５の可能な実装形式では、前記比較結果が、前記処理済みサブセット及び前記関連サブセットの前記データアイテムが同一であると示す場合、前記処理済みサブセットは、前記圧縮出力データストリーム内の前記関連サブセットへのポインタにより置き換えられ、
前記比較結果が、前記処理済みサブセット及び前記関連サブセットの前記データアイテムが同一でないと示す場合、前記処理済みサブセットは、前記圧縮出力データストリーム内で更新され、前記ハッシュテーブルは前記処理済みサブセットの新しいハッシュエントリにより更新される。

第１の態様の前述の実装形式のうちのいずれかのような又はそれに従う第１の態様による第６の可能な実装形式では、前記の同時計算は、前記プロセッサが処理済みサブセットの前記グループを前記ＳＩＭＤエンジンの少なくとも１つのＳＩＭＤレジスタにロードすること、及び前記ＳＩＭＤエンジンがサブセットの前記グループを同時処理すること、を含み、前記同時処理は、
前記グループの前記処理済みサブセットを互いに離すこと、
処理済みサブセット毎に異なるシフト値を用いて前記処理済みサブセットをシフトすること、及び、前記処理済みサブセットを処理して前記処理済みサブセット毎にハッシュ値を生成すること、を含む。

第１の態様の前述の実装形式のうちのいずれかのような又はそれに従う第１の態様による第７の可能な実装形式では、前記ハッシュテーブル内の前記処理済みサブセットの各々の前記一致についての前記の同時検索は、前記プロセッサが、前記ＳＩＭＤエンジンに、前記計算したハッシュ値の各々の前記ハッシュテーブルに格納されたハッシュ値との一致について同時検索するよう指示することを含む。

第１の態様の前述の実装形式のうちのいずれかのような又はそれに従う第１の態様による第８の可能な実装形式では、少なくとも１つの処理済みサブセットによる前記ハッシュテーブルの前記の同時更新は、前記プロセッサが、前記ＳＩＭＤエンジンに、前記少なくとも１つの処理済みサブセットに関連付けられたエントリにより、前記ハッシュテーブルを同時更新するよう指示することを含む。

第１の態様の前述の実装形式のうちのいずれかのような又はそれに従う第１の態様による第９の可能な実装形式では、前記圧縮出力データストリームは、レガシ圧縮方法を用いて圧縮された標準的圧縮出力データストリームに準拠し、前記圧縮出力データストリームは、レガシ伸長方法を用いて伸長される。

本発明の第２の態様によると、入力データストリームを圧縮して圧縮出力データストリームを生成する方法であって、複数のハッシュエントリを含むハッシュテーブルを格納するステップであって、各ハッシュエントリは、入力データストリームの複数のデータアイテムのうちのデータアイテムの複数のサブセットのうちの関連サブセットのハッシュ値と、前記関連サブセットのメモリ位置へのポインタと、を含む、ステップと、
以下の動作：
被処理サブセットのうちのサブセット毎に前記ハッシュ値を計算し、
各計算したハッシュ値の一致について前記ハッシュテーブルを検索し、
前記一致の結果に従い、前記ハッシュテーブルを更新する、
を実行するステップであって、前記動作のうちの少なくとも１つの動作は、プロセッサの単一命令多重データ処理、ＳＩＭＤ、エンジンに、前記複数の関連サブセットのうちの連続サブセットのグループの各被処理サブセットについて、前記少なくとも１つの動作を同時実行するよう指示することにより実行される、ステップと、
前記一致の結果及び前記一致の結果に依存する比較の比較結果に従い、前記圧縮出力データストリームを更新するステップと、
前記複数のサブセットを通じて、前記計算、検索、及び更新を繰り返して、前記圧縮出力データストリームを生成するステップと、を含む方法が提供される。

本発明の第２の態様の第１の可能な実装形式では、前記の同時計算は、前記プロセッサが被処理サブセットの前記グループを前記ＳＩＭＤエンジンの少なくとも１つのＳＩＭＤレジスタにロードすること、及び前記ＳＩＭＤエンジンが被処理サブセットの前記グループを同時処理すること、を含み、前記同時処理は、
前記グループの前記被処理サブセットを互いに離すこと、
被処理サブセット毎に異なるシフト値を用いて前記被処理サブセットをシフトすること、及び、前記被処理サブセットを処理して前記被処理サブセット毎にハッシュ値を生成すること、を含む。

本発明の第２の態様による第２の可能な実装形式では、前記ハッシュテーブル内の前記被処理サブセットの各々の前記一致についての前記の同時検索は、前記プロセッサが、前記ＳＩＭＤエンジンに、前記計算したハッシュ値の各々の前記ハッシュテーブルに格納されたハッシュ値との一致について同時検索するよう指示することを含む。

本発明の第２の態様による第３の可能な実装形式では、少なくとも１つの被処理サブセットによる前記ハッシュテーブルの前記の同時更新は、前記プロセッサが、前記ＳＩＭＤエンジンに、前記少なくとも１つの被処理サブセットに関連付けられたエントリにより、前記ハッシュテーブルを同時更新するよう指示することを含む。

第１の態様の前述の実装形式のうちのいずれかのような又はそれに従う第２の態様による第４の可能な実装形式では、前記圧縮出力データストリームは、レガシ圧縮方法を用いて圧縮された標準的圧縮出力データストリームに準拠し、前記圧縮出力データストリームは、レガシ伸長方法を用いて伸長される。

特に定められない限り、本願明細書で用いられた全ての技術的及び／又は科学的用語は、本発明の関連する分野の当業者により通常理解されるものと同じ意味を有する。ここに記載のものに類似する方法及び材料が本発明の実施形態の実施又は試験において使用できるが、例示的な方法及び／又は材料が。以下に記載される。対立する場合には、定義を含み本願明細書が制御する。さらに、材料、方法、及び例は、単に説明のためであり、必ずしも限定であることを意図しない。

本発明の幾つかの実施形態が、単に例として、添付の図面を参照してここで説明される。以下に特に図面を詳細に参照すると、図示の事項は例であり、本発明の実施形態の説明のための議論を目的とすることが強調される。これに関して、図面と共に取り入れられる説明は、本発明の実施形態がどのように実施されるかを当業者に明らかにする。

以下の図面がある。
本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて入力データストリームを圧縮する例示的なシステムの概略図である。 本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて入力データストリームを圧縮する例示的な処理のフローチャートである。 本発明の幾つかの実施形態による、ＳＩＭＤエンジンのレジスタに入力データストリームの複数の連続バイトを同時ロードする例示的なシーケンスの概略図である。 本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて、それぞれ入力データストリームの連続バイトを含む複数のサブセットのハッシュ値を同時計算する例示的なシーケンスの概略図である。 本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて、ハッシュテーブル内の複数のハッシュ値の一致について同時検索する例示的なシーケンスの概略図である。 本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて複数のハッシュテーブルエントリを同時更新する例示的なシーケンスの概略図である。

本発明は、その幾つかの実施形態において、データ圧縮に関し、より具体的には、排他的ではないが、ＳＩＭＤエンジンを用いるデータ圧縮に関する。

本発明は、データ、例えばデータ記憶及び／又はデータ転送、の量（容量）を削減するためにデータ圧縮を必要とする複数のアプリケーションに対して１又は複数のプロセッサのＳＩＭＤエンジンを用いる汎用データ圧縮のためのシステム及び方法を提示する。複数のデータアイテム、例えば、バイト、ワード、ダブルワード、及び／又はピクセルを含む入力データストリームは、反復データシーケンスの前のインスタンスへのポインタで反復データシーケンスを置き換えることにより、圧縮される。ここに提示される圧縮システム及び方法は、従来知られている無損失圧縮方法及び／又はアルゴリズム、例えばＬｅｍｐｅｌ−Ｚｉｖ（ＬＺ７７及びＬＺ７８）、Ｌｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ（ＬＺＷ）、Ｌｅｍｐｅｌ−Ｚｉｖ−Ｏｂｅｒｈｕｍｅｒ（ＬＺＯ）、及び／又はＬＺ４を利用する。圧縮方法は、圧縮処理を拡張するため、例えば圧縮リソース及び／又は圧縮時間を削減するために、プロセッサのＳＩＭＤエンジンにより実行される圧縮動作を実証するために必要な程度まで本発明において説明されるだけである。しかしながら、当業者は圧縮方法の全ての側面に慣れ親しんでいることが期待される。圧縮方式は、圧縮処理中の１又は複数の動作の同時実行のために、ＳＩＭＤエンジンを利用し、連続データアイテムのサブセットを処理してそれぞれのハッシュ値を計算し、ハッシュテーブル内のハッシュ値の一致について検索し、及び／又はハッシュテーブルをハッシュ値及び関連サブセットへのポインタで更新する。ＳＩＭＤエンジンは、複数データアイテムに渡る単一命令（プロセッサ命令）の同時実行をサポートする。圧縮方法及び／又はアルゴリズムは、ＳＩＭＤエンジンによる同時実行をサポートするために何らか操作されて良い。

ＳＩＭＤエンジン技術をデータ圧縮処理に適用することは、現在の既存の逐次圧縮方法（レガシ及び／又は標準的圧縮方法）と比べて有意な利益を提示し得る。一般的なベクトル処理技術及び特にＳＩＭＤ技術は、多くの側面で、例えば並列に処理され得るデータアイテム数及び／又はプロセッサの処理パワーにおいて、急速に進歩している。現在の既存の圧縮方法により使用される逐次データ圧縮は、主に時間を消費する及び／又はプロセッサ集中的動作であり得る。入力データストリームのデータアイテムは圧縮処理の基本動作に関して互いに独立であると考えられ得るので、入力データストリームの同時処理は、ＳＩＭＤエンジン及び／又は技術を最大限に活用し得る。圧縮時間及び／又は計算リソースは、ＳＩＭＤエンジンを用いて有意に削減され得る。圧縮動作のうちの１つでも同時実行することは、計算性能を有意に向上する。したがって、２つ又は全ての圧縮動作、例えばサブセットを処理してハッシュ値を計算する、ハッシュ値の一致について検索する、及び／又はハッシュテーブルを更新する、を実行するためにＳＩＭＤエンジンを適用することは、更に大きな有意な圧縮性能の向上を提示し得る。

ＳＩＭＤエンジンを用いて圧縮される圧縮データ（ストリーム）のフォーマットは、幾つかのレガシ圧縮方法を用いて圧縮されたデータに完全に準拠して良い。ＳＩＭＤエンジンを用いて圧縮されたデータの完全な準拠は、圧縮データを伸長するための従来知られた標準的な圧縮方法、技術、及び／又はツールを用いて圧縮されたデータの伸長を可能にする。勿論、伸長方法、技術、及び／又はツールは、使用される圧縮フォーマットに従い適切に選択される必要があって良い。例えば、ＬＺ４伸長は、ＬＺ４圧縮データフォーマットに従いＳＩＭＤエンジンを利用して圧縮された圧縮データを伸長するために利用されて良い。

本発明の少なくとも１つの実施形態を詳細に説明する前に、本発明は、必ずしもその用途において、以下の記載において説明された及び／又は図面及び／又は例に示されたコンポーネント及び／又は方法の構成及び配置の詳細に限定されないことが理解されるべきである。本発明は、他の実施形態又は種々の方法で実施され又は実行されることが可能である。

本発明は、システム、方法、及び／又はコンピュータプログラムプロダクトであって良い。コンピュータプログラムプロダクトは、プロセッサに本発明の態様を実施させるためのコンピュータ可読プログラム命令を有するコンピュータ可読記憶媒体（又は複数の媒体）を含み得る。

コンピュータ可読記憶媒体は、命令実行装置による使用のために命令を保持し格納可能な有形装置であり得る。コンピュータ可読記憶媒体は、例えば、限定ではないが、電子記憶装置、磁気記憶装置、光学的記憶装置、電磁気記憶装置、半導体記憶装置、又は前述の任意の適切な組合せであって良い。

ここに記載されるコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体から個々のコンピューティング／処理装置に、又はネットワーク、例えばインターネット、ローカルエリアネットワーク、広域ネットワーク、及び／又は無線ネットワークを介して外部コンピュータ若しくは外部記憶装置にダウンロードされ得る。

コンピュータ可読プログラム命令は、完全にユーザのコンピュータで、部分的にユーザのコンピュータで、スタンドアロン型ソフトウェアパッケージとして、部分的にユーザのコンピュータで及び部分的にリモートコンピュータで、又は完全にリモートコンピュータ若しくはサーバで、実行されて良い。後者のシナリオでは、リモートコンピュータは、ＬＡＮ（local area network）又はＷＡＮ(wide area network)を含む任意の種類のネットワークを通じてユーザのコンピュータに接続されて良く、或いは（例えば、インターネットサービスプロバイダを用いてインターネットを通じて）外部コンピュータへの接続が生成されて良い。幾つかの実施形態では、例えばプログラマブル論理回路、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、又はプログラマブルロジックアレイ（ＰＬＡ）を含む電子回路は、本発明の態様を実行するために、コンピュータ可読プログラム命令の状態情報を利用して電子回路をパーソナライズすることにより、コンピュータ可読プログラム命令を実行して良い。

本発明の態様は、本発明の実施形態による方法、機器（システム）及びコンピュータプログラムプロダクトのフローチャート図及び／又はブロック図を参照してここに記載される。フローチャート図及び／又はブロック図の各々のブロック、及びフローチャート図及び／又はブロック図のブロックの組合せは、コンピュータ可読プログラム命令により実装され得ることが理解される。

図中のフローチャート及びブロック図は、本発明の種々の実施形態に従うシステム、方法、及びコンピュータプログラムプロダクトの可能な実装のアーキテクチャ、機能、及び動作を示す。これに関し、フローチャート又はブロック図の各々のブロックは、特定の論理機能を実装するために１又は複数の実行可能命令を有するモジュール、セグメント、又は命令の一部、を表し得る。幾つかの代替の実施形態では、ブロックの中に記される機能は、図に示した順序と異なって生じて良い。例えば、連続して示される２つのブロックは、実際には、実質的に同時実行されて良く、或いは、これらのブロックは、含まれる機能に依存して、時には、逆の順序で実行されて良い。留意すべきことに、ブロック図及び／又はフローチャート図の各々のブロック、及びブロック図及び／又はフローチャート図のブロックの組み合わせは、特定の機能又は動作を実行する、又は特定目的ハードウェア及びコンピュータ命令の組み合わせを実行する専用ハードウェアに基づくシステムにより実施され得る。

ここで図１を参照すると、図１は、本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて入力データストリームを圧縮する例示的なシステムの概略図である。システム１００は、入力データストリーム１２０を受信する及び／又は指定する並びに圧縮出力データストリーム１３０を出力する入力／出力（Ｉ／Ｏ）インタフェース１０２、入力データストリーム１２０を圧縮して圧縮出力データストリーム１３０を生成するＳＩＭＤエンジン１０６を含むプロセッサ１０４、メモリ１０８、及びプログラムストア１１０を含む。入力データストリーム１２０は、１又は複数のフォーマット、例えばデータファイル、メディアファイル、ストリーミングデータ、等で受信されて良い。入力データストリーム１２０は、複数のデータアイテム、例えば、ストリームとして順序通り配置され得るバイト、ワード、ダブルワード、及び／又はピクセルを含む。Ｉ／Ｏインタフェース１０２は、１又は複数のインタフェース、例えばネットワークインタフェース、メモリインタフェース、及び／又は記憶装置インタフェースを含み得る。Ｉ／Ｏインタフェース１０２は、データストリーム１２０及び／又は１３０をネットワーク及び／又は１又は複数のローカル周辺機器インタフェース、例えばユニバーサルシリアルバス（ＵＳＢ）、セキュアデジタル（ＳＤ）カード、等を介して受信し及び／又は送信するために、プロセッサ１０４により使用されて良い。Ｉ／Ｏインタフェース１０２は、メモリ１０８装置のようなメモリ及び／又はプログラムストア１１０のような記憶装置にデータストリーム１２０及び／又は１３０をフェッチし及び／又は格納するために、プロセッサ１０４により使用されても良い。同種又は異種のプロセッサ１０４は、クラスタとして及び／又はそれぞれ１又は複数のＳＩＭＤエンジン１０６を有する１又は複数のマルチコアプロセッサとして、並列処理のために構成されて良い。ＳＩＭＤエンジン１０６は、ベクトル処理のための複数の処理パイプラインを含み、例えば複数のデータアイテムを同時処理する。プログラムストア１１０は、１又は複数の一時的な持続性メモリ記憶装置、例えばハードドライブ、フラッシュアレイ、等を含み得る。プログラムストア１１０は、１又は複数のネットワーク記憶装置、例えば記憶サーバ、ネットワークアクセス可能記憶装置（ＮＡＳ）、ネットワークドライブ、等を更に含んで良い。

図２も参照すると、図２は、本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて入力データストリームを圧縮する例示的な処理のフローチャートである。入力データストリームを圧縮する圧縮処理２００は、システム１００のようなシステムにより実行されて良い。圧縮処理２００は、ＳＩＭＤエンジン１０６を利用して、入力データストリーム１２０の複数のデータアイテムを同時処理して、圧縮出力データストリーム１３０を生成する。

圧縮処理２００は、例えばプロセッサ１０４により実行される複数のプログラム命令を含むコンプレッサ１１２及び／又はプログラムストア１１０からのＳＩＭＤエンジン１０６のような１又は複数のソフトウェアモジュールにより行われて良い。コンプレッサ１１２は、プロセッサ１０４の処理ユニットにより実行されて、圧縮処理管理し及び／又は調整し、例えばＳＩＭＤエンジン１０６にデータをロードし、ＳＩＭＤエンジン１０６からデータを収集し、データを同期化し、タスクを同期化し、圧縮出力データストリーム１３０を更新する、等をして良い。コンプレッサ１１２を実行するプロセッサ１０４は、圧縮処理２００を早め、したがって処理リソース及び／又は処理時間を削減するために、ＳＩＭＤエンジン１０６に、圧縮処理２００中に入力データストリーム１２０の複数のデータアイテム及び／又は中間成果物を同時処理するよう指示して良い。同時処理は、複数の処理パイプラインを用いて複数のデータアイテム及び／又は中間成果物に渡り動作（命令）を同時実行するＳＩＭＤエンジンに対して単一命令を開始するプロセッサ１０４により適用される。コンプレッサ１１２は、圧縮シーケンス２００を制御するために、メモリ１０８内に１又は複数のデータ構造、例えば履歴アレイ１１４、ハッシュテーブル１１６、等を生成して良い。

２０２に示すように、処理２００は、コンプレッサ１１２がＩ／Ｏインタフェース１０２を用いて入力データストリーム１２０を受信すること、例えばリモート装置からネットワークを介して入力データストリーム１２０を受信すること、ローカル周辺機器インタフェースから、メモリ１０８から、及び／又はプログラムストア１１０から入力データストリーム１２０をフェッチすること、で開始する。

圧縮処理２００を実行するシステム１００は、例えば従来知られている１又は複数の無損失圧縮方法、例えばＬｅｍｐｅｌ−Ｚｉｖ（ＬＺ７７及びＬＺ７８）、Ｌｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ（ＬＺＷ）、Ｌｅｍｐｅｌ−Ｚｉｖ−Ｏｂｅｒｈｕｍｅｒ（ＬＺＯ）、及び／又はＬＺ４を用いて、入力データストリーム１２０を圧縮する。先に言及したように、圧縮方法は、圧縮処理２００を拡張するためにＳＩＭＤエンジン１０６により実行される圧縮動作を実証するために必要な程度だけ、本発明において説明される。

ＳＩＭＤエンジン１０６を利用して入力データストリーム１２０を圧縮する実施形態を更に提示する前に、圧縮方法の幾つかの基本的側面が先ず記載される。圧縮方法の基本的側面は、入力データストリーム１２０内の重複データシーケンスを識別し、圧縮出力データストリーム１３０の中の重複シーケンス自体を置き換える代わりに、重複シーケンスを同じシーケンスの前のインスタンスへのポインタで置き換えることである。スライディングウインドウが入力データストリーム１２０に適用されて、入力データストリーム１２０の連続データアイテムを含むローリングシーケンスを指定する。ローリングシーケンスのデータアイテムは、履歴テーブル１１４のような履歴アレイに格納される。ハッシュ値が、ローリングシーケンスの各々について計算され、ハッシュテーブル１１６のようなハッシュテーブルのハッシュテーブルエントリに格納される。ハッシュテーブルエントリの各々は、計算したハッシュ値と履歴アレイ１１４内の関連ローリングシーケンスへのポインタとのペアを含む。全ての新しいローリングシーケンスについて、ハッシュ値が計算され、同一のハッシュ値がハッシュテーブル１１６内に存在するかどうかを調べるために、ハッシュテーブル１１６内での一致について検索される。一致が見付かった場合、新しいローリングシーケンスは、一致するハッシュ値に関連付けられた前のローリングシーケンスと同一であって良い。

ハッシュ値を計算するために、複数のハッシュ関数が使用されて良い。ハッシュ関数の選択は、計算の複雑さ及び／又は処理時間と、２つのサブセットの類似性の確実さとの間のトレードオフを提示し得る。ローリングシーケンスの各々がユニークなハッシュ値に関連付けられるように、一義的な複雑なハッシュ値を計算することが可能である。しかしながら、複雑なハッシュ値の計算は、非常に計算が要求され得る。より低い複雑さのハッシュ関数は、ローリングシーケンスについて、より少ない複雑さのハッシュ値を生成し得る。しかしながら、何らかのレベルの曖昧さが存在し得る。例えば、２以上の類似しないローリングシーケンスについて、計算したハッシュ値が同じであり得る。このような低い複雑さのハッシュ値の場合、同じハッシュ値を有する新しいローリングシーケンス及び前のローリングシーケンスの実際のデータアイテムは、一致を決定するために比較される必要がある。一致が検出された場合、新しいローリングシーケンスが一致する前のローリングシーケンスと同じであることを示し、新しいローリングシーケンスは、圧縮出力データストリーム１３０に含まれないが、一致する前のローリングシーケンスの位置へのポインタで置き換えられて良い。ポインタは、置き換えられたローリングシーケンスが挿入される必要のある、圧縮出力データストリーム１３０内の適切な位置に置かれて良い。一致が検出されない場合、ローリングシーケンスは、圧縮出力データストリーム１３０に含まれる。ハッシュテーブル検索に続き、ハッシュテーブルは相応して更新されて良い。一致が見付からなかった場合、ハッシュテーブルは、新しいローリングシーケンスについて計算された新しいハッシュ値を含むよう更新されて良い。全てのハッシュエントリが占有された場合、前のローリングシーケンスに関連付けられた１又は複数のハッシュ値、例えば一致頻度の最も低いハッシュエントリ等は、ハッシュテーブルから省略されて良い。

履歴アレイ１１４のサイズ、例えば計算に利用可能な前のローリングシーケンスの数は、変化して良い。例えば計算に利用可能なより多くの前のローリングシーケンスを含む大きな履歴アレイ１１４の場合、一致の確率は増大し、したがって計算の向上をもたらす。しかしながら、履歴アレイ１１４が大きいほど、多くの検索動作及び／又はメモリリソースが必要とされ、したがって圧縮のための処理リソース及び／又は処理時間を増大する。圧縮方法の殆どで、履歴アレイ１１６のサイズは、圧縮効率と消費処理及び／又はメモリリソースとの間の最適トレードオフを達成するために、標準的に２ＫＢ、４ＫＢ、８ＫＢ、１６ＫＢ及び／又は３２ＫＢである。

標準的に、圧縮方法は、ローリングシーケンスの各々についてハッシュ値を計算するためにシリアルシーケンスを利用し、ハッシュテーブルを検索し、及びハッシュテーブルを相応して更新する。圧縮処理２００は、他方で、圧縮処理２００を早めるために、ＳＩＭＤエンジン１０６を用いて計算、検索、及び／又は更新動作のうちの１又は複数を同時実行して良い。

２０４に示すように、コンプレッサ１１２は、大部分の最近のサブセットを格納するために、メモリ１０８内に履歴アレイ１１４を生成する。履歴アレイ１１４の標準的なサイズは、２ＫＢ、４ＫＢ、８ＫＢ、１６ＫＢ、及び／又は３２ＫＢである。処理リソースの可用性及び／又はメモリ１０８のサイズに従い、他のサイズが履歴アレイ１１４に割り当てられて良い。コンプレッサ１１２は、また、履歴アレイ１１４に格納されたサブセットのうちの１つへのポインタ及び関連サブセットについて計算したハッシュ値を含むハッシュエントリを格納するために、メモリ１０８内にハッシュテーブル１１６を生成する。つまり、最初に、圧縮処理２００の始めに、履歴アレイ１１４及びハッシュテーブル１１６は、空であり、スライドウインドウが入力データストリーム１２０に適用されるにつれ次第にサブセット（ローリングシーケンス）で満たされる。

２０６に示すように、コンプレッサ１１２は、入力データストリーム１２０に渡りローリングウインドウを適用する。サブセットの各々のサイズを指示するウインドウのサイズは、プロセッサ１０４のアーキテクチャ及び／又はＳＩＭＤエンジン１０６のアーキテクチャに従い適応されて良い。コンプレッサ１１２は、入力データストリーム１２０に渡りスライドウインドウをスライドさせ、ウインドウの全てのスライド（シフト）の間、前のローリングシーケンスの最も早い（第１）データアイテムが省略され、新しいローリングシーケンスを生成するために新しいデータアイテムが追加されるようにする。

２０８に示すように、コンプレッサ１１２は、ＳＩＭＤエンジン１０６を用いて新しいローリングシーケンスについてハッシュ値を計算する。ローリングシーケンスの同時処理を可能にするために、ローリングシーケンスは、それぞれローリングシーケンスの連続データアイテムを含む複数の被処理サブセットに分離される。被処理サブセットのグループ（ローリングシーケンス）は、ＳＩＭＤエンジン１０６を用いて同時処理される。グループ内の被処理サブセットの数は、プロセッサ１０４のアーキテクチャ及び／又はＳＩＭＤエンジン１０６のアーキテクチャに従い適応されて良い。コンプレッサ１１２は、サブセットの各々についてハッシュ値を計算するために、被処理サブセットを１又は複数のＳＩＭＤエンジン１０６にロードする。コンプレッサ１１２によりＳＩＭＤエンジンに発行されるロード命令の種類、シノプシス、特徴、及び／又は使用法は、プロセッサ１０４及び／又はＳＩＭＤエンジン１０６のアーキテクチャに従い適応されて良い。

ここで図３Ａを参照すると、図３Ａは、本発明の幾つかの実施形態による、ＳＩＭＤエンジンのレジスタに入力データストリームの複数の連続バイトを同時ロードする例示的なシーケンスの概略図である。図３Ｂも参照すると、図３Ｂは、本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて、それぞれ入力データストリームの連続バイトを含むサブセットのグループのハッシュ値を同時計算する例示的なシーケンスの概略図である。例示的なロードシーケンス３００の間、コンプレッサ１１２のようなコンプレッサは、各連続レジスタが１アイテムだけスライドされたデータのウインドウを含むように、連続データアイテム３１０を、ＳＩＭＤエンジン１０６の４個のレジスタ３０２Ａ乃至３０２Ｄにロードする。レジスタ３０２にロードされる連続データアイテムの数は、被処理サブセットの各々のサイズ及び／又はサブセットのグループのサイズを指示する。図３Ａに提示される例示的なシーケンスは１６バイトアーキテクチャを利用するＳＩＭＤエンジンを記載し、例えば各レジスタは１６バイト幅であり、８個のサブセットのグループの同時処理を可能にし、例えば４個の連続データアイテム３１０を含むサブセットについてそれぞれ計算される８個のハッシュ値３２０を計算する。後述するように、ＳＩＭＤエンジン１０６が３個のハッシュ値３２０を同時計算できるようにするために、データアイテム３１０は間隔を開けられる必要がある。データアイテム３１０は、各バイト（８ビット）がワード（１６ビット）の空間を占有するように間隔を開けられ、したがって、例示的なＳＩＭＤエンジン１０６のレジスタ幅に適合するように３２個のデータアイテム３１０が１６バイトの４個のレジスタを占有する。ＳＩＭＤエンジン１０６の他のアーキテクチャ、例えば３２、６４、１２８、２５６バイト等は、異なる数の連続データアイテム３１０をＳＩＭＤエンジン１０６のレジスタ３０２にロードすることを可能にし得る。ハッシュ値３２０は４個の連続データアイテム３１０毎に計算されるので、ＳＩＭＤエンジン１０６にロードされた３２バイトは、１１個の連続データアイテムＳ_Ｋ３１０Ａ乃至Ｓ_Ｋ＋１０３１０Ｋからなる。

プロセッサ１０４が、例えば１６バイトＳＩＭＤエンジン１０６を作動させるＳｔｒｅａｍｉｎｇ ＳＩＭＤ Ｅｘｔｅｎｓｉｏｎｓ（ＳＳＥ）命令セットを利用するＩｎｔｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＡ）プロセッサであると仮定すると、３２バイトのロード動作は８個の命令を必要とし得る。

ロード動作中、コンプレッサ１１２は、データアイテムのバイト（８ビット）をワード（１６ビット）に変換して、図３Ｂに示すように各データアイテムが１ワードを占有するようにする。

コンプレッサ１１２は、ＳＩＭＤエンジン１０６に、レジスタ３０２にロードされたデータアイテム３１０をシフトするよう指示する。以下のように、レジスタ部分３０２Ａ−３０２Ｄの各々に異なるシフトが適用される。
・レジスタ部分３０２Ａに格納されたデータアイテムＳ_Ｋ３１０Ａ乃至Ｓ_Ｋ＋７３１０Ｈは、６ビット左にシフトされる。
・レジスタ部分３０２Ｂに格納されたデータアイテムＳ_Ｋ＋１３１０Ｂ乃至Ｓ_Ｋ＋８３１０Ｉは、４ビット左にシフトされる。
・レジスタ部分３０２Ｂに格納されたデータアイテムＳ_Ｋ＋２３１０Ｃ乃至Ｓ_Ｋ＋９３１０Ｊは、２ビット左にシフトされる。
・レジスタ部分３０２Ｄに格納されたデータアイテムＳ_Ｋ＋３３１０Ｄ乃至Ｓ_Ｋ＋１０３１０Ｋは、全くシフトされない。

レジスタ３０２に適用されるシフトの程度は、レジスタ３０２にロードされる連続データアイテム３１０の数に依存し、ここでは、シフトの程度は、ＳＩＭＤエンジン１０６のアーキテクチャに依存する。

例示的な処理シーケンス３０１の間、ロードシーケンス３００に続き、コンプレッサ１１２は、ＳＩＭＤエンジン１０６に、被処理サブセットの各々についてハッシュ値３２０を同時計算する３３０よう指示して良い。コンプレッサ１１２によりＳＩＭＤエンジンに発行される計算命令の種類、シノプシス、特徴、及び／又は使用法は、プロセッサ１０４及び／又はＳＩＭＤエンジン１０６のアーキテクチャに従い適応されて良い。ハッシュ値３２０の計算３３０は、連続データアイテム３１０のサブセットに渡り実行される単純なＸＯＲ演算であって良い。連続データアイテム３１０のサブセットは、被処理サブセットとして参照される。被処理サブセットの各々は、４個のデータ連続アイテム３１０を含む。例えば、第１被処理サブセットはデータアイテムＳ_Ｋ３１０Ａ乃至Ｓ_Ｋ＋３３１０Ｄを含み、第２被処理サブセットはデータアイテムＳ_Ｋ＋１３１０Ｂ乃至Ｓ_Ｋ＋４３１０Ｅを含み、データアイテムＳ_Ｋ＋７３１０Ｉ乃至Ｓ_Ｋ＋１０３１０Ｋを含む最後の被処理サブセットまで同様である。

ＳＩＭＤエンジン１０６は、単純なＸＯＲ演算であって良い計算３３０を、被処理サブセットの各々に含まれるそれぞれ４個のデータアイテム３１０に渡り適用することにより、全ての被処理サブセットについてハッシュ値を同時計算する。ＳＩＭＤエンジン１０６の提示の例示的なシーケンス及びアーキテクチャでは、ＳＩＭＤエンジン１０６は、８個のハッシュ値３２０、データアイテムＳ_Ｋ３１０Ａ乃至Ｓ_Ｋ＋３３１０Ｄについてハッシュ値３２０Ａ、データアイテムＳ_Ｋ＋１３１０Ｂ乃至Ｓ_Ｋ＋４３１０Ｅについてハッシュ値３２０Ｂ、データアイテムＳ_Ｋ＋２３１０Ｃ乃至Ｓ_Ｋ＋５３１０Ｆについてハッシュ値３２０Ｃ、データアイテムＳ_Ｋ＋３３１０Ｄ乃至Ｓ_Ｋ＋６３１０Ｇについてハッシュ値３２０Ｄ、データアイテムＳ_Ｋ＋４３１０Ｅ乃至Ｓ_Ｋ＋７３１０Ｈについてハッシュ値３２０Ｅ、データアイテムＳ_Ｋ＋５３１０Ｆ乃至Ｓ_Ｋ＋８３１０Ｉについてハッシュ値３２０Ｆ、データアイテムＳ_Ｋ＋６３１０Ｇ乃至Ｓ_Ｋ＋９３１０Ｊについてハッシュ値３２０Ｇ、データアイテムＳ_Ｋ＋７３１０Ｈ乃至Ｓ_Ｋ＋１０３１０Ｋについてハッシュ値３２０Ｈ、を生成する。計算したハッシュ値３２０は、ＳＩＭＤエンジン１０６のレジスタ３０４に格納される。

プロセッサ１０４が、例えば１６バイトＳＩＭＤエンジン１０６を作動させるＳＳＥ命令セットを利用するＩＡプロセッサであると仮定すると、３２個のハッシュ値３２０の計算は６個の命令を必要とし得る。

もう一度、図２を参照する。２１０に示すように、コンプレッサ１１２は、計算したハッシュ値３２０の各々を、ハッシュテーブル１１６のハッシュエントリの中で利用可能な複数のハッシュ値の各々と比較することにより、計算したハッシュ値３２０の各々の一致について検索する。ハッシュテーブル１１６のハッシュエントリのうちの１つに同一ハッシュ値が見付かった場合、計算したハッシュ値３２０のうちの１つについて一致が見付かる。コンプレッサ１１２は、ＳＩＭＤエンジン１０６に、ハッシュテーブル１１６の中で計算したハッシュ値３２０の各々の一致について同時検索するよう指示するために、命令を発行して良い。コンプレッサ１１２によりＳＩＭＤエンジンに発行される検索命令の種類、シノプシス、特徴、及び／又は使用法は、プロセッサ１０４及び／又はＳＩＭＤエンジン１０６のアーキテクチャに従い適応されて良い。例えば、ＩＡプロセッサ１０４では、コンプレッサ１１２は、ＳＩＭＤエンジン１０６に検索動作を実行するよう指示するために、以下の関数１に示されるように、ＳＳＥ命令セットから「ｇａｔｈｅｒ」命令を使用して良い。

関数１：
void__m５１２i_m５１２_１３２gather_epi３２(__m５１２i vindex, void const* base_addr, int scale)
シノプシス：
void__m５１２i_m５１２_１３２gather_epi３２(__m５１２i vindex, void const* base_addr, int scale)
#include “immintrin.h”
Instruction :Vpgatherdd zmm３２z {k}, vm３２z
CPUID Flags :AVX５１２F for AVX−５１２, KNCNI for KNC
説明：
３２ビットインデックスを用いてメモリから３２ビット整数を集める。３２ビット要素は、base_addrで開始するアドレスからロードされ、vindex内の各３２ビット要素によりオフセットされる（各インデックスはscale内の因子によりスケーリングされる）。scaleは１、２、４、又は８であるべきである。
動作：
FOR j:=０ to １５
i:=j*３２
dst[i+３１:i]:=MEM[base_addr+SignExtend(vindex[i+３１:i])*scale]
ENDFOR
Dst[MAX:５１２]:=０

コンプレッサ１１２は、ＳＩＭＤエンジン１０６に検索動作を実行するよう指示するために、以下の擬似コード抜粋１に表されるように「ｇａｔｈｅｒ」命令を発行して良い。
擬似コード抜粋１：
Result[i]=hashTable[hashes[i]] for i in ０…１５

２１２に示すように、計算したハッシュ値３２０のうちの１又は複数がハッシュテーブル１１６内の格納されたハッシュ値のうちの１つに一致する場合、コンプレッサ１１２は、被処理サブセットが一致する格納されたハッシュ値を含むハッシュエントリによりポイントされる関連サブセットと同じか否かを決定するために更なる比較を開始して良い。コンプレッサ１１２により使用されるハッシュ関数計算３３０が、曖昧な結果を提示し得る、例えば同じハッシュ値３２０が異なるデータアイテム３１０を有する異なるサブセットについて計算され得る、単純なＸＯＲ演算であり得るので、更なる比較が要求されて良い。更なる比較は、被処理サブセットに含まれるデータアイテム３１０と、ハッシュテーブル１１６内の一致する格納されたハッシュ値に関連付けられた関連サブセットに含まれるデータアイテム３１０との比較を含む。被処理サブセット及び関連サブセットの両方のデータアイテム３１０が同様である場合、コンプレッサ１１２は、被処理サブセットについて一致指示を発行する。

ここで図４を参照すると、図４は、本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて、ハッシュテーブル内の複数のハッシュ値の一致について同時検索する例示的なシーケンスの概略図である。例示的な検索シーケンス４００の間、コンプレッサ１１２のようなコンプレッサは、ＳＩＭＤエンジン１０６のようなＳＩＭＤエンジンに、ハッシュ値３２０のような計算した複数のハッシュ値の、ハッシュテーブル１１６のようなハッシュテーブル内のハッシュエントリ４０２に格納されたハッシュ値との一致について、同時検索するよう指示する。例示的なシーケンス４００は、前述の例示的なロードシーケンス３００及び例示的な同時計算シーケンス３０１に続く。ＳＩＭＤエンジン１０６は、レジスタ３０４に格納された計算したハッシュ値３２０の各々を、ハッシュテーブル１１６内のハッシュエントリ４０２の中で利用可能な格納されたハッシュ値の各々と比較するよう、同時に８個の比較動作４５０を開始する。各検索動作は、計算したハッシュ値３２０のうちの１つに関連付けられる。例えば、検索動作４５０Ａは計算したハッシュ値３２０Ａに関連付けられ、検索動作４５０Ｂは計算したハッシュ値３２０Ｂに関連付けられ、検索動作４５０Ｈは計算したハッシュ値３２０Ｈに関連付けられるまで同様である。例示的な検索シーケンス４００において分かるように、検索動作４５０Ａの間、それぞれの計算したハッシュ値３２０Ａの間で一致が見付からない。しかしながら、空のハッシュエントリ４０２Ｇがハッシュテーブル１１６内で検出される。検索動作４５０Ｂの間、それぞれの計算したハッシュ値３２０Ｂとハッシュエントリ４０２Ｃ内の格納されたハッシュ値との間で一致が見付かる。検索動作４５０Ｈの間、それぞれの計算したハッシュ値３２０Ｈとハッシュエントリ４０２Ｋ内の格納されたハッシュ値との間で別の一致が検出される。ＳＩＭＤエンジン１０６により使用されるハッシュ関数計算３３０はデータアイテム３１０に渡る単純なＸＯＲ演算であって良いので、ハッシュ値３２０は曖昧である場合がある。したがって、被処理サブセット及びハッシュテーブル１１６内の一致する格納されたハッシュ値に関連付けられたサブセットの実際のデータアイテム３１０は、的確な一致を決定するために比較される必要がある。コンプレッサ１１２は、履歴アレイ１１４内の一致する計算したハッシュ値３２０毎に、比較動作４６０を開始して良い。例えば、ＳＩＭＤエンジン１０６は、計算したハッシュ値３２０Ｂとハッシュエントリ４０２Ｃに格納されたハッシュ値との間の一致を示した。コンプレッサは、したがって、ハッシュエントリ４０２Ｃに関連付けられたデータセットのデータアイテム３１０を比較するために、比較動作４６０Ａを開始する。例えば、ハッシュエントリ４０２ＣはデータアイテムＳ_Ｋ−５３１０Ｐで開始するサブセットに関連付けられると仮定すると、コンプレッサ１１２は、データアイテムＳ_Ｋ＋１３１０Ｂ乃至Ｓ_Ｋ＋４３１０Ｅ（ハッシュ値３２０Ｂを生成する）を、それぞれのデータアイテムＳ_Ｋ−５３１０Ｐ乃至Ｓ_Ｋ−２３１０Ｍと比較して、一致を決定する。データアイテムＳ_Ｋ＋１３１０Ｂ乃至Ｓ_Ｋ＋４３１０ＥがデータアイテムＳ_Ｋ−５３１０Ｐ乃至Ｓ_Ｋ−２３１０Ｍと同様である場合、コンプレッサ１１２は一致を示して良い。同様に、コンプレッサ１１２は、ハッシュエントリ４０２Ｋに関連付けられたデータセットのデータアイテム３１０を比較するために、比較動作４６０Ｂを開始する。例えば、ハッシュエントリ４０２ＫはデータアイテムＳ_Ｋ−３３１０Ｎで開始するサブセットに関連付けられると仮定すると、コンプレッサ１１２は、データアイテムＳ_Ｋ＋７３１０Ｈ乃至Ｓ_Ｋ＋１０３１０Ｋ（ハッシュ値３２０Ｈを生成する）を、それぞれのデータアイテムＳ_Ｋ−３３１０Ｎ乃至Ｓ_Ｋ３１０Ａと比較して、一致を決定する。データアイテムＳ_Ｋ＋７３１０Ｈ乃至Ｓ_Ｋ＋１０３１０ＫがデータアイテムＳ_Ｋ−３３１０Ｎ乃至Ｓ_Ｋ３１０Ａと同様である場合、コンプレッサ１１２は一致を示して良い。

もう一度、図２を参照する。２１４に示すように、コンプレッサ１１２は、一致の結果に従いハッシュテーブル１１６を更新する。コンプレッサ１１２は、命令を発行して、ＳＩＭＤエンジン１０６に、ハッシュエントリ４０２のうちの１又は複数を、それぞれの１又は複数の被処理サブセットに関連付けられた新しいハッシュエントリ４０２で同時更新するよう指示して良い。つまり、新しいハッシュエントリ４０２の各々は、それぞれのサブセットについて計算されたハッシュ値３２０と、履歴アレイ１１４内のそれぞれのサブセットへのポインタと、を含む。ハッシュテーブル１１６は、１又は複数の更新方式を用いて、１又は複数のシナリオで更新されて良い。ある方式では、全ての被処理サブセットがハッシュテーブル１１６内のエントリに関連付けられる。しかしながら、例えばハッシュテーブル１１６が、同時処理されるサブセットの数より多くのハッシュエントリ４０２を含む場合、コンプレッサ１１２は、ハッシュテーブル１１６を更新するために１又は複数の方式を適用して良い。例えば、ハッシュエントリ４０２のような１又は複数の空のハッシュエントリがＳＩＭＤエンジン１０６の一致検索動作の間に検出された場合、空のハッシュエントリの各々を有するハッシュエントリ４０２のうちの１又は複数は、更新されて、被処理サブセットのうちの１つに関連付けらて良い。これは、それぞれのハッシュエントリ４０２が、それぞれの被処理サブセットの計算したハッシュ値３２０のような計算したハッシュ値３２０と、被処理サブセットのデータアイテム３１０のような第１データアイテムへのポインタと、を含むよう生成されることを意味する。

別のシナリオでは、ＳＩＭＤエンジン１０６の一致検索動作の間に、１又は複数の計算したハッシュ値３２０は、ハッシュテーブル１１６に格納された１又は複数のハッシュ値と一致する。しかしながら、比較動作に続いて、コンプレッサ１１２は、被処理サブセットの内容（データアイテム）と、（一致するハッシュエントリによりポイントされた）関連サブセットの内容（データアイテム）とが同じでないことを示す。このような場合、コンプレッサ１１２は、ハッシュテーブル１１６内のそれぞれのハッシュエントリ４０２を、被処理サブセットの第１データアイテム３１０をポイントするポインタで更新して良い。ハッシュ値は当然に同じであり、したがって、コンプレッサ１１２はそれを変更しない。

コンプレッサ１１２は、更に、新しく生成したハッシュエントリ４０２が最近のサブセットに関連付けられた新しく計算したハッシュ値３２０を含むことを可能にするために、ハッシュエントリ４０２のうちの１又は複数をドロップする１又は複数の方法及び／又は技術を適用して良い。

コンプレッサ１１２によりＳＩＭＤエンジンに発行される更新命令の種類、シノプシス、特徴、及び／又は使用法は、プロセッサ１０４及び／又はＳＩＭＤエンジン１０６のアーキテクチャに従い適応されて良い。例えば、ＩＡプロセッサ１０４では、コンプレッサ１１２は、ＳＩＭＤエンジン１０６にハッシュテーブル１１６内の更新動作を実行するよう指示するために、以下の関数２に示されるように、ＳＳＥ命令セットから「ｓｃａｔｔｅｒ」命令を使用して良い。

関数２：
void__m５１２i_m５１２_１３２scatter_epi３２(void* base_addr, __m５１２i vindex, __５１２i a, int scale)
シノプシス：
void__m５１２i_m５１２_１３２scatter_epi３２(void* base_addr, __m５１２i vindex, __５１２ia, int scale)
#include “immintrin.h”
Instruction :vpscatterdd vm３２{k}, zmm
CPUID Flags :AVX５１２F for AVX−５１２, KNCNI for KNC
説明：
３２ビットインデックスを用いて、aからメモリに３２ビット整数を散乱させる。３２ビット要素は、base_addrで開始するアドレスに格納され、vindex内の各３２ビット要素によりオフセットされる（各インデックスはscale内の因子によりスケーリングされる）。scaleは１、２、４、又は８であるべきである。
動作：
FOR j:=０ to １５
i:=j*３２
MEM[base_addr+SignExtend(vindex[i+３１:i])*scale]:=a[i+３１:i]
ENDFOR

コンプレッサ１１２は、ＳＩＭＤエンジン１０６に更新動作を実行するよう指示するために、以下の擬似コード抜粋２に表されるようにｓｃａｔｔｅｒ命令を発行して良い。
擬似コード抜粋２：
hashTable[hashes[i]]=position[i] for i in ０…１５

ここで図５を参照すると、図５は、本発明の幾つかの実施形態による、ＳＩＭＤエンジンを用いて複数のハッシュテーブルエントリを同時更新する例示的なシーケンスの概略図である。ハッシュテーブル１１６のようなハッシュテーブルに対する例示的な更新シーケンス５００の間、コンプレッサ１１２のようなコンプレッサは、ハッシュテーブル１１６を、ハッシュエントリ４０２のような１又は複数の新しいハッシュエントリで同時更新するよう、ＳＩＭＤエンジン１０６のようなＳＩＭＤエンジンに指示する。例示的なシーケンス５００は、前述の例示的なロードシーケンス３００、例示的な同時計算シーケンス３０１、及び例示的な同時検索シーケンス４００に続く。ＳＩＭＤエンジン１０６は、ハッシュエントリ４０２を更新したハッシュ値及び被処理サブセットへの更新したポインタで更新するために、８個の更新動作５１０を同時に開始する。ＳＩＭＤエンジン１０６は、更新されたハッシュエントリ４０２の各々を、計算したハッシュ値３２０のうちのそれぞれ１つ、及び計算したハッシュ値３２０に関連付けられたそれぞれのサブセットの第１データアイテム３１０へのポインタで更新する。例示的な更新シーケンス５００において分かるように、ＳＩＭＤエンジン１０６は、ハッシュテーブル１１６内の８個のハッシュエントリ４０２を更新するために、８個の更新動作５１０を同時に開始する。例えば、更新動作５１０Ａはハッシュエントリ４０２Ｇを、データアイテムＳ_Ｋ３１０Ａ乃至Ｓ_Ｋ＋３３１０Ｄを含む被処理サブセットについて計算した計算したハッシュ値３２０Ａ、及び被処理サブセットの第１データアイテム３１０であるデータアイテムＳ_Ｋ３１０Ａをポイントする更新されたポインタで更新するために行われる。更新動作５１０Ａに続いて、データアイテムＳ_Ｋ３１０Ａ乃至Ｓ_Ｋ＋３３１０Ｄを含む被処理サブセットが、関連サブセットと考えられる。同様に、更新動作５１０Ｂはハッシュエントリ４０２Ｃを、データアイテムＳ_Ｋ＋１３１０Ｂ乃至Ｓ_Ｋ＋４３１０Ｅを含む被処理サブセットについて計算した計算したハッシュ値３２０Ｂ、及び被処理サブセットの第１データアイテム３１０であるデータアイテムＳ_Ｋ＋１３１０Ｂをポイントする更新されたポインタで更新するために行われる。更新動作５１０Ｂに続いて、データアイテムＳ_Ｋ＋１３１０Ｂ乃至Ｓ_Ｋ＋４３１０Ｅを含む被処理サブセットが、関連サブセットと考えられる。同時更新動作５１０は全ての被処理サブセットについて同様であり、ハッシュエントリ４０２Ｋを更新するために行われる更新動作５１０Ｈまで同じ方法である。更新動作５１０Ｈの間、ハッシュエントリ４０２Ｋは、データアイテムＳ_Ｋ＋７３１０Ｈ乃至Ｓ_Ｋ＋１０３１０Ｋを含む被処理サブセットについて計算した計算したハッシュ値３２０Ｈ、及び被処理サブセットの第１データアイテム３１０であるデータアイテムＳ_Ｋ＋７３１０Ｈをポイントする更新されたポインタで更新される。更新動作５１０Ｈに続いて、データアイテムＳ_Ｋ＋７３１０Ｈ乃至Ｓ_Ｋ＋１０３１０Ｋを含む被処理サブセットが、関連サブセットと考えられる。

もう一度、図２を参照する。２１６に示すように、コンプレッサ１１２は、圧縮出力ストリーム１３０を被処理サブセットで更新する。入力データストリーム１２０内の関連サブセット（前のサブセット）と一致する（同じデータアイテム３１０を有する）とされた被処理サブセット毎に、コンプレッサ１１２は、圧縮出力ストリーム１３０内の被処理サブセットを関連サブセットの位置へのポインタで置き換える。入力データストリーム１２０内のどの関連サブセット（前のサブセット）とも一致しないとされた被処理サブセット毎に、コンプレッサ１１２は、圧縮出力ストリーム１３０内に被処理サブセット自体を配置する。

決定点である２１８に示すように、コンプレッサ１１２は、追加データアイテムが入力データストリーム１２０内で利用可能かどうかを調べる。追加データアイテム３１０が検出された場合、処理２００はステップ２０６に枝分かれし、ステップ２０６乃至２１６は追加サブセットグループについて繰り返される。コンプレッサ１１２が入力データストリーム１２０の終わりに達したと決定した場合、処理２００は２２０に枝分かれする。

２２０に示すように、コンプレッサ１１２が入力データストリーム１２０を処理した後、コンプレッサ１１２は、例えばＩ／Ｏインタフェース１０２を用いて圧縮出力ストリーム１３０を出力する。

圧縮出力ストリーム１３０のフォーマットは、従来知られているレガシ（標準的な）圧縮方法、特に逐次圧縮を適用する方法により入力データストリーム１２０について生成された圧縮出力ストリームに準拠して良い。圧縮出力ストリーム１３０の準拠は、従来知られている標準的な伸長方法、技術、及び／又はツールを用いて圧縮出力ストリーム１３０を伸長することを可能にする。当然に、伸長フォーマットは、コンプレッサ１１２により利用される圧縮フォーマットに選択されて良い。例えば、圧縮出力ストリーム１３０がＬＺ４圧縮データフォーマットに従う場合、標準的なＬＺ４伸長方法、技術、及び／又はツールが圧縮出力ストリーム１３０を伸長するために要求されて良い。

＜例＞
ここで、以上の記載と一緒に本発明を非限定的に説明する以下の例を参照する。

ＳＩＭＤエンジン１０６のようなＳＩＭＤエンジンを利用する圧縮処理により提供される性能向上を検証するために、幾つかの実験が行われた。実験中、入力データストリーム１２０のような標準的な入力データストリームが、現在当分野で知られているような入力データストリームに逐次適用されるＬＺＯ圧縮アルゴリズムを用いて圧縮された（レガシ方法）。同じ標準的な入力データストリーム１２０は、また、同時にハッシュ値３２０を計算し３３０及びハッシュテーブル１１６を検索するために、ＳＩＭＤエンジン１０６を利用する処理２００により適用されるような単純な圧縮アルゴリズムを用いて圧縮された。両方の圧縮方法（レガシ及び処理２００）は、１６バイトＳＩＭＤアーキテクチャを有するＩｎｔｅｌによる３．０ＧＨｚ動作周波数のＡｄｖａｎｃｅｄ Ｖｅｃｔｏｒ Ｅｘｔｅｎｓｉｏｎｓ（ＡＶＸ）プロセッサで実行された。実験は、以下のような様々な圧縮率：１．０、２．３、及び３．８について行われた。実験の結果は以下の表１に示される。

［表１］

表１から明らかなように、ＳＩＭＤエンジン１０６を用いる圧縮処理２００は、レガシ（標準的な）圧縮処理に比べて〜４０％の有意な性能向上を示す。

本発明の種々の実施形態の記載は、説明の目的で提示されたが、包括的であることを意図せず又は開示された実施形態に限定されない。多くの変更及び変形が、記載された実施形態の範囲及び精神から逸脱することなく、当業者に明らかである。ここで使用される用語は、実施形態の原理、実際の用途又は市場に見られる技術に優る技術的向上を最適に説明するために、又は当業者がここに開示された実施形態を理解できるようにするために、選択された。

本願から成熟する特許の寿命の間、ＳＩＭＤのような多くの関連ベクトル処理技術が開発されることが予想され、用語ＳＩＭＤの範囲は推測的に全てのこのような新技術を包含することが意図される。

ここで使用される用語「訳」は±１０％を表す。

用語「含む」、「含む」、「有する」（comprises、comprising、includes、including、having）及びそれらの活用は、「含むが限定されない」を意味する。この用語は、用語「から成る」及び「基本的に〜から成る」を包含する。

語句「基本的に〜から成る」は、組立又は方法が追加構成要素及び／又はステップを含み得るが、追加構成要素及び／又はステップが請求される組立又は方法の基本的且つ新規な特徴を実質的に変更しない場合だけである。

ここで用いられるように、単数を表す語（「a」、「an」及び「the」）は、特に文脈上明示されない限り、複数への参照も含む。例えば、用語「化合物（a compound）」又は「少なくとも１つの化合物（at least one compound）」は、それらの混合物を含む複数の化合物を含み得る。

語「例示的な」は、「一例、例、又は説明を提供する」ことを意味するために本願明細書で用いられる。「例示的な」として記載される任意の実施形態は、必ずしも、他の実施形態より好適である又は有利であると考えられず及び／又は他の実施形態からの特徴の組み込みを排除しない。

語「任意的な」は、「幾つかの実施形態において提供され、他の実施形態で提供されない」ことを意味するために、本願明細書で用いられる。本発明の任意の特定の実施形態は、そのような特徴が対立しない限り、複数の「任意的な」特徴を含み得る。

本願を通じて、本発明の種々の実施形態が範囲形式で提示され得る。理解されるべきことに、範囲形式の記載は、単に便宜及び簡潔さのためであり、本発明の範囲に対する柔軟性のない限定として考えられるべきではない。したがって、範囲の記載は、全ての可能な下位範囲、並びに該範囲内にある個々の数値を具体的に開示しているものと考えられるべきである。例えば、１乃至６のような範囲の記載は、１乃至３、１乃至４、１乃至５、２乃至４、２乃至６、３乃至６、等のような下位範囲、並びに該範囲内の個々の数、例えば１、２、３、４、５、及び６を具体的に開示していると考えられるべきである。これは、範囲の幅に拘わらず適用される。

数値範囲が本願明細書に示されるときはいつも、示された範囲内の任意の前述の数（分数又は整数）を含むことを意味する。語句、第１指示数と第２指示数との「間に分布する／の範囲」、及び第１指示数から第２指示数「まで分布する／の範囲」は、本願明細書で同義的に使用され、第１及び第２指示数並びにそれらの間の全ての分数及び整数を含むことを意味する。

明確さのために別個の実施形態の文脈で記載された本発明の特定の特徴は、単一の実施形態の中で組み合わせて提供されても良いことが理解される。反対に、簡潔さのために単一の実施形態の文脈で記載された本発明の種々の特徴は、別個に又は任意の適切な小結合において、又は本発明の任意の他の記載された実施形態において適切であるとき提供されても良い。種々の実施形態の文脈で記載された特定の特徴は、実施形態がこれらの要素無しで動作不能でない限り、これらの実施形態の基本的特徴と考えられない。

本願明細書で言及される公報、特許、及び／又は特許出願は、参照により、各々個々の公報及び／又は特許出願が具体的に及び個々に参照により本願明細書に組み込まれるべきであると示されるように同程度に、それらの全体が本願明細書に組み込まれる。さらに、本願における任意の参照の引用又は特定は、このような参照が本発明に対して従来技術として利用可能であることの許可として考えられるべきではない。見出しが使用される範囲で、それらは必ずしも限定として考えられるべきではない。

Claims (15)

1. 入力データストリームを圧縮して圧縮出力データストリームを生成するシステムであって、
   ハッシュテーブルを格納するメモリであって、前記ハッシュテーブルは複数のハッシュエントリを含み、各ハッシュエントリは、入力データストリームの複数のデータアイテムのうちの続くデータアイテムの複数のサブセットのうちの関連サブセットのハッシュ値と、前記関連サブセットのメモリ位置へのポインタと、を含む、メモリと、
   前記メモリに結合されるプロセッサであって、
   以下の動作：
   被処理サブセットのうちのサブセット毎に前記ハッシュ値を計算し、
   各計算したハッシュ値の一致について前記ハッシュテーブルを検索し、
   前記一致の結果に従い、前記ハッシュテーブルを更新する、
   を実行し、前記動作のうちの少なくとも１つの動作は、単一命令多重データ処理、ＳＩＭＤ、エンジンに、前記複数のサブセットのうちの連続サブセットのグループの各被処理サブセットについて、前記少なくとも１つの動作を同時実行するよう指示することにより実行され、
   前記一致の結果及び前記一致の結果に依存する比較の比較結果に従い、前記圧縮出力データストリームを更新し、
   前記複数の関連サブセットについて、前記計算、検索、及び更新を繰り返して、前記圧縮出力データストリームを生成する、よう適応されるプロセッサと、
   を含み、
   前記複数のサブセットの各々は、前記入力データストリームに渡りスライドウインドウをスライドさせ、前のサブセットの最も早いデータアイテムが省略され、新しいデータアイテムが追加されることにより、生成される、システム。
2. 前記複数の関連サブセットの各々は、前記ＳＩＭＤエンジンのアーキテクチャに従い定義された所定数のデータアイテムを含む、請求項１に記載のシステム。
3. 前記グループ内の被処理サブセットの数は、前記ＳＩＭＤエンジンのアーキテクチャに従い設定される、請求項１又は２に記載のシステム。
4. 前記一致の結果は、各計算したハッシュ値の前記ハッシュテーブル内に存在する既存ハッシュ値との一致を示す、請求項１乃至３のいずれかに記載のシステム。
5. 前記比較は、前記一致の結果が前記計算したハッシュ値の前記ハッシュテーブル内の一致するハッシュ値との一致を示す場合に、前記比較結果を生成するよう行われ、
   前記比較は、前記計算したハッシュ値を有する前記被処理サブセットの前記データアイテムと、前記一致するハッシュエントリ内の前記ポインタによりポイントされる前記関連サブセットの前記データアイテムとの間の比較を含む、
   請求項１乃至４のいずれかに記載のシステム。
6. 前記比較結果が、前記被処理サブセット及び前記関連サブセットの前記データアイテムが同一であると示す場合、前記被処理サブセットは、前記圧縮出力データストリーム内の前記関連サブセットへのポインタにより置き換えられ、
   前記比較結果が、前記被処理サブセット及び前記関連サブセットの前記データアイテムが同一でないと示す場合、前記被処理サブセットは、前記圧縮出力データストリーム内で更新され、前記ハッシュテーブルは前記被処理サブセットの新しいハッシュエントリにより更新される、
   請求項１乃至５のいずれかに記載のシステム。
7. 前記被処理サブセットのうちのサブセット毎に前記ハッシュ値を計算する前記動作を同時実行することは、前記プロセッサが被処理サブセットの前記グループを前記ＳＩＭＤエンジンの少なくとも１つのＳＩＭＤレジスタにロードすること、及び前記ＳＩＭＤエンジンがサブセットの前記グループを同時処理すること、を含み、前記同時処理は、
   前記グループの前記被処理サブセットを互いに離すこと、
   被処理サブセット毎に異なるシフト値を用いて前記被処理サブセットをシフトすること、及び、前記被処理サブセットを処理して前記被処理サブセット毎にハッシュ値を生成すること、を含む、請求項１乃至６のいずれかに記載のシステム。
8. 各計算したハッシュ値の一致について前記ハッシュテーブルを検索する前記動作を同時実行することは、前記プロセッサが、前記ＳＩＭＤエンジンに、前記計算したハッシュ値の各々の前記ハッシュテーブルに格納されたハッシュ値との一致について同時検索するよう指示することを含む、請求項１乃至７のいずれかに記載のシステム。
9. 前記一致の結果に従い、前記ハッシュテーブルを更新する前記動作を同時実行することは、前記プロセッサが、前記ＳＩＭＤエンジンに、前記少なくとも１つの被処理サブセットに関連付けられたエントリにより、前記ハッシュテーブルを同時更新するよう指示することを含む、請求項１乃至８のいずれかに記載のシステム。
10. 前記圧縮出力データストリームは、レガシ圧縮方法を用いて圧縮された標準的圧縮出力データストリームに準拠し、前記圧縮出力データストリームは、レガシ伸長方法を用いて伸長される、請求項１乃至９のいずれかに記載のシステム。
11. 入力データストリームを圧縮して圧縮出力データストリームを生成する方法であって、
    複数のハッシュエントリを含むハッシュテーブルを格納するステップであって、各ハッシュエントリは、入力データストリームの複数のデータアイテムのうちのデータアイテムの複数のサブセットのうちの関連サブセットのハッシュ値と、前記関連サブセットのメモリ位置へのポインタと、を含む、ステップと、
    以下の動作：
    被処理サブセットのうちのサブセット毎に前記ハッシュ値を計算し、
    各計算したハッシュ値の一致について前記ハッシュテーブルを検索し、
    前記一致の結果に従い、前記ハッシュテーブルを更新する、
    を実行するステップであって、前記動作のうちの少なくとも１つの動作は、プロセッサの単一命令多重データ処理、ＳＩＭＤ、エンジンに、前記複数の関連サブセットのうちの連続サブセットのグループの各被処理サブセットについて、前記少なくとも１つの動作を同時実行するよう指示することにより実行される、ステップと、
    前記一致の結果及び前記一致の結果に依存する比較の比較結果に従い、前記圧縮出力データストリームを更新するステップと、
    前記複数のサブセットを通じて、前記計算、検索、及び更新を繰り返して、前記圧縮出力データストリームを生成するステップと、
    を含み、
    前記複数のサブセットの各々は、前記入力データストリームに渡りスライドウインドウをスライドさせ、前のサブセットの最も早いデータアイテムが省略され、新しいデータアイテムが追加されることにより、生成される、方法。
12. 前記被処理サブセットのうちのサブセット毎に前記ハッシュ値を計算する前記動作を同時実行することは、前記プロセッサが被処理サブセットの前記グループを前記ＳＩＭＤエンジンの少なくとも１つのＳＩＭＤレジスタにロードすること、及び前記ＳＩＭＤエンジンが被処理サブセットの前記グループを同時処理すること、を含み、前記同時処理は、
    前記グループの前記被処理サブセットを互いに離すこと、
    被処理サブセット毎に異なるシフト値を用いて前記被処理サブセットをシフトすること、及び、前記被処理サブセットを処理して前記被処理サブセット毎にハッシュ値を生成すること、を含む、請求項１１に記載の方法。
13. 各計算したハッシュ値の一致について前記ハッシュテーブルを検索する前記動作を同時実行することは、前記プロセッサが、前記ＳＩＭＤエンジンに、前記計算したハッシュ値の各々の前記ハッシュテーブルに格納されたハッシュ値との一致について同時検索するよう指示することを含む、請求項１１に記載の方法。
14. 前記一致の結果に従い、前記ハッシュテーブルを更新する前記動作を同時実行することは、前記プロセッサが、前記ＳＩＭＤエンジンに、前記少なくとも１つの被処理サブセットに関連付けられたエントリにより、前記ハッシュテーブルを同時更新するよう指示することを含む、請求項１１に記載の方法。
15. 前記圧縮出力データストリームは、レガシ圧縮方法を用いて圧縮された標準的圧縮出力データストリームに準拠し、前記圧縮出力データストリームは、レガシ伸長方法を用いて伸長される、請求項１１乃至１４のいずれか一項に記載の方法。

Images