Генератор псевдослучайных чисел для кластерной среды

Как я могу генерировать независимые псевдослучайные числа в кластере, например, для моделирования методом Монте-Карло? У меня может быть много вычислительных узлов (например, 100), и мне нужно генерировать миллионы чисел на каждом node. Мне нужна гарантия того, что последовательность PRN на одном node не будет перекрывать последовательность PRN на другом node.

Я мог бы сгенерировать все PRN в корневом каталоге node, а затем отправить их другим узлам. Но это было бы слишком медленно.
Я мог бы перейти к знанию расстояния в последовательности, на каждом node. Но существует ли такой алгоритм для Mersenne-Twister или для любого другого хорошего PRNG, который может быть сделан с разумным количеством времени и памяти?
Я могу использовать разные генераторы для каждого node. Но возможно ли с такими хорошими генераторами, как Мерсен-Твистер? Как это можно сделать?
Любой другой, хотя?

Ответ 1

Вы никогда не должны использовать потенциально перекрывающиеся случайные потоки, полученные из того же исходного потока. Если вы не тестировали полученный чередующийся поток, вы не знаете его статистического качества.

К счастью, Mersenne Twister (MT) поможет вам в вашей задаче распространения. Используя выделенный алгоритм, называемый Dynamic Creator (далее DC), вы можете создать независимых генераторов случайных чисел, которые будут генерировать высоко независимые случайные потоки.

Каждый поток будет создан на node, который будет использовать его. В принципе, подумайте о DC как о конструкторе в объектно-ориентированной парадигме, которая создает разные экземпляры MT. Каждый отдельный экземпляр предназначен для создания высоко независимых случайных последовательностей.

Здесь вы можете найти DC: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html
Он довольно прост в использовании, и вы сможете исправить различные параметры, такие как количество экземпляров MT, которые вы хотите получить, или период этих MT. В зависимости от его входного параметра DC будет изменяться.

В дополнение к README, идущему вместе с DC, посмотрите файл example/new_example2.c в архиве DC. Он показывает пример вызовов для получения независимых последовательностей с учетом другого входного идентификатора, что в основном означает то, что вам нужно определить задания кластера.

Наконец, если вы намерены больше узнать о том, как использовать PRNG в параллельной или распределенной среде, я предлагаю вам ознакомиться с этими научными статьями:

Практическое распределение случайных потоков для стохастических высокопроизводительных вычислений, David RC Hill, в Международной конференции по высокопроизводительным вычислениям и симуляции (HPCS), 2010

Ответ 2

Хорошо, ответ # 2; -)

Я собираюсь сказать... держите это просто. Просто используйте "короткое" семя, чтобы заполнить MT (представьте, что это семя - это 2 ³² бит из-за отсутствия лучшего ограничения). Это предполагает, что короткое семя, как мы надеемся, генерирует "достаточно распределенные" MT-состояния (например, init_genrand в коде в моем другом ответе). Это не гарантирует равнораспространенное начальное состояние, а скорее идет "достаточно хорошо", см. Ниже.

Каждый node будет использовать свою собственную последовательность семян, которые предварительно выбраны (либо список случайных семян, которые передаются, либо формула типа number_nodes * node_number * iteration). Важно то, что начальное "короткое" семя никогда не будет повторно использоваться через узлы.

Каждый node будет использовать MT PRNG, инициализированный с этим семенем n раз, когда n <<< MT_period / max_value_of_short_seed (TT800 равен 2 ⁸⁰⁰ -1 и MT19937 составляет 2 ¹⁹⁹³⁷ -1, поэтому n все еще может быть очень большим числом). После n раз node перемещается в следующее семя в выбранном списке.

Пока я не могу (и не могу) предоставить "гарантию", что no node будет иметь повторяющуюся последовательность в одно и то же время (или вообще), вот что AMD говорит об использовании разных семян: (Очевидно, что исходный алгоритм сеялки играет роль).

Из четырех способов создания нескольких потоков, описанных здесь, это наименее удовлетворительный... Например, последовательности, сгенерированные из разных исходных точек, могут перекрываться, если начальные значения находятся не слишком далеко друг от друга. Потенциал перекрывающихся последовательностей уменьшается, если период используемого генератора велик. Несмотря на отсутствие гарантии независимости последовательностей из-за его чрезвычайно большого периода, использование Mersenne Twister со случайными начальными значениями вряд ли приведет к проблемам, особенно если количество требуемых последовательностей невелико...

Счастливое кодирование.

Ответ 3

Я мог бы перейти к знанию расстояния в последовательности, на каждом node. Но это там такой алгоритм для Мерсен-Твистера или для любого другого хорошего PRNG, что можно сделать с разумным количеством времени и памяти?

Да, см. http://theo.phys.sci.hiroshima-u.ac.jp/~ishikawa/PRNG/mt_stream_en.html. Это отличное решение для получения независимых потоков случайных чисел. Выполняя переходы, которые больше, чем количество случайных чисел, необходимых от каждого потока, для создания запусков каждого потока, потоки не будут перекрываться.

Ответ 4

Отказ от ответственности: я не уверен, что гарантия MT имеет место в отношении перекрытия цикла, начиная с произвольного "uint" (или x, где x - меньшее произвольное, но уникальное значение) семя, но это может быть интересно изучить, как будто есть гарантия, тогда может быть достаточно просто запустить каждый node на другое семя "uint", а остальная часть этого сообщения станет в значительной степени спорным. (Длина цикла/период MT ошеломляет, а разделение UINT_MAX по-прежнему оставляет непонятным - за исключением бумажного номера.)

Ну, вот мои комментарии, чтобы ответить...

Мне нравится подход №2 с заранее сгенерированным множеством состояний; MT в каждом node затем инициализируется с заданным начальным состоянием.

Конечно, необходимо сохранить только начальные состояния, и как только это будет создано, эти состояния могут

Повторно использовать бесконечно, если требования выполнены, или;
Следующие состояния могут быть сгенерированы вперед на внешнем быстром поле, для чего выполняется симуляция, или
Узлы могут сообщать о завершающем состоянии (если надежный обмен сообщениями, и если последовательность используется с одинаковой скоростью среди узлов и соответствует требованиям и т.д.)

Учитывая, что MT быстро генерирует, я бы не рекомендовал # 3 сверху, поскольку он просто усложняется и имеет несколько строк. Вариант № 1 прост, но может быть недостаточно динамичным.

Вариант № 2 кажется очень хорошей возможностью. Сервер ( "быстрая машина", не обязательно node), должен только передать начальное состояние следующего "неиспользуемого блока последовательности" (скажем, один миллиард циклов) - node будет использовать генератор для одного миллиард циклов, прежде чем запрашивать новый блок. Это сделало бы его гибридом №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;
    }
}

Счастливое кодирование.

Ответ 5

TRNG - это генератор случайных чисел, созданный специально для параллельных кластерных сред (в частности, он был построен для суперкомпьютера TINA в Германии). Следовательно, очень легко создавать независимые случайные числовые потоки, а также генерировать нестандартные дистрибутивы. Существует руководство по настройке здесь: http://www.lindonslog.com/programming/parallel-random-number-generation-trng/