ハクソク

世界を動かす技術を、日本語で。

2^51基数トリック (2017)

361日前原文(chosenplaintext.ca)

概要

  • 現代CPU での大きな整数の加算・減算を高速化する技術を解説
  • キャリー伝播 が並列化の障害となる理由と、CPU命令の違いによる性能差を説明
  • 基数変換（radix 2⁵¹表現） を利用したキャリー伝播の遅延方法を紹介
  • 実際のアセンブリコード例と、正規化処理の仕組みを具体的に解説
  • 減算への応用や、パフォーマンス向上の理由も説明

現代CPUにおける高速な加算・減算

  • 紙の筆算 では右端（1の位）から順に加算し、キャリーを左へ伝播する手順
  • 大きな整数 （例: 256ビット以上）の加算も、基本的に同様のアルゴリズムを採用
  • なぜ右端から始めるかというと、 キャリー（繰り上がり） の伝播が必要なため
  • 左端から加算すると、途中でキャリーが発生した場合に 再計算 が必要となり、効率が悪化
  • 並列化 が難しく、計算の各段階が前段階の結果に依存する構造

CPUでの加算命令とキャリー処理

  • CPU は10進数ではなく、通常は64ビット整数を単位に演算
  • 256ビット整数を加算する場合、 64ビットごとに分割 （リムブ化）し、対応する部分同士を加算
  • 各リムブでオーバーフローが発生する場合、 キャリー を次のリムブに伝播する必要
  • x86系CPUには adc（add with carry）命令 があり、前回のキャリーを自動的に加算
  • 例: 
    add D, H
adc C, G
adc B, F
adc A, E
    このように、 下位から上位へ キャリーを伝播

キャリー伝播による性能低下

  • adc命令 は通常のadd命令よりも 実行が遅い 傾向
  • Haswell世代CPU では、add命令は最大4命令同時実行可能
  • しかしadc命令は 逐次実行 が必要なため、並列化できず性能が大幅に低下
  • SIMD命令 （例: vpaddq）を使えば、複数の加算を同時実行可能だが、adcによるキャリー伝播がボトルネック

キャリーを遅延させるアイデア（紙上の例）

  • キャリー発生を抑えるために、 各桁の取りうる値の範囲を拡張 （例: 0-9, A-Z, * の37種類）
  • これにより、 複数の数値をキャリーなしで加算 可能
  • ただし、最終的には正規化して 通常の表現に戻す 必要
  • この手法は キャリー伝播を遅延 させるアイデアの本質

コンピュータにおけるキャリー遅延（radix 2⁵¹表現）

  • ハードウェアの制約で 取りうる値の範囲自体は変えられない

  • 代わりに、リムブの ビット幅を減らし、余ったビットをキャリー用に確保

  • 例: 256ビット整数を 5つのリムブ（52, 51, 51, 51, 51ビット） に分割

  • これにより、 キャリー発生を遅延 し、複数回の加算をキャリーなしで並列実行可能

  • この方式は radix 2⁵¹表現 と呼ばれ、 暗号分野 でよく使われる

    • 各リムブの上位ビットをキャリー用に確保
    • 例えば13ビット余裕があれば、 213回まで加算 をキャリーなしで実行可能

実装例と正規化処理

  • 加算は単純なadd命令のみを使い、 並列処理 が可能
  • 加算後は 正規化（キャリー伝播） 処理を実施
    • 各リムブの余剰ビットを次のリムブに加算
    • and命令でリムブのビット幅を制限
  • 例: 
    mov T, E
shr T, 51
add D, T
and E, 0x0007FFFFFFFFFFFF
  • 変換コストを含めても、従来方式より高速 な場合が多い

減算への応用

  • 減算 も同様の手法を拡張可能
  • 減算では 負のキャリー が発生するため、リムブを 符号付き整数 として扱う
  • 各リムブの最上位ビットを 符号ビットとして確保
  • その結果、加算よりも 1ビット分だけ余裕が減少 するが、実用上は問題なし

まとめ

  • リムブ数の増加や操作数の増加 にも関わらず、 キャリー伝播の遅延 によって大幅な性能向上
  • 現代CPUの並列実行能力 を最大限活用できる手法
  • 暗号分野 などでの大きな整数演算の高速化に有効
  • 直感に反するが、分割と余裕を持たせることで逆に高速化 が実現可能
  • キャリーの遅延と正規化処理 の組み合わせが鍵

Hackerたちの意見

余談だけど、なんで12ビットじゃなくて13ビットなの？私たちの目的では、最上位のリムのキャリーを無視することにしてるから、2256 - 1を超えたときに数字がラップするんだ。これは、Cの通常の整数型での符号なし加算と同じ感じ。だから、最上位のリムに52ビットを割り当てて、他のリムよりもキャリーのためのスペースが足りなくなることを無視できるんだ。じゃあ、最上位のリムに64ビット、他の4つのリムにそれぞれ48ビットを与えたらどうなるの？ノーマライズする前にもっと加算できるし、命令セットに何か便利なものがあれば、分割やノーマライズの際にワードアライメントを利用できるし、オーバーフローの特性も同じだよね？

└

そうなると、OPの5ではなく256ビットの値を保持するのに6つのワードが必要になるし、それに伴って加算するための命令も増えるね。

└

2つのエンコードされた数の上位ビットを足すと、すぐにオーバーフローしちゃうから。例えば、両方を2^63に設定すると、すぐにオーバーフローするんだ。ラップアラウンド算術には問題ないかもしれないけど、一般的にはそうじゃないよね。

adcが現代のCPUでaddよりも本質的に遅いとは思えないんだけど、キャリービットによるデータハザードを除けばね。この記事のポイントがデータハザードに関するものだってことは分かるから、これは本当に小さな指摘だね。

└

uops.infoによると、（Alder Lake）でのレイテンシはどちらも1サイクルだけど、スループット（低い方が良い）はaddが0.20（つまり1サイクルで5回）、adcが0.50（つまり1サイクルで2回）だから、これが正しいみたい。これは、addがポート0、1、5、6、Bで利用できるのに対して、adcはポート0と6だけで利用できることの結果みたいだね。だから、個々の命令としては悪くないけど、依存しない命令でもOoO実行では悪化するだろうね（これは単一の命令として見るよりも現実的だよ）。

└

その通りだね。同じALUでできるけど、キャリーフラグへのデータ依存性があるから、CPUの観点から見ると本当に異なる命令になる。データ依存性が3つになるからね。CPUにとっては、命令を異なる扱いにするのが有利なんだ。

└

CPUって本当に面白くて、変わったものだよね。プログラマーの私たちは毎日それを使ってて、たくさんの仮定をしてるし、コンパイラからランタイム、ループやメソッドの動作まで、いろいろ考えちゃう。自分のC#でエンティティコンポーネントシステムを作ってるんだけど、最初からやり直して、あらゆる仮定をテストしなきゃいけなかった。直感が正しかったのはほんの数回で、ほとんどは驚くべき落とし穴があちこちに隠れてるんだよね。

C(++?)コンパイラがこの最適化を実装するのは合法なのかな？

└

C++にはuint256のネイティブサポートがあるの？

└

うん、as-ifルールに従ってるよ。挙動に観察可能な違いはないからね。例えば、32ビットや16ビットのアーキテクチャでループ内で64ビットの加算をサポートする場合にも当てはまるよ。

└

予期しない最適化がサイドチャネル（最も一般的にはタイミング）を引き起こすことがあります。これは安全だけど、「コンパイラにどれを使わないか教えるのはどうするの？」っていうのは別の話だよね。

x86_64で完全に作業している誰かが、RISC-Vがキャリーフラグを省略するのが間違っていないことを見事に示しているね。

└

それに、64ビットのリムを維持しながら別の方法もあるよ。すべての変数はuint64_t。s0 += a0; s1 += a1; s2 += a2; s3 += a3; c0 = s0。ここでの重要なポイントは、特定のリム位置での合計がすべて1でない限り、その位置からのキャリーアウトはそのリム位置へのキャリーインに依存しないってこと。元の加算がその位置でキャリーを生むかどうかだけに依存する。合計がすべて1の場合、キャリーアウトはキャリーインと同じになる。これを条件分岐で表現して、ほぼ常に取り込まれないと予測されるなら、コードは各命令ブロックを完全に並列で実行できるはず。複数の条件分岐が同じクロックサイクルで取り込まれないと予測できる場合ね。2^64回に1回はすごく遅く実行されるけど。4つのリム数がある4幅のマシンでは、adcと比べて特に利点はないけど、例えば8幅のマシンで8つのリム数があれば、かなりの利点が出てくる。今のx86_64ではあまり役に立たないかもしれないけど、AppleのM*シリーズでは効果があるかも。M1でも8幅だし、Arm ISAを回避するのは難しいかもしれないけどね。Tenstorrentの8幅RISC-V Ascalonプロセッサが今年の遅い時期か2026年初頭に登場すれば、実際にどうなるか見てみよう。そしてVentanaやRivos、XiangShanなども。広いSIMDではさらに効果的で、速い1レーンのシフト（RISC-Vでは「スライドアップ」と呼ばれる）があればいいね。

└

はは、俺だけじゃないんだ。「キャリーフラグが遅いなら、risc5 gmpの騒ぎは何だったんだ？」って思ってるのは。

└

これはすべてCがキャリーフラグを省略したことに起因していて、実際にはキャリーの目的でほとんど使われないんだよね。

└

キャリーセーブ加算が、キャリー付き加算よりも劣るケースはまだまだよくあるよ。2つのマルチワード加算アルゴリズムは互いに置き換えられないし、それぞれに使い道があるから、ADC/SBB命令はどんなまともなISAにも含まれてるんだ。追加するコストはほとんどないからね。専用のフラグレジスタは必要ないし、いくつかのISAではキャリー/ボローのフラグを汎用レジスタに格納することもあるよ。キャリーがないのはRISC-Vの最悪の特徴ではないけど、整数オーバーフローフラグがないのはもっと厄介だね。整数オーバーフローを検出するためのソフトウェアの回避策は、安全に書かれたプログラムには必須だから、キャリーがない場合の回避策よりもパフォーマンスを大幅に下げちゃうんだ。

主なポイントは、ほとんど独立している操作を増やす方が速くなるかもしれないってこと。そうすれば並列に実行できるからね。逆に、データ依存のために直列に実行されることを強いられると、操作を減らす方が遅くなるかもしれない。この考え方は、長整数の操作に限らず、もっと広く適用できるよ。

└

そうだね。別のアプローチとしては、通常の64ビットのチャンクを使って、キャリーありとなしで各加算を並列に予測実行する方法があるよ。そして、より低位の加算のキャリー結果に基づいて正しいバリアントを選ぶ。加算の数が倍になることで、伝播時間が対数的になる（線形ではなく）。

└

このルールは、マルチノードのスーパーコンピュータやクラウドにまでスケールアップします。10,000コアを使えるなら、オーバーヘッドはほとんど気にならないですね。

関連情報。他には？「radix 2^51トリック」 - https://news.ycombinator.com/item?id=33706153 - 2022年11月（コメント数6）「radix 2^51トリック（2017）」 - https://news.ycombinator.com/item?id=23351007 - 2020年5月（コメント数83）

「radixトリック」はデータ構造にも使えるよ。岡崎の本「純粋関数型データ構造」にはいい例がいくつか載ってる。

大きな掛け算をどうやってやるかって？

└

大きな掛け算は畳み込みを使って、その後にキャリーを処理することができるよ。畳み込みはFFTを使って、点ごとに掛け算して、逆FFTを行うことで、従来の掛け算のO(n^2)に対してO(n log n)でできるんだ。ただし、各ビットはキャリーがたくさんあるからかなり小さくなるかもしれないし、桁数や浮動小数点の精度によっても変わるよ。大きな掛け算はどれも何らかのFFTを使ってるんだ。GIMPS（グレート・インターネット・メルセンヌ素数探索）に関連してこれを学ぶのがすごく楽しかったよ。そこでは、無理数ベースのDWTという変種のFFTを使って、素数判定のためのメルセンヌ素数候補に必要なmod 2^n-1を無料で得られるんだ。

代わりにSIMDレジスタで加算を実装するのもアリだよ。これだと、256ビットの数をレジスタにもっと保持できるから（スタックに溢れさせる必要がない）し、スループットも良さそうだね。こんな感じになるよ：const __m256i all_ones = _mm256_set1_epi64x(~0); __m256i s = _mm256_add_epi64(a, b); int g = _mm256_cmpgt_epu64_mask(a, s); int p = _mm256_cmpeq_epu64_mask(s, all_ones); int carries = ((g こちらも見てみて: https://godbolt.org/z/P4Ts3hKKP 512ビットの数を扱うと、改善がさらに顕著になるよ。