JP7010548B2 - ハイブリッドデータ圧縮および解凍のための方法、デバイス、およびシステム - Google Patents

Description

関連出願の相互参照
本特許出願は、２０１５年５月２１日出願のスウェーデン国特許出願第１５５０６４４－７号、名称「ＭＥＴＨＯＤＳ，ＤＥＶＩＣＥＳ ＡＮＤ ＳＹＳＴＥＭＳ ＦＯＲ ＤＡＴＡ ＣＯＭＰＲＥＳＳＩＯＮ ＡＮＤ ＤＥＣＯＭＰＲＥＳＳＩＯＮ」の優先権を主張し、その内容を参照により全体として本明細書に援用する。また、本特許出願は、２０１６年１月２９日に出願のスウェーデン国特許出願第１６５０１１９－９号、名称「ＭＥＴＨＯＤＳ，ＤＥＶＩＣＥＳ ＡＮＤ ＳＹＳＴＥＭＳ ＦＯＲ ＤＥＣＯＭＰＲＥＳＳＩＮＧ ＤＡＴＡ」の優先権を主張し、その内容を参照により全体として本明細書に援用する。

技術分野
本特許出願の開示は、一般に、例えば、コンピュータシステムのキャッシュ／メモリサブシステムおよび／またはデータ転送サブシステム、またはデータ通信システムにおけるデータ圧縮および解凍の分野に関する。

データ圧縮は、データのサイズを低減するために使われる定着した技法である。これは、メモリ容量を増やすために、コンピュータシステムのメモリサブシステム中に保存されるデータに適用される。また、この技法は、コンピュータシステム内の相異なるサブシステムの間でデータが転送される際に、あるいは、一般に、通信ネットワークを含むデータ通信システムの２点の間で転送が行われる際に使用される。

データ圧縮は、１）入力として未圧縮のデータを取り込み、データ値をそれぞれの符号語に置き換える（文献では、符号化、コード化、またはコードとも言われている）ことによって未圧縮データを圧縮データに変換する圧縮（符号化とも言う）、および、２）入力として圧縮データを取り込み、符号語をそれぞれのデータ値に置き換えることによって圧縮データを圧縮されてないものに変換する解凍（復号とも言う）の２つの基本的オペレーションを必要とする。データ圧縮は、解凍後の実際のデータ値が圧縮前の当初のものと正確に同じである（ロスレス）か、あるいは解凍後のデータ値が当初のものと異なっており、当初の値が復元できない（ロッシー）かによって、ロスレスまたはロッシーであり得る。圧縮および解凍は、それぞれの方法、デバイス、およびシステムを実現するソフトウェアもしくはハードウェア、またはソフトウェアとハードウェアとの組み合わせにおいて実装され得る。

図１には、コンピュータシステム１００の一例が示されている。コンピュータシステム１００は、例えば相互接続ネットワークなどの通信手段を使ってメモリ階層１１０に接続された、１つまたは複数の処理ユニットＰ１．．．Ｐｎを含む。各処理ユニットは、プロセッサ（またはコア）を含み、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ（中央処理装置））、ＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ（グラフィックス処理ユニット））、または一般に、計算を行うブロックとすることができる。他方で、メモリ階層１１０はコンピュータシステム１００のストレージサブシステムを構成し、１つまたは複数のレベルＬ１～Ｌ３に編成することが可能なキャッシュメモリ１２０と、メモリ１３０（メインメモリとしても知られる）とを含む。メモリ１３０は補助的ストレージ（例えば、ハードディスクドライブ、ソリッドステートドライブ、またはフラッシュメモリ）にも接続されてもよい。メモリ１３０は、高速メインメモリ（例えば、ＤＤＲ）およびフラッシュメモリなど、複数のレベルに編成することができる。本例のキャッシュメモリ１２０は、３つのレベルを含み、Ｌ１およびＬ２はプライベートキャッシュであり、処理ユニットＰ１～Ｐｎの各々は専用のＬ１／Ｌ２キャッシュに接続され、Ｌ３は、全ての処理ユニットＰ１～Ｐｎの間で共有される。別の例では、当業者なら全てを認識しているように、種々のキャッシュ階層を実現することが可能であり、さらに多くの、さらに少ないキャッシュレベルで、もしくはキャッシュレベルなしでも、キャッシュをプライベートまたは共有に割り当てても割り当ててなくても、様々なメモリレベル、種々の数の処理ユニットとともに、一般には処理ユニットとメモリサブシステムとの間の種々の組み合わせで、実現することが可能である。

データ圧縮は、種々の手法でコンピュータシステムに適用することができる。図２は、図１の例示システム１００に対するのと類似のコンピュータシステムの例２００を示す。そこでは、データがメモリ、例えばかかるコンピュータシステムのメインメモリに圧縮される。これは、データが、メモリ中に保存される前に前述のようなそれぞれの圧縮オペレーションによって圧縮され、データがメモリを出て行く際に解凍されることを表す。

図３に示されたコンピュータシステムの別の例３００では、キャッシュシステムのＬ３キャッシュにデータ圧縮を適用することができる。前の例と同様に、データがキャッシュに保存される前に圧縮が必要であり、データがキャッシュから（例えば、データが圧縮されていない他のキャッシュレベル（Ｌ２）またはメモリ３３０に向けて）出て行く前に解凍が必要である。別の例において、データは、キャッシュ階層の任意のレベルに圧縮して保存することが可能である。

また、データは、コンピュータシステム中の相異なるサブシステムの間で転送されるときにだけ圧縮されてもよい。図４に示されたコンピュータシステムの別の例４００では、データは、Ｌ３キャッシュとメモリ４３０との間で、それぞれの通信手段を使って転送されるときに圧縮される。前の例と同様に、データが転送される前に圧縮され、相手方端で受信されたときに解凍されるように、通信手段の両端に圧縮部および解凍部が存在している必要がある。

コンピュータシステムの別の例５００では、図５に示されるように、サブシステムの組み合わせにおいてデータ圧縮を適用することが可能である。この例では、データは、メモリ５３０中に保存されるときと、メモリ５３０とキャッシュ階層５２０との間で転送されるときとに圧縮される。このように、データがキャッシュ階層５２０からメモリ５３０に移動するとき、データはＬ３から転送される前にだけ圧縮が必要なようにしてもよい。あるいは、メモリ５３０を出てキャッシュ階層５２０に行く圧縮データは、メモリ５３０をキャッシュ階層５２０に接続する通信手段の他方の端に受信されたときにだけ解凍が必要なようにしてもよい。コンピュータシステム中の種々のサブシステムに圧縮を適用する組み合せに関しては、どのような例も可能であり、当業者によって実現ができよう。

また、通信ネットワーク内の２つの任意の点の間でデータの転送を行うことが可能である。図６は、２点の間の通信ネットワーク６０５を含むデータ通信システム６００の一例を示す。この図ではデータはトランスミッタ６１０によって転送され、レシーバ６２０によって受信される。かかる例において、これらの点は、ネットワーク中の２つの仲介ノードとすることも、通信リンクの発信元および宛先のノードとすることも、またはこれらの場合の組み合わせとすることもできる。図７中の例示のシステム７００について描かれているように、データ圧縮はかかるデータ通信システムへの適用が可能である。データがトランスミッタ７１０によって通信ネットワーク７０５上に送信される前に圧縮を適用することが必要である一方、レシーバ７２０によって受信された後に解凍を適用することが必要である。

データ圧縮を実現するための多種多様のアルゴリズム（スキーム）がある。データ圧縮アルゴリズムの１つのファミリに、統計的圧縮アルゴリズムがあり、このアルゴリズムは、データ依存性があり、データ値の統計的特性に基づいて可変長（可変幅とも言う）の符号を割り当てるので、エントロピーに近い圧縮効率を提供することが可能である。高頻度で出現するデータ値の符号化には短い符号語が、低頻度で出現するデータ値の符号化にはより長い符号語が用いられる。ハフマン符号化は、周知の統計的圧縮アルゴリズムである。

解凍を加速するために使われるハフマン符号化の周知の一バリエーションに、カノニカルハフマン符号化がある。これに基づけば、符号語は数列特性を有する、すなわち同じ長さの符号語は連続する整数である。

従来技術の中には、カノニカルハフマンベースの圧縮および解凍メカニズムの例が存在する。かかる圧縮および解凍メカニズムは、ハフマンベースの圧縮および解凍を実行するために前述の例において使用することが可能である。

例えばカノニカルハフマン符号化などのハフマン符号化を実装する、従来技術によるコンプレッサ９００の一例が図９に示されている。これは未圧縮のブロックを入力として取り込み、該ブロックはデータ値のストリームであり、本開示全体を通して全般にｖ１、ｖ２、．．．、ｖｎで表される１つまたは複数のデータ値を含む。ストレージユニットまたは未圧縮のブロックからのデータ値の抽出器とすることができるユニット９１０は、可変長符号化ユニット９２０にデータ値を供給する。可変長符号化ユニット９２０は、符号テーブル（ＣＴ：Ｃｏｄｅ Ｔａｂｌｅ）９２２および符号語（ＣＷ：ｃｏｄｅｗｏｒｄ）セレクタ９２８を含む。ＣＴ９２２は、ルックアップテーブル（ＬＵＴ：Ｌｏｏｋ Ｕｐ Ｔａｂｌｅ）として、または（任意の何らかのアソシアティビティを有する）コンピュータキャッシュメモリとして実装することができるテーブルであり、１つまたは複数のエントリを包含する。各エントリは、或る符号語ＣＷ９２５および或る符号語長（ｃＬ：ｃｏｄｅｗｏｒｄ－ｌｅｎｇｔｈ）９２７を使って圧縮が可能な値９２３を含む。統計的圧縮アルゴリズムによって使われる様々な符号語のセットは可変長なので、これらを、各エントリが固定サイズの幅を有するＣＴ９２２（符号語９２５）中に保存する場合、これらにゼロ詰めをしなければならない。符号語長９２７は、可変長符号化の（例えば、ビットでの）実際の長さを保持する。ＣＷセレクタ９２８は、実際のＣＷを識別するためにｃＬを用い、詰められたゼロを棄てる。次いで、符号化された値は残りの圧縮値と連結され、全体で圧縮ブロックを形成する。前述の圧縮ステップに沿った圧縮方法の例示的なフローチャートが図１１に示されている。

従来技術によるデコンプレッサ１０００の一例が図１０に示されている。カノニカルハフマン解凍は２つのステップ、符号語検出および値の復元、に分割できる。これらステップの各々は、ユニット：（１）符号語検出ユニット（ＣＤＵ：Ｃｏｄｅｗｏｒｄ Ｄｅｔｅｃｔｉｏｎ Ｕｎｉｔ）１０２０、および（２）値復元ユニット（ＶＲＵ：Ｖａｌｕｅ Ｒｅｔｒｉｅｖｅ Ｕｎｉｔ）１０３０によって実装される。ＣＤＵ１０２０の狙いは、圧縮シーケンス（すなわち、圧縮されたデータ値の符号語のシーケンス）内の有効な符号語を見付けることである。ＣＤＵ１０２０は、コンパレータ１０２２のセットと、優先エンコーダ１０２４とを含む。各コンパレータ１０２２ａ、ｂ、ｃは、可能性のある各ビットシーケンスを既知の符号語と比較し、本例では、この符号語は、特定長に対する（符号生成のときの）最初に割り当てられたカノニカルハフマン符号語（ＦＣＷ：Ｆｉｒｓｔ－ａｓｓｉｇｎｅｄ ｃａｎｏｎｉｃａｌ Ｈｕｆｆｍａｎ ｃｏｄｅｗｏｒｄ）である。別の実装において、最後に割り当てられたカノニカルハフマン符号語も使用可能であろうが、その場合、正確になされた比較と異なることがある。（例えば、ＦＩＦＯまたはフリップフロップとして実装された）ストレージユニット１０１０中に保存可能であり、コンパレータの数とその中の一番幅広のコンパレータの最大幅を決める、比較されることになる前述のビットシーケンスの最大サイズは、符号の生成時に決められた有効ハフマン符号語の最大長（ｍＣＬ）の如何による。また一方、この最大長は、かかる（例えば、ソフトウェアまたはハードウェアの）デコンプレッサの実装の選択に左右される設計、コンパイル、構成、またはランタイムでの特定の値に束縛され得る。コンパレータ１０２２からの出力は、マッチする符号語の長さ（図１０では「マッチする長さ」と記されている）を出力する構造体１０２４のような優先エンコーダの中に挿入される。これに基づけば、検出された有効な符号語（マッチする符号語）が、ストレージユニット１０１０中の保存されていたビットシーケンスから抽出され、ビットシーケンスは、ＣＤＵ１０２０が次の有効な符号語を判断できるように、「マッチする長さ」が定義するのと同じ位置分シフトされ、空白の部分には圧縮シーケンスの次のビットがロードされる。

他方で、値復元ユニット（ＶＲＵ：Ｖａｌｕｅ Ｒｅｔｒｉｅｖｅ Ｕｎｉｔ）１０３０は、オフセットテーブル１０３４、減算器ユニット１０３６、および解凍ルックアップテーブル（ＤｅＬＵＴ：Ｄｅｃｏｍｐｒｅｓｓｉｏｎ Ｌｏｏｋ Ｕｐ Ｔａｂｌｅ）１０３８を含む。前のステップからの「マッチする長さ」が使われて、これも前のステップで判断されたマッチする符号語の演算値から減算せねば（１０３６）ならないオフセット値（オフセットテーブル１０３４中に保存されている）が判定され、ＤｅＬＵＴ１０３８のアドレスが得られる。そこでは、検出された符号語に対応する当初のデータ値がそのアドレスから検索され得、解凍ブロック１０４０中に保持されている解凍値の残りに付加される。デコンプレッサのこのオペレーションは、（図１０中で圧縮ブロックとして記された）圧縮保存された入力圧縮シーケンス中の全ての値が解凍データ値ｖ１、ｖ２、．．．、ｖｎとして復元されるまで繰り返される。

前述の解凍ステップに沿った解凍方法の例示的なフローチャートが、図１２中に示されている。

前述のコンプレッサおよびデコンプレッサは、迅速かつ効果的に、可変長のハフマン符号化でデータのブロックを圧縮し、可変長ハフマン符号化で圧縮されたデータのブロックを解凍することができる。また、デルタベース、パターンベースなどの他の圧縮および解凍アルゴリズムを実装するコンプレッサおよびデコンプレッサを含む他の圧縮スキームも使用可能である。

前述したような圧縮スキームには、不可避的に、圧縮および解凍に起因する待ち時間および複雑性が加わってくる。圧縮および解凍は、前述の例示のコンピュータシステムのキャッシュおよび／またはメモリサブシステム中に圧縮が適用されるとき、クリティカルメモリアクセスパスにある。また、圧縮および解凍は、コンピュータシステムまたは通信ネットワーク中のデータ転送サブシステムに圧縮および解凍が適用されるとき、転送待ち時間を増加させる可能性がある。

データは、データ値を形成するデータ型の如何によって特定のサイズのチャンクでアクセスされ処理される。特定のデータ型のデータ値は、しばしば特定の値のローカリティ特性を示す。従来技術の圧縮スキームは、圧縮および解凍処理を単純化し圧縮および解凍の待ち時間を低く保つために、どのようなデータ型が値のローカリティの根本要因であるかについて先験的な仮定を行うことによって、上記を利用しようと試みる。

値のローカリティは、ａ）時間的な値のローカリティ、およびｂ）空間的な（またはクラスタ化された）値のローカリティの２つの主な概念を含む。時間的な値のローカリティは、同じ値がしばしば出現することを示す。統計的圧縮アルゴリズムは、この値のローカリティの概念を利用した圧縮アルゴリズムの例である。他方、空間的な値のローカリティは、値が数字的に類似であることを示す。かかる値はベース値との差で値を符号化するという意味なので、デルタ符号化は、空間的値のローカリティを利用する圧縮アルゴリズムの例である。また、時間的値のローカリティは、ｉ）例えば、コンピュータシステム中のキャッシュサブシステム、および／またはメモリサブシステム、および／またはデータ転送サブシステム中で、データブロックが、図１３および図１４の左側に示されるように、全部がゼロ値のデータ値を包含する（ヌル（ｎｕｌｌ）ブロックデータ型と言われる）、ゼロ値ローカリティと、ｉｉ）例えば、データブロック中の値が幅狭の符号無し整数値で、０～２５５の範囲に属するが３２ビットで表現する必要があるとき、それらの全てがそれらの最上位の２４ビットに０のビットを有する（幅狭値データ型と言われる）、幅狭値ローカリティと、の特定の場合を含む。幅狭値ローカリティは、有意ベースの圧縮アルゴリズム、またはパターンベースの圧縮アルゴリズムによって利用される。

統計的圧縮スキームは、合理的なデフォルトの方策と見なしてよい。但し、これらは、必ずしも最高の圧縮性をもたらさない。例えば、中程度に共通性のある整数は、統計的圧縮スキームを使うと、最も共通性のある整数よりも長い符号語によって置き換えられる。また前記整数が空間的にも近い場合、代わりにデルタ符号化を使って、それらをさらに高密度にコード化できる可能性があり得る。データブロック中のデータ値には相異なるデータ型があり、および／または相異なる値のローカリティ特性を示すので、様々なデータ型に対し常に他より良く実行できる圧縮スキームはなく、圧縮性におけるロバストネスを保証することはできない。本発明者らは、データ圧縮および解凍の技術分野には改良の余地があると認識している。

データ圧縮および解凍の技術分野に改良を提供することが本発明の目的である。

本開示は、一般に、例えば、コンピュータシステム、および／またはデータ通信システム中のキャッシュサブシステム、および／またはメモリサブシステム、および／またはデータ転送サブシステムに圧縮が適用される際に、データ値のデータブロックを圧縮し、圧縮されたデータ値のデータブロックを解凍するための方法、デバイス、およびシステムを開示する。前記サブシステム中でデータを効果的に圧縮するための、様々な方法、デバイス、およびシステムがあり、これらは、その設計を単純化し圧縮および解凍待ち時間を低減するために、値のローカリティの根本要因として特定のデータ型について設計時仮定を行っている。しかしながら、データブロックは、複数のデータ型の可能性のある複数の値を含んでいるので、１つの圧縮方法が常にベストではなく、ロバストな圧縮性は保証できない。方法、デバイス、およびシステムは、２つまたは複数の圧縮方法およびデバイスを一緒に組み合わせることによって、データ値のデータブロックの圧縮および解凍を向上させ、前記圧縮方法およびデバイスは、特定のデータ型のデータ値を効果的に圧縮する。本発明の開示の第一概念によれば、ハイブリッドデータ圧縮方法、デバイス、およびシステムは、複数の圧縮方法およびデバイスを組み合わせており、ハイブリッドデータ圧縮方法、デバイス、およびシステムは、主たる選択基準として入力データブロックの支配的なデータ型を用いて、最適の圧縮方法およびデバイスを選択し、データ型は、予測方法およびデバイスによって予測される。本発明の開示の第二発明概念によれば、ハイブリッドデータ圧縮方法、デバイス、およびシステムは、２つの圧縮方法とデバイスとを組み合せ、その一方は、例えば可変長符号化を使ってデータブロックを効果的に圧縮し、他方は、複数の同じ共通値を含むデータブロックを１ビットだけで圧縮する。本発明の開示の第三発明概念によれば、高精度の予測方法（およびデバイス）が提示され、前記予測方法（およびデバイス）は、主たる選択基準として前記ブロックの予測される支配的なデータ型を用いて、入力ブロックを圧縮するための最適の圧縮方法（およびデバイス）をランタイムで予測する。前記予測方法（およびデバイス）は２つのフェーズを含み、第一フェーズでは、本方法は、データブロックを複数のセグメントに分割し、各セグメントに対し、そのデータ型を予測するために特定のビット部分を検査し、第二フェーズでは、第一フェーズの結果がある順序で評価され、最適の圧縮方法（およびデバイス）が判定される。第四発明概念によれば、予測された圧縮方法（およびデバイス）は、オラクル選択を参照として使って予測が不正確なことが判明した場合、ランタイムで調整できる。

本発明の第一態様は、未圧縮データブロックを圧縮データブロックに圧縮するためのハイブリッドデータ圧縮デバイスであって、この未圧縮データブロックは１つまたは複数のデータ型の１つまたは複数のデータ値を含み、本ハイブリッドデータ圧縮デバイスは、各コンプレッサがそれぞれのデータ圧縮スキーム用に構成された複数のデータコンプレッサと、未圧縮のデータブロックのデータ値のデータ型を予測し、主たる基準として予測されたデータ型のうちの支配的なデータ型を用いて、前記複数のデータコンプレッサの中から推定最適データコンプレッサを選択するように構成された予測器メカニズムと、を含み、本ハイブリッドデータ圧縮デバイスは、選択された推定最適データコンプレッサに未圧縮のデータブロックの全体を圧縮させることによって、圧縮データブロックを生成するように構成される。

本発明の第二態様は、未圧縮データブロックを圧縮データブロックに圧縮するためのハイブリッドデータ圧縮方法であって、未圧縮データブロックは１つまたは複数のデータ型の１つまたは複数のデータ値を含み、本ハイブリッドデータ圧縮方法は、未圧縮データブロックのデータ値のデータ型を予測するステップと、主たる基準として予測されたデータ型のうちの支配的なデータ型を用いて、複数のデータ圧縮スキームの中から、推定最適データ圧縮スキームを選択するステップと、圧縮データブロックを生成するために、選択された推定最適データ圧縮スキームによって未圧縮データブロックの全体を圧縮するステップとを含む。

本発明の第三態様は、圧縮されたデータブロックを、１つまたは複数のデータ型の１つまたは複数のデータ値を含む解凍データブロックに解凍するためのハイブリッドデータ解凍デバイスであって、本ハイブリッドデータ解凍デバイスは、各デコンプレッサがそれぞれのデータ解凍スキーム用に構成された複数のデータデコンプレッサを含み、本ハイブリッドデータ解凍デバイスは、前記複数のデータデコンプレッサの間で選択された推定最適データデコンプレッサに圧縮データブロックの全体を解凍させることによって、解凍データブロックを生成するように構成される。

本発明の第四態様は、圧縮データブロックを、１つまたは複数のデータ型の１つまたは複数のデータ値を含む解凍データブロックに解凍するためのハイブリッドデータ解凍方法であって、本ハイブリッドデータ解凍方法は、前記複数のデータ解凍スキームの中から推定最適データ解凍スキームを選択するステップと、解凍データブロックを生成するために、選択された推定最適データ解凍スキームによって、圧縮データブロックの全体を解凍するステップとを含む。

本発明の第五態様は、処理デバイスによってロードされ実行されると上記の第二態様による方法を遂行させるコード命令を含む、コンピュータプログラム製品である。

本発明の第六態様は、上記の第二態様による方法を遂行するように構成されたロジック回路を含むデバイスである。

本発明の第七態様は、処理デバイスによってロードされ実行されると上記の第四態様による方法を遂行させるコード命令を含む、コンピュータプログラム製品である。

本発明の第八態様は、上記の第四態様による方法を遂行するように構成されたロジック回路を含むデバイスである。

本発明の第九態様は、１つ以上のメモリと、上記の第一態様によるデータ圧縮デバイスと、上記の第三態様によるデータ解凍デバイスとを含むシステムである。

開示される実施形態の他の態様、目的、特徴、および利点は、以下の詳細な開示、添付の従属請求項、および図面から明らかとなろう。一般に、特許請求範囲中の全ての用語は、本明細書に明示で別に定義されていなければ、当該技術分野におけるそれらの通常の意味に従って解釈するものとする。

「ａ／ａｎ（或る）／ｔｈｅ（前記）［要素、デバイス、コンポーネント、手段、ステップなど］」の言及は、明示で別に記載されていなければ、要素、デバイス、コンポーネント、手段、ステップなどの少なくとも１つのインスタンスを言うものとオープンに解釈するものとする。本明細書で開示されるどの方法のステップも、明示で記載されている場合を除き、開示された通りに正確な順序で実行される必要ない。

背景技術および発明的態様の実施形態からの例は、以下の図面に関連して説明される。

それぞれが３レベルのキャッシュ階層およびメインメモリに接続されたｎ個の処理コアを含むコンピュータシステムのブロック図を示す。 メインメモリが圧縮された形でデータを保存している、図１のブロック図を示す。 Ｌ３キャッシュが圧縮された形でデータを保存している、図１のブロック図を示す。他のキャッシュレベルでも圧縮された形でデータを格納することが可能である。 例えばデータがメモリとキャッシュ階層との間で転送される際に、通信手段の中でデータが圧縮されている、図１のブロック図を示す。 圧縮が、メインメモリおよび該メモリをキャッシュ階層に接続しているリンクに適用可能な、図１のブロック図を示す。一般に、圧縮は、キャッシュ階層、転送手段（例えば、メモリをキャッシュサブシステムに接続しているリンク）、およびメインメモリのような部品の任意の組み合せに適用することが可能である。 通信ネットワーク中の２点を接続するデータ送信リンクのブロック図を示す。これらの点は、ネットワーク中の２つの仲介ノード、通信リンクの発信元および宛先ノード、またはこれら場合の組み合せであってよい。 転送されるデータが圧縮された形であり、データがトランスミッタ中で圧縮され、レシーバ中で解凍される必要があり得る、図６のデータ送信リンクのブロック図を示す。 左側にデータ値の未圧縮のブロックを、右側に、同じブロックのハフマン符号化を用いて生成された可変長符号化を使って圧縮された同じブロックを示す。未圧縮ブロックの全てのデータ値が、それぞれのハフマン符号語に置き換えられている。 図８に示されたようなハフマン符号化を用いてブロックを圧縮（または符号化）するために使われるコンプレッサ（圧縮器）を示す。 カノニカルハフマン符号化を用いて圧縮されたブロックを復号（または解凍）するのに使われるデコンプレッサ（解凍器）を示す。 可変長符号化（例えば、ハフマン）を用いてブロックを圧縮するための圧縮方法の例示的なフローチャートを示す。 可変長符号化（例えば、カノニカルハフマン）を用いて圧縮された圧縮ブロックの解凍するための解凍方法の例示的なフローチャートを示す。 左側に、ゼロデータ値だけを包含するブロックであるヌル未圧縮ブロックを、右側に、各ゼロ値が可能最小な幅（１ビット）の符号語によって置き換えられると仮定する可変長符号化を用いる、図９のコンプレッサによって圧縮された同じブロックを示す。 左側に、ゼロデータ値だけを包含するブロックであるヌル未圧縮ブロックを、右側に、１ビット符号化を用いて圧縮された同じブロックを示す。 左側に、図８中のものと同じブロックである未圧縮ブロックを、右側に、１ビットのインジケータ含む別の手法で圧縮された形の同じブロックを示し、このインジケータは、圧縮ブロックがヌルであるかどうか、および可変長符号化ビットシーケンスを表す。 図９のハフマンベースの圧縮デバイスと、ヌルブロック圧縮デバイスとを含む、図１４（圧縮ヌルブロック）および図１５（ビットインジケータおよび可変長符号語を含む圧縮ブロック）の未圧縮ブロックを圧縮できるハイブリッドデータ圧縮デバイスを示す。本ハイブリッドデータ圧縮デバイスは、ヌルブロック圧縮デバイスを使って全ブロックデータ値がゼロ値かどうかをチェックし、それを１ビットの符号化によって図１４のように圧縮し、それ以外の場合は、それをハフマンベースの圧縮デバイスによって図１５のように圧縮する。 図１０のデータ解凍デバイスと、ヌルブロック解凍デバイスと、ブロックの第一ビットが１であるかどうかをチェックすることによってブロックがヌルブロックとして圧縮されているかどうかを検知することが可能な追加ロジック（図１７ａの底部にある）とを含む、図１４（圧縮ヌルブロック）および図１５（ビットインジケータおよび可変長符号語を含む圧縮ブロック）の圧縮ブロックを解凍できるハイブリッドデータ解凍デバイスを示す。 図１０のデータ解凍デバイスと、ヌルブロック解凍デバイスの別の実施形態と、ブロックの第一ビットが１であるかどうかをチェックすることによってブロックがヌルブロックとして圧縮されているかどうかを検知することが可能な追加ロジック（図１７ｂの底部にある）とを含む、図１４（圧縮ヌルブロック）および図１５（ビットインジケータおよび可変長符号語を含む圧縮ブロック）の圧縮ブロックを解凍できるハイブリッドデータ解凍デバイスを示す。 ハイブリッドデータ圧縮システムの１つの実施形態を示し、該システムは、コンピュータシステムまたは通信ネットワーク中の送信リンクのキャッシュ／メモリ／リンクサブシステムの中に複数の圧縮および解凍デバイスを組み込み、このシステムは、ＨｙＣｏｍｐと言われ、ＨｙＣｏｍｐ圧縮デバイス、ＨｙＣｏｍｐ解凍デバイス、および目標先キャッシュ／メモリ／リンクの例示のサブシステムを含み、本ＨｙＣｏｍｐ圧縮デバイスは、圧縮デバイスのセット、および所与のデータ値のブロックに対する最適の圧縮デバイスを予測するための予測器を含む。 予測方法の例示的なフローチャートを示し、このチャートは、例示のハイブリッドデータ圧縮方法、デバイス、およびシステムによる使用が可能で、Ｉ）入力データブロックの１つまたは複数の特定の部分の検査、およびＩＩ）複数の方法の間で最適な圧縮方法の判定、の２つのフェーズを含む。 データブロック内の整数データ型を特徴識別することを目的とした、図１９の予測方法の検査フェーズの例示の実施形態を示す。 データブロック内のポインタデータ型を特徴識別することを目的とした、図１９の予測方法の検査フェーズの例示の実施形態を示す。 データブロック内の浮動小数点データ型を特徴識別することを目的とした、図１９の予測方法の検査フェーズの例示の実施形態を示す。 データブロックを、ヌルブロック、すなわちゼロ値を含むブロックとして特徴識別することを目的とした、図１９の予測方法の検査フェーズの例示の実施形態を示す。 データブロックを、負のヌルブロック、すなわち負符号のゼロ値を含むブロックとして、特徴識別することを目的とした、図１９の予測方法の検査フェーズの例示の実施形態を示す。 図１９の予測方法のフェーズＩを実装するブロック検査デバイス、および図１９の予測方法のフェーズＩＩを実装する判定デバイスを含む、図１９の予測方法の実装の例示の実施形態を示し、判定デバイスは、最適の圧縮デバイスの判定を導出するためのコンパレータおよび優先エンコーダを含む。 コンピュータシステムの最終レベルのキャッシュサブシステムの中に組み込まれる、図１８のシステムと類似のハイブリッド圧縮システムの例示の実施形態を示す。 ハイブリッドデータ圧縮システムが最終レベルのキャッシュに組み込まれる際の、タグストアおよびデータストアを含む、キャッシュ編成の例示の実施形態を示す。 所定の時間ウィンドウの間、予測された圧縮方法と、追跡された複数の支配的なデータ型に対して（オラクルセレクタによって生成された）理想的に選択された圧縮方法と、を比較することによって、予測方法の正確さを追跡する方法の例示的なフローチャートを示す。前記時間ウィンドウの後、本方法は、当該時点からそれ以降に向け、理想的選択に基づいて予測された圧縮方法を調整すべきかどうかを判定するために、前記正確さを特定の閾値と比較する。 本発明による、一般的ハイブリッドデータ圧縮方法示す概略的フローチャートである。 本発明による、一般的ハイブリッドデータ解凍方法示す概略的フローチャートである。 リンクサブシステムの例示の実施形態を示し、このサブシステムでは、本明細書に記載のハイブリッドデータ圧縮方法、デバイス、およびシステムが適用でき、この中では、リンクの一方端が発信元（トランスミッタ）としての機能を果たし、リンクの他方端が宛先（レシーバ）としての機能を果たす。 本発明による、ハイブリッドデータ圧縮デバイスおよびハイブリッドデータ解凍デバイスを含む一般的なシステムを示す。

本開示は、コンピュータシステム、および／またはデータ通信システム中のキャッシュサブシステム、および／またはメモリサブシステム、および／またはデータ転送サブシステムに圧縮が適用される際に、データ値の１つまたは複数のデータブロックを圧縮し、データ値の１つまたは複数の圧縮データブロックを解凍するためのハイブリッドデータ圧縮方法、デバイス、およびシステムを開示する。各前記データブロックは、任意のサイズであってよく、１つまたは複数の特定のデータ型である１つまたは複数のデータ値を含む。本明細書中で開示する方法、デバイス、およびシステムは、主たる基準として前記データブロック中で支配的なデータ型を用いて、２つまたは複数の圧縮スキームの中から推定最適なデータ圧縮スキームを選択し、前記データブロックに前記スキームを適用し、前記データブロックは、前記方法、デバイス、およびシステムによって開示される予測器を使って、前記ブロック内のデータ値のデータ型を予測することによって、前記支配的なデータ型の特徴識別される。

データブロックは任意のサイズであってよく、１つまたは複数のデータ型である１つまたは複数のデータ値を含む。図１に示されたようなコンピュータシステムの実施形態において、データ値のブロックは、あるいは、データのブロックがキャッシュ階層に保存されているときは、１）キャッシュライン、キャッシュセット、キャッシュセクタ、または類似に称され、データのブロックがメモリに保存されているときまたはかかるコンピュータシステムの通信手段中に転送されるときは、２）キャッシュライン、メモリページ、メモリセクタ、または類似に称されることがある。また一方、図６に示されたような通信ネットワーク内の送信リンクの実施形態では、データのブロックは、パケット、フリット、ペイロード、ヘッダ、または類似に称されることもあり、これらのより小さな部分であってもよい。

前記データブロック中で遭遇し得る、あり得る複数の前記データ型は、整数、ポインタ、浮動小数点数、文字、ストリング、およびブール値などの標準型を含む。また、これらあり得る複数の前記データ型は、非標準型も含むが、本明細書の背景技術に記載したように、それらは前記標準データ型の特殊なケースであり、コンピュータシステム、および／または通信ネットワーク中のキャッシュサブシステム、および／または、メモリサブシステム、および／またはデータ転送サブシステムにおいてはごく普通のものである。かかる非標準型の一例にヌルブロックデータ型がある。また、これら例示のデータ型に加えまたは換えて、以下に限らないが、コード命令、および特定のフォーマットもしくは規格（例えば、ビデオ、オーディオ）に沿ったデータ型を含め、他のデータ型も可能である。

本開示のここから以降は、本発明の態様による、データ圧縮デバイスおよびデータ解凍デバイスの特定の実施形態および関連する方法の説明である。この説明は、図１３～図２７、および図３０への具体的な参照をしながら行うこととする。その際、本開示は、図１３～図２７、および図３０に示される特定の実施形態に亘って一般化された一般的発明的態様を提示することになる。これらの一般的な発明的態様が、図２８、図２９、および図３１へのいくつかの参照によって説明されることになる。

最初に、例示するハイブリッドデータ圧縮方法（またはデバイス）は、ハフマンベースの統計的圧縮スキーム、およびヌルブロック圧縮スキームの２つの圧縮スキームを含むと仮定する。ハフマンベースの統計的圧縮スキームは、高い時間的な値のローカリティを示す何らかの型である値を含むデータブロックを効果的に圧縮することができる。かかる型の一例に整数がある。図８は、左側に８つのデータ値を含む前記ブロックの例を示し、一方、図８の右側には、例示のハフマン符号化を仮定したハフマンベースの圧縮スキームを使って圧縮された同じブロックが表されている。他方で、図１３は、左側に未圧縮のヌルデータブロックを示し、このデータブロックはゼロ値だけを含むブロックである。ハフマンベースの圧縮スキームはかかるブロックも圧縮できる。ゼロ値が可能最小なハフマン符号語（すなわち、１ビット）によって表現されることを仮定すれば、ハフマン符号化などの可変長符号化は、１符号語によって最善でも一データ値を置き換えることができるだけであり、最大圧縮率に拘束されているので、圧縮ヌルブロックは、図１３の右側に示されるように８ビットを含む。他方、ヌルブロック圧縮スキームは、図１４の右側に示されるように、１ビットだけによるゼロデータブロックを含むことが可能である。但し、ヌルブロック圧縮スキームは、ヌルブロック以外のブロックを圧縮することはできない。したがって、ハフマンベースの統計的圧縮スキームとヌルブロック圧縮スキームとを含むハイブリッドデータ圧縮方法は、支配的型がヌルブロックかまたは他の型のどちらであるかに基づいて、これら２つの間で最適のスキームを選択することによって最大の圧縮性を提供することができる。前記ハイブリッドデータ圧縮方法の予測器は、入力データブロックの全ての値でゼロ値が支配的であるかどうかを識別することができなければならず、それによって、データブロックはヌルブロックとして特徴識別されてヌルブロック圧縮スキームによって圧縮され、それ以外の場合は、入力データブロックはハフマンベースの圧縮スキームによって圧縮される。また、入力データブロックが圧縮できないまたは圧縮される代わりに拡張されることもあり得、この場合、未圧縮のまま留まるように選択することが可能である。

前記例示のハイブリッドデータ圧縮方法のデータ圧縮デバイスの実施形態が、図１６に描かれている。該デバイスは、入力未圧縮データブロック１６０５からのデータ値のストレージユニットまたは抽出器とすることができるユニット１６１０と、図９の可変長符号化ユニット９２０と類似のハフマンベースの統計的圧縮スキームの第二データコンプレッサ１６２０と、第一データコンプレッサ（ヌルブロックコンプレッサ）１６３０とを含む。ヌルブロックコンプレッサ１６３０は、コンパレータ１６３４ａ、ｂ、ｃおよびロジック１６３８を使って、入力未圧縮データブロック１６０５のデータ値が全てゼロ値かどうかをチェックする。これが真ならば当該１ビットの出力は「１」であり、そうでなければ「０」である。また、この例示のハイブリッドデータ圧縮方法の実施形態に対して、ヌルブロックコンプレッサは予測器とまったく同様に、データブロック全体がゼロデータ値を含むかどうか識別することが必要なので、このコンプレッサは、各受信データブロックの支配的型の予測器の代わりとなる。ヌルブロックコンプレッサ１６３０の出力が「１」の場合、予測の結果として入力未圧縮データブロック１６０５は、ヌルブロックとして分類され、１ビットで圧縮される。それ以外の場合は、当該ブロックはハフマンベースのコンプレッサ１６２０によって圧縮可能なブロックとして分類され、圧縮されたブロックは、「０」のビット（非ヌル圧縮ブロックであることを示す）が先行する可変長符号化（ハフマンベースのコンプレッサ１６２０からの出力）を含む。前記圧縮データブロック１６１８の例示の実施形態が、図１５の右手側に描かれている。ブロックの型の特徴識別を使って、本ハイブリッドデータ圧縮方法のコンプレッサの実施形態の出力に対する適切な圧縮ブロックの（セレクタ１６４０による）選択が制御される。当業者によって、このコンプレッサの代わりの他の実装を実現することもできよう。

前記の例示のハイブリッドデータ圧縮方法のデータ解凍デバイスの実施形態が、図１７ａに示されている。これは、図１０のデコンプレッサと類似のハフマンベースの第二データデコンプレッサ１７１０と、第一データデコンプレッサ（ヌルブロックデコンプレッサ）１７２０と、追加ロジックとを含み、前記追加ロジックは、レジスタ（例えばフリップフロップ）１７３０と、コンパレータ１７４０と、解凍データブロック１７９５に対するストレージユニット１７５０とを含む。例示のハイブリッドデータ圧縮方法のデータ解凍デバイスは、入力圧縮ブロックが圧縮ヌルブロックかどうかをチェックするために、コンパレータ１７４０を使って、入力圧縮データブロック１７０５の第一ビット（この第一ビットはレジスタ１７３０に保持されている）と「１」とを比較する。もしそうなら、解凍ブロック１７５０のデータ値は、ヌルブロックデコンプレッサ１７２０を使って値０に初期化され、該デコンプレッサは、前記比較の出力により制御され、値０を選択するセレクタをさらに含む。他方、レジスタ１７３０が、入力圧縮ブロックが非ヌル圧縮ブロックであることを示すビット「０」を保存している場合、本明細書の背景技術で述べたように、ハフマンベースのデコンプレッサ１７１０が前記入力圧縮データブロック１７０５を解凍する。

前記例示のハイブリッドデータ圧縮方法のデータ解凍デバイスの別の実施形態が図１７ｂに示され、これはヌルブロックデコンプレッサ１７２０のより単純なバージョンを包含する。解凍データブロック１７９５は、フリップフロップのアレイなどのストレージユニット１７５０中に保持され、このユニットは、該ストレージユニット１７５０の入力リセット信号が「１」にセットされると、値０にリセットすることができる（すなわち、ヌルブロックデコンプレッサ）。このリセット信号は、コンパレータ１７４０の出力端と接続されており、該出力端は、入力圧縮データブロック１７０５の第一ビットが、圧縮ヌルブロックと考えられる「１」である場合、実際に「１」を出力する。当業者によって、このデータ解凍デバイスの代わりの他の実装を実現することもできよう。

本データ解凍デバイス、および前記ハイブリッドデータ圧縮方法のデータ解凍デバイスの別の実施形態も、可変長ハフマン圧縮スキームの代わりに他のロスレス圧縮スキームを使って当業者により実現することができよう。さらに、ヌルブロック圧縮スキームと類似であるが、全ブロックに亘っての再現値が０値ではなく代わりの特定の共通値である別の圧縮スキームを含む、前記ハイブリッドデータ圧縮方法の別の実施形態も、当業者によって実現が可能であろう。

前述の実施形態は、２つの圧縮スキームだけを包含し、ヌルブロックと他の型のブロックとの間だけを区別する、単純化されたハイブリッドデータ圧縮方法である。しかしながら、実行されるアプリケーションの如何により、様々な型のデータが、コンピュータシステムのキャッシュ／メモリサブシステム中でアクセスされ、コンピュータシステム内で転送され、転送されるデータセットの領域如何によって、データ通信システム中で様々な型のデータが転送される。

図１８のブロック図は、ハイブリッドデータ圧縮システム１８００の或る実施形態を表し、該システムは、２つ以上の圧縮スキームを、コンピュータシステムのキャッシュ／メモリ／リンクサブシステム、またはデータ通信システム中の送信リンクの中に組み込み、これはＨｙＣｏｍｐと言われる。ＨｙＣｏｍｐシステム１８００は、データ圧縮デバイス（ＨｙＣｏｍｐコンプレッサ）１８１０、データ解凍デバイス（ＨｙＣｏｍｐデコンプレッサ）１８３０、および目標先キャッシュ／メモリ／リンクの例示のサブシステム１８２０を含む。ＨｙＣｏｍｐが、キャッシュ／メモリサブシステムに組み込まれるとき、ＨｙＣｏｍｐコンプレッサおよびＨｙＣｏｍｐデコンプレッサの両方が前記サブシステムに接続される。他方、ＨｙＣｏｍｐが、（コンピュータシステムもしくはデータ通信システム中の）リンクサブシステムに組み込まれるとき、ＨｙＣｏｍｐコンプレッサがトランスミッタの中に、ＨｙＣｏｍｐデコンプレッサがレシーバの中に組み込まれる。リンクの各端が、トランスミッタおよびレシーバの両方を含む場合、ＨｙＣｏｍｐコンプレッサおよびデコンプレッサの両方が各端に組み込まれる。

ＨｙＣｏｍｐコンプレッサ１８１０は、目標先サブシステム（キャッシュ／メモリ／リンク）に挿入された未圧縮データブロック１８０５を、予測器１８１２でデータ型予測を行うことによって圧縮する。予測器１８１２は、主たる基準として前記データブロック１８０５内で予測された支配的なデータ型を用いて、複数のデータ圧縮スキーム１８１４－１、１８１４－２、１８１４－３、１８１４－４（データコンプレッサ１８１４）の間で最善の圧縮性を提供すると予期されるものを選択して前記データブロック１８０５を圧縮する。次いで、圧縮データブロック１８１８が、目標先サブシステム１８２０のデータ部１８２８中に挿入され、一方、選択されたデータ圧縮スキームは、メタデータとして、目標先サブシステム１８２０のメタデータ部１８２４中に記録される１８１６。一実施形態において、このメタデータは、実際の圧縮データとは別に保存または送信することができ、別の実施形態では、メタデータは圧縮データに連結することができる。対照的に、ＨｙＣｏｍｐデコンプレッサ１８３０は、単に、メタデータ１８２４として格納されまたは送信された記録された選択圧縮スキームに基づいて、それぞれの複数のデータデコンプレッサ１８３５の複数のデータ解凍スキーム１８３５－１、１８３５－２、１８３５－３、１８３５－４から１つを選択することによって、圧縮データブロック１８３４を解凍する。しかして、ＨｙＣｏｍｐシステム１８００は、単一の圧縮スキームに比べて、予測に起因して圧縮の待ち時間が延長されることがあるが、但し、解凍は、単一の圧縮スキームを使うのと同じくらいの速さとなろう。このことは、目標先サブシステムが例えばキャッシュ／メモリの場合、圧縮よりも特に解凍がクリティカルメモリアクセスパスを用いるので、重要である。

ＨｙＣｏｍｐシステムの前記例示の実施形態１８００において、具体的な圧縮スキーム（図１８中の「Ｓ」、「Ｎ」、「Ｄ」、および「ＦＰ」）が、これらは特定の共通のデータ型のデータを効率的に圧縮するので選択される。この実施形態で検討されるこれらのデータ型は、整数、ポインタ、６４ビット高精度浮動小数点数、およびヌルブロック非標準データ型である。前記データ型と圧縮スキームとの関連は次の通りである。
・整数：整数は、統計的圧縮スキーム（図１８では「Ｓ」と表示されている）に関連付けられている。これは、かかるスキームが、可変長符号化を用いることにより、他のスキームよりも高頻度で使われる整数に、より高密度の符号を割り当てることによる。
・ポインタ：ポインタは、デルタ圧縮スキーム（図１８では「Ｄ」と表示されている）に関連付けられている。これは、ポインタが、通常、空間的な値のローカリティ、すなわち値が、ベース値へのデルタとして効率的に符号化できる少量の差のある値を表すことによる。
・浮動小数点数：浮動小数点数は、浮動小数点データを効果的に圧縮するため特殊化された特定の圧縮スキーム（図１８では「ＦＰ」と表示されている）に関連付けられている。ＦＰ圧縮方法の一例が、本特許出願と同時に出願された特許出願ＭＥＴＨＯＤＳ， ＤＥＶＩＣＥＳ ＡＮＤ ＳＹＳＴＥＭＳ ＦＯＲ ＳＥＭＡＮＴＩＣ－ＶＡＬＵＥ ＤＡＴＡ ＣＯＭＰＲＥＳＳＩＯＮ ＡＮＤ ＤＥＣＯＭＰＲＥＳＳＩＯＮに開示されており、同じ出願人および発明者を共有し、上記出願の内容は、参照によりその全体として本明細書に援用され、これは、提示される値のローカリティを増大するため、仮数を２つまたは複数のサブフィールドさらに分割した後、分離された各浮動小数点数の意味的に重要なデータ値を符号化（圧縮）する。
・ヌル（ｎｕｌｌ）ブロック：ヌルブロックは、前記ブロックを単一ビットだけで符号化するヌルブロック圧縮スキーム（図１８では「Ｎ」と表示されている）に関連付けられている。ヌルブロックのバリエーションは一般的であり、ブロックが負符号ゼロ浮動小数点値を含む場合もこれに含まれる。発明者らはかかるブロックを負のヌルブロックと称する。

データブロックは、様々なデータ型のデータ値を含み、各データ値を、そのデータ型に基づいて特定の圧縮スキームで圧縮することによって、最適の圧縮性が得られるであろう。しかしながら、これは、後での解凍のため選択された圧縮スキームを「知る」ために、メタデータの量をかなり増大することになるであろうし、これは、１つのブロックの解凍に対し、組み合わされた種々のスキームが必要になるので、解凍処理を複雑化し減速することにもなろう。本開示で開示するハイブリッドデータ圧縮方法、デバイス、およびシステムは、未圧縮データブロック全体に一圧縮スキームを適用する。適切な圧縮スキームの選択は、図１８に示されるＨｙＣｏｍｐコンプレッサ１８１０の予測器１８１２のような予測メカニズムによって、主たる基準として前記未圧縮データブロックのデータ値の支配的なデータ型を用いて行われる。

図１８のＨｙＣｏｍｐシステムの前記予測器１８１２は、予測の方法を実装している。かかる予測方法の或る実施形態は、図１９中の例示的なフローチャートによっても示される２つのフェーズを含む。
・フェーズＩ（検査）：未圧縮データブロックはセグメントに分割される。各セグメントの特定のビット位置（検査部分－ＩＰ（Ｉｎｓｐｅｃｔｉｏｎ Ｐｏｒｔｉｏｎ）と言う）が、全ての前記セグメントについてそのセグメントのデータ型を推測するために検査され、前記ブロック内の各予測データ型の出現をカウントする。このセグメントは、データ値と同じ粒度を持つように選択できるが、但し、データブロックは種々の粒度の値（大方はデータ型の如何による）を含むので、フェーズＩは同じ粒度のデータ（例えば、６４ビットのセグメント）を処理することにより単純化することができる。
・フェーズＩＩ（判定）：フェーズＩからの個別のセグメントの型特徴識別に基づいて、主として支配的なデータ型に基づいて、ブロックに対する最適の圧縮スキームが選択される。選択された圧縮スキームが、前記ブロックの全セグメントに適用される。

図１８に示されるような、コンピュータシステムのキャッシュ／メモリ／リンクサブシステム中で適用されるＨｙＣｏｍｐシステムの実施形態によって使用される前記予測方法においては、データブロックは６４バイト（すなわち、現今のコンピュータシステムで典型的サイズ）であり、セグメントのサイズは８バイト（すなわち、ブロックごとに８つのセグメント）として選択される。各検査部分（ＩＰ）のサイズ（幅）は、予測されるデータ型の如何による。前記予測方法のフェーズＩにおいて、データ型の特徴識別は次のように実行される。
・整数：ＩＰは、セグメントの最上位４バイトである。ＩＰが０ｘ００００００００（すなわち正の整数）もしくは０ｘＦＦＦＦＦＦＦＦ（すなわち負の整数）である場合、セグメントは整数として特徴識別され、それぞれのカウンタ（＃Ｉｎｔ）がインクリメントされる。図２０のブロック図は、データブロック２０１０内で整数データ型を特徴識別することを目的とした検査プロセスの例示の実施形態を示す。０ｘ００００００００との比較はコンパレータ２０２４ａ、ｂ、ｃなどで行われ、０ｘＦＦＦＦＦＦＦＦとの比較はコンパレータ２０２８ａ、ｂ、ｃなどで行われる。この比較の結果（例えば、マッチに対して「１」）は、マスク２０３４および２０３８中にマークされる。このマスクは、セグメントの数と同じ多さのビットを含む。２つのマスクの合併集合演算が行われ（これらマスクは、ロジックすなわちＯＲゲート２０４０と組み合される）、カウンタ２０５０は「１」の数をカウントし、これは、特徴識別された整数の数（すなわち＃Ｉｎｔカウント）である。
・ポインタ：ＩＰは、セグメントの最上位４バイトである。ＩＰの２つの最上位バイトが、０ｘ００００に等しく、ＩＰの２つの最下位バイトが０ｘ００００と不等の場合、当該セグメントはポインタとして特徴識別され、それぞれのカウンタ（＃Ｐｔｒ）がインクリメントされる。前記の特定の手法で最上位４バイトを検査する背後の理論的根拠は、４８ビットポンタを検出することにあり、このような例示幅は、現今のコンピュータシステムのキャッシュ／メモリサブシステム中のアドレスによって使われている。前記検査方策の１つの限界は、小さなポインタがポインタの代わりに整数として特徴識別されることである。図２１のブロック図は、データブロック２１１０内でポインタデータ型を特徴識別することを目的とする検査プロセスの例示の実施形態を示す。０ｘ００００との比較はコンパレータ２１２４ａ、ｂ、ｃなどで行われ、０ｘ００００との不等の比較はコンパレータ２１２８ａ、ｂ、ｃなどで行われる。この比較の結果（例えば、マッチに対して「１」）は、マスク２１３４および２１３８中にマークされる。このマスクは、セグメントの数と同じ多さのビットを含む。２つのマスクのＡＮＤ演算が行われ（これら２つのマスクは、両方の状態が保持されなければならないので、ロジックすなわちＡＮＤゲート２１４０と組み合される）、カウンタ２１５０は「１」の数をカウントし、これは、特徴識別されたポインタの数（すなわち＃Ｐｔｒカウント）である。
・ 浮動小数点数：ＩＰは、セグメントの最上位ビットの次の７ビットである。この理論的根拠は、ブロック中に包含される浮動小数点データ値が、しばしば同じ指数を有するか、またはそれら指数がクラスタ化されていることであり、しかして、７ビットのＩＰを相互に比較すれば（ＩＥＥＥ‐７５４規格によれば、セグメントが浮動小数点データ型である場合、ＩＰは指数の部分である）、それらまたはそれらのサブセットが指数のクラスタを形成するかどうかを明らかにできる。図２２のブロック図は、データブロック２２１０内で浮動小数点データ型を特徴識別することを目的とした検査プロセスの例示の実施形態を示す。前記実施形態では、ブロックセグメントのＩＰは、ペアで２つの手法、Ａ）相互から０の距離を有するセグメント（すなわち、隣接するセグメント）のＩＰのペア方式での比較２２２４と、Ｂ）相互から１の距離を有するセグメント（すなわち、両者の間に第三のセグメントを有するセグメントの比較）のＩＰのペア方式での比較２２２８と、で比較される。この比較の結果（例えば、マッチに対して「１」）は、マスク２２３４および２２３８中にマークされる。次いで、これらの比較の手法の各々に対し、それぞれのカウントがカウンタ２２４４および２２４８によってインクリメントされ、最終的に、２つ（すなわち、＃ＦＰ＿Ａおよび＃ＦＰ＿Ｂ）の間で最大のカウントが選択される。セグメントのサイズが８バイトなので、対象浮動小数点データ型は倍精度である。当業者は、単精度（または他の精度）の符号小数点数を検出することが可能な、または他の浮動小数点規格による、前記予測方法の別の実施形態を実現することもできよう。
・ （負の）ヌルブロック：ＩＰはセグメント全体である。各セグメントがゼロ値に等しい場合（０ｘ００．．．０）、ブロックはヌルブロックとして特徴識別され、各セグメントが負のゼロ値に等しい場合（０ｘ８０．．．０）、ブロックは負のヌルブロックとして特徴識別される。図２３ａは、データブロック２３１０をヌルブロックとして特徴識別することを目的とした検査プロセスの例示の実施形態を示し、また、図２３ｂは、データブロック２３１０を負のヌルブロックとして特徴識別することを目的とした検査プロセスの別の例示の実施形態を示す。

前記データ型の特徴識別処置は、前記方法の性能限界の如何によって、逐次的にもしくは並列に実行することができる。さらに、当業者は、この特徴識別が、単一のサイクルでもしくは個別のオペレーションとして複数のサイクルにパイプライン化して、比較、カウント、合併集合演算／ＡＮＤ演算でも実行されるように、各特徴識別ステップを実装することもできよう。また、コンパレータおよびカウンタも、当業者によって異なった手法で実装することも可能であろう。別の実施形態において、様々な粒度で現れるデータ型を明らかにするために、ブロックを様々なサイズのセグメント（すなわち、複数のセグメントサイズ）に同時に分割することができる。

図１９の例示的なフローチャートは、発見的方法として実装される前記予測方法の或る実施形態を示す。フェーズＩにおいて、前述のように、最初に検査部分がチェックされ、次いで、フェーズＩＩで、フェーズＩの結果を特定の順序で（言い換えれば、特定の優先度で）評価することによって、当該ブロックを圧縮するために最適の圧縮スキームが（前述の「Ｓ」、「Ｄ」、「Ｎ」、「ＦＰ」の中から）選択される。最初に、ブロックが（負の）ヌルブロックとして特徴識別された場合、ヌルブロック圧縮（「Ｎ」）が選択される。それ以外の場合は、カウント＃Ｉｎｔ、＃ＦＰ、および＃Ｐｔｒが全てゼロに等しいかどうかチェックされ、もしそうならば、予測方法は、ブロックデータがランダム性か、暗号化されているか、または考慮外のデータ型に属するので、効率的には圧縮できないと推測する。ゼロでなければ、圧縮スキームは、＃Ｉｎｔ、＃Ｐｔｒ、および＃ＦＰのカウントに基づいて、これらのカウントのうち＃Ｉｎｔが最大である場合は「Ｓ」、＃Ｐｔｒが最大である場合は「Ｄ」、＃ＦＰが最大である場合は「ＦＰ」が選択される。また、カウントの一部または全部が互い等しい場合、圧縮スキームは、「Ｓ」、「Ｄ」、「ＦＰ」の順序で選択される。

図２４のブロック図は、図１９の予測方法のハードウェア実装の例示のブロック図を示す。前記ブロック図は、図１９の予測方法のフェーズＩを実装する検査および特徴識別ユニット２４１０、ならびに、図１９の予測方法のフェーズＩＩを、共同して実装するコンパレータおよび優先エンコーダ、２４２０と２４３０とを含む。検査および特徴識別ユニット２４１０は、さらに、ＩＮＴ型特徴識別ユニット２０００と、ＰＴＲ型特徴識別ユニット２１００と、ＦＰ型特徴識別ユニット２２００と、ＮｕｌｌＢｌｏｃｋかつＮｅｇＮｕｌｌＢｌｏｃｋ型特徴識別ユニット２３００とを含む。ＩＮＴ、ＦＰ、およびＰＴＲ特徴識別ユニットからの結果（ユニット２４１０からの出力）は最初にユニット２４２０によって比較され、４ビットの符号化信号２４２５である、１０００（＃Ｉｎｔ＝０且つ＃ＦＰ＝０且つ＃Ｐｔｒ＝０）、０１００（最大＝＃Ｉｎｔ）、００１０（最大＝＃Ｐｔｒ）、および０００１（最大＝＃ＦＰ）が生成される。前記符号化信号２４２５は、ｉｓＮｕｌｌおよびｉｓＮｅｇＮｕｌｌ信号による優先エンコーダ２４３０への入力である。優先エンコーダ２４３０は、図１９の予測方法のフェーズＩＩに示すような（優先）順序での最適圧縮スキームの選択を実装する。当業者は、前記ハードウェアの実装を２つ以上の段階にパイプライン化することができよう。

前記予測方法および他の予測方法の別の実施形態を当業者によって実現することも可能であろう。重要なことは、当業者が、これらハイブリッドデータ圧縮方法、デバイス、およびシステムの別の実施形態を実現する場合は、対象とするシステム、コンテキスト、および用途の領域に応じて、他の圧縮スキームおよび／または他のデータ型も検討する必要があることである。

図２５は、図１８のＨｙＣｏｍｐハイブリッドデータ圧縮システムであるが、コンピュータシステムのキャッシュサブシステム、具体的には最終レベルキャッシュ（ＬＬＣ：ｌａｓｔ－ｌｅｖｅｌ ｃａｃｈｅ）に適用されたときのさらに別の実施形態２５００を示す。メインメモリ、およびキャッシュ階層の他の上位レベルのキャッシュが未圧縮の形でデータを保存していると仮定すれば、データは、メモリからＬＬＣ中に挿入される前に、またはデータが上位レベルのキャッシュからＬＬＣに書き戻されるときに圧縮される。他方、或るブロックがＬＬＣから退去するとき、またはそれが上位レベルのキャッシュによってフェッチされるときに、ブロックは解凍される必要がある。本ＨｙＣｏｍｐシステムは、メモリから挿入された、または上位レベルのキャッシュから書き戻された未圧縮のデータブロック２５０５を、前述の実施形態と同様なデータ型予測２５１２に基づいて、各未圧縮データブロックに対し最適の圧縮スキームを選択することによって圧縮する。次いで、圧縮されたデータブロック２５１８は、ＬＬＣのデータアレイ２５２８中に挿入され、使用されたスキームはメタデータとしてタグストア２５２４中に記録２５１６され、該ストアは、通常、キャッシュラインのメタデータ（例えば、タグ、有効およびダーティビット、リプレースメントステータス）を保存する。圧縮データブロック２５３４が、上位レベルキャッシュによって要求されたとき、またはメインメモリに向け退去するとき、圧縮データブロック２５３４は、単に、圧縮の過程でタグストア中に記録されたメタデータに基づいて適切なデコンプレッサ２５３５によって解凍される。

図２５のハイブリッド圧縮キャッシュシステム２５００は、特定の圧縮スキーム２５１４－１、２５１４－２、２５１４－３、２５１４－４、すなわち、ハフマンベースの統計的圧縮スキーム（例えば、米国特許出願公開第２０１３／０３１１７２２号中に開示されたもの）と、ＢＤＩ（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｒａｌｌｅｌ ａｒｃｈｉｔｅｃｔｕｒｅｓ ａｎｄ ｃｏｍｐｉｌａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ （ＰＡＣＴ ’１２）のＧｅｎｎａｄｙ Ｐｅｋｈｉｍｅｎｋｏ、Ｖｉｖｅｋ Ｓｅｓｈａｄｒｉ、Ｏｎｕｒ Ｍｕｔｌｕ、Ｐｈｉｌｌｉｐ Ｂ．Ｇｉｂｂｏｎｓ、Ｍｉｃｈａｅｌ Ａ．Ｋｏｚｕｃｈ、およびＴｏｄｄ Ｃ．Ｍｏｗｒｙによる、「Ｂａｓｅ－ｄｅｌｔａ－ｉｍｍｅｄｉａｔｅ ｃｏｍｐｒｅｓｓｉｏｎ：ｐｒａｃｔｉｃａｌ ｄａｔａ ｃｏｍｐｒｅｓｓｉｏｎ ｆｏｒ ｏｎ－ｃｈｉｐ ｃａｃｈｅｓ」に開示されたもの）と、ＦＰ－Ｈ（本出願人および発明者らによる前述の特許出願、ＭＥＴＨＯＤＳ， ＤＥＶＩＣＥＳ ＡＮＤ ＳＹＳＴＥＭＳ ＦＯＲ ＳＥＭＡＮＴＩＣ－ＶＡＬＵＥ ＤＡＴＡ ＣＯＭＰＲＥＳＳＩＯＮ ＡＮＤ ＤＥＣＯＭＰＲＥＳＳＩＯＮに開示されたもの）と、ＺＣＡ（Ｊｕｌｉｅｎ Ｄｕｓｓｅｒ、Ｔｈｏｍａｓ Ｐｉｑｕｅｔ、およびＡｎｄｒｅ Ｓｅｚｎｅｃの、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２３ｒｄ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ （ＩＣＳ ’０９）の議事録の、整数、ポインタ、浮動小数点、およびヌルブロックデータ型それぞれに関連する「Ｚｅｒｏ－ｃｏｎｔｅｎｔ ａｕｇｍｅｎｔｅｄ ｃａｃｈｅｓ」に開示されたもの）と、を使用する。これらのスキームは、これらがハードウェアに実装でき、しかしてキャッシュ圧縮に適用が可能なので選択されている。これらは、それぞれのデータ型に対し、圧縮および解凍待ち時間を、例示の圧縮キャッシュサブシステムなどに対して比較的に低くしながら、効率的な圧縮性をもたらす。

ハイブリッドデータ圧縮が適用される際のキャッシュ編成の或る実施形態が図２６に示され、これはＴＡＧストア２６１０およびＤＡＴＡストア２６２０を含む。このキャッシュ実施形態は、２つの手法のセットとの関連性を有する。従来型のキャッシュでは、圧縮が適用されない場合、各手法は、未圧縮のキャッシュブロック（またはキャッシュライン）を格納し、特定のタグ（例えば、キャッシュラインタグ２６１５）に関連付けられる。各タグは、図２６の左側に示されるように、複数のメタデータ（すなわち標準的メタデータ）を含み、「ｔａｇ」はブロックのアドレスに関連し、「ｖ」は有効ビットであり、ブロックが有効な場合にセットされ、「ｄ」はダーティビットであり、ブロックが変更された場合にセットされ、「ｒｅｐｌ」はリプレースメントステータス、すなわち、当該リプレースメントポリシーが最低使用頻度（ＬＲＵ：ｌｅａｓｔ－ｒｅｃｅｎｔｌｙ－ｕｓｅｄ）の場合、最小のカウンタ（このカウンタはブロックの使用に基づいてデクリメントされる）を有するブロックはキャッシュセットが満杯になったとき置き換えられる。

他方で、図２６の前記キャッシュサブシステムの圧縮が適用される場合、キャッシュ編成を変更する必要がある。従来技術のキャッシュ圧縮設計においては、タグストアは、データストアから切り離され、より多くのキャッシュブロックを格納し、圧縮によって解放されたスペースを利用できるようにするために、より多くのタグが各セットに関連付けられる。圧縮キャッシュブロックは、したがって、セット内部の任意のバイト位置に配置され、ポインタを使って位置付けされ、ポインタはメタデータのタグストア中に格納され、このポインタは、図２６中の追加メタデータ中では「ｉｄｘ」として表されている。例えば、図２６のキャッシュの実施形態では、２倍多くのタグ（すなわち、キャッシュセットごとに４つのタグ）が各キャッシュセットに関連付けられている。タグとキャッシュブロックとの間の関連付けが文字（Ａ、Ｂ、Ｃ、およびＤ）で表されている。さらに、データストア２６２０は複数のキャッシュセットを含む。各セットは、セット２６２８と同様であり、上限２つまでの未圧縮キャッシュブロック、および４つまでの圧縮キャッシュブロックを含む。圧縮ブロックＡはキャッシュセット２６２８の先頭（０バイト位置）に格納され、圧縮ブロックＣは、圧縮ブロックＡの終端の後の次のバイト位置に保存され、一方、圧縮ブロックＤは両方にまたがっている。圧縮ブロックの別の配置策は、セグメント化と言われ、これはキャッシュセットを固定サイズのセグメントに分割し、次いで各圧縮ブロックは、その圧縮ブロックのサイズに基づいて異なる数のセグメントを割り当てられる。当業者によって、圧縮ブロックの別の配置策を実装することも可能である。

新規ブロックがキャッシュに挿入され、例示のキャッシュセット２６２８中に保存される場合に、全てのタグが圧縮ブロックによって使用されている場合、それらブロックの１つを退去させる必要がある（ヴィクティムブロック（ｖｉｃｔｉｍ ｂｌｏｃｋ）としても知られる）。図２６のキャッシュの実施形態において、リプレースメントポリシーは最低使用頻度（ＬＲＵ）であり、しかして、最小のＬＲＵカウント２６１８を有するブロックＣがヴィクティムブロック２６２２となる。データが未圧縮で保存される従来式のキャッシュ設計では、１つのヴィクティムブロックで十分であるが、しかし、ハイブリッドデータ圧縮キャッシュの実施形態および最高圧縮されたキャッシュ設計においては、新規のブロックがヴィクティムよりも大きなサイズを有する場合に、キャッシュセット中のさらに多くのブロックを退去させる必要がある。コンパクション（ｃｏｍｐａｃｔｉｏｎ）も必要となるので、次のＬＲＵブロックを退去させるには時間がかかることがあり、コンパクションは、連続する自由なスペースを解放するために、圧縮ブロックを移動するプロセスとなる。この例示の実施形態では、隣接のブロック（図２６中のブロックＤ２６２４）が退去されるように選択される。図２６の底部に示されているキャッシュセット２６３８は、ブロック２６２２と２６２４とを新規のブロックＦ２６３２で置き換えた後のキャッシュセット２６２８と同様である。逆に、新規ブロックがヴィクティムのよりも小さい場合、次のＬＲＵブロックに対しより多くの連続するスペースを解放するためにコンパクションが行われる。

キャッシュサブシステム中で圧縮が適用される場合、タグ中に加える必要のある他の追加メタデータは、ブロックが圧縮されているかどうかを示す圧縮ステータスビット（図２６中では「ｃ」で表されている）である。キャッシュ中でハイブリッドデータ圧縮が適用される場合、例示のブロック中で使用されることを予測され選択された圧縮スキームが、「ａｌｇ」メタデータ中に記録される。この実施形態では、「ａｌｇ」は４つのスキーム、ＺＣＡ、ＢＤＩ、Ｈ、およびＦＰ－Ｈを定義している。特殊符号化のメタデータ（図２６では「ｅｎｃ」として表されている）は、圧縮スキーム依存である。例えば、選択されたスキームがＢＤＩの場合、これは、１）ベース＝８バイト、およびデルタ＝１、２または４バイト（３ケース）、２）ベース＝４バイト、およびデルタ＝１または２バイト（２ケース）、３）ベース＝２バイト、およびデルタが１バイト、の６つのケースの中から、例示のブロックを符号化するために使われるベース／デルタの組み合せを記録するための３ビットを必要とする。選択されたスキームがＺＣＡの場合、特殊符号化の右端のビットが、それがヌルブロックまたは負のヌルブロックかどうかを決める。残りのビットは使われない。他の圧縮スキームは、「ｅｎｃ」ビットを使う必要はない。

本開示のハイブリッドデータ圧縮方法、デバイス、およびシステムがコンピュータシステム中の（図２のような）メモリサブシステムに適用される場合、前記方法、デバイス、およびシステムの予測方法の、選択された圧縮スキームを追跡する上記で「ａｌｇ」で表された前記メタデータ、および選択された圧縮スキームに関連するそれぞれの「ｅｎｃ」メタデータは、ページテーブル構造体中に保存することができる。このページテーブルは、仮想アドレスの物理アドレスへの変換、および各ページについての現在ビット、ダーティビットなど、他の情報を含む。例えば、ハイブリッド圧縮が適用されたデータ値のブロックが、例えば或るページに対応する場合、前記「ａｌｇ」／「ｅｎｃ」メタデータを、ページごとの前記情報ビットとともに、そのページテーブル中の保存することができる。或るページがアクセスされる場合、その仮想から物理への変換がハードウェアキャッシュ構造体、変換索引バッファ（ＴＬＢ：Ｔｒａｎｓｌａｔｉｏｎ Ｌｏｏｋａｓｉｄｅ Ｂｕｆｆｅｒ）中に維持され、したがって、前記「ａｌｇ」／「ｅｎｃ」メタデータもＴＬＢ中に格納が可能である。

本開示のハイブリッドデータ圧縮方法、デバイス、およびシステムが、（図４のような）コンピュータシステムまたは（図７のような）通信ネットワーク中のリンクサブシステムに適用されている、別の実施形態において、「ａｌｇ」／「ｅｎｃ」メタデータの組み合せの全てまたはサブセットをメタデータキャッシュ中に維持することができる。リンク／ネットワークの構成に合わせ、一リンク端を発信元とすることができ、ブロックは圧縮されて送信され、および／または宛先となり、ブロックは受信されて解凍される。リンク端が発信元である場合、その端はコンプレッサおよびメタデータキャッシュを含み、リンク端が宛先である場合、その端はデコンプレッサおよびメタデータキャッシュを含み、リンク端が発信元および宛先の両方である場合、その端は、コンプレッサ、デコンプレッサ、およびコンプレッサおよびデコンプレッサの両方に使用される１つのメタデータキャッシュを含み、あるいは、１つのメタデータキャッシュはコンプレッサに使用され、もう１つのメタデータキャッシュはデコンプレッサによって使用される。図３０は、リンクサブシステムの例示の実施形態を示し、この実施形態では、ハイブリッドデータ圧縮方法、デバイス、およびシステムが適用され、リンクの一端（ノードｉ）は発信元（トランスミッタ）として機能し、リンクの他方の端（ノードｊ）は宛先（レシーバ）として機能する。

前記メタデータキャッシュの或るインスタンスは、１つまたは複数のエントリを含み、各エントリは、例えば「ＺＣＡ，ｎｅｇＮｕｌｌ」、「ＢＤＩ，Ｂ＝４／Ｄ＝２」など、前記「ａｌｇ」／「ｅｎｃ」メタデータの１つの特定の組み合せのＩＤを包含する。予測された圧縮デバイス／スキームを用いてデータブロックが圧縮されるとき、前記ＩＤを保持するそれぞれのメタデータキャッシュエントリのインデックスを得るために、発信元のメタデータキャッシュの中で前記予測されたデバイス／スキームのＩＤがルックアップされる。前記インデックスは、圧縮ブロックに先行して、その後に、または一緒に送信される。このインデックスは、適切な解凍デバイス／スキームのＩＤを読み出すため、宛先のメタデータキャッシュにアクセスするために使われる。発信元および宛先のメタデータキャッシュは、それらの内容の一貫性を保つために同期されている必要がある。メタデータキャッシュのサイズによりアクセス時間（したがって、圧縮および解凍待ち時間）およびインデックスの幅が決まり、複数の圧縮スキーム／デバイスが使用されると、メタデータキャッシュしたがってインデックス、およびアクセス時間が長くなり得る。別の実施形態において、メタデータキャッシュは、例えば、例示のスキーム／デバイスのセットが、複数のデータブロックに対し連続して使用される場合にも、圧縮スキーム／デバイスのＩＤの一サブセット（例えば４エントリ）だけを保持することができる。予測されたスキーム／デバイスのＩＤが発信元のメタデータキャッシュ中に見当たらない場合、そのエントリの１つが、例示のキャッシュリプレースメントポリシー（例えばＬＲＵ）を使って置き換えられ、それに伴い、宛先のメタデータキャッシュも更新される。当業者は、ハイブリッドデータ圧縮方法、デバイス、およびシステムを、コンピュータシステムまたは通信ネットワークに適用する際に、これらの予測された圧縮スキーム／デバイスを記録し読み出すための別の手法を、実装することもできよう。

ハフマンベースの統計的圧縮スキームは、例えば出現頻度などの統計的特質に基づいて、データ値に対し可変長の符号語を、より頻度の高い値には短い符号語を頻度の少ないものにはより長い符号語を割り当てる。符号化が前もって定義されていない場合、前記ハフマンベースの統計的圧縮スキームは、トレーニングフェーズおよび圧縮フェーズの２つのフェーズを含む。トレーニングフェーズの過程では、出現値（すなわち、ハイブリッド圧縮キャッシュシステムの前述の実施形態中のＬＬＣ中に格納された値）の値の頻度統計がモニタされ、＜値、カウンタ＞タプルを含むテーブルのような構造体中に収集される。前記テーブルの実施形態の例は従来技術中で説明されている。前記値の頻度統計が十分に収集されると、ハフマン符号化アルゴリズムを用いて、符号化の例が生成され、次いで、圧縮フェーズの過程で前記符号化を使ってデータ値が圧縮される。生成された符号化の品質は、統計収集プロセスの精度に大きく依存する。しかして、ハイブリッドデータ圧縮方法、デバイス、およびシステムの実施形態は、かかる圧縮スキームの圧縮過程だけでなく、トレーニングフェーズの過程にも予測の適用が可能である。このように、前記統計的圧縮スキームによって圧縮のために選択される型と無関係なデータ型に特徴識別されたデータブロックは、この値の頻度統計収集から無視することができ、潜在的により代表性のある統計のセット、つまりより良い符号化が得られる。別の実施形態において、この統計収集プロセスは、いかなるメタデータをも必要とせず、代わりに、前記統計的圧縮スキームのトレーニングフェーズの過程で、セグメントごとのよりきめ細かい型情報を使って、前記セグメントを統計の収集に用いるべきか無視すべきかを決めることができ、前記セグメントごとの型情報は、特定のデータ型と統計的圧縮スキームとの間の関連性によって、例えば、マスク２０３４／２０３８（図２０）、２１３４／２１３８（図２１）、２２３４／２２３８（図２２）によって検索することができる。

ＢＤＩは、２つのベース値へのデルタでブロック値を符号化することによるデルタ圧縮を使いキャッシュブロックを圧縮する。その主要構成において、前記ベース値の１つはゼロであり、他方はブロック中の最初の非ゼロ値である。ＢＤＩは、複数のベース／デルタ粒度を試みるが、ブロックは、全ての値が同じベース／デルタ粒度（前述した６つのケースの１つ）を使って符号化されている場合にだけ圧縮される。しかしながら、ＢＤＩは、ブロック中の全ての値が２つの値の範囲内にある場合にだけそのブロックが圧縮され、範囲内にない場合は未圧縮のまま残るという限界に悩まされる。ブロックが、３つ以上の値範囲内にあるデータ値を含む場合、そのブロックは、たとえ支配的なデータ型がポインタであっても圧縮されないことになる。こういった、既知の圧縮アルゴリズムに限界（または弱点）があるこの例示の実施形態のような場合、当業者が予測方法を構築するとき、決定プロセスに支配的なデータ型を超えた追加の選択基準を導入できる。この実施形態における１つのかかる基準は、ブロックの値が３つ以上の範囲に入るかどうかチェックするものであり、その時には、たとえ支配的なデータ型がポインタであっても、代わりに別の圧縮スキームを選択することができる。

ハイブリッドデータ圧縮システムの別の実施形態において、高頻度で出現する特徴識別されたブロック型に対する最適圧縮アルゴリズムの間違った予測については、予測器の決定をオラクルセレクタと比較することによって検出することができ、おそらくは訂正することができ、前記オラクルセレクタは、常に最良の圧縮スキームを選択する理想的なセレクタである。図２７の方法は或る例示的なフローチャートを示す。このチャートでは、モニタリングウィンドウ（図２７中で、予測がオラクル選択と比較される所定の回数だけ反復して測定される）で、予測圧縮スキームとオラクルの選択された圧縮スキームとが比較され、オラクルは、入力未圧縮ブロックを、全スキームを総当たりモードで使って圧縮し、最良の圧縮性をもたらすものを選び出すことを試みることによって実装され得る。この比較の結果は、カウンタで追跡され、各支配的なデータ型に対し１つずつ複数のカウンタが在る。モニタリングウィンドウの終了点において、（モニタリングウィンドウの過程で）追跡された各支配的なデータ型に対する測定された予測ミスが特定の閾値（ＴＨ：ｔｈｒｅｓｈｏｌｄ）を超えた場合、現時点およびそれ以降からの前記支配的なデータ型の出現に対し、予測器に選択された圧縮スキームをオラクルセレクタによって判断されたものにランタイムで調整することができ、予測方法の精度を潜在的に向上させる。前記モニタリングは、定期的にまたは必要に応じ繰り返すことができる。予測圧縮スキームとオラクル圧縮スキームとの間に不一致が生じた状態をマークするための基準の一例として、支配的なデータ型を用いることができる。別の実施形態は、例えば、ブロック内での支配的なデータ型および二番目に支配的なデータ型、または予測されたデータ型の使用など、前記状態を表すため他の手法の例を使用することができる。当業者は、ハイブリッドデータ圧縮方法、デバイス、およびシステム中で使われる予測方法およびデバイスの不正確な予測を訂正するための別の方法を実現することもできよう。

別の実施形態は、最善に達成された圧縮を上回る最適の圧縮スキームを選択するときに違った目標を用いることができる。例えば、ハイブリッドデータ圧縮が、図２５の実施形態などのコンピュータシステムのキャッシュサブシステム中に適用されるとき、圧縮スキームは、その圧縮効率だけでなく、圧縮および解凍の待ち時間に与える影響に基づいて選択するとよい。例えば、或る特性識別されたブロック型に対するベストの圧縮スキームＡが、２番目にベストの圧縮スキームＢよりも１０％より良好な圧縮性をもたらすが、解凍待ち時間に起因して３０％のキャッシュアクセス時間を増加させる場合、スキームＢがＡを越えて選択されることがあり得る。

予測方法は、好ましくは、プロセッサデバイス／プロセッサチップ、またはメモリデバイス／メモリチップ中に含まれたまたはこれらに関連付けられた任意のロジック回路によって、ランタイムで実行することができる。本開示の発明のさらなる発明的態様は、したがって、前述の方法を実行するように構成された、ロジック回路、プロセッサデバイス／プロセッサチップ、およびメモリデバイス／メモリチップを含む。

当然のことながら、明示で開示された実施形態以外の他の実施形態も、それぞれの発明の範囲内で同様に可能である。例えば、本開示の発明の各々は、限定はされないがコンピュータ用のメインメモリ（例えば、ランダムアクセスメモリ）を含め、キャッシュメモリ以外の他の型のメモリに対しても実装することができる。上記に換えてまたは加えて、本開示の発明の各々は、例えばプロセッサとメモリとの間で通信されているデータのリンク圧縮のため実装することも可能である。

一般に、本特許出願の中で言及されるエンティティ（例えば、データセット、データ型、データ値、データフィールド、データブロック、キャッシュブロック、キャッシュライン、データセグメントなど）のいずれに対してもデータサイズに特定の制限はない。

ここで、図２８、図２９、および図３１の一部を参照しながら、図１３～図２７、および図３０に示された具体的な実施形態を一般化した、一般的発明的態様を説明することとする。同様の参照符号が使われており、図面の１つでＸＸｎｎのフォーマットを有する参照符号は、一般に、他の図面のいずれにおいても、同じまたは少なくとも対応する要素ＹＹｎｎを表す。

１つの一般的発明的態様は、未圧縮データブロック（例えば、１８０５、２５０５）を圧縮データブロック（例えば、１８１８、２５１８）に圧縮するためのハイブリッドデータ圧縮デバイス（例えば、１８１０、２５１０）であり、未圧縮データブロックは１つまたは複数のデータ型の１つまたは複数のデータ値を含む。このハイブリッドデータ圧縮デバイスは、複数のデータコンプレッサ（例えば、１８１４、２５１４）を含み、各コンプレッサは、それぞれのデータ圧縮スキーム（例えば、１８１４－１．．．１８１４－ｎ、２５１４－１．．．２５１４－ｎ）用に構成される。また、本ハイブリッドデータ圧縮デバイスは、未圧縮データブロック（例えば、１８０５、２５０５）のデータ値のデータ型を予測し、主たる基準として予測されたデータ型の間での支配的なデータ型を用いて、前記複数のデータコンプレッサの中から推定最適なデータコンプレッサを選択するように構成された予測器メカニズム（例えば、１８１２、２５１２）を含む。本ハイブリッドデータ圧縮デバイスは、選択された推定最適データコンプレッサに未圧縮データブロックの全体を圧縮させることによって圧縮データブロック（例えば、１８１８、２５１８）を生成するように構成される。

本ハイブリッドデータ圧縮デバイスは、圧縮データブロック（例えば、１８１８、２５１８）に関連付けられ、選択された推定最適データコンプレッサのデータ圧縮スキームを識別する役割を果たすメタデータ（例えば、１８２４、２５２４、３０２４）を生成する（例えば、１８１６、２５１６、３０１６）ように構成することができる。加えて、本ハイブリッドデータ圧縮デバイスは、生成されたメタデータを、圧縮データブロック（例えば、１８１８、２５１８）と一緒にデータストレージ（例えば、１８２０、２５２０）に格納するように構成され、このデータストレージには、データ解凍デバイス（例えば１８３０、２５３０）によるアクセスが可能である。上記に換えて、このハイブリッドデータ圧縮デバイスは、生成されたメタデータ（例えば、３０２４）を、圧縮データブロック（例えば、３０１８）と一緒に、リンク（例えば、３０２０）を介してデータ解凍デバイス（例えば、３０３０）に送信するように構成されてもよい。

複数のデータコンプレッサ（例えば、１８１４、２５１４）は、第一データ圧縮スキーム用に構成された第一データコンプレッサ、および第一データ圧縮スキームとは異なる第二データ圧縮スキーム用に構成された第二データコンプレッサを含むことができる。第一および第二データ圧縮スキームの各々は、ロスレスまたはロッシー圧縮スキームとすることが可能である。

有利には、これら第一および第二データ圧縮スキームは、
・（例えば、ハフマン圧縮、カノニカルハフマン圧縮、算術符号化などの）統計的（可変長）符号化、
・ディクショナリベースの圧縮、
・デルタ符号化、
・パターンベースの圧縮、
・有意ベースの圧縮、または
・（例えば、ヌルブロック圧縮などの）共通ブロック値圧縮、
のうちの２つとして選択されたロスレス圧縮スキームである。

通常、第一データ圧縮スキームは、第一データ型のデータ値の間のデータローカリティを利用するように設計され、このデータローカリティは、時間的、空間的、またはこれらの組み合せであり、第二データ圧縮スキームは、第二データ型のデータ値の間のデータローカリティを利用するように設計され、このデータローカリティは、時間的、空間的、またはこれらの組み合せである。

このデータブロックは、通常、
・コンピュータシステム中のキャッシュの中にストレージするためのキャッシュライン、キャッシュセット、キャッシュブロック、またはキャッシュセクタ、
・メモリ中へのストレージまたはコンピュータシステム内での転送のためのメモリ行、メモリページ、もしくはメモリセクタ、および
・データ通信システム中の送信リンクを介して転送するためのパケット、フリット、ペイロード、またはヘッダ、
のうちの１つであってよい。

データ値のデータ型は、通常、だが限定せずに、整数、ポインタ、浮動小数点数、文字、ストリング、ブール値、コード命令、または（例えば、ビデオもしくはオーディオのフォーマットもしくは規格などの）特定のフォーマットもしくは規格によって定義されたデータ型のいずれかであってよい。

有利には、本ハイブリッドデータ圧縮デバイス（例えば、１８１０、２５１０）の予測器メカニズム（例えば１８１２、２５１２）は、未圧縮データブロック（例えば、１８０５、２５０５）をセグメントに分割し、セグメントを複数の候補データ型のうちの一予測データ型として分類するために、全セグメントに対し、各セグメントの検査ビット部分を検査し、未圧縮データブロックの支配的なデータ型を判定するため、全セグメントの予測されたデータ型の出現頻度を比較するように構成される。有利には、相異なる候補データ型に対して、これら検査ビット部分は異なっている。

候補データ型は、通常、整数、ポインタ、浮動小数点数、文字、ストリング、ブール値、共通データ値ブロック、データコード命令、または特定のフォーマットもしくは規格によって定義されたデータ型のうちの２つ以上であってよい。

或る有利な実施形態において（例えば図２０）、候補データ型の１つは整数であり、データブロックのサイズはｍバイトであり、セグメントのサイズはｎバイトであり、ｍ／ｎは２の倍数であり、検査ビット部分はセグメントの最上位のｐバイトであり、ｎ／ｐは２である。例えば、ｍ＝６４、ｎ＝８、ｐ＝４の値が適用できる。予測器メカニズム（例えば、１８１２、２５１２）は、検査ビット部分が、いくつかの事前定義されたｐバイト値のいずれかに等しい場合、セグメントを整数として分類するように構成され、これら事前定義ｐバイト値は、例えば、０ｘ００００００００および０ｘＦＦＦＦＦＦＦＦとすることができる。

この、または別の有利な実施形態（例えば、図２１）において、候補データ型の１つはポインタであり、データブロックのサイズはｍバイトであり、セグメントのサイズはｎバイトであり、ｍ／ｎは２の倍数であり、検査ビット部分はセグメントの最上位のｐバイトであり、ｎ／ｐは２である。例えば、ｍ＝６４、ｎ＝８、ｐ＝４の値が適用できる。予測器メカニズム（例えば、１８１２、２５１２）は、検査ビット部分の最上位の２バイトが、事前定義されたｐ／２バイト値に等しく、だが最下位の２バイトは不等である場合、セグメントをポインタとして分類するように構成され、この事前定義ｐ／２バイト値は、例えば、０ｘ００００とすることができる。

この、または別の有利な実施形態（例えば、図２２）において、候補データ型の１つは浮動小数点数であり、データブロックのサイズはｍバイトであり、セグメントのサイズはｎバイトであり、ｍ／ｎは２の倍数であり、検査ビット部分はセグメントの最上位ビットの次の最上位のｑビットである。例えば、ｍ＝６４、ｎ＝８、ｑ＝７の値が適用できる。予測器メカニズム（例えば、１８１２、２５１２）は、当該セグメントの検査ビット部分を、データブロック中の、同じまたはクラスタ化された浮動小数点指数を示す隣接のセグメントの検査ビット部分と突き合わせることによって、セグメントを浮動小数点数として分類するように構成される。

この、または別の有利な実施形態（例えば、図２３ａおよび図２３ｂ）において、候補データ型の１つは共通データ値であり、データブロックのサイズはｍバイトであり、セグメントのサイズはｎバイトであり、ｍ／ｎは２の倍数であり、検査ビット部分はセグメント全体である。例えば、ｍ＝６４、ｎ＝８の値が適用できる。予測器メカニズム（例えば、１８１２、２５１２）は、セグメントを、そのデータ値全てが同じ共通データ値を有する場合、共通データ値として分類するように構成される。有利には、この共通データ値はヌル値である。

有利には、本ハイブリッドデータ圧縮デバイスは、未圧縮データブロック（例えば、１８０５、２５０５）の全セグメントが共通データ値として分類されたとき、データ圧縮スキームとして共通ブロック値圧縮を備えるデータコンプレッサ（例えば、１８１４、２５１４）を推定最適データコンプレッサとして選択するように構成される。

さらに、予測器メカニズム（例えば、１８１２、２５１２）は、セグメントの２つの相異なる予測データ型が同一の出現頻度を有する場合、未圧縮のデータブロックの支配的なデータ型を決めるときにその１つを他方より優先するように構成することができる。例えば、予測器メカニズム（例えば、１８１２、２５１２）は、未圧縮のデータブロックの支配的なデータ型を判定するとき、整数を、ポインタおよび浮動小数点数よりも優先し、ポインタを、浮動小数点数よりも優先するように構成すればよい。

また、予測器メカニズム（例えば、１８１２、２５１２）は、セグメントに予測データ型の出現がない場合に、推定最適データコンプレッサとしてデフォルトのデータコンプレッサを選択するように構成することができる。上記に換えて、予測器メカニズム（例えば、１８１２、２５１２）は、セグメントに予測データ型の出現がない場合、推定最適データコンプレッサの代わりに無圧縮を選択するように構成してもよく、しかして未圧縮データブロックを圧縮するのを取り止めるように構成することができる。

一実施形態において、本ハイブリッドデータ圧縮デバイス（例えば、１８１０、２５１０）は、
・複数の圧縮サイクルの過程で、それぞれの支配的なデータ型に対するデータコンプレッサの理想的な選択に対して、それぞれの選択された推定最適データコンプレッサをモニタし、
・特定の支配的なデータ型の圧縮性に関し、別のデータコンプレッサがさらに効率的であった可能性を検知し、および
・今後の圧縮サイクルについて、当該特定の支配的なデータ型に対し、最適データコンプレッサを前記別のデータコンプレッサに変更する、ようにさらに構成される。

それぞれの支配的なデータ型に対するデータコンプレッサの理想的な選択はオラクルセレクタによって提供してもよく、該セレクタは、複数のデータコンプレッサ全て（例えば、１８１４、２５１４）のデータ圧縮スキームを使って未圧縮のデータブロックを圧縮し、それぞれの理想的選択として、それぞれの未圧縮データブロックに対する最善の圧縮性が得られるデータ圧縮スキームを有するコンプレッサを選定する。

本ハイブリッドデータ圧縮デバイスの一実施形態において、複数のデータコンプレッサは、共通ブロック値圧縮スキームである第一データ圧縮スキーム用に構成された第一データコンプレッサ（例えば、１６３０）、および第一データ圧縮スキームとは異なる、統計的（可変長）符号化、ディクショナリベースの圧縮、デルタ符号化、パターンベースの圧縮、および有意ベースの圧縮のうちの１つである第二データ圧縮スキーム用に構成された第二データコンプレッサ（例えば、１６２０）を含む。この実施形態のハイブリッドデータ圧縮デバイスは、予測器メカニズム（例えば、１６３０）によって未圧縮データブロック（例えば、１６０５）で共通データ値が支配的であることが判明した場合、第一データコンプレッサ（例えば、１６３０）に、未圧縮データブロック（例えば、１６０５）の全体を圧縮共通値データブロックに圧縮させることによって、圧縮データブロック（例えば、１６１８）を生成し、またそれ以外の場合は、第二データコンプレッサ（例えば、１６３０）に、第二データ圧縮スキームに従い未圧縮データブロック（例えば、１６０５）の全体を圧縮させることによって、圧縮データブロック（例えば、１６１８）を生成するように構成される。圧縮共通値データブロックは、単一のビットだけを有利に包含できる。この実施形態において、有益には、予測器メカニズム（例えば、１６３０）は第一データコンプレッサ（例えば、１６３０）に組み込まれる。さらに、予測器メカニズム（例えば、１６３０）は、ブロックの全データ値が共通データ値を有する場合、その未圧縮データブロック（例えば、１６０５）で共通データ値が支配的であることが見いだすように有益に構成される。この共通データ値は、通常、ヌル値または代わりに別の特定な共通データ値であってよい。

一般的発明データ圧縮方法が図２８に示されている。この一般的な発明的データ圧縮方法は、図２８中の２８１０～２８３０に開示された機能に加えおよび／またはそれらの改良として、前述の一般的な発明的態様およびその様々な実施形態による、データ圧縮デバイスの機能的特徴の一部または全部を有し得る。

別の一般的な発明的態様は、圧縮データブロック（例えば、１８３４、２５３４）を、１つまたは複数のデータ型の１つまたは複数のデータ値を含む解凍データブロック（例えば、１８９５、２５９５）に解凍するためのハイブリッドデータ解凍デバイス（例えば、１８３０、２５３０）である。この圧縮データブロックは、前述の一般的な発明的態様またはその様々な実施形態による、ハイブリッドデータ圧縮デバイスによって生成されたものであり得る。このハイブリッドデータ解凍デバイスは、複数のデータデコンプレッサ（例えば、１８３５、２５３５）を含み、各デコンプレッサは、それぞれのデータ解凍スキーム（例えば、１８３５－１．．．１８３５－ｎ、２５３５－１．．．２５３５－ｎ）用に構成される。このハイブリッドデータ解凍デバイスは、前記複数のデータデコンプレッサ（例えば、１８１４、２５１４）の中から選択された推定最適データデコンプレッサに、圧縮データブロックの全体を解凍させることによって、解凍データブロック（例えば、１８９５、２５９５）を生成するように構成される。

本ハイブリッドデータ解凍デバイスは、圧縮データブロック（例えば、１８３４、２５３４）に関連付けられたメタデータ（例えば、１８２４、２５２４、３０２４）を読み出し（例えば、１８３２、２５３２、３０３２）、そのメタデータに基づいて推定最適データデコンプレッサを選択するように構成すればよい。さらに、本ハイブリッドデータ解凍デバイスは、データストレージ（例えば、１８２０、２５２０）から、圧縮データブロック（例えば、１８３４、２５３４）と一緒にメタデータを読み出すように構成されてよく、このデータストレージには、データ圧縮デバイス（例えば、１８１０、２５１０）がアクセス可能である。上記に換えて、本ハイブリッドデータ解凍デバイス（例えば、３０３０）は、リンク（例えば、３０２０）を介してデータ圧縮デバイス（例えば、３０１０）から、圧縮データブロック（例えば、３０３８）と一緒にメタデータ（例えば、３０３４）を受信するように構成することもできる。

これら複数のデータデコンプレッサ（例えば、１８３５、２５３５）は、第一データ解凍スキーム用に構成された第一データデコンプレッサ、および第一データ解凍スキームとは異なる第二データ解凍スキーム用に構成された第二データデコンプレッサを含むことができる。第一および第二データ解凍スキームの各々はロスレス解凍スキームまたはロッシー解凍スキームである。

有利には、第一および第二データ解凍スキームは、
・ （例えば、ハフマン解凍、カノニカルハフマン解凍、算術復号などの）統計的（可変長）復号、
・ ディクショナリベースの解凍、
・ デルタ復号、
・ パターンベースの解凍、
・ 有意ベースの解凍、または
・ （例えば、ヌルブロック解凍などの）共通ブロック値解凍、
のうちの２つとして選択されるロスレス解凍スキームである。

データブロックは、通常、
・コンピュータシステム中のキャッシュの中にストレージするためのキャッシュライン、キャッシュセット、キャッシュブロック、またはキャッシュセクタ、
・メモリ中へのストレージまたはコンピュータシステム内での転送のためのメモリ行、メモリページ、もしくはメモリセクタ、および
・データ通信システム中の送信リンクを介して転送するためのパケット、フリット、ペイロード、またはヘッダ、
のうちの１つであってよい。

データ値のデータ型は、通常、だが限定せずに、整数、ポインタ、浮動小数点数、文字、ストリング、ブール値、コード命令、または（例えば、ビデオもしくはオーディオのフォーマットもしくは規格などの）特定のフォーマットもしくは規格によって定義されたデータ型のいずれかであってよい。

本ハイブリッドデータ解凍デバイスの一実施形態において、複数のデータデコンプレッサは、共通ブロック値解凍スキームである第一データ解凍スキーム用に構成された第一データデコンプレッサ（例えば、１７２０）、および、第一データ解凍スキームとは異なる、統計的（可変長）復号、ディクショナリベースの解凍、デルタ復号、パターンベースの解凍、および有意ベースの解凍のうちの１つである第二データ解凍スキーム用に構成された第二データデコンプレッサ（例えば、１７１０）を含む。この実施形態のハイブリッドデータ解凍デバイスは、当該圧縮データブロック（例えば、１７０５）が圧縮共通値データブロックであるかどうかをチェックし、そうである場合は、第一データデコンプレッサ（例えば、１７２０）に圧縮データブロック（例えば、１７０５）の全体を、解凍共通値データブロックとして解凍させることによって、解凍データブロック（例えば、１７９５）を生成し、そうでない場合は、第二データデコンプレッサ（例えば、１７１０）に、圧縮データブロック（例えば、１７０５）を、第二データ解凍スキームに従って解凍させることによって、解凍データブロック（例えば、１７９５）を生成するように構成される。圧縮共通値データブロックは、有利には単一ビットだけを包含すればよい。第一データデコンプレッサ（例えば、１７２０）は、解凍共通値データブロックに共通の値を充填することによって、圧縮データブロック（例えば、１７０５）の全体を解凍共通値データブロックに都合よく解凍するように構成できる。この共通データ値は、典型的には、ヌル値または代わりに別の特定な共通データ値であってよい。

一般的な発明的データ解凍方法が図２９に示されている。この一般的な発明データ解凍方法は、図２９中の２９１０～２９２０に開示された機能に加えおよび／またはその改良として、前述の一般的な発明的態様およびその様々な実施形態による、データ解凍デバイスの機能的特徴の一部または全部を有し得る。

本明細書で開示されたそれぞれのデータ圧縮デバイスは、例えば、集積回路中のデジタル回路として、または専用デバイス（例えばメモリコントローラ）として、またはプログラム可能処理デバイス（例えば中央処理装置（ＣＰＵ：ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ））もしくはデジタル信号プロセッサ（ＤＳＰ：ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｏｒ）として、またはフィールドプログラム可能ゲートアレイ（ＦＰＧＡ：ｆｉｅｌｄ－ｐｒｏｇｒａｍｍａｂｌｅ ｇａｔｅ ａｒｒａｙ）として、または他のロジック回路などとしてハードウェア中に実装することができる。本明細書に記載されたそれぞれのデータ圧縮方法の機能は、例えば、適切に構成されたそれぞれのデータ圧縮デバイスの任意のものによって、または、一般に、（例えばプロセッサデバイス／プロセッサチップ、またはメモリデバイス／メモリチップに含まれた、または関連付けられた）それぞれのデータ圧縮方法を実行するように構成されたロジック回路を含むデバイスによって、あるいはそれらに換えて、ＣＰＵまたはＤＳＰ（例えば、図１～５の処理ユニットＰ１．．．Ｐｎのいずれか）などの汎用処理デバイスによりロードされ実行されると、それぞれの方法を遂行させるコード命令を含むそれぞれのコンピュータプログラム製品によって、遂行されることができる。

本明細書で開示されたそれぞれのデータ解凍デバイスは、例えば、集積回路中のデジタル回路として、または専用のデバイス（例えばメモリコントローラ）として、またはプログラム可能処理デバイス（例えば中央処理装置（ＣＰＵ）もしくはデジタル信号プロセッサ（ＤＳＰ））として、フィールドプログラム可能ゲートアレイ（ＦＰＧＡ）として、または他のロジック回路などとしてハードウェア中に実装することができる。本明細書に記載されたそれぞれのデータ解凍方法の機能は、例えば、適切に構成されたそれぞれのデータ解凍デバイスの任意のものによって、または、一般に、（例えばプロセッサデバイス／プロセッサチップ、またはメモリデバイス／メモリチップに含まれた、または関連付けられた）それぞれのデータ解凍方法を実行するように構成されたロジック回路を含むデバイスによって、あるいはそれらに換えて、ＣＰＵまたはＤＳＰ（例えば、図１～５の処理ユニットＰ１．．．Ｐｎのいずれか）などの汎用処理デバイスによりロードされ実行されるとそれぞれの方法を遂行させるコード命令を含む、それぞれのコンピュータプログラム製品によって、遂行されることができる。

図３１は、本発明による一般的なシステム３１００を示す。本システムは、１つ以上メモリ３１１０、（例えば、データ圧縮デバイス１８１０、２５１０のいずれかなどの）データ圧縮デバイス３１２０、および（例えば、データ解凍デバイス１８３０、２５３０のいずれかなどの）データ解凍デバイス３１３０を含む。有利には、システム３１００は、（図１～５のコンピュータシステム１００～５００のいずれかなどの）コンピュータシステムであり、前記１つ以上のメモリ３１１０は、（図１～５のメモリＬ１～Ｌ３のいずれかなどの）キャッシュメモリ／メモリ（複数）、（図１～５のメモリ１３０～５３０のいずれかなどの）ランダムアクセスメモリ／メモリ（複数）、または補助的ストレージ／ストレージである。あるいは、システム３１００は、（図６～７の通信ネットワーク６００、７００などの）データ通信システムであり、前記１つ以上のメモリ３１１０は、（図６～７のトランスミッタ６１０、７１０およびレシーバ６２０、７２０などの）、データ通信システム中の送信および受信ノードに関連付けられたデータバッファであってもよい。

Claims (34)

1. 未圧縮データブロック（１８０５、２５０５）を圧縮データブロック（１８１８、２５１８）に圧縮するためのハイブリッドデータ圧縮デバイス（１８１０、２５１０）であって、前記未圧縮データブロックは複数のデータ型の複数のデータ値を含み、前記ハイブリッドデータ圧縮デバイスは、
   各コンプレッサがそれぞれのデータ圧縮スキーム（１８１４－１．．．１８１４－ｎ、２５１４－１．．．２５１４－ｎ）用に構成された、複数のデータコンプレッサ（１８１４、２５１４）と、
   前記未圧縮データブロック（１８０５、２５０５）のデータ値のデータ型を予測し、主たる基準として前記予測データ型のうちの支配的なデータ型を用いて、前記複数のデータコンプレッサの中から推定最適データコンプレッサを選択するように構成された予測器メカニズム（１８１２、２５１２）と、
   を含み、
   前記ハイブリッドデータ圧縮デバイスは、前記選択された推定最適データコンプレッサに前記未圧縮データブロックの全体を圧縮させることによって、前記圧縮データブロック（１８１８、２５１８）を生成するように構成される、
   ハイブリッドデータ圧縮デバイス。
2. 前記ハイブリッドデータ圧縮デバイスは、前記圧縮データブロック（１８１８、２５１８）に関連付けられ、前記選択された推定最適データコンプレッサの前記データ圧縮スキームを識別する役割を果たすメタデータ（１８２４、２５２４、３０２４）を生成する（１８１６、２５１６、３０１６）ように構成される、請求項１に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０、３０１０）。
3. 前記ハイブリッドデータ圧縮デバイスは、前記生成されたメタデータを、前記圧縮データブロック（１８１８、２５１８）と一緒にデータストレージ（１８２０、２５２０）の中に格納するように構成され、前記データストレージにはデータ解凍デバイス（１８３０、２５３０）がアクセス可能である、又は
   前記ハイブリッドデータ圧縮デバイスは、前記生成されたメタデータ（３０２４）を前記圧縮データブロック（３０１８）と一緒に、リンク（３０２０）を介してデータ解凍デバイス（３０３０）に送信するように構成される、
   請求項２に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
4. 前記複数のデータコンプレッサ（１８１４、２５１４）は、
   ・ 第一データ圧縮スキーム用に構成された第一データコンプレッサと、
   ・ 前記第一圧縮スキームとは異なる第二データ圧縮スキーム用に構成された第二データコンプレッサと、
   を含み、
   前記第一および第二データ圧縮スキームは各々、ロスレス圧縮スキームまたはロッシー圧縮スキームであり、
   前記第一データ圧縮スキームは、第一データ型のデータ値の間のデータローカリティを利用するように設計され、前記データローカリティは、時間的、空間的、またはこれらの組み合せであり、
   前記第二データ圧縮スキームは、第二データ型のデータ値の間のデータローカリティを利用するように設計され、前記データローカリティは、時間的、空間的、またはこれらの組み合せである、
   請求項１～３のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
5. 前記未圧縮データブロックは、
   コンピュータシステム中のキャッシュの中にストレージするためのキャッシュライン、キャッシュセット、キャッシュブロック、またはキャッシュセクタ、
   メモリ中へのストレージまたはコンピュータシステム内での転送のためのメモリ行、メモリページ、もしくはメモリセクタ、および
   データ通信システム中の送信リンクを介して転送するためのパケット、フリット、ペイロード、またはヘッダ、
   のうちの１つであり、
   前記データ値の前記データ型は、
   整数、ポインタ、浮動小数点数、文字、ストリング、ブール値、コード命令、または特定のフォーマットもしくは規格によって定義されたデータ型、
   のいずれかである、
   請求項１～４のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
6. 前記予測器メカニズム（１８１２、２５１２）は、
   前記未圧縮データブロック（１８０５、２５０５）をセグメントに分割し、
   全セグメントに対し、前記セグメントを複数の候補データ型のうちの一予測データ型として分類するため、各セグメントの検査ビット部分を検査し、
   前記未圧縮データブロックの前記支配的なデータ型を判定するために、全セグメントの前記予測データ型の出現頻度を比較する、
   ように構成される、請求項１～５のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
7. 前記候補データ型は、整数、ポインタ、浮動小数点数、文字、ストリング、ブール値、共通データ値ブロック、データコード命令、または特定のフォーマットもしくは規格によって定義されたデータ型、のうちの２つ以上である、請求項６に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
8. 前記検査ビット部分は、相異なる候補データ型に対して異なっている、請求項６または７に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
9. 前記候補データ型の１つは整数であり、
   前記未圧縮データブロックのサイズはｍバイトであり、
   前記セグメントのサイズはｎバイトであり、
   ｍ／ｎは２の倍数であり、
   前記検査ビット部分は前記セグメントの最上位のｐバイトであり、
   ｎ／ｐが２であり、
   前記予測器メカニズム（１８１２、２５１２）は、前記検査ビット部分がいくつかの事前定義されたｐバイト値のいずれかに等しい場合、前記セグメントを整数として分類するように構成される、
   請求項６～８のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
10. 前記候補データ型の１つはポインタであり、
    前記未圧縮データブロックのサイズはｍバイトであり、
    前記セグメントのサイズはｎバイトであり、
    ｍ／ｎは２の倍数であり、
    前記検査ビット部分は前記セグメントの最上位のｐバイトであり、
    ｎ／ｐが２であり、
    前記予測器メカニズム（１８１２、２５１２）は、前記検査ビット部分の最上位２バイトが事前定義されたｐ／２バイト値に等しく、だが最下位の２バイトは不等の場合、前記セグメントをポインタとして分類するように構成される、
    請求項６～９のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
11. 前記候補データ型の１つは浮動小数点数であり、
    前記未圧縮データブロックのサイズはｍバイトであり、
    前記セグメントのサイズはｎバイトであり、
    ｍ／ｎは２の倍数であり、
    前記検査ビット部分は前記セグメントの最上位ビットの次の最上位のｑビットであり、
    前記予測器メカニズム（１８１２、２５１２）は、前記セグメントの前記検査ビット部分を、前記未圧縮データブロック中の、同じまたはクラスタ化された浮動小数点指数を示す隣接のセグメントの検査ビット部分と突き合わせることによって、前記セグメントを浮動小数点数として分類するように構成される、
    請求項６～１０のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
12. 前記候補データ型の１つは共通データ値であり、
    前記未圧縮データブロックのサイズはｍバイトであり、
    前記セグメントのサイズはｎバイトであり、
    ｍ／ｎは２の倍数であり、
    前記検査ビット部分はセグメント全体であり、
    前記予測器メカニズム（１８１２、２５１２）は、前記セグメントを、その全データ値が同じ共通データ値を有するとき、共通データ値として分類するように構成される、
    請求項６～１１のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
13. 前記ハイブリッドデータ圧縮デバイスは、前記未圧縮データブロック（１８０５、２５０５）の全セグメントが共通データ値として分類されたとき、前記推定最適データコンプレッサとして、データ圧縮スキームとして共通データ値を有するデータコンプレッサ（１８１４、２５１４）を選択するように構成される、請求項６～１２のいずれかに記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
14. 前記予測器メカニズム（１８１２、２５１２）は、前記未圧縮データブロックの前記支配的なデータ型を判定する際に、前記セグメントの２つの異なる予測データ型が同じ出現頻度を有するとき、一方を他方よりも優先するように構成される、請求項６～１３のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
15. 前記予測器メカニズム（１８１２、２５１２）は、前記セグメントのどの予測データ型の出現もないとき、前記推定最適データコンプレッサとしてデフォルトデータコンプレッサを選択する、又は推定最適データコンプレッサの代わりに無圧縮を選択し、前記未圧縮データブロックの圧縮を取り止めるように構成される、請求項６～１４のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
16. 複数の圧縮サイクルの過程で、前記それぞれの支配的なデータ型について、データコンプレッサの理想的な選択と対比して前記それぞれの選択された推定最適データコンプレッサをモニタし、
    特定の支配的なデータ型の圧縮性に関し、別のデータコンプレッサがさらに効率的であった可能性のあることを検出し、
    今後の圧縮サイクルについて、前記特定の支配的なデータ型に対し、前記最適データコンプレッサを前記別のデータコンプレッサに変更する、
    ようにさらに構成され、
    前記それぞれの支配的なデータ型のためのデータコンプレッサの前記理想的な選択がオラクルセレクタによって提供され、前記オラクルセレクタは、複数の全てのデータコンプレッサ（１８１４、２５１４）の前記データ圧縮スキームを使って前記未圧縮のデータブロックを圧縮し、それぞれの理想的選択として、それぞれの未圧縮データブロックの最善の圧縮性が得られる前記データ圧縮スキームを有する前記コンプレッサを選定する、
    請求項１～１５のいずれか一項に記載のハイブリッドデータ圧縮デバイス（１８１０、２５１０）。
17. 前記複数のデータコンプレッサは、
    共通データ値スキームである第一データ圧縮スキーム用に構成された第一データコンプレッサ（１６３０）と、
    前記第一データ圧縮スキームとは異なる、統計的符号化、ディクショナリベースの圧縮、デルタ符号化、パターンベースの圧縮、および有意ベースの圧縮のうちの１つである第二データ圧縮スキーム用に構成された第二データコンプレッサ（１６２０）と、
    を含み、
    前記ハイブリッドデータ圧縮デバイスは、前記予測器メカニズム（１６３０）によって前記未圧縮データブロック（１６０５）で共通データ値が支配的であることが判明した場合、前記第一データコンプレッサ（１６３０）に、前記未圧縮データブロック（１６０５）の全体を圧縮共通データ値に圧縮させることによって、前記圧縮データブロック（１６１８）を生成するように構成され、それ以外の場合は、前記第二データコンプレッサ（１６２０）に、前記第二データ圧縮スキームに従い前記未圧縮データブロック（１６０５）の全体を圧縮させることによって、前記圧縮データブロック（１６１８）を生成するように構成される、
    請求項１～１６のいずれか一項に記載のハイブリッドデータ圧縮デバイス。
18. 前記圧縮共通データ値は単一ビットを包含する、請求項１７に記載のハイブリッドデータ圧縮デバイス。
19. 前記予測器メカニズム（１６３０）は前記第一データコンプレッサ（１６３０）に組み込まれる、請求項１７または１８に記載のハイブリッドデータ圧縮デバイス。
20. 前記予測器メカニズム（１６３０）は、前記未圧縮データブロック（１６０５）の全データ値が前記共通データ値を有する場合、前記未圧縮データブロックで前記共通データ値が支配的であることを見いだすように構成される、請求項１７～１９のいずれか一項に記載のハイブリッドデータ圧縮デバイス。
21. 未圧縮データブロック（１８０５、２５０５）を圧縮データブロック（１８１８、２５１８）に圧縮するためのハイブリッドデータ圧縮方法であって、前記未圧縮データブロックは複数のデータ型の複数のデータ値を含み、前記ハイブリッドデータ圧縮方法は、
    前記未圧縮データブロック（１８０５、２５０５）のデータ値のデータ型を予測するステップ（２８１０）と、
    主たる基準として前記予測データ型中の支配的なデータ型を用いて、複数のデータ圧縮スキーム（１８１４－１．．．１８１４－ｎ、２５１４－１．．．２５１４－ｎ）の中から推定最適データ圧縮スキームを選択するステップ（２８２０）と、
    前記圧縮データブロック（１８１８、２５１８）を生成するために、前記選択された推定最適データ圧縮スキームによって前記未圧縮データブロックの全体を圧縮するステップ（２８３０）と、
    を含む、ハイブリッドデータ圧縮方法。
22. 圧縮データブロック（１８３４、２５３４）を、複数のデータ型の複数のデータ値を含む解凍データブロック（１８９５、２５９５）に解凍するためのハイブリッドデータ解凍デバイス（１８３０、２５３０）であって、前記ハイブリッドデータ解凍デバイスは、
    各デコンプレッサがそれぞれのデータ解凍スキーム（１８３５－１．．．１８３５－ｎ、２５３５－１．．．２５３５－ｎ）用に構成された、複数のデータデコンプレッサ（１８３５、２５３５）、
    を含み、
    前記ハイブリッドデータ解凍デバイスは、前記複数のデータデコンプレッサ（１８３５、２５３５）の中から選択された推定最適データデコンプレッサに、前記圧縮データブロックの全体を解凍させることによって、前記解凍データブロック（１８９５、２５９５）を生成するように構成される、
    ハイブリッドデータ解凍デバイス。
23. 前記ハイブリッドデータ解凍デバイスは、前記圧縮データブロック（１８３４、２５３４）に関連付けられたメタデータ（１８２４、２５２４、３０２４）を読み出して（１８３２、２５３２、３０３２）、前記メタデータに基づいて前記推定最適データデコンプレッサを選択するように構成される、請求項２２に記載のハイブリッドデータ解凍デバイス（１８３０、２５３０）。
24. 前記ハイブリッドデータ解凍デバイスは、前記メタデータを前記圧縮データブロック（１８３４、２５３４）と一緒にデータストレージ（１８２０、２５２０）から読み出すように構成され、前記データストレージにはデータ圧縮デバイス（１８１０、２５１０）がアクセス可能である、又は前記ハイブリッドデータ解凍デバイスは、前記メタデータ（３０３４）を前記圧縮データブロック（３０３８）と一緒に、リンク（３０２０）を介してデータ圧縮デバイス（３０１０）から受信するように構成される、請求項２３に記載のハイブリッドデータ解凍デバイス（１８３０、２５３０）。
25. 前記複数のデータデコンプレッサ（１８３５、２５３５）は、
    ・ 第一データ解凍スキーム用に構成された第一データデコンプレッサと、
    ・ 前記第一データ解凍スキームとは異なる第二データ解凍スキーム用に構成された第二データデコンプレッサと、
    を含み、
    前記第一および第二データ解凍スキームの各々はロスレス解凍スキームまたはロッシー解凍スキームである、
    請求項２２～２４のいずれか一項に記載のハイブリッドデータ解凍デバイス（１８３０、２５３０）。
26. 前記解凍データブロックは、
    コンピュータシステム中のキャッシュの中にストレージするためのキャッシュライン、キャッシュセット、キャッシュブロック、またはキャッシュセクタ、
    メモリ中へのストレージまたはコンピュータシステム内での転送のためのメモリ行、メモリページ、もしくはメモリセクタ、および
    データ通信システム中の送信リンクを介して転送するためのパケット、フリット、ペイロード、またはヘッダ、
    のうちの１つであり、
    前記データ値の前記データ型は、
    整数、ポインタ、浮動小数点数、文字、ストリング、ブール値、コード命令、または特定のフォーマットもしくは規格によって定義されたデータ型、
    のいずれかである、
    請求項２２～２５のいずれか一項に記載のハイブリッドデータ解凍デバイス（１８３０、２５３０）。
27. 前記複数のデータデコンプレッサは、
    共通ブロック値解凍スキームである第一データ解凍スキーム用に構成された第一データデコンプレッサ（１７２０）と、
    前記第一データ解凍スキームとは異なる、統計的復号、ディクショナリベースの解凍、デルタ復号、パターンベースの解凍、および有意ベースの解凍のうちの１つである第二データ解凍スキーム用に構成された第二データデコンプレッサ（１７１０）と、
    を含み、
    前記ハイブリッドデータ解凍デバイスは、前記圧縮データブロック（１７０５）が圧縮共通データ値であるかどうかをチェックし、そうである場合は、前記第一データデコンプレッサ（１７２０）に、前記圧縮データブロック（１７０５）の全体を、解凍共通データ値に解凍させることによって、前記解凍データブロック（１７９５）を生成し、そうでない場合は、前記第二データデコンプレッサ（１７１０）に、前記圧縮データブロック（１７０５）を、前記第二データ解凍スキームに従って解凍させることによって、前記解凍データブロック（１７９５）を生成するように構成される、
    請求項２３～２６のいずれか一項に記載のハイブリッドデータ解凍デバイス。
28. 前記圧縮共通データ値は、単一ビットを包含する、請求項２７に記載のハイブリッドデータ解凍デバイス。
29. 前記第一データデコンプレッサ（１７２０）は、前記解凍共通データ値に共通の値を充填することによって、前記圧縮データブロック（１７０５）の全体を前記解凍共通データ値に解凍するように構成される、請求項２７または２８に記載のハイブリッドデータ解凍デバイス。
30. 圧縮データブロック（１８３４、２５３４）を、複数のデータ型の複数のデータ値を含む解凍データブロック（１８９５、２５９５）に解凍するためのハイブリッドデータ解凍方法であって、前記ハイブリッドデータ解凍方法は、
    前記複数のデータ解凍スキーム（１８３５－１．．．１８３５－ｎ、２５３５－１．．．２５３５－ｎ）の中から推定最適データ解凍スキームを選択するステップ（２９１０）と、
    前記解凍データブロック（１８９５、２５９５）を生成するために、前記選択された推定最適データ圧縮スキームによって、前記圧縮データブロック（１８３４、２５３４）の全体を解凍するステップ（２９２０）と、
    を含む、ハイブリッドデータ解凍方法。
31. 処理デバイスによってロードされ実行されると、請求項２１に記載の方法を遂行させるコード命令を含む、コンピュータプログラム。
32. 請求項２１に記載の方法を遂行するように構成されたロジック回路を含むデバイス。
33. 処理デバイスによってロードされ実行されると請求項３０に記載の方法を遂行させるコード命令を含む、コンピュータプログラム。
34. 請求項３０に記載の方法を遂行するように構成されたロジック回路を含むデバイス。

Images