Multi-GPU-Computing: Eins, zwei, drei, ganz viele

Multi-GPU-Computing:Eins, zwei, drei, ganz viele

Jörn Dinkla

para//el 2015

Karlsruhe, 22. 4. 2015

Version 0.1

Tablet, PC, Großrechner, Cloud, Spielkonsole,

Autos …

GPU-Computing ist überall

Schnelle erste Erfolge

2x – 5x Speedup

Dann wird es schwieriger …

Oft sind 10x drin

Speedup

2 3 4 5 6 7 8 9 10 11 …

„Enabler“

Bis zu 16 GPU pro Knoten

Abhängig von

Mainboard, CPU, Chipsatz, PCIe-Controller

Multi-GPU

2 GPUs

3 GPUs

…

Erreichbar? Amdahl‘s Gesetz?

X-facher Speedup?

4 6 8 10 12 14 16 18 20

6 9 12 15 18 21 24 27 30

Frameworks im Überblick

C ++ 11

C ++

C

Device

Framework

CUDA

C++

AMP

DirectX

AMDTreiberTDD

WDDM

Thrust

C++-

Wrapper

Library

OpenCL

Bolt

Intel

AMD

CUDA

⊕ Am meisten verbreitet

⊕ C++ 11

⊖ nur NVIDIA-Hardware

C++ AMP

⊕ C++ 11

⊖ Einschränkungen wegen DirectX (bisher)

⊖ geringe Verbreitung

OpenCL

⊕ Apple, Intel, AMD

⊖ Geringer Abstraktionsgrad, C99

⊖ Nicht so viele Libraries wie bei CUDA

Vor- und Nachteile

1. Partitioning

2. Communication

3. Agglomeration

4. Mapping

Siehe http://www.mcs.anl.gov/~itf/dbpp/

PCAM-Methodik

… und parallele Datenstrukturen

… und partitionierte Datenstrukturen

Aufgabenstellung ähnlich

Egal ob Multi-

-CPU,

-Core

oder -GPU

Parallele Algorithmen

Speicher und Synchronisation

1 GPU, Daten passen

Partionierung u. „Swapping“ erforderlich

1 GPU, Daten passen nicht

Partionierung erforderlich

2 GPUs, Daten passen

Szenario für

den Vortrag

Partionierung u. „Swapping“ erforderlich

2 GPUs, Daten passen nicht

Listen, Arrays

2D: Ebenen, Bilder

3D: Volumen

Ganz

Als Vektor/Liste von Ebenen

Grids, Gitter

Einfach zu partitionieren

Regelmäßige Datenstrukturen

Regelmäßige Datenstrukturen

Teilung nach Anzahl Elemente

x y*z x/2 * y

y z x*y/2

z 2 x*y*z/2

Kopie

Bäume

Teilbäume als Partitionen

Graphen

Zusammenhangskomponenten

Klein genug? Gleich groß?

Unregelmäßige Datenstrukturen

Graph Partitioning / Clustering

Aufteilung gemäß Kostenfunktion

Im allg. NP vollständig

Minimale „cuts“

Social Networks und Big Data

Apache Spark und GraphX

Kernighan-Lin, 𝑂(𝑛3)

Buluc et. al. „Recent Advances in GP“ 2013

Unregelmäßige Datenstrukturen

Homogen (Gleiche GPUs)

Gleiche Arbeit

Inhomogen (Unterschiedliche GPUs)

Messen und gewichten

Wie bei CPUs

Work-Balancing / Job-Stealing

Scheduling-Theory

Divisible Load Theory

Scheduling

Nicht das Rad neu erfinden!

„best practices“

„think parallel“

Tip

McCool et. al.

„Structured Parallel Programming“

Intel-lastig, Cilk Plus, TBB

Parallele Patterns

Parallele Patterns

Siehe http://www.parallelbook.com/

P: Elemente

C: Keine

„embarassingly parallel“

A: Granularität

CPU vs. GPU

Großer Unterschied!

M:

TBB, OpenMP, CUDA, etc.

Map mit PCAM

Beispiele

Durchschnitt, Smoothing

PDEs

P, A, M wie Map

C: Nachbarschaft

Optimierung

Speicherzugriffe und Cache

Berechnungen speichern

Stencil mit PCAM

Wärmeleitungsgleichung in 2D

Stencil

o[x,y] += c* ( i[x-1,y] + i[x+1,y]

+ i[x,y-1] + i[x, y+1]

- 4 * i[x,y] )

Beispiel: Heat-Simulation

Initialisiere Wärmequelle heat

prev := 0

Für alle Iterationen

Addiere Wärmequellen prev += heat

current := stencil(prev)

Tausche prev und current

Ablauf

Daten

Buffer(float) für Wärmequelle

Buffer(float) für prev und current

Kernel

add_heat() bzw. mask()

stencil()

Optional

Buffer(uchar4)

Kernel für Umwandlung

Zu implementieren …

Obfuscation

Aus Wilt „The CUDA Handbook“, S. 218

„Index-

Schlacht“

OptimiertNachteil: Speicherorganisation

fest verdrahtet

Größe / Extension

width, height

index(x,y)

in_bounds(x,y)

in_bounds_strict(x,y)

Extent2

0 1 2 3

0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1

2

3

Stencil-Kernel (CUDA 7.0)

Vor Kernel-Aufruf

Wechsel der Abstraktionsebene

Host zu Device

Von C++-Datenstrukturen zu Device-Pointern

Aufruf des Kernels

Kernel-Aufruf

Basis BaseBuffer

HostBuffer

Unpinned (C++)

Pinned (CUDA, nicht swapbar)

Lokaler Speicher (NUMA)

DeviceBuffer (CUDA)

ManagedBuffer (CUDA)

Buffer

GPU besteht aus mehreren SM/CU

Thread-Block wird festen SM zugewiesen

Warp / Wavefront

Kleinste Scheduling-Einheit

32 bei NVIDIA, 64 bei AMD

Occupancy

Warps und Wavefronts

W0SM* W1 W2 W3 W4 -- -- --

Thread-Block (Work group, tile)

Performance, abhängig von Hardware

Grid (NDRange)

Beispiel

Daten 8x8

Grid 2x2

Block 4x4

Grid = Data/Block

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

0

1

2

3

4

5

6

7

0 1

2 3

Daten, Pixel, Voxel Grid

kernel<<<g, tb, sm, s>>>(params)

Kernel-Konfiguration

dim3 Grid g

dim3 Thread-Block tb

Größe des Shared-Memory sm

cudaStream_t s

Oft abhängig vom Extent2

CudaExecConfig(Extent2& e)

CudaExecConfig

mask() / add_heat()

Single Instruction Multiple Threads!

Mask-Bit für jeden Thread im Warp

SIMT - Divergenz

0 1 2 3

int tid = treadIdx.x;

if (tid < 2) {

call_expensive_function()

} else {

call_expensive_function2()

}

Warps Code

CUDA

Nsight (Visual Studio, Eclipse)

nvvp, Visual Profiler (Eclipse)

Kommandozeile nvprof

OpenCL

Intel Vtune (*)

AMD CodeXL

C++ AMP

Visual Studio 2013

Concurrency Visualizer

Profiling

Computation Bound

Alle Prozessoren 100% ausgelastet

Memory Bound

Bandbreite zum Speicher voll ausgelastet

Latency Bound

Warten auf die Daten

Arten der Auslastung

NVVP sagt zu stencil()

Arithmetische

Intensität 1/5

Nicht optimal

Arithmetische Intensität niedrig

#Berechnungen / #Speichertransfers

Möglichkeiten

Mask()

Textur-Speicher ausprobieren

Stencil()

Zwischenspeichern im Shared-Memory

Fazit Single GPU

Partitionierte Map

Map mit Multi-GPU

„Overlap“

Stencil mit Multi-GPU

Halo

Ghost Cells

„Overlap“

Iterierter Stencil

Initialisiere Wärmequelle heat

Für jede GPU

Initialisiere Buffer prev und current

Kopiere Teil von heat auf‘s Device

prev := 0

Für alle Iterationen

Für jede GPU

Addiere Wärmequellen prev += heat

current := stencil(prev)

Tausche prev und current

Kopiere Halo/Ghost Cells zu Nachbarn

Kopiere Ergebnisse aller GPUs auf Host

Ablauf (Multi)

Host (wie bisher)

Wärmequellen

Endergebnis

Benötigt pro GPU

Buffer für prev und current

Heat-Buffer (Ausschnitt)

Datenstrukturen (Multi)

cudaGetDeviceCount(int* count)

Ermittelt Anzahl der Devices

cudaGetDeviceProperties(cudaDeviceProp* prop, int device)

Eigenschaften des Devices

cudaSetDevice(int device)

Setzt Device für aktuellen Thread

Betrifft alle folgenden cuda*-Funktionen

Multi-GPU mit CUDA

Jeder Thread hat CUDA-Kontext

Dieser speichert aktuelle GPU

Kernel

Nur Speicher auf gleichem Device!

Vorsicht bei Bibliotheken

Z. B. Thrust

Multi-GPU mit CUDA

Partition, CudaPartition

GPU

Explizit einschalten

cudaDeviceCanAccessPeer(&i,d,e)

cudaDeviceEnablePeerAccess(e,0)

Einschränkungen

Nicht Windows u. WDDM

Peer-to-Peer-Kopien

D2D

2D-Partition

2D-Partition auf Device

mask()-Kernel

Verschiedene Extents für Quelle und Ziel

mask()

Erinnerung: mask()

mask() mit Offset

Pos2

Mit_overlap zu mit_overlap

Kernel nur für inneren Bereich aufrufen

stencil()

Erinnerung: stencil()

stencil() mit Offset

Multi-GPU in CUDA

Halo vergessen?

Kopieren der Halos

XExtent2

Region2

Init in CUDA

Update in CUDA #1

Update in CUDA #2

Async!

Wichtig: cudaDeviceSynchronize() parallel

Analyse mit NVVP / Nsight

Orange seq.

Orange par.

Aktuelle Hardware

Intel i7-5930K, 4,0 Ghz

16 GB DDR4 RAM, 2,4 Ghz

2x NVIDIA GTX 970, Standard-Clocks

2x 16x PCIe 3.0

OS

Windows 7 bzw. Ubuntu 14.10

Benchmark Testsystem

Speedups

10x

Speedups Multi-GPU

1,955x

1,955 Speedup bei 2 GPUs

Und was bei 3, 4 oder mehr Karten?

Problem:

PCIe-Bus skaliert nur begrenzt

Bandbreite ist begrenzt

Anzahl der Geräte ist begrenzt

Und bei mehr GPUs?

Lane ist 1 bit, full duplex

Punkt-zu-Punkt Verbindung

1,2,4,8,12 oder 16 Lanes

Geschwindigkeiten

2.0: pro Lane 500MB/s, max. 8 GB/s

3.0: pro Lane 1GB/s, max. 16 GB/s (*)

Controller

Hat max. Anzahl Lanes

PCIe

Grafikkarte x16

CPU hat 40 Lanes

=> max. 2 x16 + 1x8

bis zu 4 x8

PCIe

D2D

Anzahl PCIe-Slots auf Mainboard

Anzahl Lanes des PCIe-Controller

Anzahl der Switches / IOHs

4, 8 oder 16 GPUs

Wichtig ist die Bandbreite nicht zu überladen

Praxiserfahrung:

3 GPUs waren bei vielen Kopien schneller

als 4 GPUs

Anzahl der GPUs

PCIe Switch

D2D D2D D2D

Kein D2D über QPI

NUMA

D2D D2D

Rechts-Links

„Rechts“ Erst Kopie von g zu g+1

„Links“ Dann von g zu g -1

Kopieren der Halos

PCIe-Bus

…

Für alle Iterationen

Für jede GPU

Addiere Wärmequellen prev += heat

current := stencil(prev)

Tausche prev und current

Kopiere Halo/Ghost Cells zu Nachbarn

…

Ablauf (Multi)

Kopieren der Halo‘s #2

Aktuelle GPUs können gleichzeitig

Kernel, 1 Kopie hin u. 1 Kopie zurück

Streaming

…

Für alle Iterationen

Für jede GPU

Berechne nur den Halo („Spezialkernel“)

Kopiere Asynchron zu Nachbarn

Berechne Teil ohne Halo

…

Modifizierter Ablauf (Multi)

Kopieren der Halo‘s #2

Code-Komplexität

vs. Performance

Abhängig von Implementierung und Hardware

Wie groß sind die Halos?

Lässt sich die Kopie hinter dem Kernel

verstecken?

Ab wie vielen GPUs ist der Bus ausgelastet?

Gibt es Stau („contention“) auf dem Bus?

Lohnt sich das?

Viele melden Erfolge …

Linearer Speedup

http://on-demand.gputechconf.com/gtc/2015/posters/GTC_2015_Computational_Physics_03_P5122_WEB.pdf http://on-demand.gputechconf.com/gtc/2015/presentation/S5585-Wei-Xia.pdf

2016 Pascal

4 „Connections“ per GPU

Jede 20GB/s peak, 16GB/s praktisch

US DoE, Summit 2017 150-300 PetaFLOPS

NVLINK

C++ AMP

Daten: array, array_view

Kernel: parallel_for_each

Single GPU mit AMP

DoubleBuffer<T>

Single GPU mit AMP #2

restrict(amp)

Extent2 hat schon __device__

Extent2AMP

Single GPU mit AMP #3

x, y: andere

Reihenfolge!

GPU heißt „accelerator“

accelerator_view ist logische Sicht

Argument zu parallel_for_each

Multi-GPU mit C++ AMP #1

view

array_view logische Sicht auf ein array

array<float> name(size, view)

Multi-GPU mit C++ AMP #2

„D2D“-Kopien

Aber:

Über Host

Nicht parallel zu parallel_for_each

Multi-GPU mit C++ AMP #3

OpenCL-stencil()

Kein

Extent2

Kein C++

11

OpenCL und C++Bindings

Platform

Device

Context

Program

Kernel

Buffer, Image

CommandQueue

Event

Übersicht OpenCLPlatform

Device

Context wird mit vector<> angelegt

Für jedes Device eine Queue

Single-Context, Multi-Device

OpenCL-Objekte „shared“

MemObjects, Programs, Kernels

MemObjects brauchen explizite Kopie

Kein D2D

Support für Partitions / Multi-GPU

Offsets für Kernel und Kopien

SubBuffer

Single-Context, Multi-Device

Pro Device einen Context

Alles separat und redundant

Evtl. einfacher zu programmieren

Scatter/Gather/Broadcast statt SubBuffer

Aufpassen bei der Datenhaltung

Einfache Erweiterung

Multi-Node oder heterogenes System

Multi-Context & Multi-Device

Von Single- zu Multi-GPU

1. Partionierung einführen

2. Vervielfachung der Datenstrukturen

3. Kernel erweitern

Mit Offsets und weiteren Extents

Zusammenfassung

Parallele Algorithmen

… und partitionierte Datenstrukturen

Hardware

PCIe-Problematik

Kompetenter PC-Hersteller notwendig

Fazit

Gute Speedups möglich

Wenn Halo-Kopien klein

und/oder hinter Kernel versteckt

Skaliert wegen PCIe nur begrenzt

Fazit

Multi-Node

Das gleiche Partitionierungsproblem

Kommunikation zwischen Nodes

Kein Shared-Host-Memory mehr

MPI_Send()

MPI_Recv()

GPU-spezifische Erweiterungen

OpenMPI, MVAPICH2

Multi-Node mit MPI

Titan

18688 Opterons und 18688 Tesla K20X

Nr. 2 in Top 500

Multi-NodeNur am Rande

…

Folien

http://dinkla.net/parallel2015

Sourcecode

https://github.com/jdinkla/parallel2015_gpuco

mputing

Organisatorisch

Schwerpunkte

Parallele Systeme

C++ und Java/JVM

GPU-Computing

CUDA, OpenCL, C++ AMP

Big Data, BI, Data Science

http://www.dinkla.com

Last but not least

Fragen?

Sprechen Sie mich

an oder

joern@dinkla.com