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

Dans ce chapitre, nous allons voir les opérations de manipulation de bits, des opérations qui manipulent les bits d'un opérande. La différence avec les opérations bit à bit est que les bits de colonnes différentes peuvent être combinés entre eux pour fournir leur résultat, elles peuvent les faire changer de place, en supprimer, en ajouter, etc. Mais cela deviendra plus compréhensible en voyant quelques exemples d'opérations de ce genre.

L'opération de population count

L'opération de population count compte le nombre de bits à 1 d'un opérande entier. Elle est très utilisée quand on manipule des tableaux de bits, pour le codage/décodage vidéo/audio, pour 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 parlent de l'opération elle-même, mais pas des circuits pour la calculer, erreur que nous ne ferons pas.

Le circuit de population count : les compteurs parallèles

La population count est un cas particulier d'addition multiopérande, où chaque opérande fait 1 bit. En effet, pour calculer la population count d'un opérande de N bits, il faut additionner ces N bits entre eux. Et les techniques vues dans le chapitre sur l'addition multiopérande marchent aussi pour la population count. La technique la plus simple est celle dite du diviser pour régner. L'idée est que si on découpe l'opérande en deux, la population count est la somme des population count de chaque partie. Par exemple, pour calculer la population count d'un entier 32 bits (4 octets), on peut additionner les population count des 4 octets de l'opérande. Pour cela, il faut fabriquer des circuits capables d'additionner entre 2 et 7 bits, appelés des parallel counters, terme que nous traduirons par compteurs parallèles.

Il se trouve que nous avons déjà vu des compteurs parallèles dans les chapitres précédents. Les additionneurs complets sont des compteurs parallèles 3 bits, les demi-additionneurs sont des compteurs parallèle 2 bits. Pour rappel, le premier additionne trois bits, alors que le second additionne deux bits. Dans ce qui suit, nous allons utiliser les abréviations suivantes : FA (Full-Adder) pour additionneur complet, HA (Half-Adder) pour demi-additionneur.

Le calcul de la population count peut donc utiliser des FA comme compteurs parallèles. Un tel additionneur regroupe les bits de l'opérande par triplets et additionne chaque triplet avec un FA. S'il reste une paire de bits isolées après avoir formé les triplets, elle est additionnée avec un HA. Les FA/HA calcule des population count intermédiaires codées sur 2 bits, qui sont ensuite additionnées par l'additionneur multi-opérande. Le circuit ne paye pas de mine, mais c'est un circuit de ce style qui a été utilisé sur le processeur ARM1, un des tout premier CPU ARM, prévu pour les premiers iPhones.

Le circuit précédent additionne un grand nombre de résultat intermédiaires codées sur 2 bits. L'idéal serait pourtant l'inverse : moins d'opérandes à additionner, mais celles-ci sont plus longues. Pour cela, il faut remplacer les FA par des compteurs parallèles qui fournissent des résultats codés sur 4, 5, 6, 7 bits, parfois plus. Intuitivement, on se dit qu'il faudrait découper les opérandes en groupes de 4, 8, 16 bits, ou toute autre puissance de deux. Sauf que ce n'est pas l'idéal. Par exemple, 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. Sur 5 bits, cela permet de gérer 63 bits d'entrée. À chaque fois, il nous manque un bit pour avoir un groupe bien rond de 4, 8, 16 bits. La raison est qu'il faut encoder le zéro pour le résultat.

Les compteurs parallèles peuvent être construits comme n'importe quel circuit combinatoire, à partir de la table de vérité. Mais ils peuvent aussi être construits en combinant des compteurs parallèles plus petits avec un additionneur. Il s'agit de l'implémentation la plus simple, la moins optimisée, la plus gourmande en portes logiques. Heureusement, des simplifications sont possibles, comme on le verra dans la suite du chapitre.

Les compteurs parallèles de moins de 8 bits

Dans cette section, nous allons voir comment créer des compteurs parallèles en utilisant des FA/HA, couplés à un additionneur. Nous simpliferons ces circuits par la suite. Le premier exemple intéressant est le compteur parallèle 4 bits, qui prend 4 bits d'opérande et fournit un résultat de 3 bits. Premièrement, il additionne les bits d'opérande deux par deux, avec deux HA/ Les deux résultats de 2 bits sont ensuite additionnés avec un additionneur 2 bits. Le circuit final est le suivant :

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

Pour les compteurs parallèles de plus de 4 bits, il devient intéressant d'additionner les bits par groupes de 3, par triplet. Les bits d'un triplet sont additionnés avec un FA, ce qui donne un résultat sur deux bits. Le compteur parallèle 5 bits est construit sur le même modèle. Il calcule la population count d'une paire de bit et d'un triplet de bit, et additionne le tout avec un additionneur 2 bits.

Pour un compteur de 6 bits, la première couche ne contient que des FA, tout en conservant l'additionneur 2 bits.

Dans l'exemple précédent, il est intéressant d'ajouter un 7ème bit d'opérande, pour profiter de l'entrée de retenue de l'additionneur. En effet, tous les additionneurs dignes de ce nom disposent d'une entrée de retenue, utilisée pour l'incrémentation ou d'autres opérations. Elle permet d'ajouter un bit en plus, sur la colonne des bits de poids faible. Et bien on peut rajouter un 7ème bit sur cette entrée. Et dans le cas général, au lieu d'additionner des triplets de bits, on peut rajouter un bit en plus.

Les simplifications liées aux demi-additionneurs

Les compteurs vus plus haut peuvent être simplifiés, afin de faire des économies de portes logiques. Les compteurs parallèle de 6 et 7 bits ne peuvent pas se simplifier facilement, mais ceux de 4 et 5 bits le peuvent. Les simplifications sont liés au fait que ces deux circuits intégrent des paires de HA en série, à savoir que le second prend l'entrée du premier. Et à une porte logique près, ces deux HA en série forment un FA.

Pour le compteur parallèle 5 bits, la simplification donne le circuit suivant. Le circuit originel avait deux HA et deux FA, cette version simplifié élimine un HA, ce qui fait une petite économie de circuits. Avec cette simplification, on perd l'organisation en deux couches : une couche de FA/HA qui calcule la population count de paires/triplets de bits, suivi par un additionneur 2 bits. Mais le seul désavantage est que le circuit est moins simple à expliquer, ce qui est juste un petit défaut.

Pour le compteur parallèle 4 bits, une implémentation alternative donne le circuit suivant. Le circuit incorpore un FA et deux HA, contre 4 HA avec le circuit de base. Sachant qu'un FA contient 2 HA et une porte logique, le circuit n'économise pas de portes logiques. Notez que ce circuit peut être interprété comme un FA couplé à un additionneur. Précisément, il additionne trois bits, puis décide d'incrémenter le résultat ou non suivant la valeur du quatrième bit. Le circuit est donc composé d'un FA suivi par un incrémenteur commandable (son entrée de retenue est configurable).

Compteur parallèle de 4 bits, version alternative

Les adders compressors : fusionner des additionneurs complets

Nous venons de voir une simplification assez basique, à savoir fusionner plusieurs HA en un seul FA. Mais est-ce qu'il existe un équivalent pour les FA ? A savoir un circuit qui fusionne plusieurs FA en un seul circuit amélioré ? intuitivement, on se dit que non, car un tel circuit serait tout sauf intuitif pour ce qui est des retenues. Sauf que la réponse est oui, il existe des circuits qui fusionnent plusieurs FA entre eux et fournit exactement les mêmes sorties que les FA fusionnés. De tels circuits sont appelés des adder compressors.

Les adder compressors sont utilisés dans le cadre de l'addition multiopérande en général, pas seulement pour le calcul de la population count. Ils sont surtout utilisés dans les additionneurs multiopérandes en arbre. Les arbres de Wallace ou de Dadda peuvent être modifiés de manière à fusionner des FA d'une même couche, en les remplaçant par des adder compressors. Mais la construction de l'arbre d'additionneur est alors beaucoup plus complexe, ce qui explique pourquoi je n'en ai pas parlé dans le chapitre sur l'addition multiopérande.

Les adder compressors fournissent le bit de poids faible du résultat et les différentes retenues des additions intermédiaires fournies par les FA fusionnés. Par exemple, prenons le compteur parallèle de 5 bits, composé de deux FA placés l'un à la suite de l'autre, avec un HA qui additionne les deux retenues produites par les deux FA. Les deux FA peuvent être remplacés par un mal-nommé adder compressor 4:2, qui prend 5 bit d'opérande et fournit les trois mêmes sorties que les deux FA : le bit de poids faible du résultat final, les deux retenues des additions intermédiaires. Les retenues doivent être combinées ensemble par des circuits à part, pour obtenir un compteur parallèle. Dans le cadre de l'addition multiopérande, les retenues sont simplement propagées à la colonne suivante, elles sont envoyées en entrée d'un autre adder compressor.

L'avantage est que le calcul du bit de somme est simplifié. Le mieux est de partir de l'exemple avec un compteur parallèle 5 bits, avec ses deux FA en série. Voici ce que l'on obtient en enchainant deux FA, au niveau des XOR :

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.

En clair, la fusion des FA permet de 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. Un adder compressor utilise l'arbre des portes XOR idéal, mais calcule 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.

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.

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.

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.

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.

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é permet de détecter qu'un bit a été inversé, à savoir qu'il est passé de 1 à 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, le bit de parité vaut 0 si la donnée a un nombre de bits à 1 pair, il vaut 1 si ce nombre est impair. 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é est donc le bit de poids faible de la population count. Le bit de parité se calcule donc en additionnant les bits de l'opérande, mais sans tenir compte des bits de poids fort, sans tenir compte des retenues, en ne conservant que le bit de somme. Lors de l'addition de deux bits, ce bit de somme est calculé en faisant un XOR entre les deux bits à additionner. Pour N bits, il suffit d'enchainer N-1 portes XOR. 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. 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

Les codes de Hamming calculent plusieurs bits de parité, qui sont chacun calculés en prenant en compte certains bits de l'opérande. Par exemple, le code de Hamming de type 7,4 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.

L'implémentation matérielle est donc très simple : un circuit qui génère un code de Hamming est 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. Étudions par exemple le circuit suivant, conçu pour le code 7-4-3. Il vérifie si les 4 bits de données sont valides, à savoir si les trois bits d'ECC collent bien aux données associées. 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. Le circuit corrige alors le bit erroné.

En premier lieu, le circuit calcule le code de Hamming des 4 bits de données, avec une première couche de portes XOR. Le résultat est alors comparé avec les trois bits d'ECC présents dans l'opérande, par un comparateur d'égalité, lui-même construit avec des portes XOR. Le tout est suivi par un circuit de correction d'erreur. Une couche de portes ET/NON 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.

◄ Retour vers « Les circuits pour la multiplication et la division »

Sommaire du livre

Continuer vers « Les circuits de calcul flottant » ►