Loop paralleli e Casuale producono risultati dispari

Question

Ho appena iniziato a giocare con la libreria parallela Task e ho riscontrato problemi interessanti; Ho un'idea generale di cosa sta succedendo, ma vorrei ricevere commenti da persone più competenti di me per aiutare a capire cosa sta succedendo. Le mie scuse per il codice un po 'lungo.

Ho iniziato con una simulazione non parallela di un random walk:

var random = new Random(); 
Stopwatch stopwatch = new Stopwatch(); 

stopwatch.Start(); 

var simulations = new List<int>(); 
for (var run = 0; run < 20; run++) 
{ 
    var position = 0; 
    for (var step = 0; step < 10000000; step++) 
    { 
     if (random.Next(0, 2) == 0) 
     { 
      position--; 
     } 
     else 
     { 
      position++; 
     } 
    } 

    Console.WriteLine(string.Format("Terminated run {0} at position {1}.", run, position)); 
    simulations.Add(position); 
} 

Console.WriteLine(string.Format("Average position: {0} .", simulations.Average())); 
stopwatch.Stop(); 

Console.WriteLine(string.Format("Time elapsed: {0}", stopwatch.ElapsedMilliseconds)); 
Console.ReadLine(); 

Allora ho scritto il mio primo tentativo di un ciclo parallelo:

var localRandom = new Random(); 

stopwatch.Reset(); 
stopwatch.Start(); 

var parallelSimulations = new List<int>(); 
Parallel.For(0, 20, run => 
{ 
    var position = 0; 
    for (var step = 0; step < 10000000; step++) 
    { 
     if (localRandom.Next(0, 2) == 0) 
     { 
      position--; 
     } 
     else 
     { 
      position++; 
     } 
    } 

    Console.WriteLine(string.Format("Terminated run {0} at position {1}.", run, position)); 
    parallelSimulations.Add(position); 
}); 


Console.WriteLine(string.Format("Average position: {0} .", parallelSimulations.Average())); 
stopwatch.Stop(); 

Console.WriteLine(string.Format("Time elapsed: {0}", stopwatch.ElapsedMilliseconds)); 

Console.ReadLine(); 

Quando ho eseguito su una macchina virtuale impostato per utilizzare solo 1 core, ho osservato una durata simile, ma le esecuzioni non vengono più elaborate in ordine - nessuna sorpresa.

Quando l'ho eseguito su una macchina dual-core, le cose sono andate dispari. Non ho visto alcun miglioramento nel tempo e ho osservato alcuni risultati molto strani per ogni corsa. La maggior parte delle esecuzioni termina con risultati di -1.000.000 (o molto vicini), il che indica che Random.Next restituisce 0 quasi sempre.

Quando faccio il locale casuale per ogni ciclo, tutto funziona bene, e ottengo il miglioramento durata prevista:

Parallel.For(0, 20, run => 
     { 
      var localRandom = new Random(); 
      var position = 0; 

La mia ipotesi è che il problema ha a che fare con il fatto che l'oggetto a caso è condiviso tra i loop e ha uno stato. La mancanza di miglioramento della durata nella versione "failing parallel" è dovuta al fatto che le chiamate a Random non vengono elaborate in parallelo (anche se vedo che la versione parallela usa entrambi i core, mentre l'originale no) . Il pezzo che davvero non capisco è perché i risultati della simulazione siano quello che sono.

Una preoccupazione distinta che ho è che se utilizzo le istanze Random locali per ogni ciclo, potrei incorrere nel problema di avere cicli multipli che iniziano con lo stesso seme (il problema che si ottiene quando si generano più Random troppo vicini nel tempo , risultante in sequenze identiche).

Qualsiasi intuizione in quello che sta succedendo sarebbe molto preziosa per me!

Answer 1

Nessuno di questi approcci ti fornirà numeri casuali veramente validi.

Questo post del blog copre un sacco di approcci per ottenere numeri più casuali con Random

http://blogs.msdn.com/b/pfxteam/archive/2009/02/19/9434171.aspx

Questi possono andare bene per molti giorni per le applicazioni al giorno.

Tuttavia, se si utilizza lo stesso generatore di numeri casuali su più thread anche con semi diversi, si avrà comunque un impatto sulla qualità dei numeri casuali. Questo perché stai generando sequenze di numeri pseudo-casuali che potrebbero sovrapporsi.

Questo video spiega perché in un po 'più in dettaglio:

http://software.intel.com/en-us/videos/tim-mattson-use-and-abuse-of-random-numbers/

Se si vuole veramente i numeri casuali, allora si ha realmente bisogno di utilizzare la crittografia generatore di numeri casuali System.Security.Cryptography.RNGCryptoServiceProvider. Questo è sicuro.

Answer 2

La classe Random non è thread-safe; se lo usi su più thread, può essere incasinato.

È necessario creare un'istanza separata Random su ciascun thread e assicurarsi che non finiscano con lo stesso seme. (ad esempio, Environment.TickCount * Thread.CurrentThread.ManagedThreadId)

Answer 3

Un problema centrale:

• random.Next non è thread sicuro.

due ramificazioni:

1. Qualità della casualità viene distrutta da condizioni di gara.
2. La condivisione errata distrugge la scalabilità sui multicorpi.

diverse possibili soluzioni:

• messa in sicurezza random.Next discussione: risolve problema di qualità ma non scalabilità.
• Utilizzare più PRNG: risolve il problema di scalabilità ma può peggiorare la qualità.
• ...