“A parallel hashed Oct-Tree N-body algorithm” (http://dl.acm.org/citation.cfm?id=169640) を論文セミナーで学生に紹介してもらった。案外細部は覚えていないもので、発見があった。
この論文は並列ツリーコードの新しいアルゴリズムを提案し、Intel Touchstone Deltaでの性能評価を報告した論文である。SC’93で発表された。512プロセッサで、Cold Dark Matterモデルを計算した場合の実効性能は5 - 6 GFLOPSとなった。
Seciton 4の最後の部分：
If we count only the floating point operations performed in the force calculation routine as “useful work” (30 flops per interaction) the overall speed of the code is about 5-6 Gflops. However, this number is in a sense unfair to the overall algorithm, since the majority of the code is not involved in floating point operations at all, but with tree traversal and data structure manipulation. The integer arithmetic and addressing speed of the processor areas impoctant as the floating point performance. We hope that in the future, evaluation of processors does not become overbalanced toward better floating point speed at the expense of integer arithmetic and memory bandwidth, as this code is a good example of why a balanced processor architecture is necessary for good overall performance.
この実効性能は、ツリー法で計算した粒子相互作用の浮動小数点演算数のみをカウントした場合である。単純に粒子相互作用だけを計算した場合の性能は14 GFLOPSくらいになるのに対して、実効性能はそれの30％しかない。その理由は、粒子間相互作用以外にも、まずツリーを構築する時間が必要で、さらにツリーをたどる時間やプロセッサ間通信のためにも時間がかかるためである。そのため、引用部に書いてある通り、浮動小数点演算性能だけでなく、主にアドレス計算に使われる整数演算や、このツリーアルゴリズムの場合にはshiftや論理積のような演算の性能もcriticalになってくる。
Instruction Mixの実際
では最近のGPUで似たような計算をやるとどうなるのか。直接的な結果はさておき、浮動小数点演算数とその他の命令の割合を調べてみた。これはInstructin Mixと呼ばれている。ツリーをたどりながら重力を計算するkernelをOpenCLで実装し、様々な命令の割合を調べてみた。ターゲットはSourthern IslandアーキテクチャのRadeon HD7970である。
VL=1
| 命令種類 | 命令数 |
|---|---|
| 浮動小数点演算 | 25 |
| 整数演算 | 60 |
| load/store等 | 42 |
| 合計 | 129 |
VL=2
| 命令種類 | 命令数 |
|---|---|
| 浮動小数点演算 | 50 |
| 整数演算 | 76 |
| load/store等 | 52 |
| 合計 | 172 |
VL=4
| 命令種類 | 命令数 |
|---|---|
| 浮動小数点演算 | 100 |
| 整数演算 | 104 |
| load/store等 | 72 |
| 合計 | 252 |
VL=8
| 命令種類 | 命令数 |
|---|---|
| 浮動小数点演算 | 128 |
| 整数演算 | 146 |
| load/store等 | 113 |
| 合計 | 331 |
考察
このカーネルは単精度演算を使っているので、浮動小数点演算は命令のpostfixが”f32”のものを指す。整数演算は”i32”, “b32”, “b64”等のpostfixの命令。load/store等は、文字通りのloadとstore命令に加えて、”mov”のpostfixがついている、レジスタ間コピー命令等を含む。一部命令の数え方が重複しているので、総和が合計には一致しないことに注意。
“VL”はkernelのベクトル化率。大きくすれば、ロード当たりの演算数が増えるが、レジスタ利用量が増える。実験によると最適なのはVL=4 or 8である。浮動小数点の割合は50％を下回っており、VL=1,2,4,8の時それぞれ、19.4％、29.1％、39.7％、38.7％になった。実験してみるとVL=4とVL=8ではあまり性能が変わらない。これは単に命令の種類ごとに数を数えているだけであり、分岐やループを考慮していないので、実際に実行される命令ごとの割合を調べると多少は違いがあるだろう。が、傾向としては、割合明確であった。WS93論文でもは実効性能が理論性能の30％程度である。彼らも詳細は異なるが、ここでいうベクトル化に相当することをしている。一方GPUでのツリーコードの実効性能は30命令換算ではVL=4の時に300 GFLOPS程度になる(ツリー構築やGPUとのI/Oの時間を含んだ換算)。7970の理論性能はFMA命令を使う場合は3.7 TFLOPSである。WS93の時代はFMA命令はなかったので、そこを考慮すると、我々の実効性能は16％くらいになる。分岐命令に弱いというGPUアーキテクチャではあるが、あまりかけ離れた数字ではない。汎用プロセッサでも分岐命令はそれなりのオーバーヘッドになるので、そんなもんかも。