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つ。
2. The workload: throughput computing kernels
14個のkernelで検証していて、3つの特徴で分類している。
- 演算能力とメモリ要求
- メモリアクセスの規則性。これはデータレベルでの並列化(SIMD処理)の効率に影響。
- 処理の粒度。粒度の荒さ細かさは、並列の同期処理のオーバヘッドの大小に影響する。
扱っている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
3. Conv
画像処理みたい。単純な積和演算で、メモリアクセスは近隣への規則的なもの(GPUぽい)。各ピクセルは独立に処理されるので、SIMDでもスレッドでも並列は確保出来る。B/Fは、画像処理のフィルタに依存する。たいていは、演算速度が律速。sliding-window-styleな?とか次元を変換するような処理ではまた違ってくる。TLP: Across pixels
4. FFT
時系列データを波数に変換。その逆も。離散フーリエ変換(DFT)を高速に処理するのがFFT。FFTについてはかなり研究が進んでいる。数値モデル、ハードウェアが違ってもその主要な部分は変わらない。折りたたんでいくという、お決まりの方法である。演算量は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.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のそれに比べると小さい。
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つの要素に依存。
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の性能について検討するつもりだ。