Quelques exercices tirés du cours, ou donnés en devoir à la maison.
1. Addition à propagation de retenue
Considérons le shéma du "full" adder suivant
Question : Si toutes les portes élémentaires (AND, OR et XOR) ont un temps de propagation de 1ns, quel est le temps de calcul de cette fonction ?
Le temps de calcul de cette fonction est obtenu en suivant tous les chemins possibles entre toute entrée et toute sortie de cette fonction, et en additionnant les temps de propagation le long de ces chemin.
La table suivant résume les temps de propagation le long des différents chemins:
| Source | Destination : Si | Destination : Ri+1 |
| Ri | 1ns | 2ns |
| ai | 2ns | 3ns |
| bi | 2ns | 2ns |
Le chemin (temporel) le plus long va de l'entrée ai vers la sortie Ri+1 : 3ns
Question : En déduire le temps de calcul d'un additionneur N bits construit à partir de cette fonction
Construisons tout d'abord un additionneur 4 bits et établissons le temps d'arrivée des données le long des différents chemins. Pour chaque "full adder" sont indiqués, le temps d'arrivée des données A et B (en rouge) ainsi que les temps d'arrivée des données en provenance des blocs précédents (en vert).
Dans un full adder donné, il faut tenir compte des temps d'arrivée réel des données pour déterminer le temps de sortie des signaux.
Nous obtenons un temps de calcul de 9ns. On peut réexprimer le temps de calcul sous la forme : Tcalc = Tr1 + 3 Triri+1 avec:
- Tr1 temps de calcul de la première retenue
- Triri+1 temps de propagation de retenue en retenue...
Nous pouvons généraliser à un additionneur N bits: Tcalc = Tr1 + (N-1) Triri+1
Si on néglige le cas particulier de la retenue on peut considérer que le temps de calcul de l'additionneur N bits à propagation de retenue est asymptotiquement en O(n)
2 Additionneur a saut de retenue
Le shema suivant représente un additionneur dit "à saut de retenue".
Questions : expliquez son fonctionnement, quel est son intéret du point de vue du temps de calcul ?
Cet additionneur décompose le calcul de la somme de 2 mots de 2n bits en considérant séparément le calcul sur les poids faibles (bits 0 à n-1) et les poids forts (bits n à 2n-1). Trois calculs sont effectués en parallèle :
- un calcul sur les poids faibles
- un calcul sur les poids forts, supposant que la retenue intermédiaire est 0
- un calcul sur les poids forts, supposant que la retenue intermédiaire est 1
Un multiplexeur se charge de sélectionner le bon résultat pour les poids forts lorsque la retenue sortante des poids faibles est disponible.
Un utilisant les résultats de l'exercice "Addition à propagation de retenue", nous savons que le temps de calcul d'un additionneur 2N bits est en O(2n). Dans ce nouvel additionneur nous avons quasiment un temps en O(n) (en négligeant le temps nécessaire au multiplexeur de sortie). La nouvelle structure est théoriquement 2 fois plus rapide. Nous pourrions réitérer cette opération de manière récursive (diviser les blocs de N bits en 2 blocs de N/2 bits et ainsi de suite..), cependant pour modéliser correctement le gain éventuellement obtenu, il faut tenir compte du temps de propagation réel dans chaque couche de multiplexeur: chaque nouveau découpage introduit une nouvelle couche de multiplexeur à traverser. Il 'agit donc d'un problème d'optimisation entre un phénomène décroissant (le temps de calcul des additionneurs) et un phénomène croissant (le temps de traversée des multiplexeurs).