Lee et al. (2010), Debunking the 100X GPU vs. CPU Myth: An Evaluation of Throughput Computing on CPU and GPUのメモ(書きかけ)

要点となるであろう部分だけ日本語でまとめておく。Lee et al. (2010)

1. Introduction

この論文の要点は以下の3つ。

  • 過去に多数存在した、GPUは100倍から100倍もの性能を持つと主張する論文の内容を再検討した。検討において、CPUとGPU両方を最適化した。その結果、GPUは平均2.5倍の性能をCPU比で持つことがわかった。つまり、CPUとGPUは同じ土俵(ballpark)にあるものなのだ。
  • 並列化(並行化、の方が良いのかな)の手段にkernel(ここではアプリケーション、プログラムといった意味らしい)の実効性能がどのように依存するかを、系統的に分類してまとめた。
  • CPUとGPUの性能の違いを分析し、アーキテクチャの中で、性能に影響を与える主要な部分を特定した。

2. The workload: throughput computing kernels

14個のkernelで検証していて、3つの特徴で分類している。

  1. 演算能力とメモリ要求
  2. メモリアクセスの規則性。これはデータレベルでの並列化(SIMD処理)の効率に影響。
  3. 処理の粒度。粒度の荒さ細かさは、並列の同期処理のオーバヘッドの大小に影響する。

扱っている14個は、SGEMM, MC, Conv, FFT, SAXPY, LBM, Solv, SpMV, GJK, Sort, RC, Search, Hist and Bilatである(きっと書く)。
表1には、14個のkernelについて、SIMD、TLP(Thread Level Parallelism)の性格、その他特徴についてまとめてある。
【レポート】ISCA 2010 - IntelがGPUはCPU比で"100倍"速いという説を事実誤認として証明 (1) IntelがCore i7よりGPGPUの方が速いことを認めた? | エンタープライズ | マイコミジャーナルから表のみ拝借↓

計算カーネル 用途 SIMD スレッド並列単位 特徴
SGEMM 線形代数 レギュラー 2Dタイル タイリングすると計算バウンド
Monte Carlo 金融工学 レギュラー パス 計算バウンド
Convolution 画像解析 レギュラー ピクセル 計算バウンド
FFT 信号処理 レギュラー 単位FFT 計算バウンド
SAXPY 内積計算 レギュラー ベクトル バンド幅バウンド
LBM タイムマイグレーション レギュラー セル バンド幅バウンド
Constraint Solver 剛体運動 ギャザー/スキャッタ コンストレイン 同期バウンド
SpMV 疎行列計算 ギャザー 非ゼロ要素 バンド幅バウンド
GJK 衝突検出 ギャザー/スキャッタ オブジェクト 計算バウンド
Sort データベース ギャザー/スキャッタ 要素 計算バウンド
Ray Casting ボリュームレンダリング ギャザー 光線 4〜8MBワークセット(第1レベル)、500MB以上(最終レベル)
Search データベース ギャザー/スキャッタ クエリー 小規模ツリーは計算バウンド、大規模はバンド幅バウンド
Histogram 画像解析 競合検出が必要 ピクセル リダクション/同期バウンド
Bilateral 画像解析 レギュラー ピクセル 計算バウンド
1. SGEMM

線形演算の集合。代表的なもの。単精度演算。規則的なメモリアクセス。SIMD演算向き。スレッド化が容易。行列を部分行列に分割して処理することも用意。処理を部分行列の中で独立に行う事が可能。行列の大きさの3乗のオーダの演算量であり、メモリアクセスは2乗のオーダ。メモリアクセスが追いつかないということはなくて、律速となるのは演算能力。TLP: Across 2D Tiles

2. MC

金融の事例みたい。一般には演算能力が律速。メモリアクセスは規則的で、SIMD向き。倍精度演算。TLP: Across paths

3. Conv

画像処理みたい。単純な積和演算で、メモリアクセスは近隣への規則的なもの(GPUぽい)。各ピクセルは独立に処理されるので、SIMDでもスレッドでも並列は確保出来る。B/Fは、画像処理のフィルタに依存する。たいていは、演算速度が律速。sliding-window-styleな?とか次元を変換するような処理ではまた違ってくる。TLP: Across pixels

4. FFT

時系列データを波数に変換。その逆も。離散フーリエ変換(DFT)を高速に処理するのがFFTFFTについてはかなり研究が進んでいる。数値モデル、ハードウェアが違ってもその主要な部分は変わらない。折りたたんでいくという、お決まりの方法である。演算量はNlogNのオーダ。演算は簡単だが、メモリアクセスが複雑でSIMD化を困難にしている。FFTが演算依存かメモリ依存かはサイズに依存する。TLP: Across smaller FFTs

5. SAXPY

BLASに含まれるもの。ベクタ長が長い(多次元配列)の場合は、バンド幅に依存する。ベクタ長が非常に短い場合、水平方向のreductionnの処理に依存する。TLP: Across vector SIMD: regular

6. LBM

Latice Boltzman method*1で、流体力学の問題。粒子同士が衝突した後は、各粒子が独立して運動するので、並列計算に向いている。ナビエストークス方程式を使う代わりに、離散化したボルツ万方程式を用いて、ニュートニアン流体の流れを解いている。離散化した時間間隔が1つ進むたびに、D3Q19(と言う格子があるらしい)格子では、3次元格子全体をscanした後に各格子において新しい分布関数を、隣接格子から計算する。
計算量、データ量共に格子数の一次のオーダ。処理の単位は、隣接する格子データで、データの再利用は少ないのでキャッシュが効かなくて、(その都度データを取りに行くことになるので)バンド幅依存である。
LBMはメモリバンド幅依存。TLP: Across cells SIMD: Regular

7. Solv

Solvは、ゲームでの物理計算の主要部分である。
TATは同期に制約を受ける。

3. Today's high performance compute platforms

Core i7 960とGTX280で比較検証した。

3.1 Architectural Details

3.1.1 Intel Core i7 CPU

3.2GHzで4core。L3までキャッシュ有り。

3.1.2 Nvidia GTX280 CPU

SM(streaming multiprocessers)はそれぞれ8coreを持つ。スレッドのウォープ(Warp)という単位で、SIMD処理はプログラマの見える形になっている。メモリアクセスのレイテンシを隠蔽するために、数百のスレッドを同時に走らせる事が可能となるハード構成になっている。

3.2 Implications for Throughput Computing Applications

これら2つのアーキテクチャの特徴、相違点と実効性能に影響を与えるであろう要素について。

Processing Element Difference

CPU coreは、様々な用途に対応。1スレッドでの実行にも適するようになっている。1スレッドでの性能を出すために、アウトオブオーダ実行により、命令レベルでの並列化を行っている。それぞれのCPU coreでは、SIMD処理をサポートし、複数の処理を同時に行う事が出来る。また、優れた分岐予測の機能も備えている。そのため、ある大きさのダイサイズのなかに置けるcoreの数がどうしても制限されてしまう。
それに対して、GPUでは、複雑な機能を廃する代わりにたくさんのスレッドを走らせる事が可能な演算器をダイの中にたくさん配置している。1つのフェッチ機能と8つのスカラ演算器で構成されている。それぞれの命令は、1ウォープ(32スレッド)を単位とし、8つのスカラ演算器が4サイクルで実行される。

Cache size/Multi-threading

CPUはキャッシュメモリでメインメモリのレイテンシを隠蔽。
GPUは、計量のスレッドを大量に走らせる事でレイテンシ隠蔽を行っている。GPUもキャッシュはあるが、CPUのそれに比べると小さい。

Bandwidth Difference

Core i7は32GB/s、GTX280は141GB/sと、約4.7倍の差。しかし、B/Fで比較すると、約1/1.6倍で同程度に小さくなる。このときのFは、SFUでの演算性能は含んでいない。

Other Differences
  • CPUは同期処理が速い
  • CPUはレジスタ内でのデータの入れ替えが速い。GPUでは、レジスタでのそのような処理機能はないが、共有メモリがあるけど、オーバヘッドが大きくてよろしくない。
  • GPUではgather/scatterに強く、それはSIMD処理の性能を向上させる。

4. Performance Evaluations on Core i7 and GTX280

Core i7とGTX280の実効性能を評価し、その結果を分析する。

4.1 Methodlogy

OSはSUSE Enterprise Server 11。PC1333 DDR3 6GB、M/BはIntel DX58SO。Core i7 960 3.2GHz。GTX280は同じM/Bに載せている。1.3GHz。GPUのドライバは19.180で、CUDA2.3。
計測では、アーキテクチャの違いが演算速度に与える影響を見たいので、データ転送速度は考慮したくない。よって、ここでは、GPUへのデータ転送時間(PCI-Express16を通過する際のそれ)は考慮していないので、この論文の結果はGPUでの実効性能の最も理想的なものと考えて欲しい(ずいぶん控えめだな、というか、Intelに取って都合の良い論文と思われたくなかったんでしょうな。転送時間まで入れるとどんなもんなんでしょ?)。
GPU、CPUの計算において、共に最適化を個別に合わせて行っている。

4.3 Performace Analysis

CPUとGPUの性能の違いを分析し、アーキテクチャの内、性能に影響を与える主要な部分を特定した。基本的な2要素「演算性能」「メモリバンド幅」のどちらかに強く依存するkernelについてまず述べる。続いて、「不規則なメモリアクセス」「同期の速さ」「特定の関数の性能」の要素の影響を特定する。

4.3.1 Bandwidth

どんなkernelでも、ある程度のband幅は必要である。バンド幅に依存するかは2つの要素に依存。

  1. kernelがバンド幅を使い切るに十分な計算をすること
  2. カーネルワーキングセット(メモリ使用量)が、CPU上のメモリバッファ・キャッシュの大きさに収まりきるか。

SAXPYとLBMは、メモリアクセスに演算が満たない。メモリアクセス速度に強く依存。

4.3.2 Compute Flops

メモリバンド幅依存でないなら、1cora辺りの性能が上がる成り、コア数が多くなればその恩恵を受ける。出来ないkernelもある。SGEMM、MC、Conv、FFTとBilatは、演算性能依存であることを確認した。そのうち、SGEMM、Conv、FFTは2.8から4倍の性能をGPUが。これは、GPU・CPU理論演算性能比とオーダ的には同じもの。理論での比は3(倍精度)-6(単精度)倍。理論比よりも小さくなっている。これは、GPUでは実効性能が出にくい傾向があるから。そういう論文も出ている。ここでの結果(SGEMMでのGPU実効性能)は、先行研究と似たものである。MCは倍精度演算なので、こんなもの。Bilatは、GPUには、Bilatに合った関数を持っているので、良い実効性能となる。Sortは、データ長に依存。
14のカーネルの内、7は演算性能依存。その他について以下述べる。

4.3.3 Cache

4.3.1で示したように、

4.3.4 Gather/Scatter
4.3.5 Reduction and Synchronization

Solvは同期が律速

4.3.6 Fixed Function

5.1 Platform Optimization Guide

CPUはクロックの増加の恩恵だけで良かった時代は終わって、十分に並列化をしないと性能がない。LBMでGPUがCPU比で114倍でたとの事例が過去にあるが、CPUを十分に並列化してやって、GPUにも同様に行うと、両者の差は5倍程度になる。以下、kernelの最適化で得られた、platformごとの最適化方法を述べる。

CPU optimization
GPU optimization

5.2 Hardware Recommendations

計算効率に影響を与える部分について説明。

High compute flops and memory bandwidth

演算能力を上げる方法は2つ。クロックを上げるか、SIMDの数を上げるか。

Large cache
Gather/Scatter
Efficient synchronization and cache coherence
Fixed function units

4.3のPerformance Analysisをもとに、各kernelに適切なhard、その活用についてまとめる。

6. Related work

7. Conclusion

Core i7 960とGTX280の性能を分析した。両者間には、これまでに報告されたほどの(100倍、1000倍と言った)性能差はない。これまでの検討で何故大きな差が報告されたのか。性能の低いCPUとの比較だった、またはCPUの最適化が不十分だったから、など。
CPUの最適化は、複数のスレッドでの処理、キャッシュの有効利用(コンフリクト回避)、メモリアクセスの再構成(SIMD処理の効率化向上)
GPUの最適化は、全体での同期を減らすこと、共有メモリの利用の2点が重要。
この比較で、実効性能に影響を与える要素を特定した。  など。
今後は、電力比でのCPU、GPUの性能について検討するつもりだ。

*1:「 流体 = 衝突と並進(移動)を繰り返す多数の粒子の集合体」と捉え,粒子の運きを計算することによって流体の運動を求める数値計算法で、ナビエストークス方程式の基で、希薄気体力学で用いられるBoltzmann方程式の考え方を取り入れた数値計算法、らしい。Lattice Boltzmann Methodの紹介 http://www.mh-1.scitec.kobe-u.ac.jp/rd/boltzman/lb_chap1.htmから