PivCo-Huffman「マージ」操作
PivCo-Huffman "Merge" Operations (fgiesen.wordpress.com)
要約
本記事は、データ圧縮技術であるPivCo-Huffmanの新しい論文について論じており、特に既存のハフマン符号化のシリアル性に伴う課題と、それを解決するための並列化手法を解説している。従来の複数ストリームやANSスタイルのインターリービング、ブルートフォースによるデコードといった手法の限界を指摘し、PivCo-Huffmanがこれらの問題を克服する新しいアプローチを提案していることを示唆している。
全文翻訳
PivCo-Huffman "マージ" オペレーション
PivCo-Huffman" という新しい論文が出版され、非常に興味深い内容です。通常のハフマンデコード(そして、それほどではないですがエンコードも)は、本質的に逐次的です。複数のストリームを使用することで明示的な並列化を得ることができますが、これはストリーム数が適度な数(通常は4〜8)であれば問題なくスケールします。しかし、GPUのようなワイドベクトルマシンでのベクトル化にはあまり適していません。なぜなら、ストリームが増えるごとにビットストリームにシグナリングオーバーヘッドが追加され、複数のストリームから同時にデコードするのはギャザー処理が多い操作になるからです。GPUはギャザー処理にはある程度対応できますが(ただし、分散したデータアクセスは、よりコンパクトなメモリアクセスパターンよりもはるかに多くのサイクルを消費します)、それ以外のほとんどのものは、非常にギャザー処理が多いパターンには非常に不向きです。
特に、通常のテーブルベースのデコーダーは、すぐに別のギャザー処理を行います。ただし、その部分は比較的簡単に修正できます。正規化されたコード(canonical codes)は、必要であれば、比較的容易なテーブルなしデコード(少なくとも重要な「長さ決定」部分については)を可能にします。これらのアプローチは、1回のロードが非常に安価なスカラーの1つずつデコーダーではあまり効果的ではありませんが、32幅のベクトルで作業している場合、ギャザー処理を節約する整数演算を多数行うことは、より興味深い提案となります。
ANSスタイルのインターリーブを使用して、多くの論理ビットストリームを1つの物理ビットストリームに変換することもできます。これは、GDeflate が、あちこちからギャザーする必要なく、より多くの並列化の可能性を持つビットストリームを取得するために行うことです。インターリーブは「メモリ中の至る所からの読み取り」問題を解決し、適切な機能(例: AVX-512 "EXPAND" ファミリ命令、または単に同じキャッシュラインからの高速なギャザー)を提供するGPUとCPUでうまく機能しますが、そのようなハードウェアサポートがないと遅くなります。また、ビットストリーム定義の一部としてマジックナンバー(インターリーブ係数)を選択することを強制されます。低すぎると、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しか使用せず、4はx86側のARM NEONやSSE4.2のようなもののための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" でなかった位置はまだ完了していません。それらが何であるか、そして次にどのようなステップが必要かを見てみましょう。
brcdbr
001100
これらは、ルートノードの右の子に対して出力されるビットです。一般に、すべての内部ノードで、ここまで到達したシンボルを2つの小さなサブシーケンスに分割します。1つは左サブツリーに下降し、もう1つは右サブツリーに下降します。現在の例では、左に継続するサブシーケンスは "brbr" であり、右のサブシーケンスは "cd" です。すべてがリーフにプッシュされるまで、この方法でプリオーダーツリー走査を続けます。
これは、このツリーを使用した通常のハフマン符号化と同じビットを送信していることに注意してください。ただし、順序が異なります。
これをデコードするには、ビットストリームにエンコードされているシンボルの数(Nとしましょう)を知る必要があります。すべてのシンボルはルートノードを通過したはずなので、ルートノードのビット文字列にはNビットが含まれていることがわかります。そのビット文字列内の0と1の数を数えることで、左(0)と右(1)のサブツリーにいくつのシンボルが入るかがわかります。次に、再帰的に、これらのノードでも同じことができます。これにより、個々のノードのビットが最終ビットストリームのどこに配置され、いくつのシンボルがそれらを通過するかを特定できます。
最後に、ツリーを上に上がる途中で、サブシーケンスの長さがわかったので、ボトムアップのマージプロセスでそれらが何であったかを再構築できます。
例えば、"b" と "r" のリーフの親ノードを取ります。4つのシンボルが "そこを通過する" ことがわかっており、対応するビットストリームは "0101" になります。これは、このサブツリーでコード化されたシンボルのサブシーケンスが "brbr" であることを意味します。その兄弟ノードには "01" という2ビットしかなく、"cd" をエンコードします。
それらの共通の親は、先ほど見た "001100" ビットストリングを放出する6シンボルノードです。左("0")サブツリーによってコード化された4つのシンボルが "brbr" であり、右("1")サブツリーによってコード化された2つのシンボルが "cd" であることを、ちょうど計算しました。これは、ノード全体によってコード化されたシンボルが "brcdbr" であることを意味します。最後に、これをさらに1レベル上にプッシュして "a" をマージすると、"abracadabra" が戻ってきます。
それで、なぜこれを行うのでしょうか?これは単なる通常のハフマン符号化のように見えますが、バッチ処理モードで追加の手順があります。
答えは、ハフマンエンコーディングを順序付きリストパーティショニングステップのシーケンスに変換し、デコーディングをリストマージのシーケンスに変換したことです。比較を行う代わりに、2つのリストのどちらから次の要素を取得するかを指示するビットストリームが得られます。通常のハフマン エンコーディング はそれほど悪くありませんが、デコーディングは、前述のように、非常に逐次的なプロセスです。この種のリストマージはそうではありません。取得するリスト要素を特定することは、プレフィックスサムに還元されます。これは自明ではありませんが、スキャンと呼ばれる並列アルゴリズムのクラスのプロトタイプであり、これは非常にうまく実行でき、ビットストリームが特定のベクトル幅(または類似のもの)を念頭に置いて書き込まれる必要はありません。ターゲットマシンの機能に合わせて、上下に簡単にスケールします。
他にも多くの最適化が可能です。例えば、私が示したツリーには、"b"、"r"、"c"、"d" の4つのシンボルの完全な二分木が含まれています。確かに、これを3つの二分リストパーティション(デコーダー側ではマージ)のシーケンスとしてエンコード(またはデコード)できますが、シンボルあたり2ビットを一度に送信して完了することもできます。可変長から固定アルファベットへのデコード(ハフマンが行うような)はトリッキーですが、固定長から固定アルファベットへのサブセットは簡単に並列化できます。これらのリスト全体をスキャンして "1" の数を特定したくない場合、追加のビットを消費しますが、デコーダーが(潜在的に)数万ビットをスキャンする必要を省くために、ハフマンツリーノードの一部またはすべてにこの情報を格納できます。そしてさらに続きます。
したがって、このアイデアの基本的なスカラー実装はあまり興味深いものではありませんが、GPU、あらゆる種類のベクトル命令セット、あるいは単なるスレッドであっても、ほぼすべてのデータ並列基盤にうまくマッピングできるタスクのサブセットにぴったり収まるため、いじる価値があります。そして、論文で達成された数値は確かに励みになりますが、主な結果は驚くことではありませんが、AVX-512を備えたx86-64サーバーまたはApple Silicon CPU、つまり非常にハイエンドなハードウェアで行われています。
これはアルゴリズムの将来にとって良い兆候ですが、ワイヤーフォーマットは、最高級のターゲットだけでなく、すべての人にとって機能する必要があります。
したがって、疑問が生じます。基本的なプリミティブをどれだけ安価にできるでしょうか?この記事では、特にボトムアップデコーダーの "マージ" オペレーションに焦点を当てます。
マージオペレーション
これらのマージの1つが何に帰着するかを、Python風の擬似コードで示します。
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 が処理された(および出力要素が書き込まれた)要素の数と等しいという不変条件を持っていることに注意してください。したがって、実際には両方を追跡するのは過剰です。どちらか一方が他方を意味します。そして、r_pos は、これまでに遭遇したすべての bit 値の(排他的)プレフィックスサムです。
前述のように、これは基本的に並列プログラミング101の中間学期の宿題問題に還元されます。これは非常に単純なアルゴリズムであり、私たちにとって良いニュースです。なぜなら、私たちは本当に高速なものが必要であり、これがこれほど単純な場合、通常はさまざまな方法で実行でき、現在のターゲットで最も効果的なものを選ぶことができるからです。しかし、残りの部分では、準Pythonよりも少し低レベルのものが必要になります。特に、実際のデータ型を選択する必要があります。以下では、コード化しようとしているシンボルはバイトであると仮定します。これは実用的であり、このトピックに関する以前の投稿とも一致しています。ビットストリームは、明白な方法でビットパックされます。
最も直接的な一致は、AVX512_VBMI2のようなものに見られます。これは、バイトレベルのマスクロード操作の一種であるVPEXPANDBを提供します。ここで、アクティブなSIMDレーン(対応するマスクビットが1の場合)は連続したアドレスからロードし、非アクティブなレーンはそのままにするか、ゼロで初期化します。ロードアドレスは増加しません。これはスパースデータをベクトルレジスタにロードすることを目的としており、基本的に私たちが求めているものに完全に一致します。以下のコードスニペットでは、公式の組み込み関数名は使用しません。なぜなら、慣れていないと表記が非常に威圧的だからですが、プロセスは次のようになります。擬似Pythonから擬似Cに切り替えます。
void merge(uint8* output,
const uint8* l_list, const uint8* r_list,
const uint8* bits, usize count)
{
// これらのコードスニペットは、最後の数要素のような境界ケースを処理せず、
// 境界チェックも行いません。
// 実際のインプリメンテーションではこれらが絶対に必要ですが、
// ブログ投稿の擬似コードではありません。警告しておきます。
// AVX-512は1回のイテレーションで64バイトを処理できます!
for (usize i = 0; i < count; i += 64)
{
// マスクはr_listから来る要素のビットがセットされています
// (LE順序が自然です)
uint64 mask = read64LE(&bits[i / 8]);
// l_listエントリを読み込みます
// 一時的に残りはゼロで初期化しておきます
uint8x64 result = zero_masked_vexpandb_from_mem(l_list, ~mask);
// r_listエントリを読み込みます
result = masked_vexpandb_from_mem(result, mask, r_list);
// 結果を出力バッファに格納します
vstore(&output[i], result);
// マスク内のビット数 (popcount) を決定して、
// r_listとl_listのポインタをどれだけ進めるかを判断します
uint64 npop = popcount(mask);
r_list += npop;
l_list += 64 - npop;
}
}
マスクをロードしてポインタを進めるための多少の調整がありますが、これは基本的なマージアルゴリズムの機能的なAVX512_VBMI2インプリメンテーションの擬似コードです。必ずしも最適ではありませんが、この投稿ではそれほど深くは掘り下げません。実際には3つのベクトル命令(2つのロードと1つのストア)があり、残りはロジスティクスです。
ここでの教訓は、「マシンに『それを実行する』命令があれば、これは非常に簡単だ」ということだけです。だからこそ、この記事ではAVX512バージョンのいずれにもこれ以上の時間を費やしません。これは、それが基本的に何も問題にならないことを証明するための、私たちの高いアンカーです。
私が言いたい唯一のことは、実際のプレフィックスサムがこのバージョンではほとんど見えなくなったということです。VPEXPANDB は、どのバイトをどこにルーティングするかを決定するために、アクティブなレーン全体で暗黙的に一種のプレフィックスサムを実行し、その後、最後に処理した64個のマスクビットすべてに対して人口カウントを実行して、リストポインタをどれだけ移動させるかを判断します。これが物事の進め方になります。
本質的に、この記事の残りの部分で行うことは、AVX512_VBMI2を必要とせずに、上記のループにできるだけ近づく方法を見つけることです。x86側では、AVX2(256ビット整数ベクトル)のオプションと、SSE4.2機能レベルのオプションがあるでしょう。もう少しローエンドのターゲット(SSSE3は現実的に行ける最低ラインです)にも効率的なものを実行できますが、これらはマイナーなバリエーションです。ARM側では、主にNEON/AdvSIMDに焦点を当てます。SVEとRVVは、関連ハードウェアにアクセスできる人々に任せます。
基本的なアプローチ:一度に8バイト
SSE4.2およびNEONレベルのベクトルレジスタは、AVX512の名前の由来である512ビットよりもはるかに狭いです。今のところ、ローエンドターゲットのために、128ビット(または16バイト)を一度に収容するレジスタに留まります。後でその全幅を活用する方法を見ますが、今は単純に保ち、ツールに慣れましょう。
私たちの主な作業用馬は、SSE側ではPSHUFB(SSSE3で導入)であり、ARM側ではTBL(ここでは64ビットARMのみを見ています。関連命令は32ビットARMにも存在しますが、一度に8バイトの出力しか生成しませんが、最近は主に64ビットコードで作業しています)です。TBLは、最大4つの(連続した)ソースレジスタを、それらをバイトのテーブルとして解釈し、別のソースレジスタをそれらのテーブルルックアップの結果を指定するインデックスのバイトベクトルとして使用し、宛先レジスタにすべてのテーブルルックアップの結果を書き込みます。つまり、これは汎用的なバイトからバイトへのシャッフル操作です。範囲外のインデックス値は0を生成します。
x86のPSHUFBは非常に似ていますが、いくつかの違いがあります。まず、「テーブル」は常に単一の128ビットベクトルレジスタ(16バイト)です。それ以上でもそれ以下でもありません。第二に、テーブルインデックスを選択するのは下位4ビットのみです。ビット4から6は無視されます。機能的には、テーブルアドレッシングはmod 16を意味します。第三に、インデックスベクトルでMSB(ビット7)を設定すると、そのSIMDレーンで0バイトが返されます。
これらのプロパティは、AArch64の1つの128ビットベクトルTBLとx86-64のPSHUFBが、インデックスが16から127(包括)の間でそれらの動作が異なる場合を除き、ほとんど互換性があることを意味します。
一度に8バイトを処理する場合、ビットストリームから一度に8ビット、つまり1バイト分のビットを処理することも意味します。これは便利です。8ビットは256通りの異なる組み合わせを意味し、すべての可能な組み合わせのシャッフルインデックスベクトルを合理的に事前計算してテーブルに保存できるほど小さいです。そのテーブルは256 * 8バイト = 2KiBになります。そして、l_list と r_list の両方から次の8バイトを投機的に取得し、それらを単一の16バイト(128ビット)ベクトルに結合し、TBL/PSHUFBを使用してインデックスを付けることができます。これは次のようなアルゴリズムになります。
void merge(uint8* output,
const uint8* l_list, const uint8* r_list,
const uint8* bits, usize count)
{
// 今は一度に8バイト
for (usize i = 0; i < count; i += 8)
{
// ビットストリームから1バイト分のビットをロードします
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) を決定して、
// r_listとl_listのポインタをどれだけ進めるかを判断します
usize npop = popcount(in_bits);
r_list += npop;
l_list += 8 - npop;
}
}
インデックスベクトルテーブルを生成するコードは示していませんが、行う必要があるのは、0から7までの値を含む8エントリのLリスト、対応する8から15までの値を含む8エントリのRリストを準備し、すべての256の可能な8ビットパターンでスカラーマージアルゴリズムを使用することだけです。出力リストは、シャッフル命令を制御するために使用するインデックスです。この基本的なアプローチは、この記事のすべてのテーブルベースのテクニックで機能します。毎回明示的に呼び出すことはしません。
また、8ビットのpopcount命令が利用できない場合もありますが、その場合は256エントリのバイト値テーブルで十分です。2KiBテーブル予算にさらに256バイトを追加しても、コストはそれほどかかりません。
これは十分に単純であり、改善の余地はすぐには見当たりません。事前計算されたインデックスベクトルの256エントリ2KiBテーブルは問題ありません。次に、操作サイズにきれいに分割される大きなステップは、一度に16ビットを処理することです。これには、65536エントリのテーブル(テーブルエントリあたり16B、なぜなら現在16バイトの出力を生成しているため)が必要になり、テーブルに1MiBかかります。2KiBテーブルは、どのCPUのL1Dキャッシュにも余裕で収まります。1MiBは誰のL1にも収まらず、すべてのテーブルアクセスがL1Dミス(場合によってはL2ミスも)である場合、このループのパフォーマンスは急激に低下します。
要するに、インデックスベクトルを取得するための単一のテーブルルックアップは、一度に8項目を処理する場合には完全に実用的ですが、16項目まで増やしたい場合は、別の方法が必要です。
16バイトへの道
別の問題があります。64ビットARMには2レジスタTBLがあり、1つの命令で32バイトのテーブルをインデックスできます。そして、多くの(すべてではないが)実装では、2レジスタTBLは単一のuopとして実行されるため、これは利用可能であるだけでなく効率的でもあります。しかし、x86のPSHUFBは、実際には16バイトバージョンしかありません。(AVX2 VPSHUFB は2つの128ビットPSHUFBを並列に実行します。テーブルエントリは、対応するインデックス値が存在するベクトルの同じ128ビットスライス内から常にフェッチされます)。
追加の命令を使用して、より広いPSHUFBを通常のPSHUFBから合成できます(複数のPSHUFBを小さなサブテーブルに分割し、その後、ブランチレス選択で正しいサブテーブルを選択します)。しかし、これは比較的コストがかかります。LとRのリストバイトを個別に処理する方がはるかに良いです。LとRのリスト候補バイトの合計は32バイトになりますが、各リストからは最大16バイトしか消費できません。そしてPSHUFBは、対応するインデックスMSBを設定すると0バイトを生成できます。これは、次のようなものに設定したいことを意味します。
uint8x16 l_result = vshuffle(l_bytes, l_index_vec);
uint8x16 r_result = vshuffle(r_bytes, r_index_vec);
uint8x16 result = vor(l_result, r_result);
しかし、今度は2つのインデックスベクトルを用意する必要があります。あるいは、そうする必要はありませんか?インデックスベクトルのMSBを設定すると、他のビットが何であっても関係ありません。PSHUFB(およびTBL)は常に0を返します。そして、Lリストから来る項目は、Rリストの項目がない場所に正確にあります。したがって、同じインデックスベクトルを両方に使用できます。1つのリスト(以下ではRリスト)を通常のシャッフルインデックスで使用するように設定し、もう一方のリストはMSBがセットされたシャッフルインデックスを使用します。そのインデックスベクトルを一方のリストに使用した後、排他的ORを介してすべてのインデックスMSBを反転させると、もう一方のリストに使用するインデックスベクトルが得られます。これにより、次のようになります。
uint8x16 r_result = vshuffle(r_bytes, index_vec);
uint8x16 l_result = vshuffle(l_bytes, vxor(index_vec, 128));
uint8x16 result = vor(r_result, l_result);
クール。単一のビット演算は、2つの別々のインデックスベクトルを用意する必要があるよりもはるかに優れています。ところで、これで16バイトの出力を生成するもっともらしい方法が得られましたが、そもそもそのインデックスベクトルをどこから取得するのでしょうか?
インデックスベクトルの最初の半分については、すでに持っているテーブルと同じ種類のテーブルを使用できます。そして、理論的には、2番目の半分にも同じテーブルを再度使用できます。ただ1つの問題があります。2番目の半分は l_bytes または r_bytes の先頭から始まるのではなく、最初の半分が終わった直後から始まる必要があります。
これは、最初のバイトが例えば3つのセットビットを持っていた場合、2番目の半分用のインデックスベクトルは r_bytes のすべてのインデックスに3を、l_bytes のすべてのインデックスに 8 - 3 = 5 を追加する必要があることを意味します。このアイデアの直接的な実装には、次のものが必要です。
- マスクの最初の半分(8レーン分)のテーブルルックアップを実行する
- マスクの2番目の半分(さらに8レーン分)の別のテーブルルックアップを実行する
- 最初の8つのベクトルレーンに対応するビットストリームバイトの人口カウントを決定する(おそらく、そのバイトを分離するためのANDまたはシフト、次にテーブルルックアップまたはネイティブpopcount命令を使用する)
- この人口カウントをベクトルレジスタに取得し、少なくとも8つのコピーを作成する
- ベクトルの2番目の半分用のインデックスベクトルについて、バイトがR半分またはL半分から来るかどうかを示すビットマスクを生成する(インデックスMSBから判断できる)
- 2番目の半分用の "R" レーンインデックスすべてに、複製された人口カウントを追加する(これは通常、ビットごとのANDとADDになる)
- 8ベクトルポピュレーションカウントを計算する
- 2番目の半分用の "L" レーンインデックスすべてに、8ベクトルポピュレーションカウントを追加する(AND-NOTとADD、または類似のもの)
- 最後に、2つのインデックスベクトルの半分を結合する
これは非常に多くの作業です。一度に16バイトを処理することは明らかに価値がありますが、記述されているように、これは少なくとも8命令相当であり、8バイトチャンクでデータを処理するよりも多くなります。確かに、ポインタ操作などを節約できますが、ベクトル側では、これはかなり悲惨に見えます。もっと良いものが必要です。
上記を少し調整して改善することはできますが、ここで命令を1つか2つ節約するだけでは十分ではありません。本当に必要なのは根本的な単純化です。
エレベーターピッチは次のとおりです。人口カウント(pop0と呼びます)をRインデックスに追加し、8 - pop0 をLインデックスに追加する必要があります。そして、この符号の違いが実際に問題を引き起こします。しかし、Lインデックスが否定されたらどうでしょうか?次に、それらに -(8 - pop0) を追加する必要があります。これは pop0 - 8 になり、すべてのレーンに人口カウントを追加することになります(-8バイアス部分は後で説明します)。
L値を否定しても、Lインデックスは0になる可能性があり、レーンがRリストまたはLリストのどちらから来るかをMSBから判断できる必要があるため、最終的なシャッフルロジックを機能させるために、L値を否定しても完全にはうまくいきません。しかし、r_list[i] から来るバイトはインデックスベクトル内のその場所に i を格納し、l_list[i] から来るバイトはインデックスとして 255 - i = i ^ 255 を格納するという規約に合意することができます。
2番目の半分でのシャッフルインデックスについては、最初の半分で起こったことを考慮して、まだRインデックスに pop0 を追加する必要があります。これは簡単です。Lインデックスについては、255 - (i + (8 - pop0)) = (255 - 8) - i + pop0 が必要です。
まだ2番目の半分用のシャッフルインデックスをテーブルから取得する必要があります。2番目の半分用に、事前計算されたLインデックスが 255 - i ではなく (255 - 8) - i となる別のテーブルを作成した場合(Rは同じまま)、ループ内で追加の計算は必要ありません。そして最後に、pop0 は、最初の半分テーブルルックアップで使用する最初のマスクバイトにのみ依存することに注意してください。それらのテーブルエントリが8バイトではなく16バイトを格納する場合、各テーブルエントリの後半に pop0 の8コピーを格納するだけで済みます。これらすべてをまとめると、16バイトずつのループの擬似コードは次のようになります。
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];
// index1は128ビットベクトルの後半に入れる必要があります
uint8x16 index1_wide = vcombine(vzero_uint8x8(), index1);
// 2つの値を加算してpopcount調整を実行します
uint8x16 index_vec = vadd(index0, index1_wide);
// 投機的に、l_listとr_listから次の16バイトを読み込みます
uint8x16 l_bytes = vload128(l_list);
uint8x16 r_bytes = vload128(r_list);
// バイトをシャッフルして結合します
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);
// マスク内のビット数 (popcount) を決定して、
// r_listとl_listのポインタをどれだけ進めるかを判断します
usize npop = popcount(in_bits);
r_list += npop;
l_list += 16 - npop;
}
}
テキストで述べたように、index_vec_tab0 は256個の16バイトエントリを持ち、各テーブルエントリの最初の8バイトは、r_list = { 0, 1, ... , 7 } と l_list = { 255 - 0, 255 - 1, ..., 255 - 7 } のスカラーマージを実行した結果のインデックス順列です。後半の8バイトは、テーブルインデックスの人口カウントを8回繰り返したものです。
このコードでアクセスされるindex_vec_tab1は、同じr_listと変更されたl_list = { 247 - 0, 247 - 1, ..., 247 - 7 }でのスカラーマージ結果に対応する256個の8バイトエントリを持ちます。したがって、このバージョンは約6KiBのテーブルを必要としますが、以前よりも多いものの、まだ合理的に快適な量です。
この "結合" 操作(通常、CPU内部で何らかのベクトルシャッフルになる)を望まない場合、2番目のテーブルを16バイトエントリにし、各エントリに8バイトのゼロと実際のシャッフルインデックス(この場合は後半に正しく配置される)を持つようにすることもできます。これはシャッフルを節約しますが、テーブルサイズにさらに2KiBを追加し、アドレス計算から追加のuopが発生します。x86とAArch64の実装は通常、インデックスを8倍することで(ロードアドレス生成の一部として)無料で乗算できますが、16倍はできません。そのため、通常は命令を節約しません。アドレス生成操作のためにベクトルシャッフル/シフト操作を交換するだけです。実際には、それらは通常近いですが、小さい方のロードは少しパフォーマンスが良く、2KiB小さいテーブルサイズと合わせて、私が好むバリアントです。
SSSE3/SSE4.2ターゲットの場合、この一般的なアプローチは私がこれまでに管理できた最良のものです。正確な実装詳細は少しトリッキーになりますが、ループオーバーヘッドを節約するためにさらにアンロールしたいかもしれませんが、これが要点です。
AVX2は基本的にこれを行います。ただし、一度に2つの128ビットベクトルに対して実行します。AVX2の動作方法(128ビット境界を越えるのは難しく、比較的コストがかかる)のため、これが最良の方法です。実際には、128ビットアプローチの事実上アンロールされたバージョンです。インデックスベクトルの構築は本当に128ビットベクトル操作です(おそらく、実際には64ビットベクトル操作であり、上記の計算ではすでに2つの64ビット半分を128ビットベクトルに結合していますが、そのように見えないかもしれません)。AVX2では、これらの作業をすべて2回行い、2つの128ビット半分を256ビットレジスタにマージするために追加のシャッフルを行います。
同様に、l_listとr_listを2つの別々の128ビット半分としてロードする必要があり、これも128ビットベクトルを扱うよりも実際には利点がありません。唯一の実際の256ビットベクトル操作は、「シャッフルバイトを結合する」および「ストア」の段階にあります。その結果、AVX2はSSE4.2よりも少し高速ですが、2倍にはほど遠いです。私にとっては1.2倍に近く、それさえも多くの注意が必要でした。
AVX2用に、大きなテーブルをまったく使用せず、代わりにシャッフルベクトルを計算する他のアプローチを検討しました。これらのアプローチは、より「自然に256ビット」と言えるかもしれません。そして、それらはより良いベクトル幅の利用率を持ちますが、この方法で行うとさらにいくつかの命令が必要になり、テーブルベースのアプローチのパフォーマンスにかなり近づくことはできましたが、それを超えることはできませんでした。いつか書くかもしれません。
皮肉なことに、このアプローチは512ビットベクトルにステップアップすると簡単に優位になると思いますが、それにはあまり理由がありません。AVX512_VBMI2を使用すると、ソフトウェアでは決して超えられない完全なハードウェアソリューションがあり、「AVX512だがVBMI2ではない」は、現在、ほとんどサーバーCPUに限定されており、512ビットベクトルコードが使用されると大幅にクロックダウンする傾向があります。多分いつか?しかし、それについてはあまり考えていません。
NEONの特別な点
上記のように記述されたアルゴリズムはNEONでもうまく機能し、パフォーマンスも良好です。それに問題はありません。
ただ、2テーブル128ビットTBLが高速なマシン(Apple Siliconや新しいハイエンドARM Cortex/Neoverseコアなど)では、もう少し改善できることが判明しました。ロード・シャッフル・ストア部分は次のようになります(今回は実際にNEON固有なので、直接NEON組み込み関数を使用します)。
// ソースバイトをロードします
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);
さて、その部分は非常に良いですが、インデックスベクトルをどうやって取得するのでしょうか?r_listからのフェッチは正のインデックスを使用し、l_listからのフェッチは負のインデックスを使用するようにしたいので、私たちの「すべてにpop0を追加する」という賭けは引き続き機能します。しかし、2レジスタTBLを使用している場合、最終的なl_listインデックスは16ベースである必要があります。なぜなら、l_listバイトはテーブルの16から31のインデックスに入るからです。
したがって、今回はインデックスベクトルが実際のint8になり、r_list[i]から来るバイトはiを格納し、l_list[i]から来るエントリは-(16 + i)を格納します。この規約を使用し、テーブル設定は前のステップと同じに保つことができます。シャッフルを実行する直前に、Lリストエントリのテーブルインデックスを否定したいのですが、これはすべての値の絶対値を取ることに帰着します。これにより、(正の)r_listインデックスはそのまま残り、(現在負の)l_listインデックスは必要なように否定されます。
したがって、もしそうすれば、次のようになります。
// インデックスベクトル部分をロードします
int8x16_t index0 = vld1q_s8(index_vec_tab0[in_bits & 0xff]);
int8x16_t index1 = vld1q_s8(index_vec_tab1[in_bits >> 8]);
// マージされた制御を形成します
int8x16_t summed = vaddq_s8(index0, index1);
uint8x16_t index_vec = vreinterpretq_u8_s8(vabsq_s8(summed));
これは、完全な128ビットテーブルエントリを使用するバリアントを想定しています。前述のように、2番目のテーブルを64ビットエントリにすることで、より小さくできますが、実行時にさらに1つのベクトルシャッフル型操作(通常はvextq)が必要になります。
最後のトリックは、NEONに符号付き値の|a[i] – b[i]|の命令があり、私たちが求めているのは|a[i] + b[i]|であることに気づくことです。しかし、b[i]は私たちが制御するテーブルから来ます。そのテーブル全体を否定するだけでよく、最終的なインデックスベクトルは2つのロードと1つの算術命令になり、次の完全なマージ操作が得られます。
// インデックスベクトル部分をロードします
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_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実装では、この16バイトのマージ操作が実際に完璧に最適であると思います。2つのリストからのロードとストアは厳密に必要です。単一の1バイトuop(多くのuArchでは)命令を使用してバイトシャッフルを実行することは、これらのソースベクトルを取得した後にできる最小限の作業です。前述のように、完全な16ビットインデックスからの1MiB LUTは実用的ではありません。単一のテーブルロードで実行できない場合、少なくとも2つ必要です。そして、2つの別々のテーブルロードがある場合、それらを結合するための少なくとも1つの命令が必要です。
ループの残りの部分(人口カウントの決定、ポインタの進め方など)、「制御プレーン」と言える部分についてはいくらか不確実性がありますが、この操作の「データプレーン」側は鉄壁だと思います。
そして、今日のところはこれで終わりです!自分で実装したコードへのリンクは貼りません。Marcinと話したところ、彼はこの記事で説明したことを彼のPivCo-HuffmanのGitHubリポジトリで試しており、彼のテストでそれらがより高速であることを確認しています。したがって、実際に実装されたものを見たい場合は、そこに行ってください。読んでいる時期によってはすぐには利用できないかもしれませんが、まもなく利用可能になるはずです。