Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                

aokomoriuta's blog

青子守歌のブログ

OpenCLやる前にSIMD使い切れっていう幻想

お詫び

では本編どうぞ↓

本編

若干話題に乗り遅れた感ありますが。

d.hatena.ne.jp

けど、SSEも知らねー、SIMDも知らねー、なんか俺が書いたアルゴリズム遅いけどとりあえずOpenCLとかで高速化しよっかなーとかね、甘ったれてんじゃねえよ。CPUをもっと使いきれよ。お前のアオいコードのせいでCPUが泣いてるよ。っていう話ですよ。

GPGPUなんてのはSIMDを使い切った後の話でしょ。

GPGPUするのにGPUのパワーとメモリが足りませんとか言う前にまずSIMDからだろ。

とか言われてたので、検証することにした（やっつけ）。

環境

対象

質量が2.5の10万点の質点（粒子）がそれぞれ別々の力を受け続けて等加速度運動する様子を時間刻み0.1で1000ステップ計算する、というよくあるパターン。

  • a_{t} = \frac{f_{t}}{m}
  • v_{t} = v_{t-1} + a_{t} \Delta t
  • x_{t} = x_{t-1} + v_{t-1} \Delta t + \frac{1}{2} a_{t} {\Delta t}^2

ソースコードは以下の通り。

結果

まとめ

ということで、SIMD使っても1.2倍ぐらいしか速くならないのに、OpenCL使えば2倍にもなる（C#は・・・まぁ、RyuJITが使えるようになればマシになるのかな）。

なので、SIMDを使い切るよりOpenCLを使って使い切ったほうが速そう。
SIMD使うにしても、少なくとも今回みたいにintrinsics使うぐらいにしといて、asmとか、ましてや機械語見てガリガリ最適化する暇があったら同じ労力でOpenCL使ってGPUにぶん投げたほうが速いことも多いと思うよ。

つまるところ、「SIMD使いきれ」とか「OpenCL最高」とか「C#でいいじゃん」とかじゃなくて、高速化したいなら問題に応じて適切な手法を選びましょう、ってことです。
それが認められなくなったら、引退したほうが良いと思います。

速いものが正義。

余談

  • 最適化の余地は充分に残したので、「いや、おれならもっと速くできる！」って言える最適化職人の皆様、お待ちしてます
  • AMDの石なんか使ってるからだ！って人は、他の環境で計測した結果を教えてください
  • 「OpenCL版の処理時間」をどこからどこまでにするか悩ましいところですが、今回はプラットフォーム取得する最初からデバイスからReadBufferするところ、という最大値にしときました。割にOpenCLに不利な条件ですが、これでも2倍です。単純な実行時間*1なら0.16秒とかなので10倍ですね（それはそれでOpenCLに有利すぎますけど）。プラットフォーム取得から全部をループの中に入れるのは流石に不公平すぎるんでやめときました。
  • @tanakmuraさんの言うとおり、自動ベクトル化はあんまり期待しないほうがいいと思います。少なくともVisual Studio 2013の時点では、自動ベクトル化させられるコードを書く方が大変です（やりかけて、これ意味ねーなーって思ってやめました）。

追記(2015/4/26)

List of device bit rates - Wikipedia, the free encyclopediaに書いてある通り、DDR3-1600だとだいたい13[GB/s]なので、16/13でだいたい1.3秒で合ってる感じですね。

GDDR5は48[GB/s]とかだったはずなので、もっと行くかなと思ったんですが、ビルド時間とか入っているので「全部コミコミで2倍」という結果になってんだろうと推測できます。

追記(2015/4/28)

「計算式が不利なのでは」「力が固定値っておかしい」との意見をもらったので、さらに実用的に力は位置の二乗に反比例するようにした（万有引力で万有引力定数とかがたまたま1だったと考えればいい）。

  • f_{t} = \frac{x_{t-1}}{{|x_{t-1}|}^3}

結果は以下の通り

確かにAVXでの加速率は1.5倍にあがったが、OpenCL側は4.25倍なので明らかにOpenCLの方が速い。
AVXでは倍精度浮動小数点のdotがやりづらいというのもあるんですが、それを除いても、先に述べたようにそもそもメモリ律速なので、いくらAVX使ってもDDR3使ってればそんなに速くはならないわけです。

なんだかこうして見てると、SIMD使い切るより、OpenCLにお手軽に投げたほうが速くなるしそっちのほうがいいんじゃないですかね？

追記(2015/4/29)

まず、複数スレッドだったらどうなるんだろうって話を何人かから聞かれました。
twitter上だと牧野さんとか。

あと、OpenCL側がソースのビルドまで含めるのはさすがに不公平だと言われました（Twitter上ではないので貼れないんですが）。


ということで、以下の修正を加えてみました。

  • なにもしない/AVXは、OpenMP使ってお手軽に多スレッドで動かした
  • OpenCLは、データ転送まで含めた実行時間にした

結果は

8スレッドで動かせば、4倍ぐらい速くなります*2。
よく考えれば昨日の追記の時点でsqrtとかが追加されてるのでメモリ律速というほどではなくなったんじゃないかな・・・。

あとOpenCLは、まぁビルドとか除けばこんなもんかなという感じです。ビルド時間は定数時間なはずなので、要素数とかループ回数とか計算量に依存しない部分は確かに含めないほうが正しいでしょう。

まだまだ差は縮まりませんね。

追記(2015/4/30)

何故か昨日あたりにじわじわと広がって結構な人からいろんな話を聞いたので色々追記します（追記はこれで最後にしたい）。

最初の式（メモリ律速）な状態でOpenMP化するとどうなるの？

やってみました。

こちらも約4倍ですね。
メモリ律速だったんじゃないんかって話なんですが、たぶんキャッシュに載ったりしたから速くなったんじゃないかなぁ・・・。

うちの環境で動かないんだけど！（アライン忘れてました）

すいません冒頭に書いた通りAVX使うのにアライン忘れてました。

結果は以下の通り。

sqrtとかしてる前者はまぁ結果は元とあんまり変わらないんですが、演算が少なくてメモリ律速な後者の状態だと、アラインとれたアドレスに確保したメモリに書いたり読んだりする分が増えて、まぁ全然速くならないよね・・・。

もちろん最初に配列確保するときにアライン取ってれば済む話でもあるんですが、動的確保でアラインとるのとかめんどいのと、そもそもAVXしやすいように条件変えるのは不公平だと思います。

この点、OpenCLでGPUに投げる場合は、別にアライン気にしなくていいし、演算もメモリ速度もCPU/DDR3よりとても速いので、使いきらなきゃ速くならない場合があるSIMD/AVXと比べて、載せたらとりあえず速くなるって素敵だなと思います。

N体問題にしたらどうなるの？

力固定にしろ中心力にしろ、各粒子は相互作用しない条件だと

みたいな高速化できちゃいますので、そういうことできないように、N体問題にして、相互作用させた場合はどうなるのかもやってみました。

SIMD化すると約3倍、OpenMPで8スレッドにすると4倍と、まぁ妥当な感じです。
そしてOpenCL側はキャッシュに高確率で当たり続けるので超高速です（CodeXLでプロファイルしてみたらヒット率96[%]ですって）。

SIMDをどれだけ使いきってもここから10倍は厳しいんじゃないですかね・・・。加えてOpenCL側も、今は1ワークアイテム内でループしたりしてるのを変えたりしたらもっと速くなる余地が残されてますし。

C#遅すぎない？


確かに、とりあえずstructにすれば、1秒減って6秒ぐらいになりました。

unsafeは、速くならないらしいです。
そもそも個人的にはC#でunsafe使うのあんまり好きじゃないので（互換性のためにどうしてもならともかく、性能のためにはなぁ）。

ちなみにRyuJIT CTP5入れてみましたがほとんど変わりませんでした。

JITが有効な場面でもないので仕方ないような気はします。

※C#については続きがあります。

aokomoriuta.hateblo.jp

*1:NDRangeKernel繰り返すだけの部分＝最小値

*2:Bulldozer系はFPUが4個しかないので