temps de calcul, temps de propagation

 Quelques exercices tirés du cours, ou donnés en devoir à la maison.

  1. Addition à propagation de retenue
  2. Addition à saut de retenue

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).