mercredi 25 mai 2022

Forking a random number generator deterministically?

I'm using std::mt19937 to produce deterministic random numbers. I'd like to pass it to functions so I can control their source of randomness. I could do int foo(std::mt19937& rng);, but I want to call foo and bar in parallel, so that won't work. Even if I put the generation function behind a mutex (so each call to operator() did std::lock_guard lock(mutex); return rng();), calling foo and bar in parallel wouldn't be deterministic due to the race on the mutex.

I feel like conceptually I should be able to do this:

auto fooRNG = std::mt19937(rng()); // Seed a RNG with the output of `rng`.
auto barRNG = std::mt19937(rng());
parallel_invoke([&] { fooResult = foo(fooRNG); },
                [&] { barResult = bar(barRNG); });

where I "fork" rng into two new ones with different seeds. Since fooRNG and barRNG are seeded deterministically, they should be random and independent.

  1. Is this general gist viable?
  2. Is this particular implementation sufficient (I doubt it)?

Extended question: Suppose I want to call baz(int n, std::mt19937&) massively in parallel over a range of indexed values, something like

auto seed = rng();
parallel_for(range(0, 1 << 20),
             [&](int i) {
    auto thisRNG = std::mt19937(seed ^ i); // Deterministically set up RNGs in parallel?
    baz(i, thisRng);

});

something like that should work, right? That is, provided we give it enough bits of state?




Aucun commentaire:

Enregistrer un commentaire