Generatore di numeri pseudo-casuale per ambiente cluster

https://stackoverflow.com/questions/6367058

28-10-2019
|

Domanda

Come posso generare numeri pseudo-casuali indipendenti su un cluster, ad esempio per la simulazione di Monte Carlo? Posso avere molti nodi di calcolo (ad esempio 100) e devo generare milioni di numeri su ciascun nodo. Ho bisogno di una garanzia che una sequenza PRN su un nodo non si sovrappone alla sequenza PRN su un altro nodo.

Potrei generare tutto il PRN sul nodo radice, quindi inviarli ad altri nodi. Ma sarebbe troppo lento.
Potrei saltare a una distanza di conoscenza nella sequenza, su ciascun nodo. Ma esiste un tale algoritmo per Mersenne-twister o per qualsiasi altro buon PRNG, che può essere fatto con una ragionevole quantità di tempo e memoria?
Potrei usare diversi generatori su ciascun nodo. Ma è possibile con buoni generatori come Mersenne-Swister? Come potrebbe essere fatto?
Qualche altro però?

Soluzione

Non dovresti mai usare flussi casuali potenzialmente sovrapposti ottenuti dallo stesso flusso originale. Se non hai testato il flusso interleaved risultante, non hai idea della sua qualità statistica.

Per fortuna, Mersenne Twister (MT) ti aiuterà nel tuo compito di distribuzione. Usando il suo algoritmo dedicato, chiamato Creatore dinamico (DC di seguito), puoi creare generatori di numeri casuali indipendenti Ciò produrrà flussi casuali altamente indipendenti.

Ogni flusso verrà creato sul nodo che lo utilizzerà. Fondamentalmente, pensa a DC come a un costruttore nel paradigma orientato agli oggetti che crea diversi casi di MT. Ogni istanza diversa è progettata per produrre sequenze casuali altamente indipendenti.

Puoi trovare DC qui: http://www.math.sci.hishima-u.ac.jp/~m-mat/mt/dc/dc.html
È abbastanza semplice da usare e sarai in grado di correggere parametri diversi come il numero di diverse istanze MT che si desidera ottenere o il periodo di questi MT. A seconda del suo parametro di input, DC Will Runtime cambierà.

Oltre al readme che arriva con DC, dai un'occhiata al file example/new_example2.c nell'archivio DC. Mostra esempio di chiamate per ottenere sequenze indipendenti Dato un diverso identificatore di input, che è fondamentalmente ciò che devi identificare i lavori del cluster.

Infine, se hai intenzione di saperne di più su come utilizzare i PRNG in ambienti paralleli o distribuiti, ti suggerisco di leggere questi articoli scientifici:

Distribuzione pratica di flussi casuali per calcolo stocastico ad alte prestazioni, David RC Hill, in Conferenza internazionale su elaborazione e simulazione ad alte prestazioni (HPCS), 2010

Altri suggerimenti

Ok, rispondi #2 ;-)

Dirò ... mantienilo semplice. Basta usare un seme "corto" per innescare il MT (immagina che questo seme sia 2³² bit per mancanza di migliori restrizioni). Ciò presuppone che il seme corto generi stati di partenza MT "sufficientemente distribuiti" (ad es. init_genrand Nel codice nella mia altra risposta, si spera). Questo non garantisce uno stato di partenza altrettanto distribuito, ma piuttosto è "abbastanza buono", vedi sotto.

Ogni nodo utilizzerà la propria sequenza di semi che sono preselezionati (o un elenco di semi casuali che viene trasmessa o una formula come number_nodes * node_number * iteration). L'importante è che il seme "corto" iniziale non verrà mai riutilizzato tra i nodi.

Ogni nodo utilizzerà quindi un PRNG MT inizializzato con questo seme n volte in cui n <<< MT_period / max_value_of_short_seed (TT800 è 2⁸⁰⁰-1 e mt19937 è 2¹⁹⁹³⁷-1, Così n può ancora essere un molto largo numero). Dopo n Tempi, il nodo si sposta sul seme successivo nell'elenco scelto.

Anche se non (né posso) fornire una "garanzia" che nessun nodo avrà mai una sequenza duplicata contemporaneamente (o affatto), ecco cosa AMD dice sull'uso di diverse sede: (Ovviamente l'algoritmo di semina iniziale gioca un ruolo).

Dei quattro metodi per la creazione di più flussi qui descritti, questo è il meno soddisfacente ... Ad esempio, le sequenze generate da diversi punti di partenza possono sovrapporsi se i valori iniziali non sono abbastanza lontani. Il potenziale per sequenze sovrapposte è ridotto se il periodo del generatore utilizzato è grande. Sebbene non vi sia alcuna garanzia sull'indipendenza delle sequenze, a causa del suo periodo estremamente grande, è improbabile che l'uso del twister di Mersenne con valori iniziali casuali porti a problemi, soprattutto se il numero di sequenze richieste è piccolo ...

Codice felice.

Potrei saltare a una distanza di conoscenza nella sequenza, su ciascun nodo. Ma esiste un tale algoritmo per Mersenne-twister o per qualsiasi altro buon PRNG, che può essere fatto con una ragionevole quantità di tempo e memoria?

Sì, vedi http://theo.phys.sci.hishima-u.ac.jp/~ishikawa/prng/mt_stream_en.html. Questa è una soluzione eccellente per ottenere flussi di numeri casuali indipendenti. Facendo salti più grandi del numero di numeri casuali necessari da ciascun flusso per creare gli inizi di ogni flusso, i flussi non si sovrappongono.

Disclaimer: non sono sicuro di quale garanzia Mt in termini di sovrapposizione del ciclo quando si inizia da un "uint" arbitrario (o x, dove x è un valore arbitrario ma unico più piccolo), ma potrebbe valere la pena esaminare, come se fosse lì è una garanzia quindi potrebbe essere sufficiente iniziare ogni nodo su un diverso seme "uint" e il resto di questo post diventa in gran parte discutibile. (La lunghezza/periodo del ciclo di MT è sconcertante e dividere uint_max lascia ancora un incomprensibile - Tranne su carta- numero.)

Bene, ecco i miei commenti per rispondere ...

Mi piace l'approccio n. 2 con un insieme pre-generato di stati; Il MT in ciascun nodo viene quindi inizializzato con un dato stato di partenza.

Solo gli stati iniziali devono essere preservati, ovviamente, e una volta generati questi stati possono

Essere riutilizzato indefinitamente, se i requisiti sono soddisfatti o;
I prossimi stati possono essere generati in avanti su una scatola veloce esterna perché la simulazione è in esecuzione o;
I nodi possono riferire lo stato finale (se messaggistica affidabile e se la sequenza viene utilizzata alla stessa velocità tra i nodi e soddisfa i requisiti, ecc.)

Considerando che Mt lo è veloce da generare, Non consiglierei il numero 3 dall'alto perché è solo complicato e ha un numero di stringhe allegate. L'opzione n. 1 è semplice, ma potrebbe non essere abbastanza dinamica.

L'opzione n. 2 sembra un'ottima possibilità. Il server (una "macchina veloce", non necessariamente un nodo) deve trasmettere lo stato iniziale del prossimo "blocco di sequenza inutilizzato" (diciamo, un miliardo di cicli): il nodo userebbe il generatore per un miliardo di cicli prima di chiedere per un nuovo blocco. Questo lo renderebbe un ibrido di n. 1 nel post con messaggi molto rari.

Sul mio sistema, un duo Core2, posso generare un miliardo numeri casuali in 17 secondi utilizzando il codice fornito di seguito (funziona Linqpad). Non sono sicuro di quale variante MT sia.

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

Codice felice.

TRNG è un generatore di numeri casuali costruito specificamente con ambienti di cluster paralleli (in particolare è stato costruito per il Super computer Tina in Germania). Quindi è molto facile creare flussi di numeri casuali indipendenti e generare anche distribuzioni non standard. C'è un tutorial su come impostarlo qui:http://www.lindonslog.com/programming/parallel-random-number-generation-trng/

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow