集群环境下的伪随机数生成器

Question

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

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

Answer 1

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

幸运的是，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 附带的自述文件之外，请查看 DC 存档中的文件 example/new_example2.c。它显示了调用获取独立序列给定不同的输入标识符的示例，这基本上是您识别集群作业所必须的。

最后，如果您打算了解有关如何在并行或分布式环境中使用 PRNG 的更多信息，我建议您阅读以下科学文章：

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

Answer 2

好的，回答#2 ;-)

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

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

然后，每个节点将使用使用此种子初始化的 MT PRNG n 次，其中 n << MT_period / max_value_of_short_seed（TT800 为 2⁸⁰⁰-1 和 MT19937是 2¹⁹⁹³⁷-1，所以 n 仍然可以是非常大数量）。 n 次后，节点移动到所选列表中的下一个种子。

虽然我没有（也不能）提供任何节点都不会同时（或根本）有重复序列的“保证”，但以下是 AMD 关于使用不同 Seends 的说明：（显然初始种子算法发挥了作用）。

<块引用>

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

快乐编码。

Answer 3

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

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

Answer 4

免责声明：我不确定当从任意“uint”（或 x，其中 x 是较小的任意但唯一值）种子开始时，MT 在循环重叠方面有什么保证，但这可能值得研究，好像有是一个保证，那么在不同的“uint”种子上启动每个节点可能就足够了，这篇文章的其余部分在很大程度上变得毫无意义。 （MT 的周期长度/周期令人震惊并且除out 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;
    }
}

快乐编码。

Answer 5

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