sobre técnicas de optimización para la multiplicación de...

Sobre tecnicas de optimizacionpara la multiplicacion de matrices

en plataformas hıbridas CPU+GPU

Javier Cuenca Luis Pedro GarcıaDomingo Gimenez

Universidad de Murcia Universidad Politecnica de Cartagena

Primeras Jornadas de Programacion Paralela Multicore y GPUGranada, 6 y 7 de febrero de 2014

Domingo Gimenez (UMU) [email protected] JPPMG / 6-7 febrero, 2014 1 / 19

Introduccion

La importancia adquirida recientemente por los sistemas Multicorecon aceleradores GPU y Coprocesadores:

Lista TOP500 Noviembre 2013: 1. Tianhe-2 (Intel Phi), 2. Titan(GPU NVIDIA K20x), 6. Piz Daint (GPU NVIDIA K20x), 7. Stampede(Intel Phi)Equipos de escritorio con GPUs

Dedicando un gran esfuerzo al desarrollo de software para estossistemas. Son necesarias tecnicas de optimizacion del software parapoder aproximarnos a los GFLOPs alcanzables en el sistemaCPU+GPU

En este trabajo. Tecnicas de optimizacion basadas en:Experimentos guiadosModelado empırico del tiempo de ejecucion

Obtener un balanceo optimo del trabajo a distribuir entre CPU y GPU enla Multiplicacion de Matrices


Indice

IntroduccionMotivacionMetodos de autotuning

Metodo I: Busqueda guiadaMetodo II: Modelado empırico

Resultados experimentales con el metodo IResultados experimentales con el metodo IIConclusiones y trabajos futuros


Motivacion

DGEMM en CPU y GPU

C = αAB + βC ⇒ C = α(AB1 + AB2) + β(C1 + C2)

αAB1 + βC1 se calcula en GPU y αAB2 + βC2 en CPUDGEMM en CPU+GPU

K

M A

NGPU NCPU

C1 C2

B1 B2K

N

¿Que buscamos?

Balancear el tiempo consumido en GPUy CPU

¿Que necesitamos?

Solapar computacion y comunicacionentre GPU y CPU

Distribucion del calculo

N = N gpu + N cpu dependera del tamano del problema, y de lavelocidad relativa entre CPU y GPU en cada sistema


Motivacion

DGEMM CPU+GPU

1 // Asynchronous transfer requires pinned host memory2 cudaMallocHost((void **) &h_A, sizeof(double)*szeA);3 // Copy async host memory to device4 cublasSetMatrixAsync(M, K, h_A, d_A, ...);5 cublasSetMatrixAsync(K, N_gpu, h_B+ldb*N_cpu, d_B, ...);6 // Have GPU do C_1 = AxB_17 cublasDgemm(M, N_gpu, K, d_A, d_B, d_C, ...);8 // Copy async results from device to host9 cublasGetMatrixAsync(M, N_gpu, d_C, lddc, h_C+ldc*N_cpu, ...);

10 // Have CPU do C_2 = AxB_211 dgemm_(&M, &N_cpu, &K, h_A, h_B+ldb*N_gpu, h_C+ldc*N_gpu, ...);

Librerıas BLAS

CPU: MKL, GotoBLAS, ATLASGPU: CUBLAS, MAGMA, CULA Tools


MotivacionMetodo simple basado en GFLOPs medios

1 // Change for library, GPU and CPU2 gpu_flops = 460; cpu_flops = 140;3 total_flops = gpu_flops + cpu_flops;4 N_gpu = (N*gpu_flops)/total_flops;5 N_cpu = N - N_gpu;

500 1000 1500 2000 2500 3000 3500 4000

20

40

60

80

100

120

140

160

180

matrix size

GFLOPS

Matrix Multiplication - 6CGTX690

CUBLAS DGEMMMKL DGEMM

Hybrid DGEMM Avrg. GFLOPSMKL DGEMM + CUBLAS DGEMM

1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

100

200

300

400

500

600

700

800

900

1000

matrix size

GFLOPS

Matrix Multiplication - 12CK20

CUBLAS DGEMMMKL DGEMM

HyBRID DGEMM Avrg. GFLOPSMKL DGEMM + CUBLAS DGEMM


Metodos de autotuning: I. Busqueda GuiadaEsquema Busqueda Guiada

hybrid DGEMM(.,M , N , K, A,LDA, B, LDB, C,LDC, B, LDB,N CPU)

Installation Set{384, 1152, · · · , 8064}

N CPU = N CPU + ∆N CPUN GPU = N−N CPU

Execution

T exe−T minT min

> Th.

Installation Set N CPU384 01152 96· ·· ·· ·

8064 2208

INSTALLATION

Ejecucion rutina

N CPU se decide a partir delos valores obtenidos en lainstalacion.Tamano de problema mascercano en elConjunto Instalacion o porinterpolacion

Aplicacion Busqueda Guiada

Experimentos con M ∈ Conjunto Instalacion. Valor inicial N CPU = 0

Variacion porciones B y C asignadas a CPU (N CPU) y GPU (N GPU)

N CPU = N CPU +∆N CPU hasta TEXEC exceda cierto UMBRAL a TMIN

Siguiente M ∈ Conjunto Instalacion con N CPU mejor TEXEC para tamanoproblema anterior


Metodos de autotuning: II. Modelado empırico tiempo deejecucionEsquema Modelado Empırico




Execution

LEAST SQUARETdgemm(m,n) = k1m2n + k2m2 + k3mTdgemm gpu(m,n) and Tdgemm cpu(m,n)

ki gpu and ki cpu

Tcomu(n) = ts + ntwTcomu h2d and Tcomu d2h

tsh2d, twh2d

and tsd2h , twd2h

TEXEC = max (Tdgemm cpu + γTcomu,Tdgemm gpu + Tcomu)

INSTALLATION

Aplicacion Modelado Empırico

Los experimentos se guıan de forma similar que en el Metodo I.

γ representa el solapamiento entre computacion y comunicacion. Se obtieneexperimentalmente para cada sistema γ ∈ [0, 1].

Ejecucion: Buscar N CPU que minimice TEXEC hasta TEXEC−TMINTMIN

> Th.


Metodo I. Plataformas Computacionales

Metodo I. Busqueda Guiada

12CK20: es un sistema de memoria compartida formado por doshexa-cores (12 cores) Intel Xeon E5-2620 y una tarjeta GPU TeslaK20c (con arquitectura Kepler) con una memoria global de 4800Mbytes y 2496 cores CUDA (13 Streaming Multiprocessors y 192Streaming Processors por SM)

6CGTX690: es un equipo con un hexa-core AMD 1075T y unatarjeta GPU GeForce GTX 590 con 1536 Mbytes de memoria global y512 cores CUDA (16 Streaming Multiprocessors y 32 StreamingProcessors por SM)


Resultados experimentales. Metodo I. InstalacionConjunto Instalacion

12CK20 {384, 1152, 1920, . . . , 9600, 10368, 11136}6CGTX690 {384, 1152, 1920, . . . , 6528, 7296, 8064}En ambos sistemas N CPU se ha incrementado con multiplos de 16Se ha experimentado con umbrales de 2%, 5% y 10%

Tiempos de instalacion segun umbral

Umbral 12CK20 6CGTX6902% 92 seg. 319 seg.5% 98 seg. 370 seg.

10% 229 seg. 489 seg.

Los tiempos de instalacion no son altos con ninguno de los umbralesVeremos que las diferencias no son significativas en lasprestaciones obtenidas variando el umbral


Resultados experimentales. Metodo I. Instalacion

384 1920 3456 4992 6528 8064 9600 11136

100

200

300

400

500

600

700

800

900

1000

matrix size

GFLOPS

Installation phase - Guided Search 12CK20

threshold 2%

threshold 5%

threshold 10%

384 1920 3456 4992 6528 8064

60

80

100

120

140

160

180

200

matrix size

GFLOPS

Installation phase - Guided Search 6CGTX690

threshold 2%

threshold 5%

threshold 10%

GFLOPS obtenidos con cada umbral de instalacion

Con el umbral del 10% se consiguen siempre los mayores valores de GFLOPS

Aunque no hay diferencias significativas y con un umbral del 5% en6CGTX690 se consiguen los mismos resultados que con uno del 10% y en12CK20 solo en 2 de los 15 tamanos se obtienen valores distintos


Resultados experimentales. Metodo I. Instalacion

384 1920 3456 4992 6528 8064 9600 11136

0

2

4

6

8

10

12

14

16

matrix size

NCPU

(%)

Installation phase - Guided Search 12CK20

threshold 2%

threshold 5%

threshold 10%

384 1920 3456 4992 6528 8064

0

2

4

6

8

10

12

14

16

18

20

22

24

26

matrix size

NCPU

(%)

Installation phase - Guided Search 6CGTX690

threshold 2%

threshold 5%

threshold 10%

N CPU (%) con el que se obtiene valor mas alto GFLOPs

El comportamiento varıa en los dos sistemas

Mayor incremento en % N CPU en 6CGTX690. Diferencias en los GFLOPsentre CPU y GPU

En 12CK20 descenso % N CPU: MKL dgemm y memoria pinnedDomingo Gimenez (UMU) [email protected] JPPMG / 6-7 febrero, 2014 12 / 19

Resultados experimentales. Metodo I. ValidacionConjunto Validacion 6= Conjunto Instalacion

12CK202% 5% 10% OPTIMO

n n cpu n cpu n cpu n cpu768 0 0 0 0

1536 40 40 40 02304 184 192 192 2403072 320 368 368 3363840 408 488 504 5124608 536 632 648 6405376 736 792 792 8006144 928 944 944 9606912 1072 1088 1088 10727680 1200 1200 1200 12008448 1264 1264 1264 12809216 1280 1280 1280 12809984 1280 1280 1280 1280

10572 1297 1297 1314 155211520 1344 1344 1408 1392

6CGTX6902% 5% 10% OPTIMO

n n cpu n cpu n cpu n cpu768 64 64 64 16

1536 280 304 304 3362304 576 584 584 5763072 792 792 792 8003840 1008 1008 1008 10244608 1216 1216 1216 12165376 1440 1440 1440 14406144 1664 1644 1644 16326912 1872 1872 1872 18887680 2096 2096 2096 21128448 2208 2208 2208 2336

Valor medio GFLOPS alcanzados / Desviacion respecto al optimo (%)

Umbral 12CK20 6CGTX6902% 767.38 / 3.6% 181.39 / 1.4%5% 770.03 / 3.3% 181.40 / 1.3%

10% 773.18 / 3.0% 181.40 / 1.3%


Resultados experimentales. Metodo I. Validacion

0

200

400

600

800

1000

1200

0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000

GF

LO

PS

matrix size

Matrix multiplication - 12CK20

MKL DGEMM + CUBLAS DGEMMHybrid DGEMM Optimum

Hybrid DGEMM threshold 10%CUBLAS DGEMM

MKL DGEMM

20

40

60

80

100

120

140

160

180

200

220

0 1000 2000 3000 4000 5000 6000 7000 8000 9000

GF

LO

PS

matrix size

Matrix multiplication - 6CGTX690

MKL DGEMM + CUBLAS DGEMMHybrid DGEMM Optimum

Hybrid DGEMM threshold 10%CUBLAS DGEMM

MKL DGEMM

Resumen Busqueda Guiada

Mejora: 10% (12CK20), 31% (6CGTX690) sobre DGEMM CUBLAS

Mejora: 17% (12CK20), 21% (6CGTX690) sobre metodo GFLOPS medios

Prestaciones similares a las optimas experimentales y cercanas a las ideales(MKL DGEMM + CUBLAS DGEMM)


Modelado empırico tiempo de ejecucionEsquema Modelado Empırico




Execution

LEAST SQUARETdgemm(m,n) = k1m2n + k2m2 + k3mTdgemm gpu(m,n) and Tdgemm cpu(m,n)

ki gpu and ki cpu

Tcomu(n) = ts + ntwTcomu h2d and Tcomu d2h

tsh2d, twh2d

and tsd2h , twd2h

TEXEC = max (Tdgemm cpu + γTcomu,Tdgemm gpu + Tcomu)

INSTALLATION

Instalacion. Modelado Empırico

Experimentos guıados de forma similar al Metodo I

Estimacion de ts y tw : regresion lineal: benchmark decublasSetMatrixAsync y cublasgetMatrixAsync

Estimacion de los ki : mınimos cuadrados a resultados experimentalesobtenidos con las rutinas dgemm y cublasDgemm en un Conjunto Instalacion.


Metodo II. Plataformas Computacionales

Metodo II. Modelado Empırico

12CK20: es un sistema de memoria compartida formado por doshexa-cores (12 cores) Intel Xeon E5-2620 y una tarjeta GPU TeslaK20c (con arquitectura Kepler) con una memoria global de 4800Mbytes y 2496 cores CUDA (13 Streaming Multiprocessors y 192Streaming Processors por SM)

Instalacion

Para el Conjunto Instalacion se determina experimentalmente queγ = 1

Texec = max (Tdgemm cpu,Tdgemm gpu) + TcomuNo hay solapamiento computacion CPU y comunicacion con GPUdurante la transferencia de las matrices A y B.


Resultados experimentales. Metodo II. Validacion

Conjunto Validacion 6= Conjunto Instalacion

Modelo Optimo desviacionn n cpu time n cpu time (%)

768 0 0.0036 0 0.0036 0.001536 48 0.0199 0 0.0171 16.612304 224 0.0424 240 0.0411 3.143072 384 0.0846 336 0.0842 0.463840 512 0.1459 512 0.1459 0.004608 640 0.2359 640 0.2359 0.005376 768 0.3562 800 0.3558 0.106144 896 0.5110 960 0.5100 0.186912 1008 0.7093 1072 0.7019 1.067680 1136 0.9618 1200 0.9375 2.598448 1264 1.2305 1280 1.2255 0.419216 1376 1.9682 1280 1.5803 24.559984 1504 2.1745 1280 2.1573 0.80

10572 1616 2.3111 1552 2.3101 0.0411520 1744 3.3041 1392 3.0419 8.62

El valor optimo de N CPU se selecciona bien solo en 3 de los 15 casosPero la desviacion media respecto al optimo es de un 4%


Comparativa Metodos

2000 4000 6000 8000 10000

400

600

800

1000

matrix size

GFLOPS

Matrix Multiplication - 12CK20

Hybrid DGEMM G. SearchHybrid DGEMM Model

Hybrid DGEMM OptimumMKL + CUBLAS

GFLOPS medios conseguidos en 12CK20

En general, el modelo empırico se comporta mejor en la plataforma 12CK20

Se alcanza un valor medio de unos 785.12 GFLOPS, mientras que con labusqueda guiada (10%) se alcanzan unos 773.18 GFLOPS


Conclusiones y Trabajos Futuros

Se han comparado dos metodos de autotuning para el balanceo de ladistribucion del trabajo entre CPU y GPU en la multiplicacion dematrices:

Metodo basado en la realizacion guiada de experimentos para reducir eltiempo de experimentacionMetodo basado en un modelo teorico de tiempo de ejecucion de larutina

En general, con los dos metodos se obtienen distribuciones cercanas ala optima en los dos sistemas analizadosEn la actualidad: extension de la misma metodologıa a rutinas demayor nivel. LU, QR y Cholesky.En el futuro...: Aplicacion de estas tecnicas de autotuning ensistemas con Intel Xeon Phi, extender el trabajo a sistemas multiGPU,multiMIC, etc


sobre técnicas de optimización para la multiplicación de...

Documents