Der Trick mit Radix 2^51 (2017)

 (chosenplaintext.ca)
1 Punkte von GN⁺ 2025-05-31 | 1 Kommentare | Auf WhatsApp teilen
  • Addition großer Ganzzahlen wird normalerweise verarbeitet, indem man sie in 64-Bit-Limbs zerlegt; wenn jedoch eine Carry-Propagation entsteht, lassen sich die Vorteile moderner CPUs bei der parallelen Ausführung nur schwer richtig nutzen
  • adc auf x86 hängt vom Carry Flag der vorherigen Operation ab und serialisiert dadurch die Befehlskette; selbst auf Architekturen wie Intel Haswell, die mehrere add parallel ausführen können, wird das zum Engpass
  • Die Radix-2^51-Darstellung teilt einen 256-Bit-Wert nicht in vier Stellen zur Basis 2^64, sondern in fünf Stellen zur Basis 2^51 auf und nutzt die freien oberen Bits jedes Limbs als Zwischenspeicher für Carries
  • Carries werden dabei nicht eliminiert; ihre Propagation wird über mehrere Additionen hinweg verzögert und erst in einem abschließenden Normalisierungsschritt gesammelt verarbeitet
  • In einem einfachen Benchmark auf Haswell war das Verfahren ab drei Additionen schneller als Radix 2^64, selbst inklusive der Kosten für die Umwandlung; mit steigender Wiederholungszahl wurde der Vorteil größer

Warum Carries bei der Addition großer Ganzzahlen zum Engpass werden

  • Schriftliche Addition auf Papier läuft von rechts nach links, beginnend bei der Einerstelle
    • Das Ergebnis jeder Stelle hängt vom Carry ab, der von der rechten Stelle herüberkommt
    • Addiert man von links, müsste man wegen später entstehender Carries bereits berechnete vordere Stellen nachträglich korrigieren
  • Die Addition großer Ganzzahlen unterliegt derselben Einschränkung
    • Zerlegt man die 256-Bit-Ganzzahlen x und y in vier 64-Bit-Limbs, kann man Limbs an derselben Position addieren
    • Wenn bei einem niedrigeren Limb ein Overflow entsteht, muss diese 1 an das höhere Limb weitergegeben werden
  • adc auf x86 ist der Befehl, der diese Propagation behandelt
    • Er prüft, ob die vorherige Operation übergelaufen ist, und addiert bei Bedarf 1
    • Eine korrekte 256-Bit-Addition läuft vom niederwertigsten Limb aus in der Reihenfolge add, adc, adc, adc

Warum adc auf modernen CPUs strukturell langsamer wird

  • adc hat im Allgemeinen höhere Ausführungskosten als ein normales add
    • adc nutzt mit dem Carry Flag eine dritte Eingabe und ist daher komplexer als add
    • Weil adc seltener verwendet wird als add, haben CPU-Designer weniger Anreiz, Chipfläche in die Optimierung der adc-Performance zu investieren
  • Das größere Problem sind Befehlsabhängigkeiten
    • Auf Intel Haswell benötigt ein einzelnes add 1 Zyklus zur Ausführung
    • Unter idealen Bedingungen kann Haswell bis zu 4 add pro Zyklus ausführen
    • Haswell hat 8 Execution Ports, von denen 4 Integer-add ausführen können
  • Vier unabhängige add lassen sich leicht parallel ausführen
    • Eine adc-Kette dagegen hängt bei jedem Befehl vom Carry-Flag-Ausgang des vorherigen Befehls ab
    • Die CPU kann diese Befehle nicht parallelisieren und muss sie der Reihe nach ausführen
  • Bei SIMD ist der Verlust noch größer
    • vpaddq führt vier 64-Bit-Additionen gleichzeitig aus
    • Haswell kann zwei vpaddq pro Zyklus ausführen
    • Gibt man diese Parallelität zur Carry-Verarbeitung auf, schrumpft der Performance-Vorteil

Verzögerte Carries anhand der schriftlichen Addition

  • Wenn man den dezimalen Stellenwert beibehält, aber die Zeichenmenge erweitert, die in eine Stelle passen darf, kann man Carries verzögern
    • Statt der üblichen 0-9 verwendet man zusätzlich A-Z und *, also insgesamt 37 Zeichen
    • Die Basis selbst ist dabei jedoch nicht 37; die dezimalen Stellenwerte bleiben erhalten
  • Überschreitet eine Stelle 9, muss man nicht sofort einen Carry ausführen
    • 29 + 1 kann man als 30 schreiben, aber auch als 2A, 1K oder U
    • Wenn alle Stellen zweier Zahlen auf höchstens 9 normalisiert sind, lässt sich der Carry während der Addition aufschieben
  • Das gilt nicht immer für alle Eingaben
    • Wenn wie bei 9 + W bereits ein großer Stellenwert vorhanden ist, wird ein Carry nötig
    • Bei normalisierten Zahlen lassen sich bis zu vier davon addieren, ohne einen Carry darstellen zu müssen
  • Am Ende muss wieder in die gewöhnliche Dezimaldarstellung normalisiert werden
    • Von rechts beginnend berechnet man für jede Stelle, wie viele 10er darin enthalten sind
    • Diese Menge zieht man von der aktuellen Stelle ab und überträgt sie auf die nächste Stelle
  • Der Kern ist nicht, die Carry-Propagation zu beseitigen, sondern sie während der Zwischenrechnungen zu speichern und am Ende einmal zu propagieren

Radix-2^51-Darstellung auf dem Computer

  • Teilt man einen 256-Bit-Wert in vier 2^64-Limbs auf, kann jeder Limb Werte von 0 bis 2^64−1 annehmen
    • Man betrachtet jeden Limb als Stelle zur Basis 2^64
  • Da sich der 64-Bit-Integerbereich der Hardware nicht erweitern lässt, verkleinert man die Basis
    • Statt vier Stellen zur Basis 2^64 teilt man einen 256-Bit-Wert in fünf Stellen zur Basis 2^51 auf
    • Jeder Limb wird weiterhin als 64-Bit-Integer gespeichert, nutzt tatsächlich aber nur 51 oder 52 Bit
  • Die freien oberen Bits werden zum Zwischenspeicher für Carries
    • Jeder Limb enthält 51 oder 52 Bit der ursprünglichen Zahl
    • Die übrigen 12 oder 13 Bit nehmen Carries auf, die während der Berechnung entstehen
  • In der kryptografischen Literatur heißt diese Technik radix 2^51 representation
  • Bei normalisierten Zahlen muss man innerhalb der 2^64 möglichen Limb-Werte keine Overflow der oberen 13 Bit befürchten, bevor man bis zu 2^13 Werte addiert hat

Oberstes 52-Bit-Limb und Normalisierung

  • Dem obersten Limb werden 52 Bit zugewiesen
    • Die übrigen Limbs verwenden 51 Bit
    • Ein Carry aus dem obersten Limb wird ignoriert, sodass Werte über 2^256−1 herumgewickelt werden
    • Das entspricht der Art, wie C bei der Addition unsigned Integer normaler Größe bei Overflow wrappt
  • Radix-2^51-Additionscode verwendet keine adc-Kette, sondern führt fünf add unabhängig voneinander aus
    • Gegenüber dem Ansatz mit vier 2^64-Limbs steigt die Zahl der add von 4 auf 5
    • Dafür gibt es keine Abhängigkeit vom Carry Flag, sodass parallele Ausführung möglich ist
  • In der Normalisierungsphase werden die oberen Bits jedes Limbs herausgenommen und dem nächsthöheren Limb hinzuaddiert
    • Mit shr 51 wird der Carry-Anteil extrahiert
    • Mit and 0x0007FFFFFFFFFFFF bleiben nur die unteren 51 Bit erhalten
    • Das oberste Limb wird mit and 0x000FFFFFFFFFFFFF bereinigt
  • Die Normalisierung ist der Schritt, in dem die verzögerte Carry-Propagation am Ende durchgeführt wird
    • Während der Zwischenadditionen wird keine Carry-Flag-Abhängigkeit erzeugt
    • Am Schluss wird jedes Limb wieder in den zulässigen Bereich gebracht

Performance-Ergebnisse und Erweiterung auf Subtraktion

  • In einem einfachen Benchmark zeigte Radix-2^51-Addition auf einer Haswell-CPU bessere Ergebnisse
    • Einschließlich der Kosten für die Umwandlung in die Radix-2^51-Darstellung und zurück
    • Schon bei drei Additionen war sie schneller als Radix-2^64-Addition
    • Mit zunehmender Zahl der Additionen wuchs auch die Einsparung
  • Dieselbe Idee lässt sich auch auf Subtraktion erweitern
    • Bei der Subtraktion wird der Carry zu einem negativen Carry
  • Um Subtraktion zu unterstützen, behandelt man Limbs nicht als unsigned, sondern wie signed Integer
    • Jeder Stellenwert kann positiv oder negativ sein
    • Jedes Limb kann sowohl positive als auch negative Carries speichern
  • Diese Änderung hat Kosten
    • Das oberste Bit jedes Limbs wird als Vorzeichenbit reserviert
    • Die Zahl der Operationen, die zwischen Normalisierungen möglich sind, sinkt von 2^13 auf 2^12
  • Auch wenn die Daten auf mehr Register verteilt werden und die Zahl der Operationen steigt, kann die Gesamtperformance besser werden, wenn man Carry-Abhängigkeiten reduziert

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-05-31
Hacker-News-Kommentare

  • Ich frage mich, ob man nicht das höchstwertige Limb mit 64 Bit und die übrigen vier Limbs mit jeweils 48 Bit verwenden könnte.
    Vor der Normalisierung ließen sich mehr Additionen akkumulieren, und wenn der Befehlssatz nützliche Funktionen dafür bietet, könnte man bei Aufteilung und Normalisierung auch die Wortausrichtung nutzen; auch das Overflow-Verhalten scheint gleich zu sein.

    • Wenn eines der Ziele darin besteht, 256-Bit-Operationen mit fünf 64-Bit-Registern auszuführen, nutzt man pro Wort 256/5 = 51,2 Bit; das wirkt also wie eine einigermaßen ideale Aufteilung.
      Für eine allgemeine Big-Integer-Bibliothek ist es möglicherweise nicht optimal, und früher gab es keine Barrel Shifter, die beliebige Bit-Shifts effizient ausführen konnten; daher war es wohl sinnvoll, genau 1 Byte für den Carry freizulassen und 56 von 64 Bit zu nutzen.
      Da RISC-V keine Flags hat, ist diese Diskussion ziemlich relevant.
    • Wenn man die höchstwertigen Limbs zweier codierter Zahlen addiert, läuft man viel zu schnell in einen Overflow.
      Wenn beide zum Beispiel 2^63 sind, läuft es sofort über; für Wrapping-Arithmetik könnte das okay sein, aber für den allgemeinen Fall passt es nicht.
    • Dann bräuchte man zum Speichern eines 256-Bit-Werts 6 Wörter statt der 5 Wörter der im Original beschriebenen Methode, und damit auch mehr Additionsbefehle.

  • Mit AVX512, und bis zu einem gewissen Grad auch mit AVX2, lässt sich 256-Bit-Addition ziemlich effizient implementieren; außerdem bekommt man mehr Zahlen in die Register.
    Man kombiniert etwa _mm256_add_epi64, Vergleichsmasken und Carry-Masken; auch der Durchsatz sieht besser aus: https://godbolt.org/z/e7zETe8xY
    Der Wechsel zu 512-Bit-Addition ist ebenfalls einfach, und dann dürfte die Verbesserung noch größer ausfallen.

  • Auf hinreichend modernen x86-CPUs, etwa Intel Broadwell oder AMD Ryzen, kann man auch ADX verwenden; selbst in Fällen wie Curve25519, wo die Darstellung mit radix 2^51 traditionell vorteilhaft war, kann das heute schneller sein.
    [1] https://en.wikipedia.org/wiki/Intel_ADX

  • Als verwandte Beiträge gibt es ältere Threads zum radix-2^51-Trick.
    The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - November 2022
    The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - Mai 2020

  • Der Kernpunkt ist: Auch wenn es mehr Operationen sind, können sie schneller sein, wenn sie weitgehend unabhängig sind und daher parallel ausgeführt werden können.
    Umgekehrt können weniger Operationen langsamer sein, wenn sie wegen Datenabhängigkeiten seriell ausgeführt werden müssen; diese Idee gilt weit über Langzahl-Arithmetik hinaus.

    • Ein anderer Ansatz wäre, normale 64-Bit-Stücke zu verwenden, jede Addition parallel spekulativ einmal mit und einmal ohne Carry auszuführen und anschließend anhand des Carry-Ergebnisses der niederwertigen Addition die richtige Seite auszuwählen.
      Das verdoppelt die Zahl der Additionen, kann aber die Carry-Propagationszeit von linear auf log(bits) reduzieren.
    • Was ich nicht ganz verstanden habe: Die hier gezeigte Technik scheint darauf abzuzielen, dass beim Addieren von N Werten der Ripple Carry nicht N-1-mal, sondern nur einmal auftritt.
      Die Carry-Operation ist komplizierter, aber die eigentlichen Additionen lassen sich parallelisieren.
      Da man die Eingabezahlen aber ohnehin in Bündel aus 5 Registern aufteilen muss, müsste doch auch diese Aufteilung parallelisierbar sein, damit man insgesamt gewinnt, oder?
    • Nvidia verfolgt diese allgemeine Idee offenbar genauer und erzielt in einigen Bereichen ziemlich vielversprechende Ergebnisse.
    • Diese Regel skaliert bis hin zu Multi-Node-Supercomputern oder der Cloud.
      Wenn man 10.000 Kerne einsetzen kann, ist der Overhead vernachlässigbar.

  • Jemand, der nur mit x86_64 gearbeitet hat, zeigt sehr gut, dass es bei RISC-V nicht falsch war, das Carry-Flag wegzulassen.

    • Man kann auch anders vorgehen und trotzdem 64-Bit-Limbs beibehalten.
      Die zentrale Einsicht ist: Solange die Summe an einer bestimmten Limb-Position nicht nur aus Einsen besteht, hängt der ausgehende Carry an dieser Position nicht vom eingehenden Carry ab, sondern nur davon, ob die ursprüngliche Addition an dieser Position einen Carry erzeugt hat.
      Wenn die Summe nur aus Einsen besteht, ist der ausgehende Carry gleich dem eingehenden Carry.
      Formuliert man das als bedingten Sprung, der fast immer als not-taken vorhergesagt wird, können die einzelnen Instruktionsblöcke vollständig parallel ausgeführt werden — unter der Annahme, dass mehrere bedingte Sprünge im selben Taktzyklus als not-taken vorhergesagt werden können.
      Einmal in 2^64 Fällen läuft es sehr langsam.
      Auf einer 4-wide-Maschine bringt das bei 4-Limb-Zahlen keinen Vorteil gegenüber adc, aber auf einer 8-wide-Maschine mit 8-Limb-Zahlen beginnt der Vorteil deutlich zu werden.
      Für heutiges x86_64 hilft das möglicherweise wenig, aber bei Apples M-Serie, bei der auch der M1 8-wide ist, gibt es Potenzial; wegen der Arm-ISA könnte der Umweg allerdings schwierig sein.
      Wenn Tenstorrents 8-wide RISC-V Ascalon Ende dieses Jahres oder Anfang 2026 erscheint, lässt sich das zusammen mit Ventana, Rivos, XiangShan und anderen praktisch überprüfen.
      Mit einem schnellen 1-Lane-Shift funktioniert es auch in breitem SIMD besser; bei RISC-V heißt das slideup.
    • Es gibt immer noch viele häufige Fälle, in denen carry-save addition schlechter ist als add-with-carry.
      Die beiden Algorithmen für Multi-Word-Addition ersetzen einander nicht, sondern haben unterschiedliche Einsatzbereiche; deshalb enthalten vernünftige ISAs ADC/SBB-Befehle, und die Zusatzkosten sind minimal.
      Ein dediziertes Flag-Register ist dafür auch nicht zwingend nötig; manche ISAs speichern Carry- und Borrow-Flags bei Bedarf in allgemeinen Registern.
      Dass RISC-V keinen Carry hat, ist nicht seine schlimmste Eigenschaft; schlimmer ist das Fehlen eines Integer-Overflow-Flags.
      Für Programme, die den Anspruch erheben, sicher geschrieben zu sein, ist Integer-Overflow-Erkennung unverzichtbar; sie in Software zu umgehen senkt die erreichbare Performance weit stärker als Workarounds für fehlenden Carry.
    • Diese Entwicklung geht letztlich darauf zurück, dass C das Carry-Flag ausgelassen hat; in der Praxis wird es für Carry-Zwecke kaum noch verwendet.
    • Wenn das Carry-Flag ohnehin langsam ist, war ich wohl nicht der Einzige, der dachte: „Worum ging es bei der RISC-V-GMP-Kontroverse eigentlich?“

  • Dieser radix trick lässt sich auch auf Datenstrukturen anwenden.
    In Okasakis Buch 『Purely Functional Data Structures』 gibt es ein gutes Beispiel.

  • Ich wünschte, ich hätte diesen Artikel vor ein paar Monaten gesehen.
    Beim Versuch, einen Puffer in einer beliebigen Basis zu codieren und zu decodieren, kam ich viel zu spät zu dem Schluss, dass sich der Carry bis ans Ende des Puffers fortpflanzen kann und der Algorithmus dadurch massiv langsamer wird.
    Am Ende hatte die Lösung auch Ähnlichkeiten mit diesem Trick: Ich teilte den Puffer in Chunks auf und ließ Spielraum für die Carry-Verarbeitung.
    Es war nicht exakt dasselbe; ich ließ ein paar verschwendete Bits übrig und verbrauchte dadurch minimal mehr Speicherplatz oder Netzwerkbandbreite, reduzierte aber die Rechenarbeit.
    Ich frage mich, ob man auf diese Weise Carry sammeln und in einer späteren Phase auflösen kann, um beides zu bekommen — vielleicht ist das aber auch Wunschdenken.

  • Ich weiß, dass man nach den HN-Guidelines den Titel nicht ändern soll, aber Clickbait-Titel, die eine kleine Behauptung viel zu weit aufblasen, gefallen mir nicht.
    Der Titel dieses Artikels hätte eher lauten sollen: „Der radix-2^51-Trick, um 64-Bit-Integer auf einigen x86-Architekturen parallel zu addieren, ohne die Pipeline durch Carry-Abhängigkeiten zu verlangsamen“.