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

 (github.com/trevorpogue)
3 puntos por GN⁺ 2024-03-17 | 1 comentarios | Compartir por WhatsApp
  • Este repositorio contiene el código fuente para validar una arquitectura de systolic array para GEMM y aceleradores de hardware de deep learning que calcula el mismo resultado de multiplicación de matrices con menos recursos de hardware o menos tiempo de ejecución
  • El enfoque propuesto reemplaza parte de las multiplicaciones de matrices por sumas de bajo ancho de bits más baratas, con el objetivo de reducir a la mitad los multiplicadores necesarios para el mismo rendimiento o aumentar el rendimiento por unidad MAC
  • Los resultados logran hasta 3× de aceleración en inferencia de CNN, más de 2× de rendimiento de multiplicación por multiplicador/reloj, menor área y mayor frecuencia de reloj frente a aceleradores recientes sobre plataformas de cómputo similares
  • El alcance incluye dense matrix multiplication y las fully-connected layers, CNN, RNN y attention layers/transformer models que la usan principalmente, y en general genera la misma salida que los métodos existentes en inferencia de punto fijo y cuantizada
  • La arquitectura está diseñada para mantener la misma función e interfaz que un systolic array convencional, por lo que puede integrarse reemplazando la MXU de un sistema acelerador existente sin preprocesamiento ni posprocesamiento adicional

Objetivo y resultados del proyecto

  • Algebraic Enhancements for GEMM & AI Accelerators contiene el código fuente de sistemas aceleradores de hardware para GEMM y deep learning
  • Este sistema se usa para validar arquitecturas de systolic array que implementan en hardware algoritmos eficientes de multiplicación de matrices propuestos o aún no suficientemente explorados
  • El objetivo es calcular la misma salida con menos recursos de hardware o en menos tiempo de ejecución
  • El rendimiento reportado es el siguiente
    • Hasta 3× más rápido en inferencia de CNN que aceleradores recientes implementados en el mismo tipo de plataforma de cómputo
    • Más de 2× en mults/multiplier/clock cycle, superando el límite convencional de 1
    • Menor área y mayor frecuencia de reloj

Arquitecturas validadas en papers y en la tesis doctoral

Por qué aumentar el rendimiento por MAC o por multiplicador

  • La mayor parte del trabajo de cómputo en modelos de deep learning normalmente puede mapearse a matrix multiplication, que se compone de una secuencia de operaciones multiply-accumulate
  • Sin innovación algebraica adicional, el throughput de un acelerador de deep learning queda limitado por el máximo número de operaciones MAC que puede ejecutar por clock cycle
  • Como los aceleradores de deep learning incluyen muchas MAC units, los multiplicadores y las MAC units tienden a ser recursos de cómputo que ocupan una gran parte del área de hardware en GEMM y aceleradores de deep learning
  • El throughput del acelerador puede quedar limitado directamente por la cantidad de multiplicadores que permite el presupuesto de hardware
    • En implementaciones sobre FPGA, las DSP units usadas para instanciar MAC units pueden agotarse antes que las LUT y los registers
  • Este proyecto explora cómo superar ese límite aplicando algebraic enhancements a algoritmos de matrix multiplication y a implementaciones de custom hardware

Alcance y restricciones

  • La arquitectura de hardware de systolic array propuesta mejora la aceleración de dense matrix multiplication
  • Puede usarse en modelos y layers de DNN que se descomponen principalmente en matrix multiplication
    • fully-connected layer
    • CNN
    • RNN
    • attention layer y transformer model
  • La mayoría de los aportes se enfocan en tipos de datos de punto fijo e inferencia de redes neuronales cuantizadas
    • Algunos conceptos de punto fijo podrían extenderse a floating point en el futuro
    • Como se usan tipos de datos de punto fijo, los algoritmos y arquitecturas de hardware presentados generan la misma salida que los algoritmos y arquitecturas existentes
    • No hay cambios en la numerical stability
  • Los resultados se validaron en FPGA, pero las arquitecturas propuestas son generales y la mayoría de las mejoras aplican tanto a custom integrated circuits como a implementaciones en FPGA
  • La arquitectura está basada en systolic array
    • Es un tipo de diseño eficiente usado en diseños de GEMM y aceleradores de deep learning como Google TPU
    • Algunos conceptos podrían extenderse a diseños non-systolic array en el futuro
    • Mantiene la misma función e interfaz que los systolic arrays existentes
    • El algebraic enhancement está completamente encapsulado dentro del systolic array y no requiere etapas adicionales de preprocesamiento ni posprocesamiento

Vista previa de resultados de rendimiento

  • Los resultados de síntesis y rendimiento que combinan las arquitecturas de [1] y [3] logran lo siguiente frente a aceleradores recientes sobre plataformas de cómputo similares

    • Hasta 3× más rápido en inferencia de CNN

    • 2× más alto en mults/multiplier/clock cycle

Estructura del sistema acelerador

  • El sistema acelerador de deep learning implementado en el código fuente se usa para alojar y validar los systolic arrays propuestos en [1]-[4]
  • La implementación del sistema está especializada en inferencia con entradas de punto fijo y cuantizadas de non-sparse DNN model
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • Todas las DNN layers se aceleran completamente en hardware
  • Un solo diseño de hardware puede acelerar ML models con arbitrary layer dimensions y kernel sizes
  • El input bitwidth y la dimensión del systolic array pueden configurarse como parámetros
  • También está altamente optimizado como GEMM accelerator general

Bloques principales

  • Matrix Multiply Unit / MXU

    • Incluye la arquitectura de systolic array que realiza la multiplicación de matrices
    • Los distintos systolic arrays/MXU propuestos en cada uno de los métodos [1]-[4] reemplazan la MXU del sistema

  • GEMM Unit

    • Incluye MXU, SRAM y addition logic
    • Permite ejecutar GEMM de matrices de tamaño arbitrario acumulando matrix tiles

  • Post-GEMM Unit

    • Ejecuta funciones específicas de redes neuronales sobre la salida de la matrix multiplication
    • Incluye suma de bias, inter-layer rescaling para quantization, activation, padding y pooling

  • Memory Unit

    • Incluye SRAM on-chip para almacenar activaciones de layers y lógica de control de acceso a memoria
    • Implementa algoritmos eficientes de hardware para caching y acceso a memoria que mapean convolution a GEMM in-place sin duplicación de datos ni delay
    • Usa un memory partitioning scheme que ejecuta la memoria SRAM y su control a media o cuarta frecuencia de reloj, mientras entrega datos nuevos a frecuencia completa para mejorar la frecuencia total del sistema y el consumo de energía

  • Off-chip DDR DRAM

    • Se usa para almacenar weights

  • RxTx Unit

    • Se encarga de la interfaz PCIe con el host

  • Instruction Unit

    • Decodifica las accelerator instructions enviadas por el host
    • Permite que un solo diseño de hardware acelere ML models con arbitrary layer dimensions y kernel sizes

Organización del código fuente

  • compiler
    • Compiler que parsea descripciones de ML models en Python hacia accelerator instructions
    • Incluye código que interactúa con el driver PCIe para iniciar la ejecución del model en el acelerador, leer resultados y performance counters, y probar la correctitud
  • rtl
    • SystemVerilog accelerator RTL sintetizable
  • sim
    • Scripts de configuración del simulation environment para validación
  • tests
    • Código fuente del UVM testbench escrito con Python y cocotb
  • utils
    • Paquetes adicionales de Python usados en el proyecto y utility scripts para desarrollo
  • rtl/top/define.svh y rtl/top/pkg.sv
    • Incluyen varios parámetros configurables
    • FIP_METHOD define el tipo de systolic array; ejemplos incluyen baseline, FIP, FFIP [1]
    • SZI y SZJ definen la altura y el ancho del systolic array
    • LAYERIO_WIDTH y WEIGHT_WIDTH definen el input bitwidth
  • rtl/arith
    • Incluye mxu.sv y mac_array.sv
    • Según el valor de FIP_METHOD, contiene el RTL de baseline y de algunas de las arquitecturas de systolic array propuestas, como FIP y FFIP [1]

Documentación adicional

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-03-17
Comentarios de Hacker News

  • Se ve bastante genial, pero ¿cuál es la trampa? Por ejemplo, me pregunto por qué no está ya implementado en aceleradores.
    Me pregunto si de verdad es solo un algoritmo olvidado, o si hay alguna restricción que afecte el costo de fabricar aceleradores, etc.

    • No es un simple algoritmo de software, sino una optimización de arquitectura de hardware.
      Para obtener beneficios, hay que fabricar hardware que coincida con las dimensiones del algoritmo, y esa es una decisión costosa.
    • Si se trata de un acelerador de multiplicación de matrices de punto fijo, no hay ninguna trampa especial; yo diría que simplemente es un algoritmo pasado por alto.
      Se basa en el algoritmo de Winograd, y resulta que Winograd propuso después otro algoritmo distinto que se volvió muy famoso en la aceleración de CNN, así que este algoritmo pudo haber recibido menos atención. Aunque esto es una conjetura.
    • Hay muchos algoritmos de multiplicación de matrices, y cada uno tiene ventajas y desventajas importantes.
      Siempre es un equilibrio entre precisión, tiempo de ejecución y escalabilidad, y es probable que este método tenga mala precisión con punto flotante.
    • No está completamente olvidado.
      Sobrevive en cierta medida dentro de autenticadores Wegman-Carter basados en seudoproducto interno, como UMAC. Para el contexto, ver el capítulo 3 de [1].
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • Lo revisé por encima, así que corríjanme si me equivoco, pero entendí que esto no es un reemplazo de la multiplicación de matrices, sino un método de aproximación que da resultados bastante decentes para el tipo de sistemas lineales que se ven en AI/ML.
      Para ese uso, me parece que podría ser suficientemente bueno.

  • Me recordó a algo parecido que intenté en 2018, pero lo dejé después de que me rechazaran todas las postulaciones a doctorado.
    https://github.com/ixaxaar/pytorch-dni
    El concepto aquí va un paso más allá: intenta replicar la retropropagación con una red externa y sostiene que el cerebro quizá realmente haga algo así.

    • No veo bien la conexión.
      Este trabajo es una optimización de bajo nivel de la multiplicación de matrices, mientras que el repositorio enlazado parece intentar reemplazar los gradientes retropropagados por estimaciones más baratas. Me pregunto cuál es la similitud entre ambos.
    • Esto se siente más bien como una situación de no hay almuerzo gratis.
      El tiempo que se ahorra aproximando así los gradientes parece que se perdería porque la pérdida de precisión de los gradientes exigiría más iteraciones de entrenamiento, ¿no?
    • Más allá de la discusión técnica, me pregunto con qué hicieron ese GIF de la arquitectura. Se ve bien.

  • Realmente interesante y vale la pena leerlo. Para quienes en los comentarios estén confundidos sobre por qué es mejor: el paper trata de sintetizar pipelines de multiplicación de matrices en hardware como FPGA o ASIC.
    En CPU o GPU, las sumas y las multiplicaciones suelen tardar más o menos lo mismo, así que es difícil percibir la diferencia, pero una unidad de multiplicación ocupa muchos más transistores. Reducir la complejidad del circuito puede aumentar la velocidad y el paralelismo, y reducir el consumo de energía y la complejidad del cableado. Este enfoque podría ser especialmente útil para aceleradores eficientes de multiplicación de matrices dispersas.
    Otra forma interesante de eliminar multiplicaciones en la multiplicación de matrices es usar otro semianillo (semiring) [1]. Por ejemplo, el Tropical Semiring [2] reemplaza la multiplicación por suma, y la suma por min o max. Sigue siendo multiplicación de matrices, pero con las operaciones binarias cambiadas. La investigación en Tropical Algebra [3], un campo relativamente nuevo, es ahora bastante activa y rica, y se usa en diversos problemas de optimización y en investigaciones sobre optimización de redes neuronales [4].
    Este método también se adapta bien a la síntesis de hardware, porque la mayoría de los bloques lógicos configurables de un FPGA pueden hacer add/min/max en un ciclo de reloj, mientras que una multiplicación eficiente requiere multiplicadores de hardware dedicados en el chip, de función fija.
    Otra forma relacionada de eliminar eficientemente la multiplicación con otro semianillo es usar el Log Semiring [5]. Si hay que multiplicar probabilidades en cadena, como en las cadenas de Markov, los números se vuelven muy pequeños rápidamente y se pierde precisión de punto flotante. Si primero se toma el logaritmo para escalar, la multiplicación se convierte en suma, y la suma se convierte en x + log1p(exp(y - x)).
    [1] https://en.wikipedia.org/wiki/Semiring
    [2] https://en.wikipedia.org/wiki/Tropical_semiring
    [3] https://en.wikipedia.org/wiki/Tropical_geometry
    [4] https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf
    [5] https://en.wikipedia.org/wiki/Log_semiring

    • El paper de [4] es realmente fascinante.
      Soy casi principiante en esta área, pero parece demostrar que casi cualquier red ReLU puede expresarse como una razón tropical de dos polinomios tropicales y, por lo tanto, analizarse con principios geométricos, como la visualización de superficies. También lo citan trabajos más recientes: https://scholar.google.com/scholar?cites=1003719112553620451... Me pregunto si ha habido avances significativos en esto.
    • Vaya, esto es justo lo que cubre Unified Algebra.
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • En la parte de tomar logaritmos para escalar los números, de modo que la multiplicación se vuelva suma y la suma se vuelva x + log1p(exp(y - x)): en un sistema numérico logarítmico, la suma/resta es mucho más cara que la multiplicación.
      Sobre todo si te importa obtener resultados correctamente redondeados; las tablas de consulta de hardware necesarias se vuelven bastante grandes.
    • ¿La idea de tomar logaritmos para convertir multiplicaciones en sumas no es la misma aproximación que se viene usando desde hace décadas en GF(2^x)?
      La única limitación que se me ocurre es el tamaño del cuerpo.
    • Algo relacionado es la transformada de teoría de números.
      https://ieeexplore.ieee.org/abstract/document/1451721

  • Me sorprende que esto realmente funcione.
    Por lo general, el costo de detectar si hay que usar multiplicación o suma es más lento que simplemente multiplicar. Especialmente cuando se ejecuta una cantidad enorme de trabajo en paralelo.

    • Me pregunto cómo se compararía con OpenBLAS y cuBLAS.

  • Es interesante que un procedimiento inventado en 1968 no se haya usado para este propósito hasta ahora.

    • Nadie supo para qué usar GF(2^x) hasta mediados del siglo pasado.
      Ah, ahora que lo pienso, la ciencia de la computación en sí casi no existía hasta mediados del siglo pasado.

  • Si te interesa la teoría matemática detrás de los algoritmos subcúbicos para multiplicación de matrices, puedes empezar aquí: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    Se conjetura que, para todo número real j > 0, existe algún n tal que dos matrices arbitrarias de n x n pueden multiplicarse en O(n^(2+j)) pasos.
    Actualmente está demostrado para 2+j = w = 2.3728596, es decir, para j > 0.3728596.

    • No sé si esta formulación es correcta.
      Si empieza con “para todo j existe algún n”, entonces n y j se vuelven constantes en la oración siguiente. Entonces solo dice que se pueden multiplicar matrices de tamaño constante en tiempo constante. Técnicamente es cierto, pero parece que quería afirmar algo más fuerte.
    • Parece que el progreso se vuelve más difícil con el tiempo.
      Tal vez toque fondo en j=1/e. Ni siquiera lo llamaría conjetura; solo es una constante conveniente cerca del valor actual. Sería bastante gracioso si las matemáticas nos jugaran esa broma.
    • Predecir que se cumple para cualquier j > 0 es bastante audaz.
      ¿Podrías compartir la intuición de por qué se piensa eso?

  • Este README explica realmente mal cuál es la mejora y cómo reduce a la mitad las multiplicaciones.
    ¿Cuál es el tiempo de ejecución Big O? ¿Cambia la mejor cota conocida?
    Las imágenes también son confusas y casi no explican por qué este enfoque es más rápido o mejor. Por eso me da poca gana hacer clic hasta el PDF.
    Si quieren aumentar la credibilidad del proyecto, estaría bueno explicar de forma honesta y clara qué está pasando realmente, y ofrecer explicaciones y diagramas claros en lugar de imágenes que parecen atraer a la gente con hype. Es difícil distinguir si esto es un avance enorme o algo sin mayor importancia. Lamentablemente, también se siente como una decisión deliberada para aprovechar la fiebre por la IA. La alternativa en la que preferiría creer es que el autor simplemente necesita corregirlo y dar mejor contexto.

    • Sobre “¿cuál es el tiempo de ejecución Big O?”, como la afirmación es que reduce a la mitad las multiplicaciones, no afecta la Big O.
      La matemática del paper (https://arxiv.org/abs/2311.12224) para reducir a la mitad la cantidad de multiplicaciones no es difícil de entender. Solo hace falta leer la ecuación 2, que es la multiplicación de matrices tradicional, y las ecuaciones 3 a 6.
      Parece claro que, a cambio de reducir las multiplicaciones a la mitad como se anuncia, agrega muchas sumas/restas. Después vectorizan mejor ese algoritmo, y como suele pasar con este tipo de trabajos, se vuelve complejo rápidamente.
      La principal preocupación es la estabilidad numérica.
    • El README no explica mucho, pero la introducción del paper en sí es bastante accesible.
      En cuanto a si es revolucionario, lo veo como una mejora limpia por un factor constante, aplicable directamente a aceleradores de punto fijo con restricciones de área. No va a cambiar todo de la noche a la mañana, pero tampoco es nada. Es un buen trabajo.
    • No quiero sonar elitista, pero no entiendo para nada el punto de este comentario.
      Si no entiendes la notación Big O lo suficiente como para saber que “reducir a la mitad las multiplicaciones” no cambia la Big O, no sé por qué lo preguntas.