アカウント名:
パスワード:
と言うのを使ってるとGoogle Cloudの声明にはありますね。https://en.wikipedia.org/wiki/Chudnovsky_algorithm [wikipedia.org]
たしかにこの方法なら、一部てか最後のいくつかの演算を除いて整数だけで演算が出来ます（勿論、ビット数は法外にでかくなりますが）し、SIMDやマルチスレッドを使った並列演算も捗りそう。しかしなんでOpenCLとかCUDAとか使わなかったんだろうか…と思ったけど、結局はクラウドサーバの宣伝だったんですね(^_^;
別に宣伝だからGPU使わなかったわけではなく、CPUの方が早いからGPU使わないだけです。
今現在一番早い円周率の計算は、挙げておられるchudnovskyの公式を利用する物です。その公式を利用した円周率計算ソフトで有名なのが今回Googleも使用したy-cruncher。このアルゴリズムでは計算途中に一時データとして比較的大きな量の低レイテンシメモリを必要とするので、演算コアあたりの内部キャッシュ量が少ないGPUには向いてない。
> このアルゴリズムでは計算途中に一時データとして比較的大きな量の低レイテンシメモリを必要とするので、演算コアあたりの内部キャッシュ量が少ないGPUには向いてない。
確かにGPUだと、キャッシュも小さめですが、そもそもローカルメモリとして比較的速くアクセスできる領域が（１演算ユニット辺り）せいぜい64KB、グローバルなメモリでもせいぜい16GBとかですね。途中の演算（加減やせいぜい掛け算で済むブロックを想定しています）ですら、想定される桁数が１０進換算で「メガ桁」とか「ギガ桁」、下手すると「テラ桁」になるかもしれないことを考えると、GPU側で並列演算をしようにも桁数が大きすぎて、メリットがないというのも納得がいきます。
# となると、１モジュール辺り、数テラバイトとか数十テラバイトの直接アクセスできる（インターコネクト的な部分を超えない）メモリを抱えてるGPUのようなベクトル演算プロセッサがあれば…
GPUみたいなアーキテクチャ向けの最強アルゴリズムはこれだ、みたいな研究もあるんでしょうね。今のところ使うメリットが無いけど、もしCPUとGPUの差がほげほげ以上に開いたらそっちの時代が来るぜ、とかそういう。
歴史的には大体こんな感じ
黎明期 マチンやシュテルマーのような級数展開の公式を、固定小数点で筆算のように計算 n^2の計算量なので、桁数が倍になると4倍の時間が必要
発展期 FFTを使って多倍長計算を n log n の計算量で行う方法が発明される 収束の速いボールドウィンとかベイリーの公式が好まれる 1990年代のスパコンで計算競争してた時代
21世紀 バイナリースプリッティングによって、収束の遅い公式を高速に計算する方法が発明される 最終結果を出す直前まで分数表現の整数演算で処理されるようになると共に、以前の結果を元に計算を追加する事も可能に チュドノフスキーの公式がよく使われるようになるが、原理的にはマチンとかでも可能
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
海軍に入るくらいなら海賊になった方がいい -- Steven Paul Jobs
Chudnovsky法 (スコア:2)
と言うのを使ってるとGoogle Cloudの声明にはありますね。
https://en.wikipedia.org/wiki/Chudnovsky_algorithm [wikipedia.org]
たしかにこの方法なら、一部てか最後のいくつかの演算を除いて整数だけで演算が出来ます（勿論、ビット数は法外にでかくなりますが）し、SIMDやマルチスレッドを使った並列演算も捗りそう。
しかしなんでOpenCLとかCUDAとか使わなかったんだろうか…と思ったけど、結局はクラウドサーバの宣伝だったんですね(^_^;
Re:Chudnovsky法 (スコア:5, 参考になる)
別に宣伝だからGPU使わなかったわけではなく、CPUの方が早いからGPU使わないだけです。
今現在一番早い円周率の計算は、挙げておられるchudnovskyの公式を利用する物です。
その公式を利用した円周率計算ソフトで有名なのが今回Googleも使用したy-cruncher。
このアルゴリズムでは計算途中に一時データとして比較的大きな量の低レイテンシメモリを必要とするので、演算コアあたりの内部キャッシュ量が少ないGPUには向いてない。
Re:Chudnovsky法 (スコア:3, 興味深い)
> このアルゴリズムでは計算途中に一時データとして比較的大きな量の低レイテンシメモリを必要とするので、演算コアあたりの内部キャッシュ量が少ないGPUには向いてない。
確かにGPUだと、キャッシュも小さめですが、そもそもローカルメモリとして比較的速くアクセスできる領域が（１演算ユニット辺り）せいぜい64KB、グローバルなメモリでもせいぜい16GBとかですね。
途中の演算（加減やせいぜい掛け算で済むブロックを想定しています）ですら、想定される桁数が１０進換算で「メガ桁」とか「ギガ桁」、下手すると「テラ桁」になるかもしれないことを考えると、GPU側で並列演算をしようにも桁数が大きすぎて、メリットがないというのも納得がいきます。
# となると、１モジュール辺り、数テラバイトとか数十テラバイトの直接アクセスできる（インターコネクト的な部分を超えない）メモリを抱えてるGPUのようなベクトル演算プロセッサがあれば…
Re: (スコア:0)
GPUみたいなアーキテクチャ向けの最強アルゴリズムはこれだ、みたいな研究もあるんでしょうね。今のところ使うメリットが無いけど、もしCPUとGPUの差がほげほげ以上に開いたらそっちの時代が来るぜ、とかそういう。
Re:Chudnovsky法 (スコア:2, 興味深い)
歴史的には大体こんな感じ
黎明期
マチンやシュテルマーのような級数展開の公式を、固定小数点で筆算のように計算
n^2の計算量なので、桁数が倍になると4倍の時間が必要
発展期
FFTを使って多倍長計算を n log n の計算量で行う方法が発明される
収束の速いボールドウィンとかベイリーの公式が好まれる
1990年代のスパコンで計算競争してた時代
21世紀
バイナリースプリッティングによって、収束の遅い公式を高速に計算する方法が発明される
最終結果を出す直前まで分数表現の整数演算で処理されるようになると共に、以前の結果を元に計算を追加する事も可能に
チュドノフスキーの公式がよく使われるようになるが、原理的にはマチンとかでも可能