Fonctionnement d'un ordinateur/Les circuits pour la multiplication et la division

Exemple de multiplication en binaire.

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 génération des produits partiels est assez simple. Sur le principe, la table de multiplication binaire est un simple ET logique. Générer un produit partiel demande donc, à minima, de faire un ET entre un bit du multiplicateur et le multiplicande. Le circuit pour cela est trivial.

La seconde étape est ensuite de décaler le résultat du ET pour tenir compte du poids du bit choisit. En effet, regarder le schéma de droite qui montre comment faire une multiplication en binaire. Vous voyez que c'est comme en décimal : chaque ligne correspond à un produit partiel, et chaque produit partiel est décalé d'un cran par rapport au précédent. Il faut donc ajouter de quoi faire ce décalage. Intuitivement, on se dit qu'il faut ajouter des circuits décaleurs, un pour chaque bit du multiplicateur. Ce ne sera pas toujours le cas, mais il y en aura parfois besoin.

La multiplication non-signée

Nous allons d'abord commencer par les multiplieurs qui font de la multiplication non-signée. La multiplication de deux nombres signés est en effet un peu particulière et demande des techniques particulières, là où la multiplication non-signée est beaucoup plus simple.

Les multiplieurs non-itératifs

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.

Multiplieur en arbre.

Notons que la génération des produits partiels se passe de circuits décaleur, elle se contente d'utiliser un paquet de portes ET. Le câblage permet de câbler les sorties des portes ET aux bonnes entrées de l'additionneur, ce qui permet de se passer de circuits décaleurs.

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

Circuit itératif de multiplication sans optimisation.

Rappelons que l'additionneur multiopérande itératif est composé d'un additionneur normal, à deux opérandes, couplé à un registre appelé le registre accumulateur. Il mémorise le résultat temporaire de l'addition des produits partiels. A la fin de la multiplication, une fois tous les produits partiels additionnés, il contient le résultat.

Circuit itératif de multiplication sans optimisation, détaillée.

Il existe plusieurs multiplieurs itératifs, qui différent par la façon dont ils génèrent le produit partiel. Dans tous les cas, la multiplication multiplie un bit du multiplicateur par le multiplicande. La différence tient dans le sens de parcours : certains traitent les bits du multiplicateur de droite à gauche, les autres dans le sens inverse. Dans le premier cas, le multiplieur subit un décalage à droite et il est traité de droite à gauche, des bits de poids faible vers les bits de poids fort. Dans le second cas, il subit un décalage à gauche et est traité de gauche à droite, des bits de poids fort vers les bits de poids faible.

Pour cela, on stocke le multiplieur dans un registre à décalage, ce qui fait qu'un bit sort à chaque cycle. Et c'est ce bit qui sort du registre à décalage qui est utilisé pour générer le produit partiel. 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 :

Fonctionnement multiplieur.

Il faut noter que le contenu du registre accumulateur est aussi décalé d'un cran vers la gauche ou la droite à chaque cycle, pour tenir compte du poids des bits multipliés. Pour comprendre pourquoi, rappelez-vous que dans une multiplication, en décimal ou binaire, les produits partiels ne sont pas alignés sur une même colonne : ils sont décalés d'un cran par rapport au précédent. Vu qu'on additionne les produits partiels un par un, on doit donc faire un décalage d'un cran entre chaque addition. En théorie, le décalage doit être réalisé à la génération des produits partiels, par un circuit décaleur. Mais cette solution demande d'utiliser des produits partiels qui sont deux fois plus longs que le multiplicande/multiplicateur.

Une solution alternative, beaucoup plus simple, effectue ce décalage directement dans le registre accumulateur. En effet, chaque produit partiel est décalé d'un cran vers la gauche par rapport au précédent, d'un cran vers la droite par rapport au précédent. On peut donc faire le décalage entre chaque addition. Le registre accumulateur est donc un registre à décalage ! Ce qui n'est pas le cas sur un additionneur multiopérande itératif normal. Avec cette technique, les produits partiels générés ont la même taille que le multiplicateur, le même nombre de bits. On économise pas mal de circuit : pas besoin de circuits décaleur, moins d'entrées sur l'additionneur.

Le sens de décalage du multiplicateur et du registre accumulateur sont identiques. Si on effectue la multiplication de droite à gauche, en commençant par les bits de poids faible, alors le registre accumulateur est aussi décalé vers la droite. Cela permet au produit partiel suivant d'être placé un cran à gauche du précédent. A l'inverse, si on effectue la multiplication en commençant par les bits de poids fort, alors on décale le registre accumulateur vers la gauche, histoire de placer un produit partiel à la droite du précédent.

Les deux solutions ne sont pas strictement équivalentes, car la seconde à un avantage. Prenons un multiplicateur de N bits. Avec une multiplication qui commence par les bits de poids fort, l'addition donne un résultat sur 2N bits, la totalité d'entre eux étant utiles. En allant dans l'autre sens, l'addition donne un résultat qui a N bits effectifs, à savoir que le reste sont systèmatiquement à zéro et sont en réalité pris en charge par le décalage de l'accumulateur. Commencer par les bits de poids faible permet d'utiliser des produits partiels sur n bits, donc d'utiliser un additionneur sur N bits. Les produits partiels aussi sont de N bits. Le registre accumulateur reste de 2N bits, mais seuls les N bits de poids fort sont utilisés dans l'addition.

Circuit itératif de multiplication, avec optimisation de la taille des produits partiels.

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

Multiplieur partagé

Les optimisations liées aux opérandes

les circuits plus incorporent certaines optimisations, notamment concernant le sens de parcours du multiplieur, afin de rendre les calculs plus rapides. Mais d'autres optimisations permettent de gagner encore plus en performance, mais qui dépendent de la valeur des opérandes. Avec ces optimisations, la multiplication sera plus ou moins rapide suivant l'opérande : certaines opérandes donneront une multiplication en 32 cycles, d'autres en 12 cycles, d'autres en 20, etc. L'idée est de zapper certains cycles où on sait que le multiplicande sera multiplié par zéro, ce qui arrive quand le bit du multiplieur vaut 0. En théorie, on pourrait faire cela à chaque cycle, mais cela n'a pas d'intérêt, car contourner l'additionneur n'a pas grand intérêt. Mais on peut cependant faire quelques optimisations.

La première optimisation consiste à terminer l'opération une fois que tous les calculs nécessaires ont été faits, c'est à dire une fois que le multiplieur décalé atteint 0. Dans ce cas, on a multiplié tous les bits à 1 du multiplieur, tous les produits partiels restants valent 0, pas besoin de les calculer. L'optimisation ne marche cependant que si on commence les calculs à partir du bit de poids faible du multiplieur. Si on commence par les bits de poids fort, il faudra faire plusieurs décalages pour obtenir le bon résultat. Par exemple, si les N bits de poids faible su multiplieurs valent 0, alors il faudra décaler le résultat dans le registre accumulateur de N rangs vers la gauche.

Voyons maintenant une autre optimisation, qui va de pair avec l'optimisation précédente. Prenons d'abord une multiplication qui part du bit de poids fort, et décale le multiplieur vers la gauche. Elle fonctionne sur les opérandes dont les N bits de poids fort sont à 0. L'idée est de commencer la multiplication pour le premier bit du multiplieur à 1, et de zapper les 0 précédents en décalant le multiplier. Ce faisant, on utilise un circuit qui effectue l'opération adéquate, à savoir l'opération de count leading zeros, puis décale le multiplieur de ce nombre, ainsi que le reste partiel. La même optimisation s'applique si on commence la multiplication à partir du bit de poids faible, il faut alors effectuer l'opération count trailing zeros pour savoir de combien décaler.

Opérations Find First Set ; Find First Zero ; Find Highest Set (le logarithme binaire) ; Find Highest Zero ; Count Leading Zeros ; Count Trailing Zeros ; Count Leading Ones et Count Trailing Ones

Si on décale le multiplieur vers la droite, on ne doit gérer les 0 que dans les bits de poids fort. Pour gérer les bits de poids faible à 0, il suffit de tester si l'opérande est zéro, à savoir appliquer l'optimisation précédente. Les deux optimisations sont complémentaires, elles sont deux faces d'une même pièce.

Les multiplieurs en base 4, 8, 16

Avec les multiplieurs itératifs précédents, la multiplication se fait produit partiel par produit partiel. On ne tient compte que d'un seul bit du multiplieur, qui est multiplié avec le multiplicande, ce qui génère un produit partiel. À l'inverse, avec les multiplieurs basés sur un additionneur multiopérande non-itératif, on génère tous les produits partiels en même temps, pour les additionner tous en même temps (ou presque). Il existe cependant des multiplieurs intermédiaires, qui génèrent et additionnent plusieurs produits partiels à la fois, tout en restant des multiplieurs itératifs.

L'idée est qu'au lieu de faire la multiplication bit par bit pour le multiplicande, on prend deux bits du multiplicande, ou trois ou quatre. Concrètement, on génère deux, trois, quatre produits partiels en même temps et on les additionne d'un seul coup au résultat temporaire dans le registre. On parle alors de multiplieurs en base 4, 8, ou 16. Le multiplieur en base 4 génère deux produits partiels à la fois, celui en base 8 en génère 3, celui en base 16 en génère 4, etc.

Il existe plusieurs manières de fabriquer un multiplieur en base 4, 8, 16, etc. La première, la plus simple, utilise un multiplieur hybride, qui mélange un multiplieur itératif et un autre non-itératif. La seconde, plus complexe, modifie le circuit d'un multiplieur itératif en rajoutant des circuits annexes.

Les multiplieurs hybrides

Une solution, assez évidente, mélange l'usage d'additionneurs carry save et multiplieur itératif. L'idée est simple : on génère plusieurs produits partiels à la fois, on les additionne avec le registre accumulateur avec un additionneur multiopérande normal. En clair, on rajoute des circuits de génération des produits partiels et on remplace l'additionner normal par un additionneur multiopérande. Voici ce que cela donne quand on prend deux produits partiels à la fois :

Multiplieur en base 4

La seule difficulté est de prendre en compte les décalages entre produits partiels. Déjà, dans l'exemple avec deux produits partiels, vu qu'on traite deux bits à la fois, on doit décaler le registre accumulateur de deux rangs. De plus, les deux bits du multiplieur utilisés n'ont pas le même poids. Un des produits partiel doit être décalé d'un rang par rapport à l'autre. En théorie, on devrait user d'un circuit décaleur, mais on peut s'en passer avec des bidouilles de câblage. La même chose a lieu quand on génère trois produits partiels à la fois : l'un n'est pas décalé, le suivant l'est d'un rang, l'autre de trois rangs. Et ainsi de suite avec quatre produits partiels simultanés. Rien d'insurmontable en soi, cela ne fait que marginalement complexifier le circuit.

Il est possible d'optimiser le circuit en changeant son organisation. L'idée est de faire les additions de produits partiels en carry save uniquement, sans passer par un résultat temporaire en binaire. Pour cela, il faut déplacer l'additionneur normal après le registre. De plus, le registre accumulateur mémorise le résultat temporaire en carry save. Il est donc dupliqué, avec un registre pour les retenues, et l'autre pour la somme. Une fois que tous les produits partiels ont été additionnés, on traduit le résultat temporaire en carry save en binaire normal, avec l'additionneur normal.

Multiplieur itératif en base 4 optimisé.

Le design précédent peut être amélioré en tenant compte d'un détail portant sur le registre accumulateur. Il s'agit d'un registre synchrone, commandé par un signal d’horloge non-représenté dans les schémas précédents. Une implémentation de ce registre utilise des bascules dites master-slave, composées de deux bascules D non-synchrones à entrée Enable qui se suivent, comme nous l'avions vu dans le chapitre sur les circuits synchrones. Le registre synchrone est donc composé de deux registres non-synchrones qui se suivent. Avec ce type de registres, il est possible de modifier le multiplieur précédent de manière à doubler le nombre de produits partiels additionnés à chaque cycle d'horloge. L'idée est très simple : on insère un second additionneur carry save entre les deux registres ! On obtient alors un multiplieur multibeat.

Multiplieur itératif de type multibeat

Les multiplieurs itératifs en base 4, 8, 16

La méthode précédente utilise un multiplieur hybride. Mais il est aussi possible d'utiliser un multiplieur itératif normal, et de le modifier pour en faire un multiplieur en base 4, 8, 16, etc. Les méthodes pour cela sont moins intuitives, plus complexes, mais sont cependant intéressantes à étudier. Elles ne sont pas utilisées, car elles utilisent plus de circuits ou sont moins performantes.

Leur idée est d'additionner les produits partiels entre eux avant de les additionner au registre accumulateur. Le problème est que l'on ne va pas rajouter un second additionner dans le circuit, aussi diverses méthodes permettent de ruser. La ruse consiste à précalculer tous les produits partiels possibles et de les stocker dans des registres. Le choix du produit partiel à envoyer à l'additionneur se fait avec un MUX commandé par un paquet de 2, 3, 4 bits du multiplieur.

Prenons l'exemple le plus simple : celui d'un multiplieur en base 4, qui demande d’additionner deux produits partiels à la fois, de traiter l'opérande multiplieur par paquets de deux bits. Dans ce cas, la somme des produits partiels vaut : O, A, 2A, 3A. Et c'est cette somme qu'il faut additionner au contenu du registre accumulateur. Les quatre sommes possibles sont toujours les mêmes, et on peut les précalculer et les mémoriser dans des registres dédiés. On peut choisir la bonne somme en fonction des deux bits du multiplieur

Multiplieur itératif non-hybride en base 4

Il est cependant possible de ruser afin d'éliminer certains registres. Par exemple, pas besoin d'un registre pour le 0 : juste d'un circuit de mise à zéro, comme dans n'importe quel circuit de génération de produit partiel. Pareil pour le registre contenant le double du multiplicande : un simple décalage suffit pour le calculer à la volée (une simple bidouille de câblage permet de se passer de circuit décaleur). Seuls restent les registres pour le multiplicande et son triple. Il est généré par l'additionneur normal, en fin de circuit, au tout début de l'addition.

La solution marche aussi quand on veut générer trois produits partiels à la fois, ou quatre, ou cinq, mais deviennent rapidement inutiles. Par exemple, pour générer trois produits partiels à la fois, il faut calculer 0, A, 2A, 3A, 5A et 7A, et calculer le reste à partir de cela. Mais le jeu n'en vaut pas la chandelle. Certes, calculer trois produits partiels à la fois divise par trois le nombre d'additions, sauf que générer à l'avance les produits partiels rajoute quelques additions. Ce qu'on gagne d'un côté, on le perd de l'autre.

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.

Multiplier les valeurs absolues et convertir

Une première solution pour multiplier des entiers signés est simple : on prend les valeurs absolues des opérandes, on multiplie, et on inverse le résultat si besoin. 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. On s’aperçoit qu'on doit inverser le résultat si et seulement si une seule opérande est négative, pas les deux.

Signe du multiplicande	Signe du multiplieur	Signe du résultat
+	+	+
-	+	-
+	-	-
-	-	+

Pour les entiers en signe-valeur absolue, le calcul est très simple, vu que la valeur absolue et le signe sont séparés. Il suffit de calculer le bit de signe à part, et multiplier les valeurs absolues. En traduisant le tableau d'avant 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 faire un vulgaire XOR entre les bits de signe.

Multiplication en signe-magnitude

Pour les entiers en complément à deux, cette solution n'est pas utilisée. Prendre les valeurs absolues demande d'utiliser deux incrémenteurs et deux inverseurs, sans compter qu'il faut en rajouter un de plus pour inverser le résultat. Le cout en circuits serait un peu gros, sans compter qu'on peut faire autrement.

Les multiplieurs itératifs signés en complément à deux

Pour la représentation en complément à deux, les multiplieurs non-signés 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. Les multiplieurs vus plus haut peuvent gérer la situation so on utilise 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. Cette technique marche très bien que on utilise un multiplieur qui travaille de droite à gauche, avec des décalages à droite.

Pour traiter les multiplicateurs négatifs, le produit partiel correspondant au bit de poids fort doit être soustrait. L'explication du pourquoi est assez dure à comprendre, aussi je vous épargne les détails, mais c'est lié au fait que ce bit a une valeur négative. L'additionneur doit donc être remplacé par un additionneur-soustracteur.

Multiplieur itératif pour entiers signés.

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

La division en binaire se fait de la même manière qu'en décimal : avec une série de soustractions. L'opération implique un dividende, qui est divisé par un diviseur pour obtenir un quotient et un reste.

Implémenter la division sous la forme de circuit est quelque peu compliqué. La difficulté est simplement que chaque étape de la division dépend de la précédente ! Cela réduit les possibilités d'optimisation. Il est très difficile d'utiliser des soustracteurs multiopérande non-itératifs pour créer un circuit diviseur. Pas de problème pour la multiplication, où utiliser un paquet d'additionneurs en parallèle marche bien. La division ne permet pas de faire de genre de choses facilement. C'est possible, mais le cout en circuits est prohibitif.

Les techniques que nous allons voir en premier lieu calculent le quotient bit par bit, elles font une soustraction à la fois. Il est possible de calculer le quotient non pas bit par bit, mais par groupe de deux, trois, quatre bits, voire plus encore. Mais les circuits deviennent alors très compliqués. Dans tous les cas, cela revient à utiliser des diviseurs itératifs, sur le même modèle que les multiplicateurs itératifs, sauf que l’addition est remplacée par une soustraction. Nous commencer par les trois techniques les plus simples pour cela : l'implémentation naïve, la division avec restauration, et sans restauration.

L'implémentation itérative naïve

Division en binaire.

En binaire, l'opération de division est la même qu'en décimal, si on omet que la table de soustraction est beaucoup plus simple. La seule différence est qu'en binaire, à chaque étape, on doit soit soustraire zéro, soit soustraire le diviseur, rien d'autre. Mais pour le reste, tout se passe de la même manière qu'en décimal. À chaque étape, on prend le reste partiel, le résultat de la soustraction précédente, et on abaisse le bit adéquat, exactement comme en décimal.

Sur le principe, général, un diviseur ressemble à ce qui est indiqué dans le schéma ci-dessous. On trouve en tout quatre registres : un pour le dividende, un pour le diviseur, un pour le quotient, et un registre accumulateur dans lequel se trouve le "reste partiel" (ce qui reste une fois qu'on a soustrait le diviseur dans chaque étape).

À chaque étape de la division, on effectue une soustraction, ce qui demande un circuit soustracteur. On soustrait soit le diviseur, soit zéro. Le choix entre les deux est réalisé par un multiplexeur, ou encore mieux : par un circuit de mise à zéro sélectif.

Abaisser le bit suivant demande un peu plus de réflexion. Le bit abaissé appartient au dividende, et on abaisse les bits en progressant du bit de poids fort vers le bit de poids faible. Pour faire cela, le dividende est placé dans un registre à décalage, qui se décale d'un rang vers la gauche à chaque itération. Le bit sortant du registre n'est autre que le bit abaissé. Il suffit alors de le concaténer au reste partiel, avec une petite ruse de câblage, et d'envoyer le tout en opérande du soustracteur. Rien de bien compliqué, il faut juste envoyer le bit abaissé sur l'entrée de poids faible du soustracteur, et de câbler le reste pareil à côté, ce qui décale le tout d'un rang automatiquement, sans qu'on ait besoin de circuit décaleur pour le reste partiel.

Reste ensuite à déterminer le quotient, ce qui est fait par un circuit spécialisé relié au diviseur et au dividende. Au passage, déterminer le bit du quotient permet au passage de savoir si on doit soustraire le diviseur ou non (soustraire zéro). Ce circuit n'est pas relié qu'au registre pour le quotient, mais aussi au multiplexeur mentionné précédemment. Toute la difficulté tient dans la détermination du quotient. En soi, elle est très simple : il suffit de comparer le dividende et le diviseur. Si le dividende est supérieur au diviseur, alors on peut soustraire. S'il est inférieur, on ne soustrait pas, et on passe à l'étape suivante. Si les deux sont égaux, on soustrait.

Circuit diviseur, principe général

L’optimisation de ce circuit la plus intéressante est la mise à l'échelle les opérandes. L'idée est juste de commencer la division au bon moment, en ne faisant pas certaines étapes dont on sait qu'elles vont fournir un zéro sur le quotient. L'idée marche sur les dividendes dont les n bits de poids fort sont à zéro. L'idée est de zapper ces n bits, en décalant le dividende de n rangs au début de la division, vu qu'on sait que ces bits donneront des zéros pour le quotient et pas de reste partiel. Il faut aussi décaler le quotient de n rangs, en insérant des 0 à chaque rang décalé.

L'implémentation itérative sans redondance du soustracteur

Un défaut du circuit précédent est qu'il y a une duplication de circuit cachée. En effet, le circuit de détermination du quotient est un comparateur. Mais un comparateur peut s'implémenter par un circuit soustracteur ! Pour vérifier si un opérande est supérieur, égale ou inférieur à une seconde opérande, il suffit de les soustraire entre elles et de regarder le signe du résultat. On a donc deux circuits soustracteurs cachés dans ce circuit : un pour déterminer le quotient, un autre pour faire la soustraction. Mais il y a moyen de ruser pour éliminer cette redondance.

De plus, retirer cette duplication ne rend pas le circuit plus lent. En n'utilisant qu'un seul soustracteur, on fera la comparaison et la soustraction dans le même soustracteur, l'une après l'autre. Mais avec le circuit ci-dessous, c'est la même chose : on effectue la comparaison pour sélectionner le bon opérande, avant de faire la soustraction. Dans les deux cas, c'est globalement la même chose.

Si on retire la redondance mentionnée dans la section précédente, le circuit reste globalement le même, à un détail près. Chaque étape demande de comparer reste partiel et diviseur pour déterminer le bit du quotient et l'opérande à soustraire, puis faire la soustraction. La comparaison se fait avec une soustraction, et le bit de signe du résultat est utilisé pour déterminer le signe de l'opérande. Chaque étape est donc découpée en deux sous-étapes consécutives : la comparaison et la soustraction. La manière la plus simple pour cela est de faire en sorte que le circuit fasse chaque étape en deux cycles d'horloges : un dédié à la comparaison, un autre dédié à la soustraction proprement dit.

Le circuit doit donc fonctionner en deux temps, et la meilleure manière pour cela est de lui faire faire une étape de la division en deux cycles d'horloges. Certains circuits vont fonctionner lors du premier cycle, d'autres lors du second. Lors du premier cycle, le bit du quotient est déterminé, le multiplexeur est configuré pour pointer vers le diviseur, et le registre du quotient est décalé. Les autres circuits ne fonctionnent pas. Le résultat de la soustraction n'est pas pris en compte, il n'est pas enregistré dans le registre du reste partiel. Lors du second cycle, c'est l'inverse : le multiplexeur est configuré par le bit calculé à l'étape précédente, le résultat de la soustraction est enregistré dans le registre accumulateur, et le registre du dividende est décalé.

Circuit diviseur naif amélioré en stoppant modification de l'accumulateur lors d'une comparaison

On pourrait croire que le circuit de division obtenu est plus lent, vu qu'il a besoin de deux cycles d'horloge pour faire son travail. Mais la réalité est que ce n'est pas forcément le cas. En réalité, on peut très bien doubler la fréquence de l'horloge uniquement dans le circuit de division, qui fonctionne deux fois plus vite que les circuits alentours, y compris ceux auquel il est relié. Par exemple, si le circuit de division est intégré dans un processeur, le processeur ira à une certaine fréquence, mais le circuit de division ira deux fois plus vite. Mine de rien, cette solution a été utilisée dans de nombreux designs commerciaux, et notamment sur le processeur HP PA7100.

La division avec restauration

Division avec restauration.

Un point important pour que l’algorithme précédent fonctionne est que le résultat fournit par le soustracteur ne soit pas pris en compte lors de l'étape de comparaison. Plus haut, la solution retenue était de ne pas l'enregistrer dans le registre du reste partiel. Il s'agit là de la solution la plus simple, mais il existe une solution alternative plus complexe, qui autorise l'enregistrement du reste partiel faussé dans le registre accumulateur, mais effectue une correction pour restaurer le reste partiel tel qu'il était avant la comparaison. C'est le principe de la division avec restauration que nous allons voir dans ce qui suit.

Développons la division avec restauration par un exemple illustré ci-contre. Nous allons cherche à diviser 1000 1100 1111 (2255 en décimal) par 0111 (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 soustraire le diviseur à ce bit, pour 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. On restaure alors le reste partiel antérieur, en ajoutant le diviseur retranché à tort. Ensuite, on abaisse le bit juste à côté du bit qu'on vient de tester, et on recommence. À chaque étape, on restaure le reste partiel si le résultat de la soustraction est négatif, on ne fait rien s'il est positif ou nul.

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 n’aurait pas dû 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. L'algorithme utilise en tout, pour des nombres de N bits, 2N+1 additions/soustractions maximum.

Le seul changement est la restauration du reste partiel. Restaurer le dividende initial demande d'ajouter le diviseur qu'on vient de soustraire. L'algorithme ressemble au précédent, sauf que l'on a plus besoin du multiplexeur, le diviseur est toujours utilisé comme opérande du soustracteur. Sauf que le soustracteur est remplacé par un additionneur-soustracteur. Le circuit de détermination du bit du quotient commande non seulement l'additionneur/soustracteur. Il est beaucoup plus simple que le comparateur d'avant.

Circuit de division.

La division sans restauration

La méthode précédente a toutefois un léger défaut : on a besoin de remettre le reste partiel comme il faut lorsqu'on a soustrait le diviseur décalé alors qu'on aurait pas du et que le résultat obtenu est négatif. La division sans restauration se passe de cette restauration du reste partiel et continue de calculer avec ce reste faux,. Par contre, elle effectue une phase de correction lors du cycle suivant. De plus, il faut corriger le quotient obtenu pour obtenir le quotient adéquat, pareil pour le reste.

Mettons que l'on souhaite soustraire le diviseur du reste partiel, mais que le résultat soit négatif. Au lieu de restaurer le reste partiel initial, on continue, en effectuant une correction au cycle suivant. Il y a donc deux cycles d'horloge à analyser. Au premier, on a le reste partiel R, dont on soustrait le diviseur D décalé de n rangs :

$R-D$

Si le résultat est positif, on continue la division normalement, le cycle suivant implique une soustraction normale, il n'y a rien à faire. Mais si le résultat est négatif, une division normale restaure R, puis poursuit la soustraction. Lors du second cycle, le reste partiel est décalé d'un rang vers la gauche, ce qui donne :

$2R-D$

Maintenant, regardons ce qui se passe avec une division sans restauration. On fait la soustraction, on a R - D, qui est négatif. On décale vers la gauche, et on soustrait de nouveau D au second cycle :

$2(R-D)-D=2R-3D$

Le résultat est incorrect, il faut le corriger pour obtenir le bon résultat. Pour cela, on calcule l'erreur, la différence entre les deux équations précédentes :

$[2R-D]-[2R-3D]=2D$

La correction demande donc juste de faire une addition du diviseur au cycle suivant.

Un autre point à prendre en compte est l'interprétation des bits du quotient. Avec la division avec restauration, le bit du quotient s’interprète comme suit : 0 signifie que l'on a pas soustrait le diviseur décalé par le poids du bit, 1 signifie qu'on a soustrait. Avec la division sans restauration, l'interprétation est différente : 0 signifie que l'on a additionné le diviseur décalé par le poids du bit, 1 signifie qu'on a soustrait. La différence signifie qu'il faut convertir le quotient de l'un vers l'autre pour obtenir le bon quotient. Pour cela, il faut inverser les bits du quotient, multiplier le résultat par deux et ajouter 1.

Inverser les bits du quotient peut se faire à la volée, lors du calcul, alors que les deux opérations finales se font à la toute fin du calcul, lors du dernier cycle.

Enfin, il faut tenir compte d'un cas particulier : le cas où le reste final est invalide. Cela arrive si on arrive à la fin du calcul, au dernier cycle, et que l'on effectue une soustraction mais que l'on aurait pas dû soustraire. Dans ce cas, on se retrouve avec un reste négatif. Dans ce cas, on est censé poursuivre le calcul encore un cycle pour corriger le résultat, en additionnant le diviseur. Le circuit diviseur doit détecter la situation et effectuer un cycle supplémentaire.

Pour résumer, la division sans restauration :

• Continue le calcul en cas de reste partiel incorrect, sauf qu'au cycle suivant, on additionne le diviseur au lieu de soustraire ;
• Inverser les bits du quotient, multiplier le résultat par deux et ajouter 1.
• Corrige le reste avec l'addition du diviseur si celui-ci devient négatif au dernier cycle.

Les diviseurs améliorés

On peut améliorer toutes les méthodes précédentes en ne traitant pas notre dividende bit par bit, mais en le manipulant par groupe de deux, trois, quatre bits, voire plus encore. Mais les circuits deviennent alors très compliqués. 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, sous peine d'obtenir des résultats erronés. Et si vous croyez que les constructeurs de processeurs n'ont jamais fait cette erreur, sachez qu'Intel en a 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 ! C'est de là que vient le fameux "Pentium FDIV bug".

Il est possible de modifier les circuits diviseurs pour remplacer l'additionneur-soustracteur par un équivalent qui fait les calculs en carry save. Les calculs sont alors drastiquement accélérés. Mais le circuit devient alors beaucoup plus complexe. Le calcul du quotient, qui demande un comparateur, est difficile du fait de l'usage de la représentation carry save.

De nos jours, les diviseurs utilisent une version améliorée de la division sans restauration, appelé l'algorithme de division SRT. C'est cette méthode qui est utilisée dans les processeurs pour la division entière ou la division flottante.