Bucles paralelos y resultados aleatorios de resultados aleatorios

Question

Acabo de empezar a jugar con la Biblioteca de tareas paralelas, y encontré problemas interesantes; Tengo una idea general de lo que está pasando, pero me gustaría escuchar los comentarios de personas más competentes que yo para ayudar a entender lo que está sucediendo. Mis disculpas por el código algo largo.

Empecé con una simulación no paralelos de un paseo aleatorio:

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(); 

Entonces escribí mi primer intento de un circuito paralelo:

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(); 

Cuando me encontré con él en una máquina virtual configurado para usar solo 1 núcleo, observé una duración similar, pero las ejecuciones ya no se procesan en orden, no es una sorpresa.

Cuando lo ejecuté en una máquina de doble núcleo, las cosas salieron raras. No vi ninguna mejora en el tiempo, y observé algunos resultados muy extraños para cada carrera. La mayoría de las ejecuciones terminan con resultados de -1,000,000, (o muy cercanos), lo que indica que Random.Next está regresando 0 casi todo el tiempo.

Cuando hago el azar local para cada bucle, todo funciona muy bien, y tengo la mejora de la duración esperada:

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

Mi conjetura es que el problema tiene que ver con el hecho de que el objeto aleatorio se comparte entre los bucles, y tiene algún estado. La falta de mejora en la duración en la versión "paralela fallida" es de suponer que las llamadas a Random no se procesan en paralelo (aunque veo que la versión paralela usa ambos núcleos, mientras que el original no) . La pieza que realmente no entiendo es por qué los resultados de la simulación son lo que son.

Una preocupación aparte que tengo es que si uso instancias aleatorias locales para cada ciclo, puedo encontrarme con el problema de tener múltiples bucles comenzando con la misma inicialización (el problema que surge cuando genera múltiples Randoms demasiado cerca en el tiempo) , dando como resultado secuencias idénticas).

¡Cualquier idea sobre lo que está pasando sería muy valiosa para mí!

Answer 1

Ninguno de estos enfoques le dará números aleatorios realmente buenos.

Este blog cubre una gran cantidad de métodos para obtener los números aleatorios mejorado con Random

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

Estos pueden estar bien para muchos días para aplicaciones de uso diario.

Sin embargo, si utiliza el mismo generador de números aleatorios en múltiples hilos incluso con semillas diferentes, seguirá afectando la calidad de sus números aleatorios. Esto se debe a que está generando secuencias de números pseudoaleatorias que pueden superponerse.

Este video explica por qué en un poco más de detalle:

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

Si desea que los números realmente aleatorios, entonces usted realmente necesidad de utilizar el generador de números aleatorios cripto System.Security.Cryptography.RNGCryptoServiceProvider. Esto es threadsafe

Answer 2

La clase Random no es segura para subprocesos; si lo usa en múltiples hilos, puede estropearse.

Debe crear una instancia de Random por separado en cada subproceso, y asegúrese de que no terminen utilizando la misma inicialización. (por ejemplo, Environment.TickCount * Thread.CurrentThread.ManagedThreadId)

Answer 3

Un problema central:

• random.Next no es seguro para subprocesos.

dos ramificaciones:

1. calidad de la aleatoriedad es destruida por las condiciones de carrera.
2. El uso compartido falso destruye la escalabilidad en multinúcleos.

varias soluciones posibles:

• hacer un uso seguro de rosca: random.Next resuelve problema de calidad, pero no la escalabilidad.
• Usar múltiples PRNG: resuelve problemas de escalabilidad pero puede degradar la calidad.
• ...