結果から言うと、コンパイラが頑張ってベクトル演算をつかって最適化しても、人力で命令を指定したときのほうが30％くらい速くなった。

以前N体問題でSIMD命令を使った衝突系の重力計算のコードを書いたことがある。その時にSIMD命令を使うと早くなるのかを検証したことがあるので、それについてここでまとめておく。

SIMD命令とは

Single Instruction Multiple Data streamsの略で、その逆の通常の命令群はSISDなどと呼ばれる。 SIMDを使うためには、まとまった長さのデータ配列を丸ごとベクトルとして扱う技術を要する。今回の検証ではIntelのAVX2 256bit長レジスタを使う命令を用いた。恩恵を見るために128bit長の時の結果も考慮に入れる。

SIMD命令の概略はここでもわかる。

SIMD化とは何か / Basics of SIMD - Speaker Deck

ここも非常に参考になった。SIMD命令の役割とか結構わかりやすい。

SIMDプログラミング入門（AVX-512から始める編） - Qiita

256ビットの単精度浮動小数点演算では、32ビットのレジスタが8つのベクトルレジスタを持つ。性能をフルに生かすためにはなるべくデータのロード、ストアはアドレスの境界は正しくする必要がある。ここでは各粒子の変数をSoA(Structure of Array)構造にすることで、多数の粒子の重力計算をレジスタを使い切った状態でほぼ完全に処理することができる。

また、重力計算のスキームの部分などの解説はここではしないが、SIMDの並列化の恩恵をちゃんと見れる環境である。詳しくはソースコードみて。時間があったら解説するかも。

結果

表には実行時間を秒で示している。512, 1024などは粒子数で、計算オーダーはO(N²)である。

テスト環境は、Ubuntu18.04LTS、i7-4790を用いている。

参考までに、マルチスレッドでの並列化による効果も併せて示しておく。コア数が増えるとスケーリングが低下しているのは、CPU全体のpower budgetが限られているためで、SIMD命令をかなり多く使ったとき特有の現象で電力不足で動作周波数が下げられてしまう。（詳しくはIntelのマニュアル見て。簡単に言えば、SIMD命令は電力をめちゃくちゃ食う！！）

CORE COUNT	SOLVER TYPE	512	1024	2048	4096	8192
4	optimized by compiler	0.89	1.18	2.21	6.34	21.92
4	128bit hand	0.92	1.28	2.65	8.03	28.56
4	256bit hand avx-2	0.87	1.11	1.94	5.2	17.64
2	optimized by compiler	0.94	1.44	3.33	11.2	40.35
2	128bit hand	0.98	1.64	4.06	14.17	53
2	256bit hand avx-2	0.91	1.31	2.76	8.84	31.39
1	optimized by compiler	1.07	2	5.56	19.57	74.66
1	128bit hand	1.17	2.41	7.1	25.8	100.08
1	256bit hand avx-2	1.02	1.73	4.47	15.3	57.64

考察

128ビット長から256長は大幅に性能が向上していることがわかる。ただ、コンパイラによる最適化も256ビット長の命令を使っているので、128ビット長の時より高速であるものの、256ビット長の手動で命令を指定した時ほど速度が出なかった。コンパイラにすべて最適化を任せたときよりシングルコアのとき30%くらい早い結果が得られた。ただ、思ったよりコンパイラの最適化が限られていることも同時に分かった。

コンパイラによる最適化

すべてのコードがベクトル演算に向けられたものではない。ベクトル演算のデータのロードストアはキャッシュのアライメント整列していることと、データ構造がベクトル演算化しやすくないとコンパイラが最適化できない。ここでは、SIMD命令のソルバーを単純に書き直したものをコンパイルしているので構造上はコンパイラもベクトル演算化できるはずである。

コンパイラの最適は-march=native -fopenmp -Ofast を用いた。これらのすべてを解説はできないが、Ofastは通常は勧められないオプションになる。このオプションは浮動小数点演算の実行結果に誤差を含むことを許容する(--ffast-math)。その分高速化できるのだが、SIMD命令自体が本来の計算結果から誤差を含む可能性が命令規約に含まれているからである。通常の最適化O2までは期待通りの動作になるだろう。逆にOfastまでつければ、誤差を許す代わりに積極的に誤差が含まれるベクトル演算命令を使うようになり、コンパイラができる最大限の最適化ができるようになる。

まとめ

やはり人力のほうが速度は出やすい。すべての命令セットが使えてない感じが見受けられた。ループアンローリングからベクトル演算化、リスケジューリングまで、ある程度機能はしているが完全ではない感じ。ループアンローリングの回数が制約されているせいかもしれない。ループアンローリングの数が制限されていると、ここら辺の恩恵が小さくなってしまう。また、iccがベクトル演算化が優秀とどこかで聞いたことがあるので、試してもいいかもしれない。