Fonctionnement d'un ordinateur/Les circuits de calcul flottant

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

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.

Flottants à virgule fixe[modifier | modifier le wikicode]

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.

Mémoire à interpolation[modifier | modifier le wikicode]

Une autre solution est d'utiliser ce qu'on appelle une mémoire de précalcul. Cette technique mémorise le résultat du calcul dans une mémoire ROM, ROM qui sera adressée par l'opérande : le mot mémoire qui correspond à une adresse (donc à un opérande) contient le résultat du calcul demandé.

ALU fabriquée à base de ROM

Cependant, si on utilisait cette technique telle qu'elle, pour des flottants de plus de 16 bits, la mémoire ROM serait trop importante pour être implémentée. Pour cela, on va donc devoir ruser pour réduire la taille de cette ROM.

Identités trigonométriques[modifier | modifier le wikicode]

La méthode la plus simple est de ne mémoriser qu'une partie des résultats, à savoir les résultats qui correspondent à un nombre limité d'opérandes. On ne peut alors pas envoyer les opérandes directement à cette ROM. Pour résoudre ce petit problème, on peut transformer l'opérande envoyé pour obtenir un opérande géré par la mémoire ROM. Une première technique serait d'utiliser des identités trigonométriques pour simplifier les calculs. 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 fonctions sin quand l'autre est connue. Les trois identités trigonométriques permettent de diviser par quatre le nombre de valeurs à mémoriser dans la mémoire ROM.

Interpolation linéaire[modifier | modifier le wikicode]

Une autre solution, quelque peu meilleure, est de prendre les valeurs les plus proches gérées par la ROM qui encadrent l’opérande et de les utiliser pour faire une interpolation linéaire. On obtient alors une mémoire à interpolation, qui calcule une valeur approximative, bien que largement suffisante pour beaucoup d'applications.

Interpolation memory - principe Interpolation memory

CORDIC[modifier | modifier le wikicode]

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

Principes mathématiques[modifier | modifier le wikicode]

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 :

Circuits CORDIC[modifier | modifier le wikicode]

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 : soit on ajoute un compteur et des circuits, pour que le circuit s'occupe de toutes les itérations, soit en utilisant autant de briques de base pour chaque itération.

CORDIC (Bit-Parallel, Iterative, Circular Rotation)
CORDIC (Bit-Parallel, Unrolled, Circular Rotation)

Nombres flottants IEEE754[modifier | modifier le wikicode]

Nous allons naturellement commencer par étudier les nombres flottants 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).

Normalisation et arrondis[modifier | modifier le wikicode]

Calculer sur des nombres flottants peut sembler trivial. Mais le résultat du calcul devra subir quelques transformations pour être un nombre flottant : on peut citer les arrondis, mais aussi d'autres étapes dites de normalisation.

Normalisation in circuit

Prénormalisation[modifier | modifier le wikicode]

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 le bit implicite soit un 1. 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. Pour régler ce problème, il faut corriger l'exposant du résultat pour annuler la multiplication par 2 à la puissance n. Il suffit pour cela de lui soustraire n, le nombre de rangs dont on a décalé la mantisse.

Circuit de prénormalisation.

Normalisation[modifier | modifier le wikicode]

Une fois ce résultat calculé, il faut faire un arrondi du résultat avec un circuit de normalisation. 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 | modifier le wikicode]

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

Circuit de normalisation-arrondi

Multiplication[modifier | modifier le wikicode]

Prenons deux nombres flottants de mantisses m1 et m2 et les exposants e1 et e2. Leur multiplication donne :

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

Division[modifier | modifier le wikicode]

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 voit que les mantisses sont divisées entre elles, tandis que les exposants sont soustraits.

Racine carrée[modifier | modifier le wikicode]

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

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

Addition et soustraction[modifier | modifier le wikicode]

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

Fonctions trigonométriques[modifier | modifier le wikicode]

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

Flottants logarithmiques[modifier | modifier le wikicode]

Maintenant, nous allons fabriquer une unité de calcul pour les flottants logarithmiques. Nous avions vu les flottants logarithmiques dans le chapitre Codage des nombres. C'est un type assez particulier de nombres flottants, utilisés dans des applications un peu particulières. 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. Et 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.

Multiplication et division[modifier | modifier le wikicode]

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.

Addition et soustraction[modifier | modifier le wikicode]

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 de pré-calculer toutes les sommes possibles et de les stocker dans une mémoire ROM. En envoyant les deux nombres concaténés sur le bus d'adresse, on récupère ainsi l'exposant de leur somme. Cette solution marche assez bien pour des nombres de 16 bits : une mémoire de 32 kilo-octets suffit. Mais pour du 32 bits, on atteint 16 gibi-octets. Dans ces conditions, on doit ruser pour diminuer la taille de la ROM en utilisant diverses propriétés mathématiques. L'idée est de transformer l'addition en une opération plus simple, qui peut se pré-calculer plus facilement. La table ainsi obtenue devra être plus petite.

Premièrement, 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 :

Le terme de droite peut se pré-calculer facilement, et donne une table beaucoup plus petite qu'avec l'idée initiale. Dans ces conditions, l'addition se traduit en :

  • un circuit qui divise les deux opérandes et leur ajoute 1 : un diviseur couplé à un additionneur suffit ;
  • une table qui prend en entrée le résultat de l'additionneur, et fournit le terme de droite ;
  • et un autre additionneur pour le résultat.

Résumé[modifier | modifier le wikicode]

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