一命令の中で複数の値を扱う
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になる、という予測は誤りです。要素の対応、依存、数値の契約、生成命令の四つを説明できたら実験へ進んでください。