(57)【要約】並列ハフマン復号化スキームを実装するシステム、装置及び方法を本明細書に開示する。複数の実行ユニットを含むシステムは、ハフマン符号化ビットストリームを受信する。システムは、符号化ビットストリームを複数のチャンクに分割する。各実行ユニットは、符号化ビットストリームの個別のチャンクと、隣接するチャンクの余分な部分とを復号化するように割り当てられる。このアプローチでは、チャンクの境界がシンボルの境界と揃っていないために、各実行ユニットが、ビットストリームの第１チャンクを復号化する第１実行ユニットを除いて、チャンクの先頭において或る数のシンボルを誤って復号化する可能性が高いことから、ビットストリームの復号化は、各チャンクの境界でプログラム可能な量のデータに対して重複する。システムは、各チャンク境界において復号化された余分な部分から、誤って復号化されたデータが終了する箇所と、正しく復号化されたデータが復号化されたチャンク毎に開始する箇所とを判別する。【選択図】図３
2020526095.tif 000002
【特許請求の範囲】
【請求項１】
複数の実行ユニットと、
メモリと、を備えるシステムであって、
前記システムは、
符号化ビットストリームを複数のチャンクに分割することと、
前記符号化ビットストリームの個別のチャンクと、隣接するチャンクの余分な部分とを、前記複数の実行ユニットの各実行ユニットに割り当てることと、
各実行ユニットによって、前記実行ユニットに割り当てられた前記チャンクと、前記隣接するチャンクの前記余分な部分と、を復号化することであって、前記復号化することは、前記複数の実行ユニットによって並列に実行される、ことと、
復号化された余分な部分の各々から、誤って復号化されたデータが終了する箇所と、正しく復号化されたデータが対応するチャンク内で開始する箇所と、を判別することと、
正しく復号化されたデータを前記メモリに保持し、誤って復号化されたデータを破棄することと、
を行うように構成されている、
システム。
【請求項２】
前記システムは、
前記複数の実行ユニットのうち第１実行ユニットによって復号化するために、前記符号化ビットストリームの第１チャンクと、第２チャンクの余分な部分とを割り当てることであって、前記第１チャンク及び前記第２チャンクは、前記符号化ビットストリームの隣接するチャンクである、ことと、
前記複数の実行ユニットのうち第２実行ユニットによって復号化するために、前記第２チャンクと、第３チャンクの余分な部分とを割り当てることであって、前記第２チャンク及び前記第３チャンクは、前記符号化ビットストリームの隣接するチャンクである、ことと、
復号化された第２チャンクを前記第２チャンクの復号化された余分な部分と比較することによって、誤って復号化されたデータが、復号化された第２チャンク内で終了する箇所を判別することと、
前記第２チャンクの復号化された余分な部分からの１つ以上のシンボルを、前記復号化された第２チャンクからの複数のシンボルと組み合わせることと、
を行うように構成されている、
請求項１のシステム。
【請求項３】
前記複数の実行ユニットのうち最後の実行ユニットを除く各実行ユニットは、
前記符号化ビットストリームの割り当てられたチャンクと、前記隣接するチャンクの前記余分な部分との両方を復号化することと、
前記割り当てられたチャンクの最初のＮ個（Ｎは、正の整数）の復号化されたシンボルと、次のチャンクからのデータの余分な部分の最初のＮ個の復号化されたシンボルと、について、シンボルビットストリーム位置の終端を記録することと、
前記隣接するチャンクの余分な部分のシンボルビットストリーム位置の終端が、前記隣接するチャンクについて隣接する実行ユニットによって復号化されたデータからのシンボルビットストリーム位置の終端と一致する箇所を判別することと、
前記シンボルビットストリーム位置の終端が一致する箇所まで、復号化されたデータを前記メモリ内の所定位置にコピーすることと、
を行うように構成されている、
請求項１のシステム。
【請求項４】
前記システムは、各実行ユニットによって復号化するために、隣接するチャンクの余分な部分のサイズを判別することを行うように構成されている、
請求項１のシステム。
【請求項５】
前記判別することは、ビットストリームが符号化される方法を指定するテーブルを分析することによって実行される、
請求項４のシステム。
【請求項６】
前記符号化ビットストリームは、可変長符号を使用して符号化されている、
請求項１のシステム。
【請求項７】
前記可変長符号は、ハフマン符号である、
請求項６のシステム。
【請求項８】
符号化ビットストリームを複数のチャンクに分割することと、
前記符号化ビットストリームの個別のチャンクと、隣接するチャンクの余分な部分とを、複数の実行ユニットの各実行ユニットに割り当てることと、
各実行ユニットによって、前記実行ユニットに割り当てられた前記チャンクと、前記隣接するチャンクの前記余分な部分と、を復号化することであって、前記復号化することは、前記複数の実行ユニットによって並列に実行される、ことと、
復号化された余分な部分の各々から、誤って復号化されたデータが終了する箇所と、正しく復号化されたデータが対応するチャンク内で開始する箇所と、を判別することと、
正しく復号化されたデータをメモリに保持し、誤って復号化されたデータを破棄することと、を含む、
方法。
【請求項９】
前記複数の実行ユニットのうち第１実行ユニットによって復号化するために、前記符号化ビットストリームの第１チャンクと、第２チャンクの余分な部分とを割り当てることであって、前記第１チャンク及び前記第２チャンクは、前記符号化ビットストリームの隣接するチャンクである、ことと、
前記複数の実行ユニットのうち第２実行ユニットによって復号化するために、前記第２チャンクと、第３チャンクの余分な部分とを割り当てることであって、前記第２チャンク及び前記第３チャンクは、前記符号化ビットストリームの隣接するチャンクである、ことと、
復号化された第２チャンクを前記第２チャンクの復号化された余分な部分と比較することによって、誤って復号化されたデータが、復号化された第２チャンク内で終了する箇所を判別することと、
前記第２チャンクの復号化された余分な部分からの１つ以上のシンボルを、前記復号化された第２チャンクからの複数のシンボルと組み合わせることと、を含む、
請求項８の方法。
【請求項１０】
前記符号化ビットストリームの割り当てられたチャンクと、前記隣接するチャンクの前記余分な部分との両方を復号化することと、
前記割り当てられたチャンクの最初のＮ個（Ｎは、正の整数）の復号化されたシンボルと、次のチャンクからのデータの余分な部分の最初のＮ個の復号化されたシンボルと、について、シンボルビットストリーム位置の終端を記録することと、
前記隣接するチャンクの余分な部分のシンボルビットストリーム位置の終端が、前記隣接するチャンクについて隣接する実行ユニットによって復号化されたデータからのシンボルビットストリーム位置の終端と一致する箇所を判別することと、
前記シンボルビットストリーム位置の終端が一致する箇所まで、復号化されたデータを前記メモリ内の所定位置にコピーすることと、を含む、
請求項９の方法。
【請求項１１】
各実行ユニットによって復号化するために、隣接するチャンクの余分な部分のサイズを判別することを含む、
請求項８の方法。
【請求項１２】
前記判別することは、ビットストリームが符号化される方法を指定するテーブルを分析することによって実行される、
請求項１１の方法。
【請求項１３】
前記符号化ビットストリームは、可変長符号を使用して符号化されている、
請求項８の方法。
【請求項１４】
前記可変長符号は、ハフマン符号である、
請求項１３の方法。
【請求項１５】
コマンドプロセッサと、
複数の実行ユニットと、を備える装置であって、
前記装置は、
符号化ビットストリームを複数のチャンクに分割することと、
前記符号化ビットストリームの個別のチャンクと、隣接するチャンクの余分な部分とを、前記複数の実行ユニットの各実行ユニットに割り当てることと、
各実行ユニットによって、前記実行ユニットに割り当てられた前記チャンクと、前記隣接するチャンクの前記余分な部分と、を復号化することであって、前記復号化することは、前記複数の実行ユニットによって並列に実行される、ことと、
復号化された余分な部分の各々から、誤って復号化されたデータが終了する箇所と、正しく復号化されたデータが対応するチャンク内で開始する箇所と、を判別することと、
正しく復号化されたデータをメモリに保持し、誤って復号化されたデータを破棄することと、
を行うように構成されている、
装置。
【請求項１６】
前記装置は、
前記複数の実行ユニットのうち第１実行ユニットによって復号化するために、前記符号化ビットストリームの第１チャンクと、第２チャンクの余分な部分とを割り当てることであって、前記第１チャンク及び前記第２チャンクは、前記符号化ビットストリームの隣接するチャンクである、ことと、
前記複数の実行ユニットのうち第２実行ユニットによって復号化するために、前記第２チャンクと、第３チャンクの余分な部分とを割り当てることであって、前記第２チャンク及び前記第３チャンクは、前記符号化ビットストリームの隣接するチャンクである、ことと、
復号化された第２チャンクを前記第２チャンクの復号化された余分な部分と比較することによって、誤って復号化されたデータが、復号化された第２チャンク内で終了する箇所を判別することと、
前記第２チャンクの復号化された余分な部分からの１つ以上のシンボルを、前記復号化された第２チャンクからの複数のシンボルと組み合わせることと、
を行うように構成されている、
請求項１５の装置。
【請求項１７】
前記複数の実行ユニットのうち最後の実行ユニットを除く各実行ユニットは、
前記符号化ビットストリームの割り当てられたチャンクと、前記隣接するチャンクの前記余分な部分との両方を復号化することと、
前記割り当てられたチャンクの最初のＮ個（Ｎは、正の整数）の復号化されたシンボルと、次のチャンクからのデータの余分な部分の最初のＮ個の復号化されたシンボルと、について、シンボルビットストリーム位置の終端を記録することと、
前記隣接するチャンクの余分な部分のシンボルビットストリーム位置の終端が、前記隣接するチャンクについて隣接する実行ユニットによって復号化されたデータからのシンボルビットストリーム位置の終端と一致する箇所を判別することと、
前記シンボルビットストリーム位置の終端が一致する箇所まで、復号化されたデータを前記メモリ内の所定位置にコピーすることと、
を行うように構成されている、
請求項１５の装置。
【請求項１８】
前記装置は、各実行ユニットによって復号化するために、隣接するチャンクの余分な部分のサイズを判別することを行うように構成されている、
請求項１５の装置。
【請求項１９】
前記判別することは、ビットストリームが符号化される方法を指定するテーブルを分析することによって実行される、
請求項１８の装置。
【請求項２０】
前記符号化ビットストリームは、可変長符号を使用して符号化されている、
請求項１５の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
（関連技術の説明）
可変長符号化スキームは、多くの異なるコンピューティング及び通信アプリケーションで一般的に使用されている。符号理論では、可変長符号は、ソースシンボルを可変数のビットにマッピングする符号である。可変長符号は、通常、ロスレスデータ圧縮が可能である。可変長符号化スキームの例には、ハフマン符号化、Ｌｅｍｐｅｌ−Ｚｉｖ符号化及び算術符号化が含まれる。ハフマン符号化は、いくつかの映像及び画像圧縮規格で利用されている。可変長符号化スキームは、より一般的なシンボルが、あまり一般的でないシンボルよりも少ない符号化ビットにマッピングされる確率論的手法を利用する。
【０００２】
ハフマン符号化ビットストリームの場合、符号化されたデータビットと復号化されたデータビットとの間には予測不可能な関係がある。これは、頻度の低いシンボルよりも少ないビットで符号化される頻度の高いシンボルによって引き起こされる。この特性により、単純な並列アルゴリズムを使用してハフマンデータを復号化することができない。例えば、ハフマンデータを復号化するための有効な開始位置は、その時点までの全てのデータを復号化することなく、符号化されたデータ内で任意に見つけることができない。したがって、これにより、ハフマン符号化データを復号化するための並列スキームの実装が妨げられている。
【０００３】
本明細書に記載される方法及びメカニズムの利点は、添付の図面と併せて以下の説明を参照することによって、より良く理解することができる。
【図面の簡単な説明】
【０００４】
【図１】コンピューティングシステムの一実施形態のブロック図である。
【図２】ハフマン符号化ストリームを並列に復号化するためのＧＰＵの一実施形態のブロック図である。
【図３】並列ハフマン復号化スキームを実施する一実施形態のブロック図である。
【図４】復号化されたチャンク内のシンボルオフセットの終端の一実施形態を示す図である。
【図５】並列実行ユニットによって生成されたデータの復号化されたチャンクの図である。
【図６】チャンク境界後に無効なデータの終端が発生する箇所を判別する一実施形態の図である。
【図７】複数の実行ユニットで符号化ビットストリームを並列に復号化する方法の一実施形態を示す一般化されたフロー図である。
【図８】符号化ビットストリームの隣接するチャンクを復号化する方法の一実施形態を示す一般化されたフロー図である。
【図９】並列復号化スキームを実施する方法の一実施形態を示す一般化されたフロー図である。
【発明を実施するための形態】
【０００５】
以下の説明では、本明細書に提示される方法及びメカニズムの十分な理解を提供するために、多くの具体的な詳細が述べられている。しかしながら、当業者は、これらの具体的な詳細無しに様々な実施形態を実施可能であることを認識するはずである。場合によっては、本明細書で説明するアプローチを不明瞭にすることを避けるために、周知の構造、コンポーネント、信号、コンピュータプログラム命令及び技術が詳細に示されていない。説明を簡単且つ明確にするために、図に示される要素が必ずしも縮尺通りに描かれていないことを理解されたい。例えば、いくつかの要素の寸法は、他の要素に比べて誇張されている場合がある。
【０００６】
本明細書では、並列ビットストリーム復号化スキームを実施するシステム、装置及び方法を開示する。一実施形態では、システムは、少なくとも複数の実行ユニットと、メモリと、を含む。システムは、符号化ビットストリームを受信するように構成されている。一実施形態では、受信したビットストリームは、可変長符号化スキームを使用して符号化される。例えば、一実施形態では、受信したビットストリームは、ハフマン符号化スキームを使用して符号化される。他の実施形態では、受信したビットストリームは、他のタイプの符号化スキームを使用して符号化される。
【０００７】
システムは、符号化ビットストリームを複数のチャンクに分割する。各実行ユニットは、符号化ビットストリームの個別のチャンクと、隣接するチャンクの余分な部分とを復号化するように割り当てられる。このアプローチでは、チャンクの境界がシンボルの境界と揃っていないために、各実行ユニットが、ビットストリームの第１チャンクを復号化する第１実行ユニットを除いて、チャンクの先頭において或る数のシンボルを誤って復号化する可能性が高いことから、ビットストリームの復号化は、各チャンクの境界でプログラム可能な量のデータに対して重複する。システムは、各チャンクの境界において復号化された余分な部分から、誤って復号化されたデータが終了する箇所と、正しく復号化されたデータが復号化されたチャンク毎に開始する箇所とを判別する。次に、システムは、正しく復号化されたデータをメモリに保持しながら、誤って復号化されたデータを破棄する。本明細書に使用される場合、「シンボル」という用語は、単一ユニットとして処理される１つ以上のビットの集合として定義される。
【０００８】
一実施形態では、最後の実行ユニットを除く、複数の実行ユニットの各実行ユニットは、符号化ビットストリームの割り当てられたチャンクと、隣接するチャンクの余分な部分との両方を復号化するように構成されている。ビットストリームの最後のチャンクを復号化する最後の実行ユニットは、割り当てられたチャンクのみを復号化する。また、各実行ユニットは、割り当てられたチャンクの最初のＮ個（Ｎは、正の整数）のシンボルと、隣接するチャンクからのデータの余分な部分の最初のＮ個のシンボルと、について、シンボルビットストリーム位置の終端を記録する。次に、各実行ユニットは、隣接するチャンクの余分な部分のシンボルビットストリーム位置の終端が、隣接するチャンクについて隣接する実行ユニットによって復号化されたデータからのシンボルビットストリーム位置の終端と一致する箇所を判別する。次いで、各実行ユニットは、シンボルビットストリーム位置の終端が一致する箇所まで、復号化されたデータをメモリ内の所定位置にコピーする。
【０００９】
図１を参照すると、コンピューティングシステム１００の一実施形態のブロック図が示されている。一実施形態では、コンピューティングシステム１００は、システムメモリ１５０と、入出力（Ｉ／Ｏ）インタフェース１２５と、ファブリック１２０と、グラフィックス処理装置（ＧＰＵ）１３０と、ローカルメモリ１１０と、中央処理装置（ＣＰＵ）チップセット１４０と、を含む。システム１００は、図を不明瞭にすることを避けるために、図１に示されていない他のコンポーネントも含むことができる。別の実施形態では、ＧＰＵ１３０は、別のタイプの処理ユニット（例えば、ＣＰＵ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、デジタル信号プロセッサ（ＤＳＰ））であってもよい。
【００１０】
ＧＰＵ１３０は、任意の数及びタイプの計算ユニットを表す計算ユニット１４５Ａ〜１４５Ｎを少なくとも含む。各計算ユニット１４５Ａ〜１４５Ｎは任意の数の実行ユニット１６０Ａ〜１６０Ｎを含み、実行ユニットの数は実施形態毎に異なる。ＧＰＵ１３０は、ファブリック１２０を介してローカルメモリ１１０に接続されている。一実施形態では、ローカルメモリ１１０は、高帯域幅メモリ（ＨＢＭ）を使用して実装される。一実施形態では、ＧＰＵ１３０は、描画コマンド、ピクセル動作、幾何学的計算、及び、画像をディスプレイにレンダリングするための他の動作等のグラフィックスパイプライン動作を実行するように構成されている。別の実施形態では、ＧＰＵ１３０は、グラフィックスに関係のない動作を実行するように構成されている。更なる実施形態では、ＧＰＵ１３０は、グラフィック動作及び非グラフィック関連動作の両方を実行するように構成されている。
【００１１】
一実施形態では、ＧＰＵ１３０は、可変長符号を使用して符号化されたビットストリームの並列復号化スキームを実施するように構成されている。ＧＰＵ１３０は、ビットストリームを複数のチャンクに分割し、各チャンクを、実行ユニット１６０Ａ〜１６０Ｎの異なる実行ユニットに割り当てる。各実行ユニットは、割り当てられたチャンクを復号化し、隣接するチャンクの一部に対する復号化を続行する。チャンク境界は、符号化ビットストリームのシンボル境界と必ずしも一致しないので、各実行ユニット（第１実行ユニットを除く）は、チャンクの始端において或る数のシンボルを誤って復号化する可能性がある。したがって、前の実行ユニットによって復号化されたチャンクの余分な部分が、チャンクの先頭でエラーを訂正するために利用される。復号化されたチャンク（最初のチャンクを除く）毎に、チャンクの先頭において訂正されたデータが、チャンクの残りの部分から正しく復号化されたシンボルの残りと組み合わせられる。次に、この正しく復号化されたデータを、ローカルメモリ１１０、システムメモリ１５０、又は、システム１００内の別の場所（例えば、キャッシュ、ローカルデータ共有）に記憶する。
【００１２】
Ｉ／Ｏインタフェース１２５は、ファブリック１２０に接続されており、任意の数及びタイプのインタフェース（例えば、周辺機器相互接続（ＰＣＩ）バス、ＰＣＩ−Ｅｘｔｅｎｄｅｄ（ＰＣＩ−Ｘ）、ＰＣＩＥ（ＰＣＩ  Ｅｘｐｒｅｓｓ）バス、ギガビットイーサネット（登録商標）（ＧＢＥ）バス、ユニバーサルシリアルバス（ＵＳＢ））を表す。ＧＰＵ１３０は、１つ以上のメモリモジュールを含むシステムメモリ１５０に接続されている。メモリモジュールの各々は、その上に搭載された１つ以上のメモリデバイスを含む。いくつかの実施形態では、システムメモリ１５０は、ＧＰＵ１３０及び／若しくは他のコンポーネントが搭載されるマザーボード又は他のキャリアに搭載される１つ以上のメモリデバイスを含む。一実施形態では、システムメモリ１５０を使用して、動作中にＧＰＵ１３０で使用されるランダムアクセスメモリ（ＲＡＭ）を実装する。実装されるＲＡＭは、静的ＲＡＭ（ＳＲＡＭ）、動的ＲＡＭ（ＤＲＡＭ）、抵抗変化型ＲＡＭ（ＲｅＲＡＭ）、相変化ＲＡＭ（ＰＣＲＡＭ）、又は、他の揮発性若しくは不揮発性ＲＡＭとすることができる。システムメモリ１５０を実装するのに使用されるＤＲＡＭのタイプには、ダブルデータレート（ＤＤＲ）ＤＲＡＭ、ＤＤＲ２  ＤＲＡＭ、ＤＤＲ３  ＤＲＡＭ等が含まれるが、これらに限定されない。
【００１３】
様々な実施形態では、コンピューティングシステム１００は、コンピュータ、ラップトップ、モバイルデバイス、サーバ、又は、様々な他のタイプのコンピューティングシステム若しくはデバイスの何れかであってもよい。コンピューティングシステム１００及び／又はＧＰＵ１３０のコンポーネントの数は、実施形態毎に異なってもよいことに留意されたい。図１に示す数よりも多い又は少ないコンポーネント／サブコンポーネントの各々が存在してもよい。また、コンピューティングシステム１００及び／又はＧＰＵ１３０は、図１に示されていない他のコンポーネントを含んでもよいことに留意されたい。例えば、別の実施形態では、ＧＰＵ１３０は、マルチコアプロセッサを表すことができる。また、他の実施形態では、コンピューティングシステム１００及びＧＰＵ１３０は、図１に示す以外の他の方法で構成されてもよい。
【００１４】
図２を参照すると、ハフマン符号化ビットストリームを並列に復号化するためのＧＰＵ２００の一実施形態のブロック図が示されている。一実施形態では、ＧＰＵ２００は、キャッシュ／メモリ２１５と、コマンドプロセッサ２２０と、計算ユニット２４０Ａ〜２４０Ｎと、を少なくとも含む。ＧＰＵ２００は、図を不明瞭にすることを避けるために示されない他のコンポーネントを含むことができることに留意されたい。キャッシュ／メモリ２１５は、任意の数及びタイプのキャッシュ及び／又はメモリを表す。図２に示すように、キャッシュ／メモリ２１５は、ハフマン符号化ビットストリームを表すハフマン符号化データ２２５を記憶する。一実施形態では、ＧＰＵ２００は、ハフマン符号化データ２２５を別のソースから受信する。別の実施形態では、ＧＰＵ２００は、他のデータを受信し、その後、ハフマン符号化データ２２５を生成するように処理する。
【００１５】
コマンドプロセッサ２２０は、キャッシュ／メモリ２１５及び計算ユニット２４０Ａ〜２４０Ｎに接続されている。計算ユニット２４０Ａ〜２４０Ｎは、任意の数及びタイプの計算ユニットを表す。各計算ユニット２４０Ａ〜２４０Ｎは複数の実行ユニットを含み、実行ユニットの数は実施形態毎に異なる。図２に示されていないが、各計算ユニット２４０Ａ〜２４０Ｎは、データを記憶するための１つ以上のキャッシュ及び／又はバッファを含むことができる。各実行ユニット２４５Ａ〜２４５Ｎは、対応するハフマンデコーダ２５０Ａ〜２５０Ｎを実施するための命令を実行するように構成されている。各ハフマンデコーダ２５０Ａ〜２５０Ｎは、任意の適切なハフマン復号化アルゴリズムを利用することができる。
【００１６】
一実施形態では、コマンドプロセッサ２２０は、ハフマンデコーダカーネル２５０Ａ〜２５０Ｎを呼び出して、実行ユニット２４５Ａ〜２４５Ｎ上でハフマン復号化タスクを並列に実行するように構成されている。一実施形態では、ハフマンデコーダカーネル２５０Ａ〜２５０Ｎを呼び出す前に、所定量のスペースをキャッシュ／メモリ２１５に割り当てる。次に、この割り当てられたスペースは、復号化されたデータの個々の部分を記憶するために、ハフマンデコーダカーネル２５０Ａ〜２５０Ｎによって利用される。コマンドプロセッサ２２０は、ハフマン符号化データ２２５を複数のチャンクに分割するように構成されている。次に、コマンドプロセッサ２２０は、異なるチャンクと、隣接するチャンクの余分な部分と、を実行ユニット２４５Ａ〜２４５Ｎの各実行ユニットに割り当てる。一実施形態では、コマンドプロセッサ２２０は、ハフマン符号化データ２２５の一部を各実行ユニット２４５Ａ〜２４５Ｎに伝達し、並列に復号化する。別の実施形態では、コマンドプロセッサ２２０は、開始位置及びデータ量の指標を各実行ユニット２４５Ａ〜２４５Ｎに伝え、その後、各実行ユニット２４５Ａ〜２４５Ｎは、対応するデータを、キャッシュ／メモリ２１５のハフマン符号化データ２２５から取得する。次に、各実行ユニット２４５Ａ〜２４５Ｎは、他の実行ユニット２４５Ａ〜２４５Ｎと並行に、実行ユニット２４５Ａ〜２４５Ｎに割り当てられたデータを復号化する。各実行ユニット２４５Ａ〜２４５Ｎが、割り当てられたデータとハフマン符号化データ２２５の余分な部分との復号化を終了した後に、実行ユニットは、復号化データを、実行ユニットに以前に割り当てられたキャッシュ／メモリ２１５の特定の領域に書き込む。
【００１７】
一実施形態では、各実行ユニット２４５Ａ〜２４５Ｎは、復号化データをキャッシュ／メモリ２１５に書き込む前に、隣接するチャンクの余分な部分の復号化データを、隣接するチャンクに関して別の実行ユニット２４５Ａ〜２４５Ｎによって生成された復号化データと比較する。ハフマン符号化データ２２５の第１チャンクを復号化する第１実行ユニット以外の各実行ユニット２４５Ａ〜２４５Ｎによって、各チャンクの始端においていくつかのシンボルが誤って復号化される可能性がある。各実行ユニット２４５Ａ〜２４５Ｎは、余分な部分の復号化データを使用して、各チャンクの始端において誤って復号化されたシンボルを訂正することができる。次に、正しく復号化されたデータを、キャッシュ／メモリ２１５内の所定の位置に書き込む。一実施形態では、誤って復号化されたシンボルを訂正するための余分な部分のこの処理が、複数の実行ユニット２４５Ａ〜２４５Ｎによって並列に実行されることに留意されたい。したがって、複数の実行ユニット２４５Ａ〜２４５Ｎは、割り当てられたチャンクと、隣接するチャンクの余分な部分とを並列に復号化した後に、余分な部分と、隣接するチャンクの始端と、を同時に処理して、隣接するチャンクの始端において誤って復号化されたシンボルを訂正する。例えば、一実施形態では、第１実行ユニット２４５Ａが第２チャンクの始端を処理し、第２実行ユニット２４５Ｂが第３チャンクの始端を処理する等のように、全て並列に処理される。或いは、別の実施形態では、第２実行ユニット２４５Ｂが、第１実行ユニット２４５Ａによって復号化された余分なデータを使用して第２チャンクの始端を処理し、第３実行ユニット２４５Ｃが、第２実行ユニット２４５Ｂによって復号化された余分なデータを使用して第３チャンクの始端を処理する等の処理が行われる。
【００１８】
図３を参照すると、ハフマン符号化データの並列復号化を実施する一実施形態のブロック図が示されている。長方形３０５は、ハフマン符号化データの量を表す。ブロックは、任意の量のデータを含むことができ、長方形３０５のデータ量は、実施形態に応じて変化する。一実施形態では、ハフマン符号化データ３０５を復号化するシステムは、ハフマン符号化データ３０５を復号化するのに必要な情報を受信するか、既に有している。一実施形態では、情報は、ハフマン符号を元のデータシンボルにマッピングするテーブルを含む。
【００１９】
ハフマン符号化データ３０５を、複数のより小さなチャンク３１０Ａ〜３１０Ｎに分割することができ、その後、個々のチャンク３１０Ａ〜３１０Ｎを、異なる実行ユニットによって別々に処理することができる。例えば、一実施形態では、各チャンク３１０Ａ〜３１０Ｎを、ＧＰＵの異なる実行ユニット３１５Ａ〜３１５Ｎに割り当てることができる。また、各実行ユニット３１５Ａ〜３１５Ｎは、割り当てられたチャンクのデータを処理した後に、隣接するチャンクのデータからの余分なデータ（ＥＤ）を処理する。しかしながら、最後のチャンク３１０Ｎのデータを処理する実行ユニットは、これが元のハフマン符号化データ３０５からの最後のチャンクのデータであるため、余分なデータをフェッチしない。
【００２０】
一実施形態では、各実行ユニットは、割り当てられたチャンク３１０と余分なデータとを復号化し、復号化されたデータを出力バッファに記憶する。一実施形態では、各実行ユニットは、自身のデータの最初のＮ個のシンボルのシンボルオフセットの終端と、余分なデータの最初のＮ個のシンボルのシンボルオフセットの終端と、を記憶する。Ｎ（Ｎは、正の整数）の値は、実施形態に応じて変更可能であることに留意されたい。また、Ｎの値を、様々な実施形態においてプログラム可能とすることができる。
【００２１】
一実施形態では、各実行ユニットによって処理される余分なデータの量は、実施形態に応じて変更することができる。一実施形態では、各実行ユニットが処理する余分なデータの量を、データ３０５を符号化するのに使用されるハフマン符号の分析に基づいて計算することができる。例えば、特定のハフマン符号化手法が共通のサフィックスを有する多数のシンボルを含む場合、これは、シンボルがチャンク境界の後に直ぐに再整列（realigned）される可能性が高いことを示す。この場合、隣接するチャンクから各実行ユニットによって処理される余分なデータの量は、シンボルを誤って復号化することから正しく復号化することへの移行がチャンク境界の直後に発生する可能性が高いことから、比較的少ない。そうでなければ、データ３０５を符号化するのに使用される特定のハフマン符号が、サフィックスを共有する少数のシンボルを含む場合、シンボルがチャンク境界の後に正しく再整列されるのに時間がかかる可能性が高いことから、隣接するチャンク内の各実行ユニットによって処理される余分なデータ量は、比較的多い。
【００２２】
一実施形態では、実行ユニット３１５Ａ〜３１５Ｎによるチャンク３１０Ａ〜３１０Ｎの並列実行後に、クリーンアップフェーズが実行される。例えば、所定の実行ユニットによって処理された余分なデータが、隣接する実行ユニットによって誤って復号化されたデータの量を訂正するのに十分でない場合、このチャンクのデータを復号化するときに別のパスを実行して、エラーを訂正することができる。
【００２３】
図４を参照すると、チャンク４０５，４１０内のシンボルオフセットの終端の一実施形態のブロック図が示されている。一実施形態では、所定のチャンクのデータと、隣接するチャンクからの余分なデータとを処理した各実行ユニットは、所定のチャンク内の復号化データのシンボルオフセットの最初のＮ個の終端と、隣接するチャンクからの余分なデータのシンボルオフセットの最初のＮ個の終端と、を記憶するように構成されている。記憶されるシンボルオフセットの数Ｎは実施形態毎に異なってもよいことに留意されたい。
【００２４】
次に、シンボルオフセットのこれらのＮ個の終端を利用して、シンボルオフセットの終端の隣接する実行ユニットの記録と比較することによって、所定のチャンクのデータ内で正しく復号化されたデータの開始位置を判別する。次いで、誤って復号化されたデータが破棄され、正しく復号化されたデータは、隣接するチャンクのデータを復号化している実行ユニットによって復号化されたデータ間で調整される。
【００２５】
割り当てられたチャンク４０５は、所定の実行ユニットに割り当てられ、復号化されたハフマン符号化データのチャンクの一例である。余分なデータ４１０は、隣接するチャンクの先頭で文字を正しく復号化していない隣接する実行ユニットを補うのに十分に正しく復号化されたデータを生成するために、隣接するチャンクのデータから取得され、復号化されるデータの例である。シンボルオフセット４２０Ａの終端は、割り当てられたチャンクのデータ４０５の最初に復号化されたシンボルの終端を表し、シンボルオフセット４２０Ｂの終端は、割り当てられたチャンクのデータ４０５の２番目に復号化されたシンボルの終端を表し、シンボルオフセット４２０Ｃの終端は、割り当てられたチャンクのデータ４０５の３番目に復号化されたシンボルの終端を表し、以下同様である。シンボルオフセットの最後に記憶された終端は、割り当てられたチャンクのデータ４０５のＮ番目に復号化されたシンボルの終端を表すシンボルオフセット４２０Ｎの終端として示されている。
【００２６】
同様に、余分なデータ４１０の場合、シンボルオフセット４３０Ａの終端は、余分なデータ４１０の最初に復号化されたシンボルの終端を表し、シンボルオフセット４３０Ｂの終端は、余分なデータ４１０の２番目に復号化されたシンボルの終端を表し、シンボルオフセット４３０Ｃの終端は、余分なデータ４１０の３番目に復号化されたシンボルの終端を表し、以下同様である。余分なデータ４１０のシンボルオフセットの最後に記憶された終端は、シンボルオフセット４２０Ｎの終端として示されている。
【００２７】
一実施形態では、シンボルオフセット４２０Ａ〜４２０Ｎの終端は、チャンクのデータ４０５の先頭からのビット数として記憶される。同様に、シンボルオフセットの終端は、チャンクのデータ４０５の終端（すなわち、次のチャンクのデータの始端）からのビット数として記憶される。一実施形態では、シンボルオフセット４２０Ａ〜４２０Ｎ及び４３０Ａ〜４３０Ｎの終端をテーブルに記憶する。他の実施形態では、シンボルオフセット４２０Ａ〜４２０Ｎ及び４３０Ａ〜４３０Ｎの終端を、後の取得のために、他の位置及び／又は他のタイプの構造に記憶することができる。
【００２８】
図５を参照すると、並列に動作する実行ユニットによって生成された、復号化されたチャンクのデータの図が示されている。復号化されたチャンク５０５Ａは、第１実行ユニットによって生成された復号化データを表し、復号化されたチャンク５０５Ｂは、第２実行ユニットによって生成された復号化データを表し、復号化されたチャンク５０５Ｃは、第３実行ユニットによって生成された復号化データを表し、復号化されたチャンク５０５Ｎは、Ｎ番目の実行ユニットによって生成された復号化データを表す。出力バッファに記憶される他の任意の数の復号化されたチャンクが存在してもよく、この数は、元のハフマン符号化データのサイズ、実行ユニットの数、及び、各実行ユニットによって復号化される異なるチャンクの数に応じて変わる。一実施形態では、データを復号化する各実行ユニットは、復号化データを別々のバッファに記憶する。別の実施形態では、各実行ユニットは、復号化データを、指定されたオフセットで共通バッファに記憶する。一実施形態では、ハフマン復号化カーネルを実行ユニット上で起動する前に、復号化データを記憶するためのバッファが割り当てられる。一実施形態では、復号化データを記憶するために、所定量のメモリ空間が各実行ユニットに割り当てられる。したがって、復号化データが空間内に収まるように所定量のメモリが選択され、その結果、各チャンクの復号化データの後のバッファ内に少量の未使用空間が生じる。
【００２９】
復号化されたチャンク５０５Ａの場合、これが、ハフマン符号化データからの最初のチャンクのデータであるため、復号されたチャンク５０５Ａの始端は、正しく復号されたデータを含む。これは、ハフマン符号化データの始端においてチャンク境界と並ぶシンボル境界に起因する。また、復号化されたチャンク５０５Ａは、隣接するチャンクの一部からの正しく復号化されたデータを含む。また、復号化されたチャンク５０５Ａには、隣接するチャンクの一部から正しく復号化されたデータの終端の後に未使用のバッファ空間の一部が存在する。復号化されたチャンク５０５Ｂ〜５０５Ｎの場合、チャンクの先頭位置が必ずしもシンボル境界にある必要がないため、復号化されたチャンク５０５Ｂの始端は、誤って復号化されたデータの一部を含むことができる。
【００３０】
各チャンク５０５Ｂ〜５０５Ｎ内の或るポイントで、復号化データが適切な配置（alignment）を取り戻し、復号化データは、このポイントにおいて、正しく復号化されたデータに移行する。次に、割り当てられたチャンクのデータの終端において、各チャンク５０５Ｂ〜５０５Ｎ（チャンク５０５Ｎを除く）は、隣接するチャンクからの正しく復号化されたデータの一部を含む。また、未使用バッファ空間のランダムな量を、復号化されたチャンク５０５Ｂ〜５０５Ｎの各々の終端に含むことができる。
【００３１】
図６を参照すると、チャンク境界後に無効なデータの終端が発生する箇所を判別する一実施形態の図が示されている。一実施形態では、復号化プロセスのパート１の間に、各実行ユニットは、他の実行ユニットと並列に、チャンクのデータと、隣接するチャンクからの余分な量のデータと、を復号化する。次に、復号化プロセスのパート２の間に、各実行ユニットが、他の実行ユニットと並列に、復号化された余分な量のデータ内のシンボル位置の終端と一致するシンボル位置の最初の終端について、後続のチャンクのデータの復号化されたデータ（隣接する実行ユニットによって復号化される）を検索する。シンボル位置の一致する終端についてのこの検索が、図６に示されている。
【００３２】
図６において、復号化されたチャンクのデータ６０５が、復号化されたチャンクのデータ６１０の上に示されている。復号化されたチャンクのデータ６０５及び復号化されたチャンクのデータ６１０は、ハフマン符号化データからの２つの隣接するチャンクのデータを２つの異なる実行ユニットによって復号化した結果を表す。チャンク６０５，６１０間の境界後には重複する部分があり、同じデータが各実行ユニットによって別々に復号化される。一実施形態では、チャンクのデータ６０５を復号化した実行ユニットは、復号化されたチャンクのデータ６１０を検索し、シンボル位置の最初に一致する終端を見つける。別の実施形態では、チャンクのデータ６１０を復号化した実行ユニットは、復号化されたチャンクのデータ６０５を検索し、シンボル位置の最初に一致する終端を見つける。或いは、さらなる実施形態では、異なる実行ユニットは、復号化されたチャンクのデータ６０５の終端及び復号化されたチャンク６１０の始端を検索して、シンボル位置の最初に一致する終端を見つける。
【００３３】
したがって、実行ユニットは、チャンク６０５，６１０間の重複部分において、シンボル位置の最初に一致する終端のスポット６１５を見つける。実行ユニットがスポット６１５を見つけると、実行ユニットは、スポット６１５の後に復号化されたチャンク６１０内の全てが正しく復号化されていると仮定することができる。一実施形態では、各実行ユニット（最後のチャンクのデータを復号化する最後の実行ユニット以外）は、このステップを実行して、自身の余分な復号化されたデータ内のスポット（復号化されたデータが、隣接する実行ユニットの復号化されたデータ内の復号化されたシンボルデータと一致し始めるスポット）を見つけるように構成されている。「隣接する」という用語が実行ユニットを説明するのに使用される場合、現在の実行ユニットによって復号化されたデータの直後のデータを復号化する実行ユニットを指すことが理解されるであろう。
【００３４】
一実施形態では、ハフマン復号化プロセスのパート３において、有効なデータを、異なる復号化されたチャンクのデータから再構成する。正しく復号化されたデータ６２０は、ハフマン復号化プロセスのパート３を示しており、この例では、正しく復号化されたデータ６２０は、チャンク６０５から復号化されたデータを、チャンク６１０から正しく復号化されたデータと組み合わせる。また、このプロセスは、隣接するチャンクから正しく復号化されたデータを組み合わせることによって、他のチャンクのデータについても実行することができる。一実施形態では、各実行ユニットは、その有効な復号化されたデータと、必要な復号化された余分なデータ（隣接する実行ユニットが有効な復号化されたデータを生成し始めるスポットまで）と、を出力バッファ内の正しい位置にコピーする。各実行ユニットがその有効な復号化されたデータを出力バッファにコピーした後に、訂正ハフマン復号化データの全体が利用可能になる。
【００３５】
図７を参照すると、複数の実行ユニット符号化ビットストリームを並列に復号化する方法７００の一実施形態が示されている。説明のために、本実施形態のステップ及び図８〜図１０のステップを順番に示す。しかしながら、記載された方法の様々な実施形態では、記載された要素のうち１つ以上の要素を同時に実行してもよいし、示された順序と異なる順序で実行してもよいし、完全に省略してもよいことに留意されたい。他の追加の要素が必要に応じて実行されてもよい。本明細書に記載される様々なシステム及び装置の何れかは、方法７００を実施するように構成されている。
【００３６】
複数の実行ユニットを備えるコンピューティングシステムによって、符号化ビットストリームを受信する（ブロック７０５）。一実施形態では、ビットストリームは、可変長符号を使用して符号化される。一実施形態では、ビットストリームは、ハフマン符号を使用して符号化される。説明のために、システムは、ビットストリームを復号化する方法を指定する符号化テーブルを既に有しているか受信するものと仮定する。システムは、符号化ビットストリームを複数のチャンクに分割する（ブロック７１０）。一実施形態では、符号化ビットストリームは、複数の等しいサイズのチャンクに分割される。これらのチャンクは、シンボル境界に揃えられていないことに留意されたい。次に、システムは、複数の実行ユニットの各実行ユニットによって復号化するために、符号化ビットストリームのチャンクと、隣接するチャンクの余分な部分と、の両方を割り当てる（ブロック７１５）。次いで、各実行ユニットは、割り当てられたチャンクと、隣接するチャンクの余分な部分と、の両方を復号化する（ブロック７２０）。
【００３７】
次に、システムは、復号化された余分な部分から、復号化されたチャンク（最初に復号化されたチャンクを除く）毎に、誤って復号化されたデータが終了する箇所と、正しく復号化されたデータが開始する箇所とを判別する（ブロック７２５）。ブロック７２０，７２５は、複数の実行ユニットによって並列に実行することができることに留意されたい。例えば、一実施形態では、複数の実行ユニットは、ブロック７２０，７２５を実行するために、同じ命令を同時に実行する。また、チャンク境界が符号化ビットストリームの始端においてシンボル境界と一致するので、ブロック７２５は、最初に復号化されたチャンクに適用されないことに留意されたい。次に、システムは、正しく復号化されたデータを保持し、誤って復号化されたデータを破棄する（ブロック７３０）。ブロック７３０の後に、方法７００は終了する。
【００３８】
一実施形態では、システムは、単一のパスを利用して、ビットストリームを復号化する。この実施形態では、システムは、実行ユニット毎に単一のチャンクが存在するように、符号化ビットストリームを複数のチャンクに分割する。例えば、システムは、６４個の実行ユニットを含む場合に、符号化ビットストリームを６４個のチャンクに分割した後に、異なるチャンク（及び、隣接するチャンクからの余分な部分）を各実行ユニットに割り当てる。別の実施形態では、システムは、複数のパスを利用して、ビットストリームを復号化する。例えば、システムは、１２８個の実行ユニットを含む場合に、符号化ビットストリームを１２８の整数倍に分割した後に、各パスの間に、１２８のチャンクのセットから所定のチャンク（及び、隣接するチャンクからの余分な部分）を各実行ユニットに割り当てる。実行ユニットが最初のセットを終了すると、システムは、次のパスを開始して、次の１２８のチャンクのセットを復号化する。このプロセスは、ビットストリームの全てのチャンクが復号化されるまで継続することができる。
【００３９】
図８を参照すると、符号化ビットストリームの隣接するチャンクを復号化する方法８００の一実施形態が示されている。符号化ビットストリームの第１チャンクと、第２チャンクの余分な部分とは、復号化するために複数の実行ユニットのうち第１実行ユニットに割り当てられ、第１チャンク及び第２チャンクは、符号化ビットストリームの隣接するチャンクである（ブロック８０５）。第１実行ユニットに割り当てられる第２チャンクの余分な部分は、第２チャンクの先頭から来ることに留意されたい。換言すれば、第１実行ユニットは、第２チャンクの余分な部分について、第１チャンクと第２チャンクとの境界に達した後に復号化を継続する。一実施形態では、符号化ビットストリームは、ハフマン符号化ビットストリームである。また、復号化ビットストリームの第２チャンクと、第３チャンクの余分な部分とは、復号化するために複数の実行ユニットのうち第２実行ユニットに割り当てられ、第２チャンク及び第３チャンクは、符号化ビットストリームの隣接するチャンクである（ブロック８１０）。
【００４０】
次に、第１実行ユニット及び第２実行ユニットは、割り当てられたチャンクと、隣接するチャンクの余分な部分と、を復号化する（ブロック８１５）。また、任意の数の追加の実行ユニットが、割り当てられたチャンクと、隣接するチャンクの余分な部分とを、第１実行ユニット及び第２実行ユニットと並列に復号化することができることに留意されたい。次いで、システムは、第２実行ユニットによって復号化された第２チャンクを、第１実行ユニットによって復号化された第２チャンクの余分な部分と比較することによって、誤って復号化されたデータが第２実行ユニットによって復号化された第２チャンク内で終了する箇所を判別する（ブロック８２０）。一実施形態では、ブロック８２０は、第１実行ユニットによって実行される。他の実行ユニットが、ブロック８２０と同様のステップを並列に実行して、復号化された余分な部分に基づいて、誤って復号化されたデータが隣接するチャンク内で終了する箇所を判別することができることに留意されたい。
【００４１】
次に、システムは、第１実行ユニットによって復号化された第２チャンクの余分な部分からの１つ以上のシンボルを、第２実行ユニットによって復号化された第２チャンクからの複数のシンボルと組み合わせて、当該シンボルの組み合わせを、復号化された第２チャンクとして記憶する（ブロック８２５）。また、システムは、第２実行ユニットによって復号化された第２チャンクから誤って復号化されたシンボルを破棄する（ブロック８３０）。ブロック８３０の後に、方法８００は終了する。第１実行ユニット及び第２実行ユニットによって実行される方法８００と並列に、他の実行ユニットによって方法８００が実行されてもよいことに留意されたい。
【００４２】
図９を参照すると、並列復号化スキームを実施する方法９００の一実施形態が示されている。複数の実行ユニットの各実行ユニットは、割り当てられたチャンクと、符号化ビットストリームの次のチャンクの余分な部分と、を復号化する（ブロック９０５）。次に、各実行ユニットは、割り当てられたチャンクの最初のＮ（Ｎは、正の整数である）個の復号化されたシンボルと、次のチャンクからのデータの余分な部分の最初のＮ個の復号化されたシンボルとについて、シンボルビットストリーム位置の終端を記憶する（ブロック９１０）。
【００４３】
次に、各実行ユニットは、次のチャンクの余分な部分のシンボルビットストリーム位置の終端が、次のチャンクを担当する実行ユニットによって復号化されたデータからのシンボルビットストリーム位置の終端と一致する位置を判別する（ブロック９１５）。次いで、各実行ユニットは、シンボルビットストリーム位置の終端が一致する位置まで、復号化されたデータをメモリ内の所定位置にコピーする（ブロック９２０）。ブロック９２０の後に、方法９００は終了する。「各実行ユニット」という語句は、方法９００で使用される場合、最後の実行ユニット（すなわち、符号化ビットストリームの最後のチャンクを復号化する実行ユニット）を除く各実行ユニットを意味することを理解されたい。復号化ビットストリームの最後のチャンクを復号化する実行ユニットは、最後のチャンクの終端が符号化ビットストリームの終端であるため、隣接するチャンクからの余分なデータを復号化しない。
【００４４】
様々な実施形態では、ソフトウェアアプリケーションのプログラム命令を使用して、上述した方法及び／又はメカニズムを実施する。プログラム命令は、Ｃ言語等の高水準プログラミング言語でハードウェアの挙動を記述する。或いは、Ｖｅｒｉｌｏｇ等のハードウェア設計言語（ＨＤＬ）が使用される。プログラム命令は、非一時的なコンピュータ可読記憶媒体に記憶される。複数のタイプの記憶媒体が利用可能である。記憶媒体は、プログラム命令及び付随するデータを、プログラム実行のためにコンピューティングシステムに提供するために、使用中にコンピューティングシステムによってアクセス可能である。コンピューティングシステムは、少なくとも１つ以上のメモリと、プログラム命令を実行するように構成された１つ以上のプロセッサと、を備える。
【００４５】
上述した実施形態は、実装の非限定的な例に過ぎないことを強調しておきたい。上記の開示が十分に理解されると、多くの変形及び修正が当業者に明らかになるであろう。以下の特許請求の範囲は、このような全ての変形及び修正を包含するように解釈されることを意図している。
【図１】
2020526095.tif 000003
【図２】
2020526095.tif 000004
【図３】
2020526095.tif 000005
【図４】
2020526095.tif 000006
【図５】
2020526095.tif 000007
【図６】
2020526095.tif 000008
【図７】
2020526095.tif 000009
【図８】
2020526095.tif 000010
【図９】
2020526095.tif 000011
【国際調査報告】
2020526095.tif 000012
2020526095.tif 000013