Gab es Prozessoren, die einen Integer-Quadratwurzelbefehl implementierten?

 (retrocomputing.stackexchange.com)
1 Punkte von GN⁺ 2024-04-08 | 1 Kommentare | Auf WhatsApp teilen
  • Der Streitpunkt ist nicht das übliche Gleitkomma-sqrt, sondern ob es Fälle gab, in denen Integer-Quadratwurzeln als CPU-Befehl oder Hardware-Funktion bereitgestellt wurden; der Divider/Square-Rooter des Nintendo DS ist ähnlich, aber kein nativer Befehl
  • Die RTX 2000 Forth CPU von Harris und die militärtaugliche RTX 2010 gelten als Beispiele, die mehrstufige Square-Root-Befehle bereitstellten; beim RTX 2000 wurde das Ergebnis mit einem Setup-Schritt und 15 Step-Schritten berechnet
  • Ein noch älteres Beispiel ist ENIAC, der 1946 mit einer Divider/Square-Rooter Unit Decimal-Integer-Accumulatoren steuerte und bis zu 40 Divisionen oder 3 Quadratwurzel-Operationen pro Sekunde ausführte
  • Integer-Quadratwurzeln erfordern einen schnellen Integer-Multiplizierer und ausreichende Präzision, was für historische CPUs eine große Belastung war; außerdem gibt es Ansätze wie frsqrte/frsqrts in ARMv8, die Schätzung und Iteration trennen, um Genauigkeit und Geschwindigkeit zu steuern
  • Die inverse Quadratwurzel im Quake-Stil hat auf moderner Hardware im Allgemeinen keinen Performance-Vorteil mehr; Tabellen-Lookups, Interpolation, Iterationen aus der Halley-Familie und Fixed-Point-Divide-and-Conquer sind je nach Implementierungsumgebung unterschiedliche Optionen

Umfang der Frage und der Nintendo-DS-Fall

  • Die Frage behandelt, ob es Prozessoren gab, die tatsächlich einen Integer-Quadratwurzelbefehl implementierten
  • Gleitkomma-Square-Root-Befehle sind verbreitet, aber die Ausgangslage ist, dass der Fragesteller noch keinen dedizierten Integer-Square-Root-Befehl gesehen hatte
  • Der Nintendo DS hatte einen speicherabgebildeten integer divider/square rooter
    • Da der ARM-Prozessor keine FPU und keinen Hardware-Divider hatte, half das bei 3D-Berechnungen
    • Der zentrale Hinweis der Frage ist jedoch, dass es sich nicht um einen nativen Prozessorbefehl handelte

Harris RTX 2000 und RTX 2010

  • Die RTX 2000 Forth CPU von Harris wird als Beispiel genannt, das mehrstufige Square-Root-Befehle bereitstellte
  • Auch der militärtaugliche Sibling RTX 2010 bot Funktionen aus derselben Familie
  • Als zugehöriges Material wird Stack Computers: RTX 2000 verlinkt
  • Laut RTX2000 Family Programmer’s Reference Manual ähnelt diese Funktion eher einer iterativen Square-Root-Berechnung: Man führt einen Setup-Befehl und 15 Step-Befehle aus, um den endgültigen Wert zu erhalten
  • Ken Lyons’ „A Fast Method for Finding an Integer Square Root“ wird ebenfalls als Material erwähnt, das die Hardware-Implementierung und Programmierbeispiele der RTX2000-Familie behandelt

ENIACs Divider/Square-Rooter Unit

  • Auch ENIAC von 1946 ist ein Beispiel für Integer-Quadratwurzel-Hardware
  • Der zitierten Beschreibung zufolge steuerte ENIAC vier Accumulatoren mit einer speziellen Multiplier Unit und führte damit bis zu 385 Multiplikationen pro Sekunde aus
  • Fünf Accumulatoren wurden von einer speziellen Divider/Square-Rooter Unit gesteuert und verarbeiteten bis zu 40 Divisionen oder 3 Quadratwurzel-Operationen pro Sekunde
  • Die Accumulatoren von ENIAC arbeiteten als Decimal Integer

Warum die Implementierung von Integer-Quadratwurzeln schwierig ist

  • Eine Antwort beschreibt als effiziente Methode zur Berechnung der Square Root, per Newton-Raphson-Iteration zunächst die inverse Quadratwurzel zu bestimmen und diese dann mit dem ursprünglichen Wert zu multiplizieren
  • Diese Methode ist als „Quake method“ bekannt und hat in modernen CPUs und GPUs allgemeinere Entsprechungen in Form von Initial-Estimate- und Iterationsbefehlen
  • Die wichtigste Einschränkung dieses Ansatzes ist, dass ein schneller Multiplier nötig ist
    • Für Gleitkomma-sqrt braucht man einen schnellen FP-Multiplier, und eine FPU besitzt diesen
    • Für Integer-sqrt braucht man einen schnellen Integer-Multiplier, doch historisch hatten die meisten CPUs eine solche Hardware nicht, so die Erklärung
    • Um ausreichende Präzision zu erreichen, kommt als Bedingung hinzu, dass ein schneller Multiplier mit der doppelten Breite der Eingabe nötig ist
  • Da die Anforderungen an die Präzision nicht immer gleich sind, kann man durch die Trennung von Schätzung und Iteration wie bei frsqrte und frsqrts die Anzahl der Iterationen an den gewünschten Kompromiss zwischen Geschwindigkeit und Genauigkeit anpassen

Die Quake-Methode und die Debatte um moderne sqrt-Implementierungen

  • Eine andere Antwort widerspricht der Behauptung, der Quake-Trick sei am effizientesten: Das stimme schon lange nicht mehr und gelte nur, wenn man auf bestimmter Hardware Float-Ergebnisse niedriger Qualität erhalten wolle
  • Auf modernen Chips sei ein nativer sqrt-Befehl deutlich schneller, oft im Bereich von wenigen Taktzyklen, so die Erklärung
  • Als schnellere Methode wird vorgeschlagen, eine Tabelle mit ungleichmäßig verteilten Werten zu speichern, zwei Werte schnell abzurufen und zu interpolieren, anschließend den Base-2-Exponenten zu shiften und bei Bedarf eine Iteration anzuwenden, die besser als Newton-Raphson ist
  • Verfahren aus der Halley-Familie und verschiedene Iterationsmethoden können schneller konvergieren als Newton-Raphson, die tatsächliche Geschwindigkeit hängt jedoch von den Kosten der jeweiligen Operationen ab
  • Für reine Integer-Bereiche, zum Beispiel 2^32, lässt sich dieselbe Idee mit Fixed Point anwenden
    • Als einfache Hardware-Methode wird Divide and Conquer genannt
    • Dabei können jeweils 8 Bit auf eine Tabelle mit 256 Fixed-Point-Werten abgebildet und parallel nachgeschlagen werden; anschließend werden von 3 Multiplikationen 2 parallel ausgeführt, um einen 32-Bit-Wert zu erhalten und ihn zu truncaten
  • Die Forschung zur Optimierung von sqrt geht weiter; als Beispiel wird ein INRIA-HAL-Material genannt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-04-08
Hacker-News-Kommentare

  • AArch64 NEON kommt der ursprünglichen Frage näher, als man denkt, denn es gibt dort die URSQRTE-Instruktion.
    Wenn man einen 32-Bit-Wert als Festkomma-Integer mit 32 Bits Nachkommanteil betrachtet, ist der Darstellungsbereich gleichmäßig von 0 bis 1-ε verteilt, wobei ε=2^-32 ist.
    URSQRTE berechnet eine näherungsweise inverse Quadratwurzel, teilt das Ergebnis anschließend durch zwei und clampen es auf den Bereich von 0 bis 1-ε.
    Ein Festkomma-Integer ist streng genommen kein Integer, und eine näherungsweise inverse Quadratwurzel ist auch keine Quadratwurzel, aber man kommt damit ziemlich nah heran.
    Die verwandte FRSQRTE ist eine deutlich allgemeinere Instruktion und liefert für 32-Bit-Gleitkommazahlen eine näherungsweise inverse Quadratwurzel.

    • Ich frage mich, welche Aufgabe so sehr davon profitiert, dass eine so komplexe Instruktion in AArch64 aufgenommen wurde, obwohl sie sich doch leicht in einfachere Instruktionen zerlegen ließe.

  • Ob es in einem einzigen Taktzyklus möglich ist? Mit einer sehr großen Lookup-Tabelle schon.
    Je nachdem, wie viele serielle Logikgatter innerhalb eines Taktzyklus durchlaufen werden können, ließe sich die Größe vermutlich reduzieren.
    Zum Beispiel ist die binäre Quadratwurzel von 10000 der Quadratwurzel von 100 ziemlich ähnlich; man kann sagen, dass sich nur die Anzahl der Nullen unterscheidet.

    • Gleitkomma-Instruktionen zur Schätzung der inversen Quadratwurzel (frsqrte) werden üblicherweise genau mit solchen Tabellen-Lookups implementiert, indiziert über einige Bits der Mantisse und das niederwertigste Bit des Exponenten.
      Die Genauigkeit liegt im Allgemeinen ungefähr auf dem Niveau von bf16 (ARM, RISC-V) oder fp16 (x86); braucht man mehr Präzision, führt man danach einige Newton-Raphson-Iterationen aus.
    • Bei einer Eingabelänge von n Bits kann die Integer-Quadratwurzel durch n/2 Iterationen nur mit Shifts und Additionen berechnet werden.
      In jedem Schritt wird berechnet, ob im Ergebnis n_old ein neues Bit gesetzt werden soll: n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2)).
      Danach vergleicht man mit dem ursprünglichen Operanden; wenn er größer oder gleich ist, 1) setzt man das Bit im Ergebnis und 2) aktualisiert n2_old auf n2_new.
      Mit einem passenden mikroprogrammierten Befehlssatz und einer ALU wäre das in n/2 oder vielleicht n Taktzyklen möglich; mit weiterer Optimierung ließe sich n auf den Index des höchstwertigen gesetzten Bits im Operanden reduzieren.
    • Vielleicht ist das eine dumme Frage, aber kommt es tatsächlich vor, dass ein großer Tabellen-Lookup in einem einzigen Taktzyklus fertig ist?
      Eine große Lookup-Tabelle müsste doch aus dem Speicher geholt werden; dann hätte man doch Latenzen durch Cache und Speicherhierarchie, oder?
    • So betrachtet klingt es, als ließe sich jeder Algorithmus der Welt in 1 Taktzyklus ausführen.
    • Integer-Quadratwurzel ist gar nicht so schlimm, wie man denkt: In der Größer/kleiner-Lookup-Tabelle müssen nur N^0.5 Einträge gespeichert werden.
      Man speichert also für jede Antwort N den Wert N^2.
      Für 16-Bit-Integer ist das machbar, für 32-Bit vielleicht auch, für 64-Bit aber nicht.

  • Wenn man die Definition von „Prozessor“ auf elektromechanische Geräte erweitert, konnte die Friden SRQ Quadratwurzeln nur mit Addition und Shifts berechnen, ganz ohne elektronische Bauteile außer dem Motor.
    Die Position des Dezimalpunkts musste manuell angepasst werden, technisch gesehen könnte man es also auch als Integer-Arithmetik bezeichnen.
    Video: https://youtu.be/o44a1ao5h8w

  • Kann man nicht mit der Folge 1 + 3 + 5 + ... + 2k + 1 die Integer-Quadratwurzel einer beliebigen ganzen Zahl bestimmen?
    Im Grunde sucht man dabei das k des nächstgelegenen Terms in dieser Folge, der kleiner oder gleich der eigenen Zahl ist.

    • Kannst du die Idee erklären?
      Per Definition ist das zwar ein Algorithmus, aber naiv implementiert ist er selbst für 32-Bit-Zahlen sehr langsam.
      An diesem Punkt wäre eine binäre Suche einfach deutlich schneller.
    • Eine bessere Methode könnte sein, die Entwicklung (x+y)^2=x^2+2xy+y^2 zusammen mit der Beobachtung zu nutzen, dass die Quadratwurzel einer 2n-stelligen Zahl in jeder Basis höchstens n Stellen hat.
      Das ist dieselbe übliche Methode, mit der man Quadratwurzeln per Hand mit Stift und Papier berechnet.
      Wenn man das in 8-Bit-Schritten verarbeitet, braucht man nur eine Lookup-Tabelle für die Quadratwurzel von 8-Bit-Zahlen.
    • Wenn damit gemeint ist, diese Folge einfach durchzuiterieren, dauert das exponentielle Zeit in Bezug auf die Eingabebitlänge.
    • Das ist eines der klassischen Probleme, die peinlich einfach zu parallelisieren sind.

  • Dieser Teil einer weiter unten stehenden Antwort hat mich zum Lachen gebracht:

    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.
    Eine gute Erinnerung daran, dass man sich bei cleverem Code später mit hoher Wahrscheinlichkeit nicht mehr daran erinnert, wie er funktioniert.

  • Man muss etwas weiter nach unten lesen, aber es ist wirklich witzig, dass die Antwort ENIAC lautet.

    • Viele Leute glauben, alles aus der Zeit vor ihrem Schuleintritt sei primitiv gewesen und habe gerade so funktioniert :)
      Schon ein wenig Lektüre zeigt genau das Gegenteil.
      Die meisten cleveren Ideen von heute wurden bereits in Computern der 1940er- bis 1960er-Jahre verwendet und werden in neuen Halbleiterchips wiederverwertet.
      Pipelining, Out-of-Order-Execution und Multi-Core gehören dazu.
      Alte Hardware war vielleicht etwas „grob“, aber in den Architekturen steckten sehr ausgeklügelte Techniken.

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    Wenn man Log2(x) durch Zählen führender Nullen ersetzt, erhält man eine wirklich grobe Näherung.
    Wenn man Log(2) besser approximiert, kann man näher an die Antwort kommen.

  • Wenn man keine exakte Antwort bis zur nächsten ganzen Zahl braucht, sondern nur eine sehr grobe Näherung, kann man einfach um die Hälfte der Position des führenden 1-Bits nach rechts shiften.
    Fast jeder Prozessor hat Shift-Instruktionen, und Instruktionen wie FLO (Find Leading One) oder FFS (Find First Set) scheinen so verbreitet zu sein, dass ich kaum weiß, wo es sie nicht gibt.
    Für manche Zwecke kann eine so grobe Näherung genauso nützlich sein wie die exakte Antwort.
    Zum Beispiel dann, wenn man anschließend nur einen brauchbaren Startwert für Newton-Raphson-Iterationen benötigt.
    Natürlich ist der Rechts-Shift-Trick auch als Anfangswert für eine genauere Quadratwurzelberechnung ganz okay :P

    • Kommt hier die DOOM-Geschichte ins Spiel?
      Inzwischen ist das eine ziemlich bekannte Internet-Geschichte, mit Carmack und einer magischen 32-Bit-Zahl.
    • Interessanter Fakt: FFS und die Verallgemeinerung FNS gibt es in CUDA: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      Eine weitere CUDA-Hardware-Intrinsic, die ich persönlich mag, ist log2.

  • Wenn ich mich richtig erinnere, haben die meisten, vielleicht sogar alle Festkomma-DSPs eine Quadratwurzel-Instruktion oder eine unterstützende Instruktion dafür.

  • Für 6502-Fans eine halbwegs verwandte und interessante vollständige Analyse von Quadratwurzel-Algorithmen: https://github.com/TobyLobster/sqrt_test