Algoritmos SIMD diseñados desde cero

Diseño de algoritmos SIMD

• Explicación de la optimización con SIMD: SIMD significa instrucción única, múltiples datos, y requiere pensar como un diseñador de circuitos.
• SIMD se menciona con frecuencia en rendimiento y HPC (computación de alto rendimiento), pero no es un tema familiar para principiantes.
• En la mayoría de los lenguajes de programación, las API de programación SIMD son difíciles de usar.
• Los algoritmos SIMD son difíciles de entender con una mentalidad de programación procedural, y la programación funcional puede ayudar.
• El artículo trata sobre vb64, que implementa un códec base64 usando la biblioteca std::simd de Rust.

Límites físicos

• Las computadoras existen en el mundo real y están sujetas a las leyes de la física.
• En los primeros tiempos de la computación, se podía mejorar el rendimiento comprando una computadora nueva.
• El efecto del escalado de Dennard colapsó, por lo que transistores más pequeños implican un mayor consumo de energía.
• Aumentar la cantidad de núcleos se convirtió en la nueva tendencia. El multithreading puede mejorar el rendimiento de la CPU, pero introduce sobrecarga de sincronización.

La lentitud del código procedural

• Los núcleos modernos de computadora no ejecutan código línea por línea.
• Mediante paralelismo a nivel de instrucción, realizan varias operaciones al mismo tiempo cuando no hay dependencias de datos.
• El paralelismo aumenta cuando el compilador puede resolver los riesgos de datos.
• Las bifurcaciones y las operaciones de memoria provocan stalls, lo que hace que el código sea más lento.

SIMD y los lanes

• SIMD y vector suelen usarse como sinónimos.
• Las instrucciones SIMD usan como unidad básica vectores, que son arreglos de números de tamaño fijo.
• Cada elemento del vector se llama lane, y los vectores SIMD por lo general son pequeños.

Operaciones sobre vectores reales

• Los vectores SIMD ofrecen operaciones más complejas que los registros normales.
• Los registros vectoriales admiten diversas operaciones como operaciones de bits, aritmética por lane, comparaciones por lane y shuffles.
• Los shuffles son importantes en la programación SIMD para mover los datos a la posición adecuada.

Funciones intrínsecas y selección de instrucciones

• Al escribir código SIMD, las operaciones disponibles varían según la arquitectura.
• El compilador resuelve el problema de selección de instrucciones al decidir con qué instrucción implementar la operación solicitada por el usuario.
• Escribir código SIMD portable es complejo, pero con detección de capacidades en tiempo de ejecución se puede generar código óptimo para distintos procesadores.

Parsing con SIMD

• Es posible hacer parsing de texto con SIMD, y puede ser muy rápido.
• Un ejemplo es implementar decodificación base64 con SIMD.
• El punto clave para crear una versión SIMD es eliminar todas las bifurcaciones.

Opinión de GN⁺

Lo más importante de este artículo es que la programación SIMD, a diferencia de la programación procedural tradicional, puede mejorar el rendimiento procesando datos en paralelo. SIMD es muy importante en el campo de la computación de alto rendimiento y, en particular, entender cómo usar SIMD de forma efectiva en lenguajes modernos como Rust puede ser un tema muy interesante para ingenieros de software. Esto se debe a que permite aprender a optimizar algoritmos complejos y a superar las limitaciones del hardware real.

[GN⁺]

Comentarios de Hacker News

• Un gran artículo para ver casos de uso de SIMD portable. Al reproducir los benchmarks en un sistema Zen 3, confirmé la misma mejora de velocidad. En una M1 mbp, la mejora de rendimiento aumenta gradualmente hasta un máximo de 2x con una longitud de entrada de 110 bytes. La ganancia es menor que en x86_64, pero se puede decir que cumplió el objetivo. Sin embargo, también confirmó que Rust resulta algo incómodo para tareas relacionadas con SIMD y punteros, así como para la ingeniería de rendimiento en general.
• A veces sorprende que, incluso intentando programar lo mejor posible en C++, una versión con SIMD muestre un rendimiento más de 10 veces más rápido. La portabilidad del código disminuye, pero ojalá el compilador hiciera mejor la autovectorización. También me gustaría que el lenguaje añadiera soporte para reorganizar el orden de ciertas operaciones mediante anotaciones.
• Señala que el compilador no pudo optimizar cierta implementación de popcount en una sola instrucción, aunque en otras implementaciones sí puede hacerlo en algunos casos.
• _mm256_cvtps_epu32 no es una instrucción de AVX2 sino de AVX-512, y en AVX1 los enteros existen en forma con signo, por lo que esa instrucción es _mm256_cvtps_epi32.
• Me gusta mucho el pequeño minimapa de la derecha.
• Considera que ISPC es mejor que agregar SIMD a C++ o Rust. Además, soporta despacho dinámico, una funcionalidad difícil de implementar por cuenta propia.
• Plantea la pregunta de cómo se compara con fastbase64 y expresa que le gustaría compartir la actitud optimista del autor sobre las bibliotecas portables de SIMD.
• Un gran artículo, que deja la impresión de que uno jamás podría llegar a ser tan inteligente.
• Se menciona que el primer ejemplo de implementación de popcnt no vectorizada genera "un código francamente ridículo", pero al compilar en modo release para la CPU nativa, parece que la función se vectoriza bastante bien.
• Un intento bastante bueno con Rust Simd. Plantea la pregunta de cuál fue la anomalía más sorprendente al inspeccionar el código generado.