12

ハフマンコーディングでエンコードされたデータベースがあります。ここでの目的は、関連するデコーダーを使用して GPU にコピーすることです。次に GPU でデータベースをデコードし、CPU にコピーして戻さずに、このデコードされたデータベースで処理を行います。

私はハフマンの専門家には程遠いですが、私が知っている少数の情報によると、これは本質的に制御構造に基づくアルゴリズムのようです。基本的なアルゴリズムでは、シリアライズされた操作が多くなると思います。

私の2つの質問は次のとおりです。

  • ハフマンコーディング用の効率的な GPU バージョンが存在するかどうか知っていますか?
  • そうでない場合、GPU に適合する (つまり、制御構造が少ない) ハフマン アルゴリズムが存在すると思いますか? または、効率的なハフマン デコードが GPU では効率的でないことを知っている (そして参照を提供できる) かもしれません。

他の制約も見られますが、重要ではありません: - GPU はツリーを処理するのにあまり効率的ではありませんでした: バイナリ ツリーは従来の配列に格納できます - ワークロードのバランスをとるのが難しい場合があります: 後で説明します

4

3 に答える 3

5

ハフマン コーディングの問題点は、早送りできないことです。つまり、ビットごとに線形にデコードする必要があります。

そのため、並列処理には理想的ではありません。

エンコーディングを決定できる場合は、チャンクごとに完全にエンコードして、各チャンクを個別にデコードできるようにすることができます。

于 2010-06-10T15:33:15.327 に答える
2

はい、ハフマンデコードを並行して実行できるため、メモリが問題にならない限り、GPUで利点を得ることができます。

以下の説明では、ハフマンツリーとハフマン出力について説明します。出力は、デコードするためにハフマンツリーで検索する必要がある圧縮されたシンボルです。

ハフマンアルゴリズムでは、デコード用のハフマンツリーが必要です。このツリーは大きくなる可能性があります。GPUのローカルメモリに適合する小さなハフマンツリーを使用することでこれを回避できますが、これはアルゴリズムの圧縮効率に影響します。たとえば、GPUプロセッサで許可されている限り、ツリーを最適な2^nノードに制限できます。（たとえば、1024ノードに制限されたツリーを使用します。

各GPUのローカルストレージに1つのコピーを収めることができるようにハフマンツリーを制限しない場合、すべてのGPUプロセッサが同じ共有ツリーを読み取るすべてのメモリへのアクセスをブロックされるため、期待する並列処理は実際には得られません。

ハフマン出力のシンボルは、可変ビット数でパックされます。出力の途中から始めて、シンボル境界にいるかどうかを知る方法はありません。ただし、独自の境界を作成することはできます。たとえば、出力では、xワードごとにシンボルのアラインメントを強制的にワードアラインメントすることができます。次に、出力内のxワードの任意の倍数でデコードを開始し、そのブロックを適切なツリーとともにGPU処理ノードに送信できることがわかります。

ツリーを1つだけ使用する必要はありませんが、ブロックごとに1つのツリーを使用するのもやり過ぎかもしれません。つまり、ブロックごとに1つのツリーがある場合、ブロックが小さいと、圧縮効率が大幅に低下します。

したがって、ブロックの類似性を調べて、同じツリーで類似のブロックをエンコードし、ブロックごとにツリーインデックスを保存することができます。たとえば、出力に10000ブロックが含まれていても、1024ノードツリーが50個しかない場合があります。次に、1つのブロックと1つのツリーを各GPU処理ノードに送信して、並列にデコードします。

高速化の鍵は、各GPU処理ノードがローカルメモリでのみ機能することです。

于 2012-10-10T21:07:36.560 に答える
1

GPU でのハフマンは不可能であるという明白なコンセンサスに私は驚いています。

私は、「それが起こるなら、それは可能でなければならない」という格言に訴えます。(アガサ・クリスティー、アルバート・アインシュタインなどにさまざまに起因する)

SuperXero はハフマンを GPU 上で行うので、それは可能であるに違いないと思います。

最初の実行後、CPU ハフマン圧縮が速くなりますか? (スーパーゼロ)

Google: GPU ハフマン解凍

于 2012-05-18T19:04:32.137 に答える