Parallele Programmierung mit GPUs - fbi.h-da.de 2006: ATI Close To Metal: später Stream SDK, ... CUDA Programming Guide ... OpenCL (Open Computing Language)

Parallele Programmierung mit GPUs

Jutta Fitzek

Vortrag im Rahmen des Moduls „Parallele Programmierung“, WS12/13, h_da

Jutta Fitzek Parallele Programmierung mit GPUs Slide 2 / 43

Agenda

• GPUs: Historie

• GPU Programmierung – Konzepte

– Codebeispiel

– Generelle Tipps & Tricks

– Exkurs

• Zusammenfassung

• Weiterführende Informationen


Agenda

• GPUs: Historie


– Codebeispiel


– Exkurs

• Zusammenfassung



GPU Programmierung – Historie 1/2

• Anfang 1980er: Video Display Controller: reine Bildschirmausgabe

• Mitte 1980er: Amiga/Atari: erste Berechnungen

• Mitte 1990er: 3D Zusatzkarten mit eingebauten Algorithmen

• 1999: NVIDIA prägt den Begriff der “GPU” (GeForce-256)

• 2002: Begriff “GPGPU” General Purpose Graphics Processing Unit, Schnittstellen zur allgmeinen Verwendung der GPUs


GPU Programmierung – Historie 2/2

• 2004: BrookGPU, Stanford University: BSD-Lizenz • 2006: NVIDIA CUDA: für NVIDIA Karten • 2006: ATI Close To Metal: später Stream SDK,

heute keine Bedeutung mehr • 2008: OpenCL, Khronos Group: “Open Computing

Language”, offener Standard • heute: GPUs werden in zunehmendem Maße als

Basis für die Lösung von rechenintensiven Problemen eingesetzt

• Supercomputer Top 500: 62 Systeme verwenden grafische Co-Prozessoren, Tendenz steigend


GPUs – Vorteile

• GPUs sind fokussiert auf die Berechnung von Objekten, Pixelfarben, etc., eine Aufgabe wird intensiv abgearbeitet

• Massiv-parallelen Ausführung: Datenparallelismus, SIMD, tausende Ausführungseinheiten führen dasselbe Programm auf anderen Daten aus

• Vorteil der GPUs außerdem: weite Verbreitung, geringer Preis, stetig steigende Leistung


Entwicklung der FLOP/s

©NVIDIA, CUDA Programming Guide

=> GPUs werden immer interessanter für rechenintensive Anwendungen!


GPU Programmierung – heute

• Hersteller: Intel, NVIDIA, AMD

• Programmierung von GPUs: – plattformunabhängig:

OpenCL (Open Computing Language) • Vorteil in heterogenen Umgebungen, jedoch langsamer

– plattformabhängig, hier: CUDA für NVIDIA GPUs • Einsetzbar in homogenen Umgebungen, schneller

• sehr viele vorhandene Funktionen und Libraries

59,8% 21,2%

18,5%

0,5%

Marktanteile GPU-Hersteller 2012

Intel

AMD

nVidia

andere


Agenda

• GPUs: Historie


– Codebeispiel


– Exkurs

• Zusammenfassung



Was ist CUDA?

• CUDA (seit 2006): NVIDIA's Compute Unified Device Architecture “general purpose parallel computing platform and programming model”

• Unterstützung für: C, C++, Fortran, Java, Python, DirectCompute, Directives (OpenACC)

=> hier: CUDA C / C++


CUDA Programmiermodell

• Host = CPU

• Device = GPU

– GPU fungiert als Coprozessor für die CPU

– GPU hat ihren eigenen Speicher

– GPU führt viele parallele Threads aus (tausende!)

• Kernel = Funktion, die vom Host aufgerufen und auf dem Device ausgeführt wird


Logische Strukturierung

• Threads: führen den Kernel parallel aus, kleinste parallele Einheit

• Block/Threadblock (3D): Gruppe von Threads, die gemeinsam ausgeführt wird, gemeinsamer Shared Memory, Threadsynchronisation möglich (Tesla C2075: max. 1024 Threads per Block)

• Grid (2D): Gruppe von Threadblocks, die denselben Kernel ausführen ©NVIDIA, CUDA Programming Guide, Figure 6


Hardware-Aufbau einer GPU

• SP: Streaming Processor / Thread Processor

– führt jeweils einen parallelen Thread aus

• SM: Streaming Multiprocessor

– Scheduling und Ausführung der Threads

©NVIDIA, GTS 450, Aufbau der GPU


Ausführung des Programms

• Multiprocessor (SM) bringt ein oder mehrere Threadblocks zur Ausführung, verwaltet den gemeinsam genutzten Shared Memory

• Threadblocks sind vonein- ander unabhängig!

=> Skalierbarkeit mit der Anzahl der vorhandenen SMs! dh. das Programm läuft auf allen Grafikkarten und skaliert mit den vorhandenen Ressourcen!

©NVIDIA, CUDA Programming Guide, Figure 5


„SIMT“ Architektur

• Ein SM bekommt einen oder mehrere Blocks zur Ausführung, diese werden aufgeteilt in Gruppen mit aufsteigender ThreadID

• Je 32 Threads werden als „Warp“ gemeinsam ausgeführt

• Innerhalb eines Warps wird dieselbe Anweisung für alle Threads ausgeführt, wenn die Threads auf Grund von Verzweigungen divergieren, führt dies zu einer Serialisierung

• Begriff „ SIMT”: Singe Instruction Multiple Threads Mehrere Threads führen dieselbe Instruktion aus (Datenparallelität), können aber auch divergieren. => Bedeutung im Rahmen der Performance-Optimierung

32 Threads

32 Threads

...

http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html










Speichermodell der GPU

• Read-write per-thread registers • Read-write per-thread local memory • Read-write per-block shared memory • Read-write per-grid global memory • Read-only per-grid constant memory • Read-only per-grid texture memory

©CUDA programming guide, NVIDIA, 2007

Register Memory

Shared Memory

Global Memory

Speicher- platz Band-

breite

©Michael Bussmann, HZDR, 2007


CUDA C / C++: Spracherweiterungen

• Neue Spracherweiterungen und eingebaute Variablen zur Programmierung der GPU

• Einschränkungen: – Keine Rekursion im Device Code möglich – Keine Funktionspointer

• API/Libraries – CUDA Runtime API (Host und Device) – Speicherallokation auf dem Device (cudaMalloc,...) – Eingebaute Funktionen (sin, sqrt, mod, ...) – Atomic operations (für concurrency) – Neue Datentypen (2D textures, dim2, dim3, ...)


CUDA C / C++: Spracherweiterungen 1/4

Function Type Qualifiers: spezifizieren, von wo aus eine Funktion aufgerufen werden kann __global__ ausgeführt auf dem Device, vom Host aus aufrufbar (ab 3.x auch vom Device aus aufrufbar) zentraler Einstiegspunkt, Aufruf der GPU Funktion __device__ ausgeführt auf dem Device, nur vom Device aufrufbar __host__ ausgeführt auf dem Host, nur auf dem Host aufrufbar __device__ und __host__ können zusammen verwendet werden, es wird Code für beide Seiten erzeugt



Variable Type Qualifiers: spezifizieren, in welchem GPU Speicher eine Variable gehalten wird __device__ im globalen Speicher der GPU, nicht gecacht, hohe Latenz zugreifbar von allen Threads aus existiert so lange die Anwendung läuft __constant__ im konstanten Speicher auf dem Device, gecacht(!) zugreifbar von allen Threads aus, auch vom Host existiert so lange die Anwendung läuft __shared__ im shared memory, alle Threads eines Blocks können zugreifen, existiert so lange der Block ausgeführt wird



• Speicherallokation, Zugriffe – cudaMalloc(void ** pointer, size_tnbytes) – cudaFree(void* pointer) – cudaMemcpy(void *dst, void *src,

size_tnbytes, enumDirection); enumDirection: • cudaMemcpyHostToDevice • cudaMemcpyDeviceToHost • cudaMemcpyDeviceToDevice

• Threadsynchronisation im Kernel-Code:

alle Threads eines Blocks synchronisieren sich void __syncthreads();



Aufruf eines Kernels: modifizierter Funktionsaufruf, Start einer GPU Funktion vom Host aus: kernel<<<dim3 grid, dim3 block>>>(…)

• In spitzen Klammern wird die “Ausführungskonfiguration” angegeben (“<<< >>>”):

Dimension des Grids: 2d, dh. x und y

Dimension des Thread-Blocks: 3d, dh. x, y, z


Agenda

• GPUs: Historie


– Codebeispiel


– Exkurs

• Zusammenfassung



VectorAdd – CPU Version

• Addition zweier Vektoren auf der CPU:

for (int i=0; i<500000; i++){ C[i] = A[i] + B[i]; }


VectorAdd – GPU Version



Bestimmung der Thread ID

• dim3 gridDim Dimensionen des Grids • uint3 blockIdx Position des Blocks im Grid • dim3 blockDim Dimension des Blocks • uint3 threadIdx Position des Threads im Block

Bei 2d Block und 2d Grid: threadsPerBlock = blockDim.x * blockDim.y blockNumInGrid = blockIdx.x + gridDim.x * blockIdx.y threadNumInBlock = threadIdx.x + blockDim.x * threadIdx.y


Komplexeres Beispiel



Compiler

• nvcc: eigener NVIDIA CUDA Compiler

• trennt den Host und den Device Code – der Host Code wird an einen vorhandenen

Compiler weitergegeben (Linux: gcc)

– der Device Code wird zunächst in in PTX Assembler (Parallel Thread Execution) transformiert, und dann in Maschinensprache für die GPU

• Aufruf: nvcc cudacode.cu


Entwicklungsumgebung

• nsight Eclipse Edition: Abgewandelte Eclipse Version speziell für die CUDA Programmierung, Teil des Toolkits – Gewohnte Eclipse Umgebung

– Code Editieren, Debuggen (auch Kernel Code)

– Integrierter Profiler !

©NVIDIA Webseite


Agenda

• GPUs: Historie

• GPU Programmierung

– Konzepte

– Codebeispiel


• Zusammenfassung



Tipps und Tricks: Parallelisierung

• Allgemein: Berechnungs- oder Speicherintensive Probleme können generell vom GPU-Einsatz profitieren

• 1. Schritt immer: herausfinden, welcher Teil des Algorithmus am meisten Zeit einnimmt und mit dessen Parallelisierung beginnen !!

• Datenparallelität – Einsatz von GPUs bei Datenparallelität

– Problem klar formulieren und strukturieren

– Verzweigungen / bedingte Abarbeitung vermeiden, da es sonst zur Serialisierung kommt!


Tipps und Tricks: Kopieren vermeiden

• Der Flaschenhals ist die Bandbreite zur Host CPU, Kopieren von Daten vom Host zum Device und umgekehrt ist sehr zeitintensiv!

– Daten ggf. dort lassen, wo sie sind und weitere, evtl. nicht so performante Berechnungen dort ausführen, um Kopieren zu vermeiden

– evtl. Einsatz von asynchronem memcopy, um Berechnungs- und Kopierzeiten zu überlagern


v_4

v_3

v_6

v_5

• Datenstrukturen beim Übergang zur GPU ggf. modifizieren

– Ziel: stride-one access bei Arrays: anstelle von array-of-structures statt dessen 6x ein Array der Größe N nutzen, um Perfomance zu gewinnen

...

v_2

v_1

Tipps und Tricks: Datenstrukturen

v1_1

v1_2

v1_3

v1_4

v1_5

v1_6

vN_1

vN_2

vN_3

vN_4

vN_5

vN_6


Tipps und Tricks: Speicher 1/2

• Immer möglichst den schnelleren Speicher nutzen !

– Speicherhierarchie im Hinterkopf behalten ;-)

– Register und Shared Memory, wo es möglich ist

– Constant Memory, weil gecached

– Global Memory vermeiden

– Local Memory möglichst vermeiden !


Tipps und Tricks: Speicher 2/2

• Einfache Möglichkeit ist z.B. Schleifen „ausrollen“ / Unroll loops, um Register zu verwenden:

– Compiler Direktive #pragma unroll führt zur Verwendung von Registern statt Local Memory

• Speicherzugriffe optimieren:

– Generell „Coalesced access“: Eine Speicher-Lesetransaktion, wenn alle Threads Warps auf ein zusammenhängendes Segment im global memory zugreifen


Agenda

• GPUs: Historie

• GPU Programmierung

– Konzepte

– Codebeispiel


– Exkurs



Exkurs: Single/Double Precision

• Fließkommazahlen in einfacher oder doppelter Genauigkeit (32 vs. 64Bit) sind ein wichtiges Thema bei langlaufenden rechenintensiven Programmen

• GPU: Doppelte Genauigkeit ist mittlerweile verfügbar, die Performance ist jedoch geringer als bei der Verwengung von einfacher Genauigkeit

• Vorsicht mit älteren Grafikkarten: nicht alle erfüllen den vollen IEEE 754 Standard !

• Abwägung: Performance vs. Fehlerfortpflanzung • Doppelte Genauigkeit ist noch nicht

in allen APIs verfügbar • Zukunft: die Performance der Berechnungen mit doppelter

Genauigkeit wird immer besser, aktuelle Grafikkarten erreichen bis zu 80% der Performanz


Exkurs: Thrust 1/2

• Low level programming mit CUDA für C++ (s. vorher): + Alle Möglichkeiten der Programmierung verfügbar

+ Komplette Kontrolle über die GPU

– Vielen Zeilen an „technischem Code“

– Komplexere Programme, verringerte Wartbarkeit

• High level programming mit Thrust für CUDA: http://code.google.com/p/thrust

+ Viele vordefinierte Funktionen, schnelle Lernkurve

+ Wenig/kein zusätzlicher technischer Code

+ Weniger Komplexität, bessere Wartbarkeit

– Keine volle Kontrolle, ggf. low level Programmierung nötig

– Viele Funktionen aktuell nur mit single precision verfügbar

http://code.google.com/p/thrust




Exkurs: Thrust 2/2

• Thrust bietet Funktionen für: – einfaches Anlegen von z.B. Vektoren, diese beinhalten Iteratoren – direktes Zuweisen von Host/Device Vektoren – Speicher muss nicht allokiert / freigegeben werden – eingebaute Funktionen:

• Sortieren • Transformieren • Summieren • ...

=> sehr gut geeignet als Schnelleinstieg! => GPU wird für eine breitere Nutzerbasis zugänglich

• er

Beispiel von der Thrust Projektseite: http://code.google.com/p/thrust/


Exkurs: Was ist nun mit MPI?

• Message Passing Interface (MPI): Standard für den Nachrichtenaustausch bei parallelen Berechnungen auf verteilten Computersystemen

• An einer Programmausführung nehmen mehrere Prozesse teil, die über Nachrichten miteinander kommunizieren

• Stichworte: – distributed memory – SPMD (single program, multiple data, Unterkategorie von MIMD)

• Aufbau zusammen mit GPUs:

– Jeder MPI Knoten hat zusätzlich intern ein oder mehrere GPUs – GPU zur Beschleunigung der lokalen Berechnung auf diesem Knoten – Stichwort coarse-grained parallelism zwischen den MPI Knoten

(jeder einzelne Knoten muss genug Berechnungsarbeit zu leisten haben, damit sich lokal der Einsatz der GPU lohnt)

=> GPU Programmierung und MPI Programmierung ergänzen sich und werden häufig gemeinsam eingesetzt!


Agenda

• GPUs: Historie


– Codebeispiel


– Exkurs

• Zusammenfassung



Zusammenfassung

• GPUs bieten eine einfache Möglichkeit zur Parallelen Programmierung (Datenparallelität)

• GPUs werden aktuell bereits in vielen Bereichen eingesetzt, auch in kommerziellen Produkten (z.B. Photoshop)

• Tendenz: verstärkter Einsatz in Supercomputern • Tendenz: verstärkter Einsatz allgemein, auf Grund der

hohen Verbreitung der Grafikkarten in Desktop Rechnern

• CUDA oder OpenCL ? für CUDA sprechen aktuell die vielen vorhandenen Bibliotheksfunktionen

• Zukunft ? => ein Prozessor, der alles vereint und es dem Benutzer gegenüber versteckt???


Agenda

• GPUs: Historie


– Codebeispiel


– Exkurs

• Zusammenfassung



Weiterführende Informationen

• CUDA Zone @NVIDIA: – CUDA C Programming Guide


• Bücher: – CUDA by Example

J. Sanders, E. Kandrot; Addison-Wesley – Programming Massively Parallel Processors:

A Hands-on Approach – 2nd Edition D. Kirk, W. Hwu; Morgan Kaufmann

• Kurs zur GPU Programmierung: – Stanford University Course (podcast):

http://code.google.com/p/stanford-cs193g-sp2010/














Documents

Parallele Programmierung mit GPUs - fbi.h-da.de 2006: ATI Close To Metal: später Stream SDK, ... CUDA Programming Guide ... OpenCL (Open Computing Language)