Générateur de nombres pseudo-aléatoires pour l'environnement de cluster

https://stackoverflow.com/questions/6367058

28-10-2019
|

Question

Comment générer des nombres pseudo-aléatoires indépendants sur un cluster, pour une simulation de Monte Carlo par exemple?Je peux avoir de nombreux nœuds de calcul (par exemple 100), et j'ai besoin de générer des millions de nombres sur chaque nœud.J'ai besoin d'une garantie qu'une séquence PRN sur un nœud ne chevauchera pas la séquence PRN sur un autre nœud.

Je pourrais générer tous les PRN sur le nœud racine, puis les envoyer à d'autres nœuds.Mais ce serait beaucoup trop lent.
Je pourrais sauter à une distance connue dans la séquence, sur chaque nœud.Mais existe-t-il un tel algorithme pour Mersenne-Twister ou pour tout autre bon PRNG, qui peut être fait avec un temps et une mémoire raisonnables?
Je pourrais utiliser différents générateurs sur chaque nœud.Mais est-ce possible avec de bons générateurs comme Mersenne-Twister?Comment cela pourrait-il être fait?
Un autre cependant?

La solution

Vous ne devez jamais utiliser de flux aléatoires potentiellement superposés obtenus à partir du même flux d'origine. Si vous n'avez pas testé le flux entrelacé résultant, vous n'avez aucune idée de sa qualité statistique.

Heureusement, Mersenne Twister (MT) vous aidera dans votre tâche de distribution. En utilisant son algorithme dédié, appelé Dynamic Creator (ci-après DC), vous pouvez créer des générateurs de nombres aléatoires indépendants qui produiront des flux aléatoires hautement indépendants.

Chaque flux sera créé sur le nœud qui l'utilisera. En gros, pensez à DC comme un constructeur dans un paradigme orienté objet qui crée différentes instances de MT. Chaque instance différente est conçue pour produire des séquences aléatoires hautement indépendantes.

Vous pouvez trouver DC ici: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html
C'est assez simple à utiliser et vous pourrez fixer différents paramètres tels que le nombre d'instances MT différentes que vous souhaitez obtenir ou la période de ces MT. En fonction de son paramètre d'entrée, le DC changera.

En plus du fichier README fourni avec DC, jetez un œil au fichier example/new_example2.c dans l'archive DC. Il montre des exemples d'appels pour obtenir des séquences indépendantes avec un identifiant d'entrée différent , qui est essentiellement ce dont vous avez besoin pour identifier les tâches de cluster.

Enfin, si vous avez l'intention d'en savoir plus sur l'utilisation des PRNG dans des environnements parallèles ou distribués, je vous suggère de lire ces articles scientifiques:

< Distribution pratique de flux aléatoires pour le calcul stochastique haute performance , David RC Hill, dans International Conference on High Performance Computing and Simulation (HPCS) , 2010

Autres conseils

D'accord, répondez # 2 ;-)

Je vais dire ... restez simple. Utilisez simplement une graine "courte" pour amorcer le MT (imaginez que cette graine est de 2 ³² bits faute de meilleure restriction). Cela suppose que la graine courte génère des états de départ MT "suffisamment distribués" (par exemple, init_genrand dans le code de mon autre réponse, espérons-le). Cela ne garantit pas un état de départ équitablement distribué mais plutôt "assez bon", voir ci-dessous.

Chaque nœud utilisera sa propre séquence de graines qui sont présélectionnées (soit une liste de graines aléatoires qui est transmise, soit une formule comme number_nodes * node_number * iteration). L'important est que la graine "courte" initiale ne soit jamais réutilisée entre les nœuds .

Chaque nœud utilisera alors un MT PRNG initialisé avec cette graine n fois où n <<< MT_period / max_value_of_short_seed ( TT800 vaut 2 ⁸⁰⁰ -1 et MT19937 vaut 2 ¹⁹⁹³⁷ -1 , donc n peut toujours être un nombre très grand ). Après les temps n, le nœud passe à la graine suivante dans la liste choisie.

Bien que je ne puisse pas (et ne peux pas) fournir de "garantie" qu'aucun nœud n'aura jamais de séquence dupliquée en même temps (ou pas du tout), voici ce que AMD dit à propos de l'utilisation de différents Seends : (De toute évidence, l'algorithme d'amorçage initial joue un rôle).

Des quatre méthodes de création de flux multiples décrites ici, celle-ci est la moins satisfaisante ... Par exemple, les séquences générées à partir de différents points de départ peuvent se chevaucher si les valeurs initiales ne sont pas suffisamment éloignées. Le potentiel de chevauchement des séquences est réduit si la période du générateur utilisé est grande. Bien qu'il n'y ait aucune garantie de l'indépendance des séquences, en raison de sa période extrêmement longue, il est peu probable que l'utilisation du Mersenne Twister avec des valeurs de départ aléatoires pose des problèmes , surtout si le nombre de séquences requis est petit ...

Bon codage.

Je pourrais sauter à une distance connue dans la séquence, sur chaque nœud.Mais est il existe un tel algorithme pour Mersenne-Twister ou pour tout autre bien PRNG, ce qui peut être fait avec un temps et une mémoire raisonnables?

Oui, voir http:// theo.phys.sci.hiroshima-u.ac.jp/~ishikawa/PRNG/mt_stream_en.html .C'est une excellente solution pour obtenir des flux de nombres aléatoires indépendants.En effectuant des sauts plus grands que le nombre de nombres aléatoires nécessaires pour chaque flux pour créer les débuts de chaque flux, les flux ne se chevaucheront pas.

Clause de non-responsabilité: je ne suis pas sûr de la garantie que MT a en termes de chevauchement de cycles en partant d'une graine arbitraire "uint" (ou x, où x est une valeur arbitraire mais unique plus petite), mais cela peut valoir la peine d'être examiné, comme s'il y avait une garantie, il peut être suffisant de simplement démarrer chaque nœud sur une graine "uint" différente et le reste de ce message devient largement discutable. ( La durée / période du cycle de MT est décalée et se divise out UINT_MAX laisse toujours un incompréhensible - sauf sur papier - nombre.)

Eh bien, voici mes commentaires pour répondre ...

J'aime l'approche n ° 2 avec un ensemble d'états pré-générés; le MT dans chaque nœud est alors initialisé avec un état de départ donné.

Seuls les états initiaux doivent être préservés, bien sûr, et une fois que cela est généré, ces états peuvent

Être réutilisé indéfiniment, si les conditions sont remplies, ou;
Les états suivants peuvent être générés en avant sur une boîte rapide externe pourquoi la simulation est en cours d'exécution ou;
Les nœuds peuvent rendre compte de l'état final (si la messagerie est fiable, et si la séquence est utilisée au même rythme entre les nœuds, et répond aux exigences, etc.)

Étant donné que MT est rapide à générer , je ne recommanderais pas le n ° 3 ci-dessus car il est simplement compliqué et comporte un certain nombre de conditions. L'option 1 est simple, mais peut-être pas assez dynamique.

L'option n ° 2 semble être une très bonne possibilité. Le serveur (une "machine rapide", pas nécessairement un nœud) n'a besoin que de transmettre l'état de départ du "bloc de séquence inutilisé" suivant (par exemple, un milliard de cycles) - le nœud utiliserait le générateur pendant un milliard de cycles avant de demander pour un nouveau bloc. Cela en ferait un hybride n ° 1 dans la publication avec des messages très peu fréquents.

Sur mon système, un Core2 Duo, je peux générer un milliard de nombres aléatoires en 17 secondes en utilisant le code fourni ci-dessous (il fonctionne dans LINQPad ). Je ne sais pas de quelle variante MT il s'agit.

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

Bon codage.

TRNG est un générateur de nombres aléatoires spécialement conçu pour les environnements de cluster parallèles (en particulier, il a été conçu pour le super ordinateur TINA en Allemagne).Il est donc très facile de créer des flux de nombres aléatoires indépendants et de générer également des distributions non standard.Il y a un tutoriel sur la façon de le configurer ici: http://www.lindonslog.com/programming/parallel-random-number-generation-trng /

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow