(57)【要約】【課題】  サイズの異なる複数の並列連想メモリを有利に使用して、圧縮中に高速マッチングを行う新規な圧縮及び伸張（解凍）アーキテクチャを開示する。【解決手段】  圧縮アーキテクチャは、それぞれが異なるサイズを有し、かつ入力ストリーム１００中の異なるサイズの部分に対し並行して動作するように配置された２つまたは３つ以上の連想メモリ１１４、１１６、１１８と、連想メモリ１１４、１１６、１１８に１つまたは２つ以上の一致エントリがある場合に、入力ストリーム１００中の異なるサイズの部分の１つが、圧縮出力ストリーム１５０において、選択された連想メモリとその一致エントリとを特定する圧縮表現に置き換えられるように、一致した連想メモリの１つを選択する選択ロジック１２０と、を有する。【選択図】      図１
2006092725.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが異なるサイズを有し、かつ入力ストリーム中の異なるサイズの部分に対し並行して動作するように配置された２つまたは３つ以上の連想メモリと、
前記連想メモリに１つまたは２つ以上の一致エントリがある場合に、前記入力ストリーム中の前記異なるサイズの部分の１つが、圧縮出力ストリームにおいて、選択された連想メモリとその一致エントリとを特定する圧縮表現に置き換えられるように、一致した連想メモリの１つを選択する選択ロジックと、
を有する圧縮システム。
【請求項２】
前記選択ロジックは、どのメモリが最長の一致エントリを有しているかに基づいて、前記一致した連想メモリの１つを選択する、請求項１に記載の圧縮システム。
【請求項３】
前記連想メモリは、完全一致だけでなく部分一致にも基づいて動作し、前記選択ロジックは、どのメモリが最良の部分一致エントリを有しているかに基づいて、前記一致した連想メモリの１つを選択する、請求項１に記載の圧縮システム。
【請求項４】
前記圧縮表現は、前記入力ストリームの部分のどの部位が前記エントリに一致したかを特定するマスクと、前記一致エントリに一致しなかった入力ストリームの部分についての情報の表現とを含む、請求項３に記載の圧縮システム。
【請求項５】
前記連想メモリは、一致がない場合に、前記連想メモリのエントリとして、前記入力ストリームの異なるサイズの部分を追加する、請求項１に記載の圧縮システム。
【請求項６】
前記連想メモリはシフト可能であり、前記連想メモリの先頭に一致エントリをシフトする、請求項１に記載の圧縮システム。
【請求項７】
それぞれサイズの異なる３つの連想メモリを有する、請求項１に記載の圧縮システム。
【請求項８】
前記３つの連想メモリは、それぞれ、４バイト幅、６バイト幅及び８バイト幅のエントリを処理する、請求項６に記載の圧縮システム。
【請求項９】
それぞれ異なるサイズを有する２つまたは３つ以上のメモリと、
前記２つまたは３つ以上のメモリの１つからエントリを検索することにより、圧縮ストリームの部分を復元するデコーダと、
を有し、前記エントリ及び前記メモリは、前記部分の圧縮表現において、圧縮中に非圧縮ストリームの部分と一致するような部分として特定される、解凍システム。
【請求項１０】
前記２つまたは３つ以上のメモリは、解凍中、非圧縮ストリームの一致しない部分をエントリとして追加する、請求項９に記載の解凍システム。
【請求項１１】
前記デコーダは完全一致のみならず部分一致の圧縮表現も処理する、請求項９に記載の解凍システム。
【請求項１２】
前記圧縮表現は、前記非圧縮ストリームの部分のどの部位が前記エントリに一致したかを特定するマスクと、前記エントリに一致しなかった非圧縮ストリームの部分についての情報の表現とを含む、請求項１１に記載の解凍システム。
【請求項１３】
入力ストリームの異なるサイズの部分を受け取ることと、
前記入力ストリームの異なるサイズの部分について、各連想メモリが前記入力ストリームの異なるサイズの部分に対応した異なるサイズを持つ２つまたは３つ以上の連想メモリを並行して検索することと、
前記連想メモリのいずれかに１つまたは２つ以上の一致エントリがある場合に、一致した連想メモリの１つを選択し、一致エントリに一致した入力ストリームの部分を圧縮出力ストリーム中の圧縮表現に置き換えることと、
を有し、前記圧縮表現は一致した連想メモリとその一致エントリとを特定するものである、圧縮方法。
【請求項１４】
最長の一致エントリを有する一致した連想メモリが選択される、請求項１３に記載の方法。
【請求項１５】
前記連想メモリは、完全一致のみならず部分一致も実行し、最良の部分一致エントリを有する一致した連想メモリが選択される、請求項１３に記載の方法。
【請求項１６】
前記圧縮表現は、前記入力ストリームの部分のどの部位が前記一致エントリに一致したかを特定するマスクと、前記一致エントリに一致しなかった入力ストリームの部分についての情報の表現とを含む、請求項１５に記載の方法。
【請求項１７】
前記連想メモリに一致エントリがない場合に、前記連想メモリのエントリとして入力ストリームの異なるサイズの部分を加える段階をさらに有する、請求項１３に記載の方法。
【請求項１８】
前記連想メモリはシフト可能であり、前記連想メモリの先頭に一致エントリをシフトする、請求項１３に記載の方法。
【請求項１９】
異なるサイズを有する圧縮及び非圧縮部分のシーケンスを有する圧縮ストリームを受け取ることと、
前記圧縮ストリームの異なるサイズの部分に対応して異なるサイズを有する２つまたは３つ以上のメモリの１つに次の非圧縮部分を格納することにより、シーケンス中の前記次の非圧縮部分をデコードすることと、
エントリとメモリが圧縮部分での圧縮表現で特定され、前記２つまたは３つ以上のメモリの１つから前記エントリを検索することにより、前記シーケンス中の次の圧縮部分を非圧縮部分にデコードすることと、
を有し、各デコードされた非圧縮部分が非圧縮出力ストリームを形成するシーケンスに追加される、伸張方法。
【請求項２０】
前記圧縮表現はまた、前記比圧縮部分のどの部位が前記エントリと一致したかを特定するマスクと、前記エントリに一致しなかった前記非圧縮部分についての情報の表現とを含む、請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は圧縮及び解凍アーキテクチャに関する。
【０００２】
本出願は、２００４年９月２４日に提出された米国仮出願第６０／５２２，３９０号、「圧縮システムと方法」の利益を主張し、その出願の内容を参照として本明細書に組み込んでいる。
【背景技術】
【０００３】
圧縮技術はよく知られている技術である。データを圧縮するのに好都合な手法の１つは、当該技術分野において「辞書(dictionary)」符号化と呼ばれているものであって、繰り返して発生するデータのグループを辞書中のエントリへのインデックスで置き換える方法である。辞書符号化の特に有用な例は、当該技術分野において一般にLempel-Ziv (LZ)符号化として知られている適応スキームである。例えば、T. A. Welch, "A Technique for High-Performance Data Compression," IEEE Computer, pp. 8-19 (1986)（非特許文献１）を参照されたい。データ圧縮技術は、ごく最近では、メインメモリに格納されているデータの圧縮を含めて、広範な用途で利用されてきている。こうした用途では、良好なハードウェアの実装と、小さなデータブロックにおいても十分満足できる圧縮性能とが要求される。例えば、「Ｘ−Ｍａｔｃｈ」は、連想メモリ（ＣＡＭ；content addressable memory）により実行される適応辞書符号化スキームを使用してメインメモリを圧縮する、新しいデータ圧縮アーキテクチャである。M. Kjelso, M. Gooch, S. Jones, "Design and Performance of a Main Memory Hardware Data Compressor," IEEE Proceedings of EUROMICRO-22, pp. 423-30 (Sept.1996)（非特許文献２）を参照されたい。
【非特許文献１】T. A. Welch, "A Technique for High-Performance Data Compression," IEEE Computer, pp. 8-19 (1986)
【非特許文献２】M. Kjelso, M. Gooch, S. Jones, "Design and Performance of a Main Memory Hardware Data Compressor," IEEE Proceedings of EUROMICRO-22, pp. 423-30 (Sept. 1996)
【発明の開示】
【発明が解決しようとする課題】
【０００４】
サイズの異なる複数の並列連想メモリを有利に使用し、圧縮中に高速マッチングを行う新規な圧縮及び伸張（解凍）アーキテクチャをここに開示する。
【課題を解決するための手段】
【０００５】
本発明の一実施態様によれば、入力ストリームの複数の部分が複数の連想メモリに並列に供給され、各連想メモリは、入力ストリームのサイズの異なる部分のマッチングを実行する。連想メモリはシフト可能な連想メモリであるのが好ましい。連想メモリのいずれか１つのエントリに対する一致(match)があるとき、一致エントリの１つ（最長の一致または最良の部分一致が好ましい）を、選択ロジックを使用して選択し、入力ストリームの一致した部分を特定の連想メモリのエントリに対するインデックスを含む圧縮表現で置き換える。連想メモリは、部分一致も示すことが好ましい。選択ロジックは、部分一致がある場合、一致していないバイトの表現を含んだまま、一致しているバイトを部分一致したエントリに対するインデックスで置き換えることができる。一致エントリを有する連想メモリは、また、move-to-front（先頭への移動）法を容易に行うために、好ましくは、一致したエントリ及び部分一致したエントリを連想メモリの最上位にシフトさせる。
【０００６】
本発明の他の実施態様によれば、圧縮ストリームは、圧縮ストリーム中の一致及び部分一致の圧縮表現をデコードすることにより、伸張（解凍）できる。伸張中はマッチングが不要なので、従来のメモリを使用してエントリを格納することができる。
【０００７】
本発明は、コードとデータの両方の高性能な圧縮及び伸張を提供するものであり、特に組込みシステムにおける効率的なハードウェア実装に好適である。本発明のこれら及びその他の利点は、以下の詳細な説明及び添付の図面を参照することにより、当業者に明白になるであろう。
【発明を実施するための最良の形態】
【０００８】
図１は、本発明の一実施形態による圧縮アーキテクチャのブロック図である。圧縮アーキテクチャは、入力ストリーム１００を例えばバッファから受け取る。入力ストリーム１００は、コードまたはデータのいずれかであるのが好都合である。入力ストリーム１００の部分は、ここでは例示目的のみのため、バイトシーケンスの細かさ(granularity)で参照される。圧縮アーキテクチャは、複数の連想メモリ（ＣＡＭ；content addressable memory）１１４、１１６、１１８を有している。これらの連想メモリは、いずれも、バイトシーケンスを保存し、その連想メモリに保存されたバイトシーケンスにインデックスを付与できる。図１には３つの連想メモリが示されているが、説明されているアーキテクチャの文脈においては、２つまたは３つ以上の数を含むいかなる数の連想メモリも利用することもできる。本発明者らは、２つよりも３つの連想メモリがより良好に機能するが、一方、４つまたはそれ以上のメモリによる追加のメリットはわずかでしかないことを見出した。
【０００９】
連想メモリ１１４、１１６、１１８は並行して動作し、またその各々は固定された異なるサイズであるのが好都合である。図１に示すように、連想メモリ（ＣＭＡ＿Ｌ）１１４は４バイト幅のバイトシーケンスを処理し、一方、連想メモリ（ＣＭＡ＿Ｍ）１１６は６バイト幅のバイトシーケンスを処理し、連想メモリ（ＣＭＡ＿Ｈ）１１８は８バイト幅のバイトシーケンスを処理する。連想メモリ１１４、１１６、１１８は、以下にさらに説明するように、一致する（マッチする）エントリの増加をより容易にし、かつ共通する一致の局所性を活用するために、シフト可能であることが好ましい。
【００１０】
入力ストリーム１００が圧縮アーキテクチャで処理されると、異なる長さのバイトシーケンスが連想メモリ１１４、１１６、１１８に保存される。これらの最初の一致しないバイトシーケンスは、選択ロジック１２０に転送され、選択ロジックはそれらのバイトシーケンスを処理して出力ストリーム１５０の先頭を生成する。これら最初のバイトシーケンスは、非圧縮フォーマットで出力ストリーム１５０に格納され、一致または部分一致が生じるまで連想メモリ１１４、１１６、１１８に書き込むのに使用される。入力ストリーム１００の次の部分が、連想メモリ１１４、１１６、１１８のいずれか１つにあるエントリと一致するかまたは部分一致した場合、選択ロジック１２０に出力されるのは、一致したバイトシーケンスに対するインデックスと、一致しなかったバイトの表現である。選択ロジック１２０は、連想メモリ１１４、１１６、１１８の１つからの出力を選択して、一致したバイトシーケンスの圧縮表現を生成し、生成された圧縮表現は次に出力ストリーム１５０に追加される。選択ロジック１２０は、最大サイズを有するまたは最良の部分一致を有する連想メモリからの出力を選択するのが好ましい。したがって、例えば、最初に最も幅の広い連想メモリを使用して可能な最長のバイトシーケンスを一致させることを試み、十分な一致（完全一致または部分一致）がない場合には、２番目に幅の広い連想メモリでの一致を確認するなどにより、選択ロジック１２０は「どん欲(greedy)な」方法で処理を実行することができる。上述のごとく、各連想メモリ１１４、１１６、１１８における一致処理(matching process)は、好都合にも並行して進めることができる。圧縮アーキテクチャは、入力ストリーム１００全体が処理されて最終的な圧縮ストリーム１５０が出力されるまで、バイトシーケンスを一致させる処理を続行する。
【００１１】
図２は、図１の出力ストリーム１５０に対応する圧縮ストリーム２５０を受け取り、元のストリーム２００を復元可能な、対応する伸張アーキテクチャのブロック図である。伸張（解凍）は、上述の圧縮手順によく似たやり方で進められる。圧縮ストリーム２５０が、非圧縮バイトシーケンスを格納する一連のメモリ（ＲＡＭ＿Ｌ、ＲＡＭ＿Ｍ、ＲＡＭ＿Ｈ）２２４、２２６、２２８に供給される。入力データのマッチングは全く行う必要がないため、これらのメモリは連想メモリである必要はなく、例えば、従来のランダムアクセスメモリ（ＲＡＭ）であってもよい。各メモリ２２４、２２６、２２８は、圧縮アーキテクチャの連想メモリのサイズに対応する、相互に異なるサイズのメモリである。メモリ２２４、２２６、２２８は当初は空であるが、伸張が進行するにつれ、圧縮時に書き込まれたのと同一のやり方で書き込まれる。圧縮ストリーム２５０において圧縮バイトシーケンスの表現に出会うと、一致するバイトシーケンスのインデックスを抽出し、そのインデックスを用いてメモリ２２４、２２６、２２８の１つから適切なバイトシーケンスを読み出すデコーダ２１０が用いられる。バイトシーケンスが部分一致のみである場合、一致しなかったバイトの表現も抽出されて、実際の非圧縮バイトシーケンスが再構築される。各非圧縮バイトシーケンスは、元の非圧縮ストリーム２００を復元するように、パッカー２３０で配列される。
【００１２】
圧縮ストリーム１５０／２５０の好都合なフォーマット例が図３に示されている。図３の（Ａ）は、元の入力ストリームの部分を、連想メモリの部分的な一致または完全な一致に基づいて圧縮可能な場合のフォーマットを示し、図３の（Ｂ）は、入力ストリームのその部分に一致が見つからなかった場合のフォーマットを示している。図３の（Ａ）では、圧縮された事例であることが、「１」に設定された最上位ビット（ＭＳＢ）などの固定長フィールド３１０により示されている。次に、バイトシーケンス内のどのバイトが一致したかを表わす固定長マスク３２０が格納されている。一致しなかったバイトは、出力の最後においてフィールド３４０に格納され、フィールド３３０は、入力バイトシーケンスと完全一致または部分一致した連想メモリ中のインデックスを格納している。連想メモリが複数あるので、その複数の連想メモリのどれが一致したバイトシーケンスを保存しているかを特定する情報も含ませる必要がある。インデックスは、複数の連想メモリのどれを使用すべきかを示すのにも用いられることが好ましい。例えば、３つの連想メモリが使用される場合、第１の連想メモリにインデックス０、３、６、９、…を割り当て、第２の連想メモリに１、４、７、１０、…を割り当て、第３の連想メモリに２、５、８、１１、…を割り当てるなどとすることができる。図３の（Ｂ）において、圧縮ストリームの非圧縮部分は、フィールド３１５で「０」に設定されたＭＳＢで示され、その後に、固定長のバイトシーケンス３５０が続いている。固定長のバイトシーケンスを、最小の連想メモリの幅に等しい設定長に設定することにより、非圧縮バイトシーケンスのサイズを指定する特別な符号化が不要になる。
【００１３】
図４の（Ａ）〜（Ｄ）は、図１に示した３つの連想メモリを有するアーキテクチャで処理可能な、一致（マッチング）の異なる種類をさらに示している。４つの事例は、最も幅の広い連想メモリでの一致、中間サイズの連想メモリでの一致、最も幅の狭い連想メモリでの一致、及び最後にまったく一致がない場合にそれぞれ対応している。すべての事例において、例示のために、同一入力ストリーム、すなわち「３Ｅ  ３Ｅ  ４２  ４Ｄ  ３Ｅ  ４Ｄ  Ｃ７  Ｆ５  Ｅ８  １２  ３Ｅ  ４Ｄ」が利用されている。
【００１４】
図４の（Ａ）では、８バイト幅の連想メモリで合計５バイトの一致がある。すべてのバイトが一致しているわけではないので、これは部分一致であるが、８バイト連想メモリの使用を正当とするのには十分に大きい（すなわち、８バイト中５バイトの）一致である。出力は、図３に示したフォーマットに従う。図４の（Ａ）に示した出力は、それに引き続くデータが圧縮されていることを示す「１」、連想メモリ内のインデックス位置を示す「９」であり、その後に、マスクフィールドと、最後に、８バイト連想メモリで一致しなかった後続バイトが続く。図４の（Ｂ）、（Ｃ）では、それぞれ６バイト連想メモリ及び４バイト連想メモリにおいて、対応する出力との一致がある。図４の（Ｄ）は、一致がない場合の出力を示している。図４の（Ａ）〜（Ｄ）は、シフト可能な連想メモリの機能を用いた有利な動作も示している。各サイクルにおいて、シフト可能な連想メモリは、以下のように変更される。一致したまたは部分一致したデータを含むシフト可能な連想メモリは、一致したまたは部分一致したエントリがその連想メモリの最上位(top)に移動するように、シフトされる。一方、一致していない連想メモリには入力データが書き込まれる。シフト可能な連想メモリすべてに書き込むことにより、高速マッチングが好都合にも確実に行われる。一致したデータを最上位にシフトすることによっても、より少ないビットしか使用しないで済む、平均してより小さい連想メモリのインデックスが保存されることを確実にする。これは、「move-to-front（先頭への移動）」法と呼ばれている。
【００１５】
図５は、本発明の一実施形態により上述のように実行される圧縮処理をさらに示す擬似コード(pseudo-code)である。図６は、本発明の一実施形態により上述のように実行される、対応する伸張処理をさらに示す擬似コードである。
【００１６】
本発明の代表的な図面及び特定の実施形態を説明し例示してきたが、本発明の範囲は、説明した特定の実施形態に限定されないことを理解されたい。したがって、実施形態は限定的ではなく例示的なものであると見なすべきであり、当業者であれば、以下の請求の範囲に記載される本発明の範囲、ならびにその構造的及び機能的同等物から逸脱することなく、これら実施形態の変形例を作成できることを理解されるべきであろう。多数の変形例の１つに過ぎないが、シフト可能な連想メモリ以外の連想メモリを、本発明に照らして容易に利用できることが理解されるべきであろう。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施形態による圧縮アーキテクチャのブロック図である。
【図２】本発明の一実施形態による伸張（解凍）アーキテクチャのブロック図である。
【図３】圧縮出力の例示的なフォーマットである。
【図４】図１に示したアーキテクチャで処理可能な一致の異なる種類を示している。
【図５】本発明の一実施形態により実行される圧縮処理を示す擬似コードである。
【図６】本発明の一実施形態により実行される伸張処理を示す擬似コードである。
【符号の説明】
【００１８】
１００    入力ストリーム
１１４、１１６、１１８    連想メモリ
１２０    選択ロジック
１５０    出力ストリーム
２００    非圧縮ストリーム
２５０    圧縮ストリーム
【図１】
2006092725.tif 000003
【図２】
2006092725.tif 000004
【図３】
2006092725.tif 000005
【図４】
2006092725.tif 000006
【図５】
2006092725.tif 000007
【図６】
2006092725.tif 000008