Fonctionnement d'un ordinateur/Les circuits pour la multiplication et la division
Nous allons maintenant aborder un circuit appelé le multiplieur, qui multiplie deux opérandes. La 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 vraiment très simple en binaire, jugez plutôt !
- 0 × 0 = 0.
- 0 × 1 = 0.
- 1 × 0 = 0.
- 1 × 1 = 1.
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.
La multiplication non-signée modifier
Nous allons d'abord commencer par les multiplieurs qui font de la multiplication non-signée.
Les multiplieurs à base d’additionneur multi-opérandes non-itératif modifier
Une première solution calcule tous les produits partiels en parallèle, en même temps, avant de les additionner avec un additionneur multi-opérandes non-itératif, composé d'additionneurs carry-save. C'est une solution simple, qui utilise beaucoup de circuits, mais est très rapide. C'est la solution utilisée dans les processeurs haute performance moderne, dans presque tous les processeurs grand public, depuis plusieurs décennies.
Les multiplieurs itératifs modifier
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 diviser pour régner modifier
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 modifier
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 modifier
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 :
| Signe du multiplicande | Signe du multiplieur | Signe du résultat |
|---|---|---|
| + | + | + |
| - | + | - |
| + | - | - |
| - | - | + |
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 modifier
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 modifier
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 modifier
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 modifier
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 modifier
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.
- Le résultat est négatif : cela signifie que le reste est plus petit que le diviseur et qu'on aurait pas du soustraire. Vu que notre soustraction a été effectuée par erreur, on doit remettre le reste tel qu'il était. Ce qui est fait en effectuant une addition. Il faut aussi mettre le bit de poids faible du quotient à zéro et le décaler d'un rang vers la gauche.
- Le résultat est positif : dans ce cas, on met le bit de poids faible du quotient à 1 avant de le décaler, sans compter qu'il faut décaler le reste partiel pour mettre le diviseur à la bonne place (sous le reste partiel) lors des soustractions.
Et on continue ainsi de suite jusqu'à ce que le reste partiel soit inférieur au diviseur.
La division sans restauration modifier
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 modifier
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 !