- 多倍長整数の加算は通常 64ビットの limb に分割して処理するが、桁上がり伝播が発生すると現代CPUの並列実行の利点を十分に活かしにくい
- x86 の
adc は前の演算の carry flag に依存して命令チェーンを直列化するため、Intel Haswell のように複数の add を並列実行できる構造でもボトルネックになる
- radix 2^51 表現 は 256ビット値を 4 個の 2^64 桁ではなく 5 個の 2^51 桁に分け、各 limb の余った上位ビットを中間的な桁上がりの保存領域として活用する
- 桁上がりをなくす方式ではなく、複数回の加算のあいだ 伝播を遅延 させたあと、最後の正規化段階でまとめて処理する
- Haswell での簡単なベンチマークでは、変換コストを含めても 3回の加算 から radix 2^64 方式より速く、反復回数が増えるほど利点も大きくなった
多倍長整数の加算で桁上がりがボトルネックになる理由
- 紙で行う筆算の加算は 1 の位から右から左へ進める
- 各桁の結果が右の桁から来る 桁上がり に依存するため
- 左から加算すると、あとで発生した桁上がりのせいで、すでに計算した上位桁の結果を修正し直さなければならない
- 多倍長整数の加算も同じ制約を持つ
- 256ビット整数
x と y を 4 個の 64ビット limb に分けると、同じ位置の limb 同士を加算できる
- 下位 limb でオーバーフローが起きたら、その 1 をより上位の limb に渡さなければならない
- x86 の
adc はこの伝播を処理する命令である
- 前の演算でオーバーフローしたかどうかを見て、必要なら 1 を加える
- 正しい 256ビット加算は最下位 limb から
add, adc, adc, adc の順に続く
adc が現代CPUで遅くなる構造
adc はたいてい通常の add より実行コストが高い
adc は carry flag という 3 番目の入力を使うため、add より複雑であるadd より使用頻度が低いため、CPU設計者が adc の性能最適化にチップ面積を割く動機が小さい
- より大きな問題は 命令依存性 である
- Intel Haswell では単一の
add は実行に 1 サイクルかかる
- 理想条件では Haswell は 1 サイクルあたり最大 4 個の
add を実行できる
- Haswell には 8 個の実行ポートがあり、そのうち 4 個が整数
add を実行できる
- 独立した 4 個の
add は並列実行しやすい
- 一方
adc チェーンは各命令が前の命令の carry flag 出力に依存する
- CPU はこれらの命令を並列化できず、順番に実行しなければならない
- SIMD では損失がさらに大きい
vpaddq は 4 個の 64ビット加算を同時に実行する- Haswell は 1 サイクルに 2 個の
vpaddq を実行できる
- 桁上がり処理のためにこの並列性を放棄すると、性能上の利点が縮小する
筆算で見る桁上がりの遅延
- 10進の位取りは維持したまま、各桁に入れられる文字を広げれば桁上がりを遅らせられる
- 通常の
0-9 の代わりに A-Z や * まで含め、合計 37 文字を使う
- ただし基数自体は 37 進数ではなく、依然として 10進の位取り を保つ
- 1 桁が 9 を超えても、すぐに桁上がりさせる必要がなくなる
29 + 1 は 30 と書けるが、2A, 1K, U のようにも表現できる- 2 つの数の各桁がいずれも 9 以下に 正規化 されていれば、加算中の桁上がりを先送りできる
- すべての入力に常に適用できるわけではない
9 + W のようにすでに大きい桁値が入っている場合は桁上がりが必要になる- 正規化された数同士なら最大 4 個まで、桁上がりなしで加算して表現できる
- 最後には再び通常の 10進表現へ正規化しなければならない
- 右端から各桁に 10 が何個含まれているかを計算する
- その分を現在の桁から引き、次の桁へ渡す
- 核心は桁上がり伝播をなくすことではなく、中間計算のあいだ保存 しておき、最後に一度だけ伝播する点にある
コンピュータにおける radix 2^51 表現
- 256ビット値を 4 個の 2^64 limb に分けると、各 limb は 0 から 2^64−1 までの値を取れる
- 各 limb を 2^64 進数の桁 とみなす方式である
- ハードウェアの 64ビット整数の範囲は広げられないため、基数の大きさを小さくする
- 256ビット値を 4 個の 2^64 桁ではなく 5 個の 2^51 桁 に分ける
- 各 limb は引き続き 64ビット整数として格納されるが、実際に使う値は 51ビットまたは 52ビットだけである
- 余った上位ビットが中間的な桁上がりの保存領域になる
- 各 limb には元の数の 51ビットまたは 52ビットが入る
- 残りの 12ビットまたは 13ビットが計算中に発生した桁上がりを保持する
- この手法は暗号文献で radix 2^51 representation と呼ばれる
- 正規化された数であれば、2^64 個の可能な limb 値の範囲内で、最大 2^13 個を加えるまでは上位 13ビットのオーバーフローを心配しなくてよい
52ビット最上位 limb と正規化
- 最上位 limb には 52ビットを割り当てる
- 残りの limb は 51ビットを使う
- 最上位 limb の桁上がりは無視し、2^256−1 を超える場合はラップアラウンドするように扱う
- これは C の通常サイズの unsigned 整数加算がオーバーフロー時にラップアラウンドする方式と同じである
- radix 2^51 加算コードは
adc チェーンを使わず、5 個の add を独立に実行する
- 4 個の 2^64 limb 方式より
add の数は 4 個から 5 個へ増える
- その代わり carry flag 依存がないため並列実行が可能になる
- 正規化段階では各 limb の上位ビットを取り出して次の上位 limb に加える
shr 51 で carry 部分を抽出するand 0x0007FFFFFFFFFFFF で 51ビット未満だけを残す- 最上位 limb は
and 0x000FFFFFFFFFFFFF で整える
- 正規化は遅延させておいた桁上がり伝播を最後に実行する段階である
- 中間の加算では carry flag 依存を作らない
- 最終的に各 limb を再び許容範囲内に収める
性能結果と減算への拡張
- 簡単なベンチマークで、radix 2^51 加算は Haswell CPU 上でより高速な結果を示した
- radix 2^51 表現への変換と復帰のコストまで含んでいる
- 3回の加算 だけでも radix 2^64 加算より速かった
- 加算回数が増えるほど削減効果も大きくなる
- 同じアイデアは減算にも拡張できる
- 減算をサポートするには limb を unsigned ではなく signed 整数のように扱う
- 各桁値は正にも負にもなりうる
- 各 limb は正の carry と負の carry の両方を保存できる
- この変更にはコストがある
- 各 limb の最上位ビットが符号ビットとして予約される
- 正規化のあいだに実行できる演算回数が 2^13 から 2^12 に減る
- データをより多くのレジスタに分散し、演算数が増えたとしても、桁上がり依存性 を減らせば全体性能は改善しうる
1件のコメント
Hacker News のコメント
最上位 limb を 64ビットにして、残りの 4つの limb をそれぞれ 48ビットにするのではだめなのか気になる
正規化前により多くの加算を蓄積できるし、命令セットに有用な機能があれば分割・正規化時にワード境界の整列も活用でき、オーバーフロー特性も同じに見える
汎用の多倍長整数ライブラリなら最適ではないかもしれないし、昔は任意ビットシフトを効率的に行うバレルシフタがなかったため、キャリー用にちょうど 1バイト残して 64ビット中 56ビットを使うような方式がよかったのだろう
RISC-V にはフラグがないため、この議論はかなり関係がある
たとえば両方とも 2^63 ならすぐにあふれるし、ラップアラウンド算術なら問題ないかもしれないが、一般的な場合には合わない
AVX512、そしてある程度は AVX2 でも 256ビット加算をかなり効率よく実装でき、レジスタにより多くの数を載せられる利点もある
_mm256_add_epi64、比較マスク、キャリーマスクを組み合わせる方式で、スループットもよさそうに見える: https://godbolt.org/z/e7zETe8xY512ビット加算に変えるのも簡単で、その場合は改善幅がさらに大きいはず
https://stackoverflow.com/questions/56852812/simd-instructio...
十分に新しい x86 CPU、たとえば Intel Broadwell や AMD Ryzen では ADXも使えるし、radix 2^51 表現が伝統的に有利だった Curve25519 のような状況でも、今ではこちらのほうが速い場合がある
[1] https://en.wikipedia.org/wiki/Intel_ADX
関連記事としては、以前の radix 2^51 trick のスレッドがある
The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - 2022年11月
The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - 2020年5月
核心は、演算数が多くてもおおむね独立していれば並列実行できるので、より速くなり得るということ
逆に演算数が少なくても、データ依存性のために直列実行しなければならないなら遅くなり得るし、この考え方は長整数演算よりはるかに広く適用できる
加算回数は 2倍になるが、キャリー伝播時間を線形ではなく log(bits) に減らせる
キャリー演算はより複雑だが、実際の加算は並列化できる
しかしそもそも入力の数を 5つのレジスタの組に分けなければならないので、全体として得をするには、その分割も並列化できる必要があるのではないかと思う
10,000コアを動員できるなら、オーバーヘッドは無視できるほど小さい
x86_64 だけで作業してきた人が、RISC-V が キャリーフラグを省いたのは間違いではなかったことを非常によく示している
核心的な洞察は、ある limb 位置の和がすべて 1 でない限り、その位置から出るキャリーは入ってくるキャリーに依存せず、もともとその位置の加算がキャリーを生成したかどうかだけに依存するということ
和がすべて 1 なら、出るキャリーは入ってくるキャリーと同じになる
これをほぼ常に not-taken と予測される条件分岐として表現すると、複数の条件分岐を同じクロックサイクルで not-taken と予測できるという前提のもとで、各命令ブロックを完全に並列実行できる
2^64 回に 1 回は非常に遅く実行される
4-wide マシンで 4-limb の数なら
adcに対する利点はないが、8-wide マシンで 8-limb の数なら利点が大きくなり始める現在の x86_64 にはあまり役立たないかもしれないが、M1 も 8-wide である Apple M シリーズでは可能性があり、Arm ISA のために回避策は難しいかもしれない
Tenstorrent の 8-wide RISC-V Ascalon が今年末か 2026年初めに出れば、Ventana、Rivos、XiangShan などとあわせて実際に確認できるだろう
高速な 1-lane shift があれば広い SIMD でもよりうまく動作し、RISC-V ではこれを slideup と呼ぶ
2つの多ワード加算アルゴリズムは互いを置き換えられず用途が異なるため、まともな ISA には ADC/SBB 命令が入り、追加コストもごく小さい
専用のフラグレジスタが必ず必要なわけでもなく、一部の ISA は必要なときにキャリー・ボローフラグを汎用レジスタに保存する
RISC-V にキャリーがないことは最悪の特徴ではなく、もっと悪いのは 整数オーバーフローフラグがない点
安全に書かれていると主張するプログラムには整数オーバーフロー検出が不可欠だが、これをソフトウェアで回避すると、キャリー不在の回避よりも達成可能な性能をはるかに低くしてしまう
この radix trick はデータ構造にも適用される
Okasaki の本『Purely Functional Data Structures』に良い例がある
数か月前にこの記事を見ていたらよかったと思う
任意の基数でバッファをエンコード・デコードしようとして、キャリーがバッファ末尾まで伝播し得ること、そしてそのためにアルゴリズムが大きく遅くなることに、かなり遅れて気づいた
結局、解決策もこのトリックに似たところがあり、バッファをチャンクに分けてキャリーを処理するための余裕を残した
正確に同じではなく、少しの無駄ビットを置いてストレージやネットワーク帯域をほんの少し多く使う代わりに計算を減らした
こういう形でキャリーをためておき、後の段階で解消すれば両方のいいとこ取りができるのか気になるが、希望的観測かもしれない
HN ガイドライン上、タイトルを編集するなというのは分かるが、小さな主張を過度に広げるクリックベイトなタイトルは好きではない
この記事のタイトルは「一部の x86 アーキテクチャでキャリー依存によりパイプラインを遅らせずに 64ビット整数を並列に加算する radix 2^51 trick」くらいであるべきだった