parteb - programacionbasicoi · conceptos básicos de programación paralela en los ejemplos que se...

3EAGPGPU3EAGPGPU

CUDA Básico

PARTE B PARTE B –– ProgramaciónProgramación I I 3EA3EAGPGPUGPGPU

3EAGPGPU3EAGPGPU

Pablo Pablo EzzattiEzzatti

Parte B


ContenidoContenido

• Conceptos básicos de programación paralela

• Modelo de programación CUDA

• Programación CUDA básico

– Conceptos básicos

– Estrategias de memoria compartida


Conceptos básicos de

Programación Paralela


Programación Paralela

Conceptos Básicos de Programación Paralela

• Múltiples unidades de cómputo trabajando en forma

coordinada

• Comunicación

• Sincronización


• División

• De tareas

• De datos


• Paralelismo de

• Memoria compartida (multi-core)

• Memoria distribuida (cluster)

• Contexto


• Contexto

• Homogéneo

• Heterogéneo

• Balance de carga


En este caso:

• Muchas unidades de cómputo trabajando en forma

coordinada.


• División de datos.

• Paralelismo “similar” a paralelismo a memoria compartida

(multi-core).

• Unidades de procesamiento homogéneas.


En los ejemplos que se verán a continuación:

• Se utilizará una sintaxis inspirada en la de Matlab.

• El código escrito en color negro ejecuta en forma secuencial.

• El código escrito en color indica palabras reservadas que son


• El código escrito en color azul indica palabras reservadas que son

directivas para el manejo de paralelismo.

• El código escrito en color rojo indica el punto de ramificación del

paralelismo.

• El código escrito en color verde es el código que es ejecutado en forma

paralela por cada una de las unidades de procesamiento.


Ejemplo 0:

• Se tiene una matriz con

4 columnas y se quiere

obtener la suma por

columnas de la matriz.

• Se dispone de una única


• Se dispone de una única

unidad de

procesamiento.


Ejemplo 0:

Res = zeros(1,4)

[m,n] = size(Mat)

For j = 1:4

For i = 1 : m


For i = 1 : m

Res(j) = Res(j) + Mat(i,j)


Ejemplo 1:

• Se tiene una matriz con

4 columnas y se quiere

obtener la suma por

columnas de la matriz.

• Se dispone de cuatro


• Se dispone de cuatro

unidades de

procesamiento.


Ejemplo 1:

Res = zeros(1,4)

[m,n] = size(Mat)

begin_parallel(4)

For j = 1:4

For i = 1 : m


For i = 1 : m


end_parallel


Ejemplo 2:

• Se tiene una matriz con 400 columnas y se quiere obtener la

suma por columnas de la matriz.

• Se dispone de cuatro unidades de procesamiento.



Ejemplo 2:

Res = zeros(1,400)

[m,n] = size(Mat)

begin_parallel(4)

For j = 1:400

For i = 1 : m


For i = 1 : m


end_parallel


Ejemplo 3:

• Se tiene una matriz cuadrada con 400 columnas y se quiere

obtener la suma por columnas de la matriz triangular superior.




Distribución de datos/cálculos


Distribución por bloque Distribución cíclica


Ejemplo 3:

• Es posible achicar el tamaño de los bloques.

• Por ejemplo: de 100 columnas pasar a 10 columnas por bloque.

Res = zeros(1,400)


[m,n] = size(Mat)

begin_parallel(40,cyc)

For j = 1:400

For i = 1 : j


end_parallel


Ejemplo 4:


suma por columnas de la matriz.


• En este caso, además se quiere obtener la suma parcial por


• En este caso, además se quiere obtener la suma parcial por

unidad de procesamiento.


Ejemplo 4:



Ejemplo 4:

Res = zeros(1,400)

Res2 = zeros(1,4)

[m,n] = size(Mat)

begin_parallel(40)

For j = 1:400


For j = 1:400

private idP = myId()

For i = 1 : j


Res2(idP) = Res2(idP) + Res(j)

end_parallel


Ejemplo 5:


suma de todos los elementos de la matriz.





Solución 1

• Se suma por columna


• Luego se suma todo el vector intermedio


Solución 1

• Se suma por columna y luego se suma el vector intermedio.

Res = zeros(1,400)

[m,n] = size(Mat)

begin_parallel (4)


begin_parallel (4)

For j = 1:400

For i = 1 : m


end_parallel

For j = 1:400

Sum = Sum + Res(j)


Solución 2

• Se suma por columnas para cada unidad de procesamiento.


• Luego se suma el vector intermedio.


Solución 2

• Se suma por columnas

para cada unidad de

procesamiento y luego

se suma el vector

intermedio.

Res = zeros(1,4)

[m,n] = size(Mat)

begin_parallel(4)

For j = 1:400

private idP = myId ()

For i = 1 : m


intermedio. For i = 1 : m

Res(idP) = Res(idP) + Mat(i,j)

end_parallel

For j = 1:4

Sum = Sum + Res(j)


Solución 3

• Sumo por columna

y actualizo el

resultado.

Res = zeros(1,4)

[m,n] = size(Mat)

begin_parallel(4)

For j = 1:400



• Concepto de

reduce

For i = 1 : m

Res(idP) = Res(idP) + Mat(i,j)

end_parallel

begin_parallel(2)

For j = 1:4

Sum = Sum + Res(j)

end_parallel


Race condition:

- Los hilos compiten por

el acceso a los

registros.

- Pueden haber distintos

ordenes de ejecución.

Res = zeros(1,4)

[m,n] = size(Mat)

begin_parallel(4)

For j = 1:400


For i = 1 : m


ordenes de ejecución.

- Distinto orden de

ejecución produce

resultados

diferentes!!!

- Este problema también

aparece en circuitos

electrónicos, base de

datos, etc.

For i = 1 : m

Res(idP) = Res(idP) +Mat(i,j)

end_parallel

begin_parallel(2)

For j = 1:4

Sum = Sum + Res(j)

end_parallel


[m,n] = size(Mat)

begin_parallel(4)

private Res

For j = 1:400

Reduce:

- Generalmente están

disponibles diversas

operaciones:

• +


%private idP = myId ()

For i = 1 : m

Res = Res + Mat(i,j)

end_parallel (reduce(+,Res) )

• +

• *

• min

• max


Consideremos el

siguiente código:

• Hay problemas por el

acceso concurrente a

la variable aux.

Res = zeros(1,11)

aux = 11

begin_parallel(400)

For j = 1:400

if ( aux == 1)


if ( aux == 1)

aux = aux + 10

else

aux = aux - 1

end

Res(aux) = Res(aux) +Mat(aux,j)

end_parallel


Diferentes formas de

resolverlo:

• Semáforos

• Zonas mutuo

excluidas

Res = zeros(1,11)

aux = 11

begin_parallel(400)

For j = 1:400

if ( aux == 1)


excluidas

• Operaciones atómicas

if ( aux == 1)

aux = aux + 10

else

aux = aux - 1

end

Res(aux) = Res(aux) + Mat(aux,j)

end_parallel


Res = zeros(1,11)

begin_parallel(400)

For j = 1:400

begin_mutex()

if (aux == 1)

aux = aux + 10

Con zonas mutuo

excluidas

Solo un “hilo de

ejecución” entra en la


aux = aux + 10

else

aux = aux - 1

end

Res(aux) = Res(aux) +Mat(aux,j)

end_mutex()

end_parallel

ejecución” entra en la

zona.


Res = zeros(1,400)

[m,n] = size(Mat)

begin_parallel(4)

Operaciones atómicas


For j = 1:400

For i = 1 : m


Sum = Sum + Res(j)

end_parallel


Res = zeros(1,400)

[m,n] = size(Mat)

begin_parallel(4)

For j = 1:400

For i = 1 : m

Operaciones atómicas


For i = 1 : m


begin_atomic()

Sum = Sum + Res(j)

end_atomic()

end_parallel


Diferentes caminos dependiendo del thread

begin_parallel(400)

For j = 1:400


if ( mod(idP,2) == 0)


• Estrategia comúnmente utilizada para implementar el modelo de

paralelismo Maestro-Esclavo: if soyMaestro()

if ( mod(idP,2) == 0)

Mat(j) = Mat(j) + 4

else

Mat(j) = Mat(j) + 2

end

end_parallel


Conceptos vistos

• Paralelismo

• Estrategias de scheduling y balance de carga

• Distribución de datos/cálculos


• Distribución de datos/cálculos

• Utilizar información del thread/proceso/etc.

• Reducciones

• Race conditions

• Operaciones atómicas

e


Es conveniente tener en cuenta:

• La importancia del scheduling, distribución de

datos/cálculos y control de sincronizaciones para un

buen desempeño.


buen desempeño.

• Si bien parece obvio, además de buen desempeño es

necesario correctitud. Sin embargo, esto es más

complejo de comprobar que en programas secuenciales.

Modelo de programación CUDA


IntroducciónIntroducción

El device:

• Es un coprocesador de la CPU (host).

• Posee su propia memoria DRAM (memoria del device).


• Ejecuta “muchos” threads en paralelo.

Una porción de los cálculos con paralelismo de datos se computan

con kernels en el device que corren en “muchos” threads.


Diferencias entre los threads de la GPU y CPU

• Los threads en GPU son extremadamente livianos :

Muy poco overhead para crearlos.


Muy poco overhead para crearlos.

• La GPU necesita 100s – 1000s de threads para alcanzar la

eficiencia:

Generalmente las CPU (multi-core ) necesitan unos pocos.


Se integra código en el host con código en la tarjeta:

• El código del host puede ser secuencial o paralelo.

• En la tarjeta el código es altamente paralelo (SPMT).

Código en el host (sequencial)


. . .

. . .

(sequencial)

Kernel device (paralelo) KernelA<<< nBlk, nTid >>>(args);

Código en el host (paralelo)

Kernel device (paralelo) KernelB<<< nBlk, nTid >>>(args);


Algoritmo básico

1. Instrucciones en el host

2. Se envían los datos del host a la GPU


2. Se envían los datos del host a la GPU

3. Se procesa en GPU

4. Se recuperan los datos

5. Continúan instrucciones en el host


Array de threads

• Un kernel es ejecutado por un array de threads

– Todos los threads corren el mismo código (SPMT) – Cada thread tiene un ID que se puede utilizar para computar

direcciones de memoria y tomar decisiones de control


direcciones de memoria y tomar decisiones de control

76543210

…float x = input[threadID];float y = func(x);output[threadID] = y;…

threadID


Bloques de threads

• Facilita la escalabilidad .

• Permite dividir un array de threads en múltiples bloques

• Threads en un mismo bloque cooperan via memoria

shared, operaciones atomic y barrier de sincronización.

• Threads en diferentes bloques no pueden cooperar


• Threads en diferentes bloques no pueden cooperar

directamente.


threadID



76543210 76543210

Thread Block 0 Thread Block N - 176543210

Thread Block 0


Jerarquía de threads



IDs bloque e IDs de thread

• Cada thread usa el IDs paradecidir sobre que datostrabajar

– Block ID: 1D, 2D o 3D (3D desdeFermi)


– Thread ID: 1D, 2D o 3D

• Puede simplificar el direccionamiento de memoria

– Procesamiento de imágenes.

– Resolución de PDEs (regulares) en 3D.


Jerarquía de threads

• Los bloques dentro de un grid tienen que ser

independientes.

• Los bloques de threads son ejecutados en


• Los bloques de threads son ejecutados en

cualquier orden y en principio en diferentes

multiprocesadores.

• En las tarjetas (“nuevas”) hay ejecución

concurrente de kernels (aqui no lo vamos a tener

en cuenta !!!).

Programación en CUDA



hostdevice__global__ void KernelFunc()

devicedevice__device__ float DeviceFunc()

Invocable

desde:

Ejecutable

en:

Las funciones


hosthost__host__ float HostFunc()

• __global__ define funciones “kernel”

• __device__ y __host__ pueden ser utilizados juntas

(con compilación condicional).

• __host__ puede no ponerse.


• Para invocar un kernel es necesario determinar “una

configuración de ejecución”.

__global__ void KernelFunc(...);

PARTE B PARTE B –– ProgramaciónProgramación I I 33EAEAGPGPUGPGPU

dim3 DimGrid(100, 50); // 5000 bloques

dim3 DimBlock(4, 8, 8); // 256 threads por block

size_t SharedMemBytes = 64; // 64 bytes de memoria shared

KernelFunc<<< DimGrid, DimBlock, SharedMemBytes >>>(...);

• Las llamadas a kernels son asincrónicas !!

Es necesario utilizar sincronizaciones explícitas.


Espacios de declaración de variables

Se dispone de distintos espacios (unificados) de

declaración:

• global

• _device_ residen en la memoria global del device.


• _device_ residen en la memoria global del device.

• _shared_ reside en la memoria shared del device.

extern _shared_ para allocamiento dinámico.

• _constant_ reside en memoria constante del device.

__device__ float filter[N]; __global__ void convolve (float *image) __shared__ float region[M];extern __shared__ float region[];


CUDA posee diversas keywords

– threadIdx (uint3) se accede con .x/.y/.z

– blockIdx (uint3) se accede con .x/.y/.z

– blockDim (dim3) se accede con .x/.y/.z


– blockDim (dim3) se accede con .x/.y/.z

– gridDim (dim3) se accede con .x/.y/.z

region[ threadIdx.x ] = image[i];


Funciones intrínsecas

• cudaDeviceSynchronize() : sincroniza todos los threads.

Ejecuta en el host.

• __syncthreads : permite sincronizar threads del mismo bloque.

Se invoca dentro de un kernel.


Se invoca dentro de un kernel.

• clock_t clock() : permite medir tiempos en el device.

Funciones matemáticas (más rápidas pero con posible diferencia

en el valor):

__sinf(x), __cosf(x), __log2f(x) …. __powf(x,y)

Funciones atómicas:

atomicAdd(), … atomicMin(), …


La API ofrece diversas funciones

• Para manejo de memoria

• Para transferencias

• Para manejo de las ejecuciones (lanzamiento)


• Para manejo de las ejecuciones (lanzamiento)

// Allocate memoria en GPU void *myimage = cudaMalloc((void**)& SDEVPTR, bytes)


CUDA Device Memory Allocation

• cudaMalloc ()

– Reserva espacio en la memoria

global del device

– Dos parámetros

• Puntero

Grid

Block (0, 0)

Shared Memory

Registers Registers

Block (1, 0)

Shared Memory

Registers Registers


• Puntero

• Tamaño de la memoria

reservada

• cudaFree ()

– Libera la memoria asociada a un

puntero en la mem. global del device

GlobalMemory

Thread (0, 0) Thread (1, 0) Thread (0, 0) Thread (1, 0)

Host

La reserva de memoria global se realiza en el host !!!


• Código de ejemplo

– Reservar una matriz de 64 * 64 floats (precisión

simple).

TILE_WIDTH = 64;


TILE_WIDTH = 64;float* SDEVPTRint size = TILE_WIDTH *TILE_WIDTH* sizeof(float);

cudaMalloc((void**)& SDEVPTR, size);

…..

cudaFree(SDEVPTR);


Transferencias de datos Host-Device

• cudaMemcpy()

– Transferencia de datos

– 4 parámetros

• Puntero destino

• Puntero origen

Grid

Block (0, 0)

Shared Memory

Block (1, 0)

Shared Memory


• Puntero origen

• Número de bytes a copiar

• Tipo de transferencia

– Host to Host

– Host to Device

– Device to Host

– Device to Device

• Transferencias asincrónicas

GlobalMemory

Shared Memory

Thread (0, 0)

Registers

Thread (1, 0)

Registers

Shared Memory

Thread (0, 0)

Registers

Thread (1, 0)

Registers

Host


– cudaMemcpyHostToDevice y cudaMemcpyDeviceToHost

• Código de ejemplo

– Trasferir una matriz de 64 x 64 floats (precisión

simple)


– cudaMemcpyHostToDevice y cudaMemcpyDeviceToHostson constantes simbólicas.

cudaMemcpy(SDEVPTR, SHPTR, size, cudaMemcpyHostToDe vice);

cudaMemcpy(SHPTR, SDEVPTR, size, cudaMemcpyDeviceTo Host);


Lanzamiento

• Dimensiones de la grilla (3D): variable de tipo dim3

• Dimensiones de los bloques de threads (3D): variable de tipo dim3

• Opcionales:


dim3 gridSize( 16, 16 );dim3 blockSize( 32, 32 );kernel<<<gridSize, blockSize, 0, 0>>>( ... );kernel<<<32, 512>>>( ... );

• Opcionales:

• cantidad de memoria compartida por bloque

• identificador de stream


Retomando los ejemplos de programación paralela básica:

• Consideramos que se tiene una matriz con número grande de

columnas y se quiere obtener la suma por columnas de la

matriz.



• Ejemplo, suma por columna de los elementos de una matriz.

void SumaColMatriz(int M, int N, float * Mh, float* N h){int size = M * N * sizeof(float), size2 = N*sizeof(f loat);float* Md, *Nd;…

// Allocate en device cudaMalloc(&Md, size);cudaMalloc(&Nd, size2);

// Inicializo matrices en el device


// Inicializo matrices en el devicecudaMemcpy(Md, Mh, size, cudaMemcpyHostToDevice);cudaMemset(Nd ,0, size2);

// Invocar el kernel que suma en GPU

// Traer resultado ;cudaMemcpy(Nh, Nd, size2, cudaMemcpyDeviceToHost);

// Free matrices en devicecudaFree(Md); cudaFree(Nd); }


Kernel

// Suma por columnas de una matriz__global__ void SumaColMatrizKernel(int M, float* Md , float* Nd) {// Pvalue es usado para el valor intermedio

float Pvalue = 0;int aux = threadIdx.y *M;for (int k = 0; k < M; ++k) {

Pvalue = Pvalue + Md[ aux+k ];


Pvalue = Pvalue + Md[ aux+k ];}Nd[threadIdx.y] = Pvalue;

}


Lanzamiento del kernel

// configuración de la ejecucióndim3 tamGrid(1, 1); //Grid dimensióndim3 tamBlock(1,N,1); //Block dimensión// lanzamiento del kernel


// lanzamiento del kernelSumaColMatrizKernel <<<tamGrid, tamBlock>>>(M, Md, Nd);

Restricciones:

• Solo se pueden procesar matrices de tantas columnas

como threads en un bloque !!!!

• Un solo bloque, un solo multiprocesador computando.


Vamos a la máquina 1

• Ver los códigos para el programa principal y el kernel 1.

• Compilar.

• Ejecutar.


• Ejecutar.

parteb - programacionbasicoi · conceptos básicos de programación paralela en los ejemplos que se...

Documents