Additionneur qui calcule les retenues en parallèle à partir des signaux de génération g = a·b et de propagation p = a ⊕ b de chaque rang, sans attendre leur propagation depuis les rangs inférieurs. Le délai reste faible même pour de nombreux bits. Aussi appelé additionneur carry-lookahead.
Nom japonais: 桁上げ先見加算器
Domaine: Arithmétique des ordinateurs
Pour chaque bit d'entrées a et b, le signal de génération g = a·b vaut 1 lorsque le bit produit une retenue quelle que soit la retenue entrante, et le signal de propagation p = a ⊕ b vaut 1 lorsqu'une retenue entrante le traversera. La retenue sortante est c(i+1) = g(i) + p(i)·c(i), et la somme est s(i) = p(i) ⊕ c(i). En développant la récurrence, on obtient c1 = g0 + p0·c0 et c2 = g1 + p1·g0 + p1·p0·c0 : chaque retenue peut donc s'écrire en logique à deux niveaux à l'aide des seuls signaux g et p et de la retenue d'entrée c0.
Dans un additionneur à propagation de retenue (ripple-carry), chaque additionneur complet doit attendre la retenue du bit inférieur. Dans le pire cas, par exemple en ajoutant 1 à un mot ne contenant que des 1, la retenue traverse tous les bits, de sorte que le délai croît linéairement avec la largeur ; un additionneur ripple-carry de 64 bits est bien trop lent pour un processeur cadencé à plusieurs gigahertz. Un additionneur à retenue anticipée (CLA) calcule les retenues directement à partir des entrées, en parallèle, et avec une anticipation hiérarchique son délai ne croît qu'avec le logarithme de la largeur.
Les équations de retenue entièrement développées exigent vite des portes à trop d'entrées ; les conceptions réelles utilisent donc des blocs d'environ 4 bits. Chaque bloc produit une génération de groupe, G = g3 + p3·g2 + p3·p2·g1 + p3·p2·p1·g0, et une propagation de groupe, P = p3·p2·p1·p0. Une unité d'anticipation de second niveau traite ces signaux exactement comme les signaux g et p d'un seul bit pour calculer les retenues entrant dans chaque bloc, et un troisième niveau étend le schéma à 64 bits. Les additionneurs à préfixe parallèle, comme Kogge-Stone et Brent-Kung, généralisent la même idée en échangeant câblage et surface contre profondeur logique.
Les additionneurs rapides se trouvent dans les UAL, les générateurs d'adresses et les unités de calcul flottant, ainsi que dans le dernier étage des multiplieurs. Un multiplieur réduit d'abord ses nombreux produits partiels avec des additionneurs à retenue conservée (carry-save), des additionneurs complets indépendants qui transforment trois nombres en deux avec un seul délai d'additionneur complet et sans propagation de retenue. Seuls les deux derniers nombres nécessitent une addition avec propagation de retenue, réalisée une seule fois par un additionneur à retenue anticipée ou à préfixe. D'autres compromis, comme les additionneurs à sélection de retenue (carry-select) et à saut de retenue (carry-skip), se situent entre le ripple-carry et l'anticipation complète en vitesse et en surface.
Un additionneur à propagation de retenue attend que la retenue traverse chaque bit tour à tour, de sorte que le délai croît linéairement avec la largeur. Un additionneur à retenue anticipée calcule toutes les retenues en parallèle à partir des signaux de génération et de propagation, si bien que le délai croît à peu près comme le logarithme de la largeur.
Oui, pour la chaîne de retenue : p = a + b donne les mêmes retenues, car lorsque les deux entrées valent 1, le terme de génération produit déjà la retenue. Le bit de somme nécessite toutefois a ⊕ b ; de nombreuses conceptions calculent donc le XOR pour p et l'utilisent pour les deux.
Elles résument un bloc de bits : la génération de groupe vaut 1 si le bloc produit à lui seul une retenue sortante, et la propagation de groupe vaut 1 si une retenue entrant dans le bloc le traverse entièrement. Les niveaux d'anticipation supérieurs s'en servent pour calculer rapidement les retenues des blocs.
Absorption (perte de chiffres) Additionneur à retenue conservée (carry-save) Algorithme de Booth Arbre de Wallace Arithmétique saturée Arrondi au plus proche pair bfloat16 Décalage arithmétique Élimination catastrophique (perte de chiffres significatifs) Epsilon machine