Cómo diseñar chips de GPU
Chapter 3 Parallel Programming Models

Capítulo 3: Modelos de Programación Paralela en el Diseño de GPU

Las Unidades de Procesamiento Gráfico (GPUs) han evolucionado desde aceleradores gráficos de función fija hasta motores de computación altamente paralelos y programables, capaces de acelerar una amplia gama de aplicaciones. Para permitir que los programadores aprovechen eficazmente el masivo paralelismo en las GPUs, se han desarrollado varios modelos y API de programación paralela, como NVIDIA CUDA, OpenCL y DirectCompute. Estos modelos de programación proporcionan abstracciones que permiten a los programadores expresar el paralelismo en sus aplicaciones mientras ocultan los detalles de bajo nivel del hardware de la GPU.

En este capítulo, exploraremos los conceptos y principios clave detrás de los modelos de programación paralela para GPUs, centrándonos en el modelo de ejecución SIMT (Single Instruction, Multiple Thread), el modelo de programación CUDA y sus API, y el marco de trabajo OpenCL. También discutiremos técnicas para asignar algoritmos a las arquitecturas de GPU para lograr un alto rendimiento y eficiencia.

Modelo de Ejecución SIMT (Single Instruction, Multiple Thread)

El modelo de ejecución SIMT es el paradigma fundamental utilizado por las GPUs modernas para lograr un paralelismo masivo. En el modelo SIMT, un gran número de hilos ejecutan el mismo programa (llamado kernel) en paralelo, pero cada hilo tiene su propio contador de programa y puede tomar diferentes caminos de ejecución en función de su ID de hilo y los datos con los que opera.

Kernels y Jerarquía de Hilos

Un kernel de GPU es una función que se ejecuta en paralelo por un gran número de hilos. Al lanzar un kernel, el programador especifica el número de hilos a crear y cómo se organizan en una jerarquía de grillas, bloques (o matrices de hilos cooperativos - CTAs) e hilos individuales.

  • Una grilla representa todo el espacio del problema y consta de uno o más bloques.
  • Un bloque es un grupo de hilos que pueden cooperar y sincronizarse entre sí a través de la memoria compartida y las barreras. Los hilos dentro de un bloque se ejecutan en el mismo núcleo de GPU (llamado multiprocesador de secuencia).Aquí está la traducción al español del archivo markdown, con los comentarios del código traducidos, mientras que el código en sí no se ha traducido:

Modelo de ejecución SIMT (Single Instruction, Multiple Thread)

  • Cada hilo tiene un ID único dentro de su bloque y grilla, el cual se puede usar para calcular direcciones de memoria y tomar decisiones de flujo de control.

Esta organización jerárquica permite a los programadores expresar tanto paralelismo de datos (donde la misma operación se aplica a múltiples elementos de datos) como paralelismo de tareas (donde diferentes tareas se ejecutan en paralelo).

La Figura 3.1 ilustra la jerarquía de hilos en el modelo de ejecución SIMT.

            Grilla
       ________________
      /   /   /   /   /
     /   /   /   /   / 
    /   /   /   /   /
   /   /   /   /   /
  /__/__/__/__/__/
    |   |   |   |
    |   | Bloque |
    |   |   |   |
  Hilo Hilo ...

Figura 3.1: Jerarquía de hilos en el modelo de ejecución SIMT.

Ejecución SIMT

En el modelo de ejecución SIMT, cada hilo ejecuta la misma instrucción pero opera con diferentes datos. Sin embargo, a diferencia de SIMD (Single Instruction, Multiple Data) donde todos los elementos de procesamiento se ejecutan al unísono, SIMT permite que los hilos tengan rutas de ejecución independientes y divergir en las instrucciones de control.

Cuando un warp (un grupo de 32 hilos en las GPU de NVIDIA o 64 hilos en las GPU de AMD) encuentra una instrucción de control, el hardware de la GPU evalúa la condición de control para cada hilo en el warp. Si todos los hilos toman el mismo camino (convergencia), el warp continúa la ejecución normalmente. Sin embargo, si algunos hilos toman diferentes caminos (divergencia), el warp se divide en dos o más subwarps, cada uno siguiendo un camino diferente. El hardware de la GPU serializa la ejecución de los caminos divergentes, enmascarando los hilos inactivos en cada subwarp. Cuando todos los caminos se completan, los subwarps reconvergen y continúan la ejecución al unísono.

La Figura 3.2 ilustra la ejecución SIMT con flujo de control divergente.

         Warp
   ________________
  /   /   /   /   /
 /   /   /   /   / 
/   /   /   /   /
   |   |   |
   | Control |
   |   |   |
  / \ / \ / \
 /   X   \   \
/   / \   \   \
   /   \   \
  /     \   \
 /       \   \
/         \   \
           \
```Reconvergencia

Figura 3.2: Ejecución SIMT con flujo de control divergente.

Este mecanismo de manejo de divergencia permite que SIMT admita un flujo de control más flexible que SIMD, pero tiene el costo de una eficiencia SIMD reducida cuando ocurre la divergencia. Los programadores deben esforzarse por minimizar la divergencia dentro de un warp para lograr un rendimiento óptimo.

Jerarquía de memoria

Las GPU tienen una jerarquía de memoria compleja para admitir los requisitos de alto ancho de banda y baja latencia de las cargas de trabajo paralelas. La jerarquía de memoria suele constar de:

  • Memoria global: El espacio de memoria más grande pero más lento, accesible por todos los hilos en un kernel. La memoria global suele implementarse mediante memoria GDDR o HBM de alto ancho de banda.
  • Memoria compartida: Un espacio de memoria rápido y en chip compartido por todos los hilos de un bloque. La memoria compartida se usa para la comunicación entre hilos y el intercambio de datos dentro de un bloque.
  • Memoria constante: Un espacio de memoria de solo lectura utilizado para transmitir datos de solo lectura a todos los hilos.
  • Memoria de textura: Un espacio de memoria de solo lectura optimizado para la localidad espacial y al que se accede a través de las memorias caché de textura. La memoria de textura se usa más comúnmente en cargas de trabajo gráficas.
  • Memoria local: Un espacio de memoria privado para cada hilo, utilizado para el desbordamiento de registros y las estructuras de datos grandes. La memoria local generalmente se asigna a la memoria global.

La utilización eficaz de la jerarquía de memoria es crucial para lograr un alto rendimiento en las GPU. Los programadores deben buscar maximizar el uso de la memoria compartida y minimizar los accesos a la memoria global para reducir los cuellos de botella de latencia y ancho de banda de memoria.

La Figura 3.3 ilustra la jerarquía de memoria de la GPU.

     |   Memoria   |
     |   Compartida   |
      ____________
           |
      ____________ 
     |            |
     |   Memoria   |
     |   Local    |
      ____________

Figura 3.3: Jerarquía de memoria de GPU.

Modelo de programación y APIs de CUDA

CUDA (Compute Unified Device Architecture) es una plataforma de computación paralela y un modelo de programación desarrollado por NVIDIA para computación de propósito general en GPUs. CUDA proporciona un conjunto de extensiones a los lenguajes de programación estándar, como C, C++ y Fortran, que permiten a los programadores expresar el paralelismo y aprovechar el poder computacional de las GPUs de NVIDIA.

Modelo de programación de CUDA

El modelo de programación de CUDA se basa en el concepto de kernels, que son funciones ejecutadas en paralelo por una gran cantidad de hilos (threads) en la GPU. El programador especifica el número de hilos a iniciar y su organización en una cuadrícula (grid) de bloques de hilos.

CUDA introduce varias abstracciones clave para facilitar la programación paralela:

  • Hilo (Thread): La unidad básica de ejecución en CUDA. Cada hilo tiene su propio contador de programa, registros y memoria local.
  • Bloque (Block): Un grupo de hilos que pueden cooperar y sincronizarse entre sí. Los hilos dentro de un bloque se ejecutan en el mismo multiprocesador de flujo (streaming multiprocessor) y pueden comunicarse a través de la memoria compartida.
  • Cuadrícula (Grid): Una colección de bloques de hilos que ejecutan el mismo kernel. La cuadrícula representa todo el espacio del problema y puede ser unidimensional, bidimensional o tridimensional.

CUDA también proporciona variables integradas (por ejemplo, threadIdx, blockIdx, blockDim, gridDim) que permiten a los hilos identificarse a sí mismos y calcular direcciones de memoria en función de su posición en la jerarquía de hilos.

La Figura 3.4 ilustra el modelo de programación de CUDA.

            Cuadrícula
       ________________
      /   /   /   /   /
     /   /   /   /   / 
    /   /   /   /   /
   /   /   /   /   /
  /__/__/__/__/__/
    |   |   |   |
    |   | Bloque |
    |   |   |   |
  Hilo Hilo ...

Figura 3.4: Modelo de programación de CUDA.

Jerarquía de memoria de CUDAArchivo archy

CUDA expone la jerarquía de memoria GPU al programador, permitiéndole un control explícito sobre la ubicación y el movimiento de los datos. Los principales espacios de memoria en CUDA son:

  • Memoria global: Accesible por todos los hilos en un kernel y persiste a través del lanzamiento de kernels. La memoria global tiene la latencia más alta y se usa típicamente para estructuras de datos grandes.
  • Memoria compartida: Una memoria rápida y on-chip compartida por todos los hilos de un bloque. La memoria compartida se usa para la comunicación entre hilos y el intercambio de datos dentro de un bloque.
  • Memoria constante: Un espacio de memoria de solo lectura utilizado para difundir datos de solo lectura a todos los hilos. La memoria constante se almacena en caché y proporciona un acceso de baja latencia.
  • Memoria de texturas: Un espacio de memoria de solo lectura optimizado para la localidad espacial y al que se accede a través de las cachés de texturas. La memoria de texturas se usa más comúnmente en cargas de trabajo gráficas.
  • Memoria local: Un espacio de memoria privado para cada hilo, utilizado para el derrame de registros y estructuras de datos grandes. La memoria local suele asignarse a la memoria global.

Los programadores pueden asignar y transferir datos entre la memoria del host (CPU) y del dispositivo (GPU) utilizando las API de tiempo de ejecución de CUDA, como cudaMalloc, cudaMemcpy y cudaFree.

La Figura 3.5 ilustra la jerarquía de memoria de CUDA.

      ____________
     |            |
     |   Global   |
     |   Memory   |
      ____________
           |
      ____________
     |            |
     |  Constant  |
     |   Memory   |
      ____________
           |
      ____________
     |            |
     |  Texture   |
     |   Memory   |
      ____________
           |
           |
      ____________
     |            |
     |   Shared   |
     |   Memory   |
      ____________
           |
      ____________ 
     |            |
     |   Local    |
     |   Memory   |
      ____________

Figura 3.5: Jerarquía de memoria CUDA.

Sincronización y coordinación de CUDA

CUDA proporciona primitivas de sincronización y coordinación para permitir la cooperación y la comunicación entre hilos:

  • Sincronización de barrera: __syncthreadAquí está la traducción al español de este archivo Markdown, con los comentarios del código traducidos:

La función s() actúa como una barrera que asegura que todos los hilos en un bloque hayan alcanzado el mismo punto antes de proceder.

  • Operaciones atómicas: CUDA admite operaciones atómicas (p. ej., atomicAdd, atomicExch) que permiten a los hilos realizar operaciones de lectura-modificación-escritura en la memoria compartida o global sin interferencia de otros hilos.
  • Primitivas a nivel de warps: CUDA proporciona intrínsecas a nivel de warps (p. ej., __shfl, __ballot) que permiten una comunicación y sincronización eficientes dentro de un warp.

El uso adecuado de primitivas de sincronización y coordinación es esencial para escribir programas paralelos correctos y eficientes en CUDA.

El Ejemplo 3.1 muestra un kernel CUDA simple que realiza la adición de vectores.

__global__ void vectorAdd(int *a, int *b, int *c, int n) {
    int i = blockIdx.x * blockDim.x + threadIdx.x;
    if (i < n) {
        c[i] = a[i] + b[i];
    }
}
 
int main() {
    int *a, *b, *c;
    int n = 1024;
    
    // Asignar memoria en el host
    a = (int*)malloc(n * sizeof(int));
    b = (int*)malloc(n * sizeof(int));
    c = (int*)malloc(n * sizeof(int));
    
    // Inicializar los vectores de entrada
    for (int i = 0; i < n; i++) {
        a[i] = i;
        b[i] = i * 2;
    }
    
    // Asignar memoria en el dispositivo
    int *d_a, *d_b, *d_c;
    cudaMalloc(&d_a, n * sizeof(int));
    cudaMalloc(&d_b, n * sizeof(int));
    cudaMalloc(&d_c, n * sizeof(int));
    
    // Copiar los vectores de entrada del host al dispositivo
    cudaMemcpy(d_a, a, n * sizeof(int), cudaMemcpyHostToDevice);
    cudaMemcpy(d_b, b, n * sizeof(int), cudaMemcpyHostToDevice);
    
    // Lanzar el kernel
    int blockSize = 256;
    int numBlocks = (n + blockSize - 1) / blockSize;
    vectorAdd<<<numBlocks,blockSize>>>(d_a, d_b, d_c, n);
    
    // Copiar el vector de resultado del dispositivo al host
    cudaMemcpy(c, d_c, n * sizeof(int), cudaMemcpyDeviceToHost);
    
    // Liberar la memoria del dispositivo
    cudaFree(d_a);
    cudaFree(d_b); 
    cudaFree(d_c);
    
    // Liberar la memoria del host
    free(a); 
    free(b);
    free(c);
    
    returAquí está la traducción al español de este archivo Markdown. Para el código, no se traduce el código, solo los comentarios.
 
n 0;
}

Este código CUDA lanza el kernel vectorAdd con numBlocks bloques y blockSize hilos por bloque. El kernel realiza la adición elemento a elemento de los vectores de entrada a y b y almacena el resultado en el vector c. La sintaxis <<<...>>> se utiliza para especificar las dimensiones de la rejilla y del bloque al lanzar un kernel.

Flujos y eventos CUDA

Los flujos y eventos CUDA proporcionan un mecanismo para la ejecución concurrente y la sincronización de kernels y operaciones de memoria:

  • Flujos: Una secuencia de operaciones (lanzamiento de kernels, copias de memoria) que se ejecutan en orden. Los diferentes flujos pueden ejecutarse concurrentemente, lo que permite la superposición de cálculos y transferencias de memoria.
  • Eventos: Marcadores que se pueden insertar en un flujo para registrar la finalización de operaciones específicas. Los eventos se pueden utilizar para fines de sincronización y cronometraje.

Los flujos y los eventos permiten a los programadores optimizar el rendimiento de sus aplicaciones CUDA al superponer cálculos y transferencias de memoria y aprovechar al máximo las capacidades del hardware GPU.

El Ejemplo 3.2 demuestra el uso de los flujos CUDA para superponer la ejecución de kernels y las transferencias de memoria.

// Crear dos flujos
cudaStream_t stream1, stream2;
cudaStreamCreate(&stream1);
cudaStreamCreate(&stream2);
 
// Copiar los datos de entrada al dispositivo de forma asincrónica
cudaMemcpyAsync(d_a, a, size, cudaMemcpyHostToDevice, stream1);
cudaMemcpyAsync(d_b, b, size, cudaMemcpyHostToDevice, stream2);
 
// Lanzar kernels en flujos diferentes
kernelA<<<blocks, threads, 0, stream1>>>(d_a);
kernelB<<<blocks, threads, 0, stream2>>>(d_b);
 
// Copiar los resultados de vuelta al host de forma asincrónica
cudaMemcpyAsync(a, d_a, size, cudaMemcpyDeviceToHost, stream1);
cudaMemcpyAsync(b, d_b, size, cudaMemcpyDeviceToHost, stream2);
 
// Sincronizar los flujos
cudaStreamSynchronize(stream1);
cudaStreamSynchronize(stream2);

En este ejemplo, se crean dos flujos CUDA. Los datos de entrada se copian al dispositivo de forma asincrónica utilizando cada flujo. Luego, los kernels se lanzan en los diferentes flujos, lo que permite la superposición de cálculos y transferencias de memoria.Aquí está la traducción al español del archivo Markdown, con los comentarios traducidos pero sin traducir el código:

Marco de Trabajo OpenCL

OpenCL (Open Computing Language) es un estándar abierto y libre de regalías para la programación paralela a través de plataformas heterogéneas, incluyendo CPUs, GPUs, FPGAs y otros aceleradores. OpenCL proporciona un modelo de programación unificado y un conjunto de APIs que permiten a los desarrolladores escribir código paralelo portable y eficiente.

Modelo de Programación OpenCL

El modelo de programación OpenCL es similar a CUDA, con algunas diferencias clave en la terminología y las abstracciones:

  • Kernel: Una función ejecutada en paralelo por un gran número de work-items (hilos) en un dispositivo OpenCL.
  • Work-item: La unidad básica de ejecución en OpenCL, análoga a un hilo en CUDA.
  • Work-group: Una colección de work-items que pueden sincronizarse y compartir datos a través de la memoria local. Los work-groups son análogos a los bloques de hilos en CUDA.
  • NDRange: Define el espacio de índice y la organización de work-items para la ejecución de un kernel. Puede ser de una, dos o tres dimensiones.

OpenCL también define un modelo de memoria jerárquico similar a CUDA:

  • Memoria global: Accesible por todos los work-items en todos los work-groups, análoga a la memoria global en CUDA.
  • Memoria local: Compartida por todos los work-items en un work-group, análoga a la memoria compartida en CUDA.
  • Memoria privada: Privada para un solo work-item, análoga a los registros en CUDA.
  • Memoria constante: Memoria de sólo lectura accesible por todos los work-items.

Los kernels de OpenCL se compilan en tiempo de ejecución por el tiempo de ejecución de OpenCL. El programa host puede consultar los dispositivos OpenCL disponibles, seleccionar un dispositivo apropiado, crear un contexto y compilar el kernel para ese dispositivo específico. Esto permite que las aplicaciones OpenCL sean altamente portables a través de diferentes plataformas de hardware.

El Ejemplo 3.3 muestra un kernel OpenCL que realiza una adición de vectores, similar al ejemplo CUDA en el Ejemplo 3.1.

__kernel void vectorAdd(__global const int *a, __global const int *b, __global int *c, int n) {
    // Obtener el índice global del work-item actual
    int i = get_global_id(0);
 
    // Comprobar que el índice esté dentro de los límites del vector
    if (i < n) {
        // Realizar la operación de adición de vectores
        c[i] = a[i] + b[i];
    }
}
```Aquí está la traducción al español del archivo de Markdown, con los comentarios traducidos, pero sin traducir el código:
 
```c
__kernel void vector_add(const int *a, __global int *b, __global int *c, int n) {
    int i = get_global_id(0);
    if (i < n) {
        c[i] = a[i] + b[i];
    }
}

La palabra clave __kernel define una función de kernel de OpenCL. La palabra clave __global especifica que un puntero apunta a la memoria global. La función get_global_id devuelve el índice global del trabajo actual, que se usa para calcular las direcciones de memoria de los vectores de entrada y salida.

Mapear algoritmos a las arquitecturas GPU

Mapear eficientemente los algoritmos a la arquitectura GPU es crucial para lograr un alto rendimiento. Las consideraciones clave incluyen:

  • Exponer suficiente paralelismo: El algoritmo debe descomponerse en muchos subprocesos de grano fino que puedan ejecutarse en paralelo para aprovechar al máximo las capacidades de procesamiento paralelo de la GPU.

  • Minimizar la divergencia de ramas: El flujo de control divergente dentro de un warp/wavefront puede llevar a la serialización y reducir la eficiencia de SIMD. Los algoritmos deben estructurarse para minimizar la divergencia de ramas cuando sea posible.

  • Aprovechar la jerarquía de memoria: Acceder a la memoria global es costoso. Los algoritmos deben maximizar el uso de la memoria compartida y los registros para reducir los accesos a la memoria global. Los datos también deben organizarse en la memoria para permitir accesos a la memoria coalescidos.

  • Equilibrar los cálculos y los accesos a la memoria: Los algoritmos deben tener una alta relación de operaciones aritméticas a operaciones de memoria para ocultar eficazmente la latencia de la memoria y lograr un alto rendimiento computacional.

  • Minimizar las transferencias de datos entre host y dispositivo: Transferir datos entre la memoria del host y del dispositivo es lento. Los algoritmos deben minimizar estas transferencias realizando la mayor cantidad de cálculos posible en la GPU.

Varios patrones de diseño de algoritmos paralelos se utilizan comúnmente al desarrollar kernels de GPU:

  • Map: Cada subproceso realiza la misma operación en un elemento de datos diferente, lo que permite un procesamiento paralelo simple de conjuntos de datos grandes.

  • Reduce: La reducción paralela se usa para calcular eficientemente un solo valor (por ejemplo, suma, máximo) a partir de un gran conjunto de datos de entrada.Aquí está la traducción al español de este archivo Markdown. Para el código, no he traducido el código, sino solo los comentarios.

Los hilos realizan reducciones locales, que luego se combinan para producir el resultado final.

  • Escanear: También conocido como suma prefija, el escaneo se usa para calcular la suma acumulada de elementos en una matriz. Los algoritmos de escaneo paralelo eficientes son bloques de construcción clave para muchas aplicaciones aceleradas por GPU.

  • Plantilla: Cada hilo calcula un valor en función de los elementos de datos vecinos. Los cálculos de plantillas son comunes en las simulaciones científicas y las aplicaciones de procesamiento de imágenes.

  • Reunir/Dispersar: Los hilos leen (reunir) o escriben (dispersar) en ubicaciones arbitrarias en la memoria global. Se requiere un diseño y patrones de acceso de datos cuidadosos para lograr eficiencia.

Conclusión

Los modelos de programación GPU como CUDA y OpenCL exponen las capacidades de procesamiento paralelo de las GPU modernas a los desarrolladores, lo que les permite acelerar una amplia gama de aplicaciones. Estos modelos de programación proporcionan abstracciones que permiten que las cargas de trabajo paralelas de grano fino se asignen de manera eficiente al hardware de la GPU.

Entender el modelo de ejecución, la jerarquía de memoria y los primitivos de sincronización proporcionados por estos modelos de programación es esencial para escribir código GPU de alto rendimiento. Los desarrolladores deben considerar cuidadosamente factores como la organización de hilos, la divergencia de ramas, los patrones de acceso a la memoria y el diseño de algoritmos para aprovechar al máximo el poder de cálculo de las GPU.

A medida que las arquitecturas GPU continúan evolucionando, los modelos y herramientas de programación también deben avanzar para permitir que los desarrolladores utilicen de manera efectiva las nuevas características y capacidades del hardware. La investigación continua en áreas como el diseño de lenguajes de programación, la optimización de compiladores y el autoajuste serán cruciales para mejorar la productividad de los programadores y la portabilidad del rendimiento en la era de la computación heterogénea.