(57)【要約】  プロセッサベースシステムにおける小データブロックのための効率的なロスレス圧縮を実現することが提供される。一態様では、方法が、複数の入力ワードを受信するステップを備える。複数のマスクの各マスクが、対応する複数のパターンを生成するために各非割当て入力ワードに適用される。マスクごとに、最頻出パターンが複数のパターンの中に存在する場合に、最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分が、マスクに関連するプレフィックスに関連して記憶される。プレフィックスはまた、最頻出パターンに対応する各非割当て入力ワードに割り当てられる。複数の入力ワードに割り当てられたプレフィックス、割当てプレフィックスに関連する最頻出パターン、および複数の入力ワードのうちの1つまたは複数の入力ワードに対応する非圧縮データ部分を備える圧縮出力ブロックが生成される。
2019530076.tif 000002
【特許請求の範囲】
【請求項１】
圧縮メモリコントローラ(CMC)であって、
複数のマスクおよび関連する複数のプレフィックスを提供するマスクテーブルと、
複数の入力ワードを受信することと、
前記マスクテーブルの前記複数のマスクのマスクごとに、
対応する複数のパターンを生成するために前記複数の入力ワードの各非割当て入力ワードに前記マスクを適用することと、
最頻出パターンが前記複数のパターンの中に存在するかどうかを判断することと、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、
前記マスクに関連する前記複数のプレフィックスのうちのプレフィックスに関連して出力生成回路に、前記最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を出力することと、
前記最頻出パターンに対応する各非割当て入力ワードに、前記マスクに関連する前記プレフィックスを割り当てることと、
前記複数の入力ワードに割り当てられた複数の割当てプレフィックスを前記出力生成回路に出力することと
を行うように構成されたパターン識別回路と、
前記複数の入力ワードに割り当てられた前記複数の割当てプレフィックスと、
前記複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンと、
前記複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分と
を備える圧縮出力ブロックを生成するように構成された前記出力生成回路と
を備えるCMC。
【請求項２】
前記パターン識別回路は、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するかどうかを判断することと、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するとの判断に応答して、前記0の値を有する前記複数の入力ワードのうちの前記1つまたは複数の入力ワードの各入力ワードに、0値を示す前記複数のプレフィックスのうちのプレフィックスを割り当てることと
を行うようにさらに構成される、請求項1に記載のCMC。
【請求項３】
前記パターン識別回路は、
1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するかどうかを判断することと、
1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するとの判断に応答して、非圧縮入力ワードを示す前記複数のプレフィックスのうちのプレフィックスに関連して、前記非割当て入力ワードの非圧縮データ部分として前記出力生成回路に、前記1つまたは複数の非割当て入力ワードの各非割当て入力ワードの値を出力することと
を行うようにさらに構成される、請求項1に記載のCMC。
【請求項４】
前記出力生成回路は、前記複数の割当てプレフィックスに対応し、前記圧縮出力ブロックの前記1つまたは複数の最頻出パターンが、前記複数の割当てプレフィックスの対応する割当てプレフィックスに関連する最頻出パターンを含むかどうかを各々が示す、複数のフラグインジケータをさらに備える前記圧縮出力ブロックを生成するように構成される、請求項1に記載のCMC。
【請求項５】
前記出力生成回路は、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいかどうかを判断することと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいとの判断に応答して、メモリアレイに前記圧縮出力ブロックを記憶することと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さくないとの判断に応答して、前記メモリアレイに前記複数の入力ワードを記憶することと
を行うようにさらに構成される、請求項1に記載のCMC。
【請求項６】
前記マスクテーブルの前記複数のマスクの連続するマスクは、縮小するサイズのパターンを生成するように構成される、請求項1に記載のCMC。
【請求項７】
前記パターン識別回路は、前記最頻出パターンが前記複数のパターンの中で少なくとも2回発生すると判断することによって、前記最頻出パターンが前記複数のパターンの中に存在するかどうかを判断するように構成される、請求項1に記載のCMC。
【請求項８】
前記複数のプレフィックスの各々は、3ビットを備え、
前記パターン識別回路は、それぞれサイズが32ビットである、32個の入力ワードを受信することによって、前記複数の入力ワードを受信するように構成される、請求項1に記載のCMC。
【請求項９】
複数のプレフィックスのほか、非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、前記プレフィックスに関連するパターンおよび非圧縮データ部分を備える圧縮入力ブロックを受信することと、
非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、
前記プレフィックスに基づいて、対応する前記非圧縮データ部分へのオフセットを計算することと、
前記オフセットに基づいて、対応する前記非圧縮データ部分を取り出すことと、
前記プレフィックスに対応する前記パターンおよび対応する前記非圧縮データ部分に基づいて、圧縮解除出力ワードを生成することと、
1つまたは複数の圧縮解除出力ワードを備える圧縮解除出力ブロックを生成することと
を行うように構成された圧縮解除回路をさらに備える、請求項1に記載のCMC。
【請求項１０】
集積回路(IC)に組み込まれる、請求項1に記載のCMC。
【請求項１１】
セットトップボックス、エンターテインメントユニット、ナビゲーションデバイス、通信デバイス、固定ロケーションデータユニット、モバイルロケーションデータユニット、モバイルフォン、セルラーフォン、スマートフォン、タブレット、ファブレット、サーバ、コンピュータ、ポータブルコンピュータ、デスクトップコンピュータ、携帯情報端末(PDA)、モニタ、コンピュータモニタ、テレビ、チューナ、ラジオ、衛星ラジオ、音楽プレーヤ、デジタル音楽プレーヤ、ポータブル音楽プレーヤ、デジタルビデオプレーヤ、ビデオプレーヤ、デジタルビデオディスク(DVD)プレーヤ、ポータブルデジタルビデオプレーヤ、および自動車からなる一群から選択されたデバイスに組み込まれる、請求項1に記載のCMC。
【請求項１２】
圧縮メモリコントローラ(CMC)であって、
複数の入力ワードを受信するための手段と、
複数のマスクのマスクごとに、対応する複数のパターンを生成するために前記複数の入力ワードの各非割当て入力ワードに前記マスクを適用するための手段と、
最頻出パターンが前記複数のパターンの中に存在するかどうかを判断するための手段と、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、前記マスクに関連するプレフィックスに関連して、前記最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶するための手段と、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、前記最頻出パターンに対応する各非割当て入力ワードに、前記マスクに関連する前記プレフィックスを割り当てるための手段と、
前記複数の入力ワードに割り当てられた複数の割当てプレフィックスと、
前記複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンと、
前記複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分と
を備える圧縮出力ブロックを生成するための手段と
を備えるCMC。
【請求項１３】
データブロックの効率的なロスレス圧縮を実現するための方法であって、
複数の入力ワードを受信するステップと、
複数のマスクのマスクごとに、
対応する複数のパターンを生成するために前記複数の入力ワードの各非割当て入力ワードに前記マスクを適用するステップと、
最頻出パターンが前記複数のパターンの中に存在するかどうかを判断するステップと、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、
前記マスクに関連するプレフィックスに関連して、前記最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶するステップと、
前記最頻出パターンに対応する各非割当て入力ワードに、前記マスクに関連する前記プレフィックスを割り当てるステップと、
前記複数の入力ワードに割り当てられた複数の割当てプレフィックスと、
前記複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンと、
前記複数の入力ワードの1つまたは複数の対応する入力ワードの1つまたは複数の非圧縮データ部分と
を備える圧縮出力ブロックを生成するステップと
を備える方法。
【請求項１４】
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するかどうかを判断するステップと、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するとの判断に応答して、前記0の値を有する前記複数の入力ワードのうちの前記1つまたは複数の入力ワードの各入力ワードに、0値を示すプレフィックスを割り当てるステップと
をさらに備える、請求項13に記載の方法。
【請求項１５】
前記圧縮出力ブロックを生成する前に、1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するかどうかを判断するステップと、
1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するとの判断に応答して、非圧縮入力ワードを示すプレフィックスに関連して、前記非割当て入力ワードの非圧縮データ部分として、前記1つまたは複数の非割当て入力ワードの各非割当て入力ワードの値を記憶するステップと
をさらに備える、請求項13に記載の方法。
【請求項１６】
前記複数の割当てプレフィックスに対応し、前記圧縮出力ブロックの前記1つまたは複数の最頻出パターンが、前記複数の割当てプレフィックスの対応する割当てプレフィックスに関連する最頻出パターンを含むかどうかを各々が示す、複数のフラグインジケータをさらに備える前記圧縮出力ブロックを生成するステップを備える、請求項13に記載の方法。
【請求項１７】
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいかどうかを判断するステップと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいとの判断に応答して、メモリアレイに前記圧縮出力ブロックを記憶するステップと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さくないとの判断に応答して、前記メモリアレイに前記複数の入力ワードを記憶するステップと
をさらに備える、請求項13に記載の方法。
【請求項１８】
前記複数のマスクの連続するマスクは、縮小するサイズのパターンを生成するように構成される、請求項13に記載の方法。
【請求項１９】
前記最頻出パターンが前記複数のパターンの中に存在するかどうかを判断するステップは、前記最頻出パターンが前記複数のパターンの中で少なくとも2回発生すると判断するステップを備える、請求項13に記載の方法。
【請求項２０】
前記複数のプレフィックスの各々は、3ビットを備え、
前記複数の入力ワードは、それぞれサイズが32ビットである、32個の入力ワードを備える、請求項13に記載の方法。
【請求項２１】
複数のプレフィックスのほか、非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、前記プレフィックスに関連するパターンおよび非圧縮データ部分を備える圧縮入力ブロックを受信するステップと、
非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、
前記プレフィックスに基づいて、対応する前記非圧縮データ部分へのオフセットを計算するステップと、
前記オフセットに基づいて、対応する前記非圧縮データ部分を取り出すステップと、
前記プレフィックスに対応する前記パターンおよび対応する前記非圧縮データ部分に基づいて、圧縮解除出力ワードを生成するステップと、
1つまたは複数の圧縮解除出力ワードを備える圧縮解除出力ブロックを生成するステップと
をさらに備える、請求項13に記載の方法。
【請求項２２】
プロセッサによって実行されると、前記プロセッサに、
複数の入力ワードを受信することと、
複数のマスクのマスクごとに、
対応する複数のパターンを生成するために前記複数の入力ワードの各非割当て入力ワードに前記マスクを適用することと、
最頻出パターンが前記複数のパターンの中に存在するかどうかを判断することと、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、
前記マスクに関連するプレフィックスに関連して、前記最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶することと、
前記最頻出パターンに対応する各非割当て入力ワードに、前記マスクに関連する前記プレフィックスを割り当てることと、
前記複数の入力ワードに割り当てられた複数の割当てプレフィックスと、
前記複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンと、
前記複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分と
を備える圧縮出力ブロックを生成することと
を行わせるコンピュータ実行可能命令を記憶したコンピュータ可読記憶媒体。
【請求項２３】
プロセッサによって実行されると、前記プロセッサに、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するかどうかを判断することと、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するとの判断に応答して、前記0の値を有する前記複数の入力ワードのうちの前記1つまたは複数の入力ワードの各入力ワードに、0値を示すプレフィックスを割り当てることと
をさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２４】
プロセッサによって実行されると、前記プロセッサに、
1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するかどうかを判断することと、
1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するとの判断に応答して、非圧縮入力ワードを示すプレフィックスに関連して、前記非割当て入力ワードの非圧縮データ部分として、前記1つまたは複数の非割当て入力ワードの各非割当て入力ワードの値を記憶することと
をさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２５】
プロセッサによって実行されると、前記プロセッサに、前記複数の割当てプレフィックスに対応し、前記圧縮出力ブロックの前記1つまたは複数の最頻出パターンが、前記複数の割当てプレフィックスの対応する割当てプレフィックスに関連する最頻出パターンを含むかどうかを各々が示す、複数のフラグインジケータをさらに備える前記圧縮出力ブロックを生成することをさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２６】
プロセッサによって実行されると、前記プロセッサに、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいかどうかを判断することと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいとの判断に応答して、メモリアレイに前記圧縮出力ブロックを記憶することと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さくないとの判断に応答して、前記メモリアレイに前記複数の入力ワードを記憶することと
をさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２７】
プロセッサによって実行されると、前記プロセッサに、前記最頻出パターンが前記複数のパターンの中で少なくとも2回発生すると判断することによって、前記最頻出パターンが前記複数のパターンの中に存在するかどうかを判断することをさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２８】
プロセッサによって実行されると、前記プロセッサに、
複数のプレフィックスのほか、非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、前記プレフィックスに関連するパターンおよび非圧縮データ部分を備える圧縮入力ブロックを受信することと、
非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、
前記プレフィックスに基づいて、対応する前記非圧縮データ部分へのオフセットを計算することと、
前記オフセットに基づいて、対応する前記非圧縮データ部分を取り出すことと、
前記プレフィックスに対応する前記パターンおよび対応する前記非圧縮データ部分に基づいて、圧縮解除出力ワードを生成することと、
1つまたは複数の圧縮解除出力ワードを備える圧縮解除出力ブロックを生成することと
をさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
優先出願
本出願は、その内容全体が参照により本明細書に組み込まれる、2016年9月8日に出願された「PROVIDING EFFICIENT LOSSLESS COMPRESSION FOR SMALL DATA BLOCKS IN PROCESSOR-BASED SYSTEMS」と題する米国特許出願第15/259,686号の優先権を主張する。
【０００２】
本開示の技術は、一般に、ロスレス圧縮動作に関し、詳細には、プロセッサベースシステムにおけるキャッシュラインおよびメモリの他の比較的小さいデータブロックのためにロスレス圧縮を実現することに関する。
【背景技術】
【０００３】
ロスレスデータ圧縮技法(すなわち、圧縮データから元のデータが完全に復元されることを可能にするデータ圧縮のための技法)は、様々なコンピュータプロセッサ性能およびアーキテクチャの問題に対処するために有用であることがわかる可能性を有する。非限定的な例として、ロスレスデータ圧縮は、メモリ帯域幅を改善し、有効メモリ容量を拡大し、かつ/またはラストレベルキャッシュ(LLC:last-level cache)サイズを縮小するための機構を提供し得る。これらの利益を実現するために、実装される特定のロスレスデータ圧縮機構は、従来のキャッシュラインのサイズのデータブロック(たとえば、いくつかの態様では128バイトのデータブロック)など、比較的小さいデータブロックを効率的に圧縮することが可能であるべきである。
【０００４】
だが、ZIP圧縮など、大半の従来のロスレス圧縮方法は、比較的大きいデータブロック(たとえば、1キロバイト(KB)以上のデータブロック)に対して作用するように設計されている。その上、小さいブロックの圧縮のための従来の解決策は、いくつかの関連する欠点を有するか、または有効性が未知である。たとえば、SmazおよびBase-Delta-Immediate圧縮機構は、小データブロックを圧縮するときに許容可能な結果を達成しないことがある一方、FPC(Frequent Pattern Compression)機構は、データブロック内の主に0値を圧縮することに基づく。Cache Packer(C-Pack)方法として知られている最近開発された圧縮機構は、ZIP圧縮と似ており、伝えられるところでは、小さいブロックの場合に最適化される。だが、C-Packは、実装するのが比較的複雑であり、その全体的な有効性はよく知られていない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、キャッシュラインなどの小データブロックの効率的な圧縮を実現するために、比較的単純なロスレス圧縮機構が望ましい。
【課題を解決するための手段】
【０００６】
発明を実施するための形態で開示する態様は、プロセッサベースシステムにおける小データブロックのための効率的なロスレス圧縮を実現することを含む。この点について、いくつかの態様では、比較的小さいデータブロック内のパターンを検出および符号化するための圧縮メモリコントローラが提供される。圧縮メモリコントローラは、プレフィックスに各々が関連する、複数のマスクを記憶するマスクテーブルを提供する。圧縮メモリコントローラはまた、パターン識別回路および出力生成回路を含む。
【０００７】
パターン識別回路は最初に、圧縮されるべき複数の入力ワードを備える入力データブロックを受信する。例示的な態様では、入力データブロックは、それぞれ32ビットの32個の入力ワードを備える128バイトのラインを備え得る。パターン識別回路は、次いで、マスクテーブルにおけるマスクにわたって反復し、各反復中に、複数のパターン(すなわち、入力ワードのマスクされていない部分)を生成するために入力ワードにマスクを適用する。生成パターンの間のパターンが最頻出パターンとして識別された場合、そのパターンおよび対応する各入力ワードの非圧縮データ部分(すなわち、パターンを生成するためにマスクオフされた入力ワードの部分)(ある場合)が、マスクに関連するプレフィックスに関連して出力生成回路に出力される。最頻出パターンに対応する各入力ワードは、マスクに対応するプレフィックスを割り当てられ、パターン識別回路は、残りの非割当て入力ワードに次のマスクを適用する。
【０００８】
パターン識別回路は、入力ワードの各々に割り当てられたプレフィックスを出力生成回路に出力する。出力生成回路は次いで、入力ワードごとに、割当てプレフィックスを含み、割当てプレフィックスに各々が関連する1つまたは複数の頻出パターン、および1つまたは複数の対応する入力ワードの1つまたは複数の非圧縮データ部分も含む、圧縮出力ブロックを生成する。
【０００９】
いくつかの態様では、マスクテーブルはまた、0値を示すプレフィックスを含み得る。マスクテーブルのマスクにわたる反復を始める前に、パターン識別回路は最初に、0の値を有する入力ワードがあるかどうかを判断し得る。該当する場合、パターン識別回路は、0の値を有する入力ワードに、0値を示すプレフィックスを割り当て得る。いくつかの態様は、マスクテーブルのマスクにわたる反復を完了させた後、パターン識別回路が、複数の入力ワードの間に残存する非割当て入力ワードがあるかどうかを判断し得ることを規定し得る。該当する場合、パターン識別回路は、非圧縮入力ワードを示すプレフィックスに関連して、非割当て入力ワードの非圧縮データ部分として、各非割当て入力ワードの値を出力生成回路に出力し得る。いくつかの態様によれば、出力生成回路は、マスクテーブルにおけるプレフィックスごとに1つ、圧縮中にプレフィックスのうちのどれが入力ワードに割り当てられたかを示す、フラグのセットをさらに含む圧縮出力ブロックを生成し得る。
【００１０】
別の態様では、圧縮メモリコントローラ(CMC)が提供される。CMCは、複数のマスクおよび関連する複数のプレフィックスを提供するマスクテーブルを備える。CMCは、パターン識別回路をさらに備える。パターン識別回路は、複数の入力ワードを受信するように構成される。パターン識別回路は、マスクテーブルの複数のマスクのマスクごとに、対応する複数のパターンを生成するために複数の入力ワードの各非割当て入力ワードにマスクを適用するようにさらに構成される。パターン識別回路はまた、最頻出パターンが複数のパターンの中に存在するかどうかを判断するように構成される。パターン識別回路は加えて、最頻出パターンが複数のパターンの中に存在するとの判断に応答して、マスクに関連する複数のプレフィックスのうちのプレフィックスに関連して出力生成回路に、最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を出力するように構成される。パターン識別回路は、最頻出パターンに対応する各非割当て入力ワードに、マスクに関連するプレフィックスを割り当てるようにさらに構成される。パターン識別回路はまた、複数の入力ワードに割り当てられた複数の割当てプレフィックスを出力生成回路に出力するように構成される。出力生成回路は、圧縮出力ブロックを生成するように構成される。圧縮出力ブロックは、複数の入力ワードに割り当てられた複数の割当てプレフィックスを備える。圧縮出力ブロックは、複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンをさらに備える。圧縮出力ブロックはまた、複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分を備える。
【００１１】
別の態様では、CMCが提供される。CMCは、複数の入力ワードを受信するための手段を備える。CMCは、複数のマスクのマスクごとに、対応する複数のパターンを生成するために複数の入力ワードの各非割当て入力ワードにマスクを適用するための手段をさらに備える。CMCはまた、最頻出パターンが複数のパターンの中に存在するかどうかを判断するための手段を備える。CMCは加えて、最頻出パターンが複数のパターンの中に存在するとの判断に応答して、マスクに関連するプレフィックスに関連して、最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶するための手段を備える。CMCは、最頻出パターンが複数のパターンの中に存在するとの判断に応答して、最頻出パターンに対応する各非割当て入力ワードに、マスクに関連するプレフィックスを割り当てるための手段をさらに備える。CMCはまた、複数の入力ワードに割り当てられた複数の割当てプレフィックス、複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターン、および複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分を備える圧縮出力ブロックを生成するための手段を備える。
【００１２】
別の態様では、データブロックの効率的なロスレス圧縮を実現するための方法が提供される。本方法は、複数の入力ワードを受信するステップを備える。本方法は、複数のマスクのマスクごとに、対応する複数のパターンを生成するために複数の入力ワードの各非割当て入力ワードにマスクを適用するステップをさらに備える。本方法はまた、最頻出パターンが複数のパターンの中に存在するかどうかを判断するステップを備える。本方法は加えて、最頻出パターンが複数のパターンの中に存在するとの判断に応答して、マスクに関連するプレフィックスに関連して、最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶するステップを備える。本方法は、最頻出パターンに対応する各非割当て入力ワードに、マスクに関連するプレフィックスを割り当てるステップをさらに備える。本方法はまた、複数の入力ワードに割り当てられた複数の割当てプレフィックス、複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターン、および複数の入力ワードの1つまたは複数の対応する入力ワードの1つまたは複数の非圧縮データ部分を備える圧縮出力ブロックを生成するステップを備える。
【００１３】
別の態様では、コンピュータ実行可能命令を記憶した非一時的コンピュータ可読媒体が提供される。プロセッサによって実行されると、コンピュータ実行可能命令は、プロセッサに、複数の入力ワードを受信することを行わせる。コンピュータ実行可能命令は、プロセッサに、複数のマスクのマスクごとに、対応する複数のパターンを生成するために複数の入力ワードの各非割当て入力ワードにマスクを適用することをさらに行わせる。コンピュータ実行可能命令はまた、プロセッサに、最頻出パターンが複数のパターンの中に存在するかどうかを判断することを行わせる。コンピュータ実行可能命令は加えて、プロセッサに、最頻出パターンが複数のパターンの中に存在するとの判断に応答して、マスクに関連するプレフィックスに関連して、最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶することを行わせる。コンピュータ実行可能命令は、プロセッサに、最頻出パターンに対応する各非割当て入力ワードに、マスクに関連するプレフィックスを割り当てることをさらに行わせる。コンピュータ実行可能命令は、プロセッサに、複数の入力ワードに割り当てられた複数の割当てプレフィックス、複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターン、および複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分を備える圧縮出力ブロックを生成することをさらに行わせる。
【図面の簡単な説明】
【００１４】
【図１】プロセッサベースシステムを含む例示的なシステムオンチップ(SoC)の概略図である。
【図２】複数の中央処理装置(CPU)とメモリ帯域幅の圧縮を実現するように構成された圧縮メモリコントローラ(CMC)とを有する例示的なプロセッサベースシステムを含むSoCの概略図である。
【図３】メモリ帯域幅の圧縮を実現するために用いられ得るオプションの内部メモリにCMCがさらに通信可能に結合される、図2のCMCのより詳細な概略図である。
【図４】キャッシュラインおよび他の比較的小さいデータブロックの効率的なロスレス圧縮を実現するための図2および図3のCMCの例示的な要素を示す図である。
【図５】小データブロックのロスレス圧縮を実行するための図2、図3、および図4のCMCによって使用され得る例示的なマスクテーブルを示す図である。
【図６Ａ】入力データワードを圧縮し、圧縮出力ブロックを生成するための図2、図3、および図4のCMCの例示的な動作を示す図である。
【図６Ｂ】入力データワードを圧縮し、圧縮出力ブロックを生成するための図2、図3、および図4のCMCの例示的な動作を示す図である。
【図６Ｃ】入力データワードを圧縮し、圧縮出力ブロックを生成するための図2、図3、および図4のCMCの例示的な動作を示す図である。
【図６Ｄ】入力データワードを圧縮し、圧縮出力ブロックを生成するための図2、図3、および図4のCMCの例示的な動作を示す図である。
【図６Ｅ】入力データワードを圧縮し、圧縮出力ブロックを生成するための図2、図3、および図4のCMCの例示的な動作を示す図である。
【図７】圧縮入力ブロックを圧縮解除して圧縮解除出力ブロックにするための図2、図3、および図4のCMCの例示的な動作を示す図である。
【図８Ａ】小データブロックのロスレス圧縮を実行するための図2、図3、および図4のCMCの例示的な動作を示すフローチャートである。
【図８Ｂ】小データブロックのロスレス圧縮を実行するための図2、図3、および図4のCMCの例示的な動作を示すフローチャートである。
【図８Ｃ】小データブロックのロスレス圧縮を実行するための図2、図3、および図4のCMCの例示的な動作を示すフローチャートである。
【図８Ｄ】小データブロックのロスレス圧縮を実行するための図2、図3、および図4のCMCの例示的な動作を示すフローチャートである。
【図９】圧縮入力ブロックを圧縮解除して圧縮解除出力ブロックにするための図2、図3、および図4のCMCの例示的な動作を示すフローチャートである。
【図１０】図2、図3、および図4のCMCを含むことができる例示的なプロセッサベースシステムのブロック図である。
【発明を実施するための形態】
【００１５】
ここで図面を参照して、本開示のいくつかの例示的な態様について説明する。「例示的」という語は、本明細書では「例、事例、または例示としての働きをすること」を意味するために使用される。本明細書で「例示的」と記載されている任意の態様は、必ずしも他の態様よりも好ましいまたは有利であると解釈されるべきではない。
【００１６】
発明を実施するための形態で開示する態様は、プロセッサベースシステムにおける小データブロックのための効率的なロスレス圧縮を実現することを含む。この点について、いくつかの態様では、比較的小さいデータブロック内のパターンを検出および符号化するための圧縮メモリコントローラが提供される。圧縮メモリコントローラは、プレフィックスに各々が関連する、複数のマスクを記憶するマスクテーブルを提供する。圧縮メモリコントローラはまた、パターン識別回路および出力生成回路を含む。
【００１７】
パターン識別回路は最初に、圧縮されるべき複数の入力ワードを備える入力データブロックを受信する。例示的な態様では、入力データブロックは、それぞれ32ビットの32個の入力ワードを備える128バイトのラインを備え得る。パターン識別回路は、次いで、マスクテーブルにおけるマスクにわたって反復し、各反復中に、複数のパターン(すなわち、入力ワードのマスクされていない部分)を生成するために入力ワードにマスクを適用する。生成パターンの間のパターンが最頻出パターンとして識別された場合、そのパターンおよび対応する各入力ワードの非圧縮データ部分(すなわち、パターンを生成するためにマスクオフされた入力ワードの部分)(ある場合)が、マスクに関連するプレフィックスに関連して出力生成回路に出力される。最頻出パターンに対応する各入力ワードは、マスクに対応するプレフィックスを割り当てられ、パターン識別回路は、残りの非割当て入力ワードに次のマスクを適用する。
【００１８】
パターン識別回路は、入力ワードの各々に割り当てられたプレフィックスを出力生成回路に出力する。出力生成回路は次いで、入力ワードごとに、割当てプレフィックスを含み、割当てプレフィックスに各々が関連する1つまたは複数の頻出パターン、および1つまたは複数の対応する入力ワードの1つまたは複数の非圧縮データ部分も含む、圧縮出力ブロックを生成する。
【００１９】
小データブロックのための効率的なロスレス圧縮を実現するための動作についてより詳細に述べる前に、図1〜図3に関して例示的なプロセッサベースシステムおよびその要素について説明する。この点について、図1は、プロセッサベースシステム102を含む例示的なシステムオンチップ(SoC)100の概略図である。プロセッサベースシステム102は、この例では複数の中央処理装置(CPU)ブロック104(0)〜104(N)を含み、ここで「N」は、所望のCPUブロック104(0)〜104(N)の任意の数に等しい。図1の例では、CPUブロック104(0)〜104(N)の各々は、2つのCPU106(0)、CPU106(1)を含む。CPUブロック104(0)〜104(N)は、それぞれ、共有レベル2(L2)キャッシュ108(0)〜108(N)をさらに含む。CPUブロック104(0)〜104(N)の各々のいずれかによって使用されるか、またはCPUブロック104(0)〜104(N)の各々の間で共有される、キャッシュされたデータを記憶するために、システムキャッシュ110(たとえば、レベル3(L3)キャッシュ)も設けられる。CPUブロック104(0)〜104(N)の各々がシステムキャッシュ110ならびに他の共有リソースにアクセスすることを可能にするために、内部システムバス112が設けられる。内部システムバス112を介してCPUブロック104(0)〜104(N)によってアクセスされる他の共有リソースは、メイン外部メモリ(たとえば、非限定的な例として、ダブルレートダイナミックランダムアクセスメモリ(DRAM)(DDR))にアクセスするためのメモリコントローラ114、周辺機器116、他のストレージ118、エクスプレス周辺機器構成要素相互接続(PCI-e)インターフェース120、ダイレクトメモリアクセス(DMA)コントローラ122、および/または統合メモリコントローラ(IMC)124を含み得る。
【００２０】
図1においてプロセッサベースシステム102において実行されるプロセッサベースアプリケーションの複雑性および性能が増大するにつれて、メモリ帯域幅に対する制限が、プロセッサベースシステム102に対して制約を課すことがある。外部メモリへのアクセスがメモリ帯域幅限界に達した場合、プロセッサベースシステム102のメモリコントローラ114は、メモリアクセス要求をキューイングすることを余儀なくされ得る。メモリアクセス要求のそのようなキューイングは、メモリアクセスのレイテンシを増大させることがあり、ひいてはプロセッサベースシステム102の性能を低下させることがある。
【００２１】
これらの問題に対処するために、プロセッサベースシステム102のいくつかの態様は、L2キャッシュ108(0)〜108(N)、システムキャッシュ110、および/またはシステムメモリなどのメモリアレイに書き込まれるデータのための圧縮を実現するように構成された圧縮メモリコントローラ(CMC)を提供し得る。この点について、図2は、図1のプロセッサベースシステム102と同様の複数のCPUブロック104(0)〜104(N)を有するプロセッサベースシステム202を含むSoC200の概略図である。図2のプロセッサベースシステム202は、図1のプロセッサベースシステム102と共通のいくつかの構成要素を含み、それらは、図1と図2との間で共通の要素番号によって示される。簡潔にするために、これらの構成要素を再び説明しない。しかしながら、図2のプロセッサベースシステム202では、CMC204が設けられる。CMC204は、システムメモリ206へのアクセスを制御する。システムメモリ206は、非限定的な例として、1つまたは複数のDDR DRAM208(0)〜208(R)(以下、「DRAM208(0)〜208(R)」と呼ぶ)を備え得る。この例におけるCMC204は、ここおよび以下で開示する態様によるメモリ帯域幅の圧縮を用いる。図1のプロセッサベースシステム102のメモリコントローラ114と同様に、図2のプロセッサベースシステム202におけるCMC204は、内部システムバス112を介してCPUブロック104(0)〜104(N)によって共有される。
【００２２】
図2のプロセッサベースシステム202は、要素の中でも、知られているデジタル論理要素、半導体回路、処理コア、および/もしくはメモリ構造のうちのいずれか1つ、またはそれらの組合せを包含し得る。本明細書で説明する態様は、要素の任意の特定の構成に限定されず、開示する技法は、半導体ダイまたはパッケージ上の様々な構造およびレイアウトに容易に拡張され得る。プロセッサベースシステム202のいくつかの態様が、図2に示すものに加えて要素を含んでよいことを理解されたい。
【００２３】
図2のCMC204の例示的な内部構成要素のより詳細な概略図が、図3において提供される。この例では、CMC204は、図2のCPUブロック104(0)〜104(N)を含む半導体ダイ302(0)、302(1)とは別個の半導体ダイ300上に設けられる。代替的には、いくつかの態様では、CMC204は、CPUブロック104(0)〜104(N)と共通の半導体ダイ(図示せず)内に含まれ得る。ダイ構成に関係なく、CMC204は、CPUブロック104(0)〜104(N)が内部システムバス112を介してCMC204へメモリアクセス要求を行い得、CMC204を介してメモリからデータを受信し得るように設けられる。
【００２４】
引き続き図3を参照すると、CMC204は、DRAM208(0)〜208(R)を備えるものとして図2および図3に示されたシステムメモリ206へのメモリアクセスのための動作を制御する。CMC204は、メモリアクセス要求に対処するために使用される複数のメモリインターフェース(MEM I/F)304(0)〜304(P)(たとえば、DDR DRAMインターフェース)を含む。この点について、この例におけるCMC204は、圧縮コントローラ306を含む。圧縮コントローラ306は、CPUブロック104(0)〜104(N)からのメモリアクセス要求に応答して、システムメモリ206に記憶されるデータの圧縮、およびシステムメモリ206から取り出されたデータの圧縮解除を制御する。圧縮コントローラ306はまた、内部システムバス112を介してCPUブロック104(0)〜104(N)に提供される情報の帯域幅圧縮を実行するように構成され得る。
【００２５】
ローカルメモリ308は、圧縮技法およびアルゴリズムを実行するために圧縮コントローラ306によって必要とされるデータ構造および他の情報のために設けられる。この点について、ローカルメモリ308は、スタティックランダムアクセスメモリ(SRAM)310の形態で設けられる。ローカルメモリ308は、圧縮技法およびアルゴリズムを実行するために圧縮コントローラ306のために必要とされ得るデータ構造および他のデータ記憶のために使用されるのに十分なサイズである。ローカルメモリ308はまた、CMC204内の内部使用のための追加のキャッシュメモリを提供するために、レベル4(L4)キャッシュなどのキャッシュを含むように区分され得る。したがって、L4コントローラ312もまた、L4キャッシュへのアクセスを提供するために、CMC204内に設けられ得る。強化された圧縮技法およびアルゴリズムは、より大きい内部メモリを必要とし得る。たとえば、ローカルメモリ308は、128キロバイト(kB)のメモリを提供し得る。
【００２６】
さらに、図3に示すように、オプションの、追加の内部メモリ314もまた、CMC204のために設けられ得る。追加の内部メモリ314は、一例として、DRAMとして設けられ得る。追加の内部メモリ314は、プロセッサベースシステム202のメモリ帯域幅の圧縮を増加させるために、追加の、またはメモリ帯域幅の圧縮および圧縮解除の機構を提供するCMC204のためのローカルメモリ308内よりも大量の、データ構造および他のデータの記憶を容易にし得る。いくつかの態様は、圧縮で使用するための追加の内部メモリ314へのメモリアクセスを制御するために、CMC204内に内部メモリコントローラ316を設け得る。そのような態様では、内部メモリコントローラ316は、CPUブロック104(0)〜104(N)にとってアクセス可能または可視ではない。
【００２７】
ローカルメモリ308および追加の内部メモリ314を含む、図3のCMC204内に提供されるリソースの各々は、リソースおよび領域、電力消費、増大したメモリ容量、ならびに増大した性能の間の所望のバランスを達成するために、互いに独立して、または互いに組み合わせて使用され得る。さらに、CMC204による使用のための上記で説明したリソースは、効率、電力消費、および性能の間の所望のトレードオフを達成するために有効化または無効化され得る。
【００２８】
小データブロックの効率的なロスレス圧縮を実現するための図2および図3のCMC204の例示的な要素を示すために、図4が提供される。図4に見られるように、プロセッサベースシステム202は、CMC204およびメモリアレイ400を含む。いくつかの態様では、メモリアレイ400は、非限定的な例として、図1のL2キャッシュ108(0)〜108(N)および/もしくはシステムキャッシュ110などのキャッシュ、図2のシステムメモリ206、ならびに/または図3のローカルメモリ308および/もしくは内部メモリ314を備え得る。CMC204は、複数のマスク(図示せず)および関連するプレフィックス(図示せず)が記憶されるマスクテーブル402を提供する。CMC204は、パターン識別回路404および出力生成回路406をさらに備える。パターン識別回路404は、複数の入力ワード(図示せず)を備える非圧縮入力ブロック408を受信し、パターンを生成するためにマスクテーブル402からのマスクを入力ワードに適用し、マスクごとに最頻出パターンを識別し、入力ワードを圧縮して、マスクに対応するプレフィックスおよび非圧縮データ部分にするように構成される。出力生成回路406は、圧縮データをアセンブルして圧縮出力ブロック410にする。マスクテーブル402の構造および内容は、図5に関して以下でより詳細に説明し、非圧縮入力ブロック408のロスレス圧縮を実現するためのパターン識別回路404および出力生成回路406によって実行される例示的な動作は、図6A〜図6Eに関して以下でより詳細に説明する。
【００２９】
図5は、小データブロックのロスレス圧縮を実行するための図2、図3、および図4のCMC204によって使用され得る図4のマスクテーブル402の例示的な態様を示す。説明のために、図5の例では、32ビット入力ワードを符号化するためにマスクテーブル402が使用されると仮定される。図5に見られるように、マスクテーブル402は、複数のプレフィックス500(0)〜500(7)を含み、それらの各々が、0から7までの範囲の3ビット値を備える。いくつかの態様では、プレフィックス500(0)〜500(7)の各々は、図5に示すものよりも多いまたは少ないビットを備え、図5に示す8個よりも多いまたは少ないプレフィックス500(0)〜500(7)が生じる場合があることを理解されたい。
【００３０】
マスクテーブル402は、複数のマスク502(0)〜502(5)をさらに含み、それらの各々が、それぞれ、プレフィックス500(2)〜500(7)に関連付けられ、それらの各々が、32ビットマスク値を備える。図5に見られるように、マスク502(0)〜502(5)は、マスク502(0)〜502(5)の連続するものが、論理AND演算を使用してマスク502(0)〜502(5)が適用される入力ワードのますます大きくなる部分をマスクオフするように選択される。たとえば、マスク502(1)は、0xFFFFFFF0の16進値を有し、マスク502(1)が適用される入力ワードの下位4ビットをマスクオフする一方、マスク502(2)は、0xFFFFFF00の16進値を有し、入力ワードの下位8ビットをマスクオフし、以下同様である。本明細書で使用する「非圧縮データ部分」という用語は、所与のマスク502(0)〜502(5)によってマスクオフされる入力ワードの下位ビットを指す一方、「パターン」という用語は、マスク502(0)〜502(5)によってオンにされている残りの上位ビットを指す。したがって、0xFFFF0000の16進値を有するマスク502(4)が、0x1234ABCDの16進値を有する入力ワードに適用された場合、入力ワードに関する派生パターンは、値0x1234となる一方、入力ワードに関する非圧縮データ部分は、値0xABCDとなる。
【００３１】
図5に示す態様では、プレフィックス500(0)および500(1)がマスクに関連付けられないことに留意されたい。代わりに、プレフィックス500(0)は、(0x00000000の16進値を有するマスク502が入力ワードに適用されたかのように)それが割り当てられる入力ワードが圧縮されないことを示すために使用される。プレフィックス500(1)は、それが割り当てられる入力ワードが0の値を有することを示すために使用される。
【００３２】
図5は、マスクテーブル402のプレフィックス500(0)〜500(7)およびマスク502(0)〜502(5)の使用から生じる派生パターンサイズ504(0)〜504(5)および派生非圧縮データ部分サイズ506(0)〜506(7)をさらに示す。プレフィックス500(0)は、非圧縮入力ワードを示し、32ビット(すなわち、入力ワード全体)の派生非圧縮データ部分サイズ506(0)に関連付けられる。逆に、0値を有する入力ワードを示すプレフィックス500(1)は、0ビットの派生非圧縮データ部分サイズ506(1)に関連付けられる(すなわち、入力ワードを圧縮するためにプレフィックス500(1)のみが記憶される必要がある)。図5に見られるように、マスク502(0)によって生成された派生パターンサイズ504(0)は32ビットである一方、マスク502(0)によって生成された派生非圧縮データ部分サイズ506(2)は0ビットである。これは、0xFFFFFFFFの16進値を有するマスク502(0)を入力ワードに適用すると、入力ワード全体がパターンとして使用されることになるためである。図5に示す各後続マスク502(1)〜502(5)は、先行する派生パターンサイズ504(0)〜504(4)よりも4ビット小さい派生パターンサイズ504(1)〜504(5)、および先行する派生非圧縮データ部分サイズ506(2)〜506(6)よりも4ビット大きい派生非圧縮データ部分サイズ506(3)〜506(7)を生成する。
【００３３】
いくつかの態様におけるマスク502(0)〜502(5)の値は、図5に示す値とは異なることがあり、頻繁に遭遇する入力ワード値および/または予想される入力ワード値に基づいて選択されることがあることを理解されたい。いくつかの態様によれば、マスク502(0)〜502(5)うちの1つまたは複数は、先行または後続マスク502(0)〜502(5)によって生成されるものと同じサイズを有する派生パターンを生成し得る。非限定的な例として、2つの連続するマスク502(0)〜502(5)はそれぞれ、32ビットのサイズを有する派生パターンを生成し得る。
【００３４】
図2、図3、および図4のCMC204は、入力ワードのロスレス圧縮を実行するために図5のプレフィックス500(0)〜500(7)およびマスク502(0)〜502(5)を用いる。この点について、図6A〜図6Eは、入力データワードを圧縮し、圧縮出力ブロック410を生成するための図4のパターン識別回路404および出力生成回路406の例示的な動作を示すために提供される。図6Aに見られるように、パターン識別回路404によって受信される非圧縮入力ブロック408は、複数の入力ワード600(0)〜600(X)を備える。いくつかの態様では、入力ワード600(0)〜600(X)は、それぞれサイズが32ビットである、32個の入力ワードを備え得る。説明の目的で、図6A〜図6Dは、非圧縮入力ブロック408が処理されて概念上の圧縮出力ブロック602になることを示し、これは、入力ワード600(0)〜600(X)とそれらの圧縮形式との間の関係を示す。次いで、概念上の圧縮出力ブロック602は、図6Eに示すように、再編成されて実際の圧縮出力ブロック410になる。図6A〜図6Eには示されていないが、この処理および再編成は、一時バッファ、レジスタ、メモリなどのような中間ストレージの使用を含み得る。
【００３５】
いくつかの態様によれば、パターン識別回路404は最初に、0の値を有する入力ワード600(0)〜600(X)を探し得る。これらの入力ワード600(0)〜600(X)は、全0値を示すプレフィックス500(1)を割り当てられる。図6Aの例では、パターン識別回路404は、0の値(0または0x00000000の16進値)を有する入力ワード600(3)を識別し、入力ワード600(3)を、(マスクテーブル402のプレフィックス500(1)に対応する)1の値を有する割当てプレフィックス604(3)に関連付ける。入力ワード600(3)は0の値を有するので、入力ワード600(3)を圧縮するために割当てプレフィックス604(3)以外の情報を記憶する必要がない。
【００３６】
ここで図6Bを参照すると、パターン識別回路404は次に、マスクテーブル402のマスク502(0)〜502(5)の各々を順に非割当て入力ワード600(0)〜600(2)および600(4)〜600(X)に適用するプロセスを始める。入力ワード600(3)は、割当てプレフィックス604(3)にすでに関連付けられており、さらなる処理から除外されることに留意されたい。図6Bでは、パターン識別回路404は最初に、複数の生成パターン606(0)〜606(6)を生成するために、0xFFFFFFFFの値を有するマスク502(0)を非割当て入力ワード600(0)〜600(2)および600(4)〜600(X)に適用する。マスク502(0)は、0xFFFFFFFFの16進値を有するので、生成パターン606(0)〜606(6)の各々は、対応する入力ワード600(0)〜600(2)、600(4)〜600(X)と同じ値を有する。したがって、生成パターン606(0)は、0xAEB0E67Dの16進値を有し、生成パターン606(1)は、0X9C06F5A9の16進値を有し、以下同様である。
【００３７】
パターン識別回路404は次に、最頻出パターンが生成パターン606(0)〜606(6)の中に存在するかどうかを判断する。いくつかの態様では、生成パターン606(0)〜606(6)は、それが生成パターン606(0)〜606(6)の間で少なくとも2回発生するのでなければ、最頻出パターンであるとは見なされない。いくつかの態様は、2つ以上の頻出パターンが識別された(すなわち、生成パターン606(0)〜606(6)のうちの2つ以上が繰り返し発生し、同じ回数発生する)場合に、パターン識別回路404が、頻出パターンのうちの1つをランダムに、または任意の基準に従って選択し得ることを規定し得る。図6Bの例では、パターン識別回路404は、最頻出パターンが、それぞれ、入力ワード600(2)および600(6)に対応する生成パターン606(2)および606(5)において発生する、16進値0x8FFBC3CAであると判断する。したがって、パターン識別回路404は、入力ワード600(2)および600(6)を、(マスクテーブル402のプレフィックス500(2)に対応する)2の値を各々が有する、割当てプレフィックス604(2)および604(6)に関連付ける。パターン識別回路404はまた、プレフィックス500(2)に関連して最頻出パターン608(0)として生成パターン606(2)、606(5)の値を記憶する。
【００３８】
動作は次いで図6Cで継続し、パターン識別回路404は、0xFFFFFFF0の16進値を有する次のマスク502(1)を非割当て入力ワード600(0)、600(1)、600(4)、600(5)、および600(X)に適用する。マスク502(1)は、入力ワード600(0)、600(1)、600(4)、600(5)、および600(X)の各々の下位4ビットをマスクオフするように働き、それぞれ28ビットの長さを有する生成パターン606(0)〜606(4)が生じる。結果として、生成パターン606(0)は、0xAEB0E67の16進値を有し、生成パターン606(1)は、0x9C06F5Aの16進値を有し、以下同様である。
【００３９】
パターン識別回路404は次いで、最頻出パターンが生成パターン606(0)〜606(4)の中に存在するかどうかを判断する。図6Cの例では、生成パターン606(0)、606(2)、および606(4)は、0xAEB0E67の16進値を有する一方、生成パターン606(1)および606(3)は両方とも、0x9C06F5Aの16進値を有する。したがって、パターン識別回路404は、最頻出パターンとして、入力ワード600(0)、600(4)、および600(X)に対応する、生成パターン606(0)、606(2)、および606(4)を識別する。図6Cに見られるように、パターン識別回路404は、入力ワード600(0)、600(4)、および600(X)を、それぞれ、割当てプレフィックス604(0)、604(4)、および604(X)に関連付け、割当てプレフィックス604(0)、604(4)、および604(X)の各々が(マスクテーブル402のプレフィックス500(3)に対応する)3の値を有する。生成パターン606(0)〜606(4)を生成するときにマスク502(1)によってマスクオフされた入力ワード600(0)、600(4)、および600(X)の部分も、非圧縮データ部分610(0)、610(2)、および610(4)として、割当てプレフィックス604(0)、604(4)、および604(X)とともに記憶される。たとえば、非圧縮データ部分610(0)は、マスク502(1)によってマスクオフされた入力ワード600(0)の16進値0xAEB0E67Dの下位4ビットの値に対応する、0xDの16進値を有する。最後に、パターン識別回路404は、プレフィックス500(3)に関連して最頻出パターン608(1)として生成パターン606(0)、606(2)、606(4)の値を記憶する。
【００４０】
ここで図6Dを参照すると、パターン識別回路404は、0xFFFFFF00の16進値を有するマスク502(2)を残りの非割当て入力ワード600(1)および600(5)に適用することによって継続する。生成パターン606(0)および606(1)は、16進値0x9C06F5を生成するために入力ワード600(1)、600(5)の各々の下位8ビットをマスクオフするためにマスク502(2)を使用することによって生成される。入力ワード600(1)、600(5)に対応する生成パターン606(0)および606(1)が同じ値を有するので、パターン識別回路404は、最頻出パターンとして生成パターン606(0)、606(1)を識別する。したがって、パターン識別回路404は、入力ワード600(1)および600(5)を、それぞれ、割当てプレフィックス604(1)および604(5)に関連付け、割当てプレフィックス604(1)および604(5)の各々が(マスクテーブル402のプレフィックス500(4)に対応する)4の値を有する。生成パターン606(0)、606(1)を生成するときにマスク502(2)によってマスクオフされた入力ワード600(1)および600(5)の8ビット部分も、非圧縮データ部分610(1)および610(3)として、割当てプレフィックス604(1)および604(5)とともに記憶される。図6Dの例では、非圧縮データ部分610(1)は、マスク502(2)によってマスクオフされた入力ワード600(1)の16進値0x9C06F5A9の下位8ビットの値に対応する、0xA9の16進値を有する。同様に、非圧縮データ部分610(3)は、入力ワード600(5)の16進値0x9C06F5A8の下位8ビットの値に対応する、0xA8の16進値を有する。パターン識別回路404は加えて、プレフィックス500(4)に関連して最頻出パターン608(2)として生成パターン606(0)、606(1)の値を記憶する。
【００４１】
パターン識別回路404は、この方法での処理を、残りのマスク502(3)〜502(5)を順に非割当て入力ワード600(0)〜600(X)に適用することによって続行する。マスク502(3)〜502(5)の各々に関して、パターン識別回路404は、最頻出パターン(ある場合)を識別しようとする。成功した場合、パターン識別回路404は、最頻出パターンに対応する入力ワード600(0)〜600(X)ごとに、割当てプレフィックス604(0)〜604(X)および非圧縮データ部分610を記憶し、割当てプレフィックス604(0)〜604(X)に関連して最頻出パターンも記憶する。
【００４２】
いくつかの態様では、マスク502(0)〜502(5)のすべてが処理された後、パターン識別回路404は、入力ワード600(0)〜600(X)のいずれかがプレフィックス500(1)〜500(7)に割り当てられていないままであるかどうかを判断し得る。該当する場合、パターン識別回路404は、非圧縮ワードを示すプレフィックス500(0)を、それらの非割当て入力ワード600(0)〜600(X)に割り当てる。パターン識別回路404はまた、プレフィックス500(0)に関連して入力ワード600(0)〜600(X)の非圧縮データ部分610として、各非割当て入力ワード600(0)〜600(X)の値全体を記憶する。
【００４３】
図6A〜図6Dに示す動作中、パターン識別回路404は出力生成回路406に、概念上の圧縮出力ブロック602に示されるデータの一部または全部を出力し得る。マスク502(0)〜502(5)および入力ワード600(0)〜600(X)のすべてが処理された後(またはそのような処理と並行して)、出力生成回路406は、生成されたデータを編成して圧縮出力ブロック410にする。この点について、図6Eは、圧縮出力ブロック410のための例示的なフォーマットを示す。図6Eでは、割当てプレフィックス604(0)〜604(X)は、入力ワード600(0)〜600(X)のうちの1つに各々が対応しており、圧縮出力ブロック410において最初に位置する(最右側から始まり、左に進む)。いくつかの態様では、圧縮出力ブロック410は次に、プレフィックス500(2)〜500(7)のうちの1つに各々が対応する、フラグインジケータ612(0)〜612(5)のセットを含み得る。フラグインジケータ612(0)〜612(5)の各々は、フラグインジケータ612(0)〜612(5)に対応するプレフィックス500(2)〜500(7)を使用して生成された最頻出パターン608(0)〜608(2)が圧縮出力ブロック410に存在するかどうかを示すように、出力生成回路406によって設定される。たとえば、特定の最頻出パターン608(0)〜608(2)がすべて0であった場合、対応するフラグインジケータ612(0)〜612(5)を0に設定し、全0の最頻出パターン608(0)〜608(2)を圧縮出力ブロック410から除外することによって、より高いレベルの圧縮が達成され得る。
【００４４】
次に、圧縮出力ブロック410には、圧縮出力ブロック410内に含まれるようにパターン識別回路404によって識別された最頻出パターン608(0)〜608(2)がある。これらの後に、非圧縮データ部分610(0)〜610(4)が来る。入力ワード600(0)〜600(X)の各々は対応する割当てプレフィックス604(0)〜604(X)を有するが、入力ワード600(0)〜600(X)の一部は対応する非圧縮データ部分610(0)〜610(4)を有しない場合があることに留意されたい。たとえば、0の値を有するか、またはマスク502(0)に割り当てられる入力ワード600(0)〜600(X)は、追加の非圧縮データが圧縮出力ブロック410内に記憶されることを必要としない。
【００４５】
いくつかの態様では、圧縮出力ブロック410を生成した後、出力生成回路406は、入力ワード600(0)〜600(X)の圧縮が成功と見なされるべきかどうかを判断するために、圧縮出力ブロック410のサイズを指定しきい値と比較し得る。たとえば、1024ビットの合計サイズを有する入力ワード600(0)〜600(X)のセットを処理する際に、出力生成回路406は、圧縮出力ブロック410のサイズを513ビットの指定しきい値と比較し得る。圧縮出力ブロック410が指定しきい値よりも小さい場合、出力生成回路406は、圧縮が成功したと判断することができ、圧縮出力ブロック410をメモリアレイ400に記憶することができる。一方、圧縮出力ブロック410が指定しきい値よりも小さくない場合、出力生成回路406は、圧縮が成功しなかったと判断することができ、そのため、元の非圧縮入力ワード600(0)〜600(X)をメモリアレイ400に記憶することができる。
【００４６】
上記で説明したように、CMC204のいくつかの態様は、圧縮入力ブロック414を受信し、圧縮解除出力ブロック416を生成するための圧縮解除回路412も提供し得る。この点について、図7は、圧縮解除を実行するための例示的な動作を示すために提供される。明快にするために、圧縮解除回路412が、図6Eの圧縮出力ブロック410と同じフォーマットおよび内容を有する圧縮入力ブロック414を入力として受信すると仮定される。したがって、圧縮入力ブロック414は、プレフィックス700(0)〜700(X)のセット、フラグ702(0)〜702(5)のセット、パターン704(0)〜704(2)のセット、および非圧縮データ部分706(0)〜706(4)のセットを含む。
【００４７】
圧縮入力ブロック414を圧縮解除するために、圧縮解除回路412は、圧縮解除出力ワード710(0)〜710(X)を生成するために順にプレフィックス700(0)〜700(X)の各々を処理する。0の値を示す図5のプレフィックス500(1)に対応する1の値を有するプレフィックス700(0)〜700(X)の場合、圧縮解除回路412は、さらなる計算なしに、対応する圧縮解除出力ワード710(0)〜710(X)を生成することができる。それ以外は、プレフィックス700(0)〜700(X)ごとに、圧縮解除回路412は、対応する非圧縮データ部分706(0)〜706(4)が圧縮入力ブロック414内のどこに記憶されているかを示すオフセット708を生成する。いくつかの態様では、オフセット708は、パターン704(0)〜704(2)のサイズおよび以前処理されたプレフィックス700(0)〜700(X)に関する以前処理された非圧縮データ部分706(0)〜706(4)のサイズの決定に基づいて生成される。
【００４８】
図7の例では、オフセット708は、プレフィックス700(4)に関して生成され、0xCの16進値を有する非圧縮データ部分706(2)のロケーションを示す。0xAEB0E67の16進値を有するパターン704(1)も、プレフィックス700(4)に関して取り出される。これらは、0xAEB0E67Cの16進値を有する圧縮解除出力ワード710(4)を生成するために結合される。同様の処理が、他のプレフィックス700(0)〜700(X)に関して実行され、図6A〜図6Dの非圧縮入力ブロック408と同じ値を有する圧縮解除出力ブロック416が生じる。
【００４９】
小データブロックのロスレス圧縮を実行するための図2、図3、および図4のCMC204の例示的な動作を示すために、図8A〜図8Dが提供される。明快にするために、図8A〜図8Dについて説明する際に図4、図5、および図6A〜図6Eの要素が参照される。図8Aでは、処理は、CMC204のパターン識別回路404が複数の入力ワード600(0)〜600(X)を受信すること(ブロック800)で始まる。この点について、パターン識別回路404は、本明細書では「複数の入力ワードを受信するための手段」と呼ばれ得る。いくつかの態様では、複数の入力ワード600(0)〜600(X)は、それぞれサイズが32ビットである、32個の入力ワード600(0)〜600(X)を備え得る。
【００５０】
いくつかの態様では、パターン識別回路404は次に、複数の入力ワード600(0)〜600(X)のうちの1つまたは複数の入力ワード600(0)〜600(X)が0の値を有するかどうかを判断し得る(ブロック802)。複数の入力ワード600(0)〜600(X)のいずれも0の値を有しない場合、処理は図8Bのブロック804において再開する。一方、パターン識別回路404が決定ブロック802において、複数の入力ワード600(0)〜600(X)のうちの1つまたは複数の入力ワード600(0)〜600(X)が0の値を有すると判断した場合、パターン識別回路404は、0の値を有する複数の入力ワード600(0)〜600(X)のうちの1つまたは複数の入力ワード600(0)〜600(X)の各入力ワード600(0)〜600(X)に、0値を示すプレフィックス500(1)を割り当てる(ブロック806)。次いで、処理は図8Bのブロック804において継続する。
【００５１】
ここで図8Bを参照すると、パターン識別回路404は、複数のマスク502(0)〜502(5)のマスク502(0)〜502(5)ごとに一連の動作を実行する(ブロック804)。パターン識別回路404は最初に、対応する複数のパターン606(0)〜606(6)を生成するために複数の入力ワード600(0)〜600(X)の各非割当て入力ワード600(0)〜600(X)にマスク502(0)〜502(5)を適用する(ブロック808)。したがって、パターン識別回路404は、本明細書では「複数のマスクのマスクごとに、対応する複数のパターンを生成するために複数の入力ワードの各非割当て入力ワードにマスクを適用するための手段」と呼ばれ得る。パターン識別回路404は次いで、最頻出パターン608(0)〜608(2)が複数のパターン606(0)〜606(6)の中に存在するかどうかを判断する(ブロック810)。したがって、パターン識別回路404は、本明細書では「最頻出パターンが複数のパターンの中に存在するかどうかを判断するための手段」と呼ばれ得る。最頻出パターン608(0)〜608(2)が存在しない(たとえば、いくつかの態様では、生成パターン606(0)〜606(6)のいずれも少なくとも2回発生しない)場合、処理はブロック812において再開する。
【００５２】
一方、パターン識別回路404が決定ブロック810において、最頻出パターン608(0)〜608(2)が存在すると判断した場合、パターン識別回路404は、マスク502(0)〜502(5)に関連するプレフィックス500(2)〜500(7)に関連して、最頻出パターン608(0)〜608(2)および各非割当て入力ワード600(0)〜600(X)の非圧縮データ部分610(0)〜610(4)を記憶する(ブロック814)。この点について、パターン識別回路404は、本明細書では「最頻出パターンが複数のパターンの中に存在するとの判断に応答して、マスクに関連するプレフィックスに関連して、最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶するための手段」と呼ばれ得る。パターン識別回路404は次いで、最頻出パターン608(0)〜608(2)に対応する各非割当て入力ワード600(0)〜600(X)に、マスク502(0)〜502(5)に関連するプレフィックス500(2)〜500(7)を割り当てる(ブロック816)。したがって、パターン識別回路404は、本明細書では「最頻出パターンが複数のパターンの中に存在するとの判断に応答して、最頻出パターンに対応する各非割当て入力ワードに、マスクに関連するプレフィックスを割り当てるための手段」と呼ばれ得る。パターン識別回路404は次いで、処理のために次のマスク502(0)〜502(5)に進む(ブロック812)。マスク502(0)〜502(5)のすべてがパターン識別回路404によって処理された後、処理は図8Cのブロック818において再開する。
【００５３】
ここで図8Cを参照すると、パターン識別回路404のいくつかの態様は、1つまたは複数の非割当て入力ワード600(0)〜600(X)(すなわち、図8Aのブロック806においてプレフィックス500(1)または図8Bのブロック804においてプレフィックス500(2)〜500(7)のうちの1つを割り当てられていない入力ワード600(0)〜600(X))が複数の入力ワード600(0)〜600(X)内に存在するかどうかを判断し得る(ブロック818)。非割当て入力ワード600(0)〜600(X)が存在しない場合、処理はブロック820において再開する。一方、パターン識別回路404が決定ブロック818において、1つまたは複数の非割当て入力ワード600(0)〜600(X)が複数の入力ワード600(0)〜600(X)内に存在すると判断した場合、パターン識別回路404は、非圧縮入力ワード600(0)〜600(X)を示すプレフィックス500(0)に関連して、非割当て入力ワード600(0)〜600(X)の非圧縮データ部分610(0)〜610(4)として、1つまたは複数の非割当て入力ワード600(0)〜600(X)の各非割当て入力ワード600(0)〜600(X)の値を記憶する(ブロック822)。
【００５４】
次いで、CMC204の出力生成回路406は、複数の入力ワード600(0)〜600(X)に割り当てられた複数の割当てプレフィックス604(0)〜604(X)、複数の割当てプレフィックス604(0)〜604(X)のうちの1つに各々が関連する、1つまたは複数の最頻出パターン608(0)〜608(2)、および複数の入力ワード600(0)〜600(X)の対応する1つまたは複数の入力ワード600(0)〜600(X)の1つまたは複数の非圧縮データ部分610(0)〜610(4)を備える圧縮出力ブロック410を生成する(ブロック820)。したがって、出力生成回路406は、本明細書では「複数の入力ワードに割り当てられた複数の割当てプレフィックス、複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターン、および複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分を備える圧縮出力ブロックを生成するための手段」と呼ばれ得る。いくつかの態様では、圧縮出力ブロック410を生成するためのブロック820の動作は、複数の割当てプレフィックス604(0)〜604(X)に対応し、圧縮出力ブロック410の1つまたは複数の最頻出パターン608(0)〜608(2)が、対応する割当てプレフィックス604(0)-604(X)に関連する最頻出パターン608(0)〜608(2)を含むかどうかを示す、複数のフラグインジケータ612(0)〜612(5)を含むように、圧縮出力ブロック410を生成すること(ブロック824)を含み得る。処理は、次いで、図8Dのブロック826において再開する。
【００５５】
図8Dに見られるように、出力生成回路406のいくつかの態様は、圧縮出力ブロック410のサイズが指定しきい値よりも小さいかどうかを判断し得る(ブロック826)。非限定的な例として、入力ワード600(0)〜600(X)の合計サイズが1024ビットである場合、出力生成回路406は、圧縮出力ブロック410が513ビットの指定しきい値よりも小さいかどうかを判断し得る。出力生成回路406が決定ブロック826において、圧縮出力ブロック410のサイズが指定しきい値よりも小さいと判断した場合、出力生成回路406は、メモリアレイ400に圧縮出力ブロック410を記憶し得る(ブロック828)。一方、圧縮出力ブロック410のサイズが指定しきい値よりも小さくないと決定ブロック826において判断された場合、出力生成回路406は、メモリアレイ400に複数の入力ワード600(0)〜600(X)(すなわち、元の非圧縮入力データ)を記憶し得る(ブロック830)。
【００５６】
上記で説明したように、CMC204のいくつかの態様は、圧縮入力ブロック414を圧縮解除して圧縮解除出力ブロック416にするための圧縮解除回路412も提供し得る。この点について、図9は、いくつかの態様による圧縮解除を実行するための図2、図3、および図4のCMC204の例示的な動作を示す。明快にするために、図9について説明する際に図4および図7の要素が参照される。図9における動作は、圧縮解除回路412が、複数のプレフィックス700(0)〜700(X)のほか、非0入力ワード600(0)〜600(X)を表すプレフィックス700(0)〜700(X)ごとに、パターン704(0)〜704(2)およびプレフィックス700(0)〜700(X)に関連する非圧縮データ部分706(0)〜706(4)を備える圧縮入力ブロック414を受信すること(ブロック900)で始まる。圧縮解除回路412は次いで、非0入力ワード600(0)〜600(X)を表す複数のプレフィックス700(0)〜700(X)のプレフィックス700(0)〜700(X)ごとに一連の動作を実行する(ブロック902)。圧縮解除回路412は最初に、プレフィックス700(0)〜700(X)に基づいて、対応する非圧縮データ部分706(0)〜706(4)へのオフセット708を計算する(ブロック904)。圧縮解除回路412は次いで、オフセット708に基づいて、対応する非圧縮データ部分706(0)〜706(4)を取り出す(ブロック906)。圧縮解除回路412は、プレフィックス700(0)〜700(X)に対応するパターン704(0)〜704(2)および対応する非圧縮データ部分706(0)〜706(4)に基づいて、圧縮解除出力ワード710(0)〜710(X)を生成する(ブロック908)。圧縮解除回路412は次いで、1つまたは複数の圧縮解除出力ワード710(0)〜710(X)を備える圧縮解除出力ブロック416を生成する(ブロック910)。
【００５７】
本明細書で開示する態様によるプロセッサベースシステムにおける小データブロックのための効率的なロスレス圧縮を実現することは、任意のプロセッサベースデバイス内で提供されるか、またはこれに一体化されてもよい。この例には、限定はしないが、セットトップボックス、エンターテインメントユニット、ナビゲーションデバイス、通信デバイス、固定ロケーションデータユニット、モバイルロケーションデータユニット、モバイルフォン、セルラーフォン、スマートフォン、タブレット、ファブレット、サーバ、コンピュータ、ポータブルコンピュータ、デスクトップコンピュータ、携帯情報端末(PDA)、モニタ、コンピュータモニタ、テレビ、チューナ、ラジオ、衛星ラジオ、音楽プレーヤ、デジタル音楽プレーヤ、ポータブル音楽プレーヤ、デジタルビデオプレーヤ、ビデオプレーヤ、デジタルビデオディスク(DVD)プレーヤ、ポータブルデジタルビデオプレーヤ、および自動車が含まれる。
【００５８】
この点について、図10は、図2、図3、および図4に示すCMC204を用いることができるプロセッサベースシステム1000の一例を示す。プロセッサベースシステム1000は、1つまたは複数のプロセッサ1004を各々が含む1つまたは複数のCPU1002を含む。CPU1002は、一時的に記憶されたデータへの高速アクセスのためにプロセッサ1004に結合されたキャッシュメモリ1006を有してもよい。CPU1002は、システムバス1008に結合され、プロセッサベースシステム1000内に含まれるマスタデバイスとスレーブデバイスとを相互結合することができる。よく知られているように、CPU1002は、システムバス1008を介してアドレス情報、制御情報およびデータ情報を交換することによって、これらの他のデバイスと通信する。たとえば、CPU1002は、スレーブデバイスの一例として、CMC204にバストランザクション要求を通信することができる。
【００５９】
他のマスタデバイスおよびスレーブデバイスがシステムバス1008に接続されてよい。図10に示すように、これらのデバイスは、例として、メモリシステム1012、1つまたは複数の入力デバイス1014、1つまたは複数の出力デバイス1016、1つまたは複数のネットワークインターフェースデバイス1018、および1つまたは複数のディスプレイコントローラ1020を含むことができる。入力デバイス1014は、限定はしないが、入力キー、スイッチ、音声プロセッサなどを含む、任意のタイプの入力デバイスを含むことができる。出力デバイス1016は、限定はしないが、オーディオ、ビデオ、他の視覚的インジケータなどを含む、任意のタイプの出力デバイスを含むことができる。ネットワークインターフェースデバイス1018は、ネットワーク1022との間のデータの交換を可能にするように構成された任意のデバイスであり得る。ネットワーク1022は、限定はしないが、有線ネットワークまたはワイヤレスネットワーク、プライベートネットワークまたは公衆ネットワーク、ローカルエリアネットワーク(LAN)、ワイヤレスローカルエリアネットワーク(WLAN)、ワイドエリアネットワーク(WAN)、BLUETOOTH(登録商標)ネットワーク、およびインターネットを含む、任意のタイプのネットワークであってもよい。ネットワークインターフェースデバイス1018は、必要に応じて、任意のタイプの通信プロトコルをサポートするように構成され得る。メモリシステム1012は、1つまたは複数のメモリユニット1024(0)〜1024(N)を含むことができる。
【００６０】
CPU1002はまた、システムバス1008を介してディスプレイコントローラ1020にアクセスして、1つまたは複数のディスプレイ1026に送られる情報を制御するように構成されてもよい。ディスプレイコントローラ1020は、1つまたは複数のビデオプロセッサ1028を介して、表示されるべき情報をディスプレイ1026に送り、1つまたは複数のビデオプロセッサ1028は、表示されるべき情報を処理してディスプレイ1026にとって適したフォーマットにする。ディスプレイ1026は、限定はしないが、陰極線管(CRT)、液晶ディスプレイ(LCD)、プラズマディスプレイなどを含む、任意のタイプのディスプレイを含むことができる。
【００６１】
当業者は、本明細書で開示する態様に関して説明する様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズムが、電子ハードウェア、メモリもしくは別のコンピュータ可読媒体に記憶され、プロセッサもしくは他の処理デバイスによって実行される命令、または両方の組合せとして実装され得ることをさらに諒解されよう。本明細書で説明するマスタデバイスおよびスレーブデバイスは、例として、任意の回路、ハードウェア構成要素、集積回路(IC)、またはICチップにおいて使用されてもよい。本明細書で開示するメモリは、任意のタイプおよびサイズのメモリである場合があり、所望の任意のタイプの情報を記憶するように構成される場合がある。この互換性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、およびステップについて、概してそれらの機能に関して上記において説明した。そのような機能がどのように実装されるのかは、特定の適用例、設計選択、および/またはシステム全体に課される設計制約によって決まる。当業者は、特定の適用例ごとに様々な方式で記載の機能を実装してもよいが、そのような実装の決定が、本開示の範囲からの逸脱を引き起こすと解釈されるべきではない。
【００６２】
本明細書で開示する態様に関して説明する様々な例示的な論理ブロック、モジュール、および回路は、プロセッサ、デジタル信号プロセッサ(DSP)、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)もしくは他のプログラマブル論理デバイス、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または本明細書で説明する機能を実行するように設計されたそれらの任意の組合せを用いて実装または実行されてもよい。プロセッサは、マイクロプロセッサであってもよいが、代替としてプロセッサは、任意の従来のプロセッサ、コントローラ、マイクロコントローラ、またはステートマシンであってもよい。プロセッサはまた、コンピューティングデバイスの組合せ(たとえば、DSPおよびマイクロプロセッサの組合せ、複数のマイクロプロセッサ、DSPコアと連携する1つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成)として実装されてもよい。
【００６３】
本明細書で開示する態様は、ハードウェアにおいて具現化されてもよく、かつハードウェアに記憶され、たとえば、ランダムアクセスメモリ(RAM)、フラッシュメモリ、読取り専用メモリ(ROM)、電気的プログラマブルROM(EPROM)、電気的消去可能プログラマブルROM(EEPROM)、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または当技術分野において知られている任意の他の形態のコンピュータ可読媒体の中に存在し得る命令において具現化されてもよい。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取るとともに記憶媒体に情報を書き込むことができるように、プロセッサに結合される。代替として、記憶媒体は、プロセッサと一体化してよい。プロセッサおよび記憶媒体は、ASICの中に存在する場合がある。ASICは、リモート局の中に存在する場合がある。代替として、プロセッサおよび記憶媒体は、個別構成要素としてリモート局、基地局、またはサーバの中に存在する場合がある。
【００６４】
本明細書の例示的な態様のいずれかで説明する動作ステップが、例示および説明のために記載されていることにも留意されたい。説明した動作は、図示のシーケンス以外の数多くの異なるシーケンスにおいて実行される場合がある。さらに、単一の動作ステップにおいて説明する動作は、実際にはいくつかの異なるステップにおいて実行される場合がある。さらに、例示的な態様で説明する1つまたは複数の動作ステップは、組み合わせられてよい。当業者には容易に明らかになるように、フローチャート図に示される動作ステップが数多くの異なる変更を受ける場合があることを理解されたい。情報および信号が様々な異なる技術および技法のいずれかを使用して表される場合があることも当業者は理解されよう。たとえば、上記の説明全体に渡って参照される場合があるデータ、命令、コマンド、情報、信号、ビット、シンボル、およびチップは、電圧、電流、電磁波、磁場もしくは磁気粒子、光場もしくは光学粒子、またはそれらの任意の組合せによって表されてもよい。
【００６５】
本開示の上記の説明は、あらゆる当業者が本開示を作成または使用することを可能にするために提供されている。本開示の様々な変更が当業者に容易に明らかになり、本明細書で定義する一般原理は、本開示の趣旨または範囲から逸脱することなく他の変形形態に適用されてもよい。したがって、本開示は、本明細書で説明する例および設計に限定されるものでなく、本明細書で開示する原理および新規の特徴と一致する最も広い範囲を与えられるべきである。
【符号の説明】
【００６６】
100  システムオンチップ(SoC)
102  プロセッサベースシステム
104(0)〜104(N)  中央処理装置(CPU)ブロック
106(0)  CPU
106(1)  CPU
108(0)〜108(N)  共有レベル2(L2)キャッシュ、L2キャッシュ
110  システムキャッシュ
112  内部システムバス
114  メモリコントローラ
116  周辺機器
118  他のストレージ
120  エクスプレス周辺機器構成要素相互接続(PCI-e)インターフェース
122  ダイレクトメモリアクセス(DMA)コントローラ
124  統合メモリコントローラ(IMC)
200  SoC
202  プロセッサベースシステム
204  CMC
206  システムメモリ
208(0)〜208(R)  DDR DRAM、DRAM
300  半導体ダイ
302(0)  半導体ダイ
302(1)  半導体ダイ
304(0)〜304(P)  メモリインターフェース(MEM I/F)
306  圧縮コントローラ
308  ローカルメモリ
310  スタティックランダムアクセスメモリ(SRAM)
312  L4コントローラ
314  内部メモリ
316  内部メモリコントローラ
400  メモリアレイ
402  マスクテーブル
404  パターン識別回路
406  出力生成回路
408  非圧縮入力ブロック
410  圧縮出力ブロック
412  圧縮解除回路
414  圧縮入力ブロック
416  圧縮解除出力ブロック
500(0)〜500(7)  プレフィックス
502(0)〜502(5)  マスク
504(0)〜504(5)  派生パターンサイズ
506(0)〜506(7)  派生非圧縮データ部分サイズ
600(0)〜600(X)  入力ワード
602  概念上の圧縮出力ブロック
604(0)〜604(X)  割当てプレフィックス
606(0)〜606(6)  生成パターン、パターン
608(0)  〜608(2)  最頻出パターン
610  非圧縮データ部分
610(0)〜610(4)  非圧縮データ部分
612(0)〜612(5)  フラグインジケータ
700(0)〜700(X)  プレフィックス
702(0)〜702(5)  フラグ
704(0)〜704(2)  パターン
706(0)〜706(4)  非圧縮データ部分
708  オフセット
710(0)〜710(X)  圧縮解除出力ワード
1000  プロセッサベースシステム
1002  CPU
1004  プロセッサ
1006  キャッシュメモリ
1008  システムバス
1012  メモリシステム
1014  入力デバイス
1016  出力デバイス
1018  ネットワークインターフェースデバイス
1020  ディスプレイコントローラ
1022  ネットワーク
1024(0)〜1024(N)  メモリユニット
1026  ディスプレイ
1028  ビデオプロセッサ
【図１】
2019530076.tif 000003
【図２】
2019530076.tif 000004
【図３】
2019530076.tif 000005
【図４】
2019530076.tif 000006
【図５】
2019530076.tif 000007
【図６Ａ】
2019530076.tif 000008
【図６Ｂ】
2019530076.tif 000009
【図６Ｃ】
2019530076.tif 000010
【図６Ｄ】
2019530076.tif 000011
【図６Ｅ】
2019530076.tif 000012
【図７】
2019530076.tif 000013
【図８Ａ】
2019530076.tif 000014
【図８Ｂ】
2019530076.tif 000015
【図８Ｃ】
2019530076.tif 000016
【図８Ｄ】
2019530076.tif 000017
【図９】
2019530076.tif 000018
【図１０】
2019530076.tif 000019
【手続補正書】
【提出日】平成31年3月11日(2019.3.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
圧縮メモリコントローラ(CMC)であって、
複数のマスクおよび関連する複数のプレフィックスを提供するマスクテーブルと、
複数の入力ワードを受信することと、
前記マスクテーブルの前記複数のマスクのマスクごとに、
対応する複数のパターンを生成するために前記複数の入力ワードの各非割当て入力ワードに前記マスクを適用することと、
最頻出パターンが前記複数のパターンの中に存在するかどうかを判断することと、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、
前記マスクに関連する前記複数のプレフィックスのうちのプレフィックスに関連して出力生成回路に、前記最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を出力することと、
前記最頻出パターンに対応する各非割当て入力ワードに、前記マスクに関連する前記プレフィックスを割り当てることと、
前記複数の入力ワードに割り当てられた複数の割当てプレフィックスを前記出力生成回路に出力することと
を行うように構成されたパターン識別回路と、
前記複数の入力ワードに割り当てられた前記複数の割当てプレフィックスと、
前記複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンと、
前記1つまたは複数の最頻出パターンに関連し、1つまたは複数の非割当て入力ワードへの前記マスクの前記適用によってマスクオフされていない前記複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分と
を備える圧縮出力ブロックを生成するように構成された前記出力生成回路と
を備えるCMC。
【請求項２】
前記パターン識別回路は、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するかどうかを判断することと、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するとの判断に応答して、前記0の値を有する前記複数の入力ワードのうちの前記1つまたは複数の入力ワードの各入力ワードに、0値を示す前記複数のプレフィックスのうちのプレフィックスを割り当てることと
を行うようにさらに構成される、請求項1に記載のCMC。
【請求項３】
前記パターン識別回路は、
前記1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するかどうかを判断することと、
前記1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するとの判断に応答して、非圧縮入力ワードを示す前記複数のプレフィックスのうちのプレフィックスに関連して、前記非割当て入力ワードの非圧縮データ部分として前記出力生成回路に、前記1つまたは複数の非割当て入力ワードの各非割当て入力ワードの値を出力することと
を行うようにさらに構成される、請求項1に記載のCMC。
【請求項４】
前記出力生成回路は、前記複数の割当てプレフィックスに対応し、前記圧縮出力ブロックの前記1つまたは複数の最頻出パターンが、前記複数の割当てプレフィックスの対応する割当てプレフィックスに関連する最頻出パターンを含むかどうかを各々が示す、複数のフラグインジケータをさらに備える前記圧縮出力ブロックを生成するように構成される、請求項1に記載のCMC。
【請求項５】
前記出力生成回路は、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいかどうかを判断することと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいとの判断に応答して、メモリアレイに前記圧縮出力ブロックを記憶することと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さくないとの判断に応答して、前記メモリアレイに前記複数の入力ワードを記憶することと
を行うようにさらに構成される、請求項1に記載のCMC。
【請求項６】
前記マスクテーブルの前記複数のマスクの連続するマスクは、縮小するサイズのパターンを生成するように構成される、請求項1に記載のCMC。
【請求項７】
前記パターン識別回路は、前記最頻出パターンが前記複数のパターンの中で少なくとも2回発生すると判断することによって、前記最頻出パターンが前記複数のパターンの中に存在するかどうかを判断するように構成される、請求項1に記載のCMC。
【請求項８】
前記複数のプレフィックスの各々は、3ビットを備え、
前記パターン識別回路は、それぞれサイズが32ビットである、32個の入力ワードを受信することによって、前記複数の入力ワードを受信するように構成される、請求項1に記載のCMC。
【請求項９】
複数のプレフィックスのほか、非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、前記プレフィックスに関連するパターンおよび非圧縮データ部分を備える圧縮入力ブロックを受信することと、
非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、
前記プレフィックスに基づいて、対応する前記非圧縮データ部分へのオフセットを計算することと、
前記オフセットに基づいて、対応する前記非圧縮データ部分を取り出すことと、
前記プレフィックスに対応する前記パターンおよび対応する前記非圧縮データ部分に基づいて、圧縮解除出力ワードを生成することと、
1つまたは複数の圧縮解除出力ワードを備える圧縮解除出力ブロックを生成することと
を行うように構成された圧縮解除回路をさらに備える、請求項1に記載のCMC。
【請求項１０】
集積回路(IC)に組み込まれる、請求項1に記載のCMC。
【請求項１１】
セットトップボックス、エンターテインメントユニット、ナビゲーションデバイス、通信デバイス、固定ロケーションデータユニット、モバイルロケーションデータユニット、モバイルフォン、セルラーフォン、スマートフォン、タブレット、ファブレット、サーバ、コンピュータ、ポータブルコンピュータ、デスクトップコンピュータ、携帯情報端末(PDA)、モニタ、コンピュータモニタ、テレビ、チューナ、ラジオ、衛星ラジオ、音楽プレーヤ、デジタル音楽プレーヤ、ポータブル音楽プレーヤ、デジタルビデオプレーヤ、ビデオプレーヤ、デジタルビデオディスク(DVD)プレーヤ、ポータブルデジタルビデオプレーヤ、および自動車からなる一群から選択されたデバイスに組み込まれる、請求項1に記載のCMC。
【請求項１２】
圧縮メモリコントローラ(CMC)であって、
複数の入力ワードを受信するための手段と、
複数のマスクのマスクごとに、対応する複数のパターンを生成するために前記複数の入力ワードの各非割当て入力ワードに前記マスクを適用するための手段と、
最頻出パターンが前記複数のパターンの中に存在するかどうかを判断するための手段と、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、前記マスクに関連するプレフィックスに関連して、前記最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶するための手段と、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、前記最頻出パターンに対応する各非割当て入力ワードに、前記マスクに関連する前記プレフィックスを割り当てるための手段と、
前記複数の入力ワードに割り当てられた複数の割当てプレフィックスと、
前記複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンと、
1つまたは複数の非割当て入力ワードに前記マスクを適用するための前記手段によってマスクオフされていない前記複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分と
を備える圧縮出力ブロックを生成するための手段と
を備えるCMC。
【請求項１３】
データブロックの効率的なロスレス圧縮を実現するための方法であって、
複数の入力ワードを受信するステップと、
複数のマスクのマスクごとに、
対応する複数のパターンを生成するために前記複数の入力ワードの各非割当て入力ワードに前記マスクを適用するステップと、
最頻出パターンが前記複数のパターンの中に存在するかどうかを判断するステップと、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、
前記マスクに関連するプレフィックスに関連して、前記最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶するステップと、
前記最頻出パターンに対応する各非割当て入力ワードに、前記マスクに関連する前記プレフィックスを割り当てるステップと、
前記複数の入力ワードに割り当てられた複数の割当てプレフィックスと、
前記複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンと、
1つまたは複数の非割当て入力ワードへの前記マスクの前記適用によってマスクオフされていない前記複数の入力ワードの1つまたは複数の対応する入力ワードの1つまたは複数の非圧縮データ部分と
を備える圧縮出力ブロックを生成するステップと
を備える方法。
【請求項１４】
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するかどうかを判断するステップと、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するとの判断に応答して、前記0の値を有する前記複数の入力ワードのうちの前記1つまたは複数の入力ワードの各入力ワードに、0値を示すプレフィックスを割り当てるステップと
をさらに備える、請求項13に記載の方法。
【請求項１５】
前記圧縮出力ブロックを生成する前に、1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するかどうかを判断するステップと、
前記1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するとの判断に応答して、非圧縮入力ワードを示すプレフィックスに関連して、前記非割当て入力ワードの非圧縮データ部分として、前記1つまたは複数の非割当て入力ワードの各非割当て入力ワードの値を記憶するステップと
をさらに備える、請求項13に記載の方法。
【請求項１６】
前記複数の割当てプレフィックスに対応し、前記圧縮出力ブロックの前記1つまたは複数の最頻出パターンが、前記複数の割当てプレフィックスの対応する割当てプレフィックスに関連する最頻出パターンを含むかどうかを各々が示す、複数のフラグインジケータをさらに備える前記圧縮出力ブロックを生成するステップを備える、請求項13に記載の方法。
【請求項１７】
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいかどうかを判断するステップと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいとの判断に応答して、メモリアレイに前記圧縮出力ブロックを記憶するステップと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さくないとの判断に応答して、前記メモリアレイに前記複数の入力ワードを記憶するステップと
をさらに備える、請求項13に記載の方法。
【請求項１８】
前記複数のマスクの連続するマスクは、縮小するサイズのパターンを生成するように構成される、請求項13に記載の方法。
【請求項１９】
前記最頻出パターンが前記複数のパターンの中に存在するかどうかを判断するステップは、前記最頻出パターンが前記複数のパターンの中で少なくとも2回発生すると判断するステップを備える、請求項13に記載の方法。
【請求項２０】
前記複数のプレフィックスの各々は、3ビットを備え、
前記複数の入力ワードは、それぞれサイズが32ビットである、32個の入力ワードを備える、請求項13に記載の方法。
【請求項２１】
複数のプレフィックスのほか、非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、前記プレフィックスに関連するパターンおよび非圧縮データ部分を備える圧縮入力ブロックを受信するステップと、
非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、
前記プレフィックスに基づいて、対応する前記非圧縮データ部分へのオフセットを計算するステップと、
前記オフセットに基づいて、対応する前記非圧縮データ部分を取り出すステップと、
前記プレフィックスに対応する前記パターンおよび対応する前記非圧縮データ部分に基づいて、圧縮解除出力ワードを生成するステップと、
1つまたは複数の圧縮解除出力ワードを備える圧縮解除出力ブロックを生成するステップと
をさらに備える、請求項13に記載の方法。
【請求項２２】
プロセッサによって実行されると、前記プロセッサに、
複数の入力ワードを受信することと、
複数のマスクのマスクごとに、
対応する複数のパターンを生成するために前記複数の入力ワードの各非割当て入力ワードに前記マスクを適用することと、
最頻出パターンが前記複数のパターンの中に存在するかどうかを判断することと、
最頻出パターンが前記複数のパターンの中に存在するとの判断に応答して、
前記マスクに関連するプレフィックスに関連して、前記最頻出パターンおよび各非割当て入力ワードの非圧縮データ部分を記憶することと、
前記最頻出パターンに対応する各非割当て入力ワードに、前記マスクに関連する前記プレフィックスを割り当てることと、
前記複数の入力ワードに割り当てられた複数の割当てプレフィックスと、
前記複数の割当てプレフィックスのうちの1つに各々が関連する、1つまたは複数の最頻出パターンと、
1つまたは複数の非割当て入力ワードへの前記マスクの前記適用によってマスクオフされていない前記複数の入力ワードの対応する1つまたは複数の入力ワードの1つまたは複数の非圧縮データ部分と
を備える圧縮出力ブロックを生成することと
を行わせるコンピュータ実行可能命令を記憶したコンピュータ可読記憶媒体。
【請求項２３】
プロセッサによって実行されると、前記プロセッサに、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するかどうかを判断することと、
前記複数の入力ワードのうちの1つまたは複数の入力ワードが0の値を有するとの判断に応答して、前記0の値を有する前記複数の入力ワードのうちの前記1つまたは複数の入力ワードの各入力ワードに、0値を示すプレフィックスを割り当てることと
をさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２４】
プロセッサによって実行されると、前記プロセッサに、
前記1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するかどうかを判断することと、
1つまたは複数の非割当て入力ワードが前記複数の入力ワード内に存在するとの判断に応答して、非圧縮入力ワードを示すプレフィックスに関連して、前記非割当て入力ワードの非圧縮データ部分として、前記1つまたは複数の非割当て入力ワードの各非割当て入力ワードの値を記憶することと
をさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２５】
プロセッサによって実行されると、前記プロセッサに、前記複数の割当てプレフィックスに対応し、前記圧縮出力ブロックの前記1つまたは複数の最頻出パターンが、前記複数の割当てプレフィックスの対応する割当てプレフィックスに関連する最頻出パターンを含むかどうかを各々が示す、複数のフラグインジケータをさらに備える前記圧縮出力ブロックを生成することをさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２６】
プロセッサによって実行されると、前記プロセッサに、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいかどうかを判断することと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さいとの判断に応答して、メモリアレイに前記圧縮出力ブロックを記憶することと、
前記圧縮出力ブロックのサイズが指定しきい値よりも小さくないとの判断に応答して、前記メモリアレイに前記複数の入力ワードを記憶することと
をさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２７】
プロセッサによって実行されると、前記プロセッサに、前記最頻出パターンが前記複数のパターンの中で少なくとも2回発生すると判断することによって、前記最頻出パターンが前記複数のパターンの中に存在するかどうかを判断することをさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【請求項２８】
プロセッサによって実行されると、前記プロセッサに、
複数のプレフィックスのほか、非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、前記プレフィックスに関連するパターンおよび非圧縮データ部分を備える圧縮入力ブロックを受信することと、
非0入力ワードを表す前記複数のプレフィックスのプレフィックスごとに、
前記プレフィックスに基づいて、対応する前記非圧縮データ部分へのオフセットを計算することと、
前記オフセットに基づいて、対応する前記非圧縮データ部分を取り出すことと、
前記プレフィックスに対応する前記パターンおよび対応する前記非圧縮データ部分に基づいて、圧縮解除出力ワードを生成することと、
1つまたは複数の圧縮解除出力ワードを備える圧縮解除出力ブロックを生成することと
をさらに行わせるコンピュータ実行可能命令を記憶した、請求項22に記載のコンピュータ可読記憶媒体。
【国際調査報告】
2019530076.tif 000020
2019530076.tif 000021
2019530076.tif 000022