Additionneur à anticipation de retenue : plus rapide que la propagation

Un additionneur à anticipation de retenue restructure la génération des retenues grâce aux signaux de propagation et de génération. Déduisez un CLA 4 bits, puis découvrez pourquoi les conceptions réelles sont hiérarchiques.

Denny

7 mai 20268 min de lecture

Chalkboard feature illustration for “Additionneur à anticipation de retenue : plus rapide que la propagation”

En bref : l’anticipation de retenue réécrit la récurrence sérielle $C_{i+1}=G_i+P_iC_i$ avec des signaux de génération/propagation par bit et par groupe. Un petit CLA plat peut exprimer plusieurs retenues directement à partir des opérandes. Les versions hiérarchiques et à préfixe parallèle réduisent la profondeur de retenue, de linéaire à presque logarithmique, au prix de cellules, de fan-out et de câblage supplémentaires.

Un additionneur à propagation de retenue de 4 bits est simple : enchaînez quatre additionneurs complets et dirigez chaque $C_{out}$ vers le $C_{in}$ suivant. Sa dépendance de retenue dans le pire cas grandit avec la largeur du mot. Le respect du timing dépend de la technologie, de l’horloge visée, des cellules et du chemin de données environnant ; la largeur seule ne rend pas une conception « inacceptable ».

Les additionneurs à anticipation de retenue (CLA) attaquent cette dépendance sérielle en déduisant les retenues à partir de signaux intermédiaires directement disponibles sur les opérandes.

Pourquoi la propagation de retenue est-elle lente ?

Rappelons les équations de l’additionneur complet :

$S_i = A_i \oplus B_i \oplus C_i$ $C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

La somme $S_i$ dépend de $C_i$ , et la retenue $C_{i+1}$ dépend également de $C_i$ . La chaîne de dépendances est donc $C_0 \to C_1 \to C_2 \to \dots \to C_n$ . Si un étage de retenue prend $t_c$ , le temps total d’addition dans le pire cas est environ :

$T_{ripple} \approx n \cdot t_c + t_{sum}$

La dépendance du premier ordre est linéaire avec la largeur du mot. Les nanosecondes absolues exigent une implémentation précise ; le nombre de délais de portes ne sert ici qu’à comparer les topologies. C’est ce type de limite du délai de propagation qui motive les réseaux de retenue rapides.

Génération et propagation

Reprenons l’équation de retenue :

$C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

Le premier terme, $A_i B_i$ , est vrai exactement lorsque les deux bits opérandes valent 1. L’étage $i$ produit alors inconditionnellement une retenue de sortie, quelle que soit la valeur arrivée sur $C_i$ . Définissons :

$G_i = A_i \cdot B_i$

C’est le signal de génération : l’étage $i$ génère lui-même une retenue.

Le second terme, $(A_i \oplus B_i) C_i$ , signifie que si exactement un des bits opérandes vaut 1, la retenue reçue sur $C_i$ traverse l’étage. Définissons :

$P_i = A_i \oplus B_i$

C’est le signal de propagation : l’étage transmet toute retenue entrante à sa sortie.

L’équation de retenue devient :

$C_{i+1} = G_i + P_i \cdot C_i$

Ce sont les portes ET et OU que vous connaissez, effectuant exactement ce que décrivent leurs tables de vérité, mais réunies ici dans une récurrence que l’on peut aplatir.

Aplatir la récurrence des retenues

Substituons la récurrence en elle-même. En partant d’un $C_0$ connu :

$C_1 = G_0 + P_0 C_0$

$C_2 = G_1 + P_1 C_1 = G_1 + P_1(G_0 + P_0 C_0) = G_1 + P_1 G_0 + P_1 P_0 C_0$

$C_3 = G_2 + P_2 C_2 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$

$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$

Le motif est net : chaque retenue $C_{i+1}$ est une somme de produits de signaux de génération et de propagation des étages 0 à $i$ . Logiquement, elle dépend seulement de $G$ , $P$ et $C_0$ , et non d’une transition physique achevée dans l’additionneur complet précédent. Physiquement, les produits larges et leur câblage exigent toujours des portes, buffers et routage finis.

Exemple détaillé sur 4 bits

Additionnons $A=1011_2$ (11) et $B=0110_2$ (6), avec $C_0=0$ . Écrivons les bits en commençant par le poids faible :

Bit $i$	$A_i$	$B_i$	$P_i=A_i\oplus B_i$	$G_i=A_iB_i$	$C_i$	$S_i=P_i\oplus C_i$
0	1	0	1	0	0	1
1	1	1	0	1	0	0
2	0	1	1	0	1	0
3	1	0	1	0	1	0

Les équations donnent $C_1=0$ , $C_2=1$ , $C_3=1$ et $C_4=1$ . La lecture de $C_4S_3S_2S_1S_0$ produit $10001_2=17$ , comme prévu. L’arithmétique est la même qu’avec la propagation de retenue ; seule la topologie du réseau de retenue change.

Génération et propagation par groupe

Pour un groupe de bits allant de $i$ à $j$ , définissons une propagation et une génération de groupe :

$P_{j:i}=P_jP_{j-1}\cdots P_i$

$G_{j:i}=G_j+P_jG_{j-1}+\cdots+P_jP_{j-1}\cdots P_{i+1}G_i$

La retenue quittant le groupe vaut alors :

$C_{j+1}=G_{j:i}+P_{j:i}C_i$

Deux groupes adjacents se combinent avec la même opération :

(G_H,P_H)\circ(G_L,P_L) = (G_H+P_HG_L,\;P_HP_L)

Cette associativité est la clé des additionneurs hiérarchiques et à préfixe parallèle : les paires se combinent, puis les paires de paires, formant un arbre plutôt qu’une chaîne.

Architecture d’un CLA 4 bits

Au niveau booléen, un CLA plat 4 bits possède trois fonctions :

Couche génération/propagation. $n$ portes ET produisent $G_i=A_iB_i$ en un délai ; $n$ portes XOR produisent $P_i=A_i\oplus B_i$ en un délai. Elles fonctionnent en parallèle.
Réseau de retenue. Une logique ET-OU calcule $C_1$ à $C_4$ à partir des formules développées. Avec des portes à fan-in théoriquement illimité, cela ressemble à deux niveaux logiques ; une bibliothèque réelle décompose les termes larges, ce qui augmente profondeur et charge.
Couche somme. $n$ portes XOR produisent $S_i=P_i\oplus C_i$ en un délai. (Notez que $S_i=A_i\oplus B_i\oplus C_i=P_i\oplus C_i$ une fois $P_i$ calculé.)

Sur quatre bits, ce montage peut raccourcir le chemin de retenue par rapport à une chaîne de cellules additionneur complet. Étendre indéfiniment les équations plates n’est pas pratique ; les CLA plus grands introduisent donc des groupes.

Schéma fonctionnel d’un CLA 4 bits

A0,B0 ─┬── XOR ── P0 ──┐                           ┌── XOR ── S0
       └── AND ── G0 ──┤                           │
                       │   ┌─── carry network ───┐ │
A1,B1 ─┬── XOR ── P1 ──┤   │                     │ ├── XOR ── S1
       └── AND ── G1 ──┤   │   computes          │ │
                       ├──>│   C1, C2, C3, C4    │─┤
A2,B2 ─┬── XOR ── P2 ──┤   │   from expanded     │ ├── XOR ── S2
       └── AND ── G2 ──┤   │                     │ │
                       │   │   carry expressions  │ │
                       │   └─────────────────────┘ │
A3,B3 ─┬── XOR ── P3 ──┤                           ├── XOR ── S3
       └── AND ── G3 ──┘                           │
                                                   └────────── C4
C0 ──────────────────────>┘

Fan-in, câblage et coût caché

Pour $C_4$ , la plus longue expression plate contient un terme produit à cinq entrées lorsque $C_0$ est inclus. Pour $C_{16}$ , le terme correspondant comporterait 17 entrées. Les bibliothèques de cellules standard offrent un fan-in limité, et les longues pistes ainsi que les fortes charges ajoutent du délai. Un CLA littéralement plat cesse donc de bien passer à l’échelle, même si son expression booléenne semble peu profonde.

La solution habituelle est la hiérarchie. Regroupez les bits — souvent par blocs de quatre —, calculez les $G$ et $P$ de groupe, puis combinez ces groupes à un autre niveau. Une conception 16 bits peut utiliser quatre groupes de 4 bits, puis un second étage d’anticipation. Les additionneurs à préfixe parallèle appliquent l’opération de groupe associative dans tout un arbre.

Le compromis ne se résume pas à un tableau universel de portes :

Architecture	Dépendance de retenue	Force habituelle	Coût habituel
Propagation de retenue	Linéaire	Petite surface, routage simple	Long chemin de retenue dans le pire cas
Anticipation par blocs	Hiérarchique	Compromis vitesse/surface modéré	Logique locale et câblage de groupes plus larges
Sélection de retenue	Pré-calcul des deux cas	Chemin de décision plus court	Matériel de somme dupliqué
Préfixe parallèle	Structure arborescente	Faible profondeur logique	Davantage de cellules de préfixe, câblage et parfois fan-out élevé

Le délai, la surface et l’énergie réels doivent être mesurés après mappage et implémentation physique. Une topologie gagnante en niveaux de portes abstraits peut perdre une fois congestion, buffers et charge inclus.

Au-delà du CLA : additionneurs à préfixe parallèle

L’idée d’anticipation de retenue se généralise. La récurrence $C_{i+1}=G_i+P_iC_i$ est associative avec un opérateur personnalisé : on peut apparier des positions adjacentes, puis des paires de paires, en arbre. C’est la famille des préfixes parallèles :

Kogge–Stone — faible profondeur de préfixe et fan-out logique borné, mais câblage dense et nombreux nœuds.
Brent–Kung — moins de nœuds de préfixe et moins de câblage, avec une profondeur plus grande.
Han–Carlson, Ladner–Fischer, Sklansky — autres compromis entre fan-out, complexité du câblage et profondeur.

Les additionneurs de production peuvent aussi mélanger les structures de préfixe, utiliser la parcimonie ou placer une logique de sélection autour de certains groupes. Le choix se fait selon un budget précis de timing, surface, puissance et routage ; la seule fréquence d’horloge d’un processeur ne révèle pas la topologie de son additionneur.

Implémenter un CLA dans DigiSim

Vous pouvez construire un CLA 4 bits à partir de primitives : quatre portes ET pour la génération, quatre portes XOR pour la propagation, les équations de retenue ci-dessus et quatre XOR finaux pour la somme. Les composants additionneur et additionneur 8 bits sont des commodités comportementales de haut niveau ; ne déduisez pas leur architecture interne sans indication de la documentation.

Pour comparer les topologies, enchaînez quatre additionneurs complets en propagation et construisez un CLA 4 bits séparé. Vérifiez d’abord l’équivalence fonctionnelle pour toutes les combinaisons d’opérandes. Puis, si le simulateur modélise le délai par porte, comparez le temps de stabilisation maximal après une variation d’entrée. Si les portes sont idéales, comptez plutôt les niveaux logiques dépendants : une forme d’onde idéale ne prédit pas le timing du silicium.

Pièges courants

Oublier que $P_i$ utilise XOR et non OU. Les deux définitions — $P_i=A_i+B_i$ ou $P_i=A_i\oplus B_i$ — produisent une retenue correcte, car le cas $A_i=B_i=1$ est déjà couvert par $G_i$ . Le XOR est préférable car le même fil alimente la somme : $S_i=P_i\oplus C_i$ . Avec un $P_i$ défini par OU, cette réutilisation ne fonctionne plus et il faut un XOR séparé pour la somme.
Sous-estimer le fan-in. Une expansion plate sur 16 bits comporte un terme à 17 littéraux lorsque $C_0$ est inclus. Les conceptions larges pratiques décomposent ou regroupent la logique.
Supposer que le CLA est toujours plus rapide. Pour de petites largeurs, une propagation peut gagner en surface et respecter aisément le timing. Il n’existe pas de largeur seuil indépendante de l’architecture.
Confondre les chemins critiques de somme et de retenue. La profondeur du réseau de retenue domine le délai total, mais le XOR final de somme ajoute encore un délai de porte. Spécifier le délai comme la seule « profondeur du réseau de retenue » est une erreur fréquente.

Et ensuite ?

Continuez avec Fonctionnement d’une UAL : l’unité arithmétique et logique à partir des portes, puis l’additionneur de Booth expliqué pour une autre optimisation arithmétique.

Pour comparer les deux architectures d’additionneur, ouvrez le modèle d’additionneur complet avec retenue, enchaînez quatre instances comme additionneur à propagation et observez la propagation bit par bit sur l’analyseur logique. Construisez ensuite le CLA 4 bits équivalent avec les équations de cet article et mesurez les deux circuits : toute la raison d’être des UAL rapides est là.