Fonctionnement d'un ordinateur/Les circuits pour la population count

Nous allons maintenant aborder 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. Ce calcul prend en entrée un opérande entier tout ce qu'il y a de plus normal, codé sur plusieurs bits. La population count compte le nombre de bits de l'opérande qui sont à 1.

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. 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 est aussi très courante dans les algorithmes de correction d'erreur, utilisés dans les transmissions réseaux ou dans certaines mémoires.

Les autres livres d'architecture des ordinateurs ne parlent pas des circuits de population count, sauf pour quelques exceptions assez rares. Ils parlent de l'opération elle-même, pas des circuits pour la calculer. Si nous faisons un chapitre complet sur ce circuit, c'est parce que les concepts que nous allons aborder dans ce chapitre seront une bonne préparation au chapitre portant sur l'addition multiopérande. En effet, la population count est une forme d'addition multiopérande.

Le calcul de la population count : les compteurs parallèles

La population count peut se calculer à partir du raisonnement suivant : si on découpe un nombre en deux parties, sa population count est la somme des population count de chaque partie. L'idée est donc de découper une opérande en groupes de 2, 3, 4, 5, 6, voire 7 bits ; dont on calcule la population count, avant d'additionner le tout. Pour cela, il faut des circuits qui calculent la population count pour des opérandes de 2, 3, 4, 5, 6, voire 7 bits et fournissent un résultat codé en binaire. Ils sont appelés des parallel counters, terme que nous traduirons par compteurs parallèles.

Pour le moment, nous ne disposons que d'additionneurs capables d'additionner deux opérandes, des additionneurs simples. Nous verrons dans le prochain chapitre qu'il existe des additionneurs dit multiopérande qui sont capables d'additionner 3, 4, 5 opérandes, voire plus. Par exemple, pour 5 nombres notés a, b, c, d et e, il existe un additionneur 5-opérandes capable de calculer a + b + c + d + e. De tels additionneurs multi-opérandes nous rendraient la vie plus facile. Par exemple, pour calculer la population count d'un entier 32 bits, on pourrait utiliser des compteurs parallèles prenant en entrée un octet, et additionner les 4 résultats.

D'ailleurs, la population count est une forme d'addition multiopérande, dont les opérandes font toutes 1 bit.

Circuit de calcul de population count.

Mais pour le moment, nous n'avons pas le choix que d'utiliser deux compteurs parallèles et d'additionner leur résultat avec un additionneur normal. Le tout est illustré ci-dessous.

POPCOUNT avec un adder multiopérande et des adders compressors

Mais le truc, c'est que les compteurs parallèles eux-mêmes peuvent être construits en combinant des compteurs parallèles plus petits avec un additionneur. Par exemple, si je prends un entier de 32, sa population count peut se calculer en additionnant la sortie de deux compteurs parallèles de 16 bits. Eux-mêmes peuvent se construire avec chacun deux compteurs parallèles de 8 bits et un additionneur, etc.

Population count avec des compteurs parallèles

Si on poursuit le processus jusqu'au bout, on se retrouve avec des compteurs parallèles de 2 bits, qui ne sont ni plus ni moins que des demi-additionneurs. Le résultat est une série d'additionneurs enchainés en arbre, comme illustré ci-dessous. Mais ce n'est évidemment pas la solution optimale, juste un cas extrême où le processus récursif est poussé jusqu'au bout. L'idéal serait sans doute d'utiliser d'utiliser des compteurs parallèles plus larges, par exemple de de 4, 8, 16 bits, du moins en première approche.

Circuit de calcul de population count.

Mine de rien, les schémas précédents nous donnent un moyen pour créer un additionneur multiopérande, en combinant plusieurs additionneurs normaux. Il faut les enchainer comme indiqué, en arbre, avec chaque additionneur qui additionne la somme de deux précédents. Mais nous verrons cela dans le chapitre suivant, surtout que nous verrons que ce n'est pas la meilleure manière de faire.

Les opérandes de l'opération population count sont des entiers codés sur 8, 16, 32, 64 bits, qu'on aimerait découper en groupes de 4, 8, 16 bits. Mais ce n'est pas le plus pratique. Un compteur parallèle fournit un résultat codé sur $N_{S}$ bits, à partir de $2_{S}^{N}-1$ bits d'entrée (le -1 est là car il faut encoder le zéro). Par exemple, pour un résultat codé sur 2 bits, les population count possibles sont 0, 1, 2 ou 3, des valeurs ce qui demande 3 bits en entrée. Avec un résultat de 3 bits, on peut coder les valeurs de 0 à 7, ce qui fait 7 bits. Sur 4 bits, cela permet de gérer 15 bits, pas plus. À chaque fois, il nous manque un bit pour avoir un groupe bien rond de 4, 8, 16 bits. Ceci dit, même si ce n'est pas parfait, additionner 4 ou 5 bits à la fois au lieu de deux est d'une aide précieuse. Aussi, il est intéressant de regarder ce que donne un compteur parallèle de 2, 3, 4, 5 bits d'entrée.

Il est maintenant temps de voir comment fabriquer un compteur parallèle. Nous avions vu qu'une solution est de le fabriquer avec des compteurs parallèles eux-mêmes fabriqués par des compteurs parallèles plus petits et ainsi de suite. Cependant, il existe une manière alternative, qui donne un circuit différent. Le circuit que nous allons voir est composé d'un paquet d'additionneurs complets ou de demi-additionneurs. Pour rappel, le premier additionne deux bits et une retenue, alors que le second additionne deux bits d'opérandes. Dans ce qui suit, nous allons utiliser les abréviations suivantes : FA (Full-Adder) pour additionneur complet,, FA (Half-Adder) pour demi-additionneur.

Un exemple : un compteurs parallèle de 4 bits

Intuitivement, il est intéressant de commencer par des compteurs parallèles qui prennent 2, 3 4 bits d'opérandes, pas plus. Et il se trouve que le cas d'un compteur parallèle 2 bits est très simple : il s'agit d'un simple demi-additionneur, un simple HA, qui additionne deux bits, par définition. Il en est de même avec un compteur parallèle 3 bits : c'est un additionneur complet, un FA. Certes, un FA est construit pour additionner deux bits d'opérandes et un bit de retenue. Mais le bit de retenue n'a rien de spécial, c'est un bit comme un autre. Il est parfaitement possible de le remplacer par un bit provenant d'un autre opérande, pour obtenir la somme de trois bits.

Le premier exemple intéressant est donc un compteur parallèle de 4 bits, c'est à dire 4 bits d'opérande. Le résultat est un entier codé sur 3 bits. Le seul moyen de le concevoir est de combiner plusieurs HA et FA. Une manière de faire serait d'additionner les bits d'opérande deux par deux, avec deux HA. Les deux HA fournissent deux résultats de deux bits : un bit de somme et un bit de retenue chacun. Les 2 bits de somme sont additionnés par un autre HA, qui fournit le bit de poids faible du résultat et un troisième bit de retenue.

Compteur parallèle de 4 bits, partiel

Maintenant, que faire des trois bits de retenue ? La réponse se comprend quand on écrit la table de vérité du circuit, que voici :

Opérande		Retenue 1	Retenue 2	Retenue 3		Résultat
0000		0	0	0		0	0	0
0001		0	0	0		0	0	1
0010		0	0	0		0	0	1
0011		1	0	0		0	1	1
0100		0	0	0		0	0	1
0101		0	0	1		0	1	0
0110		0	0	1		0	1	0
0111		1	0	0		0	1	1
1000		0	0	0		0	0	1
1001		0	0	1		0	1	0
1010		0	0	1		0	1	0
1011		1	0	0		0	1	1
1100		0	1	0		0	1	0
1101		0	1	0		0	1	1
1110		0	1	0		0	1	1
1111		1	1	0		1	0	0

Vous remarquerez que si on additionne les retenues, la somme est identique aux bits de poids fort du résultat. En clair, les retenues doivent être additionnées. Pour cela, on peut utiliser un FA, ce qui donne le circuit suivant :

Compteur parallèle de 4 bits, fabriqué avec des HA et FA

Les compteurs parallèles à base d'additionneurs complets

Le circuit que nous avons vu précédemment a l'air simple : on additionne les bits entre eux, ce qui donne un bit de somme et des retenues, retenues qui sont additionnées elles aussi. Mais que se passe-t-il pour les compteurs parallèles de plus de 4 bits ? Pour cela, nous allons voir le cas général.

Un compteur parallèle peut-être composé uniquement de FA ou de HA, voire combiner les deux. Nous allons commencer par parler de compteurs parallèles fabriqués uniquement avec des FA, afin de pouvoir comparer avec le même circuit fabriqué avec des HA. Pour commencer, les bits sont regroupés par groupes de 3. Les bits d'un triplet sont additionnés avec un FA, ce qui donne un résultat sur deux bits : un bit de somme, un bit de retenue.

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

Les bits de somme sont gérés à part des bits de retenue. Les bits de somme sont tous additionnés entre eux, par une couche de FA, suivie par une autre couche de FA, et ainsi de suite jusqu’à ce que tous les bits aient été additionnés. Le résultat est un arbre d'additionneurs qui calcule le bit de poids faible du résultat. L'addition des bits de somme donne le bit de poids faible du résultat, de la population count. Mais il y a aussi des bits de retenue, un par FA (en comptant toutes les couches). Ils sont utilisés pour calculer les bits de poids fort de la population count.

Première étape du calcul de la PCOUNT

Gérer les bits de retenue est assez simple : ils doivent tous être additionnés entre eux ! Sauf que cette fois-ci, on ne peut les additionner avec un simple FA. Il faut à la place utiliser un circuit qui additionne plus de 3 bits, c'est à dire un compteur parallèle ! Pour le dire autrement, on doit calculer la population count des bits de retenue ! En clair, calculer la population count d'un opérande de n bits, il faut utiliser un arbre d'additionneurs, couplé à un circuit qui calcule une population count plus courte !

Circuit complet de calcul de la population count avec des additionneurs complets

Maintenant, faisons quelques calculs, pour savoir combien de retenues doivent être additionnées. Avec des additionneurs complets, la première couche fournit 32/3 = 10 opérandes de 2 bits + un bit isolé. Mais qu'en est-il pour les autres couches ? Je vais donner le nombre de FA/retenues dans le cas général avec n bits d'opérande, mais essayez de le calculer, de trouver une formule mathématique assez simple.

Dans le cas général, pour un opérande de n bits, la première couche produit n/3 avec des FA. Et chaque couche fournit un nombre de retenues qui est divisé par 3, comparé à la couche précédente. On a donc :

${\text{Nombre total de retenues}}={n \over 3}+{n \over 3^{2}}+{n \over 3^{3}}+{n \over 3^{4}}+...=n\times \left[{1 \over 3}+{1 \over 3^{2}}+{1 \over 3^{3}}+{1 \over 3^{4}}+...\right]=n\times {1 \over 2}$

Le résultat est que l'on a moitié moins de FA/retenues. Le circuit contient un arbre de n/2 FA, et un circuit qui calcule la population count de n/2 retenues. En comptant le nombre de portes de ce dernier, et ainsi de suite, on trouve :

${\text{Nombre total de FA}}={n \over 2}+{n \over 2^{2}}+{n \over 2^{3}}+{n \over 2^{4}}+...=n\times \left[{1 \over 2}+{1 \over 2^{2}}+{1 \over 2^{3}}+{1 \over 2^{4}}+...\right]=n\times 1$

Maintenant, faisons une comparaison avec un circuit composé uniquement de demi-additionneurs (HA). Pour un opérande de n bits, le nombre de bits de retenue est de n-1. Le circuit pour n bits utilise donc n-1 HA et un compteur parallèle de n-1 bits. En faisant la somme totale, on trouve : $(n-1)+(n-2)+(n-3)+...+3+2+1$ HA. Cela fait exactement n(n+1)/2 HA. Et vu que chaque HA contient deux portes logiques, cela fait en tout $N^{2}+N\approx N^{2}$ portes logiques.

Circuit complet de calcul de la population count avec des demi-additionneurs

L'usage de FA diminue drastiquement le nombre de portes logiques utilisées : de $\approx N^{2}$ portes logiques, on passe à seulement N. Certes, un FA prend deux-trois fois plus de portes logiques qu'un HA, mais le gain est substantiel pour de longues opérandes. Peut-être est-il possible de pousser cette logique un peu plus loin, ce qui nous amène à la section suivante.

Les compteurs parallèles à base d'adders compressors

Passer d'un HA à un FA a donc fortement réduit le nombre de retenue et grandement simplifié le circuit. Maintenant, essayons de voir l'étape suivante, à savoir ce qui se passe avec des circuits qui additionnent plus de 3 bits. Par exemple, on pourrait imaginer des circuits qui additionnent 4/5/6/7 bits. Il faut noter que nous recherchons des circuits qui ne donnent pas la population count directement, seulement le bit de somme final et les retenues intermédiaires. De tels circuits sont appelés des adder compressors.

Les adder compressors ne calculent pas la population count, mais ils fournissent son bit de poids faible, ainsi que les différentes retenues des additions intermédiaires. Les retenues sont combinées ensemble par des circuits à part, typiquement un autre parallel counter. Les parallel counters sont construits en combinant un adder compressor et un circuit qui additionne les retenues (un autre parallel counter). Il est possible d'utiliser des adder compressors pour fabriquer un parallel counter, mais ils sont aussi utilisés dans d'autres circuits d'addition multiopérande.

Pour créer un adder compressor, une solution est de prendre plusieurs FA et de les combiner entre eux. Il est possible de fusionner deux additionneurs complets à la suite, voire trois, quatre, cinq, voire plus. Cependant, faire ainsi n'est pas optimal. Idéalement, il faut réorganiser la chaine de portes XOR utilisée pour calculer le bit de somme. Les portes XOR doivent idéalement former un arbre équilibré, de manière à réduire le nombre de portes XOR à traverser.

Circuit de calcul de PCOUNT de 5 bits

Pour comprendre pourquoi, prenons l'exemple de l'adder compressor illustré ci-contre. Il additionne 5 bit avec 2 additionneurs complets, combinés avec un parallel counter qui combine les retenues (en jaune). Nous allons nous attarder sur les FA et plus précisément sur la manière dont le bit de poids faible est calculé. Pour rappel, un additionneur complet calcule le bit de poids faible en faisant un XOR entre les bits d'opérande. En enchainant des additionneurs complets, voici ce que l'on obtient au niveau des XOR :

Adder compressor 4-2

Le schéma montre que l'on a quatre portes XOR placées en série, ce qui est tout sauf idéal. Mieux vaut essayer de les mettre en parallèle, pour gagner un petit peu en rapidité. Il est par exemple possible d'améliorer le circuit précédent pour passer de 4 portes en série à seulement 3, ce qui est légèrement plus rapide.

Adder compressor 4-2 optimisé

Pour résumer, nous venons d'inventer un circuit qui fusionne entre eux deux additionneurs complets. Il s'agit d'un circuit qui a un nom qui lui sied assez mal. Il s'agit du mal nommé "adder compressor 4:2". Il prend 5 bits en opérande et fournit 3 sorties : le bit de poids faible du résultat final, les deux retenues des additions intermédiaires. Les retenues sont ensuite combinées entre elles pour obtenir le résultat voulu.

Les adders compressor peuvent être utilisés pour l'addition multiopérande. Lorsqu'on additionne N opérandes, on doit faire deux choses. Premièrement, il faut additionner les bits sur la même colonne, ceux de même poids. Deuxièmement, on doit propager les retenues. Il se trouve qu'additionner les bits d'une même colonne revient à calculer la population count de cette colonne ! Cependant, le résultat sera codé sur 2, 3, 4 bits, voire plus. Et seul le bit de poids faible nous intéresse. En effet, lors d'une addition multiopérande, l'addition des bits sur une colonne calcule un bit du résultat, qui est sur la même colonne, et des retenues. En clair, pas besoin d'utiliser un circuit de population count proprement dit, on a juste besoin d'utiliser les adder compressors. 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.