Fonctionnement d'un ordinateur/Les circuits de calcul flottant

Maintenant, nous allons voir dans les grandes lignes comment fonctionnent les circuits capables de calculer avec des nombres flottants. Nous allons aborder les calculs en virgule flottante, mais aussi les calculs avec les flottants à virgule fixe et les nombres flottants logarithmiques.

Les nombres à virgule fixeModifier

Pour les flottants à virgule fixe, les opérations sont similaires à ce qu'on a avec des nombres entiers si ce n'est qu'il faut souvent ajouter une division (ou un décalage si le facteur de conversion est bien choisi). Les circuits de calculs sont donc les mêmes. Cependant, certaines opérations impossibles avec des entiers deviennent possibles avec de tels flottants. C'est le cas du calcul des fonctions trigonométriques. Il est possible de créer des circuits qui effectuent des opérations trigonométriques, mais ceux-ci sont peu utilisés dans les ordinateurs actuels. La raison est que les calculs trigonométriques sont assez rares et ne sont réellement utilisés que dans les jeux vidéos (pour les calculs des moteurs physique et graphique), dans les applications graphiques de rendu 3D et dans les applications de calcul scientifique. Ils sont par contre plus courants dans les systèmes embarqués, bien que leur utilisation reste quand même assez peu fréquente. Malgré leur rareté, il est intéressant de voir comment sont conçus ces circuits de calcul trigonométrique en virgule fixe.

L'usage d'une mémoire à interpolationModifier

Les circuits de calcul trigonométriques les plus simples utilisent ce qu'on appelle une mémoire de précalcul. Avec cette technique, il n'y a pas de circuit de calcul proprement dit, mais une ROM qui contient les résultats des calculs possibles. L'opérande du calcul sert d'adresse mémoire, et le mot mémoire associé à cette adresse contient le résultat du calcul demandé. Cette technique peut s'appliquer pour n'importe quelle opération, au point que tout circuit combinatoire existant peut être remplacé par une mémoire ROM.

Cependant, si on utilisait cette technique telle qu'elle, la mémoire ROM serait trop importante pour être implémentée. Rien qu'avec des nombres à virgule fixe de plus de 16 bits, il faudrait une mémoire de 2^16 cases mémoire, chacune faisant 16 bits, et ce pour une seule opération. Ne parlons même pas du cas avec des nombres de 32 ou 64 bits ! Pour cela, on va donc devoir ruser pour réduire la taille de cette ROM.

Mais qui dit réduire la taille de la ROM signifie que certains résultats ne seront pas connus. Il y aura forcément des opérandes pour lesquelles la ROM n'aura pas mémorisé le résultat et pour lesquels la mémoire de précalcul seule ne peut rien faire. La solution sera alors de calculer ces résultats à partir d'autres résultats connus et mémorisés dans la mémoire ROM. La mémoire ROM n'a donc pas besoin de stocker tous les résultats et peu se contenter de ne mémoriser que les résultats essentiels, ceux qui permettent de calculer tous les autres. On doit distinguer deux types d'opérandes : celles dont le résultat est stocké dans la ROM, celles dont le résultat est calculé à partir des précédentes. Les opérandes dont le résultat est en ROM seront appelées des opérandes précalculés dans ce qui suit, alors que les autres seront appelées les opérandes non-précalculés.

Une première optimisation : les identités trigonométriquesModifier

La première manière de ruser est d'utiliser les identités trigonométriques pour calculer les résultats non-précalculés.

Par exemple, on sait que  , ce qui permet d'éliminer la moitié des valeurs stocker dans la ROM. On a juste à utiliser un comparateur et un inverseur pour faire le calcul de   à partir de celui de  .

De même, l'identité   permet de calculer des cosinus à partir de sinus déjà connus, ce qui élimine le besoin d'utiliser une mémoire séparée pour les cosinus.

Enfin, l'identité   permet de calculer la moitié des sinus quand l'autre est connue.

Et on peut penser à utiliser d'autres identités trigonométriques, mais pas les trois précédentes sont déjà assez intéressantes. Le problème est qu'on ne peut pas envoyer les opérandes non-précalculés. A la place, on doit transformer l'opérande non-précalculées pour obtenir un opérande précalculé, géré par la mémoire ROM. Il faut donc des circuits qui se chargent de détecter ces opérandes , de les transformer en opérandes reconnus par la ROM, puis de corriger la donnée lue en ROM pour obtenir le résultat adéquat. Les circuits en question dépendent de l'identité trigonométrique utilisée, aussi on ne peut pas faire de généralités sur le sujet.

Une seconde optimisation : l'interpolation linéaireModifier

 
Interpolation memory - principe

La seconde ruse n'utilise pas d'identités trigonométriques qui donnent un résultat exact, mais calcule une approximation du résultat, sauf pour les opérandes précalculés. L'idée est de prendre les deux (ou trois, ou quatre, peu importe) résultats précalculés les plus proches du résultat voulu, et de les utiliser pour faire une approximation.

L'approximation du résultat se calcule en faisant une interpolation linéaire, à savoir une moyenne pondérée des deux résultats les plus proches. Par exemple, si on connait le résultat pour sin(45°) et pour sin(50°), alors on peut calculer sin(47,5°), sin(47°), sin(45,5°), sin(46,5°) ou encore sin(46°) en faisant une moyenne pondérée des deux résultats. Une telle approximation est largement suffisante pour beaucoup d'applications.

Le circuit qui permet de faire cela est appelée une mémoire à interpolation. Le schéma de principe du circuit est illustré ci-contre, alors que le schéma détaillé est illustré ci-dessous.

 
Interpolation memory.

L'algorithme CORDICModifier

Sur du matériel peu puissant, les fonctions trigonométriques peuvent être calculées avec l'algorithme CORDIC. Celui-ci est notamment très utilisé dans les calculatrices modernes, qui possèdent un circuit séquentiel ou un logiciel pour exécuter cet algorithme. Cet algorithme fonctionne par approximations successives, chaque itération de l'algorithme permettant de s’approcher du résultat final. Il utilise les mathématiques du cercle trigonométrique (qui sont considérées acquises dans ce qui suit). Cet algorithme représente un angle par un vecteur unitaire dans le cercle trigonométrique, plus précisément par l'angle que forme le vecteur avec l'axe des abscisses. Le cosinus et le sinus de l'angle sont tout simplement les coordonnées x et y du vecteur, par définition. En travaillant donc directement avec les coordonnées du vecteur, l'algorithme peut connaitre à chaque itération le cosinus et le sinus de l'angle. Dit autrement, pour un vecteur   de coordonnées (x,y) et d'ange  , on a :

 
 
CORDIC Vector Rotation 1

L'algorithme CORDIC part d'un principe simple : il va décomposer un angle en angles plus petits, dont il connait le cosinus et le sinus. Ces angles sont choisis de manière à avoir une propriété assez particulière : leur tangente est une puissance de deux. Ainsi, par définition de la tangente, on a :  . Vous aurez deviné que cette propriété se marie bien avec le codage binaire et permet de simplifier fortement les calculs. Nous verrons plus en détail pourquoi dans ce qui suit. Toujours est-il que nous pouvons dire que les angles qui respectent cette propriété sont les suivants : 45°, 26.565°, 14.036°, 7,125°, ... , 0.0009°, 0.0004°, etc.

L'algorithme part d'un angle de 0°, qu'il met à jour à chaque itération, de manière à se rapprocher de plus en plus du résultat. Plus précisément, cet algorithme ajoute ou retranche un angle précédemment cité à chaque itération. Typiquement, on commence par faire une rotation de 45°, puis une rotation de 26.565°, puis de 14.036°, et ainsi de suite jusqu’à tomber sur l'angle qu'on souhaite. A chaque itération, on vérifie si la valeur de l'angle obtenue est égale inférieure ou supérieure à l'angle voulu. Si l'angle obtenu est supérieur, la prochaine itération retranchera l'angle précalculé suivant. Si l'angle obtenu est inférieur, on ajoute l'angle précalculé. Et enfin, si les deux sont égaux, on se contente de prendre les coordonnées x et y du vecteur, pour obtenir le cosinus et le sinus de l'angle voulu.

 
CORDIC-illustration

Du principe aux calculsModifier

Cette rotation peut se calculer assez simplement. Pour un vecteur de coordonnées  , la rotation doit donner un nouveau vecteur de coordonnées  . Pour une rotation d'angle  , on peut calculer le second vecteur à partir du premier en multipliant par une matrice assez spéciale (nous ne ferons pas de rappels sur la multiplication matricielle ou les vecteurs dans ce cours). Voici cette matrice :

 

Une première idée serait de pré-calculer les valeurs des cosinus et sinus, vu que les angles utilisés sont connus. Mais ce pré-calcul demanderait une mémoire assez imposante, aussi il faut trouver autre chose. Une première étape est de simplifier la matrice. En factorisant le terme  , la multiplication devient celle-ci (les signes +/- dépendent de si on retranche ou ajoute l'angle) :

 

Encore une fois, la technique du précalcul serait utilisable, mais demanderait une mémoire trop importante. Rappelons maintenant que la tangente de chaque angle est une puissance de deux. Ainsi, la multiplication par   devient un simple décalage ! Autant dire que les calculs deviennent alors nettement plus simples. L'équation précédente se simplifie alors en :

 

Le terme   sera noté  , ce qui donne :

 

Il faut noter que la constante   peut être omise dans le calcul, tant qu'on effectue la multiplication à la toute fin de l'algorithme. A la fin de l'algorithme, on devra calculer le produit de tous les   et y multiplier le résultat. Or, le produit de tous les   est une constante, approximativement égale à 0,60725. Cette omission donne :

 

Le tout se simplifie en :

 
 

On peut alors simplifier les multiplications pour les transformer en décalages, ce qui donne :

 
 

Les circuits CORDICModifier

Ainsi, une rotation demande juste de décaler x et y et d'ajouter le tout aux valeurs avant décalage d'une certaine manière. Voici le circuit qui dérive de la matrice précédente. Ce circuit prend les coordonnées du vecteur et lui ajoute/retranche un angle précis. On obtient ainsi le circuit de base de CORDIC.

 
CORDIC base circuits

Pour effectuer plusieurs itérations, il est possible de procéder de deux manières. La plus évidente est d'ajouter un compteur et des circuits à la brique de base, afin qu'elle puisse enchainer les itérations les unes après les autres.

 
CORDIC (Bit-Parallel, Iterative, Circular Rotation)

La seconde méthode est d'utiliser autant de briques de base pour chaque itération.

 
CORDIC (Bit-Parallel, Unrolled, Circular Rotation)

Les nombres flottants IEEE754Modifier

Il est temps de voir comment créer des circuits de calculs qui manipulent des nombres flottants au format IEEE754. Rappelons que la norme IEEE754 précise le comportement de 5 opérations: l'addition, la soustraction, la multiplication et la division. Paradoxalement, les multiplications, divisions et racines carrées sont relativement simples à calculer avec des nombres flottants, là où l'addition et la soustraction sont plus complexes. Dans ce qui va suivre, nous allons d'abord parler des procédés d'arrondis des résultats, applicables à toutes les opérations, avant de poursuivre par l'étude des opérations simples (multiplications, divisions, racines carrées), avant de terminer avec les opérations compliquées (addition et soustraction).

La normalisation et les arrondis flottantsModifier

 
Normalisation in circuit

Calculer sur des nombres flottants peut sembler trivial, mais les mathématiques ne sont pas vraiment d'accord avec cela. En effet, le résultat d'un calcul avec des flottants n'est pas forcément un flottant valide. Il doit subir quelques transformations pour être un nombre flottant : il doit souvent être arrondi, mais il doit aussi passer par d'autres étapes dites de normalisation.

La prénormalisationModifier

La prénormalisation gère le bit implicite. Lorsqu'un circuit de calcul fournit son résultat, celui-ci n'a pas forcément son bit implicite à 1. On est obligé de décaler la mantisse du résultat de façon à ce que ce soit le cas. Pour savoir de combien de rangs il faut décaler, il faut compter le nombre de zéros situés avant le 1 de poids fort, avec un circuit spécialisé. Ce circuit permet aussi de détecter si la mantisse vaut zéro.

Mais si on décale notre résultat de n rangs, cela signifie qu'on le multiplie par 2 à la puissance n. Il faut donc corriger l'exposant du résultat pour compenser le décalage de la mantisse. Il suffit pour cela de lui soustraire n, le nombre de rangs dont on a décalé la mantisse.

 
Circuit de prénormalisation.

La normalisationModifier

Une fois ce résultat calculé, il faut faire un arrondi du résultat avec un circuit de normalisation. L'arrondi se base sur les bits de poids faible situés juste à gauche et à droite de la virgule., ce qui demande d'analyser une dizaine de bits tout au plus. Une fois les bits de poids faible à gauche de la virgule sont remplacé, les bits à droite sont éliminés. L'arrondi peut être réalisé par un circuit combinatoire, mais le faible nombre de bits d'entrée rend possible d'utiliser une mémoire ROM. Ce qui est réalisé dans quelques unités flottantes.

 
Circuit d'arrondi flottant basé sur une ROM.

Malheureusement, il arrive que ces arrondis décalent la position du bit implicite d'un rang, ce qui se résout avec un décalage si cela arrive. Le circuit de normalisation contient donc de quoi détecter ces débordements et un décaleur. Bien évidemment, l'exposant doit alors lui aussi être corrigé en cas de décalage de la mantisse.

 
Circuit de postnormalisation.

résuméModifier

Le circuit complet, qui effectue à la fois normalisation et arrondis est le suivant :

 
Circuit de normalisation-arrondi

La multiplication flottanteModifier

Prenons deux nombres flottants de mantisses   et   et les exposants   et  . Leur multiplication donne :

 

On regroupe les termes :

 

On simplifie la puissance :

 

En clair, multiplier deux flottants revient à multiplier les mantisses et additionner les exposants. Il faut cependant penser à ajouter les bits implicites aux mantisses avant de les multiplier.

 
Multiplieur flottant

De plus, il faut aussi gérer le fait que les exposants sont codés en représentation par excès en retirant le biais de l'exposant calculé.

 
Multiplieur flottant -- gestion des exposants

Enfin, il ne faut pas oublier de rajouter les étapes de normalisation et d'arrondis.

 
Multiplieur flottant avec normalisation

La division flottanteModifier

La division fonctionne sur le même principe que la multiplication, si ce n'est que les calculs sont quelque peu différents : les exposants sont soustraits et que les mantisses sont divisées.

Pour le démontrer, prenons deux flottants   et   et divisons le premier par le second. On a alors :

 

On applique les règles sur les fractions :

 

On simplifie la puissance de 2 :

 

On voit que les mantisses sont divisées entre elles, tandis que les exposants sont soustraits.

La racine carrée flottanteModifier

Le calcul de la racine carrée d'un flottant est relativement simple. Par définition, la racine carrée d'un flottant   vaut :

 

La racine d'un produit est le produit des racines :

 

Vu que  , on a :

 

On voit qu'il suffit de calculer la racine carrée de la mantisse et de diviser l'exposant par deux (ou le décaler d'un rang vers la droite ce qui est équivalent). Voici le circuit que cela doit donner :

 
Racine carrée FPU

L'addition et la soustraction flottanteModifier

La somme de deux flottants n'est simplifiable que quand les exposants sont égaux : dans ce cas, il suffit d'additionner les mantisses. Il faut donc mettre les deux flottants au même exposant, l'exposant choisi étant souvent le plus grand exposant des deux flottants. Convertir le nombre dont l'exposant est le plus petit demande de décaler la mantisse vers la droite, d'un nombre de rangs égal à la différence entre les deux exposants. Pour comprendre pourquoi, il faut se souvenir que décaler vers la droite diminuer l'exposant du nombre de rangs. Pour faire ce décalage, on utilise un décaleur et un circuit qui échange les deux opérandes (histoire d'envoyer le plus petit exposant dans le décaleur). Ce circuit d'échange est piloté par un comparateur qui détermine quel est le nombre avec le plus petit exposant.

 
Circuit de mise au même exposant.

Suivant les signes, il faudra additionner ou soustraire les opérandes.

 
Crcuit d'addition et de soustraction flottante.

Voici le circuit complet :

 
Additionneur flottant - circuit complet

Les fonctions trigonométriquesModifier

L'implémentation des fonctions trigonométriques est quelque peu complexe, du moins pour ce qui est de créer des circuits de calcul du sinus, cosinus, tangente, etc. S'il est possible d'utiliser une mémoire à interpolation, la majorité des processeurs actuels réalise ce calcul à partir d'une suite d'additions et de multiplications, qui donne le même résultat. Cette suite peut être implémentée via le logiciel, un petit bout de programme s'occupant de faire les calculs. Il est aussi possible, bien que nettement plus rare, d'implémenter ce bout de logiciel directement sous la forme de circuits : la boucle de calcul est remplacée par un circuit séquentiel. Mais il faut avouer que cette solution n'est pas pratique et que faire les calculs au niveau logiciel est nettement plus simple, tout aussi performant (et oui !) et moins couteux. La tactique habituelle consiste à utiliser une approximation de Taylor, largement suffisante pour calculer la majorité des fonctions trigonométriques.

 
Implémentation matérielle naive et inneficiente d'un calcul de sinus par série de taylor

Les flottants logarithmiquesModifier

Maintenant, nous allons fabriquer une unité de calcul pour les flottants logarithmiques. Nous avions vu les flottants logarithmiques dans le chapitre Codage des nombres. Pour résumer rapidement, ce sont des flottants qui codent uniquement un bit de signe et un exposant, mais sans la mantisse (qui vaut implicitement 1). L'exposant stocké n'est autre que le logarithme en base 2 du nombre codé, d'où le nom donné à ces flottants. Au passage, l'exposant est stocké dans une représentation à virgule fixe.

Nous avions dit dans le chapitre sur le codage des nombres que l'utilité de cette représentation est de simplifier certains calculs, comme les multiplications, divisions, puissances, etc. Eh bien vous allez rapidement comprendre pourquoi dans cette section. Nous allons commencer par voir les deux opérations de base : la multiplication et la division. Celles-ci sont en effet extrêmement simples dans cet encodage, bien plus que l'addition et la soustraction. C'est d'ailleurs la raison d'être de cet encodage : simplifier fortement les calculs multiplicatifs, quitte à perdre en performance sur les additions/soustractions.

La multiplication et la division de deux flottants logarithmiquesModifier

Pour commencer, il faut se souvenir d'un théorème de mathématique sur les logarithmes : le logarithme d'un produit est égal à la somme des logarithmes. Dans ces conditions, une multiplication entre deux flottants logarithmiques se transforme en une simple addition d'exposants.

 

Le même raisonnement peut être tenu pour la division. Dans les calculs précédents, il suffit de se rappeler que diviser par  , c'est multiplier par  . Or, il faut se rappeler que  . On obtient alors, en combinant ces deux expressions :

 

La division s'est transformée en simple soustraction. Dans ces conditions, une unité de calcul logarithmique devant effectuer des multiplications et des divisions est constituée d'un simple additionneur/soustracteur et de quelques (ou plusieurs, ça marche aussi) circuits pour corriger le tout.

L'addition et la soustraction de deux flottants logarithmiquesModifier

Pour l'addition et la soustraction, la situation est beaucoup plus corsée, vu qu'il n'y a pas vraiment de formule mathématique pour simplifier le logarithme d'une somme. Dans ces conditions, la seule solution est d'utiliser une mémoire de précalcul, comme vu au début du chapitre. Et encore une fois, il est possible de réduire la taille de mémoire ROM de précalcul en utilisant des identités mathématiques. L'idée est de transformer l'addition en une opération plus simple, qui peut se pré-calculer plus facilement.

Pour cela, partons de la formule suivante, qui pose l'équivalence des termes suivants :

 

Vu que le logarithme d'un produit est égal à la somme des logarithmes, on a :

 

Pour rappel, les représentations de x et y en flottant logarithmique sont égales à   et  . En notant ces dernières   et  , on a :

 

Par définition,   et  . En injectant dans l'équation précédente, on obtient :

 

On simplifie la puissance de deux :

 

On a donc :

 , avec f la fonction adéquate.

Pour la soustraction, on a la même chose, sauf que les signes changent, ce qui donne :

 , avec g une fonction différente de f.

On vient donc de trouver la formule qui permet de faire le calcul, le seul obstacle étant la fonction f et la fonction g. Heureusement, le terme de droite peut se pré-calculer facilement, ce qui donne une table beaucoup plus petite qu'avec l'idée initiale. Dans ces conditions, l'addition se traduit en :

  • un circuit qui additionne/soustrait les deux opérandes ;
  • une table qui prend le résultat de l'additionneur/soustracteur et fournit le terme de droite ;
  • et un autre additionneur pour le résultat.

RésuméModifier

Pour implémenter les quatre opérations, on a donc besoin :

  • de deux additionneurs/soustracteur et d'un diviseur pour l'addition/soustraction ;
  • de deux autres additionneurs/soustracteur pour la multiplication et la division ;
  • et d'une ROM.

Il est bon de noter qu'il est tout à fait possible de mutualiser les additionneurs pour la multiplication et l'addition. En rajoutant quelques multiplexeurs, on peut faire en sorte que le circuit puisse se configurer pour que les additionneurs servent soit pour la multiplication, soit pour l'addition. On économise en peu de circuits.

 
Unité de calcul logarithmique