Chaque add, sub, cmp et inc qu’exécute le CPU passe par l’ALU, l’unité arithmétique et logique, et au cœur de l’ALU se trouve un additionneur. Ce chapitre en construit un à partir des portes du chapitre précédent, puis l’étend en une ALU qui produit aussi les drapeaux que lit le niveau de l’assembleur.
Additionner deux bits : le demi-additionneur
Additionner deux nombres d’un bit donne un résultat de 0 à 2 : il faut donc deux bits de sortie, une somme et une retenue. Leurs tables de vérité sont deux portes déjà connues :
- Somme = A XOR B (1 quand exactement une entrée vaut 1) ;
- Retenue = A AND B (1 seulement pour 1 + 1).
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Adds two bits: Sum = A XOR B, Carry = A AND B. The two outputs read together as a 2-bit number, A + B.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
On l’appelle demi-additionneur parce qu’il ne peut pas recevoir de retenue venant d’un bit de poids inférieur.
Additionner trois bits : l’additionneur complet
Au milieu d’une addition sur plusieurs bits, chaque colonne additionne trois bits : A, B et la retenue entrante venue de la colonne de droite. Un additionneur complet (full adder) le fait, avec deux demi-additionneurs et un OR :
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Two half adders plus an OR: Sum = A ⊕ B ⊕ Cin, Cout = AB + (A ⊕ B)·Cin. It adds three bits, so full adders chain: each one's Cout is the next one's Cin.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
- Somme = A ⊕ B ⊕ Cin : 1 quand un nombre impair d’entrées vaut 1.
- Retenue sortante = AB + (A ⊕ B)·Cin : 1 quand au moins deux entrées valent 1. C’est la fonction majorité du chapitre précédent, sous une autre forme.
Additionner des nombres : l’additionneur à propagation de retenue
Enchaînez n additionneurs complets, la retenue sortante de chacun alimentant la retenue entrante du suivant, et vous additionnez deux nombres de n bits. La retenue entrante du bit 0 vaut normalement 0 :
Four full adders, the carry rippling from bit 0 (top) to bit 3. Each stage adds two gate delays to the carry path, so the worst case (e.g. 1111 + 0001) takes about 2n gate delays: step through it to watch the carry travel.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
On part de 1111 + 0000 = 1111. Désactivez auto, puis mettez B0 à 1 et appuyez plusieurs fois sur step pour voir 1111 + 0001 se résoudre. La retenue quitte le bit 0, ce qui fait produire une retenue au bit 1, puis au bit 2, puis au bit 3. Le résultat, 1 0000, n’est juste qu’une fois que la retenue s’est propagée à travers tous les étages. Il faut 8 délais de porte pour que tout se stabilise, et le chemin le plus long de l’additionneur en compte 9.
Chaque étage ajoute environ deux délais de porte à la chaîne de retenue : un additionneur à propagation de n bits en prend donc environ 2n. C’est acceptable pour 4 bits, mais un additionneur de 64 bits demanderait environ 128 délais de porte, alors qu’un cycle d’horloge d’un CPU à 4 GHz ne dure que 250 ps — de l’ordre de 15 à 25 délais de porte. L’additionneur doit finir en un cycle : les vrais CPU utilisent donc des conceptions plus rapides.
Des additionneurs plus rapides
- Sélection de retenue (carry select). Coupez l’additionneur en une moitié basse et une moitié haute, et construisez la moitié haute deux fois : une fois en supposant une retenue entrante de 0, une fois de 1. Les deux travaillent pendant que la moitié basse calcule, et quand sa vraie retenue arrive, un multiplexeur choisit le bon résultat. Le travail est dupliqué, mais le temps est à peu près divisé par deux, et l’astuce peut se réappliquer dans chaque moitié.
- Anticipation de retenue (carry lookahead). Chaque position de bit peut savoir tôt si elle va générer une retenue (g = A·B) ou propager une retenue entrante (p = A ⊕ B). La retenue sortant du bit i vaut alors cᵢ₊₁ = gᵢ + pᵢ·cᵢ, et en développant cette formule, un circuit calcule plusieurs retenues directement à partir des g et des p au lieu de les attendre une par une.
- Les additionneurs à préfixe parallèle (Kogge–Stone, Brent–Kung, et d’autres) organisent ces combinaisons de g/p en arbre : une retenue sur 64 bits prend environ log₂ 64 = 6 niveaux au lieu de 64 étages. C’est ce qu’utilisent les additionneurs rapides des CPU : plus de portes en échange de beaucoup moins de délai.
La soustraction est une addition
L’additionneur sait aussi soustraire. En complément à deux, −B = NOT B + 1, donc :
A − B = A + (NOT B) + 1
Une ALU soustrait en inversant B et en mettant la retenue entrante à 1. Voici 7 − 5, sous la forme 0111 + 1010 + 1 :
Four full adders, the carry rippling from bit 0 (top) to bit 3. Each stage adds two gate delays to the carry path, so the worst case (e.g. 1111 + 0001) takes about 2n gate delays: step through it to watch the carry travel.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Les quatre bits de somme valent 0010 = 2. La retenue sortante vaut 1, ce qui, pour une soustraction, signifie « pas d’emprunt ». C’est pourquoi le x86 met CF à l’inverse de la retenue sortante de l’additionneur après un sub ou un cmp : CF = 1 signifie que la soustraction a dû emprunter, c’est-à-dire A < B en non signé. Le même additionneur, alimenté différemment, sert à add, sub, cmp, inc, dec et neg.
L’ALU : une tranche par bit
Une ALU calcule l’une de plusieurs opérations sur deux entrées, choisie par des lignes de contrôle. La conception classique est la tranche de bit (bit slice) : un petit circuit pour une position de bit, qui contient les opérations logiques et un additionneur complet, avec un multiplexeur qui choisit quel résultat sortir. Placez 64 tranches côte à côte, chaînez leurs retenues, et vous obtenez une ALU de 64 bits.
Every function is computed in parallel (AND, OR, full-adder sum, XOR) and a 4-to-1 multiplexer picks one: Op 00 = AND, 01 = OR, 10 = ADD, 11 = XOR. Cout is the adder's carry. Chain 64 of these slices, carry to carry, and you have the ALU of a 64-bit CPU.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
Ici Op1·Op0 choisit l’opération : 00 = AND, 01 = OR, 10 = ADD, 11 = XOR. Avec A = B = 1 et ADD sélectionné, la tranche sort une somme de 0 et une retenue de 1. Passez à AND, OR ou XOR et seul le multiplexeur change. Chaque porte calcule en permanence ; les lignes de contrôle ne font que choisir quel résultat sort.
Les tranches de bits étaient autrefois de vraies puces que les concepteurs achetaient et câblaient ensemble. Aujourd’hui, ce sont des blocs d’une bibliothèque de conception, répliqués par logiciel, mais l’idée est la même. La tranche d’ALU de Tanenbaum a aussi des entrées pour forcer A ou B à zéro et pour inverser A. Ces contrôles supplémentaires permettent à un seul circuit de calculer des résultats comme B, −A ou A + 1 sans matériel dédié.
D’où viennent les drapeaux
L’ALU rapporte aussi des faits sur son résultat : ce sont les drapeaux que positionne cmp et que lisent les sauts conditionnels. Chacun ne coûte que quelques portes de plus :
| Drapeau | Signification | Circuit |
|---|---|---|
| ZF | le résultat est nul | NOR de tous les bits du résultat |
| SF | le résultat est négatif | le bit de poids fort du résultat |
| CF | retenue (ou emprunt) non signée | la retenue sortant du bit de poids fort (inversée pour la soustraction sur x86) |
| OF | débordement signé | retenue entrant dans le bit de poids fort XOR retenue qui en sort |
Le débordement est le plus subtil. Un débordement signé se produit quand deux nombres de même signe donnent un résultat de l’autre signe — exactement quand la retenue qui entre dans le bit de poids fort diffère de celle qui en sort. Essayez sur 4 bits :
Four full adders, the carry rippling from bit 0 (top) to bit 3. Each stage adds two gate delays to the carry path, so the worst case (e.g. 1111 + 0001) takes about 2n gate delays: step through it to watch the carry travel.
Unit-delay model: every gate takes one step to react. With auto off, toggle switches and press step to watch the change travel gate by gate.
0111 + 0001 = 1000. En non signé, c’est 7 + 1 = 8, correct, sans retenue sortante : CF = 0. En signé sur 4 bits, c’est 7 + 1 = −8, ce qui est faux. Une retenue est entrée dans le bit 3 mais aucune n’en est sortie : OF = 1. Les mêmes bits, lus de deux façons, donnent deux drapeaux différents. C’est pourquoi le x86 a des sauts distincts pour les comparaisons non signées (jb, ja, qui lisent CF) et signées (jl, jg, qui lisent SF et OF).
Au-delà de l’additionneur
Le reste d’une unité entière utilise des briques semblables :
- un décaleur déplace les bits vers la gauche ou la droite. Un barrel shifter décale de n’importe quelle quantité en une étape, avec des couches de multiplexeurs qui décalent de 1, 2, 4, 8… positions ;
- un multiplieur est essentiellement une foule d’additionneurs : des produits partiels additionnés en arbre, d’où les quelques cycles de
imulau lieu d’un seul ; - un diviseur travaille en général de façon itérative, quelques bits par cycle, d’où la lenteur de
div.
À retenir
- Un demi-additionneur, c’est XOR + AND. Un additionneur complet additionne trois bits, et sa retenue est la fonction majorité.
- Un additionneur à propagation de retenue enchaîne des additionneurs complets : son délai croît avec la largeur, environ 2n délais de porte.
- Les additionneurs à sélection de retenue, à anticipation de retenue et à préfixe parallèle dépensent plus de portes pour le ramener à environ log n.
- La soustraction, c’est A + NOT B + 1 : un seul additionneur sert à
add,sub,cmp,inc,decetneg. - Une ALU est une rangée de tranches de bits, avec un multiplexeur par tranche. ZF, SF, CF et OF ne sont que quelques portes de plus sur son résultat et ses retenues.