Radix-2^51-Glieder schlagen Add-with-Carry-Ketten durch verzögerte Überträge

Das Addieren von Zahlen, die breiter als 64 Bit sind, sollte einfach sein: Man teilt jede 256-Bit-Ganzzahl in vier 64-Bit-Stücke, addiert sie und propagiert jeden Überlauf nach oben. Der Haken ist der Überlauf – ohne Überträge ist das Ergebnis falsch, daher verkettet die korrekte Version x86s Add-with-Carry-Befehl (adc) vom niederwertigsten Glied aufwärts. Auf modernen Out-of-Order-CPUs ist diese Kette langsamer als der fehlerhafte parallele Code: adc ist ein schwererer Befehl, und jeder hängt vom Carry-Flag des vorherigen ab. Eine Haswell-CPU kann bis zu vier unabhängige Additionen pro Zyklus ausgeben, aber verkettete adcs werden seriell ausgeführt.

Der kontraintuitive Ausweg, in der Kryptographieliteratur als Radix-2^51-Darstellung bekannt, besteht darin, mehr Glieder zu verwenden, die jeweils kleiner als ein Register sind. Wo der naheliegende Ansatz 256 Bit in vier Ziffern zur Basis 2^64 aufteilt, teilt dieser Ansatz sie in fünf Ziffern zur Basis 2^51; jedes 64-Bit-Glied hält weiterhin seine Ziffer, aber die oberen 12–13 Bit bleiben leer als Raum, in dem sich Überträge ansammeln können. Wegen dieses Spielraums erzeugt das Addieren normalisierter Werte überhaupt keinen Übertrag, bis die freien Bits gefüllt sind – bis zu etwa 2^13 Additionen –, sodass jede Addition unabhängig ist und der Prozessor sie parallel einplant.

Überträge werden nicht beseitigt, nur verzögert. Wenn der Spielraum erschöpft ist, verschiebt ein Normalisierungsdurchlauf den Überlauf jedes Glieds in das darüberliegende Glied und leert den Puffer, und die Subtraktion funktioniert auf dieselbe Weise, indem sie die Glieder als vorzeichenbehaftet behandelt, auf Kosten eines Spielraum-Bits. Die schnellen Benchmarks des Autors auf einer Haswell-Maschine ergaben, dass die Radix-2^51-Addition bereits bei nur drei Additionen schneller ist als die Radix-2^64-Addition, einschließlich der Kosten für die Umwandlung in die Darstellung und aus ihr heraus, wobei die Einsparung mit mehr akkumulierten Additionen wächst.

Der Beitrag baut die Intuition zuerst auf dem Papier auf: Im Zehnersystem, wo man den Wertebereich jeder Ziffer so erweitert, dass sie über 9 hinaus zählen kann, lassen sich mehrere normalisierte Zahlen addieren, bevor eine Ziffer überläuft, und ein Normalisierungsdurchlauf wandelt das Ergebnis zurück. Übertragen auf Binärregister ist dasselbe Prinzip der Grund, warum die Darstellung in der Kryptographie Standard ist – und warum es, kontraintuitiv, die Arithmetik schneller macht, eine Zahl über mehr Register zu verteilen und mehr Befehle auszugeben. Der Artikel wurde erstmals 2017 veröffentlicht, im Mai 2020 auf Hacker News gepostet und erhielt 518 Punkte und 83 Kommentare.

Glieder auf 51 Bit verkleinern, damit freie Bits Überträge aufnehmen: Additionen bleiben unabhängig und parallel, und die Normalisierung erfolgt einmal am Ende

Überträge sind die Abhängigkeit: Verkettete adc-Befehle serialisieren, weil jeder auf das vorherige Carry-Flag wartet, während unabhängige einfache Additionen auf Haswell vier pro Zyklus ausgeben können.

Leerer Spielraum ist der Trick: 51-Bit-Ziffern in 64-Bit-Registern lassen 12–13 Bit frei, sodass etwa 2^13 Additionen stattfinden, bevor ein Übertrag propagiert werden muss.

Ein verzögerter Durchlauf schlägt viele sofortige: Die Normalisierung am Ende ist ein fester Durchlauf statt einer Übertragsabhängigkeit bei jeder Operation.

Das zusätzliche Glied zahlt sich aus: Fünf einfache Additionen schlagen vier adc-Ketten bereits ab drei Additionen, selbst unter Einrechnung der Umwandlungskosten.

Um eine serielle Abhängigkeit zu durchbrechen, füge Spielraum hinzu, den du später zurückzahlst: Reserviere Spielraum, damit die heiße Operation frei läuft, und erledige die aufgeschobene Arbeit dann in einem Durchlauf.

2017 veröffentlicht und im Mai 2020 auf Hacker News gepostet, erhielt es 518 Punkte und 83 Kommentare. Praktiker verankerten den Trick in echtem Code: Kommentatoren merkten an, dass Curve25519s Körperarithmetik modulo 2^255−19 arbeitet, sodass Werte in 51-Bit-Glieder passen, mit einer Radix-2^25,5-Variante auf 32-Bit-CPUs; andere diskutierten Broadwells ADCX/ADOX-Befehle und Teilregister-Stalls, und einer wies auf einen Fehler in der Erklärung des obersten Glieds im Artikel hin. Die Technik blieb das, was der Beitrag sie nannte: eine in der Kryptographie standardmäßige Radix-2^51-Darstellung, verwendet, wo Körperarithmetik schnell und konstantzeitig sein muss.