Fonctionnement d'un ordinateur/Les circuits de calcul logique et bit à bit

Dans ce chapitre et les suivants, nous allons voir comment implémenter sous forme de circuits certaines opérations extrêmement courantes dans un ordinateur. Les quelques circuits que nous allons voir seront réutilisés massivement dans les chapitres qui suivront, aussi nous allons passer quelque temps sur ces bases. Pour simplifier, les opérations réalisées par un ordinateur se classent en trois types :

• Les opérations arithmétiques, à savoir les additions, multiplications et autres, qui auront chacune leur propre chapitre.
• Les décalages et rotations, où on décale tous les bits d'un nombre d'un ou plusieurs crans vers la gauche/droite, qui feront l'objet d'un futur chapitre.
• les opérations bit à bit, qui s'appliquent entre bits de même poids d'opérandes différentes.
• Les opérations logiques qui font l'objet de ce chapitre.

Les opérations logiques manipulent un opérande, et précisément sa représentation binaire. Elles ne font pas de calcul avec cet opérande, mais manipulent ses bits. La différence avec les opérations bit à bit est que l'opération ne se fait pas bit par bit, il n'y a pas d'opération appliquée à chaque bit indépendamment des autres. Les opérations logiques combinent les bits entre eux pour fournir leur résultat, elles peuvent les faire changer de place, en supprimer, en ajouter, etc.

L'opération de 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 un 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 additionner les résultats des compteurs parallèles, il est possible d'utiliser 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.

Circuit de calcul de population count.

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

Mais pour le moment, nous ne disposons que d'additionneurs capables d'additionner deux opérandes, des additionneurs simples. Nous verrons dans le prochain chapitre comment fabriquer des additionneurs multiopérande. D'ailleurs, ce chapitre sert d'introduction propédeutique à l'addition multiopérande. En effet, la population count est une forme d'addition multiopérande, dont les opérandes font toutes 1 bit. Mais pour le moment, nous n'avons que des additionneurs normaux, ce qui nous limite à la possibilité 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

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

Le circuit ne paye pas de mine, mais c'est ce circuit qui a été utilisé sur un des tout premier processeur ARM, l'ARM1 prévu pour les premiers iPhones.

Pour ceux qui veulent en savoir plus, voici un lien vers le blog de Ken Shiriff, qui a rétroingénieuré ce processeur et qui décrit le circuit exact utilisé dans l'ARM1. Le circuit été cependant utilisé dans un contexte un peu particulier, lié à la gestion des registres du processeur, chose qui sera vu dans la cinquième partie de ce cours : Counting bits in hardware: reverse engineering the silicon in the ARM1 processor

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 longs 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 qui calcule 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 d'un adder compressor 4:2". Contrairement à ce que son nom peut faire penser, 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. Une implémentation naïve est illustrée 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é

Le but est donc d'obtenir un arbre de portes XOR équilibré, avec une taille minimale. Pour cela, il existe une solution simple : utiliser des HA au lieu des FA. Mais en faisant cela, le nombre de retenue est trop important. L'idée est alors de garder l'arbre des portes XOR obtenu avec des HA, mais de calculer les retenues par groupes de 3 bits.

Addition des bits de somme avec des HA : arbre équilibré

Les opérations FFS, FFZ, CTO et CLO

Dans cette section, nous allons aborder plusieurs opérations fortement liées entre elles, illustrées dans le schéma ci-dessous. Elles sont très courantes sur la plupart des ordinateurs, surtout dans les ordinateurs embarqués. Beaucoup d'ordinateurs, comme les anciens mac avec des processeurs type Power PC et les processeurs MIPS ou RISC ont des instructions pour effectuer ces opérations.

Mais avant de passer aux explications, un peu de terminologie utile. Dans ce qui suit, nous aurons à utiliser des expressions du type "le 1 de poids faible", "les 0 de poids faible" et quelques autres du même genre. Quand nous parlerons du 0 de poids faible, nous voudrons parler du premier 0 que l'on croise dans un nombre en partant de sa droite. Par exemple, dans le nombre 0011 1011, le 0 de poids faible est le troisième bit en partant de la droite. Quand nous parlerons du 1 de poids faible, c'est la même chose, mais pour le premier bit à 1. Par exemple, dans le nombre 0110 1000, le 1 de poids faible est le quatrième bit. Quant aux expressions "le 1 de poids fort" et "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

Par contre, les expressions "LES 1 de poids faible" ou "LES 0 de poids faible" ne parlent pas de la même chose. Quand nous voudrons parler des 1 de poids faible, au pluriel, nous voulons dire : tous les bits situés avant le 0 de poids faible. Par exemple, prenons le nombre 0011 0011 : les 1 de poids faible correspondent ici aux deux premiers bits en partant de la droite. Même chose quand on parle des zéros de poids faible au pluriel. Quant aux expressions "les 1 de poids fort" ou "les 0 de poids fort" elles sont identiques aux précédentes, sauf qu'on parcourt le nombre à partir de sa gauche.

Les opérations que nous allons voir sont au nombre de 8 et elles s'expliquent facilement avec le schéma ci-dessous.

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.

Les quatre opération suivantes donnent la position des 0/1 de poids faible/fort :

• L'opération Find First Set, donne la position du 1 de poids faible.
• L'opération Find highest set donne la position du 1 de poids fort.
• L'opération Find First Zero donne la position du 0 de poids faible (le plus à droite).
• L'opération Find Highest Zero donne la position du 0 de poids fort (le plus à gauche).

Elles ont des opérations corolaires qui elles, comptent le nombre de 0/1 avant ou après des 0/1 de poids fort/faible.

• L'opération Count Trailing Zeros compte les zéros situés à droite du 1 de poids faible.
• L'opération Count Leading Zeros compte les zéros à gauche du 1 de poids fort.
• L'opération Count Trailing Ones compte les 1 situés à gauche du 0 de poids fort.
• L'opération Count Leading Ones compte les 1 situés à droite du 0 de poids faible.

Dans toutes ces opérations, les bits sont numérotés, leur numéro étant appelé leur position ou leur indice. La position d'un bit est donc donnée par ce numéro. Ces opérations varient selon la méthode utilisée pour numéroter les bits. On peut commencer à compter les bits à partir de 0, le 0 étant le numéro du bit de poids faible. Mais on peut aussi compter à partir de 1, le bit de poids faible étant celui de numéro 1. Ces deux conventions ne sont pas équivalentes.

Si on choisit la première convention, certaines opérations sont équivalentes. Par exemple, les opérations Count Trailing Zeros et Find First Set donnent toutes les deux le même résultat. Avec la première convention, pour un nombre codé sur $n$ bits, on a :

${\text{fhs}}+{\text{clz(n)}}=n-1$

${\text{fhz}}+{\text{clo(n)}}=n-1$

${\text{ffs}}={\text{ctz(n)}}$

${\text{ffz}}={\text{cto(n)}}$

On voit que certaines opérations sont équivalentes, ce qui nous arrange bien. Il y a deux classes d'opérations : celles à gauche dans les équations précédentes, celles à droite. Les premiers donnent la position du 0/1 de poids faible/fort, celles qui comptent des 0/1 de poids faibles/fort. Et les deux classes s'implémentent par des circuits très différents.

L'implémentation avec un encodeur à priorité

La première implémentation implémente les quatre calculs suivants :

• le Find First Set, abréviée FFS ;
• le Find Highest set, abrévié FHS ;
• le Find First Zero, abréviée FFZ ;
• le Find highest Zero, abrévié FHZ.

Implémenter chaque opération peut se faire avec un encodeur à priorité. Pour les quatre opérations précédentes, il existe un encodeur à priorité qui s'en charge. Par exemple, on peut utiliser un encodeur à priorité qui donne la position du 1 de poids fort, c’est-à-dire qui réalise l'opération Find Highest Set. Il existe aussi un autre encodeur à priorité qui lui donne la position du 1 de poids faible, ce qui correspond à l'opération Find First Set. Il existe aussi un encodeur qui donne la position du zéro de poids faible (Find First Zero) et un autre qui donne celle du zéro de poids fort (Find highest Zero).

Mais utiliser quatre encodeurs différents n'est pas l'idéal. Il est en effet possible de faire avec un seul encodeur. L'idée est qu'un encodeur à priorité est composé d'un encodeur normal, couplé à un circuit de priorité qui sélectionne le 0/1 de poids fort/faible. L'idée est de rendre ce circuit configurable, de manière à choisir l'opération voulue parmi les 4 précédentes.

Encodeur à priorité

Une autre méthode utilise un inverseur commandable. En, effet, les opérations FHS et FHZ peuvent se déduire l'une de l'autre, en inversant le nombre passé en entrée : les 0 de poids fort deviennent alors des 1 de poids fort, et vice-versa. Idem pour les opérations FFS et FFZ. En inversant l'entrée, le 1 de poids faible deviendra le 0 de poids faible et inversement. Inverser les bits de l'entrée se fait avec un inverseur commandable.

Circuit qui effectue les opérations FHS, FFS, CLZ et autres.

L'implémentation avec la population count

Maintenant, voyons comment implémenter les quatre opérations suivantes. Il s'agit des opérations qui comptent les 0 ou 1 de poids faible, et ceux de poids fort.

• L'opération Count Trailing Zeros donne le nombre de zéros situés à droite de ce 1 de poids faible.
• L'opération Count Leading Zeros donne nombre de zéros situés à gauche du 1 de poids fort.
• L'opération Count Trailing Ones donnent le nombre de 1 à gauche du 0 de poids fort.
• L'opération Count Leading Ones donne le nombre de 1 à droite du 0 de poids faible.

Les quatre opérations listées plus haut comptent un certain nombre de 0 ou 1. Compter des 1 ressemble beaucoup à ce que fait le circuit de population count. La différence est qu'ici, seuls certains bits sont à prendre en compte : ceux situés à droite/gauche d'un 0/1 de poids faible/fort. Or, nous avons déjà un outil pour ignorer certains bits : l'usage de masques avec des opérations bit à bit. L'idée est alors de générer un masque qui indique la position des 0/1 de poids faible/fort. Chaque bit du masque est associé au bit à la même place dans l'opérande, celui de même poids. Un bit du masque à 1 indique que le bit est à prendre en compte, alors qu'un bit à 0 indique un bit à ignorer.

Par exemple, prenons le cas où on veut compter le nombre de Trailing Zeros, à savoir les 0 de poids faible, ceux situés à droite du premier 1 rencontré en lisant l'opérande de droite à gauche. La première étape génère un nombre qui a un 1 à la place de chaque Trailing Zero, et un 0 ailleurs.

Opérande	0010 1101 1001 1000 0000
Masque	0000 0000 0000 0111 1111

Une fois le masque voulu obtenu, on compte le nombre de 1 dans le masque généré. En clair, on calcule sa population count. Le résultat donne le nombre voulu.

Le circuit qui génère le masque a une implémentation similaire à celle utilisée par un encodeur à priorité. Avec un encodeur à priorité qui calcul l'opération Find First Set, le circuit met à 0 les bits qui suivent le 1 de poids fort. Avec l'opération Count Leading Zero, le circuit fait la même chose, sauf que les bits sont mis à 1. Le circuit est construit de la même manière, comme illustré ci-dessous. Il s'agit de l'implémentation la plus simple, composée de briques qui mettent à 0/1 un bit de l'opérande, qui sont enchainés les uns à la suite des autres.

L'implémentation de l'opération CLZ avec la population count

Le circuit précédent met à 1 un bit à la fois. Une amélioration serait d'en traiter plusieurs à la fois. Par exemple, on peut imaginer un circuit qui traite des groupes de 4/5 bits. Pour chaque groupe, un circuit détecte les 1 de poids fort et met les bits suivants à 1. Le circuit peut se concevoir simplement avec un tableau de Karnaugh. Évidemment, pour enchainer plusieurs circuits, il faut gérer le cas où un 1 de poids fort a été détecté dans un groupe précédent et mettre toutes les sorties à 1 cas échéant, avec un circuit de mise à 111111 qu'on a déjà vu.

Implémentation optimisée de l'opération CLZ basée sur la POPCOUNT

Une version améliorée de cette technique a apparemment été utilisée par Intel dans certains de ces processeurs, le brevet "Combined set bit count and detector logic" détaille l'implémentation d'une technique similaire.

Les circuits générateurs/vérificateurs d'ECC

Au tout début de ce cours, nous avions vu les codes ECC, qui détectent ou corrigent des corruptions de données. Si un bit est altéré, ils permettent de détecter que le bit en question a été inversé, et peuvent éventuellement le corriger pour retrouver la donnée initiale. Les deux codes ECC les plus connus sont le bit de parité et les codes de Hamming. Et ils sont très liés à la population count. Dans ce qui suit, nous allons voir des circuits qui calculent soit un bit de parité, soit le code de Hamming d'un nombre.

Le générateur de bit de parité

Pour rappel, le bit de parité est une technique qui permet de détecter si une donnée a été corrompue. Elle permet de détecter qu'un bit a été inversé, à savoir qu'un bit censé être à 1 est passé à 0 ou inversement. Pour cela, on ajoute un bit de parité aux données à sécuriser, afin que le nombre de bits à 1 soit pair, bit de parité inclus. En clair, si la donnée a un nombre de bit à 1 pair, alors le bit de parité vaut 0. Mais si le nombre est impair, alors le bit de parité vaut 1. Dans cette section, nous allons voir un circuit qui calcule le bit de parité d'un opérande.

Intuitivement, on se dit qu'il faut compter les 1 dans l'opérande, avant de calculer sa parité et d'en déduire le bit de parité. Le bit de parité n'est ni plus ni moins que le bit de poids faible de la population count. Mais heureusement, il existe une autre méthode bien plus simple, plus rapide, et plus économe en circuits. Pour comprendre comment, nous allons commencer avec un cas simple : le calcul à partir d'un opérande de 2 bits. Le circuit étant simple, il suffit d'utiliser les techniques vues précédemment, avec la table de vérité. En écrivant la table de vérité du circuit, on remarque rapidement que la table de vérité donne la table de vérité d'une porte XOR.

Bit 1	Bit 2	Bit de parité
0	0	0
0	1	1
1	0	1
1	1	0

Pour la suite, nous allons partir d'un nombre de trois bits. On pourrait tenter de créer ce circuit à partir d'une table de vérité, mais nous allons utiliser une autre méthode, qui nous donnera un indice important. Ce nombre de 3 bits est composé d'un nombre de 2 bits auquel on a jouté un troisième bit. L'ajout de ce troisième bit modifie naturellement le bit de parité du nombre précédent. Dans ce qui va suivre, nous allons créer un circuit qui calcule le bit de parité final, à partir : du bit de parité du nombre de 2 bits, et du bit ajouté. On voit alors que la table de vérité est celle d'une porte XOR.

Bit de parité précédent	Bit ajouté	Bit de parité final
0	0	0
0	1	1
1	0	1
1	1	0

Chose assez intéressante, ce mécanisme fonctionne quel que soit le nombre de bits de l'opérande. Ajouter un bit à un nombre modifie sa parité, celle-ci état alors égale à : bit ajouté XOR bit-parité du nombre. L’explication est relativement simple : ajouter n 0 ne modifie pas le nombre de 1, et donc le bit de parité, tandis qu'ajouter un 1 inverse le bit de parité.

Circuit de parité

Avec cette logique, on peut créer un générateur de parité parallèle., un circuit qui calcule le bit de parité d'un opérande, en faisant un XOR entre tous ses bits. Effectué naïvement, il suffit d’enchaîner des portes XOR les unes à la suite des autres. En réfléchissant, on devine qu'on peut structurer les portes XOR comme illustré ci-contre.

Le circuit précédent calcule le bit de parité d'un opérande. Pour ce qui est de vérifier si une donnée est corrompue, rien de plus simple : il suffit de générer le bit de parité de la donnée seule, et de le comparer avec le bit de parité stocké dans la donnée avec la porte logique adaptée. Le circuit qui génère un bit de parité et celui qui vérifie si le bit de parité est valide sont donc très similaires.

Le générateur/checker d'ECC

Pour ce qui est des codes de Hamming, ils calculent plusieurs bits de parité, qui sont calculés en prenant en compte une partie des bits de l'opérande. Un circuit qui génère le code de Hamming est donc composé de plusieurs circuits de génération de parité. Idem pour un circuit qui vérifie le code de Hamming d'un opérande.

Hamming(7,4)

Par exemple, voici ci-dessous le circuit pour vérifier un code de Hamming de type 7,4. Pour rappel, celui-ci prend des données sur 4 bits, et leur ajoute 3 bits de parité, ce qui fait en tout 7 bits : c'est de là que vient le nom de 7-4-3 du code. Chaque bit de parité se calcule à partir de 3 bits du nombre. Le schéma ci-contre indique quels sont les bits de données utilisés pour calculer un bit de parité : les bits de parité sont notés p, les bits de données d.

Le circuit est composé d'une première couche de portes XOR qui calculent le code de Hamming des 4 bits de données. Une seconde couche de portes XOR compare ce code calculé avec les trois bits d'ECC présents dans l'opérande. Si les deux valeurs correspondent, il n'y a pas d'erreur. Mais si les bits ne correspondent pas, alors on sait quel bit est erroné en regardant quel bit d'ECC est invalide. Une couche de portes ET/NON sert de pseudo-décodeur, qui sélectionne le bit à corriger. Elle génère un masque de 4 bits qui indique quel bit inverser : celui dont le bit du masque est à 1. La dernière couche de portes XOR prend ce masque et l'applique aux 4 bits de données, ce qui inverse le bit adéquat.

Circuit de vérification d'un code de Hamming 7,4.

Pour ce qui est de calculer l'ECC en logiciel, c'est assez simple si on dispose d'une opération de population count. Il suffit d'appliquer un masque avant de calculer le bit de parité via la population count. Le masque adéquat est appliqué pour sélectionner les bits adéquats de l'opérande, puis on calcule la population count et ne garde que le bit de poids faible. En appliquant la procédure précédente pour toutes les combinaisons de bits d'opérandes nécessaires, on obtient les différents bits de parités. Il ne reste alors qu'à les combiner entre eux pour obtenir les données d'ECC nécessaires.