NADEC 2011/07/23 - primitive: blog

http://kokucheese.com/event/index/12523/
NADEC というイベントで「12 CPU で 21000 個の球を衝突判定する話」と題した発表を行いました。
先日のデモをあれから色々最適化して 3 倍近く速くして、その経過を大雑把に解説したような感じです。

発表に使ったスライド。Actions > Show speaker notes で喋った内容も出ます。
https://docs.google.com/present/view?id=dhgfzcsr_16fqndcgff

デモのソースとバイナリ。最適化により、前回上げたのに比べて圧倒的に高速に動作するようになっています。
http://i-saint.skr.jp/tmp/atomic_ver_nadec20110723.zip
また、前回上げたのもそうですが、実行には OpenGL4.1 対応ビデオカード (GeForce GTX 460 クラス以降) が必要です。そうと知らず 4.1 を使ってしまったという。いずれ 3.0 系以前でも動くようにします…。

最適化してて感じたのが、シビアに速度追い求める場合、OOP は捨てなければならないとか (SoA 化 & SIMD 化)、割り算は全力で除去しないといけないとか、SIMD と相性のいいアルゴリズムを選ばないといけないとか、なるべくデータがキャッシュに乗るように意識しないといけないとか (間接参照なくすなど)、今時分においてもヘビーに CPU 密着型のプログラミングを強いられるということ。

学生時代「良いアルゴリズムは計算量が最小のアルゴリズム」「今はコンパイラが優秀なのでインストラクションレベルの最適化は特に意識する必要はない」などと教わったけど、現実はそこまで綺麗にはいかないようです。SIMD や並列化が絡むと計算量が最小=最速の前提は簡単に覆り、SIMD を活かすためのデータの SoA 化などはコンパイラはやってくれません。
むしろ高速化に SIMD や並列化が必須になり、メモリアクセスのペナルティが以前より大きくなった今現在、高速化の際の CPU 密着型プログラミングの必要性は以前より上がってるのかもしれず。

NADEC で行われた発表の内容については、wotakuro さんがまとめられています。
http://wotakuro.sakura.ne.jp/ginga/?p=47
意外にもプログラム関連のトピックはほとんどなく、普段あまり意識しない方面の話が新鮮だったり。今回も楽しいイベントでした。