Radix 2^51リムはキャリーを遅延させることで加算キャリー連鎖に打ち勝つ

64ビットより広い数値の加算は簡単であるべきだ。各256ビット整数を4つの64ビット片に分割し、それらを加算して、あふれた分を上位へ伝播させればよい。問題はそのオーバーフローにある。キャリーなしでは答えが誤りになるため、正しい版ではx86のキャリー付き加算命令（adc）を最下位リムから上へ連鎖させる。現代のアウトオブオーダーCPUでは、この連鎖は誤った並列コードより遅い。adcはより重い命令であり、各命令が前の命令が生成したキャリーフラグに依存するからだ。Haswell CPUは1サイクルに最大4つの独立した加算を発行できるが、連鎖したadcは直列に実行される。

直感に反する修正法は、暗号文献でradix 2^51表現として知られるもので、それぞれがレジスタより小さい、より多くのリムを使うことだ。自明な手法が256ビットを4つの基数2^64桁に分割するのに対し、この手法は5つの基数2^51桁に分割する。各64ビットリムは依然としてその桁を保持するが、上位12〜13ビットはキャリーが蓄積できる空間として空のまま残される。この余裕のおかげで、正規化された値の加算は予備ビットが埋まるまで、すなわちおよそ2^13回の加算まで、まったくキャリーを生じない。したがってすべての加算が独立し、プロセッサはそれらを並列にスケジュールする。

キャリーは排除されるのではなく、遅延されるだけだ。余裕が尽きると、1回の正規化パスが各リムのオーバーフローを上のリムへ移し、余白をクリアする。減算も同様に、1ビットの余裕を犠牲にしてリムを符号付きとして扱うことで機能する。著者がHaswellマシンで行った簡単なベンチマークでは、radix-2^51の加算は、その表現への変換と変換戻しのコストを含めても、わずか3回の加算でradix-2^64の加算よりすでに速く、加算が積み重なるほど節約は大きくなった。

この記事はまず紙の上で直感を組み立てる。基数10では、各桁の範囲を広げて9を超えて数えられるようにすると、どの桁もオーバーフローする前に複数の正規化された数を加算でき、1回の正規化パスで結果を戻せる。これをバイナリレジスタに移すと、同じ原理が、この表現が暗号で標準となっている理由であり、直感に反して、数をより多くのレジスタに分散させ、より多くの命令を発行するほど算術が速くなる理由でもある。2017年に初めて公開され、この記事は2020年5月にHacker Newsへ投稿され、518ポイントと83コメントを集めた。

リムを51ビットに縮めて予備ビットにキャリーを吸収させる。加算は独立かつ並列のままで、正規化は最後に一度だけ行われる

キャリーが依存関係である。連鎖したadc命令は各命令が前のキャリーフラグを待つため直列化するが、独立した通常の加算はHaswellで1サイクルに4つ発行できる。

空の余裕が仕掛けである。64ビットレジスタ内の51ビット桁は12〜13ビットを自由に残すため、キャリーを伝播させる必要が生じる前に、およそ2^13回の加算が行われる。

1回の遅延パスは多数の即時パスに勝る。最後の正規化は、すべての演算でのキャリー依存ではなく、固定の一掃である。

余分なリムはそれ自体で元が取れる。5つの通常の加算は、変換コストを数えても、わずか3回の加算から4つのadc連鎖に勝る。

直列依存を断ち切るには、後で返済する余裕を加える。ホットな演算が自由に走れるよう余裕を確保し、遅延した作業を1回のパスで片付ける。

2017年に公開され、2020年5月にHacker Newsへ投稿されると、518ポイントと83コメントを集めた。実務者たちはこの仕掛けを実際のコードに結びつけた。コメント投稿者たちは、Curve25519の体算術が法2^255−19で動作するため値が51ビットリムに収まり、32ビットCPUではradix-2^25.5の変種があると指摘した。他の者たちはBroadwellのADCX/ADOX命令と部分レジスタストールについて議論し、ある者は記事の最上位リムの説明の誤りを指摘した。この技法は記事が呼んだとおりのもの、すなわち暗号における標準的なradix-2^51表現であり、体算術が高速かつ定数時間でなければならない場面で使われ続けた。