Un ejemplo básico, parte I: la llamada al kernel

Vamos a diseñar un algoritmo que permita realizar llamadas a nuestro kernel de tal forma que conociendo N número de elementos a procesar o tamaño del bucle en versión serie, utilice los mínimos recursos (de procesador gráfico) minimizando también las transferencias de memoria. Nos centraremos en un típico caso que en el que se emplea la programación paralela: Reducción de vectores. En la literatura hay multitud de ejemplos y diversos enfoques, nVidia también realiza varias implementaciones hasta 7 diferentes, van ilustrando los diferentes factores para mejorar el rendimiento. Yo implementé mi propio método, que ha resultado ser más rápido que las implementaciones de nVidia y de la librería Trust en varios escenarios. En el presente post y el siguiente lo presento:

Algoritmo para la llamada al kernel

Primero necesitamos obtener las características del dispositivo donde se van a ejecutar los programas, eso lo podemos obtener en tiempo de ejecución interrogando las capacidades de cada dispositivo. Las tres variables cuyo valor necesitamos saber son: N  número de elementos a procesar, UF factor de desenrollado (Unroll factor), que determinará la velocidad de segmentación de los datos y el número de instrucciones serie que ejecuta el kernel en cada hilo, y datos que es el puntero al bloque de datos a procesar.

Una vez determinados los valores de estas variables podremos calcular el factor de ocupación. El consumo máximo de tiempo se emplea en la migración de los datos desde memoria principal a la memoria del dispositivo, por lo que realizaremos sólo un proceso de carga y otro de descarga. El tamaño de bloques necesarios para la ejecución se irá reduciendo de forma logarítmica en cada iteración, ya que este algoritmo está orientado a las operaciones de reducción de vectores.

Para acumular los valores obtenidos se sobrescribe el vector de entrada con los resultados que se van obteniendo en cada cálculo, evitando así crear dos estructuras de datos, una de entrada y otra de salida. Además para cada llamada se aprovecha la información residente en la memoria del dispositivo, reduciendo la cantidad de datos transferida entre la memoria central y la del dispositivo.

Algoritmo 2: Algoritmo de llamada a un kernel
1	Obtener_caracteristicasGPU (max_bloques, max_hilos)
2	Determinar_factor_ocupacion(N,max_bloques, max_hilos, registros_kernel, nhilos)
3	UF ← 7
4	auxN  ← N
5	huerfanos  ←  (auxN modulo UF)
6	Datos_a_dispositivo(datos_dispositivo, datos)
7	Para i ← 1 hasta (log(N) / Log(UF))
8		Ejecutar en paralelo Reduce<<<(auxN+nhilos-1)/nhilos,nhilos> >>(datos_dispositivo, auxN, huerfanos, UF)
9		auxN ← auxN / UF
10		huerfanos  ←  (auxN modulo UF)
11	Datos_a_memoria_principal(datos, datos_dispositivo)

Algoritmo 1.Llamada al Kernel

Pasaremos a comentar cada una de las líneas de l algoritmo:

1.- Obtener_caracteristicas GPU (max_bloques, max_hilos): Indica los límites de la arquitectura seleccionada, que se utilizarán para aplicar las reglas que obtendrán el mejor factor de ocupación. Adicionalmente se obtienen otras cualidades de los dispositivos como la capacidad computacional (Compute capability) que indicará cuales son los dispositivos que permiten aprovechar las nuevas capacidades de CUDA 4, caracterizados por tener una capacidad igual o superior a 2.0.

2.- Si se puede estimar el tamaño N de nuestro proceso, y esto se puede traducir en el número de hilos necesarios para invocar al kernel, se podrá determinar el mejor factor de ocupación. Este cálculo óptimo de la relación hilos/bloques se puede realizar fácilmente porque al compilar el kernel se puede conocer el tamaño de de los registros necesarios para cada hilo,   y consecuentemente, se puede determinar el número máximo de hilos por bloque y de bloques por procesador.

3.- En la línea 3 hay que proporcionar un valor de Unroll Factor (UF). Para ello se deberán de realizar varias pruebas para obtener el mejor valor para este parámetro, ya que dependerá mucho de la estructura de datos en memoria que estemos utilizando, el tipo de memoria que utilicemos para su gestión y la coalescencia de los accesos que realicemos. En nuestras pruebas hemos utilizado la memoria global del dispositivo, y los accesos no han sido alineados con la ejecución de los kernels, Como veremos más adelante para nuestro algoritmo el mejor valor ha sido 7.

4.- En la línea 4 utilizamos una variable para guardar el tamaño de procesamiento remanente. El valor de esta variable se va reduciendo logarítmicamente conforme avanza el proceso.

5.- La variable "huérfanos" se utiliza para determinar cuándo se produce un elemento huérfano, el deberá de tratarse de forma especial.

6.- La línea 6 copia los datos desde memoria principal a la memoria global del dispositivo para ser procesados por el kernel.

7.- El bucle realiza una serie de llamadas al kernel en las que se ajustan los bloques que demandamos al dispositivo en función del remanente de ejecuciones. El número de iteraciones se corresponde con el cociente entre el logaritmo  de N y el logaritmo de UF-.

11.- Una vez concluidas las ejecuciones se descargará el dato deseado a memoria principal para obtener el resultado final.  La utilización del las llamadas descendentes, la vamos a entender a continuación en cuanto se exponga el Kernel.

Os dejo analizando el algoritmo, en el próximo post, veremos la implementación del Kernel. Hasta pronto