L’astuce du radix 2^51 (2017)

• L’addition de grands entiers est généralement traitée en les découpant en limbs de 64 bits, mais dès qu’une propagation de retenue apparaît, il devient difficile d’exploiter pleinement les avantages d’exécution parallèle des CPU modernes
• Sur x86, adc dépend du carry flag de l’opération précédente, ce qui sérialise la chaîne d’instructions et devient donc un goulot d’étranglement, même sur des architectures comme Intel Haswell capables d’exécuter plusieurs add en parallèle
• La représentation en radix 2^51 découpe une valeur de 256 bits non pas en quatre chiffres de base 2^64, mais en cinq chiffres de base 2^51, afin d’utiliser les bits de poids fort restants de chaque limb comme espace de stockage intermédiaire pour les retenues
• Cette approche n’élimine pas les retenues : elle retarde leur propagation pendant plusieurs additions, puis les traite d’un seul coup lors de l’étape finale de normalisation
• Dans un benchmark simple sur Haswell, même en incluant le coût de conversion, la méthode radix 2^51 devenait plus rapide que l’approche radix 2^64 à partir de trois additions, et l’avantage augmentait encore avec le nombre d’itérations

---

Pourquoi les retenues deviennent un goulot d’étranglement dans l’addition de grands entiers

• L’addition posée sur papier se fait généralement de droite à gauche, à partir des unités
  • parce que le résultat de chaque chiffre dépend de la retenue transmise par le chiffre situé à droite
  • si l’on additionne en partant de la gauche, une retenue apparue plus tard oblige à corriger des chiffres déjà calculés
• L’addition de grands entiers subit la même contrainte
  • si l’on découpe les entiers 256 bits x et y en quatre limbs de 64 bits, on peut additionner les limbs de même rang
  • mais si un overflow se produit dans un limb de poids faible, il faut transmettre ce 1 au limb de rang supérieur
• Sur x86, adc est l’instruction qui gère cette propagation
  • elle vérifie s’il y a eu overflow à l’opération précédente et ajoute 1 si nécessaire
  • une addition 256 bits correcte enchaîne donc add, adc, adc, adc à partir du limb de poids faible

Pourquoi adc ralentit sur les CPU modernes

• adc coûte généralement plus cher à exécuter qu’un simple add
  • adc est plus complexe que add car il utilise une troisième entrée, le carry flag
  • comme adc est moins fréquent que add, les concepteurs de CPU ont moins d’incitation à consacrer de la surface de puce à son optimisation
• Le plus gros problème reste cependant la dépendance entre instructions
  • sur Intel Haswell, un add isolé prend 1 cycle à s’exécuter
  • dans des conditions idéales, Haswell peut exécuter jusqu’à 4 add par cycle
  • Haswell possède 8 ports d’exécution, dont 4 capables d’exécuter des add entiers
• Quatre add indépendants se parallélisent facilement
  • à l’inverse, une chaîne de adc fait dépendre chaque instruction de la sortie carry flag de la précédente
  • le CPU ne peut donc pas les paralléliser et doit les exécuter dans l’ordre
• La perte est encore plus importante en SIMD
  • vpaddq effectue quatre additions 64 bits simultanément
  • Haswell peut exécuter deux vpaddq par cycle
  • renoncer à ce parallélisme pour gérer les retenues réduit fortement le gain de performance

Retarder les retenues, vu comme une addition sur papier

• On peut retarder la retenue en conservant les poids décimaux, mais en élargissant l’ensemble des symboles autorisés dans chaque position
  • au lieu de 0-9, on utilise aussi A-Z et *, soit 37 symboles au total
  • mais la base n’est pas 37 : on conserve bien des positions de valeur décimale
• Un chiffre n’a alors plus besoin de produire immédiatement une retenue dès qu’il dépasse 9
  • 29 + 1 peut s’écrire 30, mais aussi 2A, 1K ou U
  • si les chiffres de départ de deux nombres sont tous normalisés et inférieurs ou égaux à 9, on peut retarder la retenue pendant l’addition
• Cela ne fonctionne pas toujours pour toutes les entrées
  • avec quelque chose comme 9 + W, une retenue devient nécessaire car un chiffre déjà élevé est présent
  • entre nombres normalisés, on peut toutefois additionner jusqu’à quatre valeurs sans retenue
• À la fin, il faut revenir à une écriture décimale ordinaire par normalisation
  • on calcule en partant de la droite combien de dizaines contient chaque position
  • on soustrait cette quantité de la position courante et on la transmet à la suivante
• L’idée essentielle n’est donc pas de supprimer la propagation des retenues, mais de la stocker pendant les calculs intermédiaires pour ne la propager qu’une seule fois à la fin

Représentation en radix 2^51 sur ordinateur

• Si l’on découpe une valeur 256 bits en quatre limbs de base 2^64, chaque limb peut prendre une valeur de 0 à 2^64−1
  • chaque limb est alors vu comme un chiffre en base 2^64
• Comme le matériel ne permet pas d’élargir la taille des entiers 64 bits, on réduit la taille de la base
  • au lieu de quatre chiffres en base 2^64, on découpe la valeur 256 bits en cinq chiffres en base 2^51
  • chaque limb est toujours stocké dans un entier 64 bits, mais n’utilise réellement que 51 ou 52 bits
• Les bits de poids fort restants servent d’espace de stockage pour les retenues intermédiaires
  • chaque limb contient 51 ou 52 bits du nombre d’origine
  • les 12 ou 13 bits restants stockent les retenues produites pendant les calculs
• Cette technique est appelée radix 2^51 representation dans la littérature cryptographique
• Pour des nombres normalisés, tant qu’on reste dans l’espace des 2^64 valeurs possibles d’un limb, on n’a pas à craindre de débordement des 13 bits de poids fort avant d’avoir additionné jusqu’à 2^13 valeurs

Limb de poids fort sur 52 bits et normalisation

• Le limb de poids fort reçoit 52 bits
  • les autres limbs utilisent 51 bits
  • la retenue du limb le plus haut est ignorée afin que les valeurs au-delà de 2^256−1 rebouclent
  • cela correspond au comportement habituel de l’addition d’entiers unsigned de taille fixe en C, qui wrappe en cas d’overflow
• Le code d’addition radix 2^51 exécute cinq add indépendants au lieu d’une chaîne de adc
  • par rapport à l’approche à quatre limbs en base 2^64, le nombre de add passe de 4 à 5
  • en contrepartie, il n’y a plus de dépendance au carry flag, donc l’exécution parallèle devient possible
• Lors de l’étape de normalisation, on extrait les bits de poids fort de chaque limb pour les ajouter au limb supérieur
  • shr 51 extrait la partie retenue
  • and 0x0007FFFFFFFFFFFF conserve uniquement les 51 bits de poids faible
  • le limb de poids fort est remis en forme avec and 0x000FFFFFFFFFFFFF
• La normalisation est l’étape qui effectue à la fin la propagation des retenues retardées
  • les additions intermédiaires ne créent pas de dépendance au carry flag
  • au final, chaque limb est ramené dans la plage autorisée

Résultats de performance et extension à la soustraction

• Dans un benchmark simple, l’addition radix 2^51 s’est montrée plus rapide sur un CPU Haswell
  • cela inclut le coût de conversion vers et depuis la représentation radix 2^51
  • à partir de trois additions, elle dépassait déjà l’addition radix 2^64
  • plus le nombre d’additions augmentait, plus l’économie réalisée devenait importante
• La même idée peut s’étendre à la soustraction
  • dans ce cas, la retenue devient une retenue négative
• Pour prendre en charge la soustraction, les limbs doivent être traités non plus comme des entiers unsigned mais comme des entiers signed
  • chaque chiffre peut alors prendre une valeur positive ou négative
  • chaque limb peut stocker à la fois une retenue positive et une retenue négative
• Cette modification a un coût
  • le bit de poids fort de chaque limb est réservé comme bit de signe
  • le nombre d’opérations possibles entre deux normalisations passe de 2^13 à 2^12
• Même si les données sont réparties sur davantage de registres et que le nombre d’opérations augmente, réduire la dépendance aux retenues peut malgré tout améliorer les performances globales

[GN⁺]

Avis de Hacker News

• Je me demande pourquoi on ne mettrait pas le limb de poids fort sur 64 bits, et les quatre autres limbs sur 48 bits chacun.
  On pourrait accumuler davantage d’additions avant normalisation, exploiter l’alignement des mots lors du découpage et de la normalisation si le jeu d’instructions dispose de fonctionnalités utiles, et les propriétés de débordement semblent identiques.

  • Si l’un des objectifs est de faire de l’arithmétique 256 bits avec 5 registres 64 bits, alors on utilise en gros 256/5 = 51,2 bits par mot, ce qui ressemble à une disposition assez idéale.
    Pour une bibliothèque généraliste de grands entiers, ce n’est peut-être pas optimal ; autrefois, faute de barrel shifter efficace pour les décalages arbitraires en bits, il aurait sans doute été préférable d’utiliser 56 bits sur 64 en laissant exactement 1 octet pour la retenue.
    Comme RISC-V n’a pas de flags, cette discussion est assez pertinente.
  • Si on additionne les limbs de poids fort de deux nombres encodés, on déborde beaucoup trop vite.
    Par exemple, s’ils valent tous les deux 2^63, on dépasse immédiatement ; cela peut convenir à une arithmétique avec wraparound, mais pas au cas général.
  • En faisant ainsi, il faut 6 mots, et non les 5 mots de la méthode de l’article, pour stocker une valeur 256 bits ; il faut donc aussi davantage d’instructions d’addition.

• Avec AVX512, et dans une certaine mesure AVX2, on peut implémenter assez efficacement une addition 256 bits, avec aussi l’avantage de mettre plus de nombres dans les registres.
  Cela revient à combiner _mm256_add_epi64, des masques de comparaison et des masques de retenue, et le débit semble meilleur : https://godbolt.org/z/e7zETe8xY
  Passer à une addition 512 bits est également simple, et l’amélioration devrait alors être plus importante.

  • En particulier, sur certaines architectures Intel, le simple fait d’utiliser un peu d’AVX512 peut faire baisser la fréquence de tout le processeur, ce qui peut au final rendre les performances irrégulières, voire plus lentes.
    https://stackoverflow.com/questions/56852812/simd-instructio...

• Sur des CPU x86 suffisamment récents, par exemple Intel Broadwell ou AMD Ryzen, on peut aussi utiliser ADX, et même dans des contextes comme Curve25519 où la représentation en radix 2^51 était traditionnellement avantageuse, cela peut aujourd’hui être plus rapide.
  [1] https://en.wikipedia.org/wiki/Intel_ADX

• Parmi les billets liés, on trouve d’anciens fils sur le radix 2^51 trick.
  The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - novembre 2022
  The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - mai 2020

• L’idée clé est que même s’il y a plus d’opérations, si elles sont globalement indépendantes, elles peuvent s’exécuter en parallèle et donc être plus rapides.
  À l’inverse, même avec moins d’opérations, si des dépendances de données imposent une exécution en série, cela peut être plus lent ; cette idée s’applique bien au-delà de l’arithmétique sur grands entiers.

  • Une autre approche consiste à utiliser des morceaux 64 bits classiques, mais à exécuter en parallèle, de façon spéculative, chaque addition avec et sans retenue, puis à choisir le bon résultat selon la retenue issue de l’addition des bits de poids faible.
    Le nombre d’additions double, mais le temps de propagation des retenues peut passer de linéaire à log(bits).
  • Ce que je n’avais pas bien compris, c’est que la technique montrée ici semble viser à faire en sorte que, lorsqu’on additionne N valeurs, le ripple carry ne se produise qu’une seule fois au lieu de N-1.
    L’opération de retenue est plus complexe, mais les additions proprement dites peuvent être parallélisées.
    Mais puisqu’il faut dès le départ découper les nombres d’entrée en groupes de 5 registres, il me semble que, pour que le gain soit global, ce découpage devrait lui aussi pouvoir être parallélisé.
  • Nvidia explore cette idée générale, et semble obtenir des résultats assez prometteurs dans plusieurs domaines.
  • Cette règle s’étend jusqu’aux supercalculateurs multinœuds et au cloud.
    Si l’on peut mobiliser 10 000 cœurs, le surcoût devient négligeable.

• Quelqu’un qui n’a travaillé qu’avec x86_64 montre très bien que RISC-V n’avait pas forcément tort d’omettre le carry flag.

  • On peut faire autrement tout en conservant des limbs 64 bits.
    L’observation clé est que, tant que la somme à une position de limb donnée n’est pas entièrement composée de 1, la retenue sortante à cette position ne dépend pas de la retenue entrante, mais seulement du fait que l’addition à cette position a produit une retenue.
    Si la somme est entièrement composée de 1, la retenue sortante est égale à la retenue entrante.
    En exprimant cela par des branchements conditionnels presque toujours prédits comme not-taken, et à condition que plusieurs branchements conditionnels puissent être prédits not-taken au même cycle d’horloge, chaque bloc d’instructions peut s’exécuter entièrement en parallèle.
    Une fois sur 2^64, l’exécution sera très lente.
    Sur une machine 4-wide avec des nombres à 4 limbs, cela n’apporte rien par rapport à adc, mais sur une machine 8-wide avec des nombres à 8 limbs, le gain commence à devenir important.
    Cela ne sert peut-être pas beaucoup sur le x86_64 actuel, mais il y a du potentiel sur les Apple M, puisque le M1 est aussi 8-wide, même si l’ISA Arm peut rendre le contournement délicat.
    Quand l’Ascalon RISC-V 8-wide de Tenstorrent sortira fin cette année ou début 2026, on pourra le vérifier concrètement, avec Ventana, Rivos, XiangShan et d’autres.
    Avec un décalage rapide sur 1 lane, cela fonctionne encore mieux en SIMD large ; dans RISC-V, cela s’appelle slideup.
  • La carry-save addition reste souvent pire que l’add-with-carry dans de nombreux cas courants.
    Les deux algorithmes d’addition multi-mots ne se remplacent pas l’un l’autre et ont des usages différents ; une bonne ISA inclut donc des instructions ADC/SBB, dont le coût additionnel est minime.
    Un registre de flags dédié n’est pas indispensable non plus : certaines ISA stockent les flags de retenue et d’emprunt dans des registres généraux quand c’est nécessaire.
    L’absence de retenue dans RISC-V n’est pas son pire défaut ; le pire est plutôt l’absence de flag de débordement entier.
    La détection des débordements entiers est indispensable dans les programmes qui se prétendent écrits de manière sûre ; la contourner en logiciel réduit les performances atteignables bien plus que contourner l’absence de retenue.
  • Cette situation découle au fond du fait que C a omis le carry flag, et en pratique il n’est presque plus utilisé pour les retenues.
  • Si le carry flag est de toute façon lent, je n’étais pas le seul à me demander : « c’était quoi, déjà, la controverse RISC-V GMP ? »

• Ce radix trick s’applique aussi aux structures de données.
  Le livre d’Okasaki, 『Purely Functional Data Structures』, en donne un bon exemple.

• J’aurais aimé lire cet article il y a quelques mois.
  En essayant d’encoder et décoder un tampon dans une base arbitraire, je suis arrivé beaucoup trop tard à la conclusion que les retenues pouvaient se propager jusqu’à la fin du tampon, ce qui ralentissait fortement l’algorithme.
  La solution finale avait elle aussi quelque chose de similaire à cette astuce : découper le tampon en chunks et laisser de l’espace libre pour gérer les retenues.
  Ce n’est pas exactement la même chose : on accepte quelques bits gaspillés, donc un tout petit peu plus de stockage ou de bande passante réseau, en échange de moins de calcul.
  Je me demande s’il serait possible de mettre ainsi les retenues en attente puis de les résoudre à une étape ultérieure pour avoir le meilleur des deux mondes, mais c’est peut-être un vœu pieux.

• Je sais que les règles de HN disent de ne pas modifier les titres, mais je n’aime pas les titres putaclic qui élargissent excessivement une petite affirmation.
  Le titre de cet article aurait dû être quelque chose comme : « L’astuce radix 2^51 pour additionner en parallèle des entiers 64 bits sur certaines architectures x86 sans ralentir le pipeline à cause des dépendances de retenue »