メルセンヌ素数で”FLOPS vs. Memory Bandwidth”を体験する


 50番目のメルセンヌ素数が見つかった,つーか,素数であることの検証が済んだ,という記事に呼応して下記のようなTweetをした。

 これって,”FLOPS vs. Memory Bandwidth”に通じる話でもあるなと思ったので,ここでもう少し詳細にメモっておく。上記のTweetより少し手直ししたプログラムは下記の通り。

 Tweetに挙げたのは\(2^p\)(mpz_ui_pow_ui関数で計算)と\(2^{p – 1}\)(mpz_sub_ui関数で計算)の両方をファイルに書き出す奴だったので,後者のみ書き出すようにするとほぼ半分の時間で済む。

 10進数テキストで書き出すと大体45MBぐらいのファイルになる訳だが,ネット越しだとダウンロードする方が時間がかかる。100BASE-TXの環境でもイーブン。大体,計算そのものにかかる時間よりファイルに書き出す時間の方が問題で,更に言うと,メインメモリ内部のデータ移動の法に時間が費やされている。128MBぐらいのL3キャッシュがあれば,FLOPS(この場合は整数演算だからMIPSだけど)上げるよりもずっと高速に計算終了している筈で,さらに言えば,ファイルに書き出しせずにオンメモリで済むならもっと高速。つまりCPU内部の演算効率よりメモリ帯域(memory bandwidth)の方がよっぽど問題,というお話になるわけで。

 という自分用メモ。

[2018-01-26(Fri) 追記] 「多倍長数値計算入門(仮)」執筆開始につき,上記のCプログラムをJuliaスクリプトで書き直してみた。なーるほど,これは使いやすいや。

破綻する区間演算の事例


 精度保証計算(という言葉はあまり好きではないのだけれど)の事例も紹介しようかと,ARB(半径)とMPFI(区間)を使ってロジスティック写像\(x_{i+1} := 4x_i(1-x_i)\)の計算をさせてみたところ,桁数が足りないと破綻することが分かった(今更)。つーことで,128bits計算の事例(上)と256bitsの事例(下)をば。

 有効桁数がなくなった途端に区間や半径が急激にデカくなって破綻していることが一目でわかるのはいいとして,精度はともかく計算は最後まで実行したい時には使えん。とりあえず,こういう桁落ちが酷い事例には区間演算だろうとそうでなかろうと桁数増やしてやんなさいという結論になるな。

 あと,実係数2次方程式の事例も作ってみたが,判別式で実数解と複素数解の区別をするif文をどうしようとか,実用に当たってはやはりメンドクサイことを考えないといけないのでその辺をどうかして工夫すると研究になる訳で,こっから先は精度保証の方々にお任せしようっと。まぁ「最初から複素係数でやれ」という結論になるんだろうけど,それはARBの演習問題にしておけばいいか。

 つーことで,使用したプログラム(logistic_arb.c, logisitc_mpfi.c)を最後に掲載しておく。使用時にはARB, MPFIの他,MPFR/GMPが必要。

GNU MP(GMP)マニュアル翻訳日記(最終)

 

 「GMP」だと全然関係ない分野の略語と被ることが多いようなので,「GNU MP」も併記して書くことにしようっと。そういえば「gmp_ja」で検索するとこちらの方のページが既にあったことに気づかされたのでご紹介しておく。GNU MPを全然知らん方は目通ししてから拙訳(HTMLPDFソース)を読むことをお勧めします。

 さて,翻訳完了から日が経つと忘れそうなことを書きつけておく。

1.GMPの開発チーム
 って表紙(PDF)に書いてあるんだもんな,誰だか知りたくなるってもんであるが,これについてはAppendix Aにまとめてある。ズラズラ時系列的に並べてあるけど,Tröbjorn以外の主要人物を抜き出すと,Paul Zimmermann(仏,MPFR開発陣の一人でもある),Kevin Ryde(豪,Perl ModuleやEmacsスクリプト著作多数),Niels Möller(瑞),Marco Bodrato(伊,Toom-Cookアルゴリズムに詳しい),Marc Glisse(仏,最近ではmini-gmpの提唱と実装)あたりが主要開発者ということになる。今でもGMPのMLでお見かけするメンツで,保守管理もマメにやり,中核人物の狷介さを和らげるクッションにもなっているわけで,実力もさることながら人間的も優れている(MLを見る限りだけど)貴重な人材である。

2.イマイチ理解できてない部分
 やっぱり最後の「アルゴリズム」の章が難物で,ここについては数論アルゴリズムと各CPUのアーキテクチャに通じている方(つーたら日本だとかなり稀少な部類な絶滅危惧種)にリライトか再翻訳をお願いしたい。特にアセンブラで書かなきゃいけなくなった理由である「桁上がり・桁借り上げ処理」(素直に「キャリー操作」の方が良かったかな・・・),「ループ展開」,「アセンブラコードの書き方」なんて,実際にアセンブラ職人になってシコシコとマイクロ秒単位のチューニングを体験しないことにはスッキリ訳せないよ! GMPマニュアルの翻訳は十数年来挫折しまくってきたけど,原因はこの辺りの解読に自信が持てないからだったりする。とはいえ,もういい加減イイ歳なので恥だろうが何だろがやっておかないと後悔するとばかりにえいやっと直訳してみたのである。とゆーことでリライトをやってくれる貴重な人材求む!

3.Texinfoとmakeinfo
 TexinfoについてはTrueRoadさんのパッケージを一部利用させて頂いたが,W32Tex環境では通らない部分があって,結局,Ubuntu 16.04にtexlive2016をフルで突っ込んでxetex使ったら何とかPDFは生成できた。この辺,最近のTeX環境に疎いのでよー分からん。HTML化もUbuntuのmakeinfo –htmlで生成。こちらはスムーズにできた。今時デカい文書をTexinfo使う方が珍しいのかしらん?
 次はMPFR 4.0のTexinfoを処理する予定なんだが,まぁ当面は上記のように処理することになりそうである。TexnicianじゃないのであまりTexinfo辺で苦労したくないんで,本来ゴシックにすべき部分も明朝になってたりするけど,この辺でご勘弁を。

4.翻訳の意義
 今時は「ない」と断言してもいいんじゃないのかな。既に古いMPFRQDの翻訳やってみたけど,ワシの場合は完全に自己満足,オナニー的なものである。Web公開しているのはGoogleという世界最高の検索ツールが使いたいからであって,備忘録以上の意味はない。ワシの業績リストにも一切入れてないし(何人かの方からお褒めの言葉は頂いたけど)。ただ,「一通り読んでみましたよ」ぐらいの意思表示はできるかなと。多倍長数値計算の基本ライブラリであるMPFR,QD,GMPぐらいはマニュアルぐらい一通り読んでおかないとこの辺の専門家でございなんて言えないし,この辺の後追いをやるにしても,先人の業績を参考文献に使うぐらいの節度は欲しいし,参考文献に入れるなら「全部読んだ」ぐらいのことは言いたいしねぇ。
 GMPについては,もう当分これを超える多倍長自然数演算カーネルは出てこないだろうなと思うし,GPUではカーネルでmalloc/freeを繰り返すと覿面に遅くなるんで,MPNカーネルそのままの移植は向いてないだろうと感じる。CUMPは今んとこbasecase演算にとどまっているし,テンポラリメモリは固定で取ってるので,これそのままだとKaratsubaやToom-Cookの移植は大変そうである(割算だけ移植して挫折した奴がここにいる)。何にせよ,多倍長精度を素直にサポートするライブラリとしてはエベレスト的存在がGMPなので,当面この方向での進化もさしてなさそうに思える。
 GMP自体,Version 4以降はアーキテクチャの進化に追随しているだけで(それだけでも大したもんなんだけど),アルゴリズム的な大幅改善はない。Version 5はあっという間にVersion 6になっちゃったけど,メジャーバージョンアップの割には新規性はかなり薄い(だもんで不満も多少でてた)。どん詰まりっぽい状況だから,マニュアル翻訳も今やっておけばさほど古びずに済みそうという予想があってやっている訳である。オナニーなら性欲のあるうちじゃないと詰まらんしねぇ。

 とりあえず,こんなもんかしら? 後はどなたかに(翻訳する人がいれば)お任せする。

GMPマニュアル翻訳日記(2)

 つーことで,GMPマニュアルの下訳が完了した。3月中にできなきゃ一生できない気がしていたので,分からないところは適当にすっ飛ばしつつ,とりあえず意味が通りそうな日本語で埋めたというレベル。

 以降は,この下訳を直しながらの作業になるので,読みながら気になるところを紹介する日記になりそうである。

 通読して感じたのは,ほぼ独力でGMPを引っ張ってきたTrobjörn Granlundの個性だ。GNUの精神に共鳴して最初期からGNU Projectに参加し,ちょろっとでも商用ソフトにコードを流用しようもんなら激烈な批判を行う。多分批判の対象はIntel Math KernelとMathematicaのようだが,Microsoftにも嫌悪感をあらわにしていた時期も長かった。最近は老成したのか丸くなった感じもあるけど,20年以上も多様なCPU, OSに対応してきた,バリバリのアセンブラ&アルゴリズムマニアにして高速化に執念を燃やし続けてきた頑固職人ってのは,全世界探してもかなり希少な存在だ。ワシはご本人に会ったことはないけど,GMPのMLに流れてくる文面をチラ見している限りはかなりのトンがったお人のようである。遠目から敬しておきたい方である。

 しかしまぁ,長年に渡ってサポートを続けてきただけのことはあって,CPUの博物館みたいなことになっているのは,貴重かつ生きたソフトウェアの文化財といえるだろう。GMPよりさらに古い歴史を持つLAPACK/BLASがCPUアーキテクチャに依存した高速化の部分を他の研究チームや企業に丸投げしているのとは対照的である。

「現在は下記のCPU用のアセンブラコードが用意されています。
 ARM Cortex-A9, Cortex-A15, 汎用ARM,DEC Alpha 21064, 21164, 21264,AMD K8 と K10 (Athlon64, Phenom, Opteron等々,いろんなブランド名で販売展開されています),BulldozerとBobcat,Intel Pentium, Pentium Pro/II/III, Pentium 4, Core2, Nehalem, Sandy bridge, Haswell, 汎用x86,Intel IA-64,Motorola/IBM PowerPC 32 と 64 (POWER970, POWER5, POWER6, POWER7),MIPS 32-bit と 64-bit,SPARC 32-bit と 全てのUltraSPARC向けサポート付きのSPARC 64-bit。
 廃止されてしまったCPU用のアセンブラコードもそのまま残っています。」(1 GMPについて)

 コンピュータ博物館に収めたいコードも一緒に配布しているってのは貴重ではあるけれど,サポート面では厄介な問題もはらむ。mini-gmpなんてプロジェクトが提唱されるのも,レガシー化しちゃって分かりずらいコードを一部だけでもスッキリさせようということだろう。

 つーことで,4月一杯ゴソゴソ修正しながら愚痴とメモをここに書きつけていく次第である。