Calcul distribué et générateurs des nombres au hasard

Les simulations stochastiques sont des méthodes numériques qui convergent très lentement. De nos jours, on dispose plusieurs méthodes pour réduire le temps nécessaire à l'obtention d'un résultat avec une précision donnée. L'idée de base de tous ces méthodes est d'effectuer certains étapes du programme parallèlement au lieu de les exécuter séquentiellement. Ceci peut se réaliser de plusieurs manières :

1. Par vectorisation du processeur. Le processeur central dispose à côté des registres scalaires des registres vectoriels qui permettent d'effectuer des blocs de boucles en une étape d'horloge (cf. annexe ???) comme sur le CRAY-1 par exemple.
2. Par parallélisation du programme. On se sert des divers processeurs d'un ordinateur multi-processeur en parallèle comme sur le SUN Entreprise par exemple.
3. Par distribution du calcul sur un réseau d'ordinateurs interconnectés. On se sert des processeurs de divers ordinateurs. La parallélisation se fait alors de manière logicielle, en se servant de programmes tels que Virtual Parallel Machine (VPM) ou MPI pour distribuer les tâches à travers le réseau.

S'agissant de simulation Monte Carlo, il y a cependant une difficulté qui surgit lorsqu'on tente de paralléliser l'algorithme de simulation. Pour illustrer ce problème, prenons l'exemple du générateur standard avec une racine . Ce générateur est défini par le système dynamique avec et . L'espace est partitionné par cette évolution en deux parties invariantes sous  : un singleton contenant contenat l'unique point fixe 0 et son complémentaire contenant l'unique orbite périodique (en vertue du théorème ). Initialiser le générateur avec une autre racine équivaut à parcourir la même orbite périodique (puisqu'elle est unique) à partir d'un autre point d'entrée. Si et sont deux racines arbitraires différentes, on note

le temps nécessaire pour que l'orbite émanant de atteigne et qui est nécessairement fini. Supposons donc qu'en parallélisant le programme, on l'a scindé en deux sous-tâches dont chacune nécessite nombres au hasard. Si on initialise le générateur avec deux racines et telles que , une partie de la suite de variables utilisées par la première sous-tâche sera identique à une partie de la suite utilisée par la deuxième sous-tâche. Donc les deux sous-tâches ne seront pas indépendantes.

Une manière peu coûteuse pour pouvoir paralléliser est suggérée par le tableau où l'on a parcouru la totalité de l'orbite émanant de et en marquant la valeur de pour . Ceci nous permet de disposer de 21 lots de valeurs pseudo-aléatoires indépendantes^2.4.

Table: En initialisant avec Racine(iter) on peut utiliser le générateur standard pour créer un lot de 100 000 000 nombres au hasard indépendemment du reste. En utilisant la racine correspondante à une autre valeur de iter, on est certain de disposer d'un autre lot de 100 000 000 nombres au hasard indépendant du précédent qui pourrait être généré en parallèle.

iter	Racine(iter)	iter	Racine(iter)
0	1	1 100 000 000	1 103 177 160
100 000 000	1 209 575 029	1 200 000 000	999 244 642
200 000 000	449 294 716	1 300 000 000	552 035 842
300 000 000	1 292 894 662	1 400 000 000	1 218 407 032
400 000 000	527 371 189	1 500 000 000	1 947 017 488
500 000 000	1 912 880 129	1 600 000 000	1 749 956 682
600 000 000	52 980 039	1 700 000 000	904 907 723
700 000 000	2 116 779 609	1 800 000 000	1 982 270 339
800 000 000	87 504 891	1 900 000 000	2 354 258
900 000 000	184 641 623	2 000 000 000	325 871 955
1 000 000 000	933 757 703	2 100 000 000	1 871 752 643

De méthodes plus avancées sont utilisées pour construire de générateurs paralélisables plus performants (cf. article de Marsaglia [#!Mar!#]).