Multiplieur-accumulateur
En programmation, à l'origine en traitement numérique du signal, l'opération combinée multiply–accumulate (MAC) ou multiply-add (MAD) est une instruction-machine qui calcule le produit de deux nombres et agrège le résultat au contenu d'un accumulateur.
Description
[modifier | modifier le code]Le circuit électronique qui réalise cette opération est appelé « multiplieur-accumulateur[1],[2] » ; l'opération elle-même est souvent abrégée en MAC ou « opération MAC. » L'opération MAC se déroule dans l'accumulateur du microprocesseur :
Le circuit, lorsqu'il traite des nombres en virgule flottante, peut générer deux arrondis consécutifs (c'est le plus souvent le cas en traitement numérique du signal), ou un seul : dans ce dernier cas, on trouve la mention fused multiply–add (FMA) ou fused multiply–accumulate (FMAC).
Les ordinateurs comportent souvent un circuit MAC propre, combinaison d'un multiplieur programmé avec des portes logiques, d'un circuit additionneur et d'un registre où le résultat est stocké. Le registre est lu par l'additionneur, de sorte qu'à chaque cycle d'horloge, la sortie du multiplieur est ajoutée au registre. Les circuits multiplieurs utilisent généralement un grand nombre de portes logiques, mais ils sont beaucoup plus rapides que l'algorithme de multiplication russe typique des premiers ordinateurs. Selon B. Randell, l'Irlandais Percy Ludgate (1883–1922) aurait été le premier (1909) à réaliser ce genre de circuit MAC pour sa version de la Machine analytique[3], et le premier à exploiter ce circuit pour effectuer une division (en utilisant astucieusement le développement en série de (1+x)−1). Il est en tous cas certain que les premiers processeurs modernes équipés d'unités MA étaient des portes logiques pour le traitement numérique du signal : c'est cette technique qui est la plus courante dans les microprocesseurs généralistes actuels[4],[5],[6],[7].
En virgule flottante
[modifier | modifier le code]Lorsqu'elle opère sur des entiers, l'opération peut évidemment être exécutée exactement (modulo une puissance de deux) ; cependant, avec les nombres en virgule flottante, la précision mathématique est par nature limitée à la taille de la mantisse. En conséquence, les opérations en virgule flottante sont en général non-associatives[8] et non-distributives.
Il importe donc bien de savoir si l'opération multiply–add comporte deux arrondis successifs ou un seul (c'est-à-dire si l'on a affaire à un fused multiply–add). La norme IEEE 754-2008 spécifie qu'elle ne devrait comporter qu'un arrondi final, pour une meilleure précision du résultat[9].
Le multiplieur-accumulateur à arrondi unique (FMA ou fmadd)[10] est une opération en virgule flottante combinée : au lieu de calculer le produit b × c, de l'arrondir à N bits significatifs, d'additionner le résultat à a, et enfin d'arrondir le résultat, elle calcule l'expression entière a + (b × c) en précision maximum avant d'arrondir le résultat final à N bits.
Un circuit FMA rapide peut ainsi améliorer la précision de toutes sortes d'opérations courantes en calcul scientifique :
- produit scalaire : certaines machines permettent même de chaîner en pipe-line plusieurs instructions multiplieur-accumulateur arrondies en une seule opération, par exemple en exécutant un produit scalaire à 4 facteurs distribués simultanément sur deux registres SIMD de 128 bits :
a0×b0 + a1×b1 + a2×b2 + a3×b3
; - multiplication de matrices ;
- évaluation des polynômes (notamment par le schéma de Horner) ;
- méthode de Newton pour l'évaluation des fonctions (en évaluant l'inverse de ladite fonction) ;
- produit de convolution et réseau de neurones artificiels ;
- multiplications en arithmétique double-double.
Toutefois, l'informaticien canadien William Kahan a montré qu'elle était source de problèmes lorsqu'on l'utilisait inconsidérément[11] : si l'on évalue, par exemple, l'expression x2 − y2 en ordonnant les calculs selon ((x × x) − y × y) (pour reprendre l'exemple de Kahan, qui suppose ici que les parenthèses forcent le compilateur à arrondir le terme (x × x) une fois calculé), le résultat sera négatif même quand x = y, à cause de la perte de chiffres significatifs dans la première multiplication. Ce genre d'erreur n'est pas anodin si, par exemple, on veut ensuite calculer la racine carrée de ce résultat.
Le câblage du FMA sur un microprocesseur peut même donner une opération plus rapide que la multiplication suivie d'une addition ; cependant, les standards industriels fondés sur l'instruction d'origine du RS/6000 d'IBM imposent que l'addition soit exécutée impérativement avec une précision de 2N-bits[12].
Un autre avantage de cette instruction est qu'elle permet une programmation efficace de la division euclidienne et de l'algorithme d'extraction de racine carrée, évitant ainsi d'introduire des circuits arithmétiques spécifiques à ces opérations[13].
Portabilité
[modifier | modifier le code]L'opération FMA est reconnue par la norme IEEE 754-2008. Elle a été introduite en 1990 dans le processeur POWER1 d'IBM, et de plus en plus de processeurs l'implémentent.
L'instruction POLY
des VAX était utilisée pour évaluer les polynômes par le schéma de Horner, qui les ramenait à une succession raisonnée d'opérations de ce genre. Le descriptif du constructeur DEC ne précisait pas si l'opération multiplier-accumuler ne comportait qu'une instruction FMA[14] ; toujours est-il que cette instruction a fait partie de la bibliothèque scientifique des VAX depuis leur version 11/780 de 1977.
Le langage C, depuis la norme ISO C99, supporte explicitement l'opération FMA, via la fonction de bibliothèque standard fma()
; le compilateur peut remplacer un tel appel par une instruction du processeur lorsque celui-ci supporte le FMA. Alternativement, la règle de contraction des expressions flottantes (contrôlable par le pragma standard FP_CONTRACT
) permet au compilateur de remplacer une multiplication suivie d'une addition par un FMA, mais un tel remplacement est toujours optionnel.
Notes et références
[modifier | modifier le code]- Marcel Lapointe, Huynh Huu Tué et Paul Fortier, « Nouvelle méthode de conception de circuits très rapides des filtres numériques linéaires invariants », Traitement du Signal, vol. 8, no 4, , p. 237-257
- « Systèmes électroniques numériques : Problème sur les MAC », sur Telecom ParisTech, (consulté le )
- (en) B. Randell, « The Feasibility of Ludgate's Analytical Machine », The Computer Journal, vol. 14, no 3, , p. 317–326 (DOI 10.1093/comjnl/14.3.317, lire en ligne)
- (en) Pavel Lyakhov, Maria Valoueva, Georgii Valouev et Nikolaï Nagornov, « A Method of Increasing Digital Filter Performance Based on Truncated Multiply-Accumulate Units », Applied Sciences, vol. 10, no 24, , p. 9052 (DOI 10.3390/app10249052)
- Tung Thanh Hoang, M. Sjalander et P. Larsson-Edefors, « Double Throughput Multiply-Accumulate unit for FlexCore processor enhancements », 2009 IEEE International Symposium on Parallel Distributed Processing, , p. 1–7 (ISBN 978-1-4244-3751-1, DOI 10.1109/IPDPS.2009.5161212, S2CID 14535090)
- (en) Jongsung Kang et Taewhan Kim, « PV-MAC: Multiply-and-accumulate unit structure exploiting precision variability in on-device convolutional neural networks », Integration, vol. 71, , p. 76–85 (ISSN 0167-9260, DOI 10.1016/j.vlsi.2019.11.003)
- « mad - ps » (consulté le )
- Michèle Pichat, Contribution à l’étude des erreurs d’arrondi en arithmétique à virgule flottante.Modélisation et simulation. Institut National Polytechnique de Grenoble - INPG; Université Joseph-Fourier, Grenoble, (lire en ligne), p. I.
- Nathan Whitehead et Alex Fit-Florea, « Precision & Performance: Floating Point and IEEE 754 Compliance for NVIDIA GPUs », nvidia, (consulté le )
- « AIX Language Reference: fmadd instrs », sur IBM Knowledge Center
- William Kahan, « IEEE Standard 754 for Binary Floating-Point Arithmetic »,
- Eric Quinnell, Floating-Point Fused Multiply–Add Architectures, université du Texas, (lire en ligne)
- Peter Markstein, « Software Division and Square Root Using Goldschmidt's Algorithms », sur 6th Conference on Real Numbers and Computers, (CiteSeerx 10.1.1.85.9648)
- « VAX instruction of the week: POLY » (version du sur Internet Archive)