整数平方根命令を実装したプロセッサはありますか？

 (retrocomputing.stackexchange.com)
1 ポイント 投稿者 GN⁺ 2024-04-08 | 1件のコメント | WhatsAppで共有
  • 論点は一般的な浮動小数点 sqrt ではなく、整数平方根を CPU 命令やハードウェア機能として提供した事例があったかどうかであり、Nintendo DS の divider/square-rooter は近い例だがネイティブ命令ではない
  • Harris RTX 2000 Forth CPU と軍用グレードの RTX 2010 は、多段階の square root 命令を提供した事例として挙げられ、RTX 2000 は setup 1回と step 15回で結果を得る構造だった
  • さらに古い例として ENIAC は 1946年に divider/square-rooter unit により decimal integer accumulator を制御し、毎秒最大40回の除算または3回の平方根演算を実行していた
  • 整数平方根は高速な整数乗算器と十分な精度が必要なため、歴史的な CPU では負担が大きく、ARMv8 の frsqrte / frsqrts のように推定と反復を分けて精度と速度を調整する方式もある
  • Quake 式の inverse square root は現代のハードウェアではもはや一般的な性能優位を持たず、テーブル参照・補間・Halley 系の反復・固定小数点の分割統治などは実装環境によって選択肢が異なる

質問の範囲と Nintendo DS の事例

  • 質問は、整数平方根命令を実際に実装したプロセッサが存在したかを扱っている
  • 浮動小数点の square root 命令は一般的だが、整数専用の square root 命令は質問者が見たことがない、という前提から出発している
  • Nintendo DS にはメモリマップされた integer divider/square rooter があった
    • ARM プロセッサには FPU やハードウェア divider がなく、3D 計算の助けになった
    • ただし ネイティブなプロセッサ命令ではない点が、この質問の重要な手がかりである

Harris RTX 2000 と RTX 2010

  • Harris RTX 2000 Forth CPU は、多段階の square root 命令を提供した事例として言及されている
  • 軍用グレードの姉妹製品である RTX 2010 も同系統の機能を備えている
  • 関連資料として Stack Computers: RTX 2000 がリンクされている
  • RTX2000 Family Programmer’s Reference Manual によれば、この機能は反復型の square root に近く、setup 命令1個と step 命令15個を実行して最終値を得る方式である
  • Ken Lyons の “A Fast Method for Finding an Integer Square Root” も、RTX2000 系のハードウェア実装とプログラミング例を扱う資料として言及されている

ENIAC の divider/square-rooter unit

  • 1946年の ENIAC も整数平方根ハードウェアの事例に該当する
  • 引用された説明によれば、ENIAC は 4個の accumulator を特殊な multiplier unit で制御し、毎秒最大 385回の乗算を実行した
  • 5個の accumulator は特殊な divider/square-rooter unit で制御され、毎秒最大 40回の除算または 3回の平方根演算を処理した
  • ENIAC の accumulator は decimal integer として動作していた

整数平方根の実装が難しい理由

  • ある回答では、Newton-Raphson 反復で 逆平方根を求め、その後に元の値を掛ける方法を、square root 計算の効率的な手法として説明している
  • この方法は「Quake method」として知られており、現代の CPU や GPU では初期推定命令と反復命令として一般化された例がある
  • このアプローチの中核的な制約は、高速な multiplier が必要である点にある
    • 浮動小数点 sqrt には高速な FP multiplier が必要であり、FPU はそれを備えている
    • 整数 sqrt には高速な integer multiplier が必要だが、歴史的にはそのようなハードウェアを持たない CPU がほとんどだったという説明である
    • 十分な精度を得るには、入力幅の2倍の幅を持つ高速 multiplier が必要だという条件も付く
  • 精度要件は常に同じとは限らないため、frsqrte と frsqrts のように推定と反復を分ければ、望む 速度・精度のトレードオフに合わせて反復回数を調整できる

Quake 手法と現代の sqrt 実装をめぐる議論

  • 別の回答では、Quake trick が最も効率的だという主張はかなり前から正しくなく、特定のハードウェアで低品質の float 結果を得る場合にのみ当てはまると反論している
  • 現代のチップではネイティブの sqrt 命令のほうがはるかに高速で、しばしば 数クロックサイクル程度だと説明されている
  • より高速な方法として、不均等間隔の値テーブルを保存し、2つの値を高速に取り出して補間し、base-2 exponent を shift し、必要なら Newton-Raphson より優れた反復を1回適用する方式が提案されている
  • Halley 系や各種反復法は Newton-Raphson より速く収束しうるが、実際の速度は各演算のコストに左右される
  • 整数専用の範囲、たとえば 2^32 であれば、同じ考え方を 固定小数点で適用できる
    • ハードウェア向けの単純な方法として divide and conquer が提示されている
    • 各 8ビットを 256個の固定小数点値テーブルにマップし、並列参照したうえで、3回の乗算のうち2回を並列実行して 32ビット値を得て truncate できる
  • sqrt 最適化の研究は現在も続いており、INRIA HAL 資料 が例として挙げられている

関連記事

1件のコメント

 
GN⁺ 2024-04-08
Hacker Newsのコメント

  • AArch64 NEON には URSQRTE 命令があり、元の質問に思ったより近い
    32ビット値を小数部 32 ビットの固定小数点整数とみなすと、表現範囲は 0 から 1-ε まで等間隔で、ε=2^-32 になる
    URSQRTE は近似 逆平方根 を計算したあと半分にし、結果を 0 から 1-ε の範囲にクランプする
    固定小数点整数は厳密な整数ではなく、近似逆平方根も平方根そのものではないが、かなり近いところまでは行ける
    関連する FRSQRTE ははるかに一般的な命令で、32 ビット浮動小数点に対する近似逆平方根を提供する

    • そういう複雑な命令が、より単純な命令へ簡単に分解できるのに AArch64 に入るほど得になる処理とは何なのか気になる

  • 単一クロックサイクルで可能かというと、とても大きな ルックアップテーブル があれば可能
    クロックサイクル内で直列の論理ゲートをどれだけ実行できるか次第では、サイズを縮められるかもしれない
    たとえば 10000 の二進平方根は 100 の平方根とかなり似ていて、0 の数だけが違うと見なせる

    • 浮動小数点の 逆平方根推定 命令(frsqrte)は普通そうしたテーブル参照で実装され、仮数の一部のビットと指数の最下位ビットでインデックスされる
      精度はだいたい bf16(ARM, RISC-V) や fp16(x86) に近い水準で、より高い精度が必要ならその後に Newton-Raphson 反復を数回行う形になる
    • 入力のビット数が n のとき、整数平方根 はシフトと加算だけで n/2 回の反復で計算できる
      各段階で、結果 n_old に新しいビットを立てるべきかを n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2)) で計算する
      そのあと元の被演算子と比較し、超えないなら 1) 結果にそのビットを立て、2) n2_old を n2_new に更新する
      適切なマイクロコード命令セットと ALU があれば n/2、あるいは n クロックサイクルで可能で、さらに最適化すれば n を被演算子で最も左に立っているビットのインデックスまで減らせるかもしれない
    • 間抜けな質問かもしれないけれど、大きなテーブル参照が本当に 1 クロックサイクルで終わることはあるのか？
      大きなルックアップテーブルならメモリから取ってこないといけないはずで、そうするとキャッシュや メモリ階層 のレイテンシが出るのではと思う
    • そう言うと、この世のどんなアルゴリズムでも 1クロックサイクル で実行できそうに聞こえる
    • 整数平方根は思ったほど悪くなく、大小比較用のルックアップテーブルには N^0.5 個の項目 だけ保存すればよい
      すべての答え N について N^2 を保存する形だ
      16 ビット整数なら現実的で、32 ビットもひょっとすると可能だが、64 ビットでは無理

  • 「プロセッサ」の定義を電気機械式装置まで広げるなら、Friden SRQ はモーター以外に電子部品を 1 つも使わず、加算とシフトだけで平方根を計算できた
    小数点位置を手動で合わせる必要があったので、技術的には整数演算だったとも言える
    動画: https://youtu.be/o44a1ao5h8w

  • 1 + 3 + 5 + ... + 2k + 1 の数列を使えば、どんな整数の 整数平方根 も求められるのでは？
    基本的には、その数列の中で自分の数以下の最も近い項の k を見つけるやり方だ

    • アイデアを説明してもらえる？
      定義上アルゴリズムとしては正しいが、素朴に実装すると 32 ビット数でも非常に遅い
      この程度なら 二分探索 したほうがずっと速い
    • より良い方法は、(x+y)^2=x^2+2xy+y^2 の展開と、どの基数でも 2n 桁の数の平方根は最大で n 桁だという観察を組み合わせることかもしれない
      紙とペンで手計算するときの一般的な平方根の求め方と同じだ
      これを 8 ビット単位で処理すれば、8ビット数の平方根 に対するルックアップテーブルだけあればよい
    • その数列をひたすら繰り返すという意味なら、入力ビット長に対して 指数時間 かかる
    • これは典型的な 困るほど並列化しやすい 作業の 1 つだ

  • 下のほうの回答にあったこの部分が面白かった:

    My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
    賢いコードを書くと、あとでそのコードがどう動くのか思い出せなくなる可能性が高い、という良い reminder だ

  • 少し下まで読まないといけないが、答えが ENIAC なのは本当に笑える

    • 多くの人は、自分が学校に入る前のものはすべて原始的で、かろうじて動いていたのだと思いがちだ :)
      少し読めばまったく逆だと分かる
      今日の賢いアイデアの大半は、すでに 1940〜60 年代のコンピュータで使われていて、新しい半導体チップで再利用されている
      パイプライン化、アウトオブオーダー実行、マルチコアなどがそうだ
      昔のハードウェアは少し「無骨」だったかもしれないが、アーキテクチャには非常に巧妙な手法が使われていた

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    Log2(x) を 先行 0 カウント に置き換えると、本当に粗い近似値が得られる
    Log(2) をもっと上手く近似すれば、答えにさらに近づける

  • 最も近い整数まで正確な答えではなく、非常に粗い近似値でよいなら、最上位の 1 ビット位置の半分だけ 右シフト すればよい
    ほぼすべてのプロセッサにはシフト命令があり、FLO(Find Leading One) や FFS(Find First Set) のような命令も、ないほうが珍しいくらい広くあるように思える
    用途によっては、こうした非常に粗い近似でも正確な答えと同じくらい有用なことがある
    たとえば後続の Newton-Raphson 反復 のために適当な初期値だけが必要な場合だ
    もちろん右シフトのトリックは、より正確な平方根計算の初期値としても悪くない :P

    • ここで DOOM の話になるのか？
      今ではかなり有名なインターネット小話で、Carmack と魔法のような 32 ビット数が登場する
    • 面白いことに、FFS とその一般化である FNS は CUDA にある: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      個人的に好きなもう 1 つの CUDA ハードウェア組み込み関数は log2 だ

  • 記憶が正しければ、ほとんど、あるいはすべての 固定小数点 DSP には平方根命令か補助命令がある

  • 6502 ファンには半分関係があって面白いかもしれない 平方根アルゴリズム の総当たり分析: https://github.com/TobyLobster/sqrt_test