Presentación en HN: multiplicación de matrices con la mitad de multiplicaciones

Nueva arquitectura de hardware para machine learning

• Este repositorio contiene el código fuente de una arquitectura de hardware de ML que logra el mismo rendimiento que las operaciones convencionales de producto interno (inner product), pero requiere casi la mitad de operaciones de multiplicación.
• Eleva los límites teóricos de rendimiento y eficiencia computacional de los aceleradores de ML al ejecutar un algoritmo alternativo de producto interno que reemplaza casi la mitad de las multiplicaciones con sumas de bajo ancho de bits (low-bitwidth).
• Se puede encontrar más información en el artículo publicado en la revista IEEE Transactions on Computers.

Nuevo algoritmo y arquitectura de hardware

• Presenta un nuevo algoritmo y arquitectura de hardware llamados Free-pipeline Fast Inner Product (FFIP).
• Mejora el algoritmo de producto interno rápido (FIP) propuesto por Winograd en 1968.
• FIP no está relacionado con el algoritmo de filtrado mínimo de Winograd aplicado a capas convolucionales (convolutional), y puede aplicarse a cualquier capa de modelos de ML que pueda descomponerse principalmente en multiplicación de matrices.
• Implementa FIP por primera vez en un acelerador de ML, y presenta el algoritmo FFIP y una arquitectura generalizada que mejoran la frecuencia de reloj de FIP y, como resultado, su rendimiento.
• Aporta optimizaciones especializadas para ML sobre los algoritmos y arquitecturas FIP y FFIP.
• FFIP puede integrarse sin fricción en aceleradores de ML basados en systolic array de punto fijo, logrando el mismo rendimiento con la mitad de unidades MAC (multiplicación-acumulación), o permitiendo implementar un tamaño máximo de systolic array mayor con un presupuesto de hardware fijo.
• Las implementaciones de FFIP para modelos de ML no dispersos (non-sparse) con entradas de punto fijo de 8 a 16 bits logran mayor rendimiento y eficiencia computacional que las mejores soluciones de su clase en el mismo tipo de plataforma de cómputo.

Estructura del código fuente

• compiler: incluye un compilador que analiza descripciones de modelos en Python y las convierte en instrucciones para el acelerador; también incluye código de interfaz con el driver PCIe para iniciar la ejecución del modelo en el acelerador, leer resultados y contadores de rendimiento, y probar la exactitud de los resultados.
• rtl: incluye RTL sintetizable en SystemVerilog.
• sim: incluye scripts para configurar el entorno de simulación para pruebas.
• tests: incluye código fuente de un testbench basado en UVM que verifica el acelerador en simulación usando Cocotb.
• utils: incluye paquetes y scripts adicionales de Python usados en el proyecto, creados por el autor para utilidades generales de desarrollo y soporte.

Opinión de GN⁺

• Este artículo presenta un avance innovador en arquitectura de hardware para ML, especialmente al describir un nuevo algoritmo y arquitectura que reducen las operaciones de multiplicación sin sacrificar rendimiento. Es un avance importante que puede mejorar de forma significativa la eficiencia de las operaciones de ML.
• El algoritmo FFIP agrega una nueva dimensión al diseño de aceleradores de ML y ofrece una forma de usar los recursos de hardware de manera más eficiente. Esto es muy importante en los entornos de cómputo modernos, donde la eficiencia energética y de costos es prioritaria.
• Sin embargo, para que esta tecnología sea adoptada ampliamente, habrá que considerar su compatibilidad con aceleradores de ML existentes, el nivel de comprensión de los desarrolladores sobre la nueva arquitectura, y los temas de rendimiento y costo al implementarla en hardware real.
• Otros proyectos o productos con capacidades similares incluyen la TPU (Tensor Processing Unit) de Google y los núcleos CUDA de NVIDIA, que ya son soluciones de aceleración de ML validadas en el mercado.
• Al adoptar una nueva tecnología u open source, conviene considerar la compatibilidad con los sistemas existentes, el aumento de costos frente a la mejora de rendimiento, y la complejidad del desarrollo y mantenimiento. Entre los beneficios de elegir FFIP están el aumento del rendimiento y de la eficiencia computacional; entre las posibles desventajas, la curva de aprendizaje para los desarrolladores y el costo inicial de implementación.

[GN⁺]

Comentarios de Hacker News

• Esta técnica parece genial, pero me pregunto por qué no se ha implementado ya en aceleradores, si simplemente es un algoritmo olvidado o si tiene costos u otras implicaciones al construir el acelerador.
• Este artículo habla de sintetizar pipelines de multiplicación de matrices en hardware, y podría ser útil en hardware como FPGA o ASIC. En CPU o GPU, la multiplicación y la suma generalmente toman el mismo tiempo, pero las unidades de multiplicación ocupan más transistores, así que reducir la complejidad del circuito puede aumentar la velocidad y el rendimiento en paralelo, y reducir el consumo de energía y la complejidad del ruteo.
• Otra forma de eliminar multiplicaciones en la multiplicación de matrices es usar varios semianillos (semiring). Por ejemplo, el semianillo tropical (Tropical Semiring) usa suma en lugar de multiplicación, y mínimo (o máximo) en lugar de suma. Sigue siendo multiplicación de matrices, pero se sustituyen las operaciones binarias. La investigación en el campo del álgebra tropical (Tropical Algebra) se usa en problemas de optimización y en investigación sobre optimización de redes neuronales, y actualmente es activa y rica.
• Usar el semianillo logarítmico (Log Semiring) también es una forma de eliminar multiplicaciones de manera eficiente. Cuando hay que multiplicar cadenas de probabilidades (por ejemplo, en una cadena de Markov), los números se vuelven tan pequeños que el punto flotante pierde precisión. Al escalar los números en logaritmos, la multiplicación se convierte en suma, y la suma pasa a ser x + log1p(exp(y - x)).
• Sorprende que este método realmente funcione, porque decidir si usar multiplicación o suma puede ser más lento que simplemente usar multiplicación, especialmente cuando se realiza una gran cantidad de trabajo en paralelo.
• Es muy interesante que este proceso se haya inventado en 1968 y no se haya usado para este propósito hasta ahora.
• Intenté un concepto parecido en 2018, pero abandoné porque rechazaron todas mis solicitudes de doctorado. El concepto aquí intenta replicar la retropropagación con una red externa, y sostiene que eso probablemente es lo que realmente hace el cerebro.
• Si te interesa la teoría matemática de los algoritmos subcúbicos (sub-cubic) para multiplicación de matrices, puedes empezar aquí. Se conjetura que existe un número ( n ) tal que todas las matrices ( n \times n ) pueden multiplicarse en ( O(n^{2+j}) ) pasos (ahora demostrado para ( 2+j = w = 2.3728596 ) o ( j > 0.3728596 )).
• A este readme le falta muchísimo para explicar cuáles son las mejoras o cómo reduce a la mitad las multiplicaciones. No queda claro cuál es el tiempo de ejecución Big O ni si cambia los mejores límites conocidos. El diagrama es confuso y no explica por qué este enfoque es rápido o bueno. Como resultado, hasta da flojera hacer clic en el PDF. Para mejorar la credibilidad del proyecto, deberían considerar ofrecer una explicación e ilustraciones honestas y claras de lo que realmente está pasando.