algoritmos paralelos uni

Algoritmos Paralelos

CUDA (3)

(clase 30.06.15)

Prof. J.Fiestas

Dynamics of growing SMBHs in galaxy cores Algoritmos Paralelos

Trazado de rayos (ray tracing)

Se escoge un punto de referencia (cámara) desde donde se observa un objeto (3D), y se determina la luz que alcanzará al sensor de la cámara. Cada pixel en el sensor deberá tener las mismas caracteristicas de intensidad y color que el rayo que lo alcanza. Por ello se puede cambiar la dirección del rayo y reconstruir la imagen del objeto en el sensor de acuerdo a lo que el pixel ‘ve’ del objeto (a la intersección del rayo con el objeto)

Asimismo, se puede sofisticar el modelo creando múltiples rayos para reflexión o brillo,



El trazado de rayos registrará los rayos enviados desde el pixel que alcanzen una esfera, registrando su profundidad. Solo la primera esfera se registrará, ocultando las que estén detrás. Las esferas estan descritas por una estructura con el centro de la esfera (x,y,z), su radio y colores (r,g,b)

#define INF 2e10f struct Sphere { float r,b,g; float radius; float x,y,z; __device__ float hit( float ox, float oy, float *n ) { float dx = ox - x; float dy = oy - y; if (dx*dx + dy*dy < radius*radius) { float dz = sqrtf( radius*radius - dx*dx - dy*dy ); *n = dz / sqrtf( radius * radius ); return dz + z; } return -INF; } };



El método hit() calcula si un rayo partiendo de (ox,oy), alcanza a una esfera, calculando la distancia a la esfera en caso suceda. La cámara está ubicada en el eje z en dirección al origen de coordenadas.

#define INF 2e10f struct Sphere { float r,b,g; float radius; float x,y,z; __device__ float hit( float ox, float oy, float *n ) { float dx = ox - x; float dy = oy - y; if (dx*dx + dy*dy < radius*radius) { float dz = sqrtf( radius*radius - dx*dx - dy*dy ); *n = dz / sqrtf( radius * radius ); return dz + z; } return -INF; } };



Se reserva memoria para el array de esferas en la escena. Asi como para la imagen bitmap que se llena con los la información de los pixels al hacer el trazado de rayos en el GPU

#define rnd( x ) (x * rand() / RAND_MAX) #define SPHERES 20 Sphere *s; int main( void ) { // capture the start time cudaEvent_t start, stop; ( cudaEventCreate( &start ) ); ( cudaEventCreate( &stop ) ); ( cudaEventRecord( start, 0 ) ); CPUBitmap bitmap( DIM, DIM ); unsigned char *dev_bitmap; // allocate memory on the GPU for the output bitmap ( cudaMalloc( (void**)&dev_bitmap, bitmap.image_size() ) ); // allocate memory for the Sphere dataset ( cudaMalloc( (void**)&s, sizeof(Sphere) * SPHERES ) );



Ya que generamos data en el CPU y GPU, usamos malloc() en el CPU para reservar memoria . Luego se inicializa con valores random la ubicación, radio y color de las esferas. En este ejemplo se generan 20 esferas.

// allocate temp memory, initialize it, copy to // memory on the GPU, and then free our temp memory Sphere *temp_s = (Sphere*)malloc( sizeof(Sphere) * SPHERES ); for (int i=0; i<SPHERES; i++) { temp_s[i].r = rnd( 1.0f ); temp_s[i].g = rnd( 1.0f ); temp_s[i].b = rnd( 1.0f ); temp_s[i].x = rnd( 1000.0f ) - 500; temp_s[i].y = rnd( 1000.0f ) - 500; temp_s[i].z = rnd( 1000.0f ) - 500; temp_s[i].radius = rnd( 100.0f ) + 20; }



Se copia el array de esferas al GPU usando cudaMemcpy() y liberando el buffer temporario. Luego se llama al kernel<<< >>> Finalmente, se copia la imagen resultante de nuevo al CPU y se muestra.

( cudaMemcpy( s, temp_s, sizeof(Sphere) * SPHERES, cudaMemcpyHostToDevice ) ); free( temp_s ); // generate a bitmap from our sphere data dim3 grids(DIM/16,DIM/16); dim3 threads(16,16); kernel<<<grids,threads>>>( dev_bitmap ); // copy our bitmap back from the GPU for display ( cudaMemcpy( bitmap.get_ptr(), dev_bitmap, bitmap.image_size(), cudaMemcpyDeviceToHost ) ); bitmap.display_and_exit(); // free our memory cudaFree( dev_bitmap ); cudaFree( s ); }



En el kernel, cada thread genera un pixel para la imagen de salida. Se empieza calculando las coordenadas x,y del thread . Las coordenadas (x,y) se desplazan en DIM/2 para que el eje z esté en el centro de la imagen de salida

__global__ void kernel( unsigned char *ptr ) { // map from threadIdx/BlockIdx to pixel position int x = threadIdx.x + blockIdx.x * blockDim.x; int y = threadIdx.y + blockIdx.y * blockDim.y; int offset = x + y * blockDim.x * gridDim.x; float ox = (x - DIM/2); float oy = (y - DIM/2); float r=0, g=0, b=0; float maxz = -INF; for(int i=0; i<SPHERES; i++) { float n; float t = s[i].hit( ox, oy, &n ); if (t > maxz) { float fscale = n; r = s[i].r * fscale; g = s[i].g * fscale; b = s[i].b * fscale; } }



Se recorre el array de esferas (ciclo for) para que cada rayo pruebe las intersecciones (hit())con las esferas. Asimismo, se controla si la esfera alcanzada es la mas cercana, y se almacena el color de la esfera intersectada

__global__ void kernel( unsigned char *ptr ) { // map from threadIdx/BlockIdx to pixel position int x = threadIdx.x + blockIdx.x * blockDim.x; int y = threadIdx.y + blockIdx.y * blockDim.y; int offset = x + y * blockDim.x * gridDim.x; float ox = (x - DIM/2); float oy = (y - DIM/2); float r=0, g=0, b=0; float maxz = -INF; for(int i=0; i<SPHERES; i++) { float n; float t = s[i].hit( ox, oy, &n ); if (t > maxz) { float fscale = n; r = s[i].r * fscale; g = s[i].g * fscale; b = s[i].b * fscale; } }



Finalmente se graban los colores en la imagen

ptr[offset*4 + 0] = (int)(r * 255); ptr[offset*4 + 1] = (int)(g * 255); ptr[offset*4 + 2] = (int)(b * 255); ptr[offset*4 + 3] = 255; }

R,g y b deberán inicializarse a cero para que el fondo sea negro (ninguna esfera sera alcanzada)


Constant memory El cuello de botella no es en este caso el rendimiento del GPU sino el ancho de banda. Ya que podemos seguir alimentando los ALU (Arithmetic Logic Unit) por la rapidez de estas unidades de cálculo. Se usa memoria constante en data que no va a ser modificada durante la ejecución del kernel. GPUs Nvidia proveen 64 KB de memoria constante


Trazado de rayos (ray tracing) usando memoria constante

Ya que el ejemplo anterior solo tiene un input (array de esferas), se puede definir este como memoria constante. En este caso, no hay necesidad de asignar memoria con cudaMalloc() o liberar memoria con cudaFree(), pero el tamaño del array deberá ser definido al inicio. Otro cambio es usar cudaMemcpyToSymbol() que copia a memoria constante, en vez de cudaMemcpy() usando cudaMemcpyHostToDevice, que copia a memoria global.

__constant__ Sphere s[SPHERES];

cudaMemcpyToSymbol( s, temp_s, sizeof(Sphere) * SPHERES ) ;


Performance usando memoria constante

Memoria constante solo puede ser leída. Esto puede ahorrar ancho de banda ya que: -  Una sola lectura de memoria constante puede ser

compartida por threads en un warp, evitando múltiples lecturas

-  Memoria constante esta reservada (cached) por lo que no cae en mayor tráfico de memoria.

Un warp es un grupo de 32 threads que están unidos físicamente (en construción). Ellos ejecutan la misma instrucción a la vez (con datos distintos). Cada lectura de memoria constante se reparte a la mitad de un warp (half-warp, 16 threads)



Para medir performance podemos utilizar el event API de CUDA. Un evento en CUDA es un registro de tiempo en un momento definido por el usuario. Ya que el GPU lo registra, se evitan retrasos al querer medir tiempos con el CPU Para registrar el tiempo actual se hace de la siguiente manera:

cudaEvent_t start; cudaEventCreate(&start); cudaEventRecord( start, 0 );



Para medir tiempos en una porción de código se crea un evento de inicio y final

cudaEvent_t start, stop; cudaEventCreate(&start); cudaEventCreate(&stop); cudaEventRecord( start, 0 ); // do some work on the GPU cudaEventRecord( stop, 0 );



Sin embargo, tareas en CUDA no están sincronizadas con el CPU, el que trabaja mientras el GPU continúa. Por ello se utiliza la función API cudaEventSynchronize() para instruir al CPU sincronizar un evento cudaEvent_t start, stop;

cudaEventCreate(&start); cudaEventCreate(&stop); cudaEventRecord( start, 0 ); // do some work on the GPU cudaEventRecord( stop, 0 ); cudaEventSynchronize( stop );


Texture memory

Esta ubicada fisicamente en el chip, como la memoria constante


Texture memory Es usada cuando threads deben leer de una dirección cercana. En un CPU las direcciones no están almacenadas consecutivamente, pero en GPUs memoria de textura esta diseñada para acelerar estos accesos (a través de texture caches), lo que aumenta el performance en comparación con el uso de memoria global


Aplicación: transferencia de calor Simulación de transferencia de calor en un modelo 2D. Cada punto de malla representa un calentador con una determinada temperatura. En este modelo, los calentadores iniciales mantienen su temperatura constante, y el calor fluye a los vecinos en el tiempo. Si los vecinos tienen temperaturas mayores, las celdas se calentarán, y si son menores se enfriaran.


Aplicación: transferencia de calor La nueva temperatura en una celda sera igual a la suma de las diferencias entre su temperatura y la temperatura de sus vecinos. La constante k representa una proporcionalidad de transferencia de calor en el sistema. A mayor k, la temperatura de equilibrio se alcanzará rápidamente. Al considerar solo 4 vecinos, y siendo k y TOLD constantes, la ecuación se reduce a:


Aplicación: transferencia de calor

El método: -  Crear la malla de celdas con temperaturas iniciales

(cero o mayor que cero) -  Actualizar las temperaturas basadas en la ecuación

anterior -  La malla de temperaturas de salida de este paso sera la

malla de entrada del paso siguiente


Aplicación: transferencia de calor

__global__ void copy_const_kernel( float *iptr, const float *cptr ) { // map from threadIdx/BlockIdx to pixel position int x = threadIdx.x + blockIdx.x * blockDim.x; int y = threadIdx.y + blockIdx.y * blockDim.y; int offset = x + y * blockDim.x * gridDim.x; if (cptr[offset] != 0) iptr[offset] = cptr[offset]; }

Este kernel copia las temperaturas de una malla constante a una malla de inicio. Primero se definen las coordenadas x,y, y se copian las temperaturas de inicio de cptr[ ] en iptr[ ] (malla de inicio)


Aplicación: transferencia de calor __global__ void blend_kernel( float *outSrc, const float *inSrc ) { // map from threadIdx/BlockIdx to pixel position int x = threadIdx.x + blockIdx.x * blockDim.x; int y = threadIdx.y + blockIdx.y * blockDim.y; int offset = x + y * blockDim.x * gridDim.x; int left = offset - 1; int right = offset + 1; if (x == 0) left++; if (x == DIM-1) right--; int top = offset - DIM; int bottom = offset + DIM; if (y == 0) top += DIM; if (y == DIM-1) bottom -= DIM; outSrc[offset] = inSrc[offset] + SPEED * ( inSrc[top] + inSrc[bottom] + inSrc[left] + inSrc[right] - inSrc[offset]*4); }

Cada thread representa una celda en la simulación, leerá su temperatura y la de sus vecinos, y actualizará la temperatura de acuerdo a la ecuación


Animación de transferencia de calor #define DIM 1024 #define PI 3.1415926535897932f #define MAX_TEMP 1.0f #define MIN_TEMP 0.0001f #define SPEED 0.25f // globals needed by the update rouMne struct DataBlock { unsigned char *output_bitmap; float *dev_inSrc; float *dev_outSrc; float *dev_constSrc; CPUAnimBitmap *bitmap; cudaEvent_t start, stop; float totalTime; float frames; };

El ejemplo cuenta con temporizador de eventos CUDA


void anim_gpu( DataBlock *d, int ticks ) { ( cudaEventRecord( d->start, 0 ) ); dim3 blocks(DIM/16,DIM/16); dim3 threads(16,16); CPUAnimBitmap *bitmap = d->bitmap; for (int i=0; i<90; i++) { copy_const_kernel<<<blocks,threads>>>( d->dev_inSrc, d->dev_constSrc ); blend_kernel<<<blocks,threads>>>( d->dev_outSrc, d->dev_inSrc ); swap( d->dev_inSrc, d->dev_outSrc ); }

anim_gpu() llama a la animación de cada imagen. Se utilizan blocks de 256 threads (16x16). Cada iteración del ciclo for calcula una unidad de tiempo de la simulación. Una imagen se calcula cada 90 unidades de tiempo.

Animación de transferencia de calor


float_to_color<<<blocks,threads>>>( d-‐>output_bitmap, d-‐>dev_inSrc ); ( cudaMemcpy( bitmap-‐>get_ptr(), d-‐>output_bitmap, bitmap-‐>image_size(), cudaMemcpyDeviceToHost ) ); ( cudaEventRecord( d-‐>stop, 0 ) ); ( cudaEventSynchronize( d-‐>stop ) ); float elapsedTime; ( cudaEventElapsedTime( &elapsedTime, d-‐>start, d-‐>stop ) ); d-‐>totalTime += elapsedTime; ++d-‐>frames; prind( "Average Time per frame: %3.1f ms\n", d-‐>totalTime/d-‐>frames ); } void anim_exit( DataBlock *d ) { cudaFree( d-‐>dev_inSrc ); cudaFree( d-‐>dev_outSrc ); cudaFree( d-‐>dev_constSrc ); ( cudaEventDestroy( d-‐>start ) ); ( cudaEventDestroy( d-‐>stop ) ); }

El kernel float_to_color() convierte temperaturas a colores y copia la imagen resultante al CPU con cudaMemcpy()


int main( void ) { DataBlock data; CPUAnimBitmap bitmap( DIM, DIM, &data ); data.bitmap = &bitmap; data.totalTime = 0; data.frames = 0; ( cudaEventCreate( &data.start ) ); ( cudaEventCreate( &data.stop ) ); ( cudaMalloc( (void**)&data.output_bitmap, bitmap.image_size() ) ); // assume float == 4 chars in size (i.e., rgba) ( cudaMalloc( (void**)&data.dev_inSrc, bitmap.image_size() ) ); ( cudaMalloc( (void**)&data.dev_outSrc, bitmap.image_size() ) ); ( cudaMalloc( (void**)&data.dev_constSrc, bitmap.image_size() ) ); float *temp = (float*)malloc( bitmap.image_size() );

for (int i=0; i<DIM*DIM; i++) { temp[i] = 0; int x = i % DIM; int y = i / DIM; if ((x>300) && (x<600) && (y>310) && (y<601)) temp[i] = MAX_TEMP; } temp[DIM*100+100] = (MAX_TEMP + MIN_TEMP)/2; temp[DIM*700+100] = MIN_TEMP; temp[DIM*300+300] = MIN_TEMP; temp[DIM*200+700] = MIN_TEMP; for (int y=800; y<900; y++) { for (int x=400; x<500; x++) { temp[x+y*DIM] = MIN_TEMP; } }

Animación de transferencia de calor


( cudaMemcpy( data.dev_constSrc, temp, bitmap.image_size(), cudaMemcpyHostToDevice ) ); for (int y=800; y<DIM; y++) { for (int x=0; x<200; x++) { temp[x+y*DIM] = MAX_TEMP; } } ( cudaMemcpy( data.dev_inSrc, temp, bitmap.image_size(), cudaMemcpyHostToDevice ) ); free( temp ); bitmap.anim_and_exit( (void (*)(void*,int))anim_gpu, (void (*)(void*))anim_exit ); }

Una imagen de la simulación de transferencia de calor

bitmap.anim_and_exit() llama a las funciones y kernels


Job scheduler Control de trabajos en el background (batch processing) Tipicamente, con una interfase gráfica, proveen un control de monitoreo y ejecución automatizado de una red de procesadores. Actualmente, dominan diferentes arquitecturas asi como sistemas operativos. Aplicación importante es el control de colas de trabajos en un cluster de computadores, asignando trabajos a procesadores con menor carga


Platform Load Sharing Facility (LSF)

Es una plataforma de manejo de trabajos en un medio de HPC. Se utiliza para ejecutar tareas de batch (ejecución automática de tareas) en redes de sistemas operativos Linux o Windows en distintas arquitecturas. Adquirido en el 2012 por IBM.


Platform Load Sharing Facility (LSF) En un medio distribuído (cientos de hosts): -  Monitorear y controlar fuentes es complejo -  El uso de recursos no es balanceado -  El usuario percibe estas deficiencias

Que recurso usar?

LSF manejará y asignará el mejor recurso disponible para los trabajos (jobs)


http://laohu.bao.ac.cn/ganglia/

Ejemplo: sistema LAOHU en NAOC, Beijing


Comandos de control LSF

algoritmos paralelos uni

Documents