Parler du temps, mais de manière formelle (2)

La vision synchrone utilise l’existence du délai critique pour s’abstraire de la propagation des fronts. Puisque les délais réels n’ont pas d’influence sur le résultat, on peut les ignorer et travailler en temps discret, en voyant le circuit comme un moyen parmi d’autres de résoudre les équations booléennes qui le décrivent. Le plus simple est d’adopter l’hypothèse de synchronisme parfait, qui considère que le circuit calcule les sorties en temps zéro. Alors, quand on compose des sous circuits, en séquence, en parallèle, ou par rebouclage de sortie sur des entrées (à condition que le graphe résultant reste acyclique), le calcul se fait toujours en temps zéro et toutes les simplifications booléennes sont applicables. Le concepteur du circuit peut travailler en synchronisme parfait, son système de CAO lui calculant le temps physique de stabilisation pour une technologie donnée. Bien sûr, il doit agir pour améliorer le temps réel de calcul si son circuit conceptuel n’est pas assez rapide par rapport aux besoins physiques.

Le reste du cours a approfondi la conception des circuits combinatoires, à travers l’addition de deux mots de n bits pour produire un résultat de n+1 bits. La méthode simple est celle de l’école : pour chaque couple de bits d’entrée a_i, b_i on instancie un additionneur FullAdder_i d’entrées a_i, b_i et de retenue entrante c_i donnée par c₀ = 0 et c_i+1 = r_i pour i > 0. Les bits de la somme sont les sorties s_i des FullAdder_i pour 0 ≤ i < n et le bit de poids fort s_n = r_n-1. Le circuit est de taille linéaire en n, mais son délai critique déterminé par le chemin de retenues est aussi linéaire en n, ce qui est trop lent dès que n n’est pas tout petit.

Le délai critique s’améliore par divers échanges temps-espace. L’additionneur de von Neumann est fondé sur les idées clefs de dichotomie et de spéculation. L’idée de la dichotomie est de couper le mot d’entrée au milieu et de réaliser simultanément les additions des demi-mots de poids faibles et des demi-mots de poids forts. Mais la retenue entrante des poids forts est la retenue sortante de la somme des poids faibles. L’idée de la spéculation est de calculer simultanément les deux sommes possibles des poids forts selon que leur retenue entrante est 0 ou 1, puis de sélectionner la bonne somme selon la retenue effective des poids faibles, l’autre somme étant purement et simplement ignorée. La sélection se fait à l’aide de multiplexeurs mux(x,y,z) calculant y si x vaut 1 et z si x vaut 0. Les sommes partielles des demi-mots de poids faibles et forts sont calculées récursivement par la même méthode. Le chemin critique est alors créé par l’arborescence de multiplexeurs qui résulte du développement de la récursion : il est logarithmique (de taille 6 au lieu de 64 pour 64 bits). Bien sûr, cette accélération temporelle a un coût en espace et en énergie, puisqu’on calcule des informations pour les ignorer ensuite.

Une autre méthode, inspirée par la programmation fonctionnelle, est due à J. Vuillemin et F. Preparata. Sa clef est que la fonction f_i : r_i → r_i+1 de propagation de la retenue à l’étage i ne dépend que des deux bits a_i et b_i : c’est la fonction constante 0 si a_i et b_i valent tous deux 0, la fonction identité si l’un vaut 0 et l’autre 1, et la fonction constante 1 si les deux valent 1. Comme la retenue entrante globale est 0, on a r_i+1 = f_i(f_i-1(…(f₁(f₀(0))))), donc r_i+1 = (f_i◦f_i-1◦…◦f₁◦f₀)(0). Puisque la composition de fonctions est associative, elle peut se calculer dichotomiquement, par exemple sous la forme ((f₇◦f₆)◦(f₅◦f₄))◦((f₃◦f₂)◦(f₁◦f₀)) pour n = 8. Les compositions peuvent donc être calculées par un arbre de calculs parallèles, donc en profondeur et temps logarithmiques. Dans le circuit, une fonction f : bool → bool est représentée par sa table de vérité, i.e. par la paire codée surdeux fils f₀ et f₁. L’application de f à x se calcule par f(x) = mux(x, f₁, f₀), et la composition g◦f, par (g◦f)_i = mux(f_i, g₁, g₀) pour i = 1,2. Voir les vidéos ou les planches du cours pour le circuit obtenu, particulièrement élégant.

Une addition bien différente utilise des bases redondantes. Une présentation très simple due à J. Vuillemin travaille avec des nombres mous, c’est-à-dire des paires de nombres A = (a’, a’’) codant de plusieurs façons la valeur a’ + a’’. Par exemple, 3 se code (0,3), (1,2), (2,1) ou (3,0). Il est facile de voir que l’additionneur de la figure 2 calcule en temps constant (indépendant du nombre de bits) un nombre mou dont la valeur est la somme des valeurs des nombres mous d’entrée. Bien sûr, on ne peut pas lire directement le résultat sans terminer par une autre addition sommant ses deux composantes, mais cette structure est très efficace quand on a une liste de nombres à additionner. On peut ainsi faire une multiplication efficace en construisant d’abord la matrice des produits individuels (simples conjonctions booléennes en base 2), en décalant les résultats comme à l’école, et en additionnant les nombres obtenus à l’aide d’un arbre dichotomique d’additionneurs mous : on obtient ainsi un résultat mou en temps logarithmique, qu’il ne reste plus qu’à durcir en un seul nombre à l’aide d’un dernier additionneur logarithmique, par exemple celui de von Neumann. Le résultat surprenant est que la multiplication se calcule effectivement en temps logarithmique. Les bases redondantes sont également fondamentales pour une division efficace, et c’est une erreur dans la tabulation de divisions molles dans une base non binaire qui a conduit au fameux bug du Pentium Pro qui a fait perdre 475 millions de dollars à Intel en 1994.


Le cours s’est terminé par le rappel d’un résultat important sur les circuits cycliques, déjà présenté en 2010. Il s’agit de généraliser la notion de chemin critique en se débarrassant de la contrainte d’acyclicité, donc de savoir quand un circuit cyclique calcule de façon déterministe et en temps prévisible pour tous délais des fils et portes. Cette question est importante d’une part car des circuits cycliques sont engendrés naturellement par synthèse à partir des langages de haut niveau et d’autre part car un circuit cyclique peut être exponentiellement plus petit que tout circuit acyclique pour certaines fonctions booléennes [2]. Notre résultat est qu’un circuit cyclique est acceptable pour le critère précédent si et seulement si ses sorties peuvent être calculées à l’aide des seules lois de la logique constructive, qui interdit le tiers exclu « x ou non x  = 1 ». Ainsi, le calcul électrique du circuit de Hamlet défini par l’équation ToBe = ToBeor not ToBe ne converge pas pour certains délais des fils et portes, car sa solution logique de l’équation demande le tiers exclu.

La restriction constructive est naturelle, car le tiers exclu demanderait une spéculation sur le résultat que les électrons sont bien incapables de réaliser. Mais la preuve du résultat est difficile. Une nouvelle version de cette preuve due à Mendler [3] sera présentée dans le cours de 2014. Elle fait intervenir une logique temporelle constructive mêlant étroitement aspects continus et discrets. Elle montre aussi qu’il faut voir un circuit non seulement comme une machine à calculer mais aussi comme une machine à prouver, ce qui donne une vue électrique de la correspondance fondamentale de Curry-Howard entre calculs en l-calcul et preuves en logique intuitionniste [4].