Nous allons maintenant aborder les circuits qui effectuent une multiplication. Ma multiplication se fait en binaire de la même façon qu'on a appris à le faire en primaire, si ce n'est que la table de multiplication est modifiée. Pour commencer, petite précision de vocabulaire : une multiplication s'effectue sur deux nombres, le "multiplicande" et le "multiplicateur". Une multiplication génère des résultats temporaires, chacun provenant de la multiplication du multiplicande par un chiffre du multiplicateur : ces résultats temporaires sont appelés des produits partiels. Multiplier deux nombres en binaire demande de générer les produits partiels, de les décaler, avant de les additionner.
Pour multiplier un nombre par un bit du multiplicateur, rien de plus simple : les tables de multiplication sont vraiment très simples en binaire, jugez plutôt !
L'addition multiopérande.
Avant de voir comment multiplier deux nombres, nous allons voir les circuits qui s'occupent d'additionner entre eux les produits partiels. Il s'agit d'additionneurs spécialisés, capables d'additionner plus de deux nombres en même temps. Il existe de nombreux types de circuits capables d'effectuer cette addition multiopérande, construits à partir d'additionneurs simples. Précisons que l'addition multi-opérande a beaucoup été étudiée par les chercheurs et ingénieurs, et que les solutions pour l'accélérer ne manquent pas. L'une d'entre elle se base sur une nouvelle représentation des nombres, particulièrement adaptée aux additions successives : la représentation "carry-save". Avec l'addition "carry-save", on ne propage pas les retenues. L'addition de trois opérandes en "carry-save" fournit deux résultats : un résultat obtenu en effectuant l'addition sans tenir compte des retenues, et un autre composé uniquement des retenues. Par exemple, 1000 + 1010 + 1110 donne 1010 pour les retenues, et 1100 pour la somme sans retenue.
Ainsi, additionner trois nombres devient très facile : il suffit d'additionner les trois nombres avec un additionneur "carry-save", et d'additionner les deux résultats avec un additionneur normal. Le même principe peut s'appliquer avec plus de trois nombres : il suffit juste d'assembler plusieurs additionneurs "carry-save" les uns à la suite des autres.
L'additionneur multi-opérandes itératif.
Le plus simple des additionneur multi-opérandes somme les opérandes une par une, le résultat temporaire étant stocké dans le registre. Il est composé d'un additionneur entier, tel que vu précédemment, couplé à un registre. Ce circuit est appelé un additionneur multi-opérande itératif.
Notons qu'il en existe une version naïve, où le résultat temporaire est codée normalement, et une autre qui utilise la représentation "carry-save". Dans cette dernière, il faut utiliser deux registres : un pour le résultat sans retenues, et un autre pour les retenues. À chaque cycle, l'additionneur additionne une nouvelle opérande, le résultat temporaire sans retenu et les retenues. Le résultat final se calcule en sommant les deux registres temporaires en fin de calcul. Évidemment, cela demande d'ajouter des circuits annexes autour pour gérer le tout.
Le chainage d'additionneurs.
La solution la plus simple consiste à additionner les nombres les uns après les autres, soit avec un circuit séquentiel, soit en enchainant des additionneurs les uns à la suite des autre. Mais diverses optimisations sont possibles. La solution la plus simple consiste à enchainer des additionneurs en série, les uns après les autres. Mais cela n'est pas la meilleure solution. Le mieux est de les organiser en arbre pour effectuer certaines additions en parallèle d'autres : on obtient alors un arbre d'additionneur.
Il est possible d'utiliser ces additionneurs carry-save dans un arbre d'additionneurs. En faisant cela, on peut se retrouver avec plusieurs formes pour l'arbre, qui donnent respectivement des additionneurs en arbres de Wallace, ou des arbres Dadda.
Les arbres les plus simples à construire sont les arbres de Wallace. Le principe est d'ajouter des couches d'additionneurs carry-save, et de capturer un maximum de nombres lors de l'ajout de chaque couche. On commence par additionner un maximum de nombres avec des additionneurs carry-save. Pour additionner n nombres, on commence par utiliser n/3 additionneurs carry-save. Si jamais n n'est pas divisible par 3, on laisse tranquille les 1 ou 2 nombres restants. On se retrouve ainsi avec une couche d'additionneurs carry-save. On répète cette étape sur les sorties des additionneurs ainsi ajoutés : on rajoute une nouvelle couche. Il suffit de répéter cette étape jusqu'à ce qu'il ne reste plus que deux résultats : on se retrouve avec une couche finale composée d'un seul additionneur carry-save. Là, on rajoute un additionneur normal, pour additionner retenues et sommes.
Les arbres de Dadda sont plus difficiles à comprendre. Contrairement à l'arbre de Wallace qui cherche à réduire la hauteur de l'arbre le plus vite possible, l'arbre de Dadda cherche à diminuer le nombre d'additionneurs carry-save utilisés. Pour cela, l'arbre de Dadda se base sur un principe mathématique simple : un additionneur carry-save peut additionner trois nombres, pas plus. Cela implique que l'utilisation d'un arbre de Wallace gaspille des additionneurs si on additionne n nombres, avec n non multiple de trois. L'arbre de Dadda résout ce problème d'une manière simple :
Et on répète cette étape d'ajout de couche jusqu'à ce qu'il ne reste plus que deux résultats : on se retrouve avec une couche finale composée d'un seul additionneur carry-save. Là, on rajoute un additionneur normal, pour additionner retenues et sommes.
La multiplication par une constante.
Passons maintenant aux circuits de multiplication proprement dit. Avant de voir les circuits capables de multiplier deux opérandes, nous allons voir un circuit qui multiplie une opérande par une constante choisie à l'avance. La multiplication par une constante est une opération assez simple à implémenter. On a vu qu'il est possible de remplacer la multiplication par une puissance de deux par un simple décalage. Pour rappel, un décalage vers la gauche de formula_1 rangs est équivalent à une multiplication par formula_2. Attention toutefois : cela ne marche que pour des entiers non-signés et/ou positifs, mais pas pour des entiers négatifs. Ce qui va suivre se baser sur ce principe, même si nous allons aborder la multiplication par autre chose qu'une puissance de deux. Aussi bizarre que cela puisse paraitre, il y a deux méthodes pour cela. Suivant la situation, l'une d'entre elle sera plus rapide que l'autre : tout dépend du nombre de bits à 1 dans la constante.
Décaler et additionner.
Comme vous le savez, tout nombre entier est une somme de multiple de puissance de deux. C'est d'ailleurs le principe qui est derrière le binaire. Dans ce cas, multiplier par une puissance, c'est multiplier par une somme de puissance de deux. Avec quelques manipulations algébriques simple, cette multiplication peut se transformer en une somme de multiplication par une puissance de deux. Supposons que je veuille effectuer une multiplication entre un nombre A, et une constante B. Il est évident que B est une somme de puissances de deux. Dans ce cas, je peux remplacer B par la somme de puissance de deux qui correspond. Dans ce qui va suivre, nous allons prendre B = 13. Pour rappel, formula_3 :
Comme on le sait tous, la multiplication est distributive. J'utilise cette propriété sur l'équation du dessus, et je trouve :
Dans cette expression, on a donc une somme, qui additionne quelques termes. Ces termes sont tous des multiplications par une puissance de deux. On peut les remplacer par un décalage vers la gauche.
Ainsi, la multiplication par 5 peut se remplacer en un décalage à gauche de 2 rangs, et une addition.
Le principe reste le même pour toute multiplication par une constante : en décomposant la constante en puissance de deux, et avec quelques calculs, on peut transformer une multiplication par une constante en série de décalages et d'additions. Le nombre de décalages effectué est égal au nombre de bits à 1 dans la constante (sa population count). Le nombre d'addition est presque identique. Si la constante contient donc trop de bits à 1, il se peut que le nombre de décalage et d'addition soit trop important : une multiplication peut être plus rapide. Cette technique ne marche donc que pour les nombres ayant une population count faible : 2-3 bits, parfois plus sur les architectures ayant une multiplication particulièrement lente. Mais pas plus.
Décaler et soustraire.
Dans le cas où un nombre contient beaucoup de bits à 1, il existe une seconde méthode. Elle se base sur un principe légèrement différent, mais assez similaire à celui utilisé dans la méthode précédente. Comme vous le savez, un nombre entier peut s'écrire sous la forme d'une somme de puissance de deux. Par exemple, formula_7. Ceci dit, 5 peut aussi s'écrire sous une autre forme. Si on remarque bien, formula_8. Dans cette expression, 8 est une puissance de 2, et 3 est un nombre comme un autre. Si on réfléchit bien, tout nombre entier peut s'écrire sous la forme formula_9.
Reprenons notre exemple avec le 5.
Dans cette expression, on peut remplacer chaque nombre par son expression en binaire. En clair, on le remplace par la somme de puissances de deux qui correspond.
Maintenant, supposons que l'on veuille multiplier un nombre A par 5. On peut alors remplacer 5 par l'expression avec décalages et soustractions :
En se rappelant que la multiplication est distributive, on obtient :
Dans cette expression, on peut alors remplacer les multiplication par des puissances de deux par des décalages à gauche :
Comme on le voit, cette expression ne contient que des décalages et des soustractions. Et le principe est le même pour tout entier. Il suffit d'écrire la constante comme une puissance de deux à laquelle on aurait soustrait ce qu'il faut. Pour cela, il suffit de prendre la puissance de deux immédiatement supérieure à notre constante : cela simplifie les calculs et diminue le nombre de soustractions.
La multiplication non-signée.
Nous allons maintenant aborder un circuit appelé le multiplieur, qui multiplie deux opérandes. Pour l'implémenter, nous avons besoin d'un circuit qui est capables de multiplier deux bits, ce qui n'était pas le cas pour le circuit précédent. La table de multiplication est modifiée. Pour multiplier un nombre par un bit du multiplicateur, rien de plus simple : les tables de multiplication sont vraiment très simples en binaire, jugez plutôt !
Cette table de vérité est celle d'une porte ET. Ainsi, notre circuit est donc très simple : il suffit d'effectuer un ET entre les bits du multiplicande, et le bit du multiplicateur adéquat. Il reste ensuite à faire un décalage (et encore, on peut s'en passer avec quelques optimisations), et le tour est joué. Et pour cela, les manières de faire sont nombreuses.
Les multiplieurs itératifs.
Les multiplieurs les plus simples génèrent les produits partiels les uns après les autres, et les additionnent au fur et à mesure. Le multiplicateur et le multiplicande sont mémorisés dans des registres. Le reste du circuit est composé d'un circuit de génération des produits partiels, suivi d'un additionneur multiopérande itératif. La multiplication est finie quand tous les bits du multiplicateur ont étés traités (ce qui peut se détermine avec un compteur).
Il existe plusieurs multiplieurs itératifs, qui différent par la façon dont ils génèrent le produit partiel : certains traitent les bits du multiplicateur de droite à gauche, les autres dans le sens inverse. Dans les deux cas, on décale le multiplicateur d'un cran à chaque cycle, et on prend son bit de poids faible. Pour cela, on stocke le multiplicateur dans un registre à décalage.
Voici comment se déroule une multiplication avec un multiplieur qui fait le calcul de droite à gauche, qui commence par les bits de poids faible du multiplicateur :
On peut remarquer une chose assez intéressante : quand le produit partiel est nul, le circuit fait quand même l'addition. Cela arrive quand le bit du multiplicateur qui génère le produit partiel est 0 : le produit partiel est naturellement nul. Mais si le produit partiel est nul, pourquoi l'additionner ? Une petite optimisation permet d'éviter cela : si le bit du multiplicateur est nul, on peut se passer de l'addition et ne faire que les décalages. Cela demande de rajouter quelques circuits.
On peut encore optimiser le circuit en utilisant des produits partiels sur n bits. Pour cela, on fait le calcul en commençant par les bits de poids fort du multiplicateur : on parcourt le multiplicateur de droite à gauche au lieu le faire de gauche à droite. L'astuce, c'est qu'on additionne le produit partiel avec les bits de poids fort du registre pour le résultat, et non les bits de poids faible. Le contenu du registre est décalé d'un cran à droite à chaque cycle, ce qui décale automatiquement les produits partiels comme il faut.
Il est même possible de ruser encore plus : on peut se passer du registre pour le multiplicateur. Il suffit d'initialiser les bits de poids faible du registre résultat avec le multiplicateur au démarrage de la multiplication. Le bit du multiplicateur choisi pour le calcul du produit partiel est simplement le bit de poids faible du résultat.
Il est possible d'optimiser les multiplieurs précédents en calculant et en additionnant plusieurs produits partiels à la fois. Il suffit d'un additionneur multi-opérande et de plusieurs circuits de génération de produits partiels. Toutefois, cette technique demande de prendre en compte plusieurs bits du multiplicateur à chaque cycle : le nombre de rangs à décaler augmente, sans compter que la génération du produit partiel est un peu plus complexe.
Les multiplieurs à base d’additionneur multi-opérandes non-itératif.
Une autre solution consiste à calculer tous les produits partiels en parallèle, en même temps, avant de les additionner avec un additionneur multi-opérandes non-itératif.
Dans sa version la plus simple, l'additionneur multi-opérandes utilisé est un additionneur séquentiel, composé d’additionneur deux-opérandes enchainés les uns à la suite des autres. Dans sa version la plus simple, on peut utiliser des additionneurs à propagation de retenue pour créer le multiplieur. Utiliser d'autres additionneurs ne donnerait que des gains en performance relativement faibles. On peut aussi enchainer des additionneurs carry-save à trois opérandes pour additionner les produits partiels, les performances étant alors marginalement meilleures.
Si on prend des additionneurs à propagation de retenue, le circuit devient le suivant :
Enchainer les additionneurs les uns à la suite des autres n'est cependant pas la meilleure solution. Le mieux est d'utiliser un additionneur multiopérande en arbre.
Si on prend des additionneurs "carry-save", le circuit devient le suivant :
Les multiplieurs diviser pour régner.
Il existe enfin un tout dernier type de multiplieurs : les multiplieurs diviser pour régner. Pour comprendre le principe, nous allons prendre un multiplieur qui multiplie deux nombres de 32 bits. Les deux opérandes A et B peuvent être décomposées en deux morceaux de 16 bits, qu'il suffit de multiplier entre eux pour obtenir les produits partiels voulus : une seule multiplication 32 bits se transforme en quatre multiplications d'opérandes de 16 bits. En clair, ces multiplieurs sont composés de multiplieurs qui travaillent sur des opérandes plus petites, associés à des additionneurs.
La multiplication de nombres signés.
Tous les circuits qu'on a vus plus haut sont capables de multiplier des nombres entiers positifs, mais on peut les adapter pour qu'ils fassent des calculs sur des entiers signés. Et la manière de faire la multiplication dépend de la représentation utilisée. Les nombres en signe-magnitude ne se multiplient pas de la même manière que ceux en complément à deux ou en représentation par excès. Dans ce qui va suivre, nous allons voir ce qu'il en est pour la représentation signe-magnitude et pour le complément à deux. La représentation par excès est volontairement mise de côté, car ce cas est assez compliqué à gérer et qu'il n'existe pas de solutions simples à ce problème. Cela explique le peu d'utilisation de cette représentation, qui est limitée aux cas où l'on sait qu'on ne fera que des additions/multiplications, le cas de l'exposant des nombres flottants en étant un cas particulier.
La multiplication en représentation signe-magnitude.
Pour les entiers en signe-valeur absolue, le calcul de la valeur absolue et du signe sont indépendants. Mathématiquement, la valeur absolue du résultat est le produit des valeurs absolues des opérandes. Quant au signe, on apprend dans les petites classes le tableau suivant :
En traduisant ce tableau en binaire, avec la convention + = 0 et - = 1, on trouve la table de vérité d'une porte XOR.
Pour résumer, il suffit de multiplier les valeurs absolues et de déduire le signe du résultat avec un vulgaire XOR entre les bits de signe des nombres à multiplier.
La multiplication signée en complément à deux.
Dans ce qui va suivre, nous allons nous intéresser à la multiplication signée en complément à deux.
Adapter les multiplieurs non-signés pour la multiplication signée.
Les multiplieurs vus plus haut fonctionnent parfaitement quand les deux opérandes ont le même signe, mais pas quand un des deux opérandes est négatif. Avec un multiplicande négatif, le produit partiel est censé être négatif. Mais dans les multiplieurs vus plus haut, les bits inconnus du produit partiel sont remplis avec des zéros, et donc positifs. Pour résoudre ce problème, il suffit d'utiliser une extension de signe sur les produits partiels. Pour cela, il faut faire en sorte que le décalage du résultat soit un décalage arithmétique. Pour traiter les multiplicateurs négatifs, on ne doit pas ajouter le produit partiel, mais le soustraire (l'explication du pourquoi est assez dure à comprendre, aussi je vous épargne les détails). L'additionneur doit donc être remplacé par un additionneur-soustracteur.
Les multiplieurs de Booth.
Il existe une autre façon, nettement plus élégante, inventée par un chercheur en cristallographie du nom de Booth : l'algorithme de Booth. Le principe de cet algorithme est que des suites de bits à 1 consécutives dans l'écriture binaire d'un nombre entier peuvent donner lieu à des simplifications. Si vous vous rappelez, les nombres de la forme 01111…111 sont des nombres qui valent 2n − 1. Donc, X × (2^n − 1) = (X × 2^n) − X. Cela se calcule avec un décalage (multiplication par 2^n) et une soustraction. Ce principe peut s'appliquer aux suites de 1 consécutifs dans un nombre entier, avec quelques modifications. Prenons un nombre composé d'une suite de 1 qui commence au n-ième bit, et qui termine au X-ième bit : celle-ci forme un nombre qui vaut 2^n − 2^n−x. Par exemple, 0011 1100 = 0011 1111 − 0000 0011, ce qui donne (2^7 − 1) − (2^2 − 1). Au lieu de faire des séries d'additions de produits partiels et de décalages, on peut remplacer le tout par des décalages et des soustractions.
C'est le principe qui se cache derrière l’algorithme de Booth : il regarde le bit du multiplicateur à traiter et celui qui précède, pour déterminer s'il faut soustraire, additionner, ou ne rien faire. Si les deux bits valent zéro, alors pas besoin de soustraire : le produit partiel vaut zéro. Si les deux bits valent 1, alors c'est que l'on est au beau milieu d'une suite de 1 consécutifs, et qu'il n'y a pas besoin de soustraire. Par contre, si ces deux bits valent 01 ou 10, alors on est au bord d'une suite de 1 consécutifs, et l'on doit soustraire ou additionner. Si les deux bits valent 10 alors c'est qu'on est au début d'une suite de 1 consécutifs : on doit soustraire le multiplicande multiplié par 2^n-x. Si les deux bits valent 01, alors on est à la fin d'une suite de bits, et on doit additionner le multiplicande multiplié par 2^n. On peut remarquer que si le registre utilisé pour le résultat décale vers la droite, il n'y a pas besoin de faire la multiplication par la puissance de deux : se contenter d’additionner ou de soustraire le multiplicande suffit.
Reste qu'il y a un problème pour le bit de poids faible : quel est le bit précédent ? Pour cela, le multiplicateur est stocké dans un registre qui contient un bit de plus qu'il n'en faut. On remarque que pour obtenir un bon résultat, ce bit précédent doit mis à 0. Le multiplicateur est placé dans les bits de poids fort, tandis que le bit de poids faible est mis à zéro. Cet algorithme gère les signes convenablement. Le cas où le multiplicande est négatif est géré par le fait que le registre du résultat subit un décalage arithmétique vers la droite à chaque cycle. La gestion du multiplicateur négatif est plus complexe à comprendre mathématiquement, mais je peux vous certifier que cet algorithme gère convenablement ce cas.
Les division signée et non-signée.
En binaire, l'opération de division ressemble beaucoup à l’opération de multiplication. L'algorithme le plus simple que l'on puisse créer pour exécuter une division consiste à faire la division exactement comme en décimal. Pour simplifier, la méthode de division est identique à celle de la multiplication, si ce n'est que les additions sont remplacées par des soustractions. Néanmoins, implémenter cet algorithme sous la forme de circuit est quelque peu compliqué. Il existe plusieurs méthodes de division matérielle, la première étant la division avec restauration, par laquelle nous allons commencer.
La division avec restauration.
Introduisons la division avec restauration par un exemple. Nous allons cherche à diviser 100011001111 (2255 en décimal) par 111 (7 en décimal). Pour commencer, nous allons commencer par sélectionner le bit de poids fort du dividende (le nombre qu'on veut diviser par le diviseur), et voir combien de fois on trouve le diviseur dans ce bit. Pour ce faire, il faut soustraire le diviseur à ce bit, et voir le signe du résultat. Si le résultat de cette soustraction est négatif, alors le diviseur est plus grand que ce qu'on a sélectionné dans notre dividende. On place alors un zéro dans le quotient. Dans notre exemple, cela fait zéro : on pose donc un zéro dans le quotient. Ensuite, on abaisse le bit juste à côté du bit qu'on vient de tester, et on recommence. On continue ainsi tant que le résultat de la soustraction obtenue est négatif. Quand le résultat de la soustraction n'est pas négatif, on met un 1 à la droite du quotient, et on recommence en partant du reste. Et on continue ainsi de suite.
Notre algorithme semble se dessiner peu à peu : on voir qu'on devra utiliser des décalages et des soustractions, ainsi que des comparaisons. L'implémentation de cet algorithme dans un circuit est super simple : il suffit de prendre trois registres : un pour conserver le "reste partiel" (ce qui reste une fois qu'on a soustrait le diviseur dans chaque étape), un pour le quotient, et un pour le diviseur. L'ensemble est secondé par un additionneur/soustracteur, et par un peu de logique combinatoire. Voici ce que cela donne sur un schéma (la logique combinatoire est omise).
L'algorithme de division se déroule assez simplement. Tout d'abord, on initialise les registres, avec le registre du reste partiel qui est initialisé avec le dividende. Ensuite, on soustrait le diviseur de ce "reste" et on stocke le résultat dans le registre qui stocke le reste. Deux cas de figure se présentent alors : le reste partiel est négatif ou positif. Dans les deux cas, on réussit trouver le signe du reste partiel en regardant simplement le bit de signe du résultat. Reste à savoir quoi faire.
Et on continue ainsi de suite jusqu'à ce que le reste partiel soit inférieur au diviseur.
La division sans restauration.
La méthode précédente a toutefois un léger défaut : on a besoin de remettre le reste comme il faut lorsqu'on a soustrait le diviseur du reste alors qu'on aurait pas du et que le résultat obtenu est négatif. On fait cela en rajoutant le diviseur au reste. Et il y a moyen de se passer de cette restauration du reste partiel à son état originel. On peut très bien continuer de calculer avec ce reste faux, pour ensuite modifier le quotient final obtenu de façon simple, pour obtenir le bon résultat. Il suffit simplement de multiplier le quotient par deux, et d'ajouter 1. Ça parait vraiment bizarre, mais c'est ainsi. Cette méthode consistant à ne pas restaurer le reste comme il faut et simplement bidouiller le quotient s'appelle la division sans restauration.
La division SRT.
On peut encore améliorer cette méthode en ne traitant pas notre dividende bit par bit, mais en le manipulant par groupe de deux, trois, quatre bits, voire plus encore. Ce principe est (en partie) à la base de l'algorithme de division SRT. C'est cette méthode qui est utilisée dans les circuits de notre processeur pour la division entière. Sur certains processeurs, le résultat de la division par un groupe 2,3,4... bits est accéléré par une petite mémoire qui précalcule certains résultats utiles. Bien sûr, il faut faire attention quand on remplit cette mémoire : si vous oubliez certaines possibilités ou que vous y mettez des résultats erronés, vous obtiendrez un quotient faux pour votre division. Et si vous croyez que les constructeurs de processeurs n'ont jamais fait cette erreur, vous vous trompez : cela arrive même aux meilleurs ! Intel en a d'ailleurs fait les frais sur le Pentium 1. L'unité en charge des divisions flottantes utilisait un algorithme similaire à celui vu au-dessus (les mantisses des nombres flottants étaient divisées ainsi), et la mémoire qui permettait de calculer les bits du quotient contenait quelques valeurs fausses. Résultat : certaines divisions donnaient des résultats incorrects !