c++ - Números aleatorios para múltiples hilos

multithreading boost

Question

Problema

Tengo la intención de escribir una aplicación C ++ 11 para Linux que hace alguna simulación numérica (no criptografía) basada en aproximadamente un millón de números pseudoaleatorios de 32 bits. Para acelerar las cosas, me gustaría realizar la simulación en subprocesos paralelos utilizando todos los núcleos de una CPU de escritorio. Me gustaría usar el Mersenne Twister mt19937 proporcionado por boost como PRNG, y supongo que por motivos de rendimiento debería tener uno de esos PRNG por hilo. Ahora no estoy seguro de cómo sembrarlos para evitar generar la misma subsecuencia de números aleatorios en múltiples hilos.

Alternativas

Estas son las alternativas que he pensado hasta ahora:

1. Sembrar el PRNG para cada hilo independientemente de /dev/urandom .

   Estoy un poco preocupado por el caso cuando el conjunto de entropía del sistema se agota, ya que no sé cómo funciona el PRNG interno del sistema. ¿Podría suceder que accidentalmente obtenga semillas consecutivas que identifiquen exactamente estados consecutivos de Mersenne Twister, debido a que /dev/urandom está usando un Mersenne Twister mismo? Probablemente muy relacionado con mis preocupaciones para el siguiente punto.

2. Siembre un PRNG de /dev/urandom y los otros de ese primero.

   Básicamente la misma preocupación también: ¿es bueno o malo usar un PRNG para sembrar otro que use el mismo algoritmo? O en otras palabras, ¿leer 625 enteros de 32 bits de un mt19937 corresponde directamente al estado interno del generador mt19937 en cualquier punto de esta generación?

3. Sembrar otros desde el principio con información que no sea de Mersenne.

   Como usar el mismo algoritmo para generar números aleatorios y generar la semilla inicial parece de alguna manera como una mala idea, pensé en introducir algún elemento que no dependa del algoritmo de Mersenne Twister. Por ejemplo, podría XOR el ID del hilo en cada elemento del vector inicial de semillas. ¿Eso mejora las cosas?

4. Comparta un PRNG entre hilos.

   Esto aseguraría que solo haya una secuencia, con todas las propiedades conocidas y deseables de Mersenne Twister. Pero el bloqueo requerido para controlar el acceso a ese generador me preocupa un poco. Como no he encontrado evidencia de lo contrario, supongo que yo, como usuario de la biblioteca, sería responsable de evitar el acceso concurrente al PRNG.

5. Pregenera todos los números aleatorios.

   Esto tendría un hilo que generara todos los números aleatorios 1M requeridos por adelantado, para ser usados ​​posteriormente por los diferentes hilos. El requisito de memoria de 4M sería pequeño en comparación con el de la aplicación general. Lo que más me preocupa en este enfoque es que la generación de números aleatorios en sí misma no es concurrente. Este enfoque completo tampoco se escala demasiado bien.

Preguntas

¿Cuál de estos enfoques sugeriría y por qué? ¿O tienes una sugerencia diferente?

¿Sabes cuáles de mis inquietudes están justificadas y cuáles simplemente se deben a mi falta de conocimiento sobre cómo funcionan realmente las cosas?

Answer 1

Eche un vistazo al siguiente documento: Creación dinámica de generadores de números pseudoaleatorios y la implementación que lo acompaña: Dynamic Creator . Aborda este problema exacto.

Answer 2

Existe una implementación (y un artículo publicado) específicamente sobre el uso del Mersenne Twister para el cálculo paralelo. Es por los autores originales del MT. Se refieren a él como "Creador dinámico", y se puede encontrar aquí:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html

Ese sería un muy buen lugar para estudiar su uso específico de MT19937, particularmente el papel allí.

Answer 3

Hilo de semilla 1 con 1, Hilo de semilla 2 con 2, etc.

Si necesita Monte Carlo esto le dará resultados reproducibles, es fácil de rastrear e implementar.

Answer 4

Me gustaría ir con # 1, sembrar cada prng de urandom. Esto garantiza que los estados sean totalmente independientes (en la medida en que los datos de inicialización sean independientes). Por lo general, habrá mucha entropía disponible a menos que tenga muchos hilos. Además, dependiendo del algoritmo utilizado para / dev / urandom, casi seguro que no necesita preocuparse por ello.

Entonces puede usar algo como lo siguiente para crear cada prng:

#include <random>
std::mt19937 get_prng() {
std::random_device r;
std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
return std::mt19937(seed);
}

Debe verificar que su implementación de std::random_device de /dev/urandom bajo su configuración. Y si usa / dev / urandom de forma predeterminada, entonces generalmente puede decir std::random_device("/dev/random") si desea usar / dev / random en su lugar.

Answer 5

Puede usar un PRNG con una estructura algebraica diferente para sembrar los diferentes PRNG. Por ejemplo, una secuencia de hash MD5.

Sin embargo, optaría por el n. ° 5. Si funciona, entonces está bien. Si no lo hace, aún puede optimizarlo.

El punto es crear un buen PRNG es mucho más difícil de lo que uno podría esperar. Un buen PRNG para aplicaciones con hilos probablemente sea algo que todavía está sujeto a investigación.

Si la cantidad de CPU es lo suficientemente baja, podría salirse con la suya. Por ejemplo, si tiene 4 núcleos, inicialice todos con los mismos valores, pero avance el núcleo 1 PRNG por 1, # 2 por y # 3 por 3. Luego avance siempre 4 pasos cuando necesite un nuevo número.

Answer 6

Si realmente quiere ser matemáticamente correcto, use las funciones de salto proporcionadas por los autores del algoritmo SFMT. Las funciones de salto garantizan el número mínimo de secuencias entre dos flujos de PRNG diferentes.

En términos prácticos, sin embargo, una inicialización / dev / urandom será suficiente.

Answer 7

Usaría una instancia para sembrar los otros. Estoy bastante seguro de que puedes hacerlo con bastante facilidad.

• Incluso pequeños cambios en el espacio de estado causan cambios bastante grandes en sentido descendente: si puedes asegurarte de que no tienen exactamente el mismo espacio de inicio (y no tienen el mismo prefijo de estado), no me preocuparía producir números idénticos. Por ejemplo, usar solo los valores 1,2,3 para sembrar tres hilos funcionaría bien; ni siquiera es necesario sembrar todo el espacio. Otra ventaja: mediante el uso de semillas claramente predecibles, se puede desacreditar fácilmente la idea de que estás eligiendo cualquier carrera (suponiendo que estés tratando de demostrar algo).
• Es trivial sembrar de una manera que signifique que los "niños" resultantes carecen de correlación. Simplemente itere de forma amplia; es decir, si desea sembrar valores N x 623 int, no sembrar 623 valores secuencialmente, sino que elija el primer N y distribuya, luego el siguiente N, etc. Incluso si hay alguna correlación entre la sembradora y los hijos, la correlación entre el varios niños deben ser prácticamente inexistentes, y eso es todo lo que te importa.
• Preferiría un algoritmo que permita la ejecución determinista siempre que sea posible, por lo que depender de urandom no es atractivo. Esto hace que la depuración sea más fácil.
• Finalmente, y obviamente - prueba. Estos PRNG son bastante robustos, pero analice los resultados y realice algunas pruebas de correlación inspiradas en lo que está simulando. La mayoría de los problemas deberían ser obvios: o se ha seminado mal y hay subsecuencias repetitivas obvias, se ha sembrado bien y la calidad viene dictada por las limitaciones de PRNG.
• Para las ejecuciones finales, una vez que haya finalizado la prueba, puede sembrar el primero de 623 valores de estado usando urandom para tranquilidad y / o la identificación del hilo.

Answer 8

Yo diría que # 3 es el ganador. Sembrar cada hilo con algo como el ID de proceso o ID de hilo; si bien es técnicamente posible, podrías tener superposición, es muy poco probable. Incluso los números consecutivos no deberían relacionarse en términos de semillas una vez que salgas de un solo dígito (no conozco el algoritmo de Twister, pero el peor PRNG que he visto estaba bien por encima de 7). Un millón de PRNG no es tan grande en comparación con el alcance de la mayoría de las ecuaciones de PRNG.

Finalmente, puedes verificar con bastante facilidad. Compruebe la última semilla generada por cada hilo contra todos los números en cada uno de los hilos. Si la semilla aparece en el hilo, entonces verifique el número anterior generado en cada hilo; si también coinciden, entonces tienes una colisión y necesitas volver a sembrar tus secuencias y volver a intentarlo.