¿Cómo generar números aleatorios en paralelo?

8 minutos de lectura

avatar de usuario
tomek tarczynski

Quiero generar números pseudoaleatorios en paralelo usando openMP, algo como esto:

int i;
#pragma omp parallel for
for (i=0;i<100;i++)
{
    printf("%d %d %d\n",i,omp_get_thread_num(),rand());
} 
return 0; 

Lo probé en Windows y obtuve una gran aceleración, pero cada subproceso generó exactamente los mismos números. Lo probé también en Linux y obtuve una gran desaceleración, la versión paralela en el procesador de 8 núcleos fue aproximadamente 10 veces más lenta que la secuencial, pero cada subproceso generó números diferentes.

¿Hay alguna manera de tener aceleración y números diferentes?

Editar 27.11.2010

Creo que lo he resuelto usando una idea de la publicación de Jonathan Dursi. Parece que el siguiente código funciona rápido tanto en Linux como en Windows. Los números también son pseudoaleatorios. ¿Qué piensa usted al respecto?

int seed[10];

int main(int argc, char **argv) 
{
int i,s;
for (i=0;i<10;i++)
    seed[i] = rand();

#pragma omp parallel private(s)
{
    s = seed[omp_get_thread_num()];
    #pragma omp for
    for (i=0;i<1000;i++)
    {
        printf("%d %d %d\n",i,omp_get_thread_num(),s);
        s=(s*17931+7391); // those numbers should be choosen more carefully
    }
    seed[omp_get_thread_num()] = s;
}
return 0; 
} 

PD.: Aún no he aceptado ninguna respuesta, porque necesito estar seguro de que esta idea es buena.

  • rand es un PRNG de muy mala calidad, solo debe usarse cuando la compatibilidad es un requisito (por ejemplo, para replicar una ejecución de simulación que usó exactamente este mismo PRNG malo). La mayoría de los sistemas operativos/bibliotecas proporcionan mejores PRNG (p. ej., FreeBSD tiene random, lrand48, arc4randometc.).

    – Dave C.

    2 de julio de 2019 a las 14:02

  • Además, considere un PRNG basado en contador como los descritos en el documento. “Números aleatorios paralelos: tan fácil como 1, 2, 3”.

    – Dave C.

    2 de julio de 2019 a las 14:04

avatar de usuario
Jonathan Dursi

Publicaré aquí lo que publiqué en Generación simultánea de números aleatorios:

Creo que está buscando rand_r(), que toma explícitamente el estado RNG actual como parámetro. Luego, cada subproceso debe tener su propia copia de los datos de inicialización (si desea que cada subproceso comience con la misma inicialización o con diferentes, depende de lo que esté haciendo, aquí desea que sean diferentes o obtendría la misma fila una y otra vez). Hay una discusión sobre rand_r() y la seguridad de subprocesos aquí: ¿si rand_r es realmente seguro para subprocesos? .

Supongamos que desea que cada subproceso tenga su semilla que comience con su número de subproceso (que probablemente no sea lo que desea, ya que daría los mismos resultados cada vez que se ejecuta con la misma cantidad de subprocesos, pero solo como ejemplo):

#pragma omp parallel default(none)
{
    int i;
    unsigned int myseed = omp_get_thread_num();
    #pragma omp for
    for(i=0; i<100; i++)
            printf("%d %d %d\n",i,omp_get_thread_num(),rand_r(&myseed));
}

Editar: Solo por broma, verificado para ver si lo anterior obtendría alguna aceleración. El código completo era

#define NRANDS 1000000
int main(int argc, char **argv) {

    struct timeval t;
    int a[NRANDS];

    tick(&t);
    #pragma omp parallel default(none) shared(a)
    {
        int i;
        unsigned int myseed = omp_get_thread_num();
        #pragma omp for
        for(i=0; i<NRANDS; i++)
                a[i] = rand_r(&myseed);
    }
    double sum = 0.;
    double time=tock(&t);
    for (long int i=0; i<NRANDS; i++) {
        sum += a[i];
    }
    printf("Time = %lf, sum = %lf\n", time, sum);

    return 0;
}

donde el tic y el tac son solo envoltorios para gettimeofday()y tock() devuelve la diferencia en segundos. Sum se imprime solo para asegurarse de que nada se optimice y para demostrar un pequeño punto; obtendrá diferentes números con diferentes números de subprocesos porque cada subproceso obtiene su propio número de subproceso como semilla; si ejecuta el mismo código una y otra vez con la misma cantidad de hilos, obtendrá la misma suma, por la misma razón. De todos modos, el tiempo (ejecutándose en una caja nehalem de 8 núcleos sin otros usuarios):

$ export OMP_NUM_THREADS=1
$ ./rand
Time = 0.008639, sum = 1074808568711883.000000

$ export OMP_NUM_THREADS=2
$ ./rand
Time = 0.006274, sum = 1074093295878604.000000

$ export OMP_NUM_THREADS=4
$ ./rand
Time = 0.005335, sum = 1073422298606608.000000

$ export OMP_NUM_THREADS=8
$ ./rand
Time = 0.004163, sum = 1073971133482410.000000

Así que acelera, si no genial; como señala @ruslik, este no es realmente un proceso intensivo en computación, y otros problemas como el ancho de banda de la memoria comienzan a jugar un papel. Por lo tanto, solo un poco más de 2x de aceleración en 8 núcleos.

  • +1. Modifiqué un poco su solución y parece funcionar bien tanto en Linux como en Windows.

    –Tomek Tarczynski

    27 de noviembre de 2010 a las 10:11

  • Como principiante en openmp, tenía curiosidad por qué declaró explícitamente “int i” antes de inicializar en el ciclo for paralelo. ¿Algo saldría mal si inicializara “i” en el bucle for?

    – Televisión

    21 de mayo de 2019 a las 10:48

No puedes usar la C rand() función de múltiples subprocesos; esto da como resultado un comportamiento indefinido. Algunas implementaciones pueden darte bloqueo (lo que lo hará lento); otros pueden permitir que los subprocesos golpeen el estado de los demás, posiblemente bloqueando su programa o simplemente dando números aleatorios “malos”.

Para resolver el problema, escriba su propia implementación de PRNG o use una existente que permita a la persona que llama almacenar y pasar el estado a la función iteradora de PRNG.

  • +1. Muy bien. La idea general es que rand() (y otros) bloquearán el acceso forzando efectivamente a los subprocesos a esperar (haciendo que la implementación sea cercana a un solo subproceso o incluso más lenta) pero nunca apuntando a la posibilidad de “… golpear el estado del otro, posiblemente bloqueando su programa “que vi en acción!

    – S Chepurin

    08/04/2013 a las 14:24


Obtenga cada subproceso para establecer una semilla diferente en función de su identificación de subproceso, por ejemplo srand(omp_get_thread_num() * 1000);

  • Es casi seguro que esto no eliminará las ralentizaciones en Linux si no hay alguna lógica que verifique si la semilla se inicializó en todos los subprocesos.

    – Axel Gneiting

    26 de noviembre de 2010 a las 18:05

  • Explicación: software.intel.com/en-us/blogs/2009/11/05/…

    – chrisaycock

    26 de noviembre de 2010 a las 18:12

  • @Axel Probablemente se deba a que rand() tiene una operación atómica que bloquea. Tendrás que buscar un RNG sin bloqueo.

    – moinudín

    26 de noviembre de 2010 a las 18:26

  • Intenté rand_r() para ver si una versión reentrante era más rápida (sin bloqueo), pero tomó la misma cantidad de tiempo en mi sistema.

    – chrisaycock

    26 de noviembre de 2010 a las 18:29


  • rand no necesariamente bloquea, y no debería hacerlo. Llamarlo desde múltiples subprocesos da como resultado comportamiento indefinido.

    – R.. GitHub DEJA DE AYUDAR A ICE

    26 de noviembre de 2010 a las 18:59

Eso parece rand tiene un estado compartido global entre todos los subprocesos en Linux y un estado de almacenamiento local de subprocesos para él en Windows. El estado compartido en Linux está provocando su ralentización debido a la sincronización necesaria.

No creo que haya una forma portátil en la biblioteca C para usar el paralelo RNG en múltiples subprocesos, por lo que necesita otro. Podrías usar un Tornado de Mersenne. Como dijo marcog, debe inicializar la semilla para cada hilo de manera diferente.

En linux/unix puedes usar

long jrand48(unsigned short xsubi[3]);

donde xsubi[3] codifica el estado del generador de números aleatorios, así:

#include<stdio.h>
#include<stdlib.h>
#include <algorithm> 
int main() {
  unsigned short *xsub;
#pragma omp parallel private(xsub)
  {  
    xsub = new unsigned short[3];
    xsub[0]=xsub[1]=xsub[2]= 3+omp_get_thread_num();
    int j;
#pragma omp for
    for(j=0;j<10;j++) 
      printf("%d [%d] %ld\n", j, omp_get_thread_num(), jrand48(xsub));
  }
}

compilar con

g++-mp-4.4 -Wall -Wextra -O2 -march=native -fopenmp -D_GLIBCXX_PARALLEL jrand.cc -o jrand

(reemplace g++-mp-4.4 con lo que necesite para llamar a g++ versión 4.4 o 4.3) y obtendrá

$ ./jrand 
0 [0] 1344229389
1 [0] 1845350537
2 [0] 229759373
3 [0] 1219688060
4 [0] -553792943
5 [1] 360650087
6 [1] -404254894
7 [1] 1678400333
8 [1] 1373359290
9 [1] 171280263

es decir, 10 números pseudoaleatorios diferentes sin bloqueo mutex ni condiciones de carrera.

  • ¿Podría elaborar un poco su respuesta? Nunca he oído hablar de jrand48, y supongo que esta función no es una biblioteca estándar.

    –Tomek Tarczynski

    5 de enero de 2011 a las 22:15

  • jrand48 está en la “familia” de drand48() y lrand48(). Es parte de la “Biblioteca C estándar (libc, -lc)”, de ahí el #include.

    –Riko Jacob

    5 de enero de 2011 a las 23:04


avatar de usuario
ruso

Los números aleatorios se pueden generar muy rápido, por lo que normalmente la memoria sería el cuello de botella. Al dividir esta tarea entre varios subprocesos, crea gastos adicionales de comunicación y sincronización (y la sincronización de cachés de diferentes núcleos no es barata).

Sería mejor usar un solo hilo con un mejor random() función.

  • ¿Podría elaborar un poco su respuesta? Nunca he oído hablar de jrand48, y supongo que esta función no es una biblioteca estándar.

    –Tomek Tarczynski

    5 de enero de 2011 a las 22:15

  • jrand48 está en la “familia” de drand48() y lrand48(). Es parte de la “Biblioteca C estándar (libc, -lc)”, de ahí el #include.

    –Riko Jacob

    5 de enero de 2011 a las 23:04


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad