この記事は GPGPU Advent Calender の二日目の記事です。
二日目の内容がコレかよ！というみなさんのつっこみが本編です。以下の内容はオマケとなります。
http://pcl.intel-research.net/publications/isca319-lee.pdf
時は2010年…くーだ使えば100倍とか1000倍とか速くなるんでしょ？なんでCPUそんな遅いの？などと、世界中でボロクソに言われたIntelは、ついにブチ切れて、「お前らは全員間違ってる！俺がその間違いを正してやる！」という内容の論文をISCAに投稿するのだった…
という事情だったのかどうかは知らないですが、内容としては、↓このグラフが全てを物語っていて、
「GPUだと100倍速いとか言うけど、あれはCPUのコードを最適化してないからで、CPUも最適化すれば、平均たったの2.5倍しか速くならない」、というような内容です。
まあ、2.5倍とか実際結構大きいので、それを"only 2.5X"とか書いてるあたり、色々な恨みがあるのかなァ…？とか余計なことを考えてしまいますが、
- 比較コードは、CPUもGPUも既にpublishされてるものと同等か、それ以上のものを用意している
- それぞれのコードについて、どの部分で差が付いているか、詳しく解析している
といった点は、内容としては大変素晴らしいと思うので、GPGPU研究者はこの姿勢を見習うべきだと思いますし、景気の良い数字に騙されてGPUを買わされそうになっている人は、「こういう数字もあるみたいだけど実際どうなの？」と問い詰めたりすべきだと思います。(個人の見解で所属するアレのソレやらではありません)
と、いうような話は、既にAndoさんが書かれてる(http://news.mynavi.jp/articles/2010/06/30/isca2010_intel/) ようなので、そちらを読むべきだと思いました。
で、ここでは、その中身の解説といきたいのですが、
- 中身の詳細は元の論文を参照してもらったほうがいい
- 日本語訳も断片的ですが、すでに書かれたものがある : http://d.hatena.ne.jp/t_azu/20100628/1294789282
みたいなので、ちょっと変えて…
この論文は、4.3 Performance Analysis のところで、各パフォーマンス特性から見たプログラムの解析をしているのですが、ここでは、各プログラムのパフォーマンスの解析というような内容にして、紹介していこうと思います。
プログラム自体の特性は、2. THE WORKLOAD: THROUGHPUT COMPUTING KERNELS に書いてあって、つまり、以下は、その2. と 4.3を混ぜて、みたいな内容になります。なお、各項目に付いてる性能は、Table 3からひっぱってきたもので、ratioはその値をもとに手元で計算しています。
SGEMM : 行列積
| GTX280[GFlops] | i7-960 | ratio |
|---|---|---|
| 364 | 94 | 3.87 |
みんな大好き行列積の単精度版です。
計算量はO(n^3)で、適切にブロック化すればメモリアクセス量は、O(n^2)です。ブロック化のやりかたは、CUDA C Programming Guide の Shared Memory のところに詳しく書いてあります。
データが綺麗に並んでいるので、SIMDの性能が出しやすく、演算あたりのメモリアクセス量もオーダーが小さいので、理論計算性能に近い値を出すことができます。
GTX280 の理論性能は、933[GFlops]ですが、これはFMA + MULを実行した場合の値で、SGEMMでは、FMAの分しか出ないので、理論性能は622[GFlops]となります。さらに、http://mc.stanford.edu/cgi-bin/images/6/65/SC08_Volkov_GPU.pdf によると、shared memory をオペランドに使った時のスループットの制限から、理論値の60%程度の性能しか出ないため、結果として、理論性能102.4GFlopsのi7との比は、このぐらいになるようです。
なお、Fermi世代では理論性能がFMA+MULではなく、FMAの数になったため、理論性能以上に実効値が良くなってると思われます。さらに、詳細はよくわからないですが、Kepler のホワイトペーパー(http://www.nvidia.com/content/PDF/kepler/NVIDIA-Kepler-GK110-Architecture-Whitepaper.pdf) によると、Kepler 世代でDGEMMの実効効率が80%に向上した、と書かれているので、ここでも、更に実効性能が良くなってると予想されます。
MC : モンテカルロシミュレーション
| GTX280[billion paths/s] | i7-960 | ratio |
|---|---|---|
| 1.4 | 0.8 | 1.75 |
巨大な一次元配列に対して要素づつにそこそこ重い演算をやります。SIMDが効くし、メモリアクセスもしないので、理論性能がほぼそのまま出ます。中の式は、CUDAのサンプルに入っているものを使っているようです。
ここでは、倍精度演算を使っており、そもそも理論性能が1.5倍程度しか違わないため、このぐらいの結果になっています。(CUDAのサンプルが倍精度を使っているからだと思われます)
Fermi以降の世代なら倍精度が速いものも用意されているので、もうちょっと差が開くと思われます。
Conv : 2D画像 Convolution
| GTX280[million pixels/s] | i7-960 | ratio |
|---|---|---|
| 3500 | 1250 | 2.8 |
2D画像のConvolutionです。
フィルターをかけるサイズによって性能特性が変わるのですが、普通は、再利用するデータがL1キャッシュとかsharedに入るサイズぐらいなので、計算律速になります。
4.3.2 には、理論性能が出るけどFMAがutilizeされるかどうかで理論性能比変わるから、こんなもんじゃね？とか書いてあるように読めるのですが、ConvってFMA効くような気が…というかそもそもi7の理論性能もMUL+ADDの値だから条件変わらないような…。GT200世代だと、sharedを使う必要があって、その分の影響が出てると勝手に推測してますが、よくわかりません。sharedの問題だとすれば、Fermi以降はキャッシュがあって余計な操作減るので、もうちょっと差が開く可能性があります。
FFT : Final Fantasy Tactics
| GTX280[GFlops] | i7-960 | ratio |
|---|---|---|
| 213 | 71.4 | 3.0 |
Fourier Transform を Fast にやります。(何回勉強しても何が起こってるかいまいち理解できないというのは秘密だ)
アクセスパターンがややこしい + 計算結果を通信でやりとりしないといけないため、プログラムの書きかたによって、計算律速になったり通信律速になったり、メモリ律速になったりする…という印象がありますが、様々な努力 [ http://hpc.sagepub.com/content/2/1/82.short が参考としてあげられてる] によって理論性能に近い値が出るようになってる…という印象があります。ここで使ってるのは、CUFFT vs MKL のようです。
これもConvと一緒で、FMAのutilizationを考えると理論性能比そのまま出てるんでは？みたいに書かれてますがこれもFMA効くような…謎。
ここには書かれてないですが、benchffthttp://www.fftw.org/benchfft/の結果http://www.fftw.org/speed/とかも見てて楽しいかもしれません。プロットスクリプトは他でも使われていて、http://www.sharcnet.ca/~merz/CUDA_benchFFT/ とかでCUFFTの比較が見られるようです。
SAXPY : かけてたす
| GTX280[GB/s] | i7-960 | ratio |
|---|---|---|
| 88.8 | 16.8 | 5.3 |
かけざんたしざんを一回づつやるだけ http://en.wikipedia.org/wiki/SAXPY 。計算が少なすぎるので配列がキャッシュに入らない場合、メモリ律速になります。
GTX280のBandwidthが141[GB/s]、i7-960が32[GB/s]で4.4倍の差があります(4.3.1 には 4.7Xとか書いてあるが…？)。ほぼこれが出ています。
LBM : Lattice Boltzmann methods
| GTX280[million lookups/s] | i7-960 | ratio |
|---|---|---|
| 426 | 85 | 5.0 |
名前しか知らない(というかこっから先はかなり理解が怪しい)。なんかLattice Boltzmann methodsを使って流体が云々と書いてある。アクセスパターンはConvと似てるけど参照データが多くてメモリ律速になると書いてある気がする。
SAXPYと一緒で、bandwidthの差がそのまま出ているようです。
Solve : 制約ソルバ
| GTX280[FPS] | i7-960 | ratio |
|---|---|---|
| 52 | 103 | 0.5 |
constraint solverで、剛体シミュレーションのコア部分とのこと。中身は http://download.intel.com/technology/itj/2007/v11i3/8-simulations/vol11-i3-art08.pdf [14] だと書いてあります。
constraintごとの処理に並列性がありますが、その中の計算量が少なく、同期のほうに時間がかかると書いてあります。
i7のコア間通信と比べると、GTX280はブロック間の通信は非常に重い処理となるため、このSolveではGTX280のほうが"1.9X slow down"だと(太字で)書いてあります。
まあ並列化の方法として上げている論文[14]がIntelの人が書いたものなので、GPUの人は、なんかうまい反論をすべきだと思いますね。というか探せばあるかもしれません。
SpMV : Sparse Matrix-Vector Multiplication
| GTX280[GFlops] | i7-960 | ratio |
|---|---|---|
| 9.1 | 4.9 | 1.9 |
Sparse Matrix-Vector Multiplication ベクトルと疎行列のかけざんをします。なんでgemmはdenseなのに、Matrix-Vectorはsparseなの？よくわかりません。詳しい人に聞いてください。"heart of many iterative solvers"と書かれてます。
Sparseの表現には色々あるけど、"compressed row storage"と呼ばれるものがよく使われると書いてあります。最適化すると、メモリ律速になるようです。
メモリ律速なのに、上のLBMやSAXPYほど性能差がありません。これは、GTX280のsharedが小さいために、vectorやcolumn indexがon-chip shared bufferに乗らなかったのに対し、i7では、vectorと、column indexの半分がキャッシュに乗ったのでi7の方が追い上げを見せたからだ、と書かれています。
Fermi以降は、L1 + sharedで64KBあって、4倍になっているので、もうちょっと差が開くかもしれません。(それでもi7と比べると計算性能に対してキャッシュ容量小さすぎなのでどうなのかわからないですが)
GJK : 衝突検出
| GTX280[FPS] | i7-960 | ratio |
|---|---|---|
| 1020 | 67 | 15.2(グラフでは14.9とか書いてるが謎) |
剛体の衝突を検出するアルゴリズムです。http://angra.blog31.fc2.com/blog-entry-115.html あたりが参考になる気が。全くどうでもいいですが、最近、成仏の鎌をJKと略すと知ってカルチャーショックを受けました。
多分内容は面白くて、cube-mapを使うことでこれを高速化する手法 http://www.deepdyve.com/lp/acm/rigid-body-collision-detection-on-the-gpu-LtHiaypAnD?key=acm があって、その効果で、14.9倍という数字を叩き出してる、と書いてあるのですが、いまいち理解できず…残念。あとこれIntelの人が書いてるというのもおもしろい点ですね。
あと、coalesce能力を持った scatter-gather も効果があると書いてあります。
Sort : なんか
| GTX280[million elements/s] | i7-960 | ratio |
|---|---|---|
| 198 | 250 | 0.8 |
詳細はよくわからないですが、Sortと呼ばれる処理をするらしいです。Sortの世界は日進月歩なため、真面目に勉強しても2、3年経つと知識が全く役に立たなくなることはよくあることです。僕は真面目に勉強したことないので全然わかりませんね。
i7では、スカラ処理を比較的よく使うradix sortを使っていますが、GTX280では、スカラ処理が遅いので、splithttp://mgarland.org/files/papers/gpusort-ipdps09.pdf と呼ばれるソートを使っているとのことです。ただ、split は、計算量がradix sortよりも増えてしまうため、結果として、i7-960のほうが速くなるようです。
ただ、Sortアルゴリズムは、日々改良が続けられているので、そのうち状況は変わるかもしれません。もしくは、既に変わってるかも。真面目に考えるなら、一度調べなおしたほうがいいと思います。
RC : Ray Casting
| GTX280[FPS] | i7-960 | ratio |
|---|---|---|
| 8.1 | 5 | 1.62 |
Ray Castingと呼ばれる3Dモデルを描画する手法のひとつです。多分レイトレと似たようなものだと思われますが、 http://en.wikipedia.org/wiki/Ray_casting によると、物体に光が当たった時に、反射してその光源を探していくのがRay Trace、それをやらないで、最初に当たった物体の形状を描画するのがRay Casting、という区別になるようです。
計算自体は、SIMD化可能ですが、使うデータがメモリ上のどこにあるかわからないため、SIMD化するにはデータのgatherが必要になります。ソフトウェアによるgatherを使ったSSEでは0.8X〜1.2X程度の高速化しかできなかったと書いてあります。
また、使用するデータが広大なメモリに分散しているので、GTX280のgatherに付いてるcoalesce機能もそれほど効果がなく、倍精度の理論値の差(1.5X)程度の差しか出ないようです。
Search : 木の探索
| GTX280[million queries/s] | i7-960 | ratio |
|---|---|---|
| 90 | 50 | 1.8 |
DBのコア部分のツリーの探索です。Intelの人が提案するFASTと呼ばれる構造を探索する性能です。FASTの日本語の解説は http://d.hatena.ne.jp/maropu/20100828/1282993147 あたりが参考になります。SIMD/キャッシュ/メモリという階層構造にあわせて木の階層構造を作る、というものです。
どこにアクセスするか予測できないため、キャッシュが大きいi7のほうに有利に働くようで、特にデータのサイズが小さい場合は、i7 が "2X faster than GPU" だと書いてあります。また、GPUだとSIMDのレーンを超えたデータ通信が無いなどの命令レベルでの問題から、GPUではデータのサイズに関係なく常に計算律速だと書いてあります。
Keplerだと、warp内でのshuffleが可能になったので、状況は変わってるかもしれません。
Hist : ヒストグラム
| GTX280[million pixels/s] | i7-960 | ratio |
|---|---|---|
| 2583 | 1517 | 1.7(本文は1.8と書いてある？) |
ヒストグラムです。
衝突検出できるベクタのストアhttp://www.cs.utexas.edu/users/ckkim/papers/glsc_isca2008.pdf があればSIMDを有効活用できるのになー。とか書いてありますが、まあ無いものはしかたありません。
atomic update supportはi7のほうが充実してるけど、i7もGTX280もatomic update使わないで、コアごとにローカルにカウントして最後にreductionしたほうが速いのでそうしていると書いてあります。
で、reductionするときに、
- コア数多いほうがreductionのコスト多いのでGTX280が不利
- GTX280のほうがSIMDのレーン間のアクセスが弱いので不利
というふたつがあるので、全体で1.8Xにしかならないと書いてあります。Searchと同じくKeplerならshuffleできるので状況は変わってるかもしれません。
Bilat : Bilateral Filter
| GTX280[million pixels/s] | i7-960 | ratio |
|---|---|---|
| 475 | 83 | 5.7 |
エッジを残しつつボカシをかけるフィルタらしいですねえ(疲れてきた)。
expとかの超越関数を使い、計算量が多いと書いてあります。
超越関数なのですが、CPUはちゃんと精度計算するのに対し、GPUだと多少精度捨ててハードウェア使ってるので、理論性能の3Xよりも差が大きくなってると書いてあります。(CUDAを使ったなら精度はほぼ同じ条件な気がするが？)
i7だと約66%程度の時間が超越関数の計算に使われていて、i7 のほうも、GTX280と同じように、超越関数を最適化すれば、差は縮んで約3倍程度と、理論値の差と同じくらいになるとのことです。
Conclusion
(元の論文だと、最適化技法とか、これからのCPUに必要なハードウェアとかについて書いてあるので、Conclusionもそういう話になってるのですが、今回はそのあたりには触れてないので、適当な蛇足Conclusionを付けておきます)
というような内容でした。個人的には、Micro-benchmarking the GT200 GPU と並んで全GPGPUプログラマが読むべき内容だと思うので、面白そうだと思った人は元論文を読むといいと思います。
あと発表とかでCUDAなら100倍！！とか言ってる人を見かけたら、「それCPUのほうも最適化したらどうなるんですか？」と聞いてあげるようにしましょう。
