L’astuce du radix 2^51 (2017)

(chosenplaintext.ca)

1 points par GN⁺ 2025-05-31 | 1 commentaires | Partager sur WhatsApp

Dans les opérations sur grands entiers, le problème des retenues (carry) est l’une des principales raisons qui rendent la parallélisation difficile
Sur l’architecture x86, l’instruction adc destinée à gérer les retenues est plus lente que l’instruction add ordinaire, et une suite de retenues limite l’exécution en parallèle
En utilisant une représentation en radix 2^51, on peut retarder la propagation des retenues et effectuer plus d’additions rapidement
Chaque limb (valeur partielle) n’utilise que 51 ou 52 bits, et l’espace restant dans les bits de poids fort sert de stockage temporaire pour les retenues
Cette technique, malgré l’usage supplémentaire de registres et le coût des conversions, offre en pratique de meilleures performances qu’un radix 2^64

Additions et soustractions rapides : le problème des retenues

Dans l’addition de grands entiers, comme lorsqu’un humain gère les retenues chiffre par chiffre à la main, l’ordinateur a lui aussi du mal à paralléliser l’algorithme à cause des retenues
En principe, on additionne en partant de la droite (chiffres de poids faible), puis on reporte la retenue produite à chaque position vers la gauche (chiffres de poids fort)
Si l’on commence l’addition par la gauche, la retenue précédente influence l’opération suivante, ce qui empêche de paralléliser l’ordre des calculs

Gestion des retenues dans un ordinateur

Un ordinateur traite les additions par blocs d’entiers 64 bits
On pourrait penser qu’un entier 256 bits, découpé en 4 limbs de 64 bits, peut être additionné en parallèle, mais en pratique il faut gérer les débordements (overflow, ou retenues) pour obtenir le bon résultat
Sur x86, l’instruction adc (add with carry) prend automatiquement en charge la retenue

Origine de la baisse de performances

L’instruction adc nécessite une entrée supplémentaire, le carry flag, ce qui la rend moins performante qu’un simple add
Sur l’architecture Haswell, add peut s’exécuter en parallèle sur plusieurs ports, alors que adc impose pratiquement une exécution sérielle
En particulier avec les instructions SIMD (vpaddq, etc.), les additions parallèles sans retenue sont bien plus rapides

L’idée de retarder les retenues (exemple sur papier)

Pour réduire les retenues, on peut élargir la plage de chiffres (par exemple de 0-9 à 0-9, A-Z et *, soit 37 symboles au total) afin d’additionner temporairement plusieurs nombres sans retenue
On peut ainsi effectuer plusieurs additions sans propager les retenues, puis les normaliser en une seule fois à la fin
Ce concept sépare l’accumulation et la propagation des retenues afin de ne traiter les retenues qu’à l’étape finale
En pratique, lorsqu’une position dépasse la valeur de base, on applique ensuite la retenue accumulée en partant de la droite

Application au calcul sur ordinateur : l’astuce du radix 2^51

Pour réduire la propagation des retenues sur ordinateur, on utilise une représentation en radix 2^51
Au lieu de découper 256 bits en 4 limbs de 64 bits, on les répartit en 5 limbs de 51 à 52 bits
- Les 12 à 13 bits de poids fort de chaque limb servent de stockage temporaire pour les retenues
Avec cette méthode, chaque limb reste dans une plage de valeurs de 2^64, mais comme les retenues apparaissent beaucoup moins facilement pendant les calculs, plusieurs opérations peuvent être exécutées en parallèle sans retenue
Une normalisation n’est nécessaire qu’après environ 2^13 opérations consécutives
Sur un CPU Haswell, après adoption du radix 2^51, le simple enchaînement de plusieurs additions sans retenue apporte un gain de performances nettement supérieur à celui d’un radix 2^64 classique
La propagation des retenues pour la normalisation n’est effectuée qu’une seule fois à la fin

Exemple de code

En répartissant la valeur dans 5 registres, on peut effectuer des additions sans retenue
La normalisation consiste à extraire les bits de poids fort de chaque limb, à les ajouter au limb voisin, puis à remettre sa propre retenue à 0, en répétant ce processus

Extension à la soustraction

La même approche peut aussi être appliquée à la soustraction
Dans ce cas, la retenue peut être négative, on traite donc les limbs comme des entiers signés
Le bit le plus élevé de chaque limb devient alors un bit de signe, ce qui réduit légèrement, par rapport à l’addition, le nombre d’opérations pouvant être enchaînées d’un seul coup

Conclusion

La technique de résistance aux retenues (ou de retardement des retenues), malgré l’augmentation du nombre de limbs et le coût supplémentaire des conversions, améliore réellement et fortement les performances globales
L’astuce du radix 2^51 est largement utilisée dans les domaines exigeant de hautes performances, comme les grands calculs entiers ou la cryptographie
C’est une idée importante pour optimiser les performances réelles du matériel et des algorithmes

1 commentaires

GN⁺ 2025-05-31

Avis Hacker News

En voyant le nombre 2^51, j’ai d’abord cru qu’il s’agissait du stockage d’entiers dans un type double, avant de réaliser que la plus grande valeur entière représentable exactement dans un double est en fait 2^53-1
AVX512 (et dans une certaine mesure AVX2 aussi) fournit un environnement permettant d’implémenter des additions 256 bits de façon assez efficace, avec l’avantage de pouvoir mettre davantage de nombres dans les registres
Un exemple direct fonctionne comme dans le code ci-dessous

__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g << 1) + p) ^ p;

__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);

On voit même une amélioration du throughput, et on peut consulter un exemple de code réel sur godbolt.org
Étendre cette logique jusqu’à l’addition 512 bits est également très simple

On souligne notamment que sur certaines architectures de CPU Intel, le simple fait d’utiliser des instructions AVX512 peut faire baisser la fréquence globale du processeur, ce qui peut conduire à des performances globales irrégulières, voire plus faibles
Voir aussi ce point de référence sur Stack Overflow
À la question « pourquoi ne pas utiliser 12 bits au lieu de 13 ? », ici on ignore la gestion de la retenue sur le bit de poids fort (limb), de sorte que cela se comporte en cas d’overflow comme un wraparound
Le résultat est qu’on alloue 52 bits au limb de poids fort, avec l’inconvénient qu’il manque d’espace plus vite que les autres limbs, mais cela fonctionne un peu comme l’addition d’entiers non signés en C
On propose alors une autre approche : 64 bits pour le limb le plus significatif et 48 bits pour chacun des quatre autres limbs
Cela permettrait d’accumuler davantage d’opérations avant normalisation, tout en apportant des avantages comme l’alignement sur mot
Le comportement face à l’overflow resterait le même
- Si l’on alloue 64 bits uniquement au limb de poids fort, l’addition des limbs de deux nombres provoque un overflow beaucoup trop vite
  Par exemple, si les deux valent 2^63, on déborde immédiatement
  En arithmétique wraparound ce n’est pas un problème, mais dans le cas général ce n’est pas acceptable
- Avec une telle structure, il faudrait 6 mots au lieu de 5 comme dans le post original
  Il faudrait aussi davantage d’instructions
- L’objectif est de faire des maths sur 256 bits avec 5 registres de 64 bits
  Autrement dit, la répartition idéale est de 256/5 = 51,2 bits par mot
  C’est très bien si l’on se limite à 256 bits, mais ce n’est pas optimal pour une bibliothèque big-int générique
  Autrefois, on cherchait aussi à faire tenir exactement une retenue dans 1 octet, et à l’époque où les barrel shifters n’existaient pas, on préférait n’utiliser que 56 bits sur 64 pour faciliter l’alignement
  Sur RISC-V, comme il n’y a pas de flags matériels, cette discussion devient encore plus importante
Sur les CPU x86 modernes (par ex. Intel Broadwell, AMD Ryzen), les instructions Intel ADX peuvent être plus rapides, même dans des cas où la représentation en radix 2^51 dominait traditionnellement (par ex. Curve25519)
Ressources de discussion associées
- The radix 2^51 trick (novembre 2022)
- The radix 2^51 trick (2017)
La leçon essentielle est que lorsque les opérations sont indépendantes les unes des autres, en exécuter davantage en parallèle peut en réalité être plus rapide
À l’inverse, si des dépendances imposent une exécution séquentielle, on peut être plus lent même avec moins d’opérations
Cette idée s’applique non seulement aux calculs sur grands entiers, mais aussi à bien d’autres domaines
- Il est proposé de découper en chunks de 64 bits et de pré-exécuter en parallèle les deux cas possibles selon qu’il y ait ou non une retenue, puis de choisir ensuite le bon résultat selon la retenue réelle
  Cette méthode double le nombre d’additions, mais accélère la propagation à une vitesse en log(bits) plutôt que linéaire
- Ce que je n’avais pas bien compris dans cette technique, c’est qu’elle revient essentiellement à faire en sorte que le ripple carry, qui s’exécuterait N-1 fois lors de l’addition de N valeurs, ne s’exécute qu’une seule fois
  La gestion des retenues devient plus complexe, mais les additions, elles, peuvent être parallélisées
  Cela dit, pour que le gain global soit réel, il faut aussi paralléliser le découpage des nombres d’entrée en blocs de 5 registres
- Cette règle peut s’étendre jusqu’au niveau des supercalculateurs ou du cloud avec des dizaines de milliers de nœuds
  Si l’on dispose de beaucoup de cœurs, l’overhead devient négligeable
- Cette idée intéresse aussi NVidia et donne de bons résultats dans plusieurs domaines
Il existe une règle HN selon laquelle il ne faut pas ajouter d’opinion dans le titre, mais je n’aime pas non plus les titres exagérément racoleurs
À mon avis, quelque chose comme « astuce radix 2^51 pour une addition parallèle d’entiers 64 bits sans dépendance à la retenue sur certaines architectures x86 » serait plus précis
Je regrette de ne pas avoir lu cet article quelques mois plus tôt, cela m’aurait aidé
En encodant et décodant un buffer dans une base arbitraire, j’ai constaté que la propagation de la retenue à travers tout le buffer ralentissait énormément l’algorithme
Au final, j’ai laissé du "mou" et traité cela par chunks pour gérer les retenues, ce qui semble assez proche de cette astuce
En pratique, j’ai choisi de sacrifier quelques bits pour économiser du calcul ou de la bande passante réseau
Je me demande s’il serait possible de regrouper aussi ce type de gestion des retenues en post-traitement
Ce serait idéal d’obtenir pratiquement tous les avantages à la fois
Mon expérience limitée à l’environnement x86_64 montre bien que l’absence de carry flag sur RISC-V n’est pas nécessairement une mauvaise approche
- En plus de cette méthode, on décrit aussi une manière de conserver des limbs sur 64 bits tout en effectuant des additions safe vis-à-vis des retenues avec uniquement des variables uint64_t
  Le flux ressemble à ceci
```
s0 += a0;
s1 += a1;
s2 += a2;
s3 += a3;
c0 = s0 < a0; // RISC-V sltu
c1 = s1 < a1;
c2 = s2 < a2;
if (s1 == -1) goto propagate0;
check_s2:
if (s2 == -1) goto propagate1;
add_carries:
s1 += c0;
s2 += c1;
s3 += c2;
goto done;
propagate0: c1 = c0; goto check_s2;
propagate1: c2 = c1; goto add_carries;
done:
```
Le point clé est que, tant que le résultat de l’addition (le limb) n’est pas entièrement à 1, la retenue en sortie de ce limb ne dépend pas de la retenue en entrée, mais uniquement du résultat de l’addition des valeurs d’origine
En revanche, si la valeur est entièrement à 1, alors retenue_sortie = retenue_entrée
Avec une structure de branches demandant très peu de prédiction, l’exécution peut être entièrement parallèle
En probabilité, cela ne ralentit qu’un cas sur 2^64, mais sur une machine 4-wide il n’y a pas de gros gain
Sur une machine 8-wide ou avec une structure à 8 limbs, l’amélioration peut devenir significative
Ce n’est pas adapté à x86_64, mais cela pourrait être pertinent sur des machines 8-wide comme les séries Apple M*
On peut espérer de bons résultats futurs sur le processeur RISC-V Ascalon 8-wide de Tenstorrent, ainsi que chez Ventana, Rivos, XiangShan, etc.
L’effet est maximal sur des architectures SIMD ou disposant d’instructions rapides de shift/slideup sur 1 lane
- L’addition carry-save n’est pas toujours supérieure à l’add-with-carry
  Ces deux familles d’algorithmes d’addition multi-mots ne sont pas interchangeables et ont chacune leurs avantages et inconvénients
  C’est pourquoi les instructions ADC/SBB doivent faire partie de base de l’ISA, avec éventuellement un stockage des flags en registres
  Sur RISC-V, un défaut plus grave encore est l’absence d’un overflow flag pour les entiers
  Lorsqu’un contournement logiciel est nécessaire pour détecter un overflow, la perte de performance est bien plus importante qu’avec un contournement pour le bit de retenue
- L’absence de carry flag sur RISC-V découle du fait que le langage C a ignoré le carry flag binaire
  En pratique, l’usage du carry flag reste assez rare
- Je ne suis donc pas le seul à m’être demandé : « si le carry flag est de toute façon lent, pourquoi y a-t-il eu la controverse risc5 gmp ? »
Le « radix trick » peut aussi s’appliquer aux structures de données
On trouve un exemple intéressant dans le livre Purely Functional Data Structures d’Okasaki