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

À cet instant du cours, nous ne disposons que d'additionneurs 2-opérandes, à savoir qu'ils additionnent deux nombres. Il est maintenant temps de voir les additionneurs qui additionnent plus de deux opérandes 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 d'ailleurs pu en parler dans le prochain chapitre sur la multiplication, mais nous en avons fait un chapitre propédeutique séparé. Nous allons voir qu'il y a différents types d'additionneurs multiopérandes, qui sont implémentés avec des circuits très différents.

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. Un additionneur itératif a juste besoin d'une entrée, il envoie une nouvelle opérande à chaque cycle sur l'entrée adéquate.

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

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

Si les additionneurs itératifs peuvent gérer un nombre arbitraire d'opérandes, ce n'est pas le cas des autres additionneurs que nous verrons dans ce chapitre. Ils additionnent toujours le même nombre d'opérandes. En conséquence, leur interface est totalement différente. Ils ont autant d'entrées qu'ils ont d'opérandes. L'un d'entre eux est illustré ci-contre, pour l'addition de trois opérandes de 4 bits.

Une implémentation naïve enchaine plusieurs additionneurs , en les mettant l'un après l'autre. Un premier additionneur additionne le deux premières opérandes, l'additionneur suivante additionne la troisième opérande au résultat de l'additionneur précédente, un troisième additionneur additionne la quatrième opérande au résultat précédent, et ainsi de suite. L'implémentation la plus simple utilise des additionneurs à propagation de retenue, mais d'autres additionneurs peuvent en théorie être utilisés. Voici le circuit d'un additionneur série de 3 opérandes de 4 bits, basé sur des additionneurs à propagation de retenue :

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

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

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 ! Et vous avez peut-être eu l'idée de mettre les additionneurs en parallèle, comme indiqué dans le schéma ci-contre, mais même cette solution est moins performante !

Sans rentrer dans des calculs de complexité algorithmique, la raison est liée au fait que la performance est limitée par la propagation des retenues. 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, avec les autres additionneurs possibles, la propagation des retenues entre les additionneurs ne se fait pas de manière optimale.

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 naïfs à plus de 3 opérandes

Pour additionner plus de trois opérandes, l'idée est d'additionner les opérandes par groupes de trois, avec une addition carry save par groupe, avant de combiner les résultats carry save entre elles. Les additionneurs précédents peuvent être adaptés de manière à utiliser des additionneurs carry save, en lieu et place d'additionneurs 2-opérandes normaux. 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 pour additionner deux opérandes par cycle, au lieu d'une seule. Le circuit obtenu est le suivant :

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.

Les additionneurs carry save organisés en arbre d'additionneurs complets

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