技術の家庭菜園

https://tpcbtw.com/

人生に迷ったのでハイコストに乱数を振った話

本稿はフィクションです。

導入

2018年5月、私は一つの大きな決断に迫られていた。
人生を左右するような大きな二択だった。
そのような決断は簡単にできるものではない。
当然熟考する。恩師や先輩や友人に話を聞く。いろんな事をやった。
結果、よくわからなくなってしまった。どちらでもそこそこの人生が歩めそうであったし、そしてどちらでも失敗の可能性も十分にあった。
リスクも同じ、リターンも同じ。ここまで同条件を並べられると決断もできない。

恩師に相談したところ、別れ際にこんな事を言われた「最後はサイコロでも振ったら？」
なるほど。ここまで熟考したのだ、後悔などすまい。運を天に任すのだ。
しかし人生を決める大きな決断だ。そんな適当に振ったサイコロで決めたくはない。
この決断に見合うハイコストな方法で乱数を振りたい。

計算機で乱数を振るということ

今欲しいのはハイコストな乱数である。
大量の乱数が欲しい時、通常は擬似乱数を用いる。擬似乱数は数学的な手段によって乱数"らしい"数を作り出したものである。
乱数は本来予測不可能で、一様でなく、再現できないもののはずだが、擬似乱数はそうでない。
私はこの決断を決定論的な疑似乱数なんかで決めたくはない。用いるのは真の乱数だ。

真の乱数を出す方法にはいろんな物がある。コインの裏表、サイコロなど簡単なものから、波の音からホワイトノイズを作ってもいいし、猫と放射性物質を箱の中に入れても良い。
しかし、この真の乱数を計算機により定めるのはそこまで難しい問題ではない。
linuxにおいては/dev/randomを参照すればそれで良い。
https://ja.wikipedia.org/wiki/dev/random
これはコンピュータ内のセンサー等から集められた環境ノイズを元にして作った乱数を出力できる。
この環境ノイズは予測不可能で、一様でなく、再現できない、つまり真の乱数である。
唯一の弱点は様々なデバイスを参照することにより乱数を作成するので、擬似乱数に比べて低速であることである。
またエントロピープールが枯渇すると、アクセスはロックされる。
低速なのであれば、これをデバイス間で並列化すればよいのだ。つまりは超並列計算機により、この乱数を振るのだ。
私の目的はハイコストに乱数を振ることであるし、この目的とも極めて合致している。
計算機は某所のスーパーコンピュータが幸運にも使える。
そうと決めてしまえば話は早い。
MPI*1による並列プログラミングをするだけである。

#include <cstdio>
#include "mpi.h"
#include <random>
#define LOOP 1000
int main(int argc, char* argv[]){
	MPI_Init(&argc, &argv);
	std::random_device rnd("/dev/random");
	for(int i=0;i<LOOP;i++){
		printf("%d\n", rnd()%2);
	}
	MPI_Finalize();
}

 *2
今回は各プロセスごと、乱数を1000回振る設定とした。プロセス数は実行時に指定できる。
コンパイルは以下の通り、まったく意味のない、intelコンパイラ、intel-mpi環境である。

$ mpiicpc -std=c++11 -O2 -xCORE-AVX2 hoge.cpp

さて、これを実行する。今回の目的はハイコストに乱数を振ることだ。
並列数もとんでもない値を指定する。
今回確保したノードはCPUが2016コア、GPUが1032192コア分のノードだ。理論値で倍精度1.6PFLOPSになる。*3
有名なスーパーコンピュータ「京」がざっくり10PFLOPSなのでその1/10くらいの性能、
そして普通のパソコンが10GFLOPS程度なのでその100000倍くらいの性能のあるマシンだ。

mpiのプロセス数は1コアに2プロセスくらい詰めても問題ないだろう。4032並列だ。

$ mpirun -n 4032 hoge.out > std.out

こんな頭の悪いmpirunは初めて書いたが、これで良いのだ。
そもそもこのプログラムはCPU律速ではなく、依存するのはマシンのエントロピープールのはずである。問答無用で実行だ。

結果 

$ grep -c "0" std.out
2016645
$ grep -c "1" std.out
2015355

 雌雄は決した、私は0番の結果に向かって人生を歩み始めたのである。

謝辞・脚注

今回の決定の際に、事前に人生の先輩たる様々な方に相談に乗っていただいた。
特にN先生、N氏、そしてすまいり氏(@smiry3333)、最凶毒素氏(@K_stjerne)には度々助言を頂いた。
結果的に乱数を振って決めるというアホな展開になってしまったが、そこで聞いたお話は私の人生決定に参考となるべきとても貴重なお話だった。
この場を借りて、御礼を申し上げたい。
また愚痴を聞いてくれたフォロワー各位、決定後祝ってくださった酒クズ諸兄にも、同様に御礼を申し上げたい。

最後に重ねて述べておくが、本記事はフィクションである。
まさか私用で世界屈指のスパコンを占領した事実など存在せず、人生決定をそのスパコンにやらせる阿呆など、どこにも存在するはずは無いのである。

補足

この記事は2018年夏に書かれたものであるが、いろんな事情により放置していたものである。
あれから一年近くがたち、いくつか補足しなければ内容、我ながらアホだと思う記述も増えてきたので補足しておきたい。

std::random deviceとは

https://cpprefjp.github.io/reference/random/random_device.html
非決定論的な乱数発生器とされるが、実装はコンパイラにより異なる。
しかし今回トークンとして明示的に/dev/randomを指定しており、通常/dev/randomを読込み出力する。

エントロピープールについて

エントロピープールはデフォルトではおおよそ4096bitの大きさをもつ。
今乱数を出力しようとstd::random deviceを呼んだとき、1回につき32bitがエントロピープールから使用される。
乱数に規則性があってはならないので一度使われた乱数が再利用されることはない。
エントロピープールの補填がなされないとき、4096bitしかないエントロピープールでは128個程度の乱数しか生成はできない。
エントロピープールの補填は随時行われてはいるが、その速度はそう早くない。
これはマシンにより大きく違うが、1分間で100bit程度であろう。
本稿では56スレッドのマシンが使われており、マシンあたりで言えば56000個の乱数、1792000bitのエントロピープールが必要となる。

このプログラムは果たして現実的な時間で実行可能なのか

現実として実行された。が、この乱数には幾つか不可解な点がある。
まずこのプログラムは1分以内に終了した。まずこれがおかしい。
先の見積もりで言えば、丸一日計算機を放置しても終わらない。
実際、テスト環境においては、エントロピープールが残り3000bit程度からスタートし、およそ100個の乱数を生成後エントロピープールは一桁となりアクセスはロックされ、プログラムの実行は極めて低速となった。

プログラムが実行された理由

しかし、本番環境ではそのエントロピープールは最大値4096中の1500前後を上下するだけで、アクセスもロックされずエントロピープールの枯渇も見られなかった。

これはおそらくrandom_deviceが/dev/randomを参照しているわけではなく、拡張命令セットであるRDRAND命令により乱数を得ているものだと考えられる。
しかしこの推測にはいくつも不可解な点がある。それらについて少しだけ考えつつ結論を放り投げ、本稿を終えたい。詳しい人がいればぜひ教えてほしい。

・結局iccにおけるrandom_deviceは/dev/randomを見てるのか？

今回に関しては間違いなく見ていない。だがこれに関してはおそらくiccが悪いわけではない。
というのも本番環境ではgccでビルドしても結局同様にエントロピープールが減少しない事が確認され、計算機依存の問題であると考えられるためである。

・テスト環境のE5-2620v2はIvy Bridgeであり、本番環境と同様にRDRAND命令は実装されているはずである。なぜrandom_deviceの解釈違いが発生するのか。

テスト環境のgcc4.4.7時点ではC+11は策定しておらず(-std=c++0x)、本番環境のicc 17.0.5では策定済みのため、random_deviceの内容が違う可能性。
プリプロセッサマクロの_GLIBCXX_X86_RDRANDが判定ミスしている可能性。
まぁよくわからない。

・そもそも明示的に/dev/randomをtokenとして示しているのに、なぜRDRANDを使うのか。

これはさっぱりわからない。

・ところでRDRANDって真の乱数なの？仮にRDRANDが疑似乱数だとするとお前の人生決定論的な疑似乱数で決定されたことになるけど大丈夫？

"That certainly depends on your view of the determinism of the universe, so is more a philosophical question, but many people consider it being random."

https://stackoverflow.com/questions/17616960/true-random-numbers-with-c11-and-rdrand

・全然話変わるけど、32bitの整数型から1bitのバイナリ出すってアホじゃないの？

これあとから気づいて死にたくなった。
rnd()%2とかいう記述はせっかく32bitある乱数列の一番下のビットを見てるだけなのである。
せやかてstd::random_deviceは32bitしか吐かないし、2進の書式指定子とか存在しないし、2進変換する部分を別で書くのもめんどっちぃ。
仮に32bitすべてを乱数として採用しても56000bitのエントロピープールが必要でどうせ/dev/randomにはできる所業じゃないから、まぁ結果的に良かったんじゃないかと思う。

・ついでにこの選択についての1年後の自分からのコメント

この2択だったら間違ってない選択だったと思うけど、これ以外の選択肢は無かったのかなぁと少し思う。

*1:MPIは並列コンピューティングに用いられる方式、まぁプロトコルのようなものである。OpenMPによる並列化ならともかく、MPIに馴染みのある人は多くはないだろう。OpenMPが共有メモリ上でのスレッド並列を提供するのに対し、MPIは分散メモリ上でのプロセス並列を提供する。そのためメモリを共有しないスーパーコンピュータなどの環境ではMPIが有効である。

*2:作法としてはMPIプロセス同士で通信を行い0番のプロセスに結果を統合し出力を行う。しかしこの場合はデータの順番や結果の統合などどうでも良いのですべて標準出力に書き出してしまえば良い。

*3:これは誇張表現であり、嘘である。GPUは使ってないし、CPUでさえ占有したかといえば怪しいとこなので、この見積もりはかなり不適当である。第一私用で使っていいスパコンなど存在しない。重ねて言うがこの記事はフィクションなのである。