Fonctionnement d'un ordinateur/Les circuits de calcul 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.

Précisons que ce chapitre est facultatif, dans le sens où il n'introduit pas de concept ou de circuits nécessaires pour la suite de ce cours. Les circuits de ce chapitre sont rarement utilisés, sans compter qu'ils sont assez complexes. Je recommande d'aborder ce chapitre comme s'il s'agissait d'une annexe, pour ceux qui sont vraiment motivés.

Malgré leur rareté, il est intéressant de voir comment sont conçus ces circuits de calcul trigonométrique. Il existe des circuits de calcul trigonométrique en virgule fixe, d'autres en virgule flottante. Les calculs trigonométriques ou transcendantaux sont surtout utilisés avec des nombres flottants, le cas avec des nombres à virgule fixe étant plus rare. Une partie des techniques que nous allons voir marche aussi bien avec des flottants qu'avec des nombres à virgule fixe. D'autres sont spécifiques aux nombres à virgule fixe, d'autres aux flottants. Nous préciserons du mieux que nous pouvons si telle ou telle technique marche avec les deux ou un seul.

L'algorithme CORDIC

modifier

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. Il fonctionne sur des nombres à virgule fixe, et plus précisément des nombres à virgule fixe codés en binaire. Mais il existe des variantes conçues pour fonctionner avec des nombres à virgule fixe codés en BCD.

CORDIC 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 connaître à 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 connaît 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. À 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 calculs

modifier

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. À 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 CORDIC

modifier

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)

L'approximation par un polynôme

modifier

Les premiers processeurs Intel, avant le processeur Pentium, utilisaient l'algorithme CORDIC pour calculer les fonctions trigonométriques, logarithmes et exponentielles. Mais le Pentium 1 remplaça CORDIC par une autre méthode, appelée l'approximation polynomiale. L'idée est de calculer ces fonctions avec une suite d'additions/multiplications bien précises. Précisément, le circuit calcule un polynôme de la forme a x + b x^2 + c x^3 + d x^4, + ... Les coefficients a,b,c,d,e,... sont choisit pour approximer au maximum la fonction voulue.

Si vous avez déjà lu des livres de maths avancés, vous aurez peut-être pensé à utiliser les séries de Taylor, mais celles-ci donnent rarement de bons résultats en pratiques, ce qui fait qu'elles ne sont pas utilisées. A la place, les fonctions sont approximées avec des polynômes conçus pour, qui ressemblent aux séries de Taylor, mais dont les coefficients sont un peu différents. Les coefficients sont calculés via un algorithme appelé l'algorithme de Remez, mais nous ne détaillerons pas ce point, qui va bien au-delà du cadre de ce cours.

Les coefficients sont mémorisés dans une mémoire ROM spécialisée, avec les coefficients d'une même opération placés les uns à la suite des autres, dans leur ordre d'utilisation. La ROM des coefficients est adressée par un circuit de contrôle qui lit le bon coefficient suivant l’opération demandée et l'étape associée. Le circuit de contrôle est implémenté via un microcode, concept qu'on verra dans les chapitres sur la microarchitecture du processeur.

L'usage d'une mémoire à interpolation

modifier

Dans cette section, nous allons voir qu'il est possible de faire des calculs avec l'aide d'une mémoire de précalcul. Avec cette technique, le circuit combinatoire qui fait le calcul est remplacé par une ROM qui contient les résultats des calculs possibles. La raison est que tout circuit combinatoire existant peut être remplacé par une mémoire ROM.

La technique marche immédiatement pour les calculs qui n'ont qu'une seule opérande, comme les calculs trigonométriques, le logarithme, l'exponentielle, la racine carrée, ce genre de calculs. L'opérande du calcul sert d'adresse mémoire, l'adresse contient le résultat du calcul demandé. Et on peut adapter cette technique pour les calculs à deux opérandes ou plus : il suffit de les concaténer pour obtenir une opérande unique.

 
ALU fabriquée à base de ROM

Cependant, la technique ne marche pas si les opérandes sont codés sur plus d'une dizaine de bits : 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, soit 128 kiloctets, 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 la ROM mémorisera moins de résultats qu'avant. Par exemple, imaginons qu'on veuille implémenter une fonction trigonométrique pour des flottants de 16 bits, avec une ROM avec des adresses de 10 bits. Il y aura 65535 flottants différents en opérandes, mais seulement 1024 résultats différents dans la ROM. Et il faut gérer la situation. Les deux sections suivantes fournissent deux solutions possibles pour cela.

Une première optimisation : éliminer les résultats redondants

modifier

Pour cela, une solution serait d'éliminer les résultats redondants, où des opérandes différentes donnent le même résultat. Pour simplifier les explications, on prend des fonctions à une seule opérande : les fonctions trigonométriques comme sinus ou cosinus, tangente, ou d'autres fonctions comme logarithme et exponentielles. Il arrive que deux opérandes différentes donnent le même résultat, ce qui fait que les résultats sont légèrement redondants. Un exemple est illustré avec les identités trigonométriques basiques pour les sinus et cosinus.

  • L'identité   permet d'éliminer la moitié des valeurs stocker dans la ROM. On a juste à utiliser des inverseurs commandables commandés par le bit de signe pour faire le calcul de   à partir de celui de  .
  • L'identité   permet de calculer la moitié des sinus quand l'autre est connue.
  • La définition   permet de calculer les tangentes sans avoir à utiliser de ROM séparée.
  • L'identité   permet de calculer des cosinus à partir de sinus, ce qui élimine le besoin d'utiliser une mémoire séparée pour les cosinus.

Et on peut penser à utiliser d'autres identités trigonométriques, d'autres formules mathématiques pour éliminer des résultats redondants. L'idée est alors de ne stocker le résultat qu'une seule fois dans la ROM, et d'ajouter des circuits autour pour que cette optimisation soit valide. L'idée est que des opérandes différentes vont pointer vers la même adresse dans la ROM des résultats, vers le même résultat. Pour cela, des circuits combinatoires déterminent l'adresse adéquate à partir des opérandes. Ce sont ces circuits qui appliquent les identités trigonométriques précédentes. Les circuits en question dépendent de l'identité trigonométrique utilisée, voire de la formule mathématique utilisée, aussi on ne peut pas faire de généralités sur le sujet.

Une seconde optimisation : l'interpolation linéaire

modifier
 
Interpolation memory - principe

Malgré l'utilisation d'identités mathématiques pour éliminer les résultats redondants, il arrive que la mémoire de précalcul soit trop petite pour stocker tous les résultats nécessaires. Il n'y a alors pas le choix que de retirer des résultats non-redondants. 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.

Il reste cependant possible de calculer une approximation du résultat, quand le résultat ne tombe pas sur un résultat précalculé. 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 connaît 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.