Des processeurs ont-ils déjà implémenté une instruction de racine carrée entière ?

 (retrocomputing.stackexchange.com)
1 points par GN⁺ 2024-04-08 | 1 commentaires | Partager sur WhatsApp
  • La question ne porte pas sur la classique instruction sqrt en virgule flottante, mais sur l’existence de cas où une racine carrée entière était fournie comme instruction CPU ou fonctionnalité matérielle ; le divider/square-rooter de la Nintendo DS est similaire, mais ce n’est pas une instruction native
  • Le Forth CPU Harris RTX 2000 et sa version durcie militaire RTX 2010 sont cités comme des exemples proposant une instruction de racine carrée en plusieurs étapes ; sur le RTX 2000, on obtenait le résultat avec 1 instruction de préparation puis 15 instructions d’itération
  • Cas encore plus ancien, ENIAC disposait dès 1946 d’une unité divider/square-rooter pilotant des accumulateurs entiers décimaux, capable d’effectuer jusqu’à 40 divisions par seconde ou 3 opérations de racine carrée par seconde
  • La racine carrée entière exige un multiplicateur entier rapide et une précision suffisante, ce qui représentait une charge importante pour les CPU historiques ; il existe aussi des approches séparant estimation et itération, comme frsqrte/frsqrts sur ARMv8, pour ajuster le compromis précision/vitesse
  • La méthode de l’inverse square root popularisée par Quake n’offre plus en général d’avantage de performance sur le matériel moderne ; recherche dans une table, interpolation, itérations de type Halley ou divide and conquer en virgule fixe restent des options selon l’environnement d’implémentation

Portée de la question et cas de la Nintendo DS

  • La question porte sur l’existence de processeurs ayant réellement implémenté une instruction de racine carrée entière
  • Les instructions de racine carrée en virgule flottante sont courantes, mais le point de départ est que l’auteur de la question n’avait jamais vu d’instruction dédiée à la racine carrée entière
  • La Nintendo DS possédait un integer divider/square rooter mappé en mémoire
    • Cela aidait aux calculs 3D, les processeurs ARM n’ayant ni FPU ni diviseur matériel
    • Mais le fait important est que ce n’était pas une instruction processeur native

Harris RTX 2000 et RTX 2010

  • Le Forth CPU Harris RTX 2000 est mentionné comme un exemple fournissant une instruction de racine carrée en plusieurs étapes
  • Son équivalent durci militaire, le RTX 2010, proposait la même famille de fonctionnalités
  • Une ressource associée est Stack Computers: RTX 2000
  • D’après le RTX2000 Family Programmer’s Reference Manual, cette fonction ressemble davantage à une racine carrée itérative, avec 1 instruction de préparation suivie de 15 instructions d’itération pour obtenir la valeur finale
  • Le texte de Ken Lyons, “A Fast Method for Finding an Integer Square Root”, est aussi cité comme source décrivant l’implémentation matérielle et des exemples de programmation sur la famille RTX2000

L’unité divider/square-rooter de l’ENIAC

  • Dès 1946, l’ENIAC constitue lui aussi un cas de matériel de racine carrée entière
  • D’après la description citée, l’ENIAC pilotait 4 accumulateurs via une unité spéciale de multiplication pour effectuer jusqu’à 385 multiplications par seconde
  • 5 accumulateurs étaient pilotés par une unité spéciale de division/racine carrée, capable de traiter jusqu’à 40 divisions par seconde ou 3 racines carrées par seconde
  • Les accumulateurs de l’ENIAC fonctionnaient en entiers décimaux

Pourquoi la racine carrée entière est difficile à implémenter

  • Une réponse explique qu’une méthode efficace consiste à calculer d’abord l’inverse de la racine carrée par itérations de Newton-Raphson, puis à multiplier par la valeur d’origine
  • Cette approche est connue via la “méthode Quake”, et on en trouve aujourd’hui des formes généralisées dans CPU et GPU modernes avec une instruction d’estimation puis une instruction d’itération
  • La contrainte clé de cette approche est la nécessité d’un multiplicateur rapide
    • Pour une racine carrée en virgule flottante, il faut un multiplicateur flottant rapide, dont dispose une FPU
    • Pour une racine carrée entière, il faut un multiplicateur entier rapide, mais historiquement la plupart des CPU ne disposaient pas d’un tel matériel
    • Il est aussi précisé que, pour fournir une précision suffisante, il faut un multiplicateur rapide d’une largeur égale au double de celle de l’entrée
  • Comme le niveau de précision requis n’est pas toujours le même, séparer estimation et itération comme avec frsqrte et frsqrts permet d’ajuster le nombre d’itérations selon le compromis vitesse/précision recherché

Débat sur la technique de Quake et les implémentations modernes de sqrt

  • Une autre réponse conteste l’idée que l’astuce de Quake soit la plus efficace : ce n’est plus vrai depuis longtemps, sauf éventuellement pour produire un résultat flottant de faible qualité sur un matériel particulier
  • Sur les puces modernes, une instruction sqrt native est bien plus rapide, parfois en quelques cycles d’horloge seulement
  • Parmi les approches plus rapides proposées figure le stockage d’une table de valeurs à espacement non uniforme, la récupération rapide de deux valeurs puis leur interpolation, le décalage de l’exposant en base 2, puis si nécessaire une itération, potentiellement meilleure que Newton-Raphson
  • Les méthodes de type Halley et d’autres schémas itératifs peuvent converger plus vite que Newton-Raphson, mais la vitesse réelle dépend du coût de chaque opération
  • Pour un domaine strictement entier, par exemple 2^32, on peut appliquer les mêmes idées en virgule fixe
    • Une méthode matérielle simple de type divide and conquer est proposée
    • Chaque bloc de 8 bits est mappé sur une table de 256 valeurs en virgule fixe, consultée en parallèle ; puis, avec 3 multiplications dont 2 en parallèle, on peut obtenir une valeur sur 32 bits avant troncature
  • La recherche sur l’optimisation de sqrt continue, et un document INRIA HAL est cité comme exemple

À lire aussi

1 commentaires

 
GN⁺ 2024-04-08
Avis de Hacker News

  • AArch64 NEON dispose de l’instruction URSQRTE, ce qui est plus proche de la question initiale qu’on pourrait le croire
    Si l’on voit une valeur 32 bits comme un entier en virgule fixe avec 32 bits de partie fractionnaire, l’intervalle représenté va de 0 à 1-ε avec un pas uniforme, où ε=2^-32
    URSQRTE calcule une approximation de la racine carrée inverse, puis la divise par deux, et borne le résultat dans l’intervalle de 0 à 1-ε
    Un entier en virgule fixe n’est pas strictement un entier, et une racine carrée inverse approximative n’est pas une racine carrée, mais on arrive tout de même assez près
    L’instruction apparentée FRSQRTE est beaucoup plus générale et fournit une approximation de la racine carrée inverse pour les nombres à virgule flottante 32 bits

    • Je me demande quelle opération tire suffisamment parti d’une instruction aussi complexe pour qu’elle figure dans AArch64, alors qu’elle pourrait facilement être décomposée en instructions plus simples

  • Est-ce possible en un seul cycle d’horloge ? Oui, avec une très grande table de consultation
    On pourrait sans doute réduire sa taille selon la quantité de portes logiques en série que l’on peut faire passer dans un cycle d’horloge
    Par exemple, la racine carrée binaire de 10000 ressemble beaucoup à celle de 100, seule la quantité de zéros change

    • Les instructions d’estimation de racine carrée inverse en virgule flottante (frsqrte) sont généralement implémentées avec ce type de consultation de table, indexée par une partie des bits de la mantisse et par le bit de poids faible de l’exposant
      La précision est en gros comparable à celle du bf16 (ARM, RISC-V) ou du fp16 (x86) ; si l’on a besoin de davantage de précision, on effectue ensuite quelques itérations de Newton-Raphson
    • Pour une entrée de n bits, la racine carrée entière peut se calculer en n/2 itérations uniquement avec des décalages et des additions
      À chaque étape, on calcule s’il faut définir un nouveau bit dans le résultat n_old via n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2))
      On compare ensuite avec l’opérande d’origine et, si c’est inférieur ou égal, 1) on positionne le bit dans le résultat et 2) on met à jour n2_old avec n2_new
      Avec un jeu d’instructions microcodées et une ALU adaptés, c’est faisable en n/2, voire peut-être n cycles d’horloge, et avec plus d’optimisation on peut réduire n à l’indice du bit le plus à gauche positionné dans l’opérande
    • Question peut-être idiote, mais arrive-t-il vraiment qu’une grande consultation de table se termine en un seul cycle d’horloge ?
      Une grande table de consultation devrait être récupérée en mémoire, non ? Il y aurait alors de la latence due au cache et à la hiérarchie mémoire
    • Vu comme ça, on dirait que n’importe quel algorithme au monde pourrait s’exécuter en 1 cycle d’horloge
    • La racine carrée entière n’est pas si mauvaise : il suffit de stocker N^0.5 entrées dans une table de consultation plus grand/plus petit
      Cela revient à stocker N^2 pour chaque réponse N
      C’est réalisable pour des entiers 16 bits, peut-être pour 32 bits, mais pas pour 64 bits

  • Si l’on élargit la définition de « processeur » aux dispositifs électromécaniques, le Friden SRQ pouvait calculer des racines carrées uniquement avec additions et décalages, sans aucun composant électronique hormis le moteur
    Il fallait régler manuellement la position de la virgule décimale, donc techniquement on peut aussi parler d’opérations entières
    Vidéo : https://youtu.be/o44a1ao5h8w

  • Avec la suite 1 + 3 + 5 + ... + 2k + 1, ne peut-on pas obtenir la racine carrée entière de n’importe quel entier ?
    En gros, cela consiste à trouver le k du terme le plus proche de cette suite qui soit inférieur ou égal à mon nombre

    • Peux-tu expliquer l’idée ?
      Par définition, c’est bien un algorithme, mais implémenté naïvement il est très lent même pour des nombres 32 bits
      À ce niveau-là, autant faire une recherche binaire, ce sera bien plus rapide
    • Une meilleure méthode pourrait consister à combiner le développement (x+y)^2=x^2+2xy+y^2 avec l’observation que, dans n’importe quelle base, la racine carrée d’un nombre à 2n chiffres a au plus n chiffres
      C’est la même méthode courante que le calcul manuel de racine carrée au papier-crayon
      Si on traite les données par blocs de 8 bits, il suffit d’une table de consultation pour la racine carrée des nombres sur 8 bits
    • Si l’idée est de dérouler toute cette suite, cela prend un temps exponentiel par rapport à la longueur en bits de l’entrée
    • C’est l’un de ces cas typiques embarrassingly parallel, c’est-à-dire très faciles à paralléliser

  • Ce passage dans une réponse plus bas m’a fait rire :

    My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
    C’est un bon rappel : quand on écrit du code malin, il y a de fortes chances qu’on ne se souvienne plus plus tard de la façon dont il fonctionne

  • Il faut descendre un peu dans les réponses pour le lire, mais le fait que la réponse soit ENIAC est vraiment drôle

    • Beaucoup de gens pensent que tout ce qui date d’avant leur entrée à l’école était primitif et fonctionnait à peine :)
      Il suffit de lire un peu pour constater l’inverse
      La plupart des idées intelligentes d’aujourd’hui étaient déjà utilisées dans les ordinateurs des années 1940 à 1960, et sont réutilisées dans les nouvelles puces à semi-conducteurs
      C’est le cas du pipeline, de l’exécution dans le désordre ou du multicœur
      Le matériel ancien était peut-être un peu « rustique », mais son architecture employait des techniques très ingénieuses

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    Si l’on remplace Log2(x) par le comptage des zéros en tête, on obtient une approximation vraiment grossière
    En approximant mieux Log(2), on peut se rapprocher davantage de la réponse

  • Si l’on veut seulement une approximation très grossière et non la réponse exacte à l’entier le plus proche, il suffit de faire un décalage à droite de la moitié de la position du premier bit à 1
    Presque tous les processeurs ont une instruction de décalage, et les instructions du type FLO (Find Leading One) ou FFS (Find First Set) semblent si courantes que je ne sais même pas à quel point elles peuvent manquer
    Dans certains usages, une approximation aussi grossière peut être aussi utile qu’une réponse exacte
    Par exemple lorsqu’il suffit d’une bonne valeur initiale pour des itérations de Newton-Raphson ensuite
    Bien sûr, l’astuce du décalage à droite convient aussi comme valeur initiale pour un calcul plus précis de racine carrée :P

    • Est-ce ici qu’on parle de DOOM ?
      C’est désormais une histoire Internet assez célèbre, avec Carmack et un nombre magique sur 32 bits
    • Fait amusant : FFS et sa généralisation FNS existent dans CUDA : https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      Une autre fonction intrinsèque matérielle CUDA que j’aime bien personnellement est log2

  • Si ma mémoire est bonne, la plupart, voire tous les DSP en virgule fixe, ont une instruction de racine carrée ou une instruction auxiliaire

  • Une analyse exhaustive d’algorithmes de racine carrée, à moitié pertinente et susceptible d’intéresser les fans du 6502 : https://github.com/TobyLobster/sqrt_test