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

Dans ce chapitre, nous allons voir les circuits pour additionner entre eux plus de deux nombres en même temps. Additiuonneur plus de deux opérandes est appelé une addition multiopérande, terme que nous utiliserons dans la suite de ce cours. C'est une opération assez utilisée, qui est notamment à la base de la multiplication binaire, qui sera vue au chapitre suivant. Mais elle est aussi utilisée pour d'autres opérations, comme certaines opérations vectorielles utilisées dans le rendu 3D (et les moteurs de jeux vidéo).

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

Il existe de nombreux types de circuits capables d'effectuer une addition multiopérande. Ce sont tous des additionneurs normaux modifiés. 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émment 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

A 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érandes, l'intuition nous dit de combiner plusieurs additionneurs 2-opérandes. Et c'est en effet une solution, qui peut se mettre en œuvre de deux manières.

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

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. Avec la seconde solution, le résultat est alors connu plus tôt, car il y a moins d'additionneurs à traverser en partant des opérandes pour arriver au résultat. Dans les deux cas, on utilise presque autant d'additionneurs que d'opérandes (un additionneur en moins, pour être précis).

Les additionneurs utilisés peuvent être n'importe quel type d'additionneurs. Pour donner un exemple d'additionneurs en série, nous allons prendre un additionneur 4-opérandes (qui additionne 8 opérandes différentes). Par exemple, si on utilise des additionneurs à propagation de retenue, le circuit d'un additionneur 4 bits est celui-ci :

Multiplieur en chaine fait avec des additionneurs à propagation de retenues

Bizarrement, l'usage d'additionneurs à propagation de retenue donne de bonnes performances, tout en économisant beaucoup de portes logiques.

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, le reste d'un additionneur étant simplement composé de portes XOR. 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.

L'adder compressor 3:2

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.

La seule contrainte est de pouvoir additionner trois bits. Il se trouve que l'on a déjà un circuit capable de le faire : 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 en général

Les additionneurs carry save additionnent plusieurs opérandes et fournissent un résultat en carry save. Faire une addition multiopérande demande donc : d'additionner les opérandes en carry save, puis de convertir le résultat carry save en résultat final. Le tout demande juste un additionneur carry save et un additionneur normal. L'avantage est que l'additionneur carry save économise beaucoup de portes logiques et est aussi plus rapide.

Additionneur multiopérande en carry save

Les additionneurs carry save sériels

Dans le cas le plus fréquent, un additionneur carry save se conçoit en combinant des additionneurs carry save 3-opérandes. La manière la plus simple est d'enchainer les additionneurs 3-opérandes les uns à la suite des autres, comme illustré ci-dessous.

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.

Mais cette méthode est généralement peu efficace, et on préfére utiliser une organisation parallèle, en arbre, avec des additions faites en parallèle. Les deux méthodes les plus connues donnent les additionneurs en arbres de Wallace, ou en arbres Dadda.

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

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 adders compressors

Dans les circuits précédents, il n'est pas rare d'enchainer plusieurs additionneurs complets l'un à la suite des autres. Mais il est possible de les regrouper par 2 ou 3, ce qui permet de faire des simplifications. Les regroupements en question sont appelés des adder compressors. Ils prennent en entrée plusieurs bits, provenant d'opérandes différents, et les additionnent. Le résultat est évidemment en carry save, ce qui fait qu'il est codé sur deux bits : un bit de retenue, un bit de résultat.

Les mal-nommés adders compressors 4:2

Le résultat de la fusion de deux additionneurs complets donne un mal nommé "adder compressor 4:2". Ils disposent de 5 entrées et fournissent 3 sorties. Plus précisément, ils prennent en entrée 4 bits pour les 4 opérandes et un bit pour la retenue d'entrée. Pour la sortie, ils fournissent 3 sorties : le bit de retenue du résultat final, les deux retenues des additions intermédiaires.

La manière la plus simple de les fabriquer est d'utiliser deux additionneurs complets l'un à la suite de l'autre. Le premier additionne trois bits d'opérande et fournit un résultat et des retenues, le résultat est ensuite additionné avec les deux opérandes restantes. Au final, on se retrouve avec deux retenues, et un résultat.

Adder compressor 4-2

Il est cependant possible d'améliorer le circuit pour le rendre légèrement plus rapide. Le problème du circuit précédent est que les portes XOR sont enchainées l'une après l'autre, alors que l'on peut faire comme suit :

Adder compressor 4-2 optimisé

L'additionneur multiopérande itératif

L'additionneur multiopérande itératif additionne les opérandes une par une, le résultat temporaire étant stocké dans le registre. Il porte le nom d'additionneur (multi-opérande) itératif. Il est composé d'un additionneur couplé à un registre, le tout entouré de circuits de contrôle (non-représentés dans les schémas suivants). Le circuit de contrôle est, dans le cas le plus simple, un simple compteur initialisé avec le nombre d'opérandes à additionner. Le registre est appelé le registre accumulateur, ce qui trahit bien son rôle dans le circuit.

Additionneur multi-opérande itératif.

L'avantage de ce circuit est que le nombre d'opérandes à additionner est 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). Dans ce cas, qui peut le plus peut le moins : 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. Par exemple, l'addition de 7 opérandes demandera seulement 6 additions, pas une de plus ou de moins. 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 itératifs hydrides

L'additionneur multiopérande itératif peut s'implémenter avec des additionneurs carry save. 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

Un cas particulier d'addition multi-opérande : le calcul de population count

Voyons maintenant un cas très particulier d'addition multi-opérande : le calcul de la population count d'un nombre, aussi appelée poids de Hamming. Il s'agit d'un calcul qui prend en entrée un nombre, une opérande tout ce qu'il y a de plus normale, codée sur plusieurs bits. La population count calcule le nombre de bits de l'opérande qui sont à 1. C'est donc une addition multi-opérande, sauf que l'on additionne des bits individuels.

Elle est très utilisée quand il faut manipuler la représentation binaire d'un nombre, ou quand on manipule des tableaux de bits. Les deux cas sont peu fréquents en-dehors des codes très bas niveau, mais tout programmeur a déjà eu l'occasion d'en manipuler. C'est une opération très courante dans les algorithmes de correction d'erreur, utilisés dans les transmissions réseaux, que nous verrons dans quelques chapitres. Elle est aussi utilisée pour le codage/décodage vidéo/audio, quand il faut crypter/décrypter des données, etc. Les réseaux de neurones artificiels, notamment ceux utilisés dans l'intelligence artificielle, font aussi usage de cette opération.

Elle peut se calculer de beaucoup de manières différentes. La plus simple s'obtient avec le raisonnement est alors le suivant : si on découpe un nombre en deux parties, la population count du nombre est la somme des population count de chaque partie. Il est possible d'appliquer ce raisonnement de manière récursive sur chaque morceau, jusqu'à réduire chaque morceau 1 bit. Or, la population count d'un bit est égale au bit lui-même, par définition. On en déduit qu'il suffit d'utiliser une série d'additionneurs enchainés en arbre, comme illustré ci-dessous.

Circuit de calcul de population count.

Le circuit est alors composé de plusieurs couches d'additionneurs différents. La première couche additionne deux bits entre eux, elle est donc composée uniquement de demi-additionneurs. La seconde couche est composée d'additionneurs qui prennent des opérandes de deux bits (le résultat des demi-additionneurs), la couche suivante est faite d'additionneurs pour opérandes de 3 bits, etc.

Illustration de la première couche du circuit de POPCNT.

Il est naturellement possible d'utiliser des additionneurs carry save pour économiser des circuits.