🔢 mathematics

Performance evaluation of branch-free fused multiply-add algorithms for multi-component-type multiple-precision floating-point arithmetic

Cet article propose et évalue de nouveaux algorithmes de multiplication-accumulation fusionnée sans branchement pour l'arithmétique de précision multiple de double, triple et quadruple mot, démontrant qu'ils permettent d'obtenir des améliorations de performance supplémentaires par rapport aux méthodes existantes en éliminant les branchements conditionnels.

Auteurs originaux : Tomonori Kouya

Publié 2026-07-14

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tomonori Kouya

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez de construire une calculatrice super précise en utilisant uniquement des briques Lego standard du commerce. Ces briques sont les nombres à virgule flottante normaux de votre ordinateur. Habituellement, quand vous empilez ces briques pour fabriquer un « double-mot » (deux briques), un « triple-mot » (trois briques) ou un « quadruple-mot » (quatre briques), vous devez constamment vérifier la taille des pièces pendant que vous construisez. Si une pièce est trop grande ou trop petite, vous devez vous arrêter, faire une pause et réorganiser la pile. Dans le monde des puces informatiques, ces « pauses » sont appelées branches.

Si vous essayez de construire un million de ces piles à la fois (comme sur une carte graphique moderne ou un processeur puissant), ces pauses deviennent un cauchemar. C'est comme un embouteillage où chaque voiture doit s'arrêter pour vérifier un panneau différent avant de continuer. Certaines voitures vont à gauche, d'autres à droite, et la file entière ralentit. C'est ce qu'on appelle la « divergence de voie », et cela tue les performances.

La Grande Découverte : L'Autoroute « Sans Arrêt »
Le papier de Tomonori Kouya introduit une nouvelle façon de construire ces piles qui ne s'arrête jamais pour vérifier les panneaux. C'est un algorithme « sans branche » (branch-free). Au lieu de demander « Est-ce que cette pièce est assez grande ? » et d'attendre une réponse, la nouvelle méthode utilise un itinéraire intelligent et pré-planifié qui fonctionne parfaitement, peu importe l'aspect des pièces.

Le papier proule, en utilisant un mathématicien-robot super intelligent (un solveur SMT nommé FPANVerifier), que ce nouvel itinéraire est sûr et précis pour tous les formats informatiques standards. La conclusion principale est qu'en supprimant ces pauses de « arrêt et vérification », l'ordinateur peut calculer beaucoup plus vite.

Le Tour de Magie : Fusionner le Mouvement
Le papier se concentre sur un mouvement spécifique appelé Fused Multiply-Add (FMA - Multiplication-Addition Fusionnée). Imaginez que vous deviez multiplier deux nombres, puis en ajouter un troisième. Habituellement, vous le faites en deux étapes :

Multiplier (et peut-être faire une pause pour corriger le résultat).
Ajouter (et peut-être faire une autre pause).

L'auteur propose une version « fusionnée » qui fait les deux en un seul mouvement fluide, comme un ninja qui lance un couteau et le rattrape dans le même souffle.

Pour le Double-Mot (2 briques) : L'ancienne méthode prenait 29 étapes. La nouvelle n'en prend que 17.
Pour le Triple-Mot (3 briques) : L'ancienne méthode prenait 96 étapes. La nouvelle en prend 66.
Pour le Quadruple-Mot (4 briques) : L'ancienne méthode prenait 209 étapes. La nouvelle en prend 146.

Le papier discute également d'une méthode de « raccourci » proposée par d'autres chercheurs (la méthode en 6 étapes). Crucialement, ce raccourci n'est PAS généralement valide. C'est un outil ultra-rapide qui ne fonctionne que si les nombres sont déjà parfaitement disposés d'une manière spécifique (plus précisément, si le nombre ajouté est au moins deux fois plus grand que le produit). Si vous essayez d'utiliser ce raccourci sur des problèmes mathématiques généraux comme la division ou la racine carrée, où vous ne pouvez pas garantir que ces nombres s'aligneront ainsi, la précision se dégrade considérablement. La nouvelle méthode de l'auteur, cependant, fonctionne pour n'importe quels nombres sans nécessiter d'arrangements spéciaux, ce qui en fait un véritable remplacement direct pour les mathématiques de haute précision.

À quel point sommes-nous sûrs ?
Les auteurs sont incroyablement confiants, mais ils soutiennent cela par des preuves concrètes, pas seulement par des suppositions.

Vérifié par machine : Ils n'ont pas seulement écrit du code en espérant ; ils ont utilisé un programme informatique pour prouver mathématiquement que l'erreur de leur nouvelle méthode est infime (spécifiquement, bornée par des formules comme $34u^2$ , $184u^3$ et $812u^4$ , où $u$ est la minuscule erreur d'arrondi d'un seul nombre).
Testé partout : Ils ont testé leurs nouveaux algorithmes sur deux supercalculateurs très différents : une puce basée sur Arm (GB10) et une puce basée sur Intel (H100).
Les Résultats :
- Sur la puce Arm, la nouvelle méthode était 1,5 à 2,1 fois plus rapide pour les calculs de division et de racine carrée.
- Sur la puce Intel, elle était 1,2 à 1,6 fois plus rapide pour la division et la racine carrée.
- Pour les tâches mathématiques massives comme la multiplication de matrices (GEMM), l'accélération était encore plus spectaculaire sur la puce Arm, atteignant jusqu'à 2,0 fois plus vite pour les triple-mots.

L'Alternative « Exacte »
Le papier mentionne également une version « Parfaite » de ce tour de magie appelée Exact FMA. Cette version est encore plus précise, mais elle vient avec un prix élevé : elle est 6 à 11 fois plus lente que la nouvelle méthode proposée. Les auteurs suggèrent d'utiliser cette version « Parfaite » uniquement lorsque vous avez absolument, 100 % besoin de la précision la plus élevée et que la vitesse ne vous importe pas. Pour presque tout le reste, la méthode « sans branche » est la gagnante.

Et concernant « l'ancienne » méthode ?
Le papier corrige également une erreur d'une version antérieure de cette recherche. Auparavant, les auteurs comparaient leur nouvelle méthode à une ancienne méthode « entièrement distillée » qui était incroyablement lente et inefficace. Ils ont réalisé que ce n'était pas un combat équitable. Lorsqu'ils ont comparé leur nouvelle méthode à la méthode « sans branche » réelle (qui est déjà assez rapide), la nouvelle méthode l'emportait toujours, mais l'accélération était plus modeste (environ 1,3 à 1,7 fois plus rapide). C'est toujours une victoire énorme, mais c'est une victoire plus réaliste.

L'essentiel
Ce papier montre qu'en supprimant les pauses de « arrêt et vérification » dans les mathématiques de haute précision, nous pouvons rendre les ordinateurs nettement plus rapides sans perdre en précision. C'est comme passer d'une voiture qui doit s'arrêter à chaque intersection à une voiture qui peut voler par-dessus elles. Les auteurs ont prouvé que cela fonctionne, l'ont testé sur du matériel réel et ont montré qu'il est prêt à être utilisé dans la prochaine génération de calculatrices ultra-rapides.

Résumé technique : Évaluation des performances d'algorithmes de multiplication-accumulation fusionnée sans branchement pour l'arithmétique multi-composantes de précision multiple

1. Énoncé du problème

L'arithmétique à précision multiple multi-composantes (par exemple, Double-Word/DW, Triple-Word/TW, Quadruple-Word/QW) atteint des performances élevées en regroupant des composantes standard binary64 (ou binary32) et en gérant les retenues de manière exacte via des transformations sans erreur (EFTs). Cependant, les étapes de renormalisation dans ces algorithmes reposent généralement sur des branchements if dépendant de la magnitude des valeurs intermédiaires. Ces branchements causent des pénalités de performance significatives dans les implémentations SIMD et GPU en raison de la divergence de registres (lane divergence) ou de warps.

Bien que Zhang et Aiken aient précédemment proposé des algorithmes sans branchement pour l'addition et la multiplication DW/TW/QW, la composition de ces opérations distinctes sans branchement reste sous-optimale. Plus précisément, effectuer une opération de multiplication-accumulation fusionnée (FMA) $z \leftarrow x \cdot y + c$ en composant séquentiellement une multiplication sans branchement et une addition sans branchement entraîne un nombre élevé d'opérations (par exemple, 29 flops pour DW, 96 pour TW, 209 pour QW) et des étapes de renormalisation redondantes.

2. Méthodologie

Le document propose de nouveaux algorithmes de multiplication-accumulation fusionnée (FMA) sans branchement pour l'arithmétique DW, TW et QW (ainsi que leurs variantes de base en simple précision DS, TS, QS). La méthodologie centrale implique :

Structure algorithmique : Le FMA proposé calcule $z \leftarrow x \cdot y + c$ $z \leftarrow x \cdot y + c$ en une seule étape fusionnée plutôt qu'en composant des multiplications et des additions séparées. Le processus comprend :
1. Expansion du produit : Décomposition des produits de composantes en utilisant TwoProd.
2. Accumulation par poids : Rassemblement des termes arrivant à la même position de puissance de deux en utilisant des chaînes de TwoSum.
3. Renormalisation : Remodelage du résultat en $K$ composantes non chevauchantes.
Sélection des portes et vérification : Un principe de conception critique est la sélection des portes de renormalisation basées sur des préconditions vérifiables par machine. L'algorithme utilise FastTwoSum (3 flops) uniquement là où la précondition $\text{exp}(a) \ge \text{exp}(b)$ peut être prouvée par machine pour toutes les précisions $p$ en utilisant le solveur SMT z3 via l'outil FPANVerifier. Là où la précondition ne peut être prouvée, TwoSum (6 flops) est utilisé pour garantir la correction.
Commutativité : Pour assurer un accord bit à bit sous échange d'opérandes ( $x \leftrightarrow y$ ), l'algorithme réassocie les sommes diagonales afin que les paires transposées (par exemple, $P_{ij}$ et $P_{ji}$ ) soient traitées en premier. Ceci est réalisé sans augmenter le nombre d'opérations.
Variante exacte : Une variante de « distillation » (Exact FMA) est également implémentée comme référence. Elle effectue une expansion complète sans erreur suivie de multiples passages de TwoSum pour atteindre des bornes d'erreur relatives au résultat, bien qu'avec un coût de calcul nettement plus élevé.

3. Contributions clés

3.1 Constructions FMA minimales sans branchement

Le document présente des algorithmes FMA sans branchement minimaux et vérifiés par machine avec les nombres d'opérations suivants (une instruction FMA fusionnée compte pour 1) :

DW (K=2) : 17 flops (contre 29 pour la composition sans branchement mul+add).
TW (K=3) : 66 flops (contre 96).
QW (K=4) : 146 flops (contre 209).

Ces décomptes représentent les constructions minimales où chaque précondition de FastTwoSum est vérifiée par machine.

3.2 Bornes d'erreur vérifiées par machine

En utilisant FPANVerifier, les auteurs certifient les bornes d'erreur relatives à $(|xy| + |c|)$ pour toutes les précisions :

DW : $34 u^2 (|xy| + |c|)$
TW : $184 u^3 (|xy| + |c|)$
QW : $812 u^4 (|xy| + |c|)$
La validité de chaque précondition de FastTwoSum et l'accord bit à bit entre la variante prouvée et une variante naïve (où FastTwoSum est placé à la queue quel que soit la preuve) sont confirmés.

3.3 Commutativité

Les algorithmes proposés sont bitwise commutatifs en $x$ et $y$ pour les six types (DD/TD/QD/DS/TS/QS). Cela est réalisé en symétrisant l'ordre d'association des additions simples, garantissant $fma(x, y, c) \equiv fma(y, x, c)$ sans ajouter d'opérations.

3.4 Variantes spécialisées pour la division et la racine carrée

Le document identifie que les résidus intermédiaires dans les algorithmes de division et de racine carrée peuvent ne pas satisfaire les hypothèses de non-chevauchement requises pour les preuves FMA standards. Par conséquent, une variante « sûre » est proposée pour ces contextes (DW 20 / TW 69 / QW 149 flops), qui rétrograde les portes FastTwoSum non prouvées en TwoSum pour garantir la précision sans avoir à revérifier toute la structure pour chaque contexte d'utilisation.

4. Résultats expérimentaux

Les algorithmes ont été évalués sur deux plateformes :

Arm : NVIDIA GB10 (Grace-Blackwell, Cortex-X925 CPU, Blackwell GPU).
x86 : Nœud H100 (Intel Xeon Gold 6526Y CPU, H100 GPU).
Implémentations : Scalaire, AVX2, AVX-512, NEON, SVE2 et CUDA.

4.1 Noyaux d'algèbre linéaire (AXPY, GEMV, GEMM)

Accélération (Speedup) : Le FMA proposé surpasse systématiquement la référence sans branchement (BF) dans les scénarios limités par le calcul (compute-bound).
- AVX2 (x86) : Accélérations de $\times 1.49$ (DD), $\times 1.32$ (TD) et $\times 1.47$ (QD) dans GEMM.
- NEON (Arm) : Accélérations de $\times 1.40$ (DD), $\times 1.42$ (TD) et $\times 1.47$ (QD) dans GEMM.
- SVE2 : Performances similaires à NEON à largeur de voie égale, avec une GEMM QD atteignant une accélération de $\times 1.62$ par rapport à BF.
- GPU (GB10) : Sur les types de précision double limités par le calcul, les accélérations correspondent aux ratios théoriques de FLOPs ( $\times 1.71$ pour DD, $\times 1.46$ pour TD, $\times 1.40$ pour QD). Sur les charges de travail limitées par la bande passante (simple précision ou H100), les accélérations sont proches de $\times 1.00$ .
Précision : Le FMA proposé maintient une précision de travail comparable aux méthodes sans branchement existantes (Q/BF). Dans les scénarios d'annulation, le comportement de l'erreur est numériquement identique à la référence. L'Exact FMA offre une précision relative au résultat supérieure mais subit un ralentissement de 2,5 à 5,0 $\times$ .

4.2 Division et Racine Carrée

Division : Le FMA proposé accélère considérablement la division longue, particulièrement pour les hautes précisions.
- NEON/SVE2 : Accélérations de $\times 1.54$ à $\times 2.11$ (la division QD atteint $\times 2.11$ , dépassant le ratio de compte d'opérations de 1.51 grâce au repliement de deux chaînes de normalisation série en une seule).
- GB10 (Calcul uniquement) : Accélérations de $\times 1.25$ à $\times 1.61$ .
Racine Carrée : Le FMA proposé atteint des accélérations de $\times 1.51$ à $\times 1.61$ avec aucune perte de précision par rapport à la référence. Cela s'explique par le fait que l'itération de Newton converge bien en dessous de l'unité d'arrondi, rendant l'erreur finale dominée par la dernière multiplication commune à toutes les méthodes.

4.3 Base en simple précision (DS/TS/QS)

Les algorithmes ont été étendus avec succès aux composantes en simple précision, maintenant la précision de travail et atteignant des accélérations de $\times 1.37$ à $\times 1.83$ par rapport à la référence BF.

5. Signification et Revendications

Le document affirme que le FMA fusionné sans branchement proposé représente une construction minimale et vérifiée par machine qui parvient à fusionner les deux étapes des multiplications et additions sans branchement existantes en une seule opération.

Performance : Il fournit des accélérations réelles (jusqu'à $\times 2.11$ dans la division sur CPU et $\times 1.71$ dans GEMM sur GPU) en rédu\isant le nombre d'opérations et en raccourcissant les chaînes de dépendance, particulièrement bénéfique pour les hautes précisions (TW/QW).
Correction : Les algorithmes sont rigoureusement vérifiés. Les bornes d'erreur et les préconditions de FastTwoSum sont prouvées par machine pour toutes les précisions, et l'accord bit à bit entre la variante prouvée et une variante naïve (où FastTwoSum est placé à la fin quel que soit la preuve) est confirmé via des tests étendus (plus de 200 000 essais).
Généralité : L'approche n'est pas limitée à l'algèbre linéaire ; elle accélère efficacement les algorithmes de division et de racine carrée, qui reposent fortement sur les opérations MAC.
Commutativité : Contra à certaines approches antérieures sans branchement, le FMA proposé préserve la commutativité bit à bit, une propriété cruciale pour la reproductibilité dans les réductions parallèles.

Les auteurs positionnent ce travail comme un remplacement pratique de la composition d'opérations séparées sans branchement, offrant une accélération « drop-in » pour les bibliothèques d'arithmétique multi-composantes sans sacrifier la précision ou la prouvabilité. Des travaux futurs sont suggérés pour explorer des structures de renormalisation alternatives (par exemple, de type Priest) afin de potentiellement réduire davantage le nombre d'opérations tout en maintenant la vérifiabilité par machine.