体系ガイド · 基礎から応用へ

SIMDとループのベクトル化

独立した配列加算から、レーン・端数・重なり・丸めを追い、最適化診断と逆アセンブルで変換を確かめます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 一命令の中で複数の値を扱う
  2. 配列の式をレーンへ対応させる
  3. 自動ベクトル化を妨げる条件を探す
  4. 浮動小数点の順序を別に扱う
  5. 診断と逆アセンブルを組み合わせる
  6. 命令数の削減と全体時間を分ける
  7. 幅とメモリ量の計算を照合する
  8. 端数と依存の課題を解く
  9. この記事をロゲイアに質問する理解を確かめる

一命令の中で複数の値を扱う

SIMDは、一つの命令で複数のデータ要素へ同じ種類の演算を行う考え方です。例えば128ビットのレジスタへ32ビットの浮動小数点数を四つ入れ、それぞれ対応する値を加算できます。一つのプログラムを四つのOSスレッドで動かしたことにはなりません。CPUの主教材と配列のメモリ配置を前提に、連続配列の加算を、要素単位の式、生成命令、端数の処理へ分けて追います。複数命令を同時に実行するアウトオブオーダ実行とも、同じ説明へまとめないようにしましょう。

データベースのベクトル化実行では、複数の行を塊として演算子へ渡し、行ごとの呼出し費用を減らすことがあります。その塊が1024行でも、CPUが一命令で1024個の値を処理するとは限りません。塊の中のループでSIMDを使う場合も、使わない場合もあります。SIMD、行のバッチ、複数スレッドは組み合わせられますが、導入の条件と得られる効果をそれぞれ確かめます。既存のベクトル化実行の記事は、このソフトウェア側の塊を扱う前提記事です。

配列の式をレーンへ対応させる

out[i]=a[i]+b[i]という式を、i=0からn−1まで計算します。四つずつ処理する場合、最初の組はaの0〜3番とbの0〜3番を読み、四つの和をoutの0〜3番へ書きます。レーン0が別の組のレーン1の答えを待つような依存はありません。連続して同じ型を置けば、値をまとめて読みやすくなります。反対に、構造体の離れたフィールドや不規則な添字なら、値を集める命令や追加の処理が必要になる場合があります。

n=11、処理幅4なら、最初の二組で0〜7番を処理し、8〜10番の三つが残ります。端数を単一要素の命令で処理する方法、より狭いベクトルを使う方法、マスクを使う方法などがあります。どれを採るかはISAと生成コードによります。端数を捨てると、速さ以前に出力が誤ります。また割当ての外まで読んで使わなければ安全、とは言えません。読み書きする範囲が全て有効であることを先に確かめます。

自動ベクトル化を妨げる条件を探す

コンパイラがループを変換するには、まとめて実行しても同じ意味を保てる必要があります。aとoutが重なり、outがaより一要素だけ後ろを指している場合、先に書いた値を次の反復が読むことがあります。このとき、元の順序で一つずつ更新する結果と、四つの古い入力を先に読んだ結果は違います。独立した配列を別々に確保する実験と、重なった範囲を許すAPIは、同じ契約ではありません。依存を無視して変換するよう求めないでください。

付属実験のrestrictは、関数の呼出し側が必要な非重複の契約を守るという指定です。コンパイラへ希望を伝えるだけの印ではなく、違反した呼出しの動作を正当化するものでもありません。例では三つの配列を別々に確保して守ります。ほかに、外部関数の呼出し、反復間の更新依存、複雑な分岐、処理量が小さすぎることなども変換を妨げます。最適化診断を使い、変換できなかった理由と、変換しない方が有利と判断した場合を区別して読みます。

浮動小数点の順序を別に扱う

要素ごとの加算では各out[i]が独立していますが、全要素を一つのsumへ加える集約は順序の問題を含みます。浮動小数点では、(x+y)+zとx+(y+z)の丸めが同じとは限りません。複数のレーンで部分和を作って最後に足すと、元の一列の加算とは順番が変わります。数学上の交換法則だけを根拠に、ビット単位で同じ結果を保証しないでください。数値安定性と桁落ちの教材を参照し、許容誤差や特別な値の扱いを先に決めます。

高速な数学演算を許す設定には、再結合だけでなく、NaNや無限大、符号付きゼロなどの前提を変えるものがあります。-ffast-mathを理由の説明なしに付けて、速さだけを比べる設計は避けます。今回の加算実験は、入力を小さい整数値のfloatとして作り、各要素の正解と端数を照合します。加算を融合積和へ置き換える実験をするなら、丸めが一回になることと、演算数をどう数えるかも明記します。変換の適用範囲と、結果の契約を対にして記録しましょう。

診断と逆アセンブルを組み合わせる

実験はGCCの-O3と、ベクトル化を無効にする設定を分けてコンパイルします。最適化診断は、どのソース行が変換されたとコンパイラが判断したかを示します。逆アセンブルでは、実際に呼ばれたadd関数を開き、複数のfloatを加える命令と、ループのアドレスの進み方を確認します。今回のx86-64向けの実行ではaddpsと、端数側のaddssを確認する対象にします。別のISAでは命令名が違うので、文字列がないことだけで変換失敗と決めません。

最適化を無効にした版にも、浮動小数点を計算するためSIMD用レジスタが登場することがあります。xmmという名前が見えただけでは、複数要素を同時に処理している証拠になりません。命令が扱う要素数と、添字の進み方を読みます。nを4で割り切れない1,048,579にしたのは、主ループだけでなく残り三つを処理する経路を検査するためです。全体の出力が正しくても、該当関数が呼ばれていなければ測りたい対象ではないため、呼出し先も照合します。

命令数の削減と全体時間を分ける

四つの加算を一つの命令へまとめても、全体が必ず4倍速くなるわけではありません。入力二つと出力一つを運ぶ帯域、ロードとストアの入口、端数、関数呼出し、実行資源の共有も費用になります。要素数が少なければ、準備や切替の割合が大きくなります。入力が大きく主記憶の帯域が限界なら、加算器を速くしても改善が小さい場合があります。Rooflineのガイドでは、計算とデータ移動の上限を同じ単位で比べます。

時間測定は配列の準備と照合を外し、addの呼出し区間を対象にします。初回と繰り返しを含む全標本を保存し、コンパイラ版、ISA、CPU、サイズを記録します。今回の仮想環境では、生成命令の有無と結果は確認できますが、専有した実機での最高性能やPMUのイベントは測っていません。短い時間差が揺れたら、都合のよい標本だけを残さず分布を確認します。命令を確認できたという結論と、何倍速いという結論には異なる根拠が必要です。

幅とメモリ量の計算を照合する

四要素の加算を一組として見ると、floatの入力二つで32バイト、出力で16バイトを名目上使います。合計48バイトに加算4回なので、強度は4/48=1/12 FLOP/Bです。スカラで数えた一要素あたり1/12と同じです。SIMD化は命令あたりの要素数を変えますが、同じ配列の必要な値を自動で減らすわけではありません。名目強度が同じまま速くなる場合と、配置や再利用で転送量を減らす場合を、別の最適化として比較します。処理幅が増えただけでDRAM帯域の上限を越えられるという計算にはしません。

出力の精度と処理範囲を守ったうえで、命令と時間の両方を比較してください。

端数と依存の課題を解く

課題は、幅4の処理でn=10なら何組と何要素が残るかを説明することです。解答は、四つずつの組が二つ、残りが二つです。0〜7番の後に8、9番を処理します。出力配列の10番は存在しないので、そこへ書く処理を「端数を無視するだけ」と正当化できません。マスク付き命令を使う実装では、有効なレーンがどれで、そのISAがどんなアクセスを許すかまで確認します。端数の方式が変わっても、必要な10要素が正しいという契約は変わりません。

追加課題は、out[i]=out[i−1]+a[i]へ変えた場合です。解答では前の反復の出力を読む依存が生まれるため、元の独立加算と同じ単純な束ね方は使えないと説明します。並列prefix sumなど別のアルゴリズムを考えることはできますが、作業量、順序、丸めの契約を改めて検証する必要があります。連続した配列なら全て自動で同じSIMDになる、という予測は誤りです。要素の対応、依存、数値の契約、生成命令の四つを説明できたら実験へ進んでください。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 7

AI基盤へ進む · STEP 4

学習コースから次を選ぶ