Generadores de números pseudoaleatorios paralelos

20

Esta pregunta se relaciona principalmente con un problema práctico de ingeniería de software, pero me gustaría saber si los teóricos podrían proporcionar más información al respecto.


En pocas palabras, tengo una simulación de Monte Carlo que usa un generador de números pseudoaleatorio, y me gustaría paralelizarlo para que haya 1000 computadoras que ejecuten la misma simulación en paralelo. Por lo tanto, necesito 1000 secuencias independientes de números pseudoaleatorios.

¿Podemos tener 1000 flujos paralelos con las siguientes propiedades? Aquí debería ser un PRNG muy conocido y ampliamente estudiado con todo tipo de buenas propiedades teóricas y empíricas.X

  1. Las transmisiones son probablemente tan buenas como las que obtendría si simplemente usara y dividiera la transmisión generada por en 1000 transmisiones.XXX

  2. Generando el siguiente número en cualquier corriente es (casi) tan rápido como la generación de la siguiente número con .X

Dicho de otra manera: ¿podemos obtener múltiples transmisiones independientes "gratis"?

Por supuesto, si simplemente usamos , siempre descartando 999 números y escogiendo 1, entonces ciertamente tendríamos la propiedad 1, pero perderíamos en el tiempo de ejecución por el factor 1000.X

Una idea simple sería usar 1000 copias de , con semillas 1, 2, ..., 1000. Esto ciertamente sería rápido, pero no es obvio si los flujos tienen buenas propiedades estadísticas.X


Después de buscar en Google, he encontrado, por ejemplo, lo siguiente:

  • La biblioteca SPRNG parece estar diseñada exactamente para este propósito y es compatible con múltiples PRNG .

  • El tornado de Mersenne parece ser un PRNG popular hoy en día, y encontré algunas referencias a una variante que es capaz de producir múltiples flujos en paralelo.

Pero todo esto está tan lejos de mis propias áreas de investigación, que no pude entender qué es realmente el estado del arte y qué construcciones funcionan bien no solo en teoría sino también en la práctica.


Algunas aclaraciones: no necesito ningún tipo de propiedades criptográficas; Esto es para el cálculo científico. Necesitaré miles de millones de números aleatorios, por lo que podemos olvidar cualquier generador con un período de .<232

Editar: no puedo usar un verdadero RNG; Necesito un PRNG determinista. En primer lugar, ayuda mucho con la depuración y hace que todo sea repetible. En segundo lugar, me permite hacer, por ejemplo, la búsqueda de mediana de manera muy eficiente al explotar el hecho de que puedo usar el modelo de múltiples pasos (ver esta pregunta ).

Edición 2: hay una pregunta estrechamente relacionada @ StackOverflow: generador de números pseudoaleatorios para el entorno de clúster .

Jukka Suomela
fuente
66
¿Por qué no usarías el PRNG con semillas muestreadas independientemente? No entiendo cómo esto no satisface 1 y 2, ya que no requiere coordinación entre las diferentes máquinas1000
Sasho Nikolov
No soy un experto, pero recientemente (buscando información sobre una pregunta de TCS) encontré este hardware: idquantique.com/true-random-number-generator/… ... una placa PCI que puede generar un flujo de 16Mbits / seg. (cuánticos) bits aleatorios. ... puedes comprar un montón de ellos e implementar algunos servidores generadores de números aleatorios ... no es un gran enfoque teórico, pero los bits están garantizados para ser "buenos" :-) :-)
Marzio De Biasi
@Vor: Me gustaría mantener todo repetible y determinista. Dada una semilla fija, quiero obtener exactamente el mismo resultado si vuelvo a ejecutar el experimento. Y quiero poder ejecutar el mismo experimento en una sola máquina y obtener de nuevo los mismos resultados. (Por un lado, ayuda mucho al depurar algoritmos paralelos ...)
Jukka Suomela
@Jukka: ok! ... y supongo que almacenar miles de millones de bits salvajes descomprimidos junto con los resultados del experimento no es tan factible :-) ... ¡se necesita un experto en PRNG!
Marzio De Biasi
2
¡Gracias por las respuestas hasta ahora! Veamos si tenemos más participación con una recompensa ...
Jukka Suomela

Respuestas:

7

Puede utilizar una evolución del algoritmo Mersenne Twister desarrollado por Saito y Matsumoto:

Twister Mersenne rápido orientado a SIMD (SFMT)

SFMT es un generador de Registro de desplazamiento de retroalimentación lineal (LFSR) que genera un entero pseudoaleatorio de 128 bits en un solo paso. SFMT está diseñado con el paralelismo reciente de las CPU modernas, como la canalización en varias etapas y las instrucciones SIMD (por ejemplo, entero de 128 bits). Admite enteros de 32 y 64 bits, así como punto flotante de doble precisión como salida. SFMT es mucho más rápido que MT, en la mayoría de las plataformas. No solo se mejora la velocidad, sino también las dimensiones de las equidistribuciones con precisión de v-bit. Además, la recuperación del estado inicial en exceso 0 es mucho más rápida. Ver Tesis de Maestría de Mutsuo Saito para más detalles .

El período varía de a 2 216091 - 1 .2607122160911

El uso de un mismo generador de números al azar para generar múltiples flujos independientes cambiando los valores iniciales puede causar un problema (con una probabilidad insignificantemente pequeña). Para evitar el problema, se prefiere usar diferentes parámetros para cada generación. Esta técnica se llama creación dinámica de los parámetros MT.

En el código fuente SFMT puede encontrar algunos ejemplos de conjuntos de parámetros (de períodos variables) y un script awk para convertir un archivo CSV en un conjunto de parámetros compilable. También hay una herramienta llamada " Creación dinámica de generadores Mersenne Twister ".

Los autores desarrollaron recientemente otra versión modificada de Mersenne Twister, Mersenne Twister para procesadores gráficos , diseñada para ejecutarse en GPU y aprovechar sus hilos de ejecución paralelos nativos. La característica clave es la velocidad: enteros aleatorios cada 4.6ms en una GeForce GTX 260.5×107

Los períodos de secuencia generada son , 2 23209 - 1 y 2 44497 - 1 para la versión de 32 bits, y 2 23209 - 1 , 2 44497 - 1 , 2 110503 - 1 para la versión de 64 bits. Es compatible con 128 conjuntos de parámetros para cada período, en otras palabras, puede generar 128 secuencias de números pseudoaleatorios independientes para cada período. Hemos desarrollado Dynamic Creator para MTGP, que genera más conjuntos de parámetros2112131223209124449712232091244497121105031

De hecho, proporcionan una herramienta MTGPDC para crear hasta conjuntos de parámetros (es decir, flujos independientes).232

El algoritmo pasa las principales pruebas de aleatoriedad como Diehard y NIST.

También está disponible un documento preliminar sobre arXiv: una variante de Mersenne Twister adecuada para procesadores gráficos

Marzio De Biasi
fuente
Una herramienta relacionada pero más antigua es Matsumoto y Nishimura (1998): Creación dinámica de generadores de números pseudoaleatorios . Pero no he podido averiguar cuáles de estas herramientas son solo una prueba de concepto y cuáles son paquetes de software de gran uso industrial.
Jukka Suomela
@ Jukka: quizás puedas preguntarlo directamente a los autores del algoritmo MTGP. Desde su sitio: "... Cualquier comentario es bienvenido (envíe un correo electrónico a Mutsuo Saito, saito" en el signo "math.sci.hiroshima-u.ac.jp y m-mat" en el signo "math.sci.hiroshima- u.ac.jp) ... ". Quizás no sean 100% imparciales, pero seguramente conocen bien los puntos fuertes y débiles de MTGP, y pueden decirle si puede ser adecuado para sus propósitos.
Marzio De Biasi
Parece que Mersenne Twister + Dynamic Creation es la forma recomendada de hacerlo en Mathematica.
Jukka Suomela
@Jukka: el paquete MT + DC también se puede encontrar en el sitio de Matsumoto ( math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html ); y creo que MTGP es solo una variante adecuada para GPU. Por lo tanto, MT + DC parece una opción mejor (y probada / estable) (a menos que necesite absolutamente enteros aleatorios cada 4.6ms en cada transmisión :-))))5×107
Marzio De Biasi
@Vor: si edita su respuesta y reemplaza MTGP con dcmt , puedo aceptarlo.
Jukka Suomela
12

Parece que hay muchas formas de abordar este problema, pero una forma sencilla sería utilizar el Blum Blum Shub PRNG. Este PRNG se define por la relación de recurrencia , donde N es un semiprime. Para obtener un bit aleatorio de esto, simplemente puede tomar la paridad de bits de x i . Lo bueno de esto es que dado que x i + k = x 2 k i  mod  N = x 2 k  mod  λ ( N ) ixi+1=xi2 mod NNxi puede calcular directamente cualquier paso en la constante de tiempo en k (es decir, O ( log ( N ) 3 ) o más rápido dependiendo del algoritmo de multiplicación que utilice para el exponencial modular). Por lo tanto, si tienemáquinas M , entonces para la máquina indexada por y puede usar el generador x i + 1 , y = x 2 M mod  λ ( N ) i  mod  N , donde x 0 , y = xxi+k=xi2k mod N=xi2k mod λ(N)mod NkO(log(N)3)Myxi+1,y=xi2Mmod λ(N) mod N, dondex0es su semilla. Convenientemente, esto genera exactamente el mismo flujo de números como si usara un solo flujo y distribuye su salida a cada una de las máquinas.x0,y=x02y mod λ(N) mod Nx0

Sin embargo, este no es el PRNG más rápido, por lo que solo será útil si la sobrecarga de lo que esté haciendo en la simulación es significativamente mayor que el costo del PRNG. Sin embargo, vale la pena señalar que será mucho más rápido para ciertas combinaciones de y N que otras, particularmente si la representación binaria de 2 M  mod  λ ( N ) contiene pocos 1s o es pequeña.MN2M mod λ(N)

Joe Fitzsimons
fuente
1
Creo que sería más rápido dejar que cada máquina genere una porción contigua de la secuencia, espaciándolas tan separadas que no se crucen. De todos modos, usar Blum Blum Shub para aplicaciones no criptográficas me parece un poco exagerado.
Antonio Valerio Miceli-Barone
1
@Antonio: Sí, eso sería un poco más rápido, especialmente si sabe con anticipación cuántas pruebas necesita exactamente. Si no lo sabe, entonces creo que obtendrá la misma escala de cualquier manera. Wierdly Blum Blum Shub fue exactamente el PRNG que nos enseñaron en física computacional hace años. Si no lo está utilizando para fines criptográficos, puede usar un módulo mucho más pequeño, por lo que no es realmente tan lento, y para muchas tareas, será rápido en comparación con cualquier función de la variable aleatoria que necesite calcular.
Joe Fitzsimons
5

snX1000ns1,s2,,s10001i1000sin

X

siiX

Xs1i<j1000sisjs

MS Dousti
fuente
¿No es esencialmente el mismo enfoque que lo que sugirió @Antonio: usar un PRNG para generar semillas por sí mismo? Tengo un sentimiento un poco incómodo sobre esto ... Para dar un ejemplo trivial de lo que podría salir mal, considere un PRNG donde output = estado interno y la semilla simplemente establece el estado interno.
Jukka Suomela
@Jukka: Mi enfoque es similar al de Antonio, pero el mío es más general. El PRNG en su ejemplo (donde salida = estado interno) no parece ser criptográficamente seguro. Un PRNG es criptográficamente seguro si su salida es computacionalmente indistinguible de la distribución uniforme. Vea esto para más información. PD: El Blum-Blum-Shub PRNG satisface esta condición.
MS Dousti
2

fM=1000{0,1,,M1}jif(i+jM)M

Esto le dará un RNG criptográfico en cada proceso, pero no necesariamente conlleva un costo de rendimiento. AES es rápido si tiene hardware que lo admita, y ChaCha es rápido independientemente. Por supuesto, querrá medir esto en su configuración específica para estar seguro.

f

prf
fuente
Si no me importa la fuerza criptográfica, ¿cómo se compara ChaCha (contador) con, por ejemplo, Mersenne Twister? ¿Es más rápido o más lento? ¿Tiene al menos tan buenas propiedades estadísticas? Traté de buscar en Google, pero no pude encontrar ningún artículo que compare estos dos en un contexto no criptográfico.
Jukka Suomela
2

Ahora hay una función de salto para SFMT (una implementación rápida de Mersenne Twister).

Esto me permite inicializar 1000 MT para que no haya superposición de ciclos. Y SFMT debería ser más rápido que MTGP. Casi perfecto para mis propósitos.

Jukka Suomela
fuente
1

Solo puede usar 1000 instancias del Mersenne Twister inicializado con diferentes semillas.

Puede probar las semillas de otro Mersenne Twister o, para estar más seguro de su independencia, del generador de números pseudoaleatorios criptográficos del sistema operativo (/ dev / urandom en Linux).

El Mersenne Twister siempre funciona en la misma secuencia cíclica, la semilla controla dónde comienzas a generarlo. Con semillas muestreadas independientemente, cada generador comenzará en puntos diferentes, típicamente muy lejanos, con una probabilidad muy pequeña de intersección.

Antonio Valerio Miceli-Barone
fuente
¿Entonces MT tiene algunas propiedades especiales que garantizan que sembrar MT con otro MT tiene sentido?
Jukka Suomela
¿MT tiene alguna propiedad demostrable de pseudoaleatoriedad?
Sasho Nikolov
@ Jukka: no tengo conocimiento de ninguno. Es por eso que sugerí usar otro tipo de PRNG para la siembra si temes particularmente algún tipo extraño de correlaciones desconocidas.
Antonio Valerio Miceli-Barone
@Sasho: la página de Wikipedia menciona la distribución k y el período grande.
Antonio Valerio Miceli-Barone
1
kk