PivCo-Huffman「マージ」操作

コンテンツをスキップする フォロー：RSS Twitter rygブログ 大人になったら発明家になるんだ。 ホーム 概要 コーディング 圧縮 コンピュータアーキテクチャ デモシーン グラフィックパイプライン 数学 マルチメディア ネットワーキング 論文 物語 思考 未分類 PivCo-Huffman「マージ」操作 2026年6月21日 「PivCo-Huffman」という新しい論文（注釈付きHTML版はこちら）が発表され、非常に興味深い内容です。 通常のハフマン復号（そして、程度は低いですが符号化も）は、本質的に非常にシリアルです。複数のストリームを使用することで明示的な並列処理が可能になり、中程度の数のストリーム（4〜8程度）には問題なくスケールします。しかし、GPUのようなベクトル化や広幅ベクトルマシンにはあまり適していません。追加のストリームごとにビットストリームにシグナリングオーバーヘッドが加わり、多くのストリームから一度に復号することはギャザー（散在したデータアクセス）が重い操作になるためです。GPUはギャザーをある程度処理できますが（ただし、散在したデータアクセスはよりコンパクトなメモリアクセスパターンよりも多くのサイクルを消費します）、それ以外のほとんどのものは極端にギャザーが重いパターンには非常に不満を抱きます。特に、通常のテーブルベースのデコーダーはすぐに別のギャザーを伴うためですが、その部分はより簡単に修正できます。カノニカルコードは、必要であれば（少なくとも重要な「長さ決定」部分に関して）比較的簡単なテーブルレス復号を可能にします。これらのアプローチは、単一のロードが非常に安価なスカラーの逐次デコーダーでは特に魅力的ではありませんが、32幅のベクトルで作業している場合、ギャザーを節約する一連の整数演算を行うことはより興味深い提案となります。 また、ANSスタイルのインターリービングを使用して、複数の論理ビットストリームを単一の物理ビットストリームに変換することもできます。これはGDeflateが、あらゆる場所からギャザーすることなく、より多くの並列処理の可能性を持つビットストリームを得るために行っていることです。インターリービングは「メモリ全体に散らばった読み出し」問題を解決し、適切な機能を提供するGPUやCPU（例：AVX-512の「EXPAND」ファミリー命令、または同じキャッシュラインからの高速ギャザー）で非常にうまく機能しますが、そのようなハードウェアサポートがない場合は遅くなります。また、ビットストリーム定義の一部としてマジックナンバー（インターリーブファクター）を選択することを強制されます。低すぎると、GPUのような広幅ベクトルマシンはデコード時の利用率が悪くなります。高すぎると、スカラーマシンはビットストリームを効率的にデコードできなくなります。さらに悪いことに、AVX-512やGPUにちょうど良い数値は重なるものの、ほとんどのGPUやAVX-512のようなCPUがまともな利用率を得られるインターリーブストリームの最小数は約32であり、典型的なレジスタ数を持つスカラーまたは狭幅ベクトルマシンが快適にデコードできる最大数は8〜16（やり方によって異なります）であり、16から32の間は誰も満足しない「涙の谷」です。これが、GDeflate以外ではこのスタイルのビットストリームがあまり見られない理由です。それは、すべての実装に大きな影響を与え、しかも常に変化するハードウェアの詳細に左右されるマジックナンバーの選択に本質的に依存しているからです。確かに、NVIDIA GPUは、長らく32ビット/レジスタを使用する32の「スレッド」（むしろSIMDレーン）を持つワープを中心に構築されてきましたが、AMDは以前は64を好み（数世代前にほとんど32に切り替えましたが）、Intel GPUは8を中心に設計され、一部のモバイルGPUは4しか持たないものもありました。また、ARM NEONやx86側のSSE4.2のようなものでは4つの32ビットレーンがあり、AVX2で8に拡張されました。最後に、ARM SVEとRISC-V V拡張は実装定義としていますが、SAXPYのような単純なベクトル数学カーネルを実行するモデルであれば問題ありませんが、物理的なベクトル幅が、場合によっては何十年も続く永続的なワイヤーフォーマットに焼き付けられたマジック定数になる場合は、全く別の話です。 「これは非常にシリアルだ」という難問に対する最後の主要な人気のある解決策は、完全にブルートフォースで解決することです。入力から多数のビットをフェッチします。並列に、ビット0、ビット1、ビット2、3などからデコードを開始します。これを多くの連続する候補位置で行います。16以上といった数です。最終的に、ビット0から始まるコードが6ビット長であることが判明します。素晴らしい！これは、ビットオフセット1から6までに行ったすべての作業を破棄し、すでに事前にデコードされたビット6から始まるコードが何であったかを見ることを意味します。それは5ビット長なので、ビット7から10までに行った投機的な作業を破棄し、ビット11から始まる別のコードが5ビット長であることがわかります。おめでとうございます、16のコストで3つの値をデコードしました。これはうまく機能します。信じられないかもしれませんが、1サイクルあたり1つ以上のスループットが必要な場合、これは実際にハードウェアでこのようなシーケンシャルビットストリームをデコードするための推奨される方法です。特にカノニカルコードと過度に大きくない長さ制限の場合、これは合理的に安価に実現できます。最終的に出力する実際の値のシーケンスを追いかけることは潜在的なスケーラビリティの問題ですが、一度に3つか4つであればそれほど悪くなく、それが十分でない場合は、さらに並列性をもたらすこれらのリンクを追いかけるより良いアルゴリズムがあります。要するに、これは可能であり、専用ハードウェアを構築すれば悪くはありませんが、汎用ハードウェアでソフトウェアとして行いたいものではありません。私は好奇心からこれを実装しましたが、GPUでさえ、行われた作業の80%以上を日常的に捨てることは高速なコードの秘訣ではなく、電力制約のあるバッテリー駆動デバイスでこのようなことを試みた場合の無駄なエネルギーについては言うまでもありません。 これまでのところ、主な選択肢は次の通りでした。一度に1つずつシーケンシャルにデコードできますが、これはスケールしません。複数の独立したビットストリームを使用できます。これは理論的にはスレッドレベルまたは命令レベルの並列処理のようなものを提供しますが、その並列処理の量はビットストリームに組み込まれており、ある程度のオーバーヘッドが追加されます（各デコーダスレッドがどこから開始すべきかを知る必要があるため）。また、メモリアクセスパターンが異なるため、SIMDスタイルの実装には適していません。インターリーブされたビットストリームを使用することもできます。これはメモリ参照の局所性がはるかに高く、原則としてSIMDおよびGPUアーキテクチャに適合しますが、ビットストリームの仕様時にマジックナンバーを選択する必要があり、それがデコーダの並列処理量を永遠に制限するだけでなく、選択した数値が高すぎてターゲットハードウェアの一部がレジスタを使い果たした場合、私たちの状況を台無しにします。そして、同じ種類のデバイス（例えばGPU）内であっても、その数値がどうあるべきかについて合意のようなものはありません。最後に、私たちは肩をすくめ、極めて無駄な方法で、行った作業のほとんどをすぐに破棄することもできます。これは確かに並列処理ですが、作業効率が良いとは言えません。 PivCoの登場です。 Marcin Żukowskiの「Pivco-Huffman」は、これを文字通り逆転させます。本稿の核心に迫るため、ここでは手早く説明し、詳細は論文を参照してください。 具体的に、「abracadabra」という文字列を符号化したいとします。標準的なハフマン木を構築すると（ここでは説明しない教科書的なアルゴリズムです）、次のような図が得られます。 「abracadabra」のハフマン木 通常、どの記号を符号化する場合でも、ルートから開始し、木の適切な葉に到達するために必要なエッジのラベルを送信します。「a」はこの木では「0」として符号化され、「b」は「100」、rは「101」などとなります。次の記号に進む前に、各記号を完全に送信します。 PivCo-Huffmanは、代わりに概念的に文字列全体を一度に処理し、それをゆっくりと木の下に押し下げます。ルートノードから開始すると、「a」を含むすべての位置が「0」を送信し、それ以外のすべてが「1」を送信していることがわかります。文字列を並べると、ルートノードに対してどのようなビットが出力されるかを見ることができます。 abracadabra 01101010110 これらのビットは直接出力ビットストリームに入ります。ルートノードの左側のサブツリーは「a」の葉だけなので、「0」を送信したすべての位置は実質的に完了です。しかし、「a」ではなかった位置はまだ完了していません。これをさらに見ていきましょう。