Chapitre 3 : Déterminisme et arithmétique à virgule fixe

3.1 Pourquoi le déterminisme n’est pas négociable

Le chapitre 1 a introduit les modèles de synchronisation réseau, le Lockstep et le Rollback, qui exigent tous deux que la simulation produise des résultats bit à bit identiques sur chaque machine. Le chapitre 2 a montré comment des allocateurs sur mesure éliminent une première source d’indéterminisme, à savoir l’ordre et l’adresse des allocations. La plus insidieuse, pourtant, ne se trouve pas dans la mémoire : elle se cache dans les calculs eux-mêmes.

Posons la question directement. Deux machines qui exécutent le même code physique avec les mêmes entrées produiront-elles le même résultat ? Si l’on s’en remet à l’arithmétique à virgule flottante standard, la réponse est un non catégorique.¹

3.2 Les pièges de l’arithmétique à virgule flottante (IEEE 754)

3.2.1 La norme IEEE 754

Les nombres à virgule flottante (floating-point) sont représentés selon la norme IEEE 754 sous la forme :

$(-1)^s \times 1.m \times 2^{e - \text{biais}}$

Où $s$ est le bit de signe, $m$ la mantisse (23 bits pour float, 52 bits pour double) et $e$ l’exposant (8 ou 11 bits). Cette représentation couvre une plage dynamique colossale, de $\sim 10^{-38}$ à $\sim 10^{38}$ pour un float, mais au prix de compromis critiques.²

3.2.2 Les sources d’indéterminisme

Prenons un exemple concret. Sur une simulation de 1000 ticks avec un seul calcul de position par tick, une différence d’arrondi de $2^{-23}$ (1 ULP pour float) au tick 0 s’amplifie exponentiellement par propagation d’erreur. Après un millier de ticks d’une simulation chaotique, typiquement de la physique avec contacts, les positions divergent de façon macroscopique : un joueur voit un projectile là où un autre ne voit rien.³

3.2.3 Contre-mesures en virgule flottante

On peut contraindre le compilateur pour réduire, sans pour autant l’éliminer, l’indéterminisme flottant :

// Forcer le SSE2 au lieu du x87 (précision stricte 32/64 bits)
// GCC/Clang : -msse2 -mfpmath=sse
// MSVC : /fp:strict

// Interdire la réassociation et les FMA implicites
// GCC/Clang : -fno-fast-math (défaut)
// MSVC : /fp:strict (pas /fp:fast !)

// Définir le mode d'arrondi au démarrage
#include <cfenv>
fesetround(FE_TONEAREST);

Ces mesures, cependant, ne garantissent pas le déterminisme d’une plateforme à l’autre (x86 contre ARM). Les instructions NEON d’ARM et SSE d’Intel n’implémentent pas les opérations de la même façon à l’ULP près. Pour un déterminisme absolu entre plateformes, il n’existe qu’une seule solution vraiment fiable : l’arithmétique à virgule fixe.

3.3 L’arithmétique à virgule fixe

3.3.1 Principe et notation Q

Un nombre à virgule fixe est un entier dont une fraction fixe des bits représente la partie fractionnaire. La notation Q spécifie cette répartition. En Q16.16, seize bits codent la partie entière signée et seize la partie fractionnaire, ce qui donne une plage de $[-32768, +32767.999985]$ et une résolution de $2^{-16} \approx 0.0000153$. Le Q8.24 déplace le curseur vers la précision, avec huit bits entiers et vingt-quatre fractionnaires, au prix de la plage. Le Q32.32, enfin, stocké dans un int64_t, réunit une plage massive et une haute précision.

La conversion, elle, est triviale. Pour stocker la valeur $x$ au format Q16.16, on calcule $\text{fixed} = (int32\_t)(x \times 2^{16})$, et pour revenir en arrière, $x = \text{fixed} / 2^{16}$.

struct Fixed32 {
    static constexpr int FRAC_BITS = 16;
    static constexpr int32_t ONE = 1 << FRAC_BITS;  // 65536

    int32_t raw;

    static Fixed32 FromFloat(float f) { return {(int32_t)(f * ONE)}; }
    static Fixed32 FromInt(int i)     { return {i << FRAC_BITS}; }
    float ToFloat() const { return (float)raw / ONE; }

    // Addition et soustraction : directes
    Fixed32 operator+(Fixed32 b) const { return {raw + b.raw}; }
    Fixed32 operator-(Fixed32 b) const { return {raw - b.raw}; }
};

3.3.2 Multiplication et Division

La multiplication de deux nombres Q16.16 nécessite un intermédiaire 64 bits pour éviter le débordement, puis un décalage pour réaligner le point fixe :

$\text{result} = \frac{a \times b}{2^{16}}$

Fixed32 operator*(Fixed32 b) const {
    // Promotion en 64 bits pour éviter le débordement
    int64_t temp = (int64_t)raw * b.raw;
    return {(int32_t)(temp >> FRAC_BITS)};
}

Fixed32 operator/(Fixed32 b) const {
    // Pré-décalage du dividende pour maintenir la précision
    int64_t temp = ((int64_t)raw << FRAC_BITS);
    return {(int32_t)(temp / b.raw)};
}

La division est l’opération la plus coûteuse en virgule fixe : sur x86, l’instruction IDIV prend de 20 à 90 cycles selon la taille des opérandes, contre 3 à 5 cycles pour une multiplication. C’est pourquoi les moteurs déterministes l’évitent autant que possible et la remplacent par une multiplication par l’inverse pré-calculé, ou par des tables de correspondance (LUT).⁴

3.3.3 Saturation ou repli (wrapping)

Que se passe-t-il lors d’un débordement ? Deux comportements sont possibles. Le repli (wrapping), comportement par défaut en C pour les types non signés, fait « boucler » le résultat : $32767 + 1 = -32768$. C’est silencieux, donc catastrophique. La saturation, à l’inverse, plafonne le résultat à la valeur maximale ou minimale ; c’est plus sûr, mais il faut des vérifications explicites.

Fixed32 SaturatingAdd(Fixed32 a, Fixed32 b) {
    int64_t result = (int64_t)a.raw + b.raw;
    if (result > INT32_MAX) return {INT32_MAX};
    if (result < INT32_MIN) return {INT32_MIN};
    return {(int32_t)result};
}

Les processeurs ARM, eux, ont des instructions de saturation matérielles (QADD, QSUB). Sur mobile et sur embarqué, la saturation y est donc pratiquement gratuite.

3.4 Fonctions trigonométriques : CORDIC et LUT

3.4.1 L’algorithme CORDIC

Les fonctions sin(), cos() et atan2() de la bibliothèque standard sont calculées en virgule flottante, et ne sont donc pas déterministes d’une plateforme à l’autre. En virgule fixe, on leur préfère l’algorithme CORDIC (COordinate Rotation DIgital Computer), inventé par Volder en 1959 : il calcule les fonctions trigonométriques par une série de rotations itératives qui n’utilisent que des additions, des soustractions et des décalages de bits, sans la moindre multiplication ni division.⁵

Le principe : pour calculer $\sin(\theta)$ et $\cos(\theta)$, CORDIC part du vecteur $(1, 0)$ et applique $N$ rotations d’angles pré-calculés $\alpha_i = \arctan(2^{-i})$ :

$x_{i+1} = x_i - \sigma_i \cdot 2^{-i} \cdot y_i$ $y_{i+1} = y_i + \sigma_i \cdot 2^{-i} \cdot x_i$

Où $\sigma_i = +1$ ou $-1$ selon le signe de l’angle restant. Après $N$ itérations, $(x_N, y_N)$ converge vers $(\cos\theta, \sin\theta)$ multiplié par un facteur constant $K = \prod \frac{1}{\sqrt{1+2^{-2i}}} \approx 0.6073$.

Avec 16 itérations, CORDIC atteint une précision de 16 bits, ce qui tombe parfaitement pour un format Q16.16.

3.4.2 Tables de correspondance (LUT)

Pour les cas où la performance prime sur la flexibilité, une Look-Up Table (LUT) pré-calcule les valeurs en virgule fixe pour toutes les entrées possibles :

// Table de sinus pour 4096 angles (résolution de 360/4096 ≈ 0.088°)
static constexpr int32_t SIN_TABLE[4096] = { /* pré-calculé */ };

Fixed32 FixedSin(Fixed32 angle) {
    // Normaliser l'angle en index [0, 4095]
    int index = (angle.raw >> 4) & 0xFFF; // Masque 12 bits
    return {SIN_TABLE[index]};
}

L’accès à la LUT se fait en $O(1)$ : un simple accès mémoire indexé. Le compromis se joue sur la mémoire consommée (4096 × 4 octets, soit 16 Ko pour une table) et sur la résolution angulaire, forcément finie. Une interpolation linéaire entre deux entrées voisines améliore la précision pour un surcoût minime.

3.5 SIMD et virgule fixe

Les instructions SIMD (Single Instruction, Multiple Data) traitent 4, 8 ou 16 valeurs entières en parallèle dans un seul registre vectoriel. Comme les opérations en virgule fixe sont des opérations entières, elles profitent naturellement de cette vectorisation.

#include <immintrin.h>

// Multiplication de 8 valeurs Q16.16 en parallèle (AVX2)
__m256i FixedMul8(__m256i a, __m256i b) {
    // Extraire les parties basse et haute de la multiplication 32×32→64
    __m256i lo = _mm256_mullo_epi32(a, b);  // 32 bits bas
    __m256i hi = _mm256_mulhi_epi32(a, b);  // 32 bits hauts (non standard)
    // Note : implémentation simplifiée — en pratique, utiliser
    // _mm256_mul_epi32 pour les 64 bits complets puis recombiner
    return _mm256_srli_epi32(lo, 16); // Décalage pour réaligner
}

Sur les processeurs modernes, les opérations entières SIMD ont une latence comparable aux opérations flottantes SIMD. La différence principale est l’absence d’instructions FMA (Fused Multiply-Add) pour les entiers, ce qui nécessite deux instructions séparées au lieu d’une pour les calculs de type $a \times b + c$.⁶

3.6 Comparaison microarchitecturale : ALU contre FPU

3.6.1 Latences et débits mesurés

On entend souvent que « la virgule fixe est plus rapide que la virgule flottante ». C’est un mythe hérité des années 1990, que les mesures sur les processeurs modernes démentent. Sur les architectures de bureau et serveur actuelles, la FPU vectorisée dépasse souvent l’ALU entière en débit pur, grâce aux instructions FMA et à la largeur des pipelines :

Sources : Agner Fog, Instruction Tables⁷

La puissance de feu vectorielle est colossale. Un processeur capable de 2 FMA AVX2 par cycle sur des vecteurs de 8 float produit $2 \times 8 \times 2 = 32$ FLOPs par cycle et par cœur. L’architecture Zen 4 d’AMD monte à 48 FLOPs/cycle grâce à ses unités FMA et ADD indépendantes, et le cœur Apple Firestorm (M1) aligne 4 pipelines NEON de 128 bits, ce qui quadruple le débit des architectures ARM antérieures.⁷

Or, lors d’un calcul intensif en virgule fixe, cette FPU massivement vectorisée reste complètement inactive. C’est l’ALU qui devient le goulot d’étranglement, alors qu’elle doit déjà gérer les compteurs de boucle, l’arithmétique de pointeurs et les adresses. Autre coût caché : chaque multiplication fixe réclame un décalage de bits pour réaligner la virgule, et la prévention du débordement impose des promotions 32→64 bits coûteuses.

3.6.2 Le gouffre de la division

La division pénalise l’ALU comme la FPU, et de façon asymétrique. Contrairement à la multiplication, les instructions DIV, IDIV et FDIV ne sont en général pas entièrement pipelinées : elles reposent sur un algorithme itératif, bit à bit ou microcodé.

• Division entière x86/x64 : 12 à 44 cycles selon la taille des opérandes.
• Division flottante (DIVPD sur Haswell) : 10 à 20 cycles, débit d’une instruction tous les 8 à 14 cycles.
• La division a un débit 6× à 40× pire que la multiplication dans une boucle serrée.⁷

C’est pourquoi les algorithmes haute performance remplacent systématiquement la division par une multiplication par l’inverse pré-calculé dès que c’est mathématiquement possible.

3.6.3 Émulation logicielle sur ARM sans FPU (soft-float)

Beaucoup de microcontrôleurs ARM (Cortex-M0, M3 de base) n’ont pas de FPU matérielle. L’ABI ARM contourne le problème par émulation logicielle (soft float) : le compilateur injecte des appels vers des fonctions de bibliothèque (__aeabi_fmul, __aeabi_fadd) qui décomposent chaque opération flottante en instructions entières élémentaires.⁸

Source : SEGGER Runtime Library Benchmarks⁸

Sur ces cibles contraintes, réécrire les algorithmes en virgule fixe produit une accélération de 10× à 50×. C’est précisément le scénario du matériel BCI embarqué dans un casque FullDive, où le processeur de traitement du signal (DSP) peut être un Cortex-M4 sans FPU activée.

3.7 Quantification INT8 pour l’inférence IA

La virgule fixe trouve un usage spectaculaire dans l’intelligence artificielle embarquée. Pendant l’entraînement des réseaux de neurones, le standard reste le FP32, ou le FP16/BFloat16, pour éviter l’évanouissement du gradient. Mais au moment de l’inférence, c’est-à-dire du déploiement en production, la quantification ramène les poids du réseau de 32 bits flottants à 8 bits entiers (INT8), soit, au fond, un format de type virgule fixe.⁹

L’effet est considérable. La mémoire est divisée par quatre : un modèle de 100 Mo tombe à 25 Mo. L’accélération, ensuite, est spectaculaire ; en INT8, les cœurs Tensor d’une NVIDIA H100 vont 13 à 59 fois plus vite qu’en FP32 vectoriel, tout simplement parce que le goulot d’étranglement est la bande passante mémoire (HBM), pas le calcul. Quant à la perte de précision, elle reste modérée, et le Quantization-Aware Training (QAT) la rattrape via TensorRT ou TFLite.

Pour LplKernel, la quantification INT8 est directement applicable à l’inférence BCI embarquée : un réseau LSTM ou Transformer léger classifiant les signaux EEG en temps réel (Motor Imagery, P300) peut être quantifié pour s’exécuter sur le processeur embarqué du casque sans GPU dédié.

3.8 Applications au-delà du jeu vidéo

L’arithmétique à virgule fixe n’est pas une curiosité rétro : elle reste omniprésente dans des domaines critiques.

3.9 Synthèse : la règle d’or du déterminisme

Pour garantir le déterminisme dans LplKernel, la règle tient en une phrase :

Toute opération mathématique dont le résultat influence l’état de la simulation doit être effectuée en arithmétique à virgule fixe.

Le rendu graphique, lui, peut se permettre des flottants : il n’affecte pas l’état logique. L’interface aussi. En revanche, la physique, la logique de jeu et le réseau, bref tout ce qui touche à l’état synchronisé, doivent passer par l’arithmétique entière déterministe.

Notes de bas de page (chapitre 3)