Le Pentium disposait d’un circuit dédié complexe pour multiplier par 3

 (righto.com)
3 points par GN⁺ 2025-03-04 | 1 commentaires | Partager sur WhatsApp
  • En 1993, l’Intel Pentium intégrait un circuit ×3 dédié produisant une valeur triplée afin d’accélérer les multiplications en virgule flottante, et ce petit circuit à lui seul utilisait plusieurs milliers de transistors
  • Le Pentium utilise la multiplication radix-8 pour réduire, dans une multiplication 64 bits, le nombre de termes à additionner de 64 à 22, mais cette méthode exige de produire rapidement le multiple ×3
  • Le calcul ×3 lui-même n’est qu’une addition x + 2x, mais comme le reste de la multiplication attend ce résultat, il faut des techniques d’addition rapide comme le carry lookahead et Kogge-Stone
  • Le circuit a une structure hiérarchique combinant huit blocs de 8 bits et un lookahead de niveau supérieur ; la sortie réelle est élargie à 69 bits pour gérer les dépassements et l’arrondi
  • Le fait qu’environ 9 000 transistors soient utilisés pour un seul circuit ×3 montre à quel point des optimisations matérielles complexes étaient mobilisées à l’époque du Pentium pour gagner en performance

Pourquoi le Pentium avait un circuit ×3 séparé

  • Le multiplicateur en virgule flottante du Pentium multiplie deux nombres de 64 bits selon une méthode radix-8
    • Une multiplication binaire classique ajoute 0 ou le multiplicande pour chaque bit ; une multiplication 64 bits nécessite donc 64 termes
    • La méthode radix-8 regroupe le multiplicateur par paquets de 3 bits et multiplie par une valeur de 0 à 7, ce qui réduit le nombre de termes à additionner à 22
  • Parmi les multiples de 0 à 7, certains sont relativement simples à produire en matériel
    • ×2 se traite par un décalage d’un bit vers la gauche
    • ×4 se traite par un décalage de deux bits vers la gauche
    • ×6 et ×7 peuvent être traités avec l’algorithme de multiplication de Booth, en combinant le +1 du chiffre radix-8 suivant avec une soustraction sur le chiffre courant
    • ×5 peut être obtenu en soustrayant ×3 à ×8
  • Au final, le multiple difficile est ×3, que le Pentium résout avec un circuit dédié à l’intérieur du multiplicateur en virgule flottante

Le point où une simple addition devient un goulot d’étranglement

  • La valeur triplée peut être produite en additionnant la valeur d’entrée avec cette même valeur décalée d’un bit vers la gauche
    • Structurellement, il s’agit simplement de l’addition x + 2x
  • Le goulot d’étranglement vient de la propagation de la retenue pendant l’addition
    • Dans un additionneur à retenue propagée, la retenue générée dans les bits de poids faible doit être transmise séquentiellement jusqu’aux bits de poids fort
    • Tant que le résultat ×3 n’est pas prêt, le reste du processus de multiplication ne peut pas commencer ; il faut donc réduire ce délai
  • Le Pentium utilise un carry-lookahead adder afin de calculer les retenues en parallèle plutôt que de les propager séquentiellement
    • Chaque bit produit des signaux carry generate et carry propagate
    • generate indique que la position concernée génère une retenue
    • propagate indique qu’une retenue entrante est transmise vers la sortie
    • Une fois les retenues calculées en parallèle, les bits de somme peuvent eux aussi être calculés en parallèle

Kogge-Stone et carry lookahead à deux niveaux

  • Si l’on implémente naïvement un carry lookahead direct, le coût en circuits et en câblage augmente fortement avec le nombre de bits
    • Plus la position du bit est élevée, plus la logique devient complexe
    • Les portes avec de nombreuses entrées sont plus lentes pour des raisons électriques
  • Le Pentium utilise un additionneur à préfixe parallèle Kogge-Stone par unités de 8 bits
    • Kogge-Stone fusionne les signaux propagate/generate par plages afin de calculer les retenues en parallèle
    • Il réutilise des résultats intermédiaires pour maîtriser le délai et la quantité de circuits
  • Plutôt que de traiter les 64 bits avec un seul Kogge-Stone, le circuit est divisé en une structure hiérarchique à deux niveaux
    • Le niveau inférieur comprend huit circuits Kogge-Stone de 8 bits qui calculent les retenues internes à chaque bloc
    • Le niveau supérieur considère chaque bloc de 8 bits comme une unité et calcule les retenues entre blocs
    • Les deux niveaux combinés fournissent rapidement les retenues nécessaires à la somme sur 64 bits
  • On peut voir le circuit comme prévu pour 64 bits, mais en pratique il produit une sortie de 69 bits incluant des bits supplémentaires pour éviter les dépassements et gérer l’arrondi

Réduire l’attente avec le carry-select

  • Chaque bloc de 8 bits contient un carry-select adder
    • Les deux sommes possibles, pour une retenue entrante de 0 et pour une retenue entrante de 1, sont calculées à l’avance
    • Lorsque le circuit de lookahead supérieur fournit la retenue entrante réelle, un multiplexeur sélectionne le bon résultat
  • Cette méthode consomme davantage de matériel, mais économise du temps
    • Elle nécessite deux additionneurs et un multiplexeur pour sélectionner le résultat
    • Elle superpose le calcul de la somme et le calcul des retenues, réduisant le délai global
  • Le bloc de 8 bits le plus bas n’a pas de retenue entrante et n’a donc pas besoin de circuit carry-select
    • Les bits de sortie de ce bloc sont calculés avec des portes XNOR

Ce qui se passe dans un bloc de 8 bits

  • Chaque bloc de 8 bits du circuit ×3 divise les lignes d’entrée entre l’additionneur de gauche et le chemin de droite
    • Cette structure de branchement additionne la valeur d’entrée et la valeur d’entrée décalée d’un bit vers la gauche pour implémenter ×3
  • La partie supérieure du bloc est constituée du circuit qui produit les signaux propagate/generate
    • Ces signaux entrent dans le circuit lookahead Kogge-Stone de 8 bits
    • La partie Kogge-Stone a une complexité différente selon les positions de bits, si bien qu’elle ne ressemble pas à un bloc répétitif mais plutôt à une structure irrégulière
  • La partie inférieure du bloc correspond à la zone du carry-select adder
    • Les deux sommes sont calculées à l’avance, puis un multiplexeur choisit selon la retenue entrante
    • Le bloc carry-select adder est disposé plus étroitement que les circuits environnants, afin de laisser de la place à une partie du circuit Kogge-Stone supérieur
  • Chaque bloc amplifie ses bits de sortie via un circuit driver avant de les envoyer au circuit multiplicateur suivant

Porte XNOR et implémentation au niveau des transistors

  • Dans la zone des bits de poids faible, les portes XNOR sont implémentées dans le Pentium sous forme de multiplexeurs
    • L’Intel 386 implémentait le XOR avec des portes AND-NOR, et le Z-80 utilisait des transistors de passage, mais l’approche du Pentium est différente
  • Ce circuit XNOR est composé de quatre inverseurs et d’un multiplexeur à transistors de passage
    • L’entrée B sélectionne l’entrée A ou A inversée parmi les deux entrées du multiplexeur
    • Le résultat produit la fonction XNOR
  • Dans l’analyse de la photo de la puce, les deux couches métalliques supérieures sont retirées afin d’observer la couche métallique inférieure M1 et les zones de silicium dopé
    • Le point où une ligne de polysilicium traverse le silicium dopé devient la grille d’un transistor
    • Le circuit CMOS est composé de transistors NMOS en haut et PMOS en bas

Drivers de sortie BiCMOS

  • La sortie du circuit ×3 nécessite un courant élevé
    • Chaque signal ×3 peut piloter jusqu’à 22 termes dans le multiplicateur en virgule flottante
    • Le circuit de destination peut être situé loin du circuit ×3
    • Les longs fils et les nombreuses grilles de transistors augmentent la capacité, et il faut un courant important pour commuter rapidement le signal
  • Le Pentium utilise un procédé BiCMOS combinant bipolar transistor et CMOS sur la même puce
    • Le Pentium utilise largement des circuits BiCMOS afin de réduire les délais de signal jusqu’à 35 %
    • Intel a également utilisé le BiCMOS dans les Pentium Pro, Pentium II, Pentium III et Xeon
    • À mesure que la tension des puces diminuait, les avantages du bipolar transistor se sont réduits, et le BiCMOS a fini par ne plus être utilisé
  • Le driver du circuit ×3 est structuré comme un driver BiCMOS qui pilote à son tour un second driver BiCMOS
    • Les grilles de transistors de l’inverseur à fort courant sont grandes, ce qui impose une étape intermédiaire pour les piloter
    • Amplifier un petit signal en plusieurs étapes permet de réduire le délai total
  • Les transistors NPN du driver BiCMOS ressemblent, contrairement aux transistors MOS ordinaires, à de grands rectangles
    • L’inverseur utilise une structure CMOS standard : PMOS pour tirer la sortie vers le haut et NMOS pour la tirer vers le bas
    • Certains inverseurs sont conçus avec des caractéristiques de courant asymétriques pour produire une sortie fortement high ou fortement low

La complexité croissante révélée par le matériel de multiplication

  • L’histoire du matériel de multiplication informatique remonte aux années 1950
  • Les premiers microprocesseurs avaient une prise en charge matérielle limitée de la multiplication
    • Les processeurs comme le 6502 n’avaient pas de matériel de multiplication, obligeant les utilisateurs à l’implémenter en logiciel avec des décalages et des additions
    • L’Intel 8086 exécutait une lente boucle shift-and-add en microcode
    • Le 386 incluait une multiply unit, mais une instruction de multiplication pouvait prendre jusqu’à 41 cycles d’horloge
  • À l’époque du Pentium, il était possible d’intégrer des millions de transistors, ce qui permettait des optimisations de performance plus complexes
    • La multiplication en virgule flottante du Pentium prend 3 cycles d’horloge, et le circuit de multiplication est utilisé pendant 2 de ces cycles
    • La multiplication entière MUL est bien plus lente, à 11 cycles
    • En 2008, la microarchitecture Nehalem a réduit le temps de multiplication en virgule flottante à 1 cycle
  • Le multiplicateur ×3 du Pentium contient environ 9 000 transistors
    • C’est un peu plus que l’ensemble du microprocesseur Z80 de 1976
    • Le circuit ×3 n’est qu’une petite partie du multiplicateur en virgule flottante situé dans l’unité de virgule flottante du Pentium

À lire aussi

1 commentaires

 
GN⁺ 2025-03-04
Avis Hacker News

  • C’est un peu hors sujet, mais il y a longtemps, en travaillant sur une émulation d’ordinateur ternaire, j’avais utilisé une petite astuce amusante pour trouver une transformation en forme fermée qui remplace une division par des puissances de 3 par une série de décalages de bits et d’additions
    Il suffit d’abord de voir que 1/3 - 1/2 = 2/6 - 3/6, donc que 1/3 = 1/2 - 1/2 (1/3)
    En réinjectant indéfiniment cette équation dans son membre de droite, on obtient une forme 1/3 = -(-1/2)^N, avec N dans l’intervalle 1..inf
    On peut faire quelque chose de similaire non seulement pour les paires de puissances de 2 et de 3, mais aussi dans d’autres bases
    Ce que cela signifie, c’est que pour des valeurs proches d’une puissance de 2, on peut assez facilement construire un circuit de division par constante en temps fixe avec seulement des additionneurs et des soustracteurs

    • Incroyable. Un ordinateur ternaire devait être fondé sur une logique à trois états ; est-il correct de comprendre que cela le rendait moins fiable que des transistors encodant des états binaires, voire que des tubes à vide ?

  • Le processeur des jeux d’arcade Cinematronics possède deux accumulateurs 12 bits
    L’instruction de multiplication les décale vers la droite comme s’ils formaient une seule valeur de 24 bits, et ajoute le contenu de la mémoire si un 1 sort du bit de poids faible
    Donc on effaçait la moitié haute, on chargeait une valeur dans la moitié basse, j’ai oublié comment l’adresse mémoire de l’autre opérande était configurée, puis on exécutait plusieurs multiplications d’un bit à la suite
    On pouvait ainsi obtenir un produit sur 24 bits, mais la plupart du code que j’ai vu enchaînait 8 multiplications, et l’usage le plus courant était la multiplication de matrices 2x2 pour faire tourner les coordonnées des objets du jeu
    C’était construit au milieu des années 1970 avec des composants 7400 du commerce, et le débit maximal était de 5 MIPS

    • Je ne crois pas qu’une multiplication prenait exactement un cycle. Dans ce cas, les 5 MIPS devaient être vite consommés
      Ces vingt dernières années, j’ai eu quelques occasions de devoir faire du calcul en virgule fixe, et mon respect pour les programmeurs des générations précédentes a augmenté

  • Pour compléter le passage où il est dit que vous avez peut-être entendu parler de techniques comme carry lookahead ou Kogge-Stone addition, le Kogge en question est Peter Kogge
    Il a fait son doctorat à Stanford, a travaillé sur la navette spatiale, est IBM Fellow et a inventé le premier CPU multicœur

    • Il a sans aucun doute accompli beaucoup de choses, mais on peut parfaitement rester exact sans dire qu’il a inventé le premier CPU multicœur, et le monde s’en porterait mieux sans ce genre de formulation
      Un « CPU multicœur » est, à strictement parler, davantage une idée qu’une invention. À un certain stade de l’histoire des semi-conducteurs, c’est même une idée assez évidente et triviale
      Faire fonctionner réellement un CPU multicœur n’a rien de trivial, mais ce n’est pas non plus une invention unique ; à ce moment-là, les équipes de développement étaient devenues si grandes qu’affirmer qu’une seule personne a résolu tous les problèmes à elle seule est plutôt insultant
      Kogge a peut-être dirigé le développement du premier CPU multicœur, et il a peut-être été un pionnier en poussant l’idée avant que d’autres ne la jugent possible, mais dans un cas comme dans l’autre il ne l’a pas inventé seul
    • Je pensais que l’équipe du premier CPU multicœur était dirigée par Kunle Olukotun
    • Autre ajout : Peter Kogge a écrit l’un des premiers manuels sur la microarchitecture pipeline, à lire si l’on veut comprendre comment étaient conçus les processeurs vectoriels des premiers supercalculateurs : The Architecture of Pipelined Computers (1981)
    • Peter a autrefois conseillé notre laboratoire et collaboré avec lui. Il défendait l’idée de rapprocher le calcul de télédétection des capteurs, ce qu’on appellerait aujourd’hui de l’edge computing
      Cette approche est intellectuellement tout à fait défendable. Elle est pertinente quand déplacer les données vers un calcul central entraîne de la latence ou des coûts, et dans notre cas, avec des capteurs spatiaux, on pouvait avancer cet argument
      Cela dit, à ma connaissance, ce mode de traitement n’a jamais été adopté de façon systématique dans les systèmes de traitement spatiaux, même si beaucoup de systèmes comme les radars effectuent une réduction provisoire des données sur du matériel proche du capteur
      Merci d’avoir indiqué ce lien

  • Je suis l’auteur. S’il y a des questions, j’y répondrai

    • Je me demande ce qu’est devenu le multiplieur par 3 dédié dans les machines ultérieures. Est-il resté sous une forme ou une autre, ou bien les tactiques ont-elles changé au point de le rendre inutile ?
    • Ken, il n’est pas temps de publier un livre ?
    • Question peut-être basique, mais est-ce destiné à la multiplication en virgule flottante ? Comme il faut aussi additionner les exposants, la partie réellement multipliée n’est-elle pas plus petite que 64 bits ?
    • Ma compréhension est floue, donc ignorez-moi si la question est trop bête, mais si « quand on sait calculer ×3, on peut le soustraire de ×8 pour obtenir ×5 », pourquoi ne peut-on pas soustraire x4 de x7 pour obtenir x3 ?

  • J’ai l’impression qu’il manque quelque chose
    Si ×2 est assez facile à calculer pour pouvoir utiliser 6x = 8x - 2x, et si ×4 est aussi facile à calculer comme 4x = 4x, je ne vois pas pourquoi calculer 3x comme la somme de 2x + 1x ou comme la différence de 4x - 1x serait plus difficile que cela
    Et si ×6 peut être calculé facilement d’une manière ou d’une autre, je me demande aussi pourquoi on ne pourrait pas décaler cette valeur vers la droite pour obtenir ×3. C’est une étape supplémentaire, mais cette étape est un décalage

    • Dans une multiplication 64 bits, on additionne 22 termes au total, un pour chaque chiffre octal. Pensez à la multiplication posée apprise à l’école primaire
      Chaque terme doit être trivial à calculer : pour obtenir un terme, on peut faire un décalage ou inverser le signe, mais pas effectuer une autre addition
      L’idée clé est que si l’on pré-calcule ×3 une fois, on peut ensuite simplement l’insérer dans n’importe lequel des 22 termes où il est nécessaire
      On ne peut pas mettre ×2 et ×1 dans un terme pour fabriquer ×3. Cela exigerait un autre additionneur pour chaque terme
      Autrement dit, ce que l’on veut, c’est un seul circuit qui calcule ×3, pas 22 circuits
      Pour la question sur ×6, cette valeur est calculée en mettant un ×2 négatif dans le terme et en ajoutant conceptuellement 1 au chiffre suivant pour obtenir ×8. Cette valeur ×8 fait partie d’un terme complètement différent, donc on ne peut pas la décaler vers la droite
      Il y a beaucoup de va-et-vient entre les nombres et les sommes, ce qui rend le tout complexe, mais vu comme ça, cela devrait avoir du sens

  • La multiplication par 3 est en réalité une opération courante, notamment dans le calcul d’adresses, où l’on multiplie souvent un index par 3 avec un décalage et une addition.
    Une implémentation naïve augmente pas mal la latence. Mais avec ce circuit, l’instruction LEA (Load Effective Address) peut être traitée en un cycle ; consacrer ce budget de transistors à cela était donc un choix tout à fait raisonnable.

    • Ce circuit sert-il vraiment à ça ? D’après ce que j’ai compris de l’article, ce circuit fait partie de la multiplication en virgule flottante.
    • Je ne vois pas ce que ça veut dire.
      LEA est simplement une instruction qui place l’adresse calculée par le mode d’adressage dans l’opérande de sortie, au lieu de déplacer les données depuis cette adresse ; et tous les calculs d’adresse que LEA peut faire, l’instruction MOV peut aussi les faire.
      En x86, le mode d’adressage indexé utilisé par MOV ou LEA ne prend pas en charge un facteur d’échelle de 3, seulement des puissances de 2 comme 1, 2, 4 et 8. Il n’y a donc pas d’usage pour une multiplication par 3 dans la génération d’adresses.
      L’article indique clairement que le multiplicateur par 3 fait partie du multiplicateur en virgule flottante.

  • « Ce multiplicateur ×3 contient environ 9 000 transistors, soit un peu plus que l’ensemble du microprocesseur Z80 (1976). Gardez à l’esprit que le multiplicateur ×3 n’est qu’une petite partie du multiplicateur en virgule flottante situé dans l’unité en virgule flottante du Pentium. Autrement dit, un petit morceau d’une fonctionnalité est plus complexe qu’un microprocesseur entier vieux de 17 ans, ce qui montre à quel point la complexité des processeurs a énormément augmenté. »
    C’est ce rythme de croissance des performances qui a engendré l’inflation logicielle actuelle. Les gains de performance de l’année suivante pouvaient en effet masquer la plupart des fautes dues au fait de ne pas réfléchir de façon critique aux algorithmes, au flux des données, au contexte et à la localité.
    Aujourd’hui, d’après ce que j’ai lu, nous avons atteint les limites pratiques de ce qu’il est raisonnablement possible de faire avec la technologie des semi-conducteurs au silicium et notre compréhension actuelle de la physique. Le balancier doit maintenant repartir dans l’autre sens : les ordinateurs doivent travailler non pas plus fort, mais plus intelligemment.

    • Les « limites pratiques de ce que permet notre compréhension actuelle de la physique » avaient déjà été atteintes il y a des décennies.
    • Le phénomène selon lequel l’inflation logicielle rattrape le rythme d’amélioration du matériel est connu sous le nom de loi de Wirth : https://en.wikipedia.org/wiki/Wirth%27s_law
      Cela dit, j’ai l’impression que l’inflation logicielle augmente encore plus vite.
    • À l’inverse, un multiplicateur a une structure bien plus régulière que celle d’un Z80. Le chemin de données du Pentium est aussi plusieurs fois plus large.
    • Histoire des appels de fonction : déplacement d’instructions avec goto/jmp → recherche dans une vtable → hachage et recherche dans un dictionnaire → exécution d’un grand modèle de langage.
    • Heureusement, la plupart des applications ont encore une grande marge d’amélioration.

  • « Au lieu de multiplier par 7, on ajoute 8 fois le nombre puis on soustrait le nombre pour obtenir 7 fois ce nombre. On pourrait croire qu’il faut deux étapes, mais grâce à une astuce consistant à multiplier par 1 de plus à la position de gauche, on obtient le coefficient 8 sans étape supplémentaire. »
    Est-ce que cela signifie qu’il y a un additionneur qui ajoute 1 à la « position suivante » avant d’envoyer le nombre dans la partie principale du multiplicateur ? Cela ressemble en soi à un circuit de prédiction de retenue.
    Je me demande aussi dans quels cas c’est nécessaire : 7 = 8-1, 6 = 8-2, 5 = 8-3, 4 = 8-4
    Pour le dernier cas, l’article ne dit pas qu’ils le font, mais déterminer s’il faut ajouter 1 à la position suivante à partir du bit de poids fort d’une valeur sur 3 bits semblerait permettre d’économiser quelques portes.

  • Le choix d’un multiplicateur de Booth en base 8, qui nécessite un circuit ×3, est intéressant. Cela ressemble à un compromis surface/performance pour pousser la fréquence maximale, et comme on aurait pu faire la même chose avec davantage de pipeline, il devait y avoir une contrainte sur le nombre de cycles de latence.

    • Oui, c’est un compromis. À l’époque, beaucoup d’autres unités en virgule flottante utilisaient la base 4, car cela permettait d’éviter le circuit ×3 supplémentaire.
      Le pipeline est délicat, car il n’y a pas vraiment de bon endroit pour couper en deux le réseau de multiplication.

  • https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
    8086 : 29 000
    386 : 275 000
    486 : 1,2 million
    Pentium : 3,1 millions
    D’après mes souvenirs, la NSA est entrée dans ce domaine à un moment donné après 2000.