24

問題

約 100 万個の 32 ビット疑似乱数に基づいて数値シミュレーション (暗号化ではない) を行う Linux 用の C++11 アプリケーションを作成するつもりです。高速化するために、デスクトップ CPU のすべてのコアを使用して並列スレッドでシミュレーションを実行したいと考えています。ブーストによって提供されるMersenne Twister を PRNG として使用したいと思いmt19937ます。パフォーマンス上の理由から、スレッドごとに 1 つの PRNG を使用する必要があると思います。複数のスレッドで乱数の同じサブシーケンスを生成しないようにするために、それらをシードする方法がわかりません。

代替案

これまでに考えた代替案は次のとおりです。

  1. から独立してすべてのスレッドの PRNG をシードし/dev/urandomます。

    システム内部の PRNG がどのように動作するのかわからないため、システムのエントロピー プールが枯渇した場合が少し心配です。/dev/urandomMersenne Twister 自体を使用しているため、Mersenne Twister の連続した状態を正確に識別する連続したシードを誤って取得することはありますか? おそらく、次のポイントに対する私の懸念と強く関連しています。

  2. 1 つの PRNG をシード/dev/urandomし、最初のものから他をシードします。

    基本的に同じ懸念事項: ある PRNG を使用して、同じアルゴリズムを使用する別の PRNG をシードすることは良いことですか、悪いことですか? または、言い換えると、 から 625 個の 32 ビット整数を読み取ることは、この生成中の任意の時点でmt19937のジェネレーターの内部状態に直接対応しますか?mt19937

  3. メルセンヌ以外の情報を最初からシードします。

    乱数の生成と初期シードの生成に同じアルゴリズムを使用するのは、どこか悪い考えに思えるので、Mersenne Twister アルゴリズムに依存しない要素を導入することを考えました。たとえば、スレッド ID を初期シード ベクトルの各要素に XOR することができます。それは物事をより良くしますか？

  4. スレッド間で 1 つの PRNG を共有します。

    これにより、メルセンヌ ツイスターの既知の望ましい特性をすべて備えたシーケンスが 1 つだけ存在することが保証されます。しかし、そのジェネレーターへのアクセスを制御するために必要なロックのオーバーヘッドは、やや心配です。反対の証拠が見つからなかったので、ライブラリ ユーザーとして、PRNG への同時アクセスを防止する責任があると思います。

  5. すべての乱数を事前に生成します。

    これにより、1 つのスレッドが必要な 1M 乱数をすべて前もって生成し、後で別のスレッドで使用できるようになります。4M のメモリ要件は、アプリケーション全体のメモリ要件に比べて小さくなります。このアプローチで私が最も心配しているのは、乱数の生成自体が並行していないことです。このアプローチ全体も、あまりうまくスケーリングしません。

質問

これらのアプローチのどれを提案しますか?またその理由は? それとも別の提案がありますか？

私の懸念のどれが正当で、どれが単に物事が実際にどのように機能するかについての洞察の欠如によるものか知っていますか?

4

8 に答える 8

7

私は＃1に行き、urandomからすべてのprngをシードします。これにより、状態が完全に独立していることが保証されます (シード データが独立している限り)。通常、多くのスレッドがない限り、利用可能なエントロピーは十分にあります。また、 /dev/urandom に使用されるアルゴリズムによっては、ほとんど心配する必要はありません。

したがって、次のようなものを使用して各prngを作成できます。

#include <random>

std::mt19937 get_prng() {
    std::random_device r;
    std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
    return std::mt19937(seed);
}

std::random_deviceプルの実装が構成の下から行われていることを確認する必要があり/dev/urandomます。また、デフォルトで /dev/urandom を使用する場合は、通常、std::random_device("/dev/random")代わりに /dev/random を使用するかどうかを指定できます。

于 2013-02-17T18:14:35.937 に答える
5

異なる代数的構造を持つPRNGを使用して、異なるPRNGをシードすることができます。たとえば、MD5ハッシュのシーケンス。

しかし、私は＃5を選びます。それが機能する場合、それは問題ありません。そうでない場合でも、最適化できます。

重要なのは、優れたPRNGを作成することは、予想よりもはるかに難しいということです。スレッド化されたアプリケーションに適したPRNGは、おそらくまだ調査の対象となっているものです。

CPUの数が十分に少ない場合は、リープフロッグを回避できます。たとえば、コアが4つある場合は、すべて同じ値で初期化しますが、コア1のPRNGを1ずつ、＃2を、＃3を3ずつ進めます。次に、新しい番号が必要な場合は、常に4ステップ進めます。

于 2013-02-17T17:47:42.083 に答える
3

1つのインスタンスを使用して他のインスタンスをシードします。私はあなたがこれをかなり簡単に安全に行うことができるとかなり確信しています。

  • 状態空間の小さな変更でさえ、ダウンストリームでかなり大きな変更を引き起こします-それらが完全に同じ開始空間を持たない（そして同じ状態プレフィックスがない）ことを確認できれば、同じ番号を生成することについて心配する必要はありません。たとえば、値1、2、3だけを使用して3つのスレッドをシードすると、正常に機能します。スペース全体をシードする必要はありません。もう1つの利点：明確に予測可能なシードを使用することで、実行をチェリーピッキングしているという考えを簡単に信用できなくなります（何かをデモンストレーションしようとしていると仮定します）。
  • 結果として生じる「子供」が非常に無相関であることを意味する方法でシードすることは簡単です。幅優先の方法で繰り返すだけです。つまり、N x 623のint値をシードする場合は、623の値を順番にシードせずに、最初のNを選択して分散し、次に次のNなどを選択します。シーダーと子の間に何らかの相関関係がある場合でも、さまざまな子供は事実上存在しないはずです-そしてそれはあなたが気にするすべてです。
  • 可能な限り決定論的な実行を可能にするアルゴリズムを好むので、urandomに依存することは魅力的ではありません。これにより、デバッグが容易になります。
  • 最後に、そして明らかに-テスト。これらのPRNGはかなり堅牢ですが、必ず結果を確認し、シミュレートしているものに触発されたいくつかの相関テストを実行してください。ほとんどの問題は明白であるはずです-あなたがひどくシードし、明らかな繰り返しのサブシーケンスがあるか、あなたがうまくシードしたか、そして品質はPRNGの制限によって決定されます。
  • 最終的な実行では、テストが完了した後、安心のためにurandomを使用して623の状態値の最初の値をシードしたり、スレッドIDをシードしたりできます。
于 2013-02-17T17:44:50.893 に答える
3

種糸 1 と 1、種糸 2 と 2 など。

モンテカルロが必要な場合、これにより再現可能な結果が得られ、追跡と実装が簡単になります。

于 2013-02-17T21:05:53.543 に答える
2

次の論文をご覧ください：擬似乱数生成器の動的作成とそれに伴う実装：動的作成者。それはこの正確な問題に取り組みます。

于 2013-02-17T17:44:28.853 に答える
1

＃3が勝者だと思います。processIDやthreadIDのようなもので各スレッドをシードします。技術的には重複する可能性はありますが、その可能性はほとんどありません。1桁から抜けると、連続する数字でさえシードの観点から関連するべきではありません（Twisterアルゴリズムはわかりませんが、私が見た中で最悪のPRNGは7を超えても問題ありませんでした）。100万のPRNGは、ほとんどのPRNG方程式の範囲と比較してそれほど多くはありません。

最後に、かなり簡単に確認できます。各スレッドによって生成された最後のシードを、他の各スレッドのすべての番号と照合します。シードがスレッドに表示される場合は、各スレッドで生成された以前の番号を確認してください。それらも一致する場合は、衝突が発生しているため、ストリームを再シードして再試行する必要があります。

于 2013-02-17T17:41:03.227 に答える
1

並列計算のための Mersenne Twister の使用に特に関連する実装 (および公開された論文) があります。これは、MT の元の作成者によるものです。彼らはそれを「ダイナミッククリエーター」と呼んでおり、ここで見つけることができます：

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html

これは、MT19937 の特定の使用法、特にそこにある論文を調べるのに非常に適した場所です。

于 2013-03-13T11:36:00.943 に答える