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

Le circuit électronique qui réalise cette opération est appelé « multiplieur-accumulateur » ; 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 :

$\ a\leftarrow a+(b\times c)$

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, et le premier à exploiter ce circuit pour effectuer une division (en utilisant astucieusement le développement en série de (1+x)⁻¹). 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.

En virgule flottante

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 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.

Le multiplieur-accumulateur à arrondi unique (FMA ou fmadd) 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 : si l'on évalue, par exemple, l'expression x² − y² 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.

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.

Portabilité

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 ; 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.

Annexes

Articles connexes

• Informatique