Fonctionnement d'un ordinateur/Les circuits pour l'addition multiopérande

Dans ce chapitre, nous allons voir les circuits qui additionnent plus de deux nombres en même temps. Additionner plus de deux opérandes est appelé une addition multiopérande, terme que nous utiliserons dans la suite de ce cours. C'est l'opération à la base de la multiplication binaire, mais aussi d'autres opérations, comme certaines opérations vectorielles utilisées dans le rendu 3D (les moteurs de jeux vidéo). Nous aurions pu en parler dans le prochain chapitre sur la multiplication, mais les circuits d'addition multiopérande étant un peu compliqués, nous en avons fait un chapitre propédeutique séparé.

Additionneur multiopérande de 4 bits, pour 3 opérandes.

L'interface de ces additionneurs est la même que celle des additionneurs normaux, sauf qu'ils disposent de plusieurs entrées pour les opérandes. L'un d'entre eux est illustré ci-contre, pour l'addition de trois opérandes de 4 bits. Il est préférable de voir les circuits d'addition multiopérande séparément des circuits pour la multiplication, pour diverses raisons pédagogiques, ce qui est fait dans ce cours.

Les implémentations naïves, non-optimisées

À cet instant du cours, nous ne disposons que d'additionneurs 2-opérandes, à savoir qu'ils additionnent deux nombres. Pour créer un additionneur multiopérande, nous pouvons utiliser un ou plusieurs additionneurs 2-opérandes.

L'additionneur multiopérande itératif

Ladditionneur multi-opérande itératif additionne les opérandes une par une, le résultat temporaire étant stocké dans un registre. Il est composé d'un additionneur 2-opérandes couplé à un registre dit accumulateur, terme qui trahit bien son rôle dans le circuit. Le tout entouré de circuits de contrôle (non-représentés dans les schémas suivants), qui se résume souvent à un simple compteur initialisé avec le nombre d'opérandes à additionner.

Additionneur multi-opérande itératif.

Un avantage de ce circuit est qu'il gère un nombre d'opérandes variable. Par exemple, prenons un additionneur itératif qui permet d'additionner maximum 127 opérandes (le compteur des circuits de contrôle est de 7 bits). Il peut additionner seulement 16 opérandes, seulement 7, seulement 20, etc. Et le résultat est alors connu plus vite : moins on a d'opérandes à additionner, moins le circuit fera d'additions.

Les autres circuits que nous verrons dans ce chapitre sont moins flexibles. Ils additionnent toujours le même nombre d'opérandes, ce qui n'est pas un problème dans les cas où ils sont utilisés. Rien n'empêche de mettre certaines opérandes à 0, ce qui permet de faire moins, de faire des calculs avec moins d'opérandes.

Les additionneurs multiopérande sériels et parallèles

Additionneur multiopérande série versus parallèle.

Une autre méthode combine plusieurs additionneurs 2-opérandes. Et cette solution peut se mettre en œuvre de deux manières, illustrées ci-contre. La première solution utilise des additionneurs en série, placés l'un après l'autre. La seconde solution effectue certaines additions en parallèle d'autres : on obtient alors un additionneur parallèle.

Les additionneurs utilisés peuvent être n'importe quel additionneur 2-opérandes. Par exemple, si on utilise des additionneurs à propagation de retenue, le circuit d'un additionneur série de 3 opérandes de 4 bits est celui-ci :

Multiplieur en chaine fait avec des additionneurs à propagation de retenues.

Bizarrement, mettre des additionneurs à propagation de retenue en série est la solution qui donne les meilleures performances, tout en économisant beaucoup de portes logiques. Les performances sont même meilleures qu'un utilisant des additionneurs à anticipation de retenue en parallèle !

Sans rentrer dans des calculs de complexité algorithmique, la raison est liée à la propagation des retenues, qui limite les performances. Avec des additionneurs à propagation de retenue, les retenues se propagent rapidement entre couches d'additionneurs, chaque additionneur peut commencer ses calculs à peine un cycle après le précédent. Par contre, en enchainant des additionneurs à anticipation de retenue, certains additionneurs doivent attendre que des retenues arrivent. Idem si on les met en parallèle.

Avec des additionneurs à propagation de retenue en série, le temps est proportionnel à $N\times \log n$. Avec les additionneurs à anticipation de retenue en parallèle, le temps de calcul est proportionnel à $\log n\times \log k+\left(\log n\times \log {(\log n)}\right)$. Ce qui est plus grand que $N\times \log n$ si N et n sont assez grands.

L'addition carry save

Le problème de l'addition, qu'elle soit multiopérande ou non, est la propagation des retenues. La propagation des retenues prend du temps. Mais il se trouve qu'il est possible d'additionner un nombre arbitraire d'opérandes et de ne propager les retenues qu'une seule fois ! Pour cela, on additionne les opérandes entre elles avec une addition carry-save, une addition qui ne propage pas les retenues.

L'addition carry save de trois opérandes

L'addition 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. Pour que cela soit plus concret, nous allons étudier le cas où l'on additionne trois opérandes entre elles. Par exemple, 1000 + 1010 + 1110 donne 1010 pour les retenues, et 1100 pour la somme sans retenue. L'addition se fait comme en binaire normal, colonne par colonne, sauf que les retenues ne sont pas propagées.

Carry save (addition)

Une fois le résultat en carry-save obtenu, il faut le convertir en résultat final. Pour cela, il faut faire une addition normale, avec les retenues placées sur la bonne colonne (les retenues sont ajoutées sur la colonne suivante). L'additionneur carry save est donc suivi par un additionneur normal. L'avantage de cette organisation se comprend quand on compare la même organisation sans carry save. Sans carry save, on devrait utiliser deux additionneurs normaux. Avec, on utilise un additionneur normal et un additionneur carry save plus simple et plus rapide.

Reste à voir comment faire l'addition en carry save. Notez que les calculs se font indépendamment, colonne par colonne. Cela vient du fait que la table d'addition en binaire, pour 3 bits, le permet :

• 0 + 0 + 0 = 0, retenue = 0 ;
• 0 + 0 + 1 = 1, retenue = 0 ;
• 0 + 1 + 0 = 1, retenue = 0 ;
• 0 + 1 + 1 = 0, retenue = 1 ;
• 1 + 0 + 0 = 1, retenue = 0 ;
• 1 + 0 + 1 = 0, retenue = 1 ;
• 1 + 1 + 0 = 0, retenue = 1 ;
• 1 + 1 + 1 = 1, retenue = 1.

Le tout donne la table de vérité de l'additionneur complet ! Un circuit d'addition de trois opérandes en carry save est donc composé de plusieurs additionneurs complets indépendants, chacun additionnant le contenu d'une colonne. Le tout est illustré ci-dessous.

Additionneur carry-save.

Les additionneurs carry save à plus de 3 opérandes

L'addition carry save permet d'additionner trois opérandes assez simplement, avec un cout en circuit à peine plus élevé que pour l'addition deux-opérandes. Mais qu'en est-il pour additionner plus de trois opérandes ? L'idée est d'additionner les opérandes par groupes de deux/trois, avec une addition carry save pour chaque groupe de deux/trois, avant de combiner les résultats carry save entre elles.

Les additionneurs précédents peuvent être adaptés de manière à fonctionner avec des additionneurs carry save. La seule contrainte est de faire attention au poids des bits à additionner (les retenues doivent être décalées d'un cran avant l'addition). Par exemple, un additionneur itératif peut utiliser un additionneur carry save et un registre pour additionner les opérandes, avant d'envoyer le résultat final à un additionneur normal pour calculer le résultat final. Le circuit obtenu est un L'additionneur multiopérande hybride, mi-itératif, mi carry save.

Additionneur multi-operande itératif en carry save

Il est aussi possible de faire la même chose avec un additionneur multiopérande sériel, où plusieurs additionneurs simples sont enchainés l'un après l'autre. En remplaçant les additionneurs 2-opérandes par des additionneurs carry save, le circuit devient tout de suite plus rapide.

Adder carry save 5 opérandes séquentiel

Prenez garde : les retenues sont décalées d'un rang pour être additionnées. En conséquence, le circuit ressemble à ceci :

Implémentation d'un additionneur multiopérande avec des additionneur carry-save 3:2.

Avec des additionneurs 2-opérande, utiliser des additionneurs à propagation de retenue était la meilleure solution. Mais ce n'est plus le cas avec des additionneurs carry save. Une organisation en arbre, avec des additions faites en parallèle, devient plus rapide. Et il existe de nombreuses manières pour construire un arbre d'additionneurs. Les deux méthodes les plus connues donnent les additionneurs en arbres de Wallace, ou en arbres Dadda. La première a le meilleur temps de calcul, l'autre est la plus économe en portes logiques.

Les arbres de Wallace

Les arbres les plus simples à construire sont les arbres de Wallace. Le principe est d'ajouter des couches d'additionneurs carry-save les unes à la suite des autres. Lors de l'ajout de chaque couche, on vise à 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.

Arbre de Wallace pour l'addition de 8 nombres de 8 bits.

Les arbres de Dadda

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 :

• si n est multiple de trois, on ajoute une couche complète d'additionneurs carry-save ;
• si n n'est pas multiple de trois, on ajoute seulement 1 ou 2 additionneur carry-save : le but est de faire en sorte que la couche suivante fournisse un nombre d'opérandes multiple de trois.

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.

Arbre de Dadda pour l'addition de 8 nombres de 8 bits.

Les additionneurs multiopérande basés sur des adder compressors

L'usage d'additionneurs carry save est une première étape, mais il y a moyen d'aller encore plus loin. L'addition carry save permet d'additionner trois opérandes en même temps, mais on peut les additionner par paquets de 4 ou 5 opérandes. Dans le chapitre précédent, nous avons vu les compteurs parallèles, des circuits qui additionnent plusieurs bits et fournissent un résultat encodé en binaire. L'idée est de faire comme l'addition en carry save, sauf qu'au lieu d'utiliser des FA qui additionnent 3 bits à la fois, on utilise des compteurs parallèles qui additionnent 4/5/6/ bits d'un coup. Par contre, vu qu'ils fournissent plusieurs retenues, le circuit est plus complexe.

Le résultat est assez variable. Les adder compressors 4:2 sont souvent utilisés, mais ceux allant au-delà (qui fusionnent plus de 2 additionneurs complets) sont déjà plus controversés.

L'addition multiopérande à propagation de retenue avec des compteurs parallèles

Additionner N opérandes demande d'additionner les bits sur la même colonne, ceux de même poids, avec éventuellement une retenue. Il se trouve qu'additionner les bits d'une même colonne revient à calculer la population count de cette colonne, ce que fait un compteur parallèle ! Cependant, le résultat du compteur parallèle sera codé sur 2, 3, 4 bits, voire plus. Il contiendra un bit de somme et deux bits de retenue. Les retenues doivent être propagées à la colonne suivante et additionnées avec les autres bits.

Il est donc possible de créer un circuit équivalent à un additionneur à propagation de retenue. Pour rappel, l'additionneur à propagation de retenue était composé de FA enchainés les uns à la suite des autres. Chacun additionnait deux bits, et la retenue provenant de la colonne précédente. Ici, les FA sont remplacés par des compteurs parallèles qui additionnent tous les bits de la colonne, mais aussi les retenues des colonnes précédentes. Un exemple avec une addition de 5 opérande est illustré ci-dessous : on voit qu'il y a deux retenues, une provenant de la colonne précédente, une provenant de deux colonnes avant. Le nombre de retenues et la distance des colonnes précédente varie suivant le nombre d'opérandes.

Addition multiopérande avec des compteurs parallèles, circuit à propagation de retenues.

L'addition multiopérande parallèle avec des compteurs parallèles

Une autre solution permet de se passer de la propagation de la retenue. L'idée est de ne pas tenir compte des retenues, mais de les laisser à plus tard. Les bits d'une même colonne sont additionnés par un compteur parallèle, qui fournit un bit de somme et des retenues pour chaque colonne. Le tout est suivi par un autre additionneur multiopérande qui additionne les retenues et sommes.

En effet, il est possible de faire une analogie avec le carry save. Le carry save donne un résultat pour la somme et un pour les retenues. Mais avec des compteurs parallèles autres que des FA, on a un résultat somme et plusieurs résultats pour les retenues. Mais la logique reste la même : les différents résultats peuvent être additionnés pour donner le résultat. Il faut juste penser à décaler les retenues du nombre de rangs adéquat pour chaque retenues.

Addition multiopérande avec des adder compressor, sans propagation de retenue

Avec moins de 8 opérandes, on peut utiliser des compteurs parallèles assez directement. En effet, un compteur parallèle ayant 4 à 7 bits d'entrée fournit trois bits de résultat : un bit de somme, un premier bit de retenu et un bit de retenue de poids fort. Donc, l'additionneur fournit trois résultats : un pour les bits de somme, un autre pour les retenues intermédiaires, un troisième pour les retenues de poids fort.

Le circuit est donc composé de trois additionneurs à la suite. Un premier additionneur est composé de compteurs parallèles qui fournit trois résultats. Ces trois résultats sont additionnés avec un additionneur trois-opérandes carry save, en faisant attention au fait que les bits ne sont pas sur les mêmes colonnes. Les trois résultats sont à additionner, en tenant compte que les bits de chaque résultat sont décalés. Ils ne sont pas sur les mêmes colonnes : si un bit de somme est sur une colonne, la retenue intermédiaire se trouve sur la colonne suivante, et la retenue de poids fort sur la colonne encore suivante.

Additionneur multiopérande en carry save

Mais avec plus de 7 opérandes, on a plus de trois couches. Par exemple, prenons l'exemple d'un additionneur 64 opérandes. Il est tout d'abord composé d'une couche de compteurs parallèles qui additionnent chacun 64 bits et fournissent 7 bits par colonne. Puis, une seconde couche de compteurs parallèles additionne les 7 bits pour fournir 3 bits en sortie, le tout étant suivi par un additionneur carry save et un additionneur 2-opérande.