World’s first SIMD ray-triangle intersection in AVX?

by syoyo

ray_triangle_avx.png

https://ucille.svn.sourceforge.net/svnroot/lucille/angelina/
haskellmuda/examples/raytracingD/

isect.mu (algorithm description in MUDA)

isect.c (AVX code generated by MUDA compiler)

I’ve wrote possibly world’s first SIMD ray-triangle intersection code(except for Intel lab?) with Intel’s new AVX instruction by adding AVX codegen support for MUDA.

At this time, there’s no real processor which can execute Intel’s new AVX instruction, but the simulator, gcc compiler and assembler which supports AVX is available.

http://www.intel.com/software/avx/

http://gcc.gnu.org/svn.html
(Use ix86/avx branch)

http://www.tortall.net/projects/yasm/
(AVX ready assembler)

In my initial experience with AVX, I’ve found AVX can reduce mov* instructions about 30% compared to SSE version of identical code.
This is almost due to 3 operand form of AVX instruction format.

[Ja]

MUDA に AVX 命令を対応させて、たぶん実世界(Intel lab 以外で)では初であろう,
レイと三角形の交差判定処理を AVX で実装してみました.
1 レイと 4 三角形同時、もしくは 4 >レイと 1 三角形を SIMD で同時に処理しています.

もう少し時間があれば、レイトレくらいまで実装を進めたいところ
AVX 命令はまだ現状の CPU ではサポートされていないので実行できませんが、
シミュレータがあるので少なくとも AVX を使ったコードが正しく動くかを確認することができます.

コンパイラは AVX 対応の gcc ブランチを使いました.
ただ、.o までは出せないので、 .s まで出力して、アセンブラに AVX 命令に対応している yasm を使ってバイナリを作っています.

コンパイル手順はこんな感じになります.


$ mudah --avx isect.mu > isect.c         # .mu -> .c
$ gcc-avx -mavx -S isect.c               # .c  -> .s
$ yasm -f elf -p gas isect.s             # .s  -> .o
$ gcc-avx -mavx main.c isect.o           # .o  -> a.out

そして、以下のように AVX シミュレータで実行します.


$ sde -- ./a.out

シミュレータはデバッグやプロファイル情報の出力とかをしなければ、思ったより結構早く動きます.

SSE vs AVX

AVX は 3 operand 形式という新しい命令フォーマットになってよりフレキシブルになったということで、
SSE 版と AVX 版で、アセンブラ出力にどれくらい違いがでるのか調べてみました.

SSE 版は float x 4, AVX 版は double x 4 と, 精度に違いがありますがおなじアルゴリズム(上記のレイと三角形の交差判定)をコンパイルして出力を比較しました.

出力されるインストラクションはほぼ同一で精度のプレフィックスが違う程度なのを確認しました。この条件であれば SSE と AVX でのコード品質の違いを見るのに一番 fair な条件と言えるでしょう.

SSE 版と AVX 版、それぞれ 32bit と 64bit の場合の結果です.

SSE 版(32bit) 163 命令.

AVX 版(32bit) 140 命令.

SSE 版(64bit) 138 命令.

AVX 版(64bit) 109 命令.

SSE 版と AVX 版の命令数違いは主に mov 系命令による.
32bit では、SSE は mov 系は 80 命令, AVX は 63 命令,
64bit では SSE 62 命令, AVX は 42 命令と, AVX のほうがそれぞれ 17 命令, 20 命令少ない.

この mov 系命令数の差異のほとんどがレジスタ間コピー, たとえば
mov %xmm0, %xmm1
によるものである. 実際、AVX 版にはレジスタ間コピー命令がまったくない.

SSE は 2 オペランド形式なのでこのような命令が必要になりやすいが、
AVX は 3 オペランドなので,よりレジスタを使い回しやすくなり、レジスタ間コピーが必要無くなっているようです.
(ところで、2 operand 形式と 3 operand 形式では register pressure に影響はあるのだろうか.
直感的には 2 operand のほうがレジスタが割り当てにくく、また register spill がより多く発生しそうな気がする)

というわけで、AVX では 3 operand 形式により、無駄な mov 命令が減る傾向がある.
ただ、だからといって実際により高速にコードが動くかは分かりませんが、
すくなくとも相対的に少ない命令数によりデコード処理は早くなるので、デコードネックなアプリなら効果はあると思います.

まとめ

– 現状でも, AVX 命令を使うプログラムをシミュレーションで実行することができる.
アルゴリズムの移植や検証なら、今からでも行える.

– AVX のほうが同じ処理でも命令数が少なくなる. これは主に 3 operand 形式導入により、レジスタ間コピー命令が減るため.

– 見た目のアセンブラ出力も AVX のほうがきれい.
ただし SSE -> AVX でどれくらい実際の速度に差がでるかは実チップが出てくるまでおあずけ.

Advertisements