誰もがSIMDを知るべきだ
Everyone Should Know SIMD (mitchellh.com)
要約
SIMD(Single Instruction, Multiple Data)は、CPUが一度に複数のデータに対して同じ命令を実行する並列処理技術です。一般的に複雑でニッチな最適化と見なされがちですが、筆者は、多くの開発者が日常的なプログラミングでもSIMDの恩恵を受けられると主張しています。この記事では、Zig言語を例に、SIMDの基本的な概念と、一般的な「N個の値を一度に処理する」コードの構造を、具体的な例を交えて解説しています。
全文翻訳
誰もがSIMDを知るべき理由
SIMDは複雑だという評判があります。私は、それを学ぶには複雑すぎる、あるいは日常的なプログラミングには役立たない、ごく一部の高性能ソフトウェアのためだけの最適化だと考えて、SIMDを敬遠している非常に優秀なソフトウェアエンジニアに数多く会ってきました。
私はそれは間違いだと思います。SIMDは理解するのが簡単1であり、一般的な「一度にN個の値」を処理するSIMDコードは、単純なforループを高速化するために、ほぼ常に同じ一般的な形状に従います。基本を学べば、SIMDを書くことはforループを書くのとほとんど同じくらい簡単です。そして、そうでない場合は、今はスキップするのが良い兆候であることがほとんどです。
すべての開発者は、少なくともその程度のSIMDを知っておくべきです。
この記事ではZigを例として使用しますが、これはどのプログラミング言語にも適用できる一般的な内容です。SIMD命令のサポートはプログラミング言語によって異なりますが、将来的に多くのプログラミング言語がこれらの一般的な概念を公開してくれることを願っています!
最近はすべての投稿でこれをしなければならないのが嫌ですが、これもAIの助けなしに完全に手書きされたものであることを付け加えておきたいです。
目次
- 背景: SIMDとは何か?
- 一般的な形状
- 実際の例
- ステップ1: 定数をブロードキャストする
- ステップ2: 一度に1つのベクトルをループする
- ステップ3: SIMD演算を実行する
- ステップ4: ベクトル結果を削減する
- ステップ5: スカラーテールで完了する
- 要約: 一般的な形状
- なぜコンパイラはこれをできないのか?
- 誰もがSIMDを知るべき
背景: SIMDとは何か?
すでにSIMDが何であるかを知っている場合は、このセクションをスキップしてください。
SIMDは、CPUが複数の値を並列に操作できるようにします。例えば、一度に1バイトを比較する代わりに、CPUは単一の命令で4バイト、8バイト、あるいはそれ以上のバイトを比較できます。
コードでこのようなループを見たことがあるなら、
for (byte in bytes) { /* ... */ }
for (character in string) { /* ... */ }
for (value in array) { /* ... */ }
SIMDを使用する機会があります。SIMDはそれらを次のように変換します。
for (8 byte chunk in bytes) { /* ... */ }
これにより、並列性に直接対応する局所的な高速化が得られます。つまり、データを4倍、8倍、あるいはそれ以上に高速に処理できます。
これが効果を発揮するための唯一の真の要件は、定期的に十分な量のバイトを処理する必要があることです。もしこれらのforループを、数バイトや数十バイトにしかならないデータに対して実行しているなら、それは価値がありません。しかし、数百、数千、数百万バイトを反復処理している場合、その効果は絶大です。
それが基本です。simdutfやsimdjsonのようなプロジェクトはこれを極限まで推し進め、理解するのが難しいSIMDテクニックを使用しています。しかし、SIMDの恩恵を受けるために、そのようなアルゴリズムを書く必要はありません。一般的なケースは劇的にシンプルです。
一般的な形状
一般的な「一度にN個の値」を処理するSIMDコードは、同じ5つのステップに従います。
- 必要な定数をブロードキャストし、もしあればベクトルアキュムレータを初期化します。
- 一度に1ベクトル幅のチャンクで入力をループします。
- 必要に応じて、すべてのレーンで比較または算術演算を実行します。
- 必要に応じて、ベクトル結果を削減または格納します。
- 残りの要素をスカラーテールで処理します。スカラーテールは、ベクトル化する前の通常のループと同じですが、完全なベクトルに収まらない残りを処理するだけです。
これを繰り返すうちに、すべてのforループをこれらの5つのステップに分解できるようになり、SIMDを書くことはスカラーループを書くのと同じくらい自然になります。
実際の例
Ghosttyからの実際の例を見てみましょう。スカラー実装、SIMD実装を見て、それを上記の一般的な形状にマッピングします。
デコードされたコードポイントのスライスがあり、0xF(C0制御文字)以下の値を見るまで消費したいとします2。ターミナルはほとんどが印刷可能な文字なので、それらをまとめてバッチ処理しようとします。したがって、このループは次の印刷可能なランの終わりをできるだけ早く見つけます。
スカラーループは1行です。
while (end < cps.len and cps[end] > 0xF) end += 1;
これは一度に1つのコードポイントを処理します。理解しやすいです。
CPU固有のイントリンシック3やコメントなしの汎用ベクトルバージョンは次のとおりです。後で詳しく説明します。
if (simd.lanes(u32)) |lanes| {
const V = @Vector(lanes, u32);
const threshold: V = @splat(0xF);
while (end + lanes <= cps.len) : (end += lanes) {
const values: V = cps[end..][0..lanes].*;
const greater_than_threshold = values > threshold;
if (@reduce(.And, greater_than_threshold)) continue;
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
}
}
while (end < cps.len and cps[end] > 0xF) end += 1;
さらに12行のコードです。
これは、ARM NEON(Apple Siliconを含む)で最大4倍、AVX2(ほとんどの最新x86 CPU)で8倍、AVX-512(一部のIntel CPUおよびAMD Zen 4以降)で16倍ループのスループットを向上させることができます。
実際のターミナルプログラムから最終的なターミナル状態までのエンドツーエンドのスループットでは、AVX2搭載のIntelデスクトップで5倍程度の高速化でした。SIMDコードの周辺の他の要因により、理想的な速度のいくらかは常に失われますが…それでも5倍です!
さて、これらの12行が、概念に慣れていない人には非常に異質に見えることがわかりました。そこで、ステップバイステップで説明し、以前に述べた形状に直接マッピングしましょう。
ステップ1: 定数をブロードキャストする
最初の3行から始めましょう。
if (simd.lanes(u32)) |lanes| {
const V = @Vector(lanes, u32);
const threshold: V = @splat(0xF);
simd.lanes(u32)はGhosttyのヘルパーで、ターゲットCPUが一度に処理できるu32値の数を返します。これらの個々の値はレーンと呼ばれます。ARMでは4、AVX2では8、AVX-512では16を返します。ターゲットに目的のベクトルサイズがない場合、nullを返し、このコード全体をスキップしてSIMD処理を一切行いません。
@Vector(lanes, u32)はベクトル型を作成します。lanesが8の場合、VはCPUが並列に操作できる8つのu32値を含む単一の値になります。そして、それに続きます。
最後に、すべての値を0xFと比較する必要があります。ベクトル比較には両側にベクトルが必要なため、@splat(0xF)は0xFを各レーンにコピー、つまりブロードキャストします。結果は次のようなベクトルになります。
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
これがステップ1です。ベクトル型を準備し、定数をブロードキャストします。一部のアルゴリズムでは、ここでベクトルアキュムレータも初期化しますが、このアルゴリズムでは必要ありません。
ステップ2: 一度に1つのベクトルをループする
次に、一度に1つの完全なベクトルをループします。
while (end + lanes <= cps.len) : (end += lanes) {
const values: V = cps[end..][0..lanes].*;
lanesが8の場合、少なくとも8つの値が残っている場合にのみループに入ります。ループ内では、それらの8つの値をvaluesベクトルにロードします。各ループの終わりに、end += lanesは1つではなく8つずつ進みます。
完全なベクトルが必要であるという要件は重要です。値が5つしか残っていない場合、8レーンのベクトルをロードすることはできません。これに対処するためのさまざまなトリックがありますが、簡単な方法として、後でステップ5で説明するスカラーテールで処理します。
これがステップ2です。一度に1ベクトル幅のチャンクで入力をロードしてループします。ここでレーン数による高速化が見られます!
ステップ3: SIMD演算を実行する
次に比較を実行します。
const greater_than_threshold = values > threshold;
valuesとthresholdはどちらもベクトルなので、これはベクトル演算(文字通りのベクトルCPU命令)にマッピングされます。1つの>は、valuesの各レーンをthresholdの対応する各レーンと比較します。8つのレーンがある場合、これはスカラー比較cps[end] > 0xFを8回実行するのと同等ですが、CPU命令1つで実行されます4。
結果は、レーンごとに1つのブール値を持つ別のベクトルになります。概念的には、次のようになります。
values: { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold: { 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
これが実際のSIMD演算です。明示的な内部ループはありません。>演算子は、すべてのレーンに並列に適用されます。
比較は一例にすぎません。これは加算、乗算、最小値、最大値、またはベクトル型でサポートされているその他の演算である可能性があります。重要なのは、コードの形状が同じままであることです。
ステップ4: ベクトル結果を削減する
これでブール値のベクトルが得られましたが、元のループは0xF以下の最初の値の位置を知る必要があります。
まず、すべての値が0xFより大きい一般的なケースを処理しましょう。
if (@reduce(.And, greater_than_threshold)) continue;
@reduce(.And, ...)は、すべてのブール値をandで結合し、単一のブール値を返します。すべてのレーンがtrueの場合、continueして次のベクトルを処理します。私たちの例では、レーン3はfalseなので、@reduceはfalseを返し、どのレーンが失敗したかを正確に見つけるためにフォールスルーします。
いずれかのレーンがfalseの場合、どのレーンが失敗したかを正確に見つける必要があります。
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
@bitCastはブール値のベクトルを、レーンごとに1ビットを持つ整数に変換します。1ビットは値が0xFより大きいことを意味し、0はそうでないことを意味します。失敗した比較が1になるようにマスクを反転させ、次に@ctzは最初の失敗の前のゼロビットの数を数えます。その数は、最初の失敗したレーンのインデックスです。
そのインデックスをendに追加してbreakします。なぜなら、制御文字が見つかったからです。
ステップ3と同じ値を使用して、レーンごとのこの変換を確認できます。
values: { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask: { 1, 1, 1, 0, 1, 1, 1, 1 }
~mask: { 0, 0, 0, 1, 0, 0, 0, 0 }
@ctz(~mask)は、最初の1の前の3つのゼロビットを数えるため、3を返します。endに3を追加すると、レーン3、つまり0x0A(最初の制御文字)を指します。
これがステップ4です。ベクトル結果を元のアルゴリズムが必要とするものに削減します。これは、アルゴリズム間で最も変化するステップでもあります。合計はベクトルアキュムレータを単一の数値に削減するかもしれません。変換はベクトル全体を出力バッファに格納するかもしれません。私たちのスキャンは、ベクトルをビットマスクに変換して、特定のレーンを見つけられるようにします。
ステップ5: スカラーテールで完了する
ベクトルループの後、最初にあったスカラーループをそのまま実行します。
while (end < cps.len and cps[end] > 0xF) end += 1;
入力長がベクトル幅の正確な倍数でない場合、これは残りの値を処理します。例えば、8レーンのベクトルループは、このループのために0から7の値のいずれかを残します。これはスカラーテールと呼ばれます。
このループは、simd.lanes(u32)がnullを返すCPUも処理します。その場合、SIMDコード全体をスキップし、スカラーループがすべての入力を処理します。元の実装は、フォールバックとテールの両方として残ります。
これがステップ5です。通常のループです。
要約: 一般的な形状
実装全体を5つのステップにマッピングしましょう。
@splat(0xF)は比較値を各レーンにブロードキャストします。whileループは一度にlanes個の値をロードします。values > thresholdは各レーンを並列に比較します。@reduce、@bitCast、@ctzは最初の失敗した比較を見つけます。- 元のスカラーループは残りとサポートされていないCPUを処理します。
ステップ4の詳細を理解するには最初は時間がかかりますが、全体的な形状は簡単です。そして、ステップ1、2、3、5は、完全に異なるアルゴリズム間でもほぼ同じように見えます。
for (byte in bytes)を見るたびに、この形状にマッピングすることになります。
なぜコンパイラはこれをできないのか?
時にはできます!コンパイラは、特に複雑な制御フローのない単純な算術ループを、自動ベクトル化できます。手動でSIMDを書く前に、常に最適化を有効にしてスカラーバージョンをコンパイルし、コンパイラが何を出力するかを確認すべきです。
しかし、コンパイラが自動ベクトル化できるものには深刻な制限があり、一般的にその能力は非常に劣っています。自動ベクトル化は数十年にわたりコンパイラ研究の活発な分野であり、最近の研究でさえ、本番環境のコンパイラが定期的にベクトル化の機会を逃しているという観察から始まっています。これはすぐに消える問題ではないと思います。
さらに重要なのは、このループが5倍の高速化を気にするほど重要になった場合、ベクトル化が明示的で予測可能であることを望むことです。無関係なコード変更やコンパイラの更新によって、それが静かにスカラーループに戻ってしまうことを望みません。
誰もがSIMDを知るべき
すべての開発者は機会を認識できるべきであり、最も重要なのはSIMDを恐れるべきではありません。ホットなループが大量の連続データをスキャン、比較、カウント、または変換しているのを見た場合、一度に1ベクトル幅のチャンクで処理することを想像できるはずです。
この記事は、これらの一般的なケースが非常に規則的なパターンに従っており、すぐに慣れることを示しています。そして、優れた言語サポートがあれば、簡単な改善を得るためにアセンブリ言語やCPU固有の癖を知る必要はありません。
誰もがこれを実行するために必要な程度のSIMDを知っておくべきです5。
フットノート
- simdutfやsimdjsonのような非常に印象的なプロジェクトは、目標を達成するために非常に複雑なSIMDトリックを使用しています。しかし、これは私が「日常的なSIMD」と考えるものではありません。↩
- C0制御文字は
0xFを超えて拡張されます。これはGhosttyがこの特定のコードパスで使用するカットオフであり、ESCおよびその他の制御シーケンスの処理は elsewhere で行われます。↩ - 汎用ベクトルはCPU固有の構文を削除しますが、CPU固有のコード生成を削除するわけではありません。Zigはこれらの操作をターゲットに有効化された命令セットに低下させます。Ghosttyは、サポートされているベクトル幅を選択できない場合にスカラーコードにフォールバックします。↩
- 比較自体は1つのベクトル操作です。ベクトルのロード、結果の削減、失敗したレーンの特定には追加の命令が必要です。重要なのは、複数の比較を一度に行っていることです。↩
- この記事は、私が書いたLobstersのコメントに基づいています。↩