Generador de números pseudo-aleatorio para entorno de clúster

https://stackoverflow.com/questions/6367058

28-10-2019
|

Pregunta

¿Cómo puedo generar números pseudo-aleatorios independientes en un clúster, para la simulación de Monte Carlo, por ejemplo? Puedo tener muchos nodos de cómputo (por ejemplo, 100), y necesito generar millones de números en cada nodo. Necesito una garantía de que una secuencia PRN en un nodo no superponga la secuencia PRN en otro nodo.

Podría generar todo PRN en el nodo raíz, luego enviarlos a otros nodos. Pero sería demasiado lento.
Podría saltar a una distancia de conocimiento en la secuencia, en cada nodo. Pero, ¿hay tal algoritmo para Mersenne-Twister o para cualquier otro buen PRNG, que se puede hacer con una cantidad razonable de tiempo y memoria?
Podría usar diferentes generadores en cada nodo. ¿Pero es posible con buenos generadores como Mersenne-Twister? ¿Cómo se puede hacer?
¿Algún otro aunque?

Solución

Nunca debe usar corrientes aleatorias potencialmente superpuestas obtenidas de la misma transmisión original. Si no ha probado la corriente entrelazada resultante, no tiene idea de su calidad estadística.

Afortunadamente, Mersenne Twister (MT) te ayudará en su tarea de distribución. Usando su algoritmo dedicado, llamado Creador dinámico (DC en adelante), puedes crear Generadores de números aleatorios independientes Eso producirá corrientes aleatorias altamente independientes.

Cada secuencia se creará en el nodo que lo usará. Básicamente, piense en DC como un constructor en paradigma orientado a objetos que crea diferentes instancias de MT. Cada instancia diferente está diseñada para producir secuencias aleatorias altamente independientes.

Puedes encontrar DC aquí: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/mt/dc/dc.html
Es bastante sencillo de usar y podrá corregir diferentes parámetros, como la cantidad de diferentes instancias de MT que desea obtener o el período de estos MT. Dependiendo de su parámetro de entrada, DC Will Runtime cambiará.

Además de que el ReadMe viene con DC, eche un vistazo al archivo example/new_example2.c En el archivo de DC. Muestra un ejemplo de llamadas para obtener secuencias independientes. dado un identificador de entrada diferente, que es básicamente lo que tienes para identificar los trabajos de clúster.

Finalmente, si tiene la intención de aprender más sobre cómo usar PRNG en entornos paralelos o distribuidos, le sugiero que lea estos artículos científicos:

Distribución práctica de transmisiones aleatorias para computación estocástica de alto rendimiento, David RC Hill, en Conferencia internacional sobre computación y simulación de alto rendimiento (HPCS), 2010

Otros consejos

Está bien, respuesta #2 ;-)

Voy a decir ... mantenlo simple. Simplemente use una semilla "corta" para preparar el MT (imagine que esta semilla es 2³² bits por falta de mejor restricción). Esto supone que la semilla corta genera estados iniciales "suficientemente distribuidos" (por ejemplo init_genrand en el código en mi otra respuesta, con suerte). Esto no garantiza un estado inicial igualmente distribuido, sino que va para "lo suficientemente bueno", ver a continuación.

Cada nodo usará su propia secuencia de semillas que se preseleccionan (ya sea una lista de semillas aleatorias que se transmiten o una fórmula como number_nodes * node_number * iteration). Lo importante es que la semilla "corta" inicial nunca se reutilizará en los nodos.

Cada nodo usará un MT PRNG inicializado con esta semilla n veces donde n <<< MT_period / max_value_of_short_seed (TT800 es 2⁸⁰⁰-1 y mt19937 es 2¹⁹⁹³⁷-1, asi que n todavía puede ser un muy grande número). Después n Times, el nodo se mueve a la siguiente semilla en la lista elegida.

Si bien no (ni puedo) proporcionar una "garantía" de que ningún nodo tenga una secuencia duplicada al mismo tiempo (o en absoluto), esto es qué es lo que AMD dice sobre el uso de diferentes asendios: (Obviamente, el algoritmo de siembra inicial juega un papel).

De los cuatro métodos para crear múltiples transmisiones descritas aquí, este es el menos satisfactorio ... Por ejemplo, las secuencias generadas a partir de diferentes puntos de partida pueden superponerse si los valores iniciales no están lo suficientemente separados. El potencial para la superposición de secuencias se reduce si el período del generador que se utiliza es grande. Aunque no hay garantía de la independencia de las secuencias, debido a su período extremadamente grande, es poco probable que el uso de Mersenne Twister con valores iniciales aleatorios conduzca a problemas, especialmente si el número de secuencias requeridas es pequeña ...

Feliz codificación.

Podría saltar a una distancia de conocimiento en la secuencia, en cada nodo. Pero, ¿hay tal algoritmo para Mersenne-Twister o para cualquier otro buen PRNG, que se puede hacer con una cantidad razonable de tiempo y memoria?

Si, mira http://teo.phys.sci.hiroshima-u.ac.jp/~ishikawa/prng/mt_stream_en.html. Esta es una excelente solución para obtener flujos de números aleatorios independientes. Al hacer saltos que son más grandes que el número de números aleatorios necesarios de cada transmisión para crear los inicios de cada transmisión, las transmisiones no se superponen.

Descargo de responsabilidad: no estoy seguro de qué garantía tiene MT en términos de superposición de ciclo al comenzar desde una semilla arbitraria "uint" (o x, donde x es una semilla arbitraria pero única) más pequeña, pero puede valer la pena considerar, como si hay es una garantía, entonces puede ser suficiente comenzar cada nodo en una semilla "uint" diferente y el resto de esta publicación se vuelve en gran medida discutible. (La duración del ciclo/período de MT es asombroso y dividir uint_max todavía deja un incomprensible - excepto en papel- número).

Bueno, aquí van mis comentarios para responder ...

Me gusta el enfoque #2 con un conjunto de estados pregenerados; El MT en cada nodo se inicializa con un estado inicial dado.

Solo los estados iniciales deben ser preservados, por supuesto, y una vez que esto se genera, estos estados pueden

Ser reutilizado indefinidamente, si se cumplen los requisitos, o;
Los siguientes estados pueden generar hacia adelante en un cuadro rápido externo por qué la simulación se está ejecutando o;
Los nodos pueden informar el estado final (si la mensajería confiable, y si la secuencia se usa a la misma velocidad entre los nodos, y cumple con los requisitos, etc.)

Considerando que MT es rápido para generar, No recomendaría el n. ° 3 desde arriba, ya que es simplemente complicado y tiene una serie de cuerdas adjuntas. La opción n. ° 1 es simple, pero puede que no sea lo suficientemente dinámica.

La opción #2 parece una muy buena posibilidad. El servidor (una "máquina rápida", no necesariamente un nodo) solo necesita transmitir el estado inicial del próximo "bloque de secuencia no utilizado" (por ejemplo, mil millones de ciclos): el nodo usaría el generador durante mil millones de ciclos antes de preguntar para un nuevo bloque. Esto lo convertiría en un híbrido del #1 en la publicación con mensajes muy poco frecuentes.

En mi sistema, un dúo Core2, puedo generar un mil millones Números aleatorios en 17 segundos utilizando el código proporcionado a continuación (se ejecuta en Linqpad). No estoy seguro de qué variante MT es esta.

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;
    }
}

Feliz codificación.

TRNG es un generador de números aleatorios construido específicamente con entornos de clúster paralelos en mente (específicamente fue construido para la super computadora Tina en Alemania). Por lo tanto, es muy fácil crear flujos de números aleatorios independientes y también generar distribuciones no estándar. Hay un tutorial sobre cómo configurarlo aquí:http://www.lindonslog.com/programming/parallel-random-number-generation-trng/

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow