Por qué todos los desarrolladores deberían conocer SIMD

 (mitchellh.com)
1 puntos por GN⁺ 2 시간 전 | 1 comentarios | Compartir por WhatsApp
  • SIMD no es una técnica compleja reservada solo para software de máximo rendimiento, sino una optimización cotidiana que acelera bucles comunes procesando datos contiguos de a varios valores
  • El código SIMD típico sigue una estructura de 5 pasos: broadcast de constantes, recorrido por unidades de vector, operaciones en paralelo, reducción o almacenamiento del resultado, y manejo de la cola escalar
  • El bucle de búsqueda de puntos de código de Ghostty compara 4, 8 o 16 u32 a la vez, y en teoría puede aumentar el throughput hasta 4 veces en ARM NEON, 8 veces en AVX2 y 16 veces en AVX-512
  • En una desktop Intel con AVX2, el throughput total de la terminal se volvió aproximadamente 5 veces más rápido; si no hay un ancho de vector compatible o queda entrada sobrante, el bucle escalar existente procesa toda la entrada o el remanente
  • La vectorización automática del compilador puede perder oportunidades incluso en bucles simples, así que conviene revisar primero la salida optimizada; para hot loops importantes, SIMD explícito permite mantener predecibles el comportamiento y el rendimiento

Qué hace SIMD

  • SIMD permite que la CPU procese varios valores en paralelo con una sola instrucción
    • En lugar de comparar bytes de uno en uno, se pueden comparar 4, 8 o más de una sola vez
    • Hay oportunidades para convertir bucles como for (byte in bytes), for (character in string), for (value in array) en procesamiento por ancho de vector
  • Si los datos tienen cientos, miles o millones de bytes, se puede obtener una aceleración local de 4 veces, 8 veces o más, según el ancho de paralelismo
  • Si solo hay unos pocos datos o unas decenas, no vale la pena aplicar SIMD
  • simdutf y simdjson usan técnicas SIMD complejas, pero el SIMD cotidiano no necesita ser tan complejo
  • El ejemplo usa Zig, pero la estructura de 5 pasos se aplica también a otros lenguajes, aunque cada lenguaje ofrece soporte para instrucciones SIMD de manera distinta

La estructura repetida de 5 pasos

  1. Hacer broadcast de las constantes necesarias a todos los lanes e inicializar acumuladores vectoriales si hace falta
  2. Recorrer la entrada de a tamaño de ancho de vector
  3. Ejecutar comparaciones u operaciones aritméticas en paralelo en todos los lanes
  4. Reducir o almacenar los resultados vectoriales según el algoritmo
  5. Procesar el remanente que no entra en un vector completo con el bucle existente, la cola escalar (scalar tail)
  • Una vez familiarizado con esta estructura, se puede descomponer un bucle común en los mismos 5 pasos, por lo que escribir SIMD se vuelve tan simple como escribir un bucle escalar
  • Si no se puede expresar de forma simple con esta estructura, probablemente convenga omitir SIMD por ahora

El bucle de búsqueda real de Ghostty

  • Ghostty consume datos de un arreglo de puntos de código decodificados hasta encontrar un valor igual o menor que 0xF
    • La mayor parte de los datos de una terminal son caracteres normales para mostrar, así que los procesa en grupos
    • El bucle encuentra lo más rápido posible el final del siguiente tramo imprimible
  • La implementación escalar original revisa los puntos de código uno por uno
while (end < cps.len and cps[end] > 0xF) end += 1;
  • La implementación vectorial usa vectores generales sin funciones intrínsecas específicas de CPU, y suma 12 líneas de código frente a la implementación escalar
  • La mejora esperada de throughput corresponde a la cantidad de lanes del vector
    • ARM NEON y Apple Silicon: hasta 4 veces
    • AVX2, compatible con la mayoría de las CPU x86 modernas: hasta 8 veces
    • AVX-512, compatible con algunas CPU Intel y AMD Zen 4 o superior: hasta 16 veces
  • En una desktop Intel con AVX2, el throughput total medido desde la entrada del programa de terminal hasta el estado final de la terminal se volvió aproximadamente 5 veces más rápido
    • No se obtiene toda la aceleración teórica por el trabajo alrededor de SIMD
  • Los caracteres de control C0 también existen después de 0xF, pero 0xF es el umbral usado en esta ruta de código de Ghostty
    • ESC y otras secuencias de control se procesan en rutas separadas

Paso 1: broadcast de constantes

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
  • simd.lanes(u32) de Ghostty devuelve la cantidad de u32 que la CPU objetivo puede procesar simultáneamente
    • Cada valor se llama lane
    • ARM devuelve 4, AVX2 devuelve 8 y AVX-512 devuelve 16
    • Si no hay un tamaño de vector utilizable, devuelve null y se omite el código SIMD
  • @Vector(lanes, u32) crea un tipo vectorial con esa cantidad de lanes
    • Si lanes es 8, un V contiene 8 valores u32 que se pueden procesar en paralelo
  • Como una comparación vectorial requiere vectores de ambos lados, @splat(0xF) replica 0xF en todos los lanes
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
  • Este algoritmo no necesita acumulador vectorial, pero otros algoritmos pueden inicializar uno en este paso

Paso 2: recorrer un vector a la vez

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;
  • Si lanes es 8, el bucle entra solo cuando quedan al menos 8 valores, y carga 8 valores en values
  • Al final de cada iteración, end aumenta no en 1, sino por la cantidad de lanes
  • Como se debe poder cargar un vector completo, si solo quedan 5 valores no se lee un vector de 8 lanes
  • Los valores que no entran en el vector los procesa la cola escalar del paso 5

Paso 3: comparación paralela de todos los lanes

const greater_than_threshold = values > threshold;
  • Como values y threshold son vectores, > compara cada lane correspondiente como una sola operación vectorial
  • Con 8 lanes, realiza en paralelo 8 comparaciones equivalentes a cps[end] > 0xF
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
  • No hay un bucle interno explícito, y el resultado es un vector con booleanos por lane
  • La misma estructura se puede aplicar no solo a comparaciones, sino también a operaciones soportadas por tipos vectoriales, como suma, multiplicación, mínimo y máximo
  • La comparación en sí es una sola operación vectorial, pero la carga del vector, la reducción del resultado y la búsqueda del lane fallido requieren instrucciones adicionales

Paso 4: reducción del resultado vectorial

if (@reduce(.And, greater_than_threshold)) continue;
  • @reduce(.And, ...) combina todos los booleanos con and para producir un solo booleano
  • Si todos los lanes son true, pasa al siguiente vector; si alguno es false, busca la ubicación exacta que falló
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
  • @bitCast convierte el vector de booleanos en una máscara entera de 1 bit por lane
    • 1 significa que el valor es mayor que 0xF
    • 0 significa que la comparación falló
  • Al invertir la máscara, las comparaciones fallidas quedan como 1, y @ctz cuenta la cantidad de bits 0 antes del primer 1
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }
  • En este ejemplo, @ctz(~mask) devuelve 3, y mueve end al lane 3 donde está el primer carácter de control, 0x0A
  • La reducción de resultados es la parte que más cambia entre algoritmos dentro de los 5 pasos
    • Una suma puede reducir un acumulador vectorial a un solo número
    • Una transformación puede almacenar todo el vector en el búfer de salida
    • Esta búsqueda crea una máscara de bits para encontrar la posición de un lane específico

Paso 5: procesar la cola escalar

while (end < cps.len and cps[end] > 0xF) end += 1;
  • Si la longitud de la entrada no es un múltiplo exacto del ancho de vector, el bucle escalar original procesa el resto
  • Después de un bucle vectorial de 8 lanes, pueden quedar entre 0 y 7 valores
  • En una CPU donde simd.lanes(u32) es null, se omite la sección SIMD y el bucle escalar procesa toda la entrada
  • La implementación original cumple al mismo tiempo el rol de manejo del remanente y fallback de compatibilidad
  • Los vectores generales eliminan la sintaxis específica de CPU, pero no eliminan la generación de código específica de CPU
    • Zig convierte las operaciones vectoriales al conjunto de instrucciones habilitado para el objetivo

Lo que se le escapa a la vectorización automática

  • El compilador puede vectorizar automáticamente código simple, como bucles aritméticos regulares sin flujo de control complejo
  • Antes de escribir SIMD manual, hay que compilar la versión escalar con opciones de optimización y revisar el código generado
  • Los compiladores de producción suelen perder oportunidades de vectorización, y aunque la vectorización automática se investiga desde hace décadas, investigaciones recientes también parten de este problema
  • Si un bucle es lo bastante importante como para que una aceleración de 5 veces importe, escribir la vectorización de forma explícita permite mantener predecible su comportamiento
    • Se puede evitar que cambios de código no relacionados o actualizaciones del compilador conviertan silenciosamente un bucle vectorial de vuelta en uno escalar

El alcance de SIMD que deberían aprender los desarrolladores

  • Al detectar hot loops que buscan, comparan, cuentan o transforman grandes volúmenes de datos contiguos, conviene poder considerar el procesamiento por ancho de vector
  • El SIMD cotidiano sigue una forma regular: preparar constantes, cargar vectores, operar en paralelo, reducir resultados y manejar la cola escalar
  • Si el lenguaje soporta bien SIMD, se puede mejorar el rendimiento sin conocer directamente assembly ni detalles específicos de cada CPU
  • El nivel necesario para todos los desarrolladores no son las técnicas complejas al estilo simdutf o simdjson, sino poder reconocer oportunidades de aplicar SIMD y aprovechar su estructura común

Lecturas relacionadas

1 comentarios

 
GN⁺ 2 시간 전
Opiniones de Hacker News

  • Es un buen artículo, pero no resulta muy convincente empezar diciendo que SIMD es fácil de entender y tan fácil de escribir como un bucle for y luego, desde el primer ejemplo, convertir una línea de código escalar en 12 líneas.
    Sería mejor decir con honestidad que SIMD es difícil, pero que los resultados valen la pena. Si está dirigido a principiantes, no debería usar desde el paso 1 términos propios de SIMD como broadcast sin explicarlos, y el paso 5, que explica el manejo de la cola escalar, está bien planteado.

    • SIMD y el primer ejemplo no son tanto difíciles como mucho más engorrosos.
      Hay que determinar cuántos elementos puede procesar el hardware a la vez, agrupar el trabajo en ese tamaño, desempaquetar de nuevo los resultados, manejar aparte los elementos restantes y también convertir las constantes en vectores replicados. Nada de eso es difícil por sí solo, pero aumenta la cantidad de trabajo y lo vuelve engorroso.
    • Aprendí Parallel-C, creado alrededor de 1990 en plena fiebre por Transputer; era un lenguaje que agregaba capacidades de programación paralela a C.
      Mi función favorita era par(; ; ), que permitía al compilador paralelizar automáticamente bucles for bajo ciertas condiciones de borde.
    • Yo estoy bastante cerca del público objetivo y lo leí con interés, pero la dificultad sube demasiado rápido y se siente parecido al infame meme de dibujar el búho.
    • SIMD en sí es simple; lo incómodo es usar operaciones paralelas sobre datos en un lenguaje escalar.
    • Uno de los mayores errores en la educación técnica es declarar que un tema es simple para quitarle el miedo. No hay que decir que es simple: hay que demostrarlo.
      Si el tema realmente es complejo, hay que dividirlo en partes más pequeñas y simples, ordenar bien el recorrido para que se pueda subir una curva de aprendizaje empinada y convencer de que vale la pena.

  • Un mejor consejo sería que todos deberían conocer la programación con arreglos. La optimización con SIMD suele requerir esa forma de pensar, y las técnicas específicas solo para SIMD empaquetado son sorprendentemente raras.
    La programación con arreglos facilita la vectorización automática por parte del compilador, por lo que en general produce código con buen rendimiento sin tener que escribir SIMD directamente.

    • La programación con arreglos que primero realiza todas las comparaciones y después busca el primer fallo no ayuda mucho cuando los tramos de ejecución son cortos. Al no ofrecer salida anticipada por sí misma, puede gastar mucho tiempo en comparaciones innecesarias.
    • No me gustan los lenguajes de código cerrado y MATLAB también tiene muchos defectos, pero en la universidad era muy natural escribir de forma eficiente código vectorizado para simulaciones numéricas.
      No tengo demasiada experiencia, pero Julia parece ser lo más cercano a un lenguaje más moderno y expresivo con capacidades de vectorización similares.

  • En los últimos días optimicé con AVX-512 operaciones matriciales de un proyecto de bioinformática y quedé muy satisfecho.
    En la mayoría de las aplicaciones, el cuello de botella está en leer grandes conjuntos de datos desde memoria; por eso, en vez de leerlos repetidamente para varias operaciones, se puede procesar todo de una vez con registros AVX y kernels fusionados. Es común ver mejoras de velocidad de 5 veces, y aunque usé intrínsecos directamente, con el crate wide las operaciones comunes se vuelven muy simples: https://docs.rs/wide/latest/wide/

  • La abrumadora mayoría de los desarrolladores no necesita aprender SIMD en absoluto. Me pregunto por qué se induce la idea de que todos los desarrolladores tienen que conocerlo para ser desarrolladores de verdad.

    • Al menos vale la pena conocer la existencia de SIMD y lo que permite. Si eres desarrollador, probablemente hayas escrito algún bucle crítico que suma o compara valores simples, y saber que el compilador puede optimizarlo para la arquitectura de CPU objetivo es útil en muchas situaciones.

  • Sería mejor cambiar el título a “todos deberían saber cuándo no se está aplicando SIMD”.
    Los compiladores modernos vectorizan muy bien, pero de pronto retroceden a código escalar por una sola suposición o una rama con dependencia de datos. Puede ser más valioso aprender a revisar los informes de optimización del compilador que aprender a escribir SIMD.

    • La solución a una mala vectorización automática es escribir código SIMD directamente, así que dudo que saber leer informes de optimización sea realmente más valioso que eso.
      Si solo puedes identificar el problema, al final todo termina en un “qué lástima”.
    • De hecho, justo eso ocurrió: https://xcancel.com/mitchellh/status/2079672171321081908#m

  • El año pasado empecé a aprender SIMD en x86 y ARM mientras construía un sintetizador de audio: https://github.com/seclorum/SIMDSynth
    La arquitectura de un sintetizador multitimbral y polifónico, que aplica el mismo procesamiento a varios flujos de datos, resultó muy adecuada para aprender los principios de SIMD. Sin embargo, depurar fue bastante difícil; sentí una gran necesidad de un simulador que permitiera entender el estado de cada canal de procesamiento, y parece que investigar herramientas para SIMD requeriría otra gran inversión.

  • El artículo es bueno y ojalá más lenguajes soportaran SIMD, pero cuando los dos lenguajes más populares no lo soportan de forma nativa, suena un poco raro decir que “todo programador debería saberlo”.

    • Es difícil asumir que los lenguajes más populares sean necesariamente los más usados por los ingenieros de software a los que apuntan artículos como este.

  • Aunque no vayas a escribir SIMD directamente o planees dejárselo a la IA, deberías saber qué tareas pueden acelerarse con SIMD en qué hardware. Así puedes diseñar los algoritmos y la estructura del código para que SIMD sea aplicable.
    El impacto de las dependencias de datos, el costo de aumentar el ancho de los elementos vectoriales y cómo evitarlo, cómo convertir condiciones y ramas en máscaras, o características como “no hay instrucción de división” se interiorizan mucho más fácilmente cuando has usado SIMD aunque sea un poco.

    • No se trata lo suficiente cuándo SIMD acelera las cosas.
      Funciona bien cuando se inspeccionan o transforman grandes bloques de datos contiguos de una sola vez, pero si hay que tomar una decisión cada pocos bytes de entrada, puede ser igual o más lento que el enfoque escalar. SIMD no es un botón mágico de aceleración.

  • Este es un video útil en el que Casey Muratori explica cómo el equipo de desarrollo de The Witness resolvió un problema real de rendimiento con SIMD: https://www.youtube.com/watch?v=Ge3aKEmZcqY

    • Es una excelente charla, pero el video es demasiado largo para recomendarlo a otras personas; sería bueno tener una versión escrita centrada en lo esencial.
      Como ejemplo de integración vertical para rendimiento, muestra cómo, después de entender por qué existen las abstracciones generales y por qué deben ser de propósito general, en un caso de uso concreto se puede integrar verticalmente desde la definición del problema hasta SIMD y obtener grandes beneficios.

  • Antes de meterse en microoptimizaciones como SIMD, primero hay que revisar seriamente las estructuras de datos y los patrones de acceso.
    En un código antiguo en Zig había aplicado SIMD, pero el modelo de estructuras de datos iba exactamente en contra de la optimización; era como ponerle llantas de carreras de alto rendimiento a un auto viejo con el motor arruinado. Fue la típica optimización prematura, sin medir el rendimiento ni considerar dónde se asignaba la memoria.
    Ahora veo los datos como si fueran tablas SQL y diseño las estructuras alrededor de posibles claves primarias y patrones de acceso. Antes usaba un árbol que apuntaba a otras estructuras en el heap, cargando con las desventajas de una lista enlazada, la fragmentación de múltiples vectores en el heap y el costo lento de creación y liberación; solo Drop ya consumía una parte considerable del tiempo de ejecución.
    Como un árbol siempre se puede linearizar, reviso los patrones de acceso e inserción, si en realidad es un árbol u otro tipo de grafo, y si conviene almacenarlo como un Vec o como una estructura con varios Vec. Como resultado, el código se volvió más rápido y más simple; los datos quedan reunidos en arreglos homogéneos, lo que facilita aprovechar las optimizaciones SIMD del compilador y la caché L1, y cuando hace falta también se puede escribir directamente código SIMD sin ramificaciones.
    Material relacionado: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

    • Para acelerar un hot loop con SIMD, la disposición de los datos y una estructura amigable con la caché son clave.
      En los cuellos de botella reales hay que evitar asignaciones de memoria, búsquedas en tablas de funciones virtuales y un exceso de indirecciones. Incluso vector de C++ no siempre es la mejor opción si puede invocar asignaciones inesperadas.
    • Como ingeniero de performance, es un problema que veo todo el tiempo. El rendimiento empieza en la arquitectura, y en rutas calientes con mala disposición de datos hay un límite a la performance que se puede exprimir.
      En cambio, el código orientado a datos casi siempre facilita el soporte para threading y SIMD.
    • Más básico aún: importan los patrones de acceso a memoria.
      Curiosamente, incluso el código para CPU termina escribiéndose con un estilo tipo GPU, y una forma de hacerlo es usar una estructura de arreglos al estilo Parquet en lugar de un arreglo de objetos.
    • Las tablas son una forma eficiente de implementar grafos generales y, mientras no se pueda especializar el grafo, son la mejor representación que conozco.