ブログを書くことにしたものの、あまりにも日常の話しかないので、たまに技術的なことも書こうと思います。 なかなか仕事終わりには時間が取れないので、そこまで深い話は書けない前提ではあります。 ほとんど自分用のメモ書きです。
最近個人的な興味で圧縮アルゴリズムを多少勉強していて、その中で GDeflate というアルゴリズム & 圧縮形式について知りました。 GDeflateのベースとしてはDeflateというアルゴリズムが前提知識になっていて、これはLZ77（正確にはLZSS）というランレングスの強化版のようなアルゴリズムで 繰り返し部分を圧縮した後、ハフマン符号による符号化を行ってビット列に変換して圧縮します。 Deflateは数十年前から広く使われている圧縮アルゴリズムで、libdeflate といったガチガチにチューニングされた実装もあります。
Deflateのような圧縮アルゴリズムの難点として、伸長（デコード）の並列化が難しいという点があります。 そこでビット列（ビットストリーム）をサブストリームに分割して並び替える (swizzle) ことで、 サブストリームごとにデコードできるようにするのが特徴です。 そこで例として図が出てくるのですが、これを見ても当初は全然意味が分かりませんでした。
(引用元: https://docs.nvidia.com/cuda/nvcomp/gdeflate.html)
この例では圧縮されたビット列 (swizzled gdeflate block) からどのようにデコード結果 (output stream) が出力されるかを示しています。 ここで書いてあるT0, T1, …というのがスレッドを意味していて、同じスレッドが書いてあるところが逐次に処理されていくイメージです。 この例だとスレッドは4つあって、まずそれぞれがswizzled gdeflate blockの最初の左4つの要素を読んで、自分の状態とします。 この図だと最初が 1101011 となってますが、図に書かれていないだけで 4 B (byte) = 32 bits ある前提です。 つまり、各スレッドは最初に 32 bit ずつ読み込みます。
ここからがポイントで、各スレッドが下位ビット側の可変長符号を一つデコードして、デコード結果をスレッド番号順に最終的な出力列に並べていきます。 これで 1 ターン目、図中だと output stream の group 1 のデコードされた列ができあがります。 各スレッドは 32 bit の値から一部を符号として消費するので、右シフトして次の符号を処理できるようにします。 ここで、各スレッドは 32 bit 未満しかビット列が残っていない時、次の 32 bit を自分の状態（上位ビット）に付け加えます。 そして次の group 2 を処理して、と繰り返す形です。 可変長ビット列なので自分の状態に 32 bit 以上残っていることもありえて、その際は例えば3回目（黄色）の時のT0, T1, T3のように読み出さないこともあります。 次の 32 bit を読み出すかを決めるのはその時の各スレッドの状態にある残りのビット数なので、これは一意に決まるという仕組みです。
group 1 では 4 スレッドそれぞれに符号が割り当てられていますが、group 2 では 2 スレッドにしか割り当てられていません。 これは LZ77 の繰り返し符号 (length+distance) が出てきた時は次の group で符号を割り当てないという仕組みにしているからのようです。 これもデコード時には直前の符号が literal か length+distance かで読み出すかどうかを一意に決定できます。
このような形で、あまり説明になっていないかもしれませんが、 並列で符号をデコードできるようにあらかじめ並び替えて圧縮する仕組みであることが理解できました。 データ形式としてはデコード時が基準となっていて、デコード時の各スレッドの状態から逆算してエンコード時の並び替えの位置を決めている、という考え方のようです。 また、基本的には逐次アルゴリズムをベースにしていて、過去の Deflate の資産を有効利用しようとしていることがよく分かります。 一方で、デコーダー側がどの程度並列性を持っているかは無視して、エンコーダー側が決めうちで並列度（実際には32らしいです）を決めているのは若干違和感がありました。
最近出てきた圧縮形式で Zstandard も比較的有名で、GDeflateの概念を Zstandard に適用しようとした実装を見かけましたが、
あまり上手くいかなかったといったようなことが書かれていました。
https://github.com/elasota/gstd