2019年3月14日、Googleが円周率を31兆桁計算したと発表しました。このニュースを聞いて僕は「GoogleがノードまたぎFFTをやったのか！」と大変驚き、「円周率の計算には高度な技術が必要」みたいなことをつぶやきました。しかしその後、実際にはシングルノードで動作する円周率計算プログラム「y-cruncher」を無改造で使っていることを知り、「高度な技術が必要だとつぶやいたが、それは撤回」とつぶやきました。円周率の計算そのもののプログラムを開発していなかったとは言え、これだけマッシブにディスクアクセスのある計算を長時間安定実行するのは難しく、その意味においてこの挑戦は非自明なものだったのですが、まるでその運用技術のことまで否定したかのような書き方になってしまい、さらにそれが実際に計算を実行された方の目にもとまったようで、大変申し訳なく思っています。
このエントリでは、なぜ僕が「GoogleがノードまたぎFFT!?」と驚いたか、そんな話を書いてみたいと思います。
円周率の計算には、いくつかの公式があります。よく知られているのはarctanの公式で、奇数の逆数を交互に足したり引いたりしていくとπ/4になる奴でしょう。これは収束が遅いので実際の計算には使われません。最近はy-cruncherというアプリケーションで採用されていることもあり、Chudnovskyの公式がよくつかわれているようです。さて、円周率の計算は、基本的には「たくさん計算するほど円周率に近づいていく」ような級数を計算します。その計算の過程で必要になるのが、馬鹿でかい桁の数同士の四則演算、特に乗算です。普通に筆算の要領でN桁の数の乗算をやると、O(N^2)の計算がかかってしまいます。しかし、高速フーリエ変換(FFT)の要領でうまいことやるとO(N log N)に落とすことができます。なので、円周率を計算するには、多倍長演算が必要になり、多倍長演算を実行するにはFFTが必要になります。
このFFTですが、数値計算で頻出します。非圧縮流体の計算や、乱流の計算、電場の解析など、数値計算ではフーリエ変換すると劇的に計算量が落ちる問題が結構あるため、フーリエ変換は極めて重要です。さて、フーリエ変換はとても便利なのですが、スパコンで実行しようとすると困ることがあります。それは、分散メモリ並列での実行が難しいことです。
高速フーリエ変換は、バタフライ演算と呼ばれるパターンで計算します。これを並列化しようとすると、まずは隣り合ったノードが通信、次は一つ飛ばして通信・・・と、あるノードからすべてのノードに通信が発生します。分散メモリ並列マシンにおけるFFTを「グローバルFFT」と呼んだりしますが、グローバルFFTを高い効率で実行するには、高い「バイセクションバンド幅が要求されます。「バイセクションバンド幅」とは、要するに「スパコンを一番『いじわるに』二つのグループに分割した時、その二つのグループの間の総通信性能」のことです。
「全てのノードから全てのノードに、まったく干渉なく自由に通信できる」ようなネットワークを、FATツリーと言います。FATツリーはネットワークとしてはとても素晴らしいのですが、その分、とても高くつきます。普段、スパコン全体にわたる通信をがっつりやる機会は少ないため、そのためだけに、そこにお金をかけるのは難しいです。
すると、例えば「近くは太いけど、遠くは細くなる」もしくは、「グリッド上に通信路を用意しているので、みんなが遠くと通信しようとすると幹線道路で渋滞が起きてしまう」なんてことがおきます。このようなマシンで効率的なグローバルFFTを実行するのは容易ではありません。
そんなわけで、スパコン上における円周率の計算とは、ほぼそのままグローバルFFTの歴史と言ってもよいものです(ちょっと過言かも)。
また、円周率を何兆桁も計算すると、当然のことながらそのすべてをメモリに載せることはできません。すると、適宜データをストレージに吐いたり読み込み戻したりしながら計算を実行する必要があります。多数のノードのメモリに保存されたデータを、工夫しないで一気にストレージに書きに行くとそこで詰まってしまい、全体として全く性能が出せません。したがって、スパコンで円周率を計算するには、並列IOも工夫する必要があります。
スパコン上での円周率の計算は、ノードまたぎFFTとIOという、大きな二つの困難がありました。それに対して、PCで長時間計算する、というアプローチがとられるようになりました。少なくとも、1台のPCで計算すればノードまたぎFFTをやらなくてもよく、また、(スパコンを使う場合に比べれば)計算が遅くなるためIOに対する要求性能も下がります。スパコンを使った円周率の計算は、2002年の金田先生の1兆桁、2009年の高橋先生の2兆桁を最後に記録更新されておらず、後はすべて一つのPCで長時間計算して実行されたものです。
ただし、一つのPCで計算すると通信部分は楽になるとは言え、大規模なストレージが必要になるのは変わらず、2013年の12兆桁のチャレンジでは、記録達成者がとにかくストレージが大変だったとぼやいています。そのあたりの苦労はあるにせよ、トータルで見れば、スパコンを使うよりも圧倒的に低コストで計算できることに代わりはありません。
スパコンを使った円周率の記録の更新は2009年が最後です。それから10年も経ったため、今は「スパコンで円周率」というイメージはないかもしれません。昔は「円周率と言えばスパコン」だったのですが。
高橋先生がT2K-Tsukubaで円周率2兆桁を達成した同じ年に、一台のPCで長時間プログラムを走らせることで記録がわずかに更新されました。翌年、PCによる計算でさらに記録は倍に伸び、「PCで計算できるものを、なぜこれまでわざわざスパコンで計算してたんだ」みたいなことを(当時は)言う人もいました。
一般に、時間とストレージをかけていいなら、スパコンで行う計算のほとんどは、PCやPCクラスタでもできます。また、時間はかかるものの、トータルのコストはスパコンよりもPCの方が安くなります。ただ、それで「スパコン要らないじゃん」と思うのは、ちょっと乱暴かな、と思います。
例えば東京から名古屋に行くのに、鈍行で行こうが新幹線使おうが、距離は同じです。だからといって「新幹線いらないじゃん」とはなりません。多くのサービスには「特急サービス」があり、時短の代わりに高いコストを要求します。結果が同じでも、早くその結果が得られることには価値があるからです。典型的な例は天気予報です。たとえコストが1/10になろうとも、明日の天気が一週間後にわかるようでは意味がないわけです。
スパコンを使うには並列化が必要になります。世の中には、本質的に並列化が難しいものと、さほど難しくないものがありますが、FFTは並列化が難しいものの一つです。FFTが多くの数値計算のコア技術である以上、今後もグローバルFFTの研究は進められると思います。そして円周率の並列計算は、そのベンチマークの一つになっています。
話をもとにもどしてGoogleの話です。上記のような頭があったため、「Googleが円周率の記録を大幅に更新した」と聞いたときに、脊髄反射で「GoogleがノードまたぎFFTの効果的なアルゴリズム開発したのか！」と思ってしまいました。それはかなり困難なことですが、「Googleならやりかねない」と思ったのです。実際にGoogleの公式発表を読み、y-cruncherを使ったことも見ていたにも関わらず、記録達成者が、FFTで有名な高橋先生ゆかりの方だと聞いて、完全に「ノードまたぎFFT」をやったものだと思い込んでしまいました。
FFTは数値計算では極めて重要なコア技術ですが、「Googleが必要とするコア技術か？」と言われると、少なくとも僕に見えている情報から考えるに、そうは思えません。だからこそ、「今は直接必要ない技術に投資したのか」と驚いてしまったのです。今思うと、並列実行したにしては、時間がかかりすぎていることにすぐ気づくべきでした。
そう驚いてつぶやいて、「素のy-cruncherを使っており、ノードまたぎFFTをやっていない」と聞いて驚いてまたつぶやいて、不適切な表現になったことは冒頭に述べた通りです。
繰り返しになりますが、これだけ長時間、相当馬鹿でかいディスクに対してずっと読み書きをするというのはかなりのチャレンジであり、それを見事完遂したというのは、当初僕が想定したのとは異なる分野ですが、やはり高い技術と言わざるを得ません。
かつて円周率は、スパコンの性能のベンチマークのような存在でした。少なくともそう思っている人がいました(僕とか)。しかし、2009年の高橋先生の記録を最後に、スパコンによる円周率の並列計算による記録更新は途絶えています。計算能力の向上に比べて、通信やIOまわりの能力の向上はゆるやかで、その性能差はどんどん開いており、その分だけ「円周率の並列計算」は相対的に苦しくなっているように思います。今回の偉業は偉業として、でも、いつか近いうちに並列計算による円周率の記録更新がなされて欲しいものです。Googleにも円周率ガチ勢が何名かいるのを知っていますし、他のスパコンセンターでも、だれかが虎視眈々と記録更新を狙っているかもしれません。
たかが円周率、されど円周率。
次はどんな形で記録が更新されるか、楽しみにしています。