génération de nombres aléatoires thread-safe pour l'intégration Monte-Carlo

Question

Im essayant d'écrire quelque chose qui calcule très rapidement des nombres aléatoires et peuvent être appliqués sur plusieurs threads. Mon code actuel est:

/* Approximating PI using a Monte-Carlo method. */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <omp.h>
#define N 1000000000  /* As lareg as possible for increased accuracy */

double random_function(void);

int main(void)
{
   int i = 0;
    double X, Y;
   double count_inside_temp = 0.0, count_inside = 0.0;
   unsigned int th_id = omp_get_thread_num();
   #pragma omp parallel private(i, X, Y) firstprivate(count_inside_temp)
   {
      srand(th_id);
      #pragma omp for schedule(static)
      for (i = 0; i <= N; i++) {
         X = 2.0 * random_function() - 1.0;
         Y = 2.0 * random_function() - 1.0;
         if ((X * X) + (Y * Y) < 1.0) {
        count_inside_temp += 1.0;
     }
  }
  #pragma omp atomic
      count_inside += count_inside_temp;
   }
   printf("Approximation to PI is = %.10lf\n", (count_inside * 4.0)/ N);
   return 0;
}

double random_function(void)
{
   return ((double) rand() / (double) RAND_MAX);
}

Cela fonctionne, mais d'observer un gestionnaire de ressources Je sais que ne pas utiliser tous les fils. Est-ce que rand () travail pour le code multithread? Et sinon est-il une bonne alternative? Merci beaucoup. Jack

Answer 1

est-fil rand() sécurité? Peut-être, peut-être pas:

  

La fonction rand () n'a pas besoin d'être rentrante. Une fonction qui n'est pas besoin d'être réentrante n'est pas nécessaire d'être thread-safe. "

Un test et un bon exercice d'apprentissage serait de remplacer l'appel à rand() avec, par exemple, un entier fixe et voir ce qui se passe.

La façon dont je pense que des générateurs de nombres pseudo-aléatoires est comme une boîte noire qui prend un entier en entrée et retourner un nombre entier en tant que sortie. Pour toute entrée donnée la sortie est toujours le même, mais il n'y a pas de modèle dans la séquence des nombres et la séquence est répartie uniformément sur toute la gamme des sorties possibles. (Ce modèle est tout à fait exact, mais il le fera.) La façon dont vous utilisez cette boîte noire est de choisir un nombre à regarder (la graine), utilisez la valeur de sortie dans votre application et que l'entrée pour le prochain appel à la générateur de nombres aléatoires. Il y a deux approches communes pour la conception d'une API:

1. Deux fonctions, une pour définir la semence initiale (par exemple srand(seed)) et une pour récupérer la prochaine valeur de la séquence (par exemple rand()). L'état du PRNG est stocké en interne dans une sorte de variable globale. Création d'un nouveau nombre aléatoire soit ne sera pas sûr de fil (difficile à dire, mais le flux de sortie ne sera pas reproductible) ou sera lente dans le code multithreded (vous vous retrouvez avec une sérialisation autour de la valeur d'état).
2. Une interface où l'état de PRNG est exposé au programmeur d'application. Ici, vous avez généralement trois fonctions: init_prng(seed), qui retourne une représentation opaque de l'état PRNG, get_prng(state), qui retourne un nombre aléatoire et change la variable d'état, et destroy_peng(state), qui nettoie juste la mémoire allouée et ainsi de suite. PRNGs avec ce type d'API doivent tous être en sécurité et exécuter fil en parallèle sans verrouillage (parce que vous êtes en charge de la gestion du (fil maintenant locale) variable d'état.

Je vous écris généralement Fortran et utiliser de Ladd mise en œuvre du Mersenne Twister PRNG (ce lien est la lecture vaut). Il y a beaucoup de PRNG est indiqué en C qui exposent l'état de votre commande. PRNG semble bon et en utilisant ce (avec initialisation et détruire les appels à l'intérieur de la région parallèle et privé de l'Etat variables) devraient vous donner une bonne speedup.

Enfin, il est souvent le cas que PRNGs peuvent être faits pour mieux performer si vous demandez une séquence entière de nombres aléatoires en une seule fois (par exemple, le compilateur peut vectoriser les entrailles de PRNG). En raison de ces bibliothèques ont souvent quelque chose comme des fonctions de get_prng_array(state) que vous REDONNER un tableau complet de nombres aléatoires comme si vous mettez get_prng dans une boucle remplissant les éléments du tableau - ils font juste plus rapidement. Ce serait une seconde optimisation (et aurait besoin d'une ajouté boucle à l'intérieur du parallèle pour la boucle. De toute évidence, vous ne voulez pas manquer de par thread espace de pile faisant cela!