Un ejemplo básico, parte III: Análisis del rendimiento

Para realizar las pruebas se ha utilizado la plataforma "Davinci" que es una computadora gestionada por el Grupo de Investigación TIC-146 Supercomputación: Algoritmos de la Universidad de Almería. Este servidor multicore dedicado a computación GPGPU cuenta con:

 2 Intel Xeon Quad Core E5640 2.67 GHz 64 bits

 GeForce GTX 295 (2x240 cores)

 2 Tesla C2050 (Fermi) (448 cores)

 GeForce GTX 480 (480 cores)

Todas las GPU son Compatibles con CUDA, si bien sólo las Tesla C2050 y la GeForce GTX 480 ofrecen las prestaciones de cómputo 2.0 necesarias para aprovechar al máximo las prestaciones de CUDA 4.

El sistema operativo de este servidor es un Linux Version  de kernel 2.6.26-2-amd64, con una distribución Debian GNU/Linux 5.0.8 (lenny). La versión de Cuda instalada es la 4.0.

Los programas se han desarrollado en lenguaje C y CUDA, utilizando los compiladores gcc (The GNU Compiler Collection) y nvgc (el compilador CUDA de nVidia).

Las pruebas se han realizado sobre diferentes tamaños de vectores partiendo de 10.000 elementos, y con incrementos de ese mismo número hasta llegar a los 1.000.000 de elementos del vector.

A.     Reducción de matrices

En las pruebas no se ha tenido en cuenta el tiempo de introducir valores aleatorios a los elementos del vector, ya que es común para los tres escenarios. Los tres escenarios comparados son los siguientes: por un lado la versión secuencial de la suma ejecutada en la CPU, nuestro algoritmo de reducción de vectores propuesto, y la reducción de vectores que la nueva librería Thrust® ofrece y que simplifica la programación paralela para CUDA.

Cada uno de los test se ha realizado 10 veces consecutivas y se ha calculado la media aritmética de los resultados obtenidos.

Para medir los tiempos de respuesta de cada uno de los algoritmos hemos utilizado la gestión de eventos de CUDA. Dentro del tiempo de cómputo para las versiones paralelas, se ha incluido el tiempo de copia de memoria principal a memoria de dispositivo y viceversa. La siguiente tabla muestra los resultados obtenidos en el test:

N	CPU	GPU1	Thrust
10000	0.0000382	0.00007563	0.00031225
20000	0.0000758	0.00010429	0.00031417
30000	0.0001138	0.00013749	0.00033243
40000	0.0001512	0.00016749	0.00035026
50000	0.0001884	0.00019928	0.00036693
60000	0.0002266	0.00022946	0.0003838
70000	0.0002640	0.00025606	0.00040174
80000	0.0003020	0.00028915	0.00041772
90000	0.0003392	0.00031836	0.00043793
100000	0.0003770	0.00035073	0.00046362
110000	0.0004146	0.00038296	0.00049638
120000	0.0004536	0.00041684	0.00051473
130000	0.0004896	0.00044498	0.00056173
140000	0.0005274	0.00046391	0.00058575
150000	0.0005678	0.00048342	0.0005885
160000	0.0006090	0.00050197	0.00060389
170000	0.0006442	0.00051199	0.00061768
180000	0.0006782	0.00052612	0.00063185
190000	0.0007172	0.00054233	0.00064476
200000	0.0007548	0.00055549	0.00066341

Tabla 1. Tiempo (en segundos) de respuesta para los algoritmos

La tabla anterior muestra en la columna N el número de elementos del vector tratado, la columna CPU muestra los tiempos de respuesta obtenidos para el algoritmo en serie sobre la CPU, la columna GPU1 se refiere al algoritmo de reducción propuesto y finalmente Thrust muestra los tiempos de respuesta obtenidos utilizando las librerías Thrust®.

Como se puede observar el rendimiento obtenido con nuestra propuesta de algoritmo es bastante superior al rendimiento obtenido por el algoritmo de reducción de la librería Thrust de nVidia.

Figura 1. Comparativa rendimientos obtenidos

Se realizó una segunda comparativa entre CPU y GPU1 con un crecimiento exponencial de elementos de la forma 1024ⁱ para i = 1 hasta 12 con los siguientes resultados:

N	CPU	GPU1	SpeedUp
1024	0.0000042	0.00004873	0.08618921
2048	0.0000082	0.00004486	0.18279091
4096	0.000016	0.00005397	0.296461
8192	0.0000318	0.00006936	0.45847751
16384	0.0000624	0.00009197	0.67848211
32768	0.000124	0.00014606	0.84896618
65536	0.0002474	0.00024655	1.00344758
131072	0.000494	0.00045282	1.09094121
262144	0.000992	0.00070173	1.41364912
524288	0.0019882	0.00116573	1.70554073
1048576	0.0039892	0.00213745	1.86633605
2097152	0.0109062	0.00441923	2.46789599

Tabla 2. SpeedUp respecto a GPU1

En la siguiente figura se puede observar cómo la pendiente de la tendencia creciente exponencial de la GPU1 es minorada por el factor de SpeedUp obtenido en cada tramo:

Figura 2. Evolución del SpeedUp al aumentar N

B.     Determinación del Punto Muerto Computacional[1]

Trataremos de determinar el punto donde es indiferente realizar los cálculos en CPU respecto de la GPU ó

GPU respecto de la CPU porque el rendimiento sea el mismo. En las pruebas anteriores, hemos podido observar cómo en los tramos donde el número de elementos que componen el vector a reducir es bajo, se daba la situación que el algoritmo en serie ejecutado en la CPU obtenía mejores resultados que sus homólogos paralelizados sobre GPU. Evidentemente debemos de tener esto en cuenta a la hora de decidir en donde debemos ejecutar cada trabajo.

Dicho punto coincidirá con el punto de corte de las funciones que representan el tiempo de ejecución que emplea cada algoritmo en procesar exactamente el mismo trabajo (incluidos en este caso para los algoritmos de GPU, los tiempos de proceso consumidos en la transferencia de memoria principal a memoria del dispositivo y una vez realizado el cálculo, vuelta a recibir los datos a memoria principal) y obtener exactamente el mismo resultado.

Si realizamos un zoom sobre los datos tratados apreciamos

Figura 3. Punto de corte función CPU y GPU1

un punto de corte entre las funciones de tiempo de respuesta sobre el tamaño N del vector. Así, en la Figura 18 podemos observar cómo ese punto de corte está cerca de los 70000 elementos. Podemos decir que en este punto es indiferente la utilización de un algoritmo u otro en términos de tiempos de ejecución. Por debajo de este valor sería mejor computar sobre la CPU, mientras que por encima de ese valor sería mejor hacerlo en GPU.

Evidentemente, esta visión es algo ingenua, y se deberían tener otros factores en cuenta a la hora de tomar esta decisión.

- Coste de utilización: es el coste que implica la utilización de cada escenario. En muchos casos (como en grandes centros de computación) se calcula como la suma del coste de adquisición  más el coste en potencia (watios) por euro de cada recurso.

- Coste de oportunidad[2]: es un concepto más sutil pero muy interesante a la hora de tomar decisiones económicas. Aplicado a nuestro caso, se puede definir como el coste que supone la decisión de computar un algoritmo en un recurso (que es escaso) y no computar o descartar la computación de otro algoritmo en ese mismo recurso.

Teniendo en cuenta los costes anteriores se podrán tomar decisiones por ejemplo: de utilizar una GPU para realizar un determinado proceso aunque el tiempo de respuesta sea similar o peor al obtenido en CPU, debido a que el coste por watio de la GPU es muy inferior, y a que el coste del trabajo que puede realizarse en la CPU sea mucho mayor.

C.      Determinación del Factor de Desenrollado

Ya se habló en post anteriores de la importancia de este factor, y de cómo ha sido un caballo de batalla en los compiladores desde los inicios de la informática.

El objetivo fundamental que perseguimos con esta técnica es compensar los efectos negativos en el rendimiento que producen los tiempos de latencia que se producen en los accesos a memoria.

De forma intuitiva, podemos expresar este efecto como el que se produce en las líneas de autobuses urbanos: un autobús puede transportar 50 pasajeros a la vez, tarda prácticamente lo mismo si trasporta 1 o si trasporta a 50. El problema está en que la compañía de autobuses espera optimizar su beneficio, y establece unos horarios de salida y llegada, por eso, aunque un pasajero suba al autobús, deberá esperar cierto tiempo hasta ser trasportado a su destino. En nuestro caso los pasajeros son los datos que necesitamos tratar, la parada de origen es la memoria global del dispositivo, y la parada final, los registros locales del hilo que ejecuta un kernel. La arquitectura CUDA, está diseñada para esperar en la parada de origen entre 400 y 600 ciclos de reloj, además hay que tener en cuenta el número de pasajeros que se permite trasportar en cada viaje.

Como podemos deducir, para optimizar el proceso, cada vez que realicemos un acceso a memoria global del dispositivo, lo haremos de tal manera que llenemos el autobús, y todos esos datos trasportados, los procesaremos en el mismo hilo.

Para nuestro algoritmo, hemos realizado una serie de pruebas partiendo de un factor de desenrollado de 2 hasta 10, 25, 50 y 100, la siguiente tabla muestra los tiempos de respuesta obtenidos en cada caso.

UF	GPU1
2	0.00010693
3	0.00008918
4	0.00008308
5	0.00007948
6	0.00008024
7	0.00007638
8	0.00007826
9	0.00008013
10	0.00007762
25	0.0000807
50	0.00008548
100	0.00011343

Tabla 3. Tiempos de respuesta para distintos valores de UF

Hemos determinado de forma empírica que el mejor factor es el de 7. Para otros algoritmos puede variar ya que todo esto depende del tipo de dato que se esté transportando, del tamaño de los registros necesarios en el kernel, etc.

Figura 4. Selección del mejor factor de Unroll

---

[1] Este término ha sido acuñado para el presente trabajo como analogía al término económico “Punto Muerto” o “Umbral de rentabilidad” donde los ingresos son iguales a los gastos 

[2] Es el término económico utilizado para referirnos al coste de la mejor opción no realizada. Este término fue inventado por Friedrich von Wieser en su Theorie der gesellschaftlichen Wirtschaft (Teoría de la economía social). El coste de la oportunidad es aquello a lo que renunciamos cuando tomamos una decisión económica.