Der Radix-2^51-Trick (2017)

 (chosenplaintext.ca)
1 Punkte von GN⁺ 2025-05-31 | 1 Kommentare | Auf WhatsApp teilen
  • Das bei großen Ganzzahloperationen auftretende Carry-Problem (Übertrag) ist ein Hauptgrund dafür, dass sich Operationen nur schwer parallelisieren lassen
  • In der x86-Architektur ist die adc-Instruktion zur Carry-Verarbeitung langsamer als die normale add-Instruktion, und aufeinanderfolgende Carry-Verarbeitung begrenzt die parallele Ausführung
  • Mit der Radix-2^51-Darstellung lässt sich die Carry-Weitergabe verzögern, sodass mehr Additionen schnell ausgeführt werden können
  • Jedem Limb (Teilwert) werden nur 51 oder 52 Bit zugewiesen, sodass der verbleibende obere Bitbereich als temporärer Carry-Speicher genutzt werden kann
  • Diese Technik liefert trotz zusätzlicher Registerverwendung und Umwandlungskosten in der Praxis eine bessere Performance als die Radix 2^64

Schnelle Addition und Subtraktion: das Carry-Problem

  • Bei der Addition großer Ganzzahlen ist es wie beim händischen Rechnen mit Überträgen: Auch für Computer erschwert Carry die Parallelisierung des Additionsalgorithmus
  • Grundsätzlich addieren wir von rechts (niedrigwertige Stellen) nach links, wobei ein an jeder Stelle entstehender Carry an die nächste höhere Stelle weitergegeben wird
  • Würde man stattdessen von links mit der Addition beginnen, beeinflusst der vorherige Carry die Berechnung der nächsten Stelle, sodass sich die Reihenfolge der Operationen nicht parallelisieren lässt

Carry-Verarbeitung im Computer

  • Computer führen Additionen in Einheiten von 64-Bit-Ganzzahlen aus
  • Eine 256-Bit-Ganzzahl lässt sich zwar scheinbar in vier 64-Bit-Limbs zerlegen und parallel addieren, tatsächlich muss aber Overflow (Carry) verarbeitet werden, damit das Ergebnis korrekt ist
  • x86 besitzt mit adc (add with carry) eine Instruktion, die die Carry-Verarbeitung automatisch übernimmt

Ursache des Performance-Verlusts

  • Die adc-Instruktion benötigt mit dem Carry-Flag einen zusätzlichen Eingabewert und ist daher im Vergleich zu einfachem add weniger performant
  • In der Haswell-Architektur kann add parallel über mehrere Ports ausgeführt werden, während adc zwangsläufig seriell ausgeführt werden muss
  • Besonders bei SIMD-Instruktionen (vpaddq usw.) ist parallele Addition ohne Carry deutlich schneller

Die Idee, Carry zu verzögern (Beispiel auf Papier)

  • Um Carry zu reduzieren, kann man den Stellenbereich erweitern (z. B. von 0-9 auf insgesamt 37 Stellen mit 0-9, A-Z und *), sodass sich vorübergehend mehrere Zahlen ohne Carry addieren lassen
  • So können mehrere Additionen ohne Carry-Weitergabe durchgeführt und der Carry erst am Ende in einem Schritt bereinigt (normalisiert) werden
  • Dieses Konzept trennt die Akkumulation und Weitergabe von Carry und sorgt dafür, dass Carry erst im Endschritt verarbeitet wird
  • Wenn in der tatsächlichen Berechnung Werte oberhalb der Stellenbasis entstehen, wird der Carry anschließend von rechts nach links der Reihe nach übernommen

Anwendung der Carry-Verzögerung im Computer (Radix-2^51-Trick)

  • Um die Carry-Weitergabe im Computer zu verringern, wird eine Radix-2^51-Darstellung verwendet
  • 256 Bit werden nicht in vier 64-Bit-Limbs, sondern in fünf Limbs zu je 51 bis 52 Bit aufgeteilt
    • Die oberen 12 bis 13 Bit jedes Limb dienen als temporärer Carry-Speicher
  • Bei dieser Methode bleibt pro Limb zwar der Wertebereich von 2^64 erhalten, in der eigentlichen Berechnung tritt Carry aber nicht so leicht auf, sodass mehrere Operationen ohne Carry parallel ausgeführt werden können
  • Nach etwa 2^13 aufeinanderfolgenden Operationen ist einmalig eine Normalisierung (normalization) erforderlich
  • Auf Haswell-CPUs verbessert die Anwendung von Radix 2^51 die Performance gegenüber gewöhnlicher Radix 2^64 deutlich, weil mehrfach nur einfache Additionen ohne Carry ausgeführt werden
  • Die Carry-Propagation zur Normalisierung wird nur einmal am Ende durchgeführt

Codebeispiel

  • Werte werden auf fünf Register verteilt, sodass Additionen ohne Carry möglich sind
  • Bei der Normalisierung werden die oberen Bits jedes Limb extrahiert, zum benachbarten Limb addiert und der eigene Carry-Wert dabei wieder auf 0 gesetzt

Erweiterung auf Subtraktion

  • Dasselbe Verfahren lässt sich ähnlich auch auf Subtraktion anwenden
  • Dabei kann Carry auch negativ werden, weshalb Limbs als signed integer behandelt werden
  • Das höchstwertige Bit des Limb dient als Vorzeichenbit, wodurch sich die Anzahl der in einem Schritt verarbeitbaren Operationen gegenüber der Addition leicht verringert

Fazit

  • Die Technik der Carry-Resistenz bzw. Carry-Verzögerung verbessert die Gesamtperformance real deutlich, obwohl sie mehr Limbs und zusätzliche Umwandlungsschritte erfordert
  • Der Radix-2^51-Trick wird breit in Bereichen mit hohen Performance-Anforderungen wie großen Ganzzahloperationen und Kryptografie eingesetzt
  • Diese Technik ist eine wichtige Idee zur Optimierung der realen Performance von Hardware und Algorithmen

Verwandte Beiträge

1 Kommentare

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

  • Als ich die Zahl 2^51 sah, dachte ich zunächst, es gehe um das Speichern von Ganzzahlen im double-Typ, bemerkte dann aber, dass sich Integer tatsächlich bis 2^53-1 exakt in double darstellen lassen

  • AVX512 (und zu einem gewissen Grad auch AVX2) bietet ein Umfeld, in dem sich 256-Bit-Additionen recht effizient implementieren lassen, mit dem zusätzlichen Vorteil, mehr Zahlen in Registern unterbringen zu können
    Ein direktes Beispiel funktioniert wie im folgenden Code

__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g << 1) + p) ^ p;

__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);

Es zeigt sich sogar eine Verbesserung des Durchsatzes; ein reales Codebeispiel ist auf godbolt.org zu sehen
Diese Logik auf 512-Bit-Addition zu erweitern, ist ebenfalls sehr einfach

  • Besonders auf bestimmten Intel-CPU-Architekturen kann schon die bloße Verwendung von AVX512-Befehlen den gesamten Prozessortakt senken, was zu inkonsistenter oder sogar insgesamt schlechterer Performance führen kann
    Einen relevanten Hinweis dazu gibt es im Stackoverflow-Link

  • Auf die Frage „Warum nicht 12 Bit statt 13 Bit?“: Hier wird die Carry-Behandlung des höchstwertigen Bits (Limb) ignoriert, sodass es bei Overflow als Wraparound arbeitet
    Dadurch erhält das höchstwertige Limb 52 Bit, was den Nachteil hat, dass ihm früher als den anderen Limbs der Platz ausgeht, aber es verhält sich ähnlich wie die Addition vorzeichenloser Integer in C
    Dann kam der Vorschlag: Warum nicht dem obersten Limb 64 Bit und den übrigen vier Limbs jeweils 48 Bit zuweisen?
    Damit könnte man vor der Normalisierung mehr Operationen ansammeln und hätte Vorteile wie Wortausrichtung
    Das Overflow-Verhalten wäre dasselbe

    • Wenn nur dem obersten Limb 64 Bit zugewiesen werden, tritt beim Addieren der Limbs zweier Zahlen zu schnell Overflow auf
      Sind zum Beispiel beide 2^63, kommt es sofort zum Overflow
      Bei Wraparound-Arithmetik ist das egal, im allgemeinen Fall aber nicht praktikabel

    • Mit einer solchen Struktur wären statt wie im OP 5 eher 6 Wörter nötig
      Außerdem wären mehr Befehle erforderlich

    • Das Ziel ist, 256-Bit-Arithmetik mit 5 64-Bit-Registern zu lösen
      Also wäre eine Verteilung von 256/5 = 51.2 Bit pro Wort ideal
      Für genau 256 Bit ist das in Ordnung, für eine allgemeine Big-Int-Bibliothek aber nicht optimal
      Früher gab es den Hintergrund, für ein Carry genau 1 Byte zu verwenden, und in Zeiten ohne Barrel Shifter zog man es vor, zur Ausrichtung nur 56 von 64 Bit zu nutzen
      Bei RISC-V ist diese Diskussion noch wichtiger, weil es dort hardwareseitig keine Flags gibt

  • Auf modernen x86-CPUs (z. B. Intel Broadwell, AMD Ryzen) kann die Verwendung von Intel ADX-Befehlen sogar dort schneller sein, wo die Darstellung in Radix 2^51 traditionell stark war, etwa bei Curve25519

  • Als verwandtes Diskussionsmaterial

  • Die zentrale Lehre ist: Wenn Operationen voneinander unabhängig sind, kann es schneller sein, mehr davon parallel auszuführen
    Umgekehrt können bei Abhängigkeiten, die eine serielle Ausführung erzwingen, sogar weniger Operationen langsamer sein
    Diese Idee lässt sich nicht nur auf lange Integer-Arithmetik, sondern auch auf viele andere Bereiche anwenden

    • Es wurde vorgeschlagen, in 64-Bit-Chunks zu zerlegen und je nach möglichem Carry zwei Fälle vorab parallel auszuführen, um danach anhand des tatsächlichen Carry-Ergebnisses die richtige Rechnung auszuwählen
      Dabei verdoppelt sich die Anzahl der Additionen, aber die Ausbreitungsgeschwindigkeit sinkt auf log(bits) statt linear

    • Der Punkt, den ich an dieser Technik zunächst nicht gut verstanden hatte, ist, dass sie das Ripple-Carry, das beim Addieren von N Werten eigentlich N-1 Mal ausgeführt wird, im Wesentlichen auf ein einziges Mal reduziert
      Die Carry-Behandlung selbst wird komplexer, aber die Additionen lassen sich parallelisieren
      Allerdings muss auch das Aufteilen der Eingabezahlen in Blöcke zu je 5 Registern parallelisierbar sein, damit die Gesamteffizienz wirklich zählt

    • Diese Regel lässt sich bis auf Supercomputer oder Cloud-Umgebungen mit zehntausenden Knoten ausdehnen
      Wenn viele Kerne verfügbar sind, ist der Overhead vernachlässigbar

    • Auch NVidia interessiert sich für diese Idee, und sie liefert in vielen Bereichen gute Ergebnisse

  • Es gibt zwar HN-Richtlinien dagegen, der Überschrift Meinungen hinzuzufügen, aber ich mag übertrieben reißerische Clickbait-Titel auch nicht
    Etwas wie „Radix-2^51-Trick für parallele 64-Bit-Integer-Addition ohne Carry-Abhängigkeit auf einigen x86-Architekturen“ wäre meines Erachtens präziser

  • Schade, dass ich diesen Beitrag nicht schon ein paar Monate früher gelesen habe
    Beim Kodieren/Dekodieren eines Puffers in eine beliebige Basis habe ich erlebt, wie sich Carry über den gesamten Puffer ausbreitet und den Algorithmus stark verlangsamt
    Am Ende habe ich die Chunks mit etwas „Luft“ dazwischen aufgeteilt, um Carry zu behandeln; das scheint dieser Technik zu ähneln
    Praktisch habe ich mich dafür entschieden, einige Bits zu verschwenden, um Rechenaufwand oder Netzwerkbandbreite zu sparen
    Ich frage mich, ob sich eine solche Carry-Behandlung ebenfalls als Nachbearbeitung bündeln lässt
    Die Hoffnung wäre eine Struktur, die praktisch alle Vorteile mitnimmt

  • Nach meinen Erfahrungen ausschließlich auf x86_64 zeigt das sehr klar, dass das Fehlen eines Carry-Flags bei RISC-V nicht zwangsläufig ein schlechter Ansatz ist

    • Es wurde auch eine Methode erklärt, bei der man 64-Bit-Limbs beibehält und trotzdem mit reinen uint64_t-Variablen carry-sichere Addition macht
      Der Ablauf sieht etwa so aus
    s0 += a0;
s1 += a1;
s2 += a2;
s3 += a3;
c0 = s0 < a0; // RISC-V sltu
c1 = s1 < a1;
c2 = s2 < a2;
if (s1 == -1) goto propagate0;
check_s2:
if (s2 == -1) goto propagate1;
add_carries:
s1 += c0;
s2 += c1;
s3 += c2;
goto done;
propagate0: c1 = c0; goto check_s2;
propagate1: c2 = c1; goto add_carries;
done:

    Entscheidend ist: Wenn das Additionsergebnis (Limb) nicht vollständig aus Einsen besteht, hängt sein Carry-out nicht vom Carry-in ab, sondern nur vom Ergebnis der ursprünglichen Addition
    Wenn der Wert dagegen nur aus Einsen besteht, dann gilt Carry-out = Carry-in
    Bei einer Verzweigungsstruktur, die fast keine Vorhersage benötigt, ist das vollständig parallel ausführbar
    Statistisch verlangsamt es nur in 1/2^64 der Fälle, bringt aber auf 4-fach breiten Maschinen keinen großen Vorteil
    Auf 8-fach breiten Maschinen oder bei einer Struktur mit 8 Limbs ist ein sinnvoller Performancegewinn möglich
    Für x86_64 passt es nicht, aber auf 8-fach breiten Maschinen wie Apples M*-Serie könnte es nützlich sein
    Bei Tenstorrents 8-fach breitem RISC-V-Ascalon-Prozessor, Ventana, Rivos, XiangShan usw. gibt es dafür Potenzial in der Zukunft
    Auf SIMD-Architekturen oder Architekturen mit schnellen 1-lane shift(slideup)-Befehlen ist der Effekt am größten

    • Carry-Save-Addition ist nicht immer besser als Add-with-Carry
      Die beiden Arten von Multi-Word-Additionsalgorithmen sind nicht gegenseitig austauschbar und haben jeweils eigene Vor- und Nachteile
      Deshalb gehören ADC/SBB-Befehle zur Grundausstattung einer ISA, und Flags können auch registerbasiert gespeichert werden
      Ein schwerwiegenderer Nachteil bei RISC-V ist das Fehlen eines Integer-Overflow-Flags
      Wenn zur Overflow-Erkennung Software-Workarounds nötig sind, ist der Performanceverlust deutlich größer als bei einem Workaround für das Carry-Bit

    • Dass RISC-V kein Carry-Flag hat, leitet sich daraus ab, dass C ein binäres Carry-Flag ignoriert
      Tatsächlich wird ein Carry-Flag viel seltener genutzt

    • Ich war also nicht der Einzige, der dachte: „Wenn das Carry-Flag ohnehin langsam ist, warum gab es dann diese risc5-gmp-Kontroverse?“

  • Der „Radix-Trick“ lässt sich auch auf Datenstrukturen anwenden
    In Okasakis Buch Purely Functional Data Structures gibt es ebenfalls interessante Beispiele