Présentation sur HN : une multiplication de matrices qui réduit de moitié le nombre de multiplications

Nouvelle architecture matérielle pour le machine learning

• Ce dépôt contient le code source d’une architecture matérielle ML qui atteint les mêmes performances que les opérations classiques de produit scalaire (inner product), tout en ne nécessitant qu’environ la moitié des multiplications.
• Elle exécute un algorithme alternatif de produit scalaire qui remplace près de la moitié des multiplications par des additions en faible précision (low-bitwidth), ce qui repousse les limites théoriques de débit et d’efficacité de calcul des accélérateurs ML.
• Plus de détails sont disponibles dans un article publié dans la revue IEEE Transactions on Computers.

Nouvel algorithme et nouvelle architecture matérielle

• Présentation d’un nouvel algorithme et d’une nouvelle architecture matérielle appelés Free-pipeline Fast Inner Product (FFIP).
• Il s’agit d’une amélioration du Fast Inner Product (FIP), un algorithme rapide de produit scalaire proposé par Winograd en 1968.
• Le FIP n’a aucun lien avec l’algorithme de filtrage minimal de Winograd appliqué aux couches convolutionnelles (convolutional) et peut s’appliquer à toute couche de modèle ML pouvant principalement se ramener à une multiplication de matrices.
• Première implémentation du FIP dans un accélérateur ML, avec présentation de l’algorithme FFIP et d’une architecture généralisée qui améliorent la fréquence d’horloge du FIP et, par conséquent, le débit obtenu.
• Contribution d’optimisations spécialisées ML pour les algorithmes et architectures FIP et FFIP.
• FFIP peut être intégré de façon transparente dans les accélérateurs ML à systolic array en virgule fixe (fixed-point), afin d’atteindre le même débit avec moitié moins d’unités MAC (multiply-accumulate), ou de permettre une taille maximale de systolic array plus grande à budget matériel constant.
• Les implémentations FFIP pour des modèles ML non clairsemés (non-sparse) utilisant des entrées en virgule fixe de 8 à 16 bits atteignent un débit et une efficacité de calcul supérieurs à ceux des meilleures solutions actuelles sur le même type de plateforme de calcul.

Structure du code source

• compiler : contient un compilateur qui convertit les descriptions de modèles Python en instructions pour l’accélérateur, ainsi que le code d’interface avec le pilote PCIe pour lancer l’exécution du modèle sur l’accélérateur, lire les résultats et les compteurs de performance, et tester l’exactitude des résultats.
• rtl : contient du RTL SystemVerilog synthétisable.
• sim : contient des scripts qui configurent l’environnement de simulation pour les tests.
• tests : contient le code source d’un banc de test basé sur UVM, utilisant Cocotb pour valider l’accélérateur en simulation.
• utils : contient des paquets et scripts Python supplémentaires utilisés dans le projet, créés par l’auteur pour l’aide au développement et les utilitaires généraux.

Avis de GN⁺

• Cet article présente une avancée innovante dans l’architecture matérielle ML, en particulier un nouvel algorithme et une nouvelle architecture qui réduisent les multiplications tout en conservant les performances. Il s’agit d’un progrès important susceptible d’améliorer fortement l’efficacité des calculs ML.
• L’algorithme FFIP ajoute une nouvelle dimension à la conception des accélérateurs ML existants et propose une manière d’utiliser les ressources matérielles plus efficacement. C’est particulièrement important dans les environnements informatiques modernes où l’efficacité énergétique et le coût sont des critères majeurs.
• Toutefois, pour que cette technologie soit largement adoptée, il faut tenir compte de sa compatibilité avec les accélérateurs ML existants, de la compréhension de cette nouvelle architecture par les développeurs, ainsi que des questions de performance et de coût lors d’une implémentation sur du matériel réel.
• Parmi les autres projets ou produits offrant des fonctions similaires, on peut citer le TPU (Tensor Processing Unit) de Google ou les cœurs CUDA de NVIDIA, déjà validés par le marché comme solutions d’accélération ML.
• Lorsqu’on adopte une nouvelle technologie ou un nouvel open source, il faut considérer la compatibilité avec les systèmes existants, l’augmentation éventuelle des coûts par rapport aux gains de performance, ainsi que la complexité du développement et de la maintenance. Les avantages de FFIP résident dans l’augmentation du débit et de l’efficacité de calcul, tandis que ses inconvénients potentiels incluent la courbe d’apprentissage pour les développeurs et le coût initial d’implémentation.

[GN⁺]

Discussion Hacker News

• Cette technique semble intéressante, mais je me demande pourquoi elle n’a pas déjà été implémentée dans des accélérateurs : est-ce simplement un algorithme oublié, ou bien y a-t-il un coût ou d’autres implications pour la construction de tels accélérateurs ?
• Cet article parle de la synthèse de pipelines de multiplication matricielle en matériel, ce qui pourrait être utile sur du matériel comme les FPGA ou les ASIC. Sur CPU ou GPU, multiplication et addition prennent généralement le même temps, mais les unités de multiplication occupent davantage de transistors ; réduire la complexité du circuit peut donc améliorer la vitesse et le débit parallèle, tout en réduisant la consommation électrique et la complexité du routage.
• Une autre façon d’éliminer les multiplications dans la multiplication matricielle consiste à utiliser différents semirings. Par exemple, le Tropical Semiring utilise l’addition à la place de la multiplication, et le minimum (ou le maximum) à la place de l’addition. Cela reste une multiplication matricielle, mais avec des opérations binaires remplacées. Les recherches dans le domaine de l’algèbre tropicale sont utilisées pour les problèmes d’optimisation et l’optimisation des réseaux de neurones, et le domaine est actuellement très actif et riche.
• L’utilisation du Log Semiring est également un moyen efficace d’éliminer les multiplications. Quand il faut multiplier des chaînes de probabilités (par exemple dans les chaînes de Markov), les nombres deviennent si petits que les flottants perdent en précision. En passant les nombres à l’échelle logarithmique, les multiplications deviennent des additions, et les additions deviennent x + log1p(exp(y - x)).
• Comme le fait de décider s’il faut utiliser une multiplication ou une addition peut être plus lent que d’utiliser simplement une multiplication, il est surprenant que cette méthode fonctionne réellement, surtout quand une grande quantité de travail est effectuée en parallèle.
• Le fait que ce procédé ait été inventé en 1968 et n’ait pas été utilisé à cette fin jusqu’à aujourd’hui est vraiment très intéressant.
• J’ai essayé un concept similaire en 2018, mais toutes mes candidatures en doctorat ont été rejetées, alors j’ai abandonné. Le concept ici essaie de dupliquer la rétropropagation dans un réseau externe, en affirmant que c’est probablement ce que fait réellement le cerveau.
• Si la théorie mathématique des algorithmes sous-cubiques pour la multiplication matricielle vous intéresse, vous pouvez commencer ici. On conjecture qu’il existe un nombre ( n ) tel que toutes les matrices ( n \times n ) puissent être multipliées en ( O(n^{2+j}) ) étapes (il est désormais démontré que ( 2+j = w = 2.3728596 ), soit ( j > 0.3728596 )).
• Ce readme explique très mal en quoi consistent les améliorations ni comment réduire de moitié le nombre de multiplications. Le temps d’exécution en Big O n’est pas clair, pas plus que le fait de savoir si cela change la meilleure borne connue. Les diagrammes sont confus et n’expliquent pas pourquoi cette approche est rapide ni en quoi elle est bonne. Résultat : je n’ai même pas envie de cliquer sur le PDF. Pour renforcer la crédibilité du projet, il faudrait envisager une explication honnête et claire, avec des illustrations, de ce qui se passe réellement.