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

 (chosenplaintext.ca)
1 ポイント 投稿者 GN⁺ 2025-05-31 | 1件のコメント | WhatsAppで共有
  • 多倍長整数演算で発生する carry（桁上がり）の問題は、演算の並列化を難しくする主な原因である
  • x86アーキテクチャでは、carry 処理用の adc 命令は通常の add 命令より遅く、連続した carry 処理は並列実行を制限する
  • Radix 2^51 表現を使うと carry の伝播を遅延させ、より多くの加算を高速に実行できる
  • 各 limb（部分値）には 51 または 52 ビットだけを割り当て、残りの上位ビット領域を carry の一時保存領域として使う
  • このテクニックは、追加のレジスタ使用や変換コストがあるにもかかわらず、実際には 2^64 進数より高い性能を提供する

高速な加算と減算: carry の問題

  • 多倍長整数の加算では、人間が手で桁ごとに carry を処理するのと同じように、コンピュータでも carry のために加算アルゴリズムの並列化が難しい
  • 基本的には、右側（下位桁）から 1 つずつ足し、各桁で発生した carry を左側（上位桁）へ繰り上げる
  • もし左側から加算を始めると、前の carry が次の桁の演算に影響するため、演算順序を並列化できない

コンピュータでの carry 処理

  • コンピュータは 64ビット整数単位で加算を処理する
  • 256ビット整数を 64ビット limb 4 個に分割すれば並列に加算できそうに見えるが、実際には overflow（carry）を処理しなければ正しい結果にならない
  • x86 には carry 処理を自動で行う adc（add with carry）命令がある

性能低下の原因

  • adc 命令は carry flag という追加の入力値を必要とするため、単純な add に比べて 性能が劣る
  • Haswell アーキテクチャでは、add は複数ポートで並列実行できる一方、adc は 直列（逐次）実行が避けられない
  • 特に SIMD 命令（vpaddq など）を使う場合、carry のない並列加算のほうがはるかに高速である

carry を遅延させるアイデア（紙の上での例）

  • carry を減らすため、桁の範囲を拡張して（例: 0-9 に加えて A-Z、* までの合計 37 桁）、一時的に carry なしで複数の数を足せるようにする
  • こうすると carry の伝播なしで複数の加算を進め、最後にまとめて carry を整理（normalization）できる
  • この概念では carry の蓄積と伝播を分離し、最終段階でのみ carry 処理を行う
  • 実際の演算では、桁の基準値以上になった値があれば、右から順に carry を累積して反映する

carry 遅延のコンピュータへの適用（Radix 2^51 トリック）

  • コンピュータで carry の伝播を減らすために radix 2^51 表現を使う
  • 256ビットを 64ビット 4 個の limb ではなく、51〜52ビットずつの 5 個の limb に分割する
    • 各 limb の上位 12〜13 ビットは carry の一時保存領域として機能する
  • この方式では、各 limb が 2^64 の値域を保ったまま、実際の演算時には carry が起きにくいため、複数の演算を carry なしで並列に実行できる
  • 約 2^13 回の連続演算ごとに 1 回 normalization（正規化）が必要になる
  • Haswell CPU では、radix 2^51 を適用すると carry のない単純な加算を何度も実行できるため、通常の radix 2^64 より性能が大きく向上する
  • normalization のための carry propagation は最後に 1 回だけ行う

コード例

  • 5 個のレジスタに値を分けて格納し、carry のない加算を可能にする
  • normalization は各 limb の上位ビットを取り出して隣の limb に加え、自分の carry 値を 0 にする操作を繰り返す

減算への拡張

  • 減算にも同様の方法を適用できる
  • この場合 carry は負になることもあるため、limb を signed integer として扱う
  • limb の最上位ビットが符号ビットに割り当てられるため、加算に比べて 1 回で処理できる演算回数はやや減る

結論

  • carry 耐性（遅延）テクニックは、limb 数の増加や変換処理の追加にもかかわらず、全体の演算性能を実際に大きく向上させる
  • Radix 2^51 トリックは、多倍長整数演算や暗号技術など高い性能が求められる分野で広く活用されている
  • このテクニックは、実際のハードウェア／アルゴリズム性能を最適化する重要なアイデアである

関連記事

1件のコメント

 
GN⁺ 2025-05-31
Hacker Newsの意見

  • 2^51 という数字を見て最初は double 型に整数を格納する話かと思ったが、実際に Integer を double で正確に保持できるのは 2^53-1 までだと気づいた

  • AVX512（そしてある程度は AVX2 でも）は、256 ビット加算をかなり効率的に実装できる環境を提供しており、より多くの数をレジスタに載せられるという利点もある
    直接的な例は以下のコードのように動作する

__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);

スループットまで改善している様子が、実際のコード例として godbolt.org で見られる
この論理を 512 ビット加算まで拡張するのも非常に簡単だ

  • 特に一部の Intel CPU アーキテクチャでは、AVX512 命令を使うだけでプロセッサ全体のクロックが低下し、結果として性能が不安定になったり、かえって全体性能が遅くなったりすることがあると指摘
    関連する参考情報は stackoverflow のリンク で確認できる

  • 「13 ビットではなく 12 ビットを使えないのか？」という疑問について、ここでは最上位ビット（リム）のキャリー処理を無視し、オーバーフロー時に wraparound 形式で動作するようにしている
    その結果、最上位リムには 52 ビットを割り当てており、他のリムより早く空きがなくなる欠点はあるものの、C 言語の符号なし整数加算に近い挙動になる
    それなら最上位リムに 64 ビット、残り 4 リムにそれぞれ 48 ビットを割り当てる方式はどうか、という提案
    こうすると正規化前により多くの演算を蓄積でき、ワード境界の整列などの利点もある
    オーバーフロー処理の特性も同じだ

    • 最上位リムだけに 64 ビットを割り当てる場合、2 つの数のリムを足すとすぐにオーバーフローしてしまう
      たとえば両方とも 2^63 の値なら即座にオーバーフローする
      wraparound 算術なら問題ないが、一般的には無理がある

    • この構成だと、OP のように 5 個ではなく 6 個のワードが必要になる
      命令数も増えることになる

    • 目標は 256 ビット演算を 5 個の 64 ビットレジスタで処理することにある
      つまり各ワードには 256/5 = 51.2 ビットの割り当てが理想となる
      これは 256 ビット限定ならよいが、汎用 big-int ライブラリには最適ではない
      昔は 1 キャリーにちょうど 1 バイトを使いたいという背景があり、バレルシフタがなかった時代なら整列のために 64 ビット中 56 ビットしか使わないことを好んだ
      RISC-V ではハードウェアフラグがないため、この種の議論はさらに重要になる

  • 現代の x86 CPU（例: Intel Broadwell、AMD Ryzen）では、Intel ADX 命令を活用することで、2^51 radix 表現が伝統的に優勢だったケース（例: Curve25519）でも、より高速になる可能性がある

  • 関連する議論資料として

  • 核心的な教訓は、演算同士が独立しているなら、より多くを並列に実行するほうがむしろ速くなりうるということ
    一方で、依存関係のために逐次実行しなければならないなら、演算回数が少なくても遅くなりうる
    この考え方は長整数演算だけでなく、さまざまな分野に応用できる

    • 64 ビットチャンクに分割し、キャリーの有無に応じた 2 通りのケースをあらかじめ並列実行しておき、その後に実際のキャリー結果に従って正しい演算を選ぶ方式を提案
      この方式では加算回数は 2 倍になるが、伝播速度は線形ではなく log(bits) レベルまで速くなる

    • この手法についてうまく理解できていなかった点は、本質的に ripple carry が N 個の値を足すときに N-1 回必要だった処理を 1 回で済ませていることだった
      キャリー処理自体は複雑になるが、加算は並列化できる
      ただし入力値を 5 レジスタ単位に分割する作業自体も並列化できなければ、全体効率としてはあまり意味がない

    • このルールは、数万ノード規模のスーパーコンピュータやクラウドレベルにまで拡張できる
      多くのコアを使えるなら、オーバーヘッドは無視できる程度になる

    • このアイデアには NVidia も関心を示しており、複数の分野で良い結果を出している

  • タイトルに意見を加えてはいけないという HN のガイドラインはあるが、過度に煽るクリック狙いのタイトルは好まない
    「一部の x86 アーキテクチャで carry 依存なしに 64 ビット整数の並列加算を可能にする radix 2^51 トリック」程度に抑えるほうがより正確だと思う

  • この文章を数か月早く読めていれば助かったのに、という惜しさがある
    バッファを任意の基数でエンコード／デコードする過程で、キャリーがバッファ全体へ波及してアルゴリズムが大きく遅くなる経験をした
    最終的には「余白」を残してチャンクに分割し、キャリーを処理したのだが、このトリックと似ている気がする
    実際には一部のビットを無駄にする代わりに、演算量やネットワーク帯域幅を節約する方法を選んだ
    こうしたキャリー処理も後処理としてまとめられるのか気になる
    事実上あらゆる利点を持てる構造になるのでは、と期待している

  • x86_64 環境しか使ってこなかった経験から見ても、RISC-V に carry flag がないことが必ずしも間違った設計ではないと明確に示している

    • この方式以外にも、64 ビットリムを維持したまま、すべて uint64_t 変数で carry-safe な加算を行う方法が説明されている
      以下のような流れになる
    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:

    要点は、加算結果（リム）がすべて 1 でない限り、そのリムのキャリーアウトはキャリーインに依存せず、単に元の値の加算結果だけに依存すること
    一方、値がすべて 1 ならキャリーアウト = キャリーイン
    分岐予測がほとんど不要な構造なら、完全に並列実行できる
    確率的には 2^64 分の 1 でしか遅くならないが、4-wide マシンなどでは大きな利得はない
    8-wide マシンや 8 リム構成では意味のある性能向上がある
    x86_64 には向かないが、Apple M* シリーズのような 8-wide マシンなら活用の可能性がある
    Tenstorrent の 8-wide RISC-V Ascalon プロセッサ、Ventana、Rivos、XiangShan などに将来性が期待される
    SIMD 構造や高速な 1-lane shift（slideup）命令がある構造では効果が最大化される

    • carry-save 加算が常に add-with-carry より優れているわけではない
      2 種類の multi-word addition アルゴリズムは相互に代替不可能で、それぞれ長所と短所がある
      したがって ADC/SBB 命令は ISA に基本搭載されるべきで、レジスタベースのフラグ保存も可能だ
      RISC-V でより深刻な欠点は integer overflow flag がないことだ
      オーバーフロー検出のためにソフトウェア回避が必要な場合、その性能低下は carry ビット回避よりずっと大きい

    • RISC-V に carry flag がないのは、C 言語がバイナリ carry flag を無視したことに由来する
      実際には carry flag の活用頻度はかなり低い

    • 「carry flag がどうせ遅いなら、なぜ risc5 gmp 論争があったのか」と思ったのは自分だけではなかった

  • 「Radix trick」はデータ構造にも応用できる
    Okasaki の『Purely Functional Data Structures』にも興味深い例がある