Mersenne Twister for Graphic Processors (MTGP)

Mersenne Twister for Graphic Processors (MTGP):
a new variant of Mersenne Twister^*1.

MTGP について

MTGPは2009年に、松本眞と斎藤睦夫によって、開発された新しいタイプのメルセンヌ・ツイスタです。 Graphic Processor の特徴である並列性とテクスチャメモリなどの定数参照の速さを活かしたアルゴリズムになっています。 MTGPには32ビット版と64ビット版があり、 32ビット版は符号なし32ビット整数または単精度浮動小数点数を生成、 64ビット版は符号なし64ビット整数または倍精度浮動小数点数を生成します。

周期は32ビット版が2¹¹²¹³-1,2²³²⁰⁹-1, 2⁴⁴⁴⁹⁷-1であり、 64ビット版が2²³²⁰⁹-1, 2⁴⁴⁴⁹⁷-1, 2¹¹⁰⁵⁰³-1です。それぞれの周期について、128個のパラメータセットがあります。つまり、周期ごとに、128系統の独立した乱数系列が作れます。それ以上の系列が必要な場合に備えて、Dynamic Creator の MTGP版を開発しました。

Preprint in arXiv.
A paper of MTGP (under review, coauthored with Makoto Matsumoto).

A PDF slide 'A deviation of XORWOW of CURAND' in MCQMC 2012.

CUDA で実装したサンプルプログラムがあります。Open CL, ATI Stream に対応したサンプルは、まだありませんが、Radeon でも高速に実行出来るのではないかと考えています。

MTGPのダウンロード

このプログラムは2009年11月17日に一般に公開されました。公開されたばかりなので、いくつかバグがあるかも知れません。バグ報告、その他ご意見などありましたら、saito アットマーク math.sci.hiroshima-u.ac.jp および m-mat アットマーク math.sci.hiroshima-u.ac.jp までメールしてください。

version	archive	changes
new! 1.1.2	MTGP-src-1.1.2.zip MTGP-src-1.1.2.tar.gz	CUDA sample が CUDA 5.0 環境で動作するように修正しました。 (2012/10/24)
1.1.1	MTGP-src-1.1.1.zip MTGP-src-1.1.1.tar.gz	jump 機能を追加しました。 OpenCL sample を追加しました。(jump 機能を含む) CUDA 5.0 環境では正しく動作しません。 (2012/10/18)
1.1	MTGP-src-1.1.zip MTGP-src-1.1.tar.gz	均等分布次元を改良するために mtgp32 のパラメータファイルを変更しました。この変更によって出力が変更されますが、単精度浮動小数点数の出力は変更されません。この変更は符号なし整数の下位９ビットにだけ影響するもので、その9ビットは浮動小数点数に変換するときに捨てられるからです。以前のバージョンを使用している方は、古いパラメータファイルをそのまま使用しても問題ありません。 cuda-sampleディレクトリにあるサンプルファイルをCUDA 4.0 環境でもコンパイル出来るように修正しました。 (2011/6/6)
1.0.2	MTGP-src-1.0.2.zip MTGP-src-1.0.2.tar.gz	CUDA-sample の MEXPを11213に変更。これはactive threadを多くするためです。(2010/3/26)
1.0.1	MTGP-src-1.0.1.zip MTGP-src-1.0.1.tar.gz	64bit 初期化バグ修正 (2010/1/5)
1.0	MTGP-src-1.0.zip MTGP-src-1.0.tar.gz	初期バージョン。 CUDA用サンプルプログラム付き。(2009/11/17)

ダウンロードがうまくいかない時は、こちらのページからやってみてください。

MTGP Dynamic Creator (MTGPDC)

MTGPDCはMTGP用のパラメータセットを作成します。 MTGPには周期毎に128個のパラメータセットが付属していますが、それ以上のパラメータが必要な場合はMTGPDCを使用して2³²個までのパラメータを作成することができます。

MTGPDCは2³²¹⁷, 2⁴⁴²³, 2¹¹²¹³, 2²³²⁰⁹, 2⁴⁴⁴⁹⁷ という周期のMTGPのパラメータを作成することができます。

MTGPDCはいくつかのライブラリを使用していますので、コンパイルには以下のライブラリが必要です。

Victor Shoup's NTL: A Library for doing Number Theory.
C++ TR1 Libraries. (g++ ver. 4.0 or later)
Boost C++ Libraries.
OpenSSL.

さらにMTGPはUNIX系OSとGNU C++ compiler(g++)を必要とします。

MTGPDCのダウンロード

このプログラムは2010年3月26日に一般に公開されました。公開されたばかりなので、いくつかバグがあるかも知れません。バグ報告、その他ご意見などありましたら、saito アットマーク math.sci.hiroshima-u.ac.jp および m-mat アットマーク math.sci.hiroshima-u.ac.jp までメールしてください。

version	archive	changes
new! 0.3.1	MTGPDC-src-0.3.1.zip MTGP-src-0.3.1.tar.gz	ver. 0.3 のmtgp64dc のテンパリングパラメータがすべてゼロになるというバグを修正しました。(2011/3/9)
0.3	MTGPDC-src-0.3.zip MTGP-src-0.3.tar.gz	search_temper.hpp のバグを修正。このバグは最下位５ビットのテンパリングに影響し、その均等分布次元を本来のものより低くしていました。更に、テンパリングパラメータの探索アルゴリズムを改善しました。改善された探索アルゴリズムはMSBからの均等分布次元だけでなく、 LSBからの均等分布次元も考慮するようになっています。これはJonathan Passerat-Palmbach, David R.C. Hill および Claude Mazel によるMTGPのLSBに関する統計的検定結果の報告によるものです。報告ありがとうございます。 (2011/3/4) 64bit 版である mtgp64dc には、探索されたテンパリングパラメータがすべてゼロになるという重大なバグがありますので使用しないでください。このバグはこのバージョン0.3のみに存在し、以前のバージョンにはありません。また、0.3.1で修正されています。 (2011/3/9)
0.2	MTGPDC-src-0.2.zip MTGP-src-0.2.tar.gz	BUG Fixが少し溜まったのでリリース (2010/6/8)
0.1	MTGPDC-src-0.1.zip MTGP-src-0.1.tar.gz	初期バージョン (2010/3/26)

ダウンロードがうまくいかない時は、こちらのページからやってみてください。

License

MTと同様に、MTGP, MTGPDCは商用利用を含むどんな目的にも自由に使用することができます。詳細については、LICENSE.txt　を見てください。これは修正BSDライセンスです。

メルセンヌ・ツイスタのページへ。
SFMTのページへ。

*1 この研究は日本学術振興会先端研究拠点事業の補助を受けて行われています。No. 18005: "数論幾何・モチーフ理論・ガロア理論の新展開と、その社会的実用"
この研究は日本学術振興会科学研究費の補助も受けています。 No. 19204002, No. 18654021, No. 21654004.