La importancia de la programación paralela y la vectorización SIMD (I)


Arquitectura de Computadores Paralelismo Eficiencia Rendimiento Optimización Programación Paralela Vectorización SIMD GPU Modelos de Programación Desarrollo Software GPGPU Portabilidad del Rendimiento

El diseño de los computadores se ve fuertemente impulsado por innovaciones tecnológicas, científicas e industriales, siempre tratando de superarse a sí mismas, consiguiendo arquitecturas más eficientes y versátiles. Se destacan dos entre las más relevantes y con mayor impacto en todos los programas, determinando su potencial rendimiento y consumo energético.

La jerarquía de la memoria es una de las características más importantes de la ingeniería de computadores, pues trata de solventar el cuello de botella de las arquitecturas von Neumann, que se produce en toda transferencia de datos entre los procesadores y la memoria del sistema. No obstante, el paralelismo es otra característica que cada vez está teniendo más relevancia en las arquitecturas de computadores, sobre todo en la última década. Los microprocesadores modernos incorporan distintos niveles de paralelismo para mejorar su rendimiento. Esto ocurre prácticamente en todos los procesadores que conocemos, desde CPUs y GPUs, hasta dispositivos vectoriales como los many cores Intel Xeon Phi o los aceleradores TSUBASA Vector Engine.

Una vía para clasificar los distintos tipos de paralelismo es la taxonomía de Flynn, quien identifica cuatro clases de arquitecturas en relación con los flujos de instrucciones y de datos de los computadores: SISD, MISD, SIMD y MIMD.

La taxonomía de Flynn para clasificar las arquitecturas de computadores según el número de flujos de instrucciones y de datos

La taxonomía de Flynn para clasificar las arquitecturas de computadores según el número de flujos de instrucciones y de datos. PU = Unidad de procesamiento.

  • Single Instruction, Single Data (SISD): el modelo de arquitectura tradicional de von Neumman donde una sola unidad de procesamiento opera con un solo flujo de datos. El caso más simple, típicamente encontrado en máquinas mono núcleo de computadores más convencionales.
  • Single Instruction, Multiple Data (SIMD): una sola unidad de procesamiento opera simultáneamente con múltiples conjunto de datos. Este caso lo veremos en este artículo, mediante las operaciones vectoriales. Otro ejemplo serían las GPUs mediante su paralelismo a nivel de hilo (SIMT).
  • Multiple Instruction, Multiple Data (MIMD): utiliza múltiples unidades de procesamiento que ejecutan diferentes instrucciones sobre múltiples conjuntos de datos. Una particularidad de las GPUs, y es que son dispositivos que disponen de múltiples cores (cientos o miles) independientes que pueden ejecutar instrucciones diferentes sobre distintos datos (generalmente en conjuntos, wavefronts/warps), aunque cada core de GPU opera en modo SIMD sobre sus datos.
  • Multiple Instruction, Single Data (MISD): emplea múltiples unidades de procesamiento para ejecutar diferentes instrucciones sobre un solo flujo de datos. Algunos ejemplos de estas arquitecturas son los arrays sistólicos y las arquitecturas segmentadas (pipelines), aunque puede ser debatible porque los datos se transforman por cada etapa. Es el caso más complejo de encontrar en el mundo real.

Considerando las distintas características y estrategias aplicadas en los procesadores modernos, así como el impacto en la explotación de los diferentes niveles de paralelismo, se distinguen estas tres vías de aplicación:

  • El paralelismo a nivel de instrucciones (ILP). El uso de instrucciones en pipeline y ejecución superescalar facilita la explotación de ILP. El pipelining solapa la ejecución de los diferentes estados de diversas instrucciones, tales como fetch, decode, register fetch o memory access. Con el paralelismo superescalar se consigue que múltiples unidades de ejecución ejecuten instrucciones independientes simultáneamente. A menudo las instrucciones son reordenadas por el sistema, realizando ejecución fuera de orden. Ahora bien, las dependencias de datos tienen que ser consideradas para generar programas correctos (típicamente, operaciones read-after-write RAW).
  • Las unidades vectoriales. Generalmente, los procesadores actuales disponen de unidades SIMD en cada core, por lo que pueden ejecutar instrucciones vectoriales que operan simultáneamente con conjuntos de datos. Por ejemplo, una unidad vectorial de 256 bits permite realizar operaciones en paralelo con 8 pares de números flotantes de simple precisión.
  • Multiples cores (núcleos). Los microprocesadores modernos usan el paralelismo MIMD al incorporar cores o streaming multi-processors que permiten ejecutar hilos de forma asíncrona e independiente. En las máquinas modernas, es el mecanismo que más beneficios potenciales proporciona, tanto en términos de rendimiento como de consumo energético y escalabilidad. Sin embargo, es necesario que los programadores consideren este cambio en el modelo de programación, pues generalmente complica la lógica del programa debido al indeterminismo y el conjunto de flujos de ejecución simultáneos. Este tipo de programas suelen ser complejos, afectando a todas las capas del diseño software.

Asumiendo que queremos centrarnos en una mejora de la programación secuencial, descartando las modificaciones del flujo de ejecución del software, vamos a realizar una optimización basada en el uso de las unidades vectoriales. Las arquitecturas SIMD explotan el paralelismo de datos mediante la ejecución (issuing) de la misma instrucción a todas las PUs o ALUs (Arithmetic Logical Units) en cada ciclo de reloj. De esta forma, solo requieren una sola unidad de control para lanzar (dispatch) instrucciones. De esta forma, se simplifica el diseño de los PUs, ya que no requieren lógica adicional para el control del programa.

Por ejemplo, si queremos adaptar a una máquina SIMD un código que realiza una resta entre dos vectores a nivel de elemento, todas las iteraciones del bucle son independientes. De esta forma, es muy fácil aplicar un estilo SIMD.

for (i = 0; i < N; ++i)
  o[i] = a[i] - b[i];

Considerando una unidad de control que opera con un conjunto M de ALUs, se puede determinar cómo el valor o[i] puede computarse con la primera carga de valores a[i] y b[i] en los registros internos A y B, para posteriormente realizar la instrucción de resta A - B de forma paralela. Este sistema será capaz de realizar M operaciones simultáneamente (carga de datos, ejecución y guardado), determinando el valor a incrementar/iterador del bucle.

Sin embargo, no todos los algoritmos son fácilmente aplicables en modo SIMD, como ocurre con las sentencias condicionales, iteradores dinámicos o con saltos variables, llamadas a funciones (no inlined) o generalmente, ante situaciones con lógica y flujos de notable complejidad.

En un caso como el siguiente, es necesario permitir que las ALUs puedan estar idle mientras otras operan. Las sentencias condicionales están penalizando la eficiencia del sistema compuesto de unidades vectoriales, pues la divergencia necesita ser evaluada en cada caso. Es decir, unos elementos a[i] podrían valer 1 y otros no, haciendo necesario ejecutar ambas ramas y mantener estados de espera entre ellas. En términos teóricos generales, en esta ocasión se estaría consiguiendo alrededor de un 0.5 de eficiencia. Como curiosidad, este es un problema bien conocido en arquitecturas GPU y siempre hay que tratar de conseguir que el wavefront/warp ejecute todos sus threads en la misma rama divergente, con el objetivo de mejorar la eficiencia (estudios científicos sobre branch divergence).

for (i = 0; i < N; ++i)
  if (a[i] != 1)
    o[i] = a[i] + b[i];
  else
    o[i] = a[i] - b[i];

Hasta aquí hemos visto la clasificación de las arquitecturas de computadores y unos primeros indicios de la vectorización (SIMD), resaltando el impacto de los niveles de paralelismo existentes. En los siguientes artículos de esta serie veremos cómo exprimir estas arquitecturas paralelas y unidades vectoriales con casos prácticos de programación paralela y vectorial usando arquitecturas de computadores actuales.

Cada vez es más habitual que nos encontremos con dispositivos con más núcleos, mayor diversidad en las unidades especializadas de cómputo y variedad de coprocesadores. La tendencia es bien clara: más heterogeneidad y potencial para explotar el paralelismo. Por tanto, es vital que seamos conscientes de sus capacidades y ventajas, pero también de sus complejidades.

Un aspecto fundamental es que los softwares, frameworks y algoritmos implementados aseguren la portabilidad del rendimiento, siendo capaces de aprovechar las características de los computadores, independientemente al número de cores, ancho de unidades vectoriales o configuración de la jerarquía de memoria. Por este motivo, los modelos de programación y las técnicas de computación paralela y vectorial son determinantes para posibilitar que los programadores elaboren programas escalables, rápidos y energéticamente eficientes.

Este sitio web emplea cookies propias y de terceros para analizar el tráfico y ofrecerle una mejor experiencia. Al navegar o utilizar nuestros servicios el usuario está aceptando su uso.Más información.