Virgule flottante ou virgule fixe : un choix entre précision et efficience

Si vous cherchez à optimiser un logiciel et si celui-ci manipule des valeurs réelles, alors il y a de grandes chances pour que le passage des données à l’arithmétique Fixed Point (Virgule Fixe) vous fasse économiser du temps d’exécution et de l’énergie.
		Baptiste Daniel Lamazière Ingénieur R&D, spécialisé en arithmétique à virgule fixe

_____________________________________________________________________________________________________

Représentation des nombres à virgule

Virgule flottante

En informatique, le type de données qui sert le plus souvent à représenter des nombres réels est le float. Ce type de données est défini par la norme IEEE 754, qui définit les calculs et le comportement du type float. Selon la norme IEEE-754, un float représente un nombre en 3 parties : 

1. Son signe s
2. Son exposant e
3. Sa mantisse m

On retrouve ensuite la valeur du nombre avec la formule suivante donnée par le standard IEEE 754[08] :

Le standard IEEE 754 permet de représenter des nombres avec des valeurs d’exposant différentes en s’adaptant aux valeurs représentées lors de l’exécution. L’utilisation de standard est relativement simple pour les développeurs, en effet, les nombres peuvent s’écrire directement sous leur forme décimale et le standard prend en charge les erreurs arithmétiques comme le dépassement de valeur ou la division par zéro.

L’arithmétique flottante nécessite de mettre en place des opérations arithmétiques spécifiques, initialement celles-ci étaient implémentées dans la partie logicielle, ce qui obligeait les développeurs à programmer eux-mêmes ces opérations. 

Mais, à partir des années 1950, les processeurs ont commencé à inclure des FPU (Floating Point Unit, coprocesseur dédié aux calculs en arithmétique flottante) ce qui permet des calculs, sur des nombres en arithmétique flottante, rapides et ne nécessitant pas d’intervention de la part du développeur.

Les progrès réalisés par les fabricants de hardware dans le domaine des FPU permettent maintenant d’utiliser les types floats sur de nombreux ordinateurs avec des temps de calculs très faibles.

 

Virgule fixe

Bien que la méthode de représentation float soit utilisée en grande majorité, il existe d’autres formats parmi lesquels on trouve la représentation en virgule fixe. La virgule fixe est un format plus ancien que la virgule flottante, qui était utilisé avant l’apparition de standards et de composants électroniques permettant les calculs sur des nombres représentés en arithmétique à virgule flottante. Toutefois, ce format est toujours utilisé dans des cas où la cible matérielle sur laquelle s’exécute le logiciel ne dispose pas de FPU.

La représentation en virgule fixe consiste à représenter un nombre réel de la même façon qu’un entier. On fixe arbitrairement une taille de partie entière et une taille de partie fractionnaire (ce qui fixe l’emplacement de la virgule), on représente la partie entière sous la forme d’un entier et la partie fractionnaire en représentant les puissances de 2 inverses (2^-1,2^-2, etc) [Yates]. La représentation en virgule fixe englobe donc plusieurs formats. Par exemple, sur 32 bits, on peut représenter des réels à l’aide d’une représentation en virgule fixe dite Q0.31, c’est-à-dire avec un bit de signe, aucun bit de partie entière et une partie fractionnaire de 31 bits; on peut également opter pour un format Q15.16, c’est à dire avec un bit de signe, une partie entière codée sur 15 bits et une partie fractionnaire codée sur 16 bits.

Pour retrouver la valeur d’un nombre représenté en virgule fixe on applique la formule suivante :

où

• v est la valeur du nombre,
• s est le bit de signe,
• 0 si positif et 1 si négatif;
• m est la taille de la partie entière,
• et n la taille de la partie fractionnaire de notre représentation;
• enfin b_i est la valeur du bit d’indice i dans la représentation en virgule fixe.

Et, pour convertir un nombre décimal en son équivalent en virgule fixe on applique l’algorithme suivant :

où

• fxp est la variable qui stocke la représentation en virgule fixe,
• int est la partie entière du nombre décimal
• et frac la partie fractionnaire du nombre décimal.

Pour comprendre pourquoi la représentation en virgule flottante est souvent préférée à la représentation en virgule fixe, il faut aussi comparer l’étendue de valeurs qu’on peut représenter avec une seule variable de chaque représentation.

 

Gamme Dynamique

Pour mesurer l’étendue de valeurs qu’une variable peut représenter, on utilise une grandeur appelée gamme dynamique. La gamme dynamique est la valeur exprimée en décibels du rapport de la plus grande valeur atteignable sur la plus petite valeur possible. La formule de la gamme dynamique est donc la suivante, où X_MAX est la valeur de plus grande amplitude que l’on peut représenter et X_MIN la valeur de plus petite amplitude.

La valeur de la gamme dynamique dépend donc de la taille de l’exposant dans le format de représentation. Si on prend l’exemple du type de données float qui représente les nombres réels sur 32 bits avec 1 bit de signe, 8 bits d’exposant et 23 bits de mantisse, on peut estimer la gamme dynamique de la façon suivante : avec 8 bits pour représenter l’exposant, la plus grande valeur d’exposant possible est 2⁸-1 = 127  et la plus petite est -127. Le rapport X_MAX / X_MIN est donc de 2^2*127+1,

La gamme dynamique du type de données float (IEEE 754) est alors de 1535 (Pas mal, pas mal ! Enfin, ça dépend avec quoi on compare).

Si on compare avec la gamme dynamique de la virgule fixe on se rend compte que la gamme dynamique évolue linéairement en fonction du nombre de bits utilisés pour encoder la variable virgule fixe, si on note N_MAX l’indice du bit de poids le plus fort et N_MIN l’indice du bit de poids faible, on obtient la formule suivante :

Pour 32 bits, on a donc une gamme dynamique en décibels de 186. On est loin des 1535 du format float.

 

Avantages de la virgule fixe

Toutefois, même si la virgule fixe a une gamme dynamique plus petite, elle permet d’utiliser des opérations binaires et entières pour ses opérations, ce qui est souvent moins consommateur d’énergie que d’utiliser les opérations de float pour un même calcul. 

Le tableau suivant détaille ces différences de performances, pour les opérations d’addition et de multiplication, sur des types ac_int et ac_float sur 32 et 64 bits, sur une cible ASIC (un Fully Depleted Silicon On Insulator, FDSOI de 28nm), on compare pour chaque opération sur les différents types : 

1. La surface utilisée par l’opération
2. La puissance totale utilisée par le design 
3. Le chemin critique (c’est à dire la latence) de l’opération
4. Le produit puissance-latence, (Power-Delay Product : PDP), l’énergie nécessaire pour réaliser l’opération

	Area (µm2)	Total power (mW)	Critical path (ns)	Power-Delay  Product (fJ)
32-bit float ADD	653	4.39E-4	2.42	1.06E-3
64-bit float ADD	1453	1.12E-3	4.02	4.50E-3
32-bit int ADD	189	3.66E-5	1.06	3.88E-5
64-bit int ADD	373	7.14E-5	2.10	1.50E-4
32-bit float MUL	1543	8.94E-4	2.09	1.87E-3
64-bit float MUL	6464	6.56E-3	4.70	3.08E-2
32-bit int MUL	2289	6.53E-5	2.38	1.55E-4
64-bit int MUL	8841	1.84E-4	4.52	8.31E-4

Tableau 1 : Comparaison des coûts pour des opérations en virgule flottante et des opérations entières

Les résultats de ce tableau permettent de comprendre que le passage des données en arithmétique virgule fixe, réduira la latence des opérations d’addition sur 32 et 64 bits et de multiplication sur 64 bits. De plus, le passage à la virgule fixe réduira la consommation d’énergie des opérations d’addition et de multiplication peu importe la taille des données.

 

Pour conclure, en utilisant la virgule fixe, certaines instructions de calcul (comme l’addition) deviennent plus courtes en nombre de cycles que les opérations flottantes; attention car ce n’est pas le cas de toutes les opérations, en effet la multiplication en arithmétique virgule fixe est plus longue que la multiplication en arithmétique virgule flottante. 

De plus, les opérations en arithmétique virgule fixe demandent moins de puissance pour être effectuées que les opérations en arithmétique virgule flottante (Tableau 1).

 

Comment convertir un code de la virgule flottante à la virgule fixe ?

Lorsqu’on convertit un code en virgule fixe, on ne peut pas s’adapter aux ordres de grandeurs des valeurs prises par la variable au runtime comme avec la virgule flottante. Il faut donc savoir avant d’exécuter le code quelles seront les valeurs prises par la variable.

Pour ce faire, chez WedoLow, on réalise une analyse dynamique des variables en virgule flottante dans le programme que l’on souhaite optimiser. On instrumente ces variables en remplaçant leur type par un type qui va enregistrer toutes les valeurs prises par la variable au cours de l’exécution du programme. 

Il y a plein de façons de connaître l’ordre de grandeur des valeurs que prendront les variables lors de l’exécution d’un code, mais mieux vaut choisir une méthode que vous pouvez automatiser (notamment si vous souhaitez convertir un grand nombre de variables). Une méthode qui donne un résultat lisible et compréhensible (afficher toutes les valeurs prises par une variable dans la console n’est peut-être pas très bon pour votre vue), et qui soit exploitable.

 

À l’issue de cette analyse dynamique, on peut définir le format de la représentation en virgule fixe que va prendre chaque variable. Attention, car un format de représentation mal adapté aux valeurs prises par la variable engendre des erreurs de précision (on perd des bits de poids faible car la partie entière est plus grande que nécessaire) ou de dépassement (on perd des bits de poids fort car la partie fractionnaire est trop grande).

Attention également à ne pas trop souvent écrire des opérations entre variables de formats différents, car il faut alors ajouter des décalages. Ces décalages génèrent des instructions en plus dans le code généré en langage machine, et par conséquent du temps d’exécution en plus. 

Afin d’éviter d’avoir trop de décalages dans notre code en virgule fixe, on peut regrouper entre elles les variables qui ont des opérations en commun et leur assigner le même format de représentation. 

Il faut donc arbitrer pour chaque variable entre la précision et la réduction du nombre d’instructions. 

Pour chaque variable, on peut choisir un format optimal selon la valeur d’exposant maximale que la variable prendra. Mais, on peut également choisir de diviser une variable en 2 pour avoir 2 variables représentées plus précisément, ou inversement, on peut choisir de représenter plusieurs variables avec le même format pour réduire le temps d’exécution.

 

Vérifications

À l’issue de l’optimisation, il est primordial de vérifier que le code optimisé donne toujours le même résultat que la version d’origine. On réalise donc un test de non-régression avec les mêmes données d’entrées, et on quantifie l’écart entre les valeurs de sortie pour calculer l’erreur induite par le changement de format de représentation. 

Attention car les types en virgule fixe n’ont pas forcément de mécanisme de gestion des erreurs comme c’est le cas pour les floats du standard IEEE-754. Il n’y a donc pas de NaN (Not a Number), la division par zéro n’est pas gérée et c’est au développeur d’ajouter des vérifications pour éviter ce genre d’erreur.

Attention également, dans certains cas (rarissimes) la virgule fixe peut s’avérer plus précise que le format en virgule flottante. Il faut alors comparer les valeurs obtenues avec un type plus précis (en double précision voire des types à précision multiple comme MPFR [MPFR] [MPFR2]).

Pour résumer 

1. L’optimisation de virgule fixe consiste à modifier le format de représentation des réels depuis une représentation en virgule flottante qui s’adapte aux ordre de grandeurs des valeurs prises par une variable donnée vers une représentation en virgule fixe, qui ne peut pas s’adapter aux valeurs et qui fixe donc un ordre de grandeur par défaut pour sa représentation.

2. Pour définir cet ordre de grandeur il faut connaître par avance les valeurs que les variables vont prendre lors de l’exécution du programme.

3. Une fois que l’on peut anticiper les ordres de grandeurs que les variables vont prendre, il faut définir le format des représentations en virgule fixe. Pour chaque variable, on réalise un arbitrage entre réduction du temps d’exécution et précision du résultat.

4. Le fait de passer en virgule fixe change la nature des instructions assembleur nécessaires pour les opérations de calcul des nombres à virgule. Ces nouvelles instructions sont plus courtes et moins consommatrices d’énergie.

5. Le passage en virgule fixe a un impact sur les résultats d’opérations arithmétiques impliquant des nombres à virgule, il est donc nécessaire de comparer le comportement du code optimisé avec celui du code d’origine.

Sources

[Yates] YATES, Randy. Fixed-point arithmetic: An introduction. Digital Signal Labs, 2009, vol. 81, no 83, p. 198.

[MPFR] FOUSSE, Laurent, HANROT, Guillaume, LEFÈVRE, Vincent, et al. MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Transactions on Mathematical Software (TOMS), 2007, vol. 33, no 2, p. 13-es.

[MPFR2] GNU MPFR 4.2.1 manual , https://www.mpfr.org/mpfr-current/mpfr.html#Top

[Benjamin Barrois] Methods to evaluate accuracy-energy trade-off in operator-level approximate computing. Computer Arithmetic. Université de Rennes, 2017. English. ⟨NNT : 2017REN1S097⟩. ⟨tel-01665015v2⟩

[08] “IEEE Standard for Floating-Point Arithmetic”. In : IEEE Std 754-2008 (2008),

70. 1-70. doi : 10.1109/IEEESTD.2008.4610935.