🔢 mathematics

Performance evaluation of branch-free fused multiply-add algorithms for multi-component-type multiple-precision floating-point arithmetic

本論文は、ダブルワード、トリプルワード、およびクアドラプルワードの多倍長演算に向けた新しい分岐フリーの融合積和アルゴリズムを提案およびベンチマークし、それらが条件分岐を排除することによって既存の手法よりもさらなる性能向上を実現することを実証する。

原著者： Tomonori Kouya

公開日 2026-07-14

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Tomonori Kouya

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、標準的な市販のレゴブロックだけを使って、超精密な計算機を作ろうとしていると想像してください。これらのブロックは、あなたのコンピュータにおける通常の浮動小数点数です。通常、これらのブロックを積み重ねて「ダブルワード（2個のブロック）」、「トリプルワード（3個）」、「クアドラプルワード（4個）」の数字を作る際、パーツのサイズが適切かどうかを常に確認しなければなりません。もしパーツが大きすぎたり小さすぎたりすると、作業を中断し、止まって、スタックを組み直す必要があります。コンピュータチップの世界では、これらの「一時停止」は**分岐（ブランチ）**と呼ばれます。

これらのスタックを一度に100万個作る（現代のグラフィックスカードや強力なプロセッサのように）とき、これらの一時停止は悪夢となります。それは、すべての車が異なる標識を確認するために停止しなければならない交通渋滞のようなものです。ある車は左へ、ある車は右へと進むため、列全体が停滞します。これは「レーン分岐（レーン・ダイバージェンス）」と呼ばれ、パフォーマンスを著しく低下させます。

大きな発見：「止まらない」高速道路
Tomonori Kouyaの論文は、決して標識を確認するために止まることのない、新しいスタックの構築方法を紹介しています。それは「分岐フリー（branch-free）」のアルゴリズムです。パーツが十分に大きいかどうかを問い、「答えを待つ」代わりに、この新しい手法は、どのようなパーツであっても完璧に機能する、巧妙に計画されたルートを使用します。

この論文は、超スマートなロボット数学者（FPANVerifierと呼ばれるSMTソルバー）を用いて、この新しいルートがすべての標準的なフォーマットにおいて安全かつ正確であることを証明しています。主な知見は、これらの「停止して確認する」ためのポーズを取り除くことで、コンピュータがはるかに速く計算できるということです。

魔法のトリック：動きの融合
この論文は、**融合積和演算（Fused Multiply-Add: FMA）**と呼ばれる特定の動きに焦点を当てています。想像してみてください、2つの数を掛け合わせ、そこに3つ目の数を足す必要があります。通常、これは2つのステップで行われます。

掛け算（そして、おそらく結果を修正するために一時停止する）。
足し算（そして、おそらく再び一時停止する）。

著者は、これら両方を一つの滑らかな動きで行う「融合（Fused）」バージョンを提案しています。まるで、ナイフを投げると同時にキャッチする忍者のようなものです。

ダブルワード（2個のブロック）の場合： 旧来の方法は29ステップかかりましたが、新しい方法ではわずか17ステップです。
トリプルワード（3個のブロック）の場合： 旧来の方法は96ステップかかりましたが、新しい方法では66ステップです。
クアドラプルワード（4個のブロック）の場合： 旧来の方法は209ステップかかりましたが、新しい方法では146ステップです。

また、論文では他の研究者によって提案された「ショートカット」手法（6ステップ法）についても議論しています。決定的なことに、このショートカットは一般的には有効ではありません。 これは、数値がすでに特定の配置（具体的には、足される数が積の少なくとも2倍である場合）になっている場合にのみ機能する、高速なツールです。もし、数値が整列していることを保証できない除算や平方根のような一般的な数学の問題にこのショートカットを使おうとすると、精度が著しく低下します。しかし、著者の新しい手法は、特別な配置を必要とせず、あらゆる数値に対して機能するため、一般的な高精度数学のための真の「ドロップイン（そのまま置き換え可能な）」リプレースメントとなります。

どれほど確かなのか？
著者たちは非常に自信を持っていますが、それは単なる推測ではなく、確かな証拠に基づいています。

機械検証済み： 彼らは単にコードを書いて期待したわけではありません。エラーが極めて小さいこと（具体的には、 $34u^2$ 、 $184u^3$ 、 $812u^4$ といった式で抑えられること。ここで $u$ は単一の数の微小な丸め誤差）を数学的に証明するために、コンピュータプログラムを使用しました。
あらゆる場所でテスト済み： 彼らは、これら新しいアルゴリズムを、2つの全く異なるスーパーコンピュータ、**Armベースのチップ（GB10）とIntelベースのチップ（H100）**で実行しました。
結果：
- Armチップ上では、除算および平方根の計算において、新しい手法は1.5倍から2.1倍速くなりました。
- Intelチップ上では、除算および平方根において、1.2倍から1.6倍速くなりました。
- 行列乗算（GEMM）のような大規模な数学的タスクでは、トリプルワードの場合、Armチップ上で最大2.0倍の高速化という劇的な結果が得られました。

「正確な」代替案
論文では、このトリックのさらに精密な「完璧な」バージョンであるExact FMAについても言及しています。このバージョンはさらに正確ですが、重い代償を伴います。それは、提案された新しい手法よりも6倍から11倍遅いということです。著者らは、絶対的な、100%の精度が必要であり、速度を気にしない場合にのみ、この「完璧な」バージョンを使用することを提案しています。それ以外のほとんどのケースでは、「分岐フリー」の手法が勝者となります。

「古い」方法については？
この論文は、以前のバージョンの研究における間違いも訂正しています。以前、著者らは自分たちの新しい手法を、非常に遅く非効率な「完全に蒸留された（fully distilled）」旧来の方法と比較していました。彼らは、それが公平な戦いではないと気づきました。新しい手法を、実際の標準的な「分岐フリー」手法（これはすでにかなり高速です）と比較したとき、新しい手法は依然として勝利しましたが、そのスピードアップはより控えめなもの（約1.3倍から1.7倍の高速化）でした。これは依然として大きな勝利ですが、より現実的な結果です。

結論
この論文は、高精度な数学における「停止して確認する」ためのポーズを取り除くことで、精度を損なうことなく、コンピュータを大幅に高速化できることを示しています。それは、あらゆる交差点で止まらなければならない車から、交差点を飛び越えていくことができる車へとアップグレードするようなものです。著者たちは、これが機能することを証明し、実際のハードウェアでテストし、次世代の超高速計算機の準備ができていることを示しました。

技術要約：マルチコンポーネント型多倍長浮動小数点演算のための、分岐フリーな融合積和演算（FMA）アルゴリズムの性能評価

1. 問題提起

マルチコンポーネント多倍長演算（例：Double-Word/DW、Triple-Word/TW、Quadruple-Word/QW）は、標準的なbinary64（またはbinary32）のコンポーネントをまとめ、誤差なし変換（Error-Free Transformations: EFTs）を介してキャリーを正確に処理することで、高い性能を実現している。しかし、これらのアルゴリズムにおける繰り上げ（renormalization）段階は、通常、中間値の大きさに依存するif分岐に依存している。これらの分岐は、SIMDやGPUの実装において、レーンまたはワープのダイバージェンス（分岐の不一致）を引き起こし、大幅な性能低下を招く。

ZhangとAikenは、以前にDW/TW/QWの加算および乗算のための分岐フリーなアルゴリズムを提案したが、これらの個別の分岐フリー演算を合成する方法は最適とは言えない。具体的には、分岐フリーの乗算と分岐フリーの加算を逐次的に合成して、融合積和（FMA）演算 $z \leftarrow x \cdot y + c$ を実行する場合、演算回数（例：DWで29回、TWで96回、QWで209回）が多くなり、冗長な繰り上げステップが発生する。

2. 手法

本論文では、DW、TW、QW演算（およびそれらの単精度ベース・バリアントであるDS、TS、QS）のための、新しい分岐フリーな融合積和（FMA）アルゴリズムを提案する。コアとなる手法は以下の通りである：

アルゴリズム構造： 提案するFMAは、乗算と加算を個別に合成するのではなく、単一の融合ステージとして $z \leftarrow x \cdot y + c$ $z \leftarrow x \cdot y + c$ を計算する。プロセスは以下を含む：
1. 積の展開（Product Expansion）： TwoProd を用いてコンポーネントの積を分解する。
2. 重みごとの累積（Weight-wise Accumulation）： TwoSum の連鎖を用いて、同じ2のべき乗位置に到達する項を集約する。
3. 繰り上げ（Renormalization）： 結果を $K$ 個の重複しないコンポーネントへと再形成する。
ゲート選択と検証： 設計上の重要な原則は、機械的に検証可能な前提条件に基づく繰り上げゲートの選択である。本アルゴリズムでは、すべての精度 $p$ において、SMTソルバである z3 を用いた FPANVerifier ツールにより、前提条件 $\text{exp}(a) \ge \text{exp}(b)$ が機械的に証明可能である場合にのみ、FastTwoSum（3 flops）を使用する。この前提条件が証明できない場合には、正確性を保証するために TwoSum（6 flops）を使用する。
可換性（Commutativity）： オペランドの交換（ $x \leftrightarrow y$ ）の下でのビット単位の一致を保証するため、対角成分の和を再結合し、転置されたペア（例： $P_{ij}$ と $P_{ji}$ ）が最初に処理されるようにする。これは演算回数を増やすことなく達成される。
厳密なバリアント（Exact Variant）： リファレンスとして「Exact FMA（厳密なFMA）」という蒸留バリアントも実装されている。これは完全な誤差なし展開を実行した後、結果相対誤差境界を達成するために複数の TwoSum スイープを実行するが、計算コストは大幅に高くなる。

3. 主な貢献

3.1 最小限の分岐フリーFMA構成

本論文は、以下の演算回数（融合FMA命令を1とカウント）を持つ、最小限かつ機械検証された分岐フリーFMAアルゴリズムを提示する：

DW (K=2): 17 flops（分岐フリーの乗算＋加算の合成では29 flops）。
TW (K=3): 66 flops（合成では96 flops）。
QW (K=4): 146 flops（合成では209 flops）。

これらのカウントは、すべてのFastTwoSumの前提条件が機械的に検証されている最小限の構成を表している。

3.2 機械検証された誤差境界

著者らは FPANVerifier を使用して、すべての精度において $(|xy| + |c|)$ に対する誤差境界を証明している：

DW: $34 u^2 (|xy| + |c|)$
TW: $184 u^3 (|xy| + |c|)$
QW: $812 u^4 (|xy| + |c|)$
すべての FastTwoSum の前提条件の妥当性と、証明されたバリアントと、FastTwoSum を（証明に関わらず）末尾に配置したナイーブなバリアントとの間のビット単位の一致が確認されている。

3.3 可換性

提案されたアルゴリズムは、6つの全タイプ（DD/TD/QD/DS/TS/QS）において $x$ と $y$ に関してビット単位で可換である。これは、単純な加算の結合順序を対称化することにより、演算数を増やすことなく $fma(x, y, c) \equiv fma(y, x, c)$ を実現している。

3.4 除算および平方根のための特化バリアント

本論文では、除算および平方根アルゴリズムにおける中間残差が、標準的なFMAの証明に必要な非重複の仮定を満たさない可能性があることを指摘している。そのため、「安全な」バリアントがこれらの文脈のために提案されており（DW 20 / TW 69 / QW 149 flops）、証明されていない FastTwoSum ゲートを TwoSum に格下げすることで、あらゆる使用文脈に対して正確性を保証している。

4. 実験結果

アルゴリズムは以下の2つのプラットフォームで評価された：

Arm: NVIDIA GB10 (Grace-Blackwell, Cortex-X925 CPU, Blackwell GPU)。
x86: H100 ノード (Intel Xeon Gold 6526Y CPU, H100 GPU)。
実装: スカラー、AVX2、AVX-512、NEON、SVE2、およびCUDA。

4.1 線形代数カーネル (AXPY, GEMV, GEMM)

スピードアップ： 提案されたFMAは、計算量に制約のある（compute-bound）シナリオにおいて、分岐フリーのベースライン（BF）を一貫して上回る。
- AVX2 (x86): GEMMにおいて、 $\times 1.49$ (DD)、 $\times 1.32$ (TD)、 $\times 1.47$ (QD) のスピードアップ。
- NEON (Arm): GEMMにおいて、 $\times 1.40$ (DD)、 $\times 1.42$ (TD)、 $\times 1.47$ (QD) のスピードアップ。
- SVE2: 同等のレーン幅においてNEONと同等の性能を示し、QD GEMMではBFに対して $\times 1.62$ のスピードアップに達した。
- GPU (GB10): 計算量に制約のある倍精度型において、スピードアップは理論的なFLOP比に一致する（DDで $\times 1.71$ 、TDで $\times 1.46$ 、QDで $\times 1.40$ ）。帯域幅に制約のあるワークロード（単精度またはH100）では、スピードアップは $\times 1.00$ に近い。
精度： 提案されたFMAは、既存の分岐フリー手法（Q/BF）と同等のワーキング精度を維持している。キャンセルが発生するシナリオにおいても、誤差挙動はベースラインと数値的に同一である。Exact FMAはより優れた結果相対精度を提供するが、2.5～5.0倍の低速化を招く。

4.2 除算および平方根

除算： 提案されたFMAは、特に高精度において長除算を大幅に加速させる。
- NEON/SVE2: $\times 1.54$ から $\times 2.11$ のスピードアップ（QD除算は $\times 2.11$ に達し、2つの連続する正規化チェーンを1つに折り畳むことにより、演算数の比率である1.51を超えている）。
- GB10 (計算限定): $\times 1.25$ から $\times 1.61$ のスピードアップ。
平方根： 提案されたFMAは、ベースラインと比較して精度の損失なしに $\times 1.51$ から $\times 1.61$ のスピードアップを達成する。これは、ニュートン反復が丸め単位よりも十分に低いレベルまで収束するため、最終的な誤差がすべての手法に共通する最後の乗算によって支配されるためである。

4.3 単精度ベース (DS/TS/QS)

アルゴリズムは単精度コンポーネントにも正常に拡張され、ワーキング精度を維持しながら、BFベースラインに対して $\times 1.37$ から $\times 1.83$ のスピードアップを達成した。

5. 意義と主張

本論文は、提案された分岐フリーFMAが、既存の分岐フリー乗算と加算の2つのステージを単一の演算へと融合させた、最小限かつ機械検証された構成であることを主張している。

性能： 演算回数の削減と依存関係の連鎖の短縮（特にTW/QWの高精度において顕著）により、実世界でのスピードアップ（除算での最大 $\times 2.11$ 、GEMMでの $\times 1.71$ ）を提供する。
正確性： アルゴリズムは厳密に検証されている。誤差境界と FastTwoSum の前提条件はすべての精度において機械的に証明されており、スカラー、SIMD、およびGPU実装間のビット単位の一致が20万回以上の試行を通じて確認されている。
汎用性： このアプローチは線形代数に限定されない。MAC演算に大きく依存する除算および平方根アルゴリズムを効果的に加速する。
可換性： 一部の従来の分岐フリーアプローチとは異なり、提案されたFMAはビット単位の可換性を保持しており、これは並列リダクションにおける再現性に不可欠な特性である。

著者らは、本研究を、精度や証明可能性を損なうことなく、個別の分岐フリー演算を構成する代わりの実用的な置き換えとして位置づけており、マルチコンポーネント演算ライブラリへの「ドロップイン」的な加速を提供すると述べている。今後の課題として、機械検証性を維持しつつ、演算回数をさらに削減できる可能性のある代替的な繰り上げ構造（例：Priestスタイル）の探索が示唆されている。