Posibles fuentes de semillas de números aleatorios

Question

Dos puntos: primero, el ejemplo está en Fortran, pero creo que debería ser válido para cualquier idioma; segundo, los generadores de números aleatorios incorporados no son realmente aleatorios y existen otros generadores, pero no estamos interesados ​​en usarlos para lo que estamos haciendo.

La mayoría de las discusiones sobre semillas aleatorias reconocen que si el programa no lo inicializa en tiempo de ejecución, entonces la semilla se genera en tiempo de compilación. Entonces, la misma secuencia de números se genera cada vez que se ejecuta el programa, lo que no es bueno para números aleatorios. Una forma de superar esto es sembrar el generador de números aleatorios con el reloj del sistema.

Sin embargo, cuando se ejecuta en paralelo con MPI en una máquina multi-core, el enfoque de reloj del sistema para nosotros generó los mismos tipos de problemas. Si bien las secuencias cambiaron de ejecución a ejecución, todos los procesadores obtuvieron el mismo reloj del sistema y, por lo tanto, la misma semilla aleatoria y las mismas secuencias.

así que considere el siguiente código de ejemplo:

PROGRAM clock_test 
    IMPLICIT NONE 
    INCLUDE "mpif.h" 
    INTEGER :: ierr, rank, clock, i, n, method 
    INTEGER, DIMENSION(:), ALLOCATABLE :: seed 
    REAL(KIND=8) :: random 
    INTEGER, PARAMETER :: OLD_METHOD = 0, & 
         NEW_METHOD = 1 

    CALL MPI_INIT(ierr) 

    CALL MPI_COMM_RANK(MPI_COMM_WORLD, rank, ierr) 

    CALL RANDOM_SEED(SIZE=n) 
    ALLOCATE(seed(n)) 

    DO method = 0, 1 
     SELECT CASE (method) 
     CASE (OLD_METHOD) 
     CALL SYSTEM_CLOCK(COUNT=clock) 
     seed = clock + 37 * (/ (i - 1, i = 1, n) /) 
     CALL RANDOM_SEED(put=seed) 
     CALL RANDOM_NUMBER(random) 

     WRITE(*,*) "OLD Rank, dev = ", rank, random 
     CASE (NEW_METHOD) 
     OPEN(89,FILE='/dev/urandom',ACCESS='stream',FORM='UNFORMATTED') 
     READ(89) seed 
     CLOSE(89) 
     CALL RANDOM_SEED(put=seed) 
     CALL RANDOM_NUMBER(random) 

     WRITE(*,*) "NEW Rank, dev = ", rank, random 
     END SELECT 
     CALL MPI_BARRIER(MPI_COMM_WORLD, ierr) 
    END DO 

    CALL MPI_FINALIZE(ierr) 
END PROGRAM clock_test 

que cuando se ejecutan en mi estación de trabajo con 2 núcleos, da:

OLD Rank, dev =   0 0.330676306089146  
OLD Rank, dev =   1 0.330676306089146  
NEW Rank, dev =   0 0.531503215980609  
NEW Rank, dev =   1 0.747413828750221  

Por lo tanto, hemos superado el problema del reloj mediante la lectura de la semilla de la /dev/urandom en lugar. De esta forma, cada núcleo obtiene su propio número aleatorio.

¿Qué otros enfoques de semilla existen que funcionen en un sistema MPI de múltiples núcleos y sigan siendo únicos en cada núcleo, desde la ejecución hasta la ejecución?

Answer 1

Si echa un vistazo en Random Numbers In Scientific Computing: An Introduction de Katzgrabber (que es una discusión excelente y lúcida de los pormenores del uso de PRNG para informática técnica), en paralelo sugieren utilizar una función hash de tiempo y PID para generar una semilla . Desde su sección 7.1:

long seedgen(void) { 
    long s, seed, pid; 

    pid = getpid(); 
    s = time (&seconds); /* get CPU seconds since 01/01/1970 */ 

    seed = abs(((s*181)*((pid-83)*359))%104729); 
    return seed; 
} 

por supuesto, en Fortran esto sería algo así como

function seedgen(pid) 
    use iso_fortran_env 
    implicit none 
    integer(kind=int64) :: seedgen 
    integer, intent(IN) :: pid 
    integer :: s 

    call system_clock(s) 
    seedgen = abs(mod((s*181)*((pid-83)*359), 104729)) 
end function seedgen 

También a veces es útil para poder pasar en el tiempo, en lugar de llamar desde dentro seedgen, para que cuando estés probando puedas darle valores fijos que luego generen una secuencia reproducible (== comprobable).

Answer 2

La hora del sistema generalmente se devuelve (o al menos se convierte fácilmente) en un tipo entero: simplemente agregue el rango del proceso al valor y utilícelo para inicializar el generador de números aleatorios.