Úvod GPGPU Aplikace
GPGPU Obecné výpočty na grafických procesorech
Jan Vacata
Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Motivace Technologie
Motivace 3 GHz Intel Core 2 Extreme QX9650 Výkon: 96 GFLOPS
NVIDIA GeForce 9800 GX2 Výkon: 768 GFLOPS
Propustnost paměti: 21 GB/s
Propustnost paměti: 128 GB/s
Orientační cena: 1300 USD
Orientační cena: 600 USD
Obrázek: Sledování změn výkonu Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Motivace Technologie
Motivace - pokračování
Proč jsou GPU tak rychlé? 1
Technologický důvod: Specializace GPU pro rychlé provádění nezávislých paralelních výpočtů
2
Ekonomický důvod: Obrovský trh s počítačovými hrami
Podrobněji: Propustnost paměti Široká paměťová směrnice pro rychlé čtení z textur (384 bitů u G80)
Vícejádrové procesory - budoucnost paralelních výpočtů Nejnovější CPU (AMD, Intel) → 8 jader GPU NVidia G92 → 128 (×2) jader GPU AMD RV670 → 320 (×2) jader
Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Tradiční GPGPU Moderní GPGPU, NVIDIA CUDA
General Purpose Computation on GPUs (GPGPU) Nevýhody tradičního GPGPU: Nepřirozený programovací model, obtížné pro vývojáře neznalé principů zpracování 3D grafiky Další nevýhody spojené s využitím grafického API mapování textury Y
textura Z data z textury
textura
rasterizace
geometrie
rastrové operace framebuffer
X
zpracování fragmentů
viewport
Obrázek: Tradiční GPGPU
Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Tradiční GPGPU Moderní GPGPU, NVIDIA CUDA
NVIDIA CUDA
NVIDIA CUDA (z angl. Compute Unified Device Architecture) Kombinace SW/HW řešení (Změny v HW, ovladač grafické karty, runtime knihovna) GPU jako jistá forma architektury se sdílenou pamětí GPU jako koprocesor pro provádění nezávislých, datově paralelních výpočtů Snadno uchopitelný programovací model, naprosté odstínění od grafických pojmů Očekávaná podpora aritmetiky fp64 (double)
Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Metody Krylovových podprostorů Řešení soustav lineárních algebraických rovnic A ∈ Rn,n regulární, x ∈ Rn , b ∈ Rn
Ax = b,
Nejznámější zástupci nestacionárních iteračních metod Hledáme aproximaci přesného řešení x∗ v prostoru Km (A, r0 ) = [r0 , Ar0 , A2 r0 , . . . , Am−1 r0 ]λ ,
r0 = b − Ax0
Metodám společné 1
Nalezení ortonornální báze Km (A, r0 ) = [v1 , . . . , vm ]λ ,
2
Hledání aproximace ve tvaru xm = x0 + Vm ym Jan Vacata
GPGPU
VmT Vm = I
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Metody Krylovových podprostorů - pokračování Konkrétní metody: Metoda Konjugovaných gradientů (CG) rm = b − Axm ⊥ Km (A, r0 ) Minimalizuje 1
kx∗ − xm kA = (A(x∗ − xm ), x∗ − xm ) 2 Metoda Zobecněných minimálních reziduí (GMRES) rm = b − Axm ⊥ AKm (A, r0 ) Minimalizuje kb − Axm k2
Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Typy a struktura operací (CG, GMRES)
Operace Saxpy Sdot SpMV Struktura Metoda CG GMRES
y = αx + y α = (x, y ) y = Ax operací Sdot 2 i +1
x, y ∈ Rn , α ∈ R x, y ∈ Rn , α ∈ R x, y ∈ Rn , A ∈ Rn,n
Saxpy 3 i +1
SpMV 1 1
Jan Vacata
Předpodmínění 1 1
GPGPU
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Měření operací Saxpy/Sdot • Optimalizované funkce knihovny MKL na straně hostitele • Optimalizované funkce knihovny CUBLAS • Uživatelská implementace (CUDA)
80
80 CPU MKL GPU User Kernel GPU CUBLAS
CPU MKL GPU User Kernel GPU CUBLAS
70
60
60
50
50 GB/s
GB/s
70
40
40
30
30
20
20
10
10
0
0 0
1
2
3
4
5
6
7
8
9
0
# of elements (x 106)
1
2
3
4
5
6
7
# of elements (x 106)
Obrázek: Operace Saxpy
Obrázek: Operace Sdot Jan Vacata
GPGPU
8
9
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Měření operace SpMV • OpenMP paralelizovaná implementace na straně hostitele • Naivní CUDA implementace • Optimalizovaná CUDA implementace
70
25
CPU User GPU Naive GPU Optimized
CPU User GPU Naive GPU Optimized 60 20 50
15 GB/s
GB/s
40
30 10 20 5 10
0
0 0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
0
0.2
0.4
0.6
0.8
1
1.2
1.4
# of elements (x 106)
# of elements (x 106)
Obrázek: Operace SpMV - náhodná nestrukturovaná matice Jan Vacata
Obrázek: Operace SpMV - matice s několika diagonálami GPGPU
1.6
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Testované matice
Matice Dubcova3
Matice parabolic fem
Matice thermal2
Matice helm2do3
Matice language
Matice cage14
Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Výsledky měření metody CG Matice Rozměr Počet nenul Počet Iterací CPU Čas výpočtu (s) CSR uloženo hodnot Norma rezidua Chyba GPU Čas výpočtu (s) PCSR uloženo hodnot Norma rezidua Chyba Relativní urychlení
Dubcova3 146689 3636643 200
parabolic fem 525825 3674625 1000
thermal2 1228045 8580313 3000
3.97 7419988 2.23 × 10−4 5.18 × 10−3
24.7 7875076 2.2 × 10−4 3.54 × 10−1
196 18388672 3.4 × 10−3 4.107
0.189 7471914 2.18 × 10−4 4.75 × 10−3 21
1.24 7895026 2 × 10−4 8.69 × 10−1 19.9
10.4 22440374 3.2 × 10−3 2.739 18.8
Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Výskedky měření metody GMRES Matice Rozměr Počet nenul Restartování Počet Iterací CPU Čas výpočtu (s) CSR uloženo hodnot Norma rezidua Chyba GPU Čas výpočtu (s) PCSR uloženo hodnot Norma rezidua Chyba Relativní urychlení
helm2d03 392257 2741935 40 1000
language 399130 1216334 10 1000
cage14 1505785 27130349 10 500
40.5 5876128 1.2 × 10−1 37.4
66.5 2831799 2.5 × 10−5 8.55 × 10−3
96.5 55766484 2.2 × 10−5 1.4 × 10−4
4 5897508 1.2 × 10−1 37.3 10.1
10.6 10174163 1.9 × 10−5 2 × 10−4 6.27
4.4 58400009 2.3 × 10−5 8.6 × 10−5 21.9
Jan Vacata
GPGPU
Úvod GPGPU Aplikace
Metody Krylovových podprostorů Elementární operace Měření výkonu
Literatura
Jan Vacata. GPGPU: Obecné výpočty na grafických procesorech diplomová práce, 2007. Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. GPU Computing. Proceedings of the IEEE 96(5):879-899, 2008. http://www.gpgpu.org http://www.nvidia.com/object/cuda_home.html
Jan Vacata
GPGPU
