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

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 $V$ de coordonnées (x,y) et d'ange $\gamma$, on a :

$V={\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}\cos \gamma \\\sin \gamma \end{pmatrix}}$

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 : ${\frac {y}{x}}={\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},{\frac {1}{32}},...$. 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

Cette rotation peut se calculer assez simplement. Pour un vecteur de coordonnées $(x,y)$, la rotation doit donner un nouveau vecteur de coordonnées $(x',y')$. Pour une rotation d'angle $\gamma$, 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 :

${\begin{pmatrix}x'\\y'\end{pmatrix}}={\begin{pmatrix}\cos \gamma &-\sin \gamma \\\sin \gamma &\cos \gamma \end{pmatrix}}.{\begin{pmatrix}x\\y\end{pmatrix}}$

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 $\cos(\gamma )~$, la multiplication devient celle-ci (les signes +/- dépendent de si on retranche ou ajoute l'angle) :

${\begin{pmatrix}x'\\y'\end{pmatrix}}=\cos \gamma {\begin{pmatrix}1&-\tan \gamma \\\tan \gamma &1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}$

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 $\tan \gamma$ devient un simple décalage ! Autant dire que les calculs deviennent alors nettement plus simples. L'équation précédente se simplifie alors en :

${\begin{pmatrix}x'\\y'\end{pmatrix}}=\cos(\arctan(2^{-i})){\begin{pmatrix}1&-2^{-i}\\2^{-i}&1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}$

Le terme $\cos(\arctan(2^{-i}))$ sera noté $K(i)$, ce qui donne :

${\begin{pmatrix}x'\\y'\end{pmatrix}}=K{\begin{pmatrix}x-2^{-i}\times y\\x\times 2^{-i}+y\end{pmatrix}}$

Il faut noter que la constante $K$ 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 $K(i)$ et y multiplier le résultat. Or, le produit de tous les $K(i)$ est une constante, approximativement égale à 0,60725. Cette omission donne :

${\begin{pmatrix}x'\\y'\end{pmatrix}}={\begin{pmatrix}x-2^{-i}\times y\\x\times 2^{-i}+y\end{pmatrix}}$

Le tout se simplifie en :

$x'=K(x-2^{-i}\times y)$

$y'=K(x\times 2^{-i}+y)$

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

$x'=K(x-y>>i)$

$y'=K(x>>i+y)$

Les circuits CORDIC

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

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

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

Pour cela, une solution serait d'éliminer les résultats redondants, où deux opérandes ont le même résultat. C'est possible avec les fonctions trigonométriques comme sinus ou cosinus, tangente, mais pas vraiment pour les autres. Par exemple, une méthode pour cela utilise les identités trigonométriques pour calculer les résultats non-précalculés.

Par exemple, on sait que $\sin {-a}=-\sin {a}$, ce qui 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 $\sin {-a}$ à partir de celui de $\sin {a}$.

De même, l'identité $\sin {a}=\cos {{\frac {\pi }{2}}-a}$ 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é $\sin {a}=\sin {\pi -a}$ 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. À 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éaire

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.

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.

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