Présentation HN : multiplication matricielle avec deux fois moins de multiplications

 (github.com/trevorpogue)
3 points par GN⁺ 2024-03-17 | 1 commentaires | Partager sur WhatsApp
  • Ce dépôt contient le code source destiné à valider une architecture de systolic array qui calcule les mêmes résultats de multiplication matricielle avec moins de ressources matérielles ou en moins de temps dans des accélérateurs matériels GEMM et de deep learning
  • L’approche proposée remplace une partie des multiplications matricielles par des additions à faible largeur de bits, moins coûteuses, avec pour objectif de réduire de moitié le nombre de multipliers nécessaires à performances égales, ou d’augmenter les performances par unité MAC
  • Les résultats atteignent jusqu’à 3× d’accélération pour l’inférence CNN par rapport aux accélérateurs de pointe sur des plateformes de calcul similaires, plus de 2× de débit de multiplication par multiplier/clock, ainsi qu’une faible surface et une fréquence d’horloge élevée
  • Le champ d’application couvre la dense matrix multiplication et les fully-connected layers, CNN, RNN, attention layers/modèles transformer qui l’utilisent principalement ; l’approche produit les mêmes sorties que les méthodes existantes, surtout en inférence fixe·quantifiée
  • L’architecture est conçue pour conserver les mêmes fonctions et interfaces qu’un systolic array existant, ce qui permet de l’intégrer en remplaçant le MXU d’un système d’accélérateur existant, sans prétraitement ni post-traitement supplémentaires

Objectif et résultats du projet

  • Algebraic Enhancements for GEMM & AI Accelerators contient le code source de systèmes d’accélération matérielle GEMM et de deep learning
  • Ce système sert à valider des architectures de systolic array qui implémentent en matériel des algorithmes efficaces de multiplication matricielle, proposés ou encore peu explorés
  • L’objectif est de calculer les mêmes sorties avec moins de ressources matérielles ou un temps d’exécution plus court
  • Les performances présentées sont les suivantes
    • Jusqu’à 3× plus rapide pour l’inférence CNN que les accélérateurs de pointe implémentés sur des plateformes de calcul du même type
    • Plus de 2× de mults/multiplier/clock cycle, au-delà de la limite conventionnelle de 1
    • Faible surface et fréquence d’horloge élevée

Architectures validées dans les articles et la thèse de doctorat

Pourquoi augmenter les performances par MAC·multiplier

  • La majeure partie du calcul dans les modèles de deep learning peut généralement être mappée vers de la matrix multiplication, elle-même composée de séquences d’opérations multiply-accumulate
  • Sans innovation algébrique supplémentaire, le débit des accélérateurs de deep learning est limité par le nombre maximal d’opérations MAC réalisables par clock cycle
  • Les accélérateurs de deep learning contiennent de nombreuses unités MAC ; les multipliers et les unités MAC tendent donc à devenir des compute resources occupant une grande part de la surface matérielle dans les accélérateurs GEMM et de deep learning
  • Le débit de l’accélérateur peut être directement limité par le nombre de multipliers que le budget matériel peut prendre en charge
    • Dans une implémentation FPGA, les unités DSP qui instancient les unités MAC peuvent être épuisées avant les LUT et les registres
  • Ce projet explore comment dépasser cette limite en appliquant des algebraic enhancements aux algorithmes de multiplication matricielle et à leurs implémentations custom hardware

Champ d’application et contraintes

  • L’architecture matérielle de systolic array proposée améliore l’accélération de la dense matrix multiplication
  • Elle peut être utilisée dans les modèles et layers DNN principalement décomposés en multiplication matricielle
    • fully-connected layer
    • CNN
    • RNN
    • attention layer et modèle transformer
  • La plupart des contributions se concentrent sur les types de données à virgule fixe et l’inférence de réseaux neuronaux quantifiés
    • Certains concepts en virgule fixe pourraient être étendus à la virgule flottante à l’avenir
    • Comme les types de données à virgule fixe sont utilisés, les algorithmes et architectures matérielles présentés produisent les mêmes sorties que les algorithmes et architectures existants
    • La stabilité numérique n’est pas modifiée
  • Les résultats ont été validés sur FPGA, mais les architectures proposées sont générales et la plupart des améliorations s’appliquent aussi bien aux implémentations en custom integrated circuit qu’aux FPGA
  • Les architectures reposent sur des systolic arrays
    • Il s’agit d’un type de conception efficace utilisé dans les architectures GEMM et d’accélération du deep learning, comme les Google TPU
    • Certains concepts pourraient être étendus à l’avenir à des conceptions non systolic array
    • Elles conservent les mêmes fonctions et interfaces qu’un systolic array existant
    • Les algebraic enhancements sont entièrement self-contained à l’intérieur du systolic array et ne nécessitent aucune étape supplémentaire de prétraitement ou de post-traitement

Aperçu des résultats de performance

  • Les résultats de synthèse et de performance combinant les architectures de [1] et [3] atteignent les résultats suivants par rapport aux accélérateurs de pointe sur des plateformes de calcul similaires

Structure du système d’accélérateur

  • Le système d’accélérateur de deep learning implémenté dans le code source sert à héberger et valider les systolic arrays proposés dans [1]-[4]
  • L’implémentation du système est spécialisée pour l’inférence à entrées en virgule fixe·quantifiées de modèles DNN non sparse
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • Tous les layers DNN sont entièrement accélérés en matériel
  • Une seule conception matérielle peut accélérer un modèle ML avec des dimensions de layers et des tailles de kernels arbitraires
  • La input bitwidth et la dimension du systolic array sont configurables sous forme de paramètres
  • Le système est aussi fortement optimisé comme accélérateur GEMM généraliste

Blocs principaux

  • Matrix Multiply Unit / MXU

    • Contient l’architecture de systolic array qui effectue la multiplication matricielle
    • Les différents systolic arrays/MXU proposés par chacune des méthodes de [1]-[4] remplacent le MXU du système

  • GEMM Unit

    • Contient le MXU, la SRAM et la logique d’addition
    • Accumule des matrix tiles pour permettre l’exécution de GEMM sur des matrices de taille arbitraire

  • Post-GEMM Unit

    • Exécute des fonctions neural network-specific sur la sortie de la multiplication matricielle
    • Inclut l’ajout de biais, l’inter-layer rescaling pour la quantization, l’activation, le padding et le pooling

  • Memory Unit

    • Contient la SRAM on-chip qui stocke les layer activations et la logique de contrôle des accès mémoire
    • Implémente des algorithmes matériels efficaces de caching et d’accès mémoire qui mappent les convolutions vers GEMM in-place, sans duplication de données ni délai
    • Utilise un memory partitioning scheme qui exécute la mémoire SRAM et le contrôle à une fréquence d’horloge moitié ou quart, tout en émettant de nouvelles données à pleine fréquence, afin d’améliorer la fréquence et la consommation du système global

  • Off-chip DDR DRAM

    • Utilisée pour stocker les weights

  • RxTx Unit

    • Prend en charge l’interface PCIe connectée à l’host

  • Instruction Unit

    • Décode les instructions de l’accélérateur envoyées par l’host
    • Permet à une seule conception matérielle d’accélérer un modèle ML avec des dimensions de layers et des tailles de kernels arbitraires

Organisation du code source

  • compiler
    • Compilateur qui parse une description de modèle ML en Python en instructions d’accélérateur
    • Inclut le code qui s’interface avec le driver PCIe pour lancer l’exécution du modèle sur l’accélérateur, lire les résultats et les performance counters, et tester la correctness
  • rtl
    • RTL d’accélérateur SystemVerilog synthétisable
  • sim
    • Scripts de configuration de l’environnement de simulation pour la vérification
  • tests
    • Code source de testbench UVM écrit en Python et cocotb
  • utils
    • Packages Python supplémentaires et scripts utilitaires de développement utilisés dans le projet
  • rtl/top/define.svh et rtl/top/pkg.sv
    • Contiennent plusieurs paramètres configurables
    • FIP_METHOD définit le type de systolic array ; baseline, FIP et FFIP [1] en sont des exemples
    • SZI et SZJ définissent la hauteur et la largeur du systolic array
    • LAYERIO_WIDTH et WEIGHT_WIDTH définissent la input bitwidth
  • rtl/arith
    • Contient mxu.sv et mac_array.sv
    • Contient le RTL de la baseline ainsi que de certaines architectures de systolic array proposées, FIP et FFIP [1], selon la valeur de FIP_METHOD

Documentation supplémentaire

À lire aussi

1 commentaires

 
GN⁺ 2024-03-17
Avis sur Hacker News

  • Ça a l’air plutôt cool, mais où est le piège ? Par exemple, je me demande pourquoi ce n’est pas déjà implémenté dans les accélérateurs.
    Je me demande si c’est vraiment juste un algorithme oublié, ou s’il existe des contraintes qui influent sur le coût de fabrication des accélérateurs, etc.

    • Ce n’est pas un simple algorithme logiciel, mais une optimisation d’architecture matérielle.
      Pour en tirer parti, il faut construire du matériel adapté aux dimensions de l’algorithme, et c’est une décision coûteuse.
    • Pour un accélérateur de multiplication matricielle en virgule fixe, il n’y a pas de piège particulier ; à mon avis, c’est simplement un algorithme qui a été négligé.
      Il est basé sur l’algorithme de Winograd ; par coïncidence, Winograd a ensuite proposé un autre algorithme, distinct, devenu très célèbre pour l’accélération des CNN, ce qui a peut-être fait passer celui-ci au second plan. Mais ce n’est qu’une hypothèse.
    • Il existe beaucoup d’algorithmes de multiplication matricielle, chacun avec de gros avantages et inconvénients.
      C’est toujours un compromis entre précision, temps d’exécution et scalabilité ; cette approche risque d’avoir une mauvaise précision en virgule flottante.
    • Il n’est pas complètement oublié.
      Il subsiste en partie dans les authentificateurs de Wegman-Carter fondés sur des pseudo-produits scalaires, comme UMAC. Pour le contexte, voir le chapitre 3 de [1].
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • Je n’ai fait que parcourir rapidement, donc corrigez-moi si je me trompe, mais je l’ai compris non pas comme un remplacement de la multiplication matricielle, mais comme une méthode d’approximation qui donne d’assez bons résultats pour le type de systèmes linéaires qu’on voit en IA/ML.
      Pour cet usage, ça me semble largement acceptable.

  • Ça me rappelle un truc similaire que j’avais essayé de faire en 2018, avant d’abandonner après avoir été refusé à toutes mes candidatures en doctorat.
    https://github.com/ixaxaar/pytorch-dni
    Ici, le concept va un cran plus loin : il tente de répliquer la rétropropagation avec un réseau externe, et soutient que le cerveau pourrait réellement fonctionner ainsi.

    • Je ne vois pas bien le lien.
      Ce travail est une optimisation bas niveau de la multiplication matricielle, tandis que le dépôt lié semble chercher à remplacer les gradients rétropropagés par une estimation moins coûteuse. Je me demande en quoi les deux se ressemblent.
    • Ça ressemble plutôt à une situation de type pas de repas gratuit.
      Le temps économisé en approximant ainsi les gradients risque d’être perdu parce que la baisse de précision des gradients exigera davantage d’itérations d’entraînement, non ?
    • En dehors de la discussion technique, je me demande avec quoi ce GIF d’architecture a été fait. Il est joli.

  • Vraiment intéressant et ça vaut la lecture. Pour ceux qui, dans les commentaires, ne voient pas pourquoi c’est mieux : l’article parle de synthétiser un pipeline de multiplication matricielle dans du matériel comme des FPGA ou des ASIC.
    Sur CPU ou GPU, les additions et les multiplications prennent globalement un temps similaire, donc c’est difficile à percevoir, mais les unités de multiplication occupent beaucoup plus de transistors. Réduire la complexité du circuit peut augmenter la vitesse et le débit parallèle, tout en diminuant la consommation et la complexité du routage. Cette approche peut être particulièrement utile pour des accélérateurs efficaces de multiplication de matrices creuses.
    Une autre façon élégante d’éliminer les multiplications dans la multiplication matricielle consiste à utiliser un autre semi-anneau (semiring) [1]. Par exemple, le Tropical Semiring [2] remplace la multiplication par l’addition, et l’addition par min ou max. Cela reste une multiplication matricielle, mais avec des opérations binaires différentes. La Tropical Algebra [3], domaine relativement récent, fait aujourd’hui l’objet de recherches assez actives et riches, et elle est utilisée dans divers problèmes d’optimisation ainsi que dans la recherche sur l’optimisation des réseaux de neurones [4].
    Cette méthode se prête aussi bien à la synthèse matérielle, car la plupart des blocs logiques configurables des FPGA peuvent faire add/min/max en un cycle d’horloge, tandis qu’une multiplication efficace nécessite des multiplicateurs matériels dédiés et fixes sur la puce.
    Une autre manière, liée, d’éliminer efficacement les multiplications avec un autre semi-anneau consiste à utiliser le Log Semiring [5]. Quand il faut multiplier des probabilités en chaîne, comme dans les chaînes de Markov, les nombres deviennent très vite extrêmement petits et la précision en virgule flottante se dégrade. Si l’on prend d’abord les logarithmes pour changer d’échelle, la multiplication devient une addition, et l’addition devient 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

    • L’article [4] est vraiment fascinant.
      Je suis presque débutant dans ce domaine, mais il semble montrer que presque tout réseau ReLU peut être représenté comme le quotient tropical de deux polynômes tropicaux, et donc analysé à l’aide de principes géométriques comme la visualisation de surfaces. Il est aussi cité par des travaux plus récents : https://scholar.google.com/scholar?cites=1003719112553620451... Je me demande s’il y a eu des avancées significatives depuis.
    • Waouh, c’est exactement le genre de choses dont traite Unified Algebra.
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • Concernant le fait de prendre les logarithmes pour changer l’échelle des nombres, de sorte que la multiplication devienne une addition et l’addition x + log1p(exp(y - x)) : dans un système de nombres logarithmiques, l’addition/soustraction coûte beaucoup plus cher que la multiplication.
      En particulier si l’on se soucie d’obtenir un résultat correctement arrondi, les tables de correspondance matérielles nécessaires deviennent assez grandes.
    • Transformer la multiplication en addition en prenant des logarithmes, ce n’est pas la même approche que celle utilisée depuis des décennies avec GF(2^x) ?
      La seule limite qui me vient à l’esprit est la taille du corps.
    • Dans le même esprit, il y a aussi les transformées arithmétiques en nombres entiers.
      https://ieeexplore.ieee.org/abstract/document/1451721

  • C’est étonnant que ça fonctionne réellement.
    En général, le coût de détection pour savoir s’il faut utiliser une multiplication ou une addition est plus lent que de simplement faire la multiplication. C’est encore plus vrai quand on exécute une quantité énorme de travail en parallèle.

    • Je me demande ce que ça donnerait face à OpenBLAS et cuBLAS.

  • C’est intéressant qu’une procédure inventée en 1968 n’ait pas été utilisée à cette fin jusqu’à maintenant.

    • Personne ne savait vraiment à quoi servirait GF(2^x) non plus avant le milieu du siècle dernier.
      Ah, maintenant que j’y pense, l’informatique elle-même n’existait quasiment pas avant le milieu du siècle dernier.

  • Si la théorie mathématique derrière les algorithmes sous-cubiques de multiplication matricielle vous intéresse, vous pouvez commencer ici : https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    On conjecture que pour tout réel j > 0, il existe un certain n tel que deux matrices n x n arbitraires puissent être multipliées en O(n^(2+j)) étapes.
    Actuellement, c’est prouvé pour 2+j = w = 2.3728596, c’est-à-dire pour j > 0.3728596.

    • Je ne suis pas sûr que cette formulation soit correcte.
      Si l’on commence par « pour tout j, il existe un n », alors dans la suite de la phrase n et j deviennent des constantes. Cela revient seulement à dire qu’on peut multiplier des matrices de taille constante en temps constant. Techniquement c’est vrai, mais j’imagine que l’intention était d’affirmer quelque chose de plus fort.
    • On dirait que les progrès deviennent de plus en plus difficiles avec le temps.
      Peut-être que le plancher se situera à j=1/e. Je n’irais même pas jusqu’à appeler ça une conjecture, c’est juste une constante pratique proche de la valeur actuelle. Ce serait assez drôle si les maths nous jouaient ce genre de tour.
    • Prédire que c’est vrai pour tout j > 0 est plutôt audacieux.
      Peux-tu partager l’intuition qui te fait penser cela ?

  • Ce README explique vraiment mal quelle est l’amélioration et comment le nombre de multiplications est divisé par deux
    Quel est le temps d’exécution en Big O ? Est-ce que cela modifie la meilleure borne connue ?
    Les schémas sont eux aussi confus et n’expliquent presque pas pourquoi cette approche serait plus rapide ou meilleure. Du coup, je n’ai pas très envie de cliquer jusqu’au PDF
    Si le projet veut gagner en crédibilité, il vaudrait mieux expliquer honnêtement et clairement ce qui se passe réellement, et fournir des explications et des schémas nets plutôt que des illustrations qui semblent attirer les gens avec du battage médiatique. Il est difficile de dire si c’est une avancée majeure ou quelque chose d’assez anodin. Malheureusement, cela donne aussi l’impression d’un choix délibéré visant à profiter de l’engouement autour de l’IA. L’hypothèse alternative à laquelle j’aimerais davantage croire, c’est que l’auteur doit simplement corriger la présentation et donner un meilleur contexte

    • À propos de « quel est le temps d’exécution en Big O ? », comme l’affirmation est que le nombre de multiplications est divisé par deux, cela n’a pas d’effet sur le Big O
      Les mathématiques qui divisent par deux le nombre de multiplications dans l’article (https://arxiv.org/abs/2311.12224) ne sont pas difficiles à comprendre. Il suffit de lire l’équation 2, qui correspond à la multiplication matricielle classique, puis les équations 3 à 6
      En échange de cette division par deux des multiplications, comme annoncé, il semble clair qu’on ajoute beaucoup d’additions/soustractions. Ensuite, l’algorithme est mieux vectorisé, et comme c’est souvent le cas avec ce genre de travail, cela devient vite complexe
      Ma principale inquiétude concerne la stabilité numérique
    • Le README n’explique pas grand-chose, mais l’introduction de l’article lui-même est assez accessible
      Quant à savoir si c’est révolutionnaire, je vois ça comme une amélioration propre d’un facteur constant, directement applicable aux accélérateurs en virgule fixe soumis à des contraintes de surface. Ça ne va pas tout changer du jour au lendemain, mais ce n’est pas rien non plus. C’est du bon travail
    • Je ne veux pas paraître élitiste, mais je ne comprends pas du tout le sens de ce commentaire
      Si l’on ne comprend pas assez la notation Big O pour savoir que « diviser par deux les multiplications » ne change pas le Big O, je ne vois pas pourquoi poser la question