10

如何在集群上生成独立的伪随机数，例如蒙特卡罗模拟？我可以有许多计算节点（例如 100 个），我需要在每个节点上生成数百万个数字。我需要保证一个节点上的 PRN 序列不会与另一个节点上的 PRN 序列重叠。

  • 我可以在根节点上生成所有 PRN，然后将它们发送到其他节点。但这太慢了。
  • 我可以在每个节点上跳到序列中的已知距离。但是对于 Mersenne-Twister 或任何其他好的 PRNG，是否有这样的算法，可以用合理的时间和内存来完成？
  • 我可以在每个节点上使用不同的生成器。但是像 Mersenne-Twister 这样好的发电机有可能吗？怎么可能做到？
  • 还有别的吗？
4

5 回答 5

11

您永远不应使用从同一原始流中获得的可能重叠的随机流。如果您尚未测试生成的交错流，则您不知道它的统计质量。

幸运的是，Mersenne Twister (MT)将帮助您完成分发任务。使用其专用算法，称为Dynamic Creator（以下简称 DC），您可以创建独立的随机数生成器，生成高度独立的随机流。

每个流都将在将使用它的节点上创建。基本上，将 DC 视为创建不同 MT 实例的面向对象范式中的构造函数。每个不同的实例都旨在产生高度独立的随机序列。

你可以在这里找到 DC：http: //www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html
它使用起来非常简单，你可以修复不同的参数，例如您想要获取的不同 MT 实例的数量或这些 MT 的周期。根据其输入参数，DC 将运行时会发生变化。

除了 DC 随附的 README 之外，请查看example/new_example2.cDC 存档中的文件。它显示了在给定不同输入标识符的情况下获取独立序列的调用示例，这基本上是您识别集群作业所必须的。

最后，如果你打算了解更多关于如何在并行或分布式环境中使用 PRNG，我建议你阅读这篇科学文章：

随机高性能计算的随机流的实际分布，David RC Hill，在国际高性能计算和仿真会议 (HPCS)上，2010

于 2011-06-16T07:13:19.110 回答
1

好的，回答 #2 ;-)

我要说...保持简单。只需使用“短”种子来启动 MT（假设这个种子是 2 32位，因为没有更好的限制）。这假设短种子生成“充分分布”的 MT 起始状态（例如init_genrand，在我的其他答案中的代码中，希望如此）。这并不能保证平均分布的起始状态，而是“足够好”，见下文。

每个节点将使用它自己的预先选择的种子序列（传输的随机种子列表或类似的公式number_nodes * node_number * iteration）。重要的是，最初的“短”种子永远不会跨节点重复使用。

然后每个节点将使用一个用这个种子n时间初始化的 MT PRNG，其中n <<< MT_period / max_value_of_short_seed（TT800 是 2 800 -1 并且 MT19937 是 2 19937 -1，所以n仍然可以是一个非常大的数字）。多次之后n，节点移动到所选列表中的下一个种子。

虽然我没有（也不能）提供“保证”没有节点会同时（或根本没有）有重复的序列，但AMD 关于使用不同的 Seends的说法如下：（显然，最初的播种算法在播放职务）。

在此处描述的用于创建多个流的四种方法中，这是最不令人满意的……例如，如果初始值相距不够远，则从不同起点生成的序列可能会重叠。如果正在使用的生成器的周期很大，则重叠序列的可能性会降低。尽管不能保证序列的独立性，但由于其周期非常大，使用具有随机起始值的 Mersenne Twister 不太可能导致问题，尤其是在所需的序列数量很少的情况下......

快乐编码。

于 2011-06-16T05:52:15.087 回答
1

我可以在每个节点上跳到序列中的已知距离。但是对于 Mersenne-Twister 或任何其他好的 PRNG，是否有这样的算法，可以用合理的时间和内存来完成？

是的，请参阅http://theo.phys.sci.hiroshima-u.ac.jp/~ishikawa/PRNG/mt_stream_en.html。这是获得独立随机数流的绝佳解决方案。通过进行大于从每个流创建每个流的开始所需的随机数数量的跳转，流将不会重叠。

于 2013-03-01T03:08:50.017 回答
0

免责声明：我不确定从任意“uint”（或 x，其中 x 是较小的任意但唯一值）种子开始时，MT 在循环重叠方面有什么保证，但这可能值得研究，好像有是一个保证，那么只需在不同的“uint”种子上启动每个节点就足够了，而这篇文章的其余部分在很大程度上变得没有意义。（MT 的周期长度/周期是惊人的，除以 UINT_MAX 仍然留下一个难以理解的数字——除了在纸上——数字。）

好吧，这里是我的评论来回答......

我喜欢方法#2，它带有一组预先生成的状态；然后用给定的起始状态初始化每个节点中的 MT。

当然，只有初始状态必须保留，一旦生成，这些状态就可以

  1. 如果满足要求，可以无限期地重复使用，或者；
  2. 下一个状态可以在模拟运行的外部快速框上向前生成，或者；
  3. 节点可以报告结束状态（如果可靠的消息传递，以及是否在节点之间以相同的速率使用序列，并且满足要求等）

考虑到 MT 的生成速度很快，我不推荐上面的#3，因为它很复杂并且附带了许多字符串。选项 #1 很简单，但可能不够动态。

选项#2 似乎是一个很好的可能性。服务器（“快速机器”，不一定是节点）只需要传输下一个“未使用序列块”的起始状态（比如十亿个周期）——节点会在询问之前使用生成器十亿个周期对于一个新块。这将使它成为帖子中#1 的混合体，并且消息很少。

在我的系统 Core2 Duo 上，我可以使用下面提供的代码在 17 秒内生成十亿个随机数（它在LINQPad中运行）。我不确定这是什么 MT 变体。

void Main()
{
    var mt = new MersenneTwister();
    var start = DateTime.UtcNow;
    var ct = 1000000000;
    int n = 0;
    for (var i = 0; i < ct; i++) {      
        n = mt.genrand_int32();
    }
    var end = DateTime.UtcNow;
    (end - start).TotalSeconds.Dump();
}

// From ... and modified (stripped) to work in LINQPad.
// http://mathnet-numerics.googlecode.com/svn-history/r190/trunk/src/Numerics/Random/MersenneTwister.cs
// See link for license and copyright information.
public class MersenneTwister
{
    private const uint _lower_mask = 0x7fffffff;
    private const int _m = 397;
    private const uint _matrix_a = 0x9908b0df;
    private const int _n = 624;
    private const double _reciprocal = 1.0/4294967295.0;
    private const uint _upper_mask = 0x80000000;
    private static readonly uint[] _mag01 = {0x0U, _matrix_a};
    private readonly uint[] _mt = new uint[624];
    private int mti = _n + 1;

    public MersenneTwister() : this((int) DateTime.Now.Ticks)
    {
    }       
    public MersenneTwister(int seed)
    {
                init_genrand((uint)seed);
    }       

    private void init_genrand(uint s)
    {
        _mt[0] = s & 0xffffffff;
        for (mti = 1; mti < _n; mti++)
        {
            _mt[mti] = (1812433253*(_mt[mti - 1] ^ (_mt[mti - 1] >> 30)) + (uint) mti);
            _mt[mti] &= 0xffffffff;
        }
    }

    public uint genrand_int32()
    {
        uint y;
        if (mti >= _n)
        {
            int kk;

            if (mti == _n + 1) /* if init_genrand() has not been called, */
                init_genrand(5489); /* a default initial seed is used */

            for (kk = 0; kk < _n - _m; kk++)
            {
                y = (_mt[kk] & _upper_mask) | (_mt[kk + 1] & _lower_mask);
                _mt[kk] = _mt[kk + _m] ^ (y >> 1) ^ _mag01[y & 0x1];
            }
            for (; kk < _n - 1; kk++)
            {
                y = (_mt[kk] & _upper_mask) | (_mt[kk + 1] & _lower_mask);
                _mt[kk] = _mt[kk + (_m - _n)] ^ (y >> 1) ^ _mag01[y & 0x1];
            }
            y = (_mt[_n - 1] & _upper_mask) | (_mt[0] & _lower_mask);
            _mt[_n - 1] = _mt[_m - 1] ^ (y >> 1) ^ _mag01[y & 0x1];

            mti = 0;
        }

        y = _mt[mti++];

        /* Tempering */
        y ^= (y >> 11);
        y ^= (y << 7) & 0x9d2c5680;
        y ^= (y << 15) & 0xefc60000;
        y ^= (y >> 18);

        return y;
    }
}

快乐编码。

于 2011-06-16T05:00:29.190 回答
0

TRNG 是一个随机数生成器，专门针对并行集群环境构建（特别是为德国的 TINA 超级计算机构建）。因此，创建独立的随机数流并生成非标准分布非常容易。这里有一个关于如何设置的教程： http ://www.lindonslog.com/programming/parallel-random-number-generation-trng/

于 2013-08-10T17:38:13.910 回答