PivCo-Huffman：新しい論文と並列化戦略について

最近、「PivCo-Huffman」と題された新しい論文が発表されました（HTML 版と注釈付き資料はこちら）。非常に興味深い内容です。

ハフマン復号化の並列性の課題

通常のハフマン復号化は、本質的に並列処理に不向きです。

• 限定的な並列性: 複数のストリームを利用することで並列性を導入することは可能ですが、**中程度のストリーム数（4〜8）**でしか問題ありません。
• 広帯域マシンへの非適応: ベクトル化や GPU などのアーキテクチャには向いていません。
  • シグナリングオーバーヘッド: ストリームごとに発生し、効率的ではありません。
  • Gather（散在データ読み出し）の多さ: 多数のストリームからの復号は「gather」操作が多く、メモリアクセスが不連続です。CPU や GPU はこれにより多くのサイクルを消費します。

既存のアプローチと制限

• カノニカル符号の利用: テーブルベースの復号器から「長さ決定」を除けば、簡素な復号が可能です。しかし、スカラー（一度に 1 つ処理）方式では魅力がありません。
• ベクトル化による回避: 単一のロード命令で多数の整数演算を行うことで gather を回避できますが、ハードウェア依存적입니다。
  • GDeflate とインターリーブ: 多数の論理ストリームを物理ストリームに圧縮しますが、「マジックナンバー（インターリーブ係数）」を選定する必要があります。
    • GPU/AVX-512: 最小ストリーム数は約 32。
    • スカラー/狭窄ベクトル: 最大処理可能なストリーム数は 8〜16。
  • ギャップ問題: 「16」と「32」の間の領域は「誰も幸せにならない」性能低下ゾーンです。ハードウェアの進化（AVX-512→SSE2 など）により、最適なマジックナンバーが頻繁に変動するため、柔軟なアルゴリズム開発が困難でした。

PivCo-Huffman の概要

PivCo-Huffman は、従来の並列性のジレンマを解決する新しいアプローチです。

• 概念的な転換: 文字列全体を一度に処理し、ハフマン木の上からゆっくり「押し進める」スタイル。
  • 符号化: ルートノードから各シンボルに対応するビット（左子なら

    0

    、右子なら

    1

    ）を出力します。
  • 復号化プロセス:
    1. ルートノードのビット列（0 と 1 の数）から、左部分木と右部分木のシンボル数を算出。
    2. 再帰的に各部分木に対して同じ処理を行う。
    3. ボトムアップでマージし、元の文字列を復元する。
• 本質: ハフマン符号化を「順序保持リスト分割」に変換し、復号化を**「リストマージ（Merge）のシーケンス」**に置き換えました。
  • 通常は直次的なプロセスでしたが、リストマージは**並列アルゴリズム（前項和など）**と等価です。
  • ハードウェア依存のマジックナンバーを選定する必要がなくなり、スケーラビリティが高まりました。

マージ（Merge）操作の実装戦略

PivCo-Huffman の核心は、マージ操作を高速化することにあります。以下にその手法を整理します。

基本的なアルゴリズム

def merge(l_list, r_list, bitstream):
    output = []
    l_pos, r_pos = 0, 0
    for bit in bitstream:
        if bit == 0:
            output.append(l_list[l_pos])
            l_pos += 1
        else:
            output.append(r_list[r_pos])
            r_pos += 1
    return output

• 不変式: $l_pos + r_pos =$ 以前処理された要素数。
• 並列化への挑戦: シンプルすぎるため、真の高速化のために低レベルな最適化（SIMD 指令）が必要です。

AVX-512 の対応

AVX-512_VBMI2（特に

VPEXPANDB

）は、マスキードロードを提供するため理想的です。

• 非アクティブレーンの処理: ゼロ初期化して無視し、必要なデータだけをベクトルレジスタにロード。
• 実装の注意点: 実際の

  -prefix summing

  は明示的に現れませんが、

  VPEXPANDB

  が内部で計算します。

SSE4.2 / ARM NEON 向け最適化（8 バイト単位）

AVX-512 を持たない環境での実用的なアプローチです。TBL（ARM）またはPSHUFB（x86）を利用し、事前に計算したテーブルルックアップを行います。

• テーブルのサイズ: 256 通り（8 ビットパターン）× 8 バイト = 2KiB。これは L1 キャッシュに収まります。
• 動作原理:
  1. ビットストリームから 1 バイトを読み込み、インデックスベクトルテーブルを検索。

  2. l_list

     と

     r_list

     から各 8 バイトを推測的に読み取る。
  3. シャッフル操作で結果を生成し、出力バッファに格納。
  4. ポピュレーションカウント（1 の数）からポインタを進める量を算出。

void merge(uint8* output, const uint8* l_list, const uint8* r_list, const uint8* bits, usize count) {
    for (usize i = 0; i < count; i += 8) {
        uint8 in_bits = bits[i / 8];
        // インデックステーブルからの事前計算結果を読み込む
        uint8x16 index_vec = index_vec_table[in_bits]; 
        
        // 次の 8 バイトを両リストから読み出す
        uint8x8 l_bytes = vload64(l_list);
        uint8x8 r_bytes = vload64(r_list);
        
        // 結合（128 ビットベクトル）とシャッフル
        uint8x16 lr_bytes = vcombine(l_bytes, r_bytes);
        uint8x16 result = vshuffle(lr_bytes, index_vec);
        
        // 結果を出力バッファへ格納
        vstore(&output[i], result);

        // ポインタを進める計算 (popcount)
        usize npop = popcount(in_bits);
        r_list += npop;
        l_list += 8 - npop;
    }
}

SSE4.2 / ARM NEON 向け最適化（16 バイト単位）

より大きな処理単位へ拡張すると、テーブルのサイズが 1MiB となり L1 キャッシュから外れるためパフォーマンスが低下します。より複雑なロジックで 6KiB のテーブルで対応可能です。

• 問題点: 16 バイト処理するには、後半分のインデックスを調整する必要があります（前半の処理量に応じたシフト）。
• 解決策: 「combine」操作を避け、適切なオフセットを持つ 2 つの独立したインデックスベクトルを使用します。

void merge(uint8* output, const uint8* l_list, const uint8* r_list, const uint8* bits, usize count) {
    for (usize i = 0; i < count; i += 16) {
        // 2 バイト分を読み込み（高バイトと低バイトを区別）
        uint16 in_bits = read16LE(&bits[i / 8]);
        
        // 2 つのテーブルルックアップ（前半用と後半用）
        uint8x16 index0 = index_vec_tab0[in_bits & 0xff];
        uint8x8 index1 = index_vec_tab1[in_bits >> 8];
        uint8x16 index1_wide = vcombine(vzero_uint8x8(), index1);
        
        // オフセット調整後の最終インデックス
        uint8x16 index_vec = vadd(index0, index1_wide);

        // 次の 16 バイトを両リストから読み出す
        uint8x16 l_bytes = vload128(l_list);
        uint8x16 r_bytes = vload128(r_list);
        
        // シャッフル処理（一方は MSB を設定してマスク）
        uint8x16 r_result = vshuffle(r_bytes, index_vec);
        uint8x16 l_result = vshuffle(l_bytes, vnot(index_vec));
        uint8x16 result = vor(r_result, l_result);
        
        // 出力バッファに格納
        vstore(&output[i], result);

        // ポインタを進める計算
        usize npop = popcount(in_bits);
        r_list += npop;
        l_list += 16 - npop;
    }
}

• テーブルサイズ: 約 6KiB。L1 キャッシュ内に収まり、パフォーマンスを保証します。

NEON への特別対応（Optimal Approach）

ARM NEON 環境では、符号付き値の差計算命令を利用することでさらに最適化できます。

    // インデックスベクトルをロード (int8x16)
    int8x16_t index0 = vld1q_s8(index_vec_tab0[in_bits & 0xff]);
    int8x16_t index1 = vld1q_s8(index_vec_tab1[in_bits >> 8]);

    // 足算を行い、絶対値（符号なし）に変換
    uint8x16_t index_vec = vreinterpretq_u8_s8(vabdq_s8(index0, index1));

    // ソースデータをロード (uint8x16x2)
    uint8x16x2_t src;
    src.val[0] = vld1q_u8(r_list);
    src.val[1] = vld1q_u8(l_list);

    // シャッフルと格納
    uint8x16_t result = vqtbl2q_u8(src, index_vec);
    vst1q_u8(dest, result);

• このアプローチは、ロード・シャッフル・ストアを最小限に抑えつつ、テーブルルックアップのオーバーヘッドも効率的に行うため、**NEON 環境では事実上の最適解（Optimal）**となります。

まとめと展望

• スカラー実装: PivCo-Huffman 自体は面白いですが、単なる蛮力処理に留まる可能性があります。
• データ並列サブストレートへの適合性: このアプローチは GPU や SIMD ベクトル指令セット（AVX-512, AVX2, NEON など）との相性が極めて良いため、GPU や高機能な CPU サーバーで特に効果的です。
• 将来性: ハフマン復号化をリストマージ問題に変換したことはアルゴリズム進化の大きな一歩ですが、ワイヤフォーマット（デコード効率）は低エンドデバイスのユーザーにも適応できる必要があります。基本的なプリミティブを安価に実装し、幅広いハードウェアで動作させることが今後の課題です。

論文で報告された数値は鼓舞的ですが、主な成果は高性能サーバーや Apple Silicon 環境でのものです。ワイヤフォーマットが低消費電力デバイスでも効率的になるためには、さらに研究が必要です。