Discussion :

[Matthieu Brucher]

Non, ca ne suffit pas. J'ai deja tente ce genre de chose, la seule bonne solution est de prendre un generateur qui est prevu pour ca, comme un generateur cryptographique. De plus, ils sont plus rapides que les Mersenne Twister sur les derniers procs Intel, du meme ordre pour les autres, consomment moins de memoire et en plus ils sont robustes, contrairement au Mersenne Twister. En fait, il n'y a plus aucune raison mathematique de prendre le generateur de la bibliotheque standard...

[Emmanuel Deloget]

Non, ca ne suffit pas. J'ai deja tente ce genre de chose, la seule bonne solution est de prendre un generateur qui est prevu pour ca, comme un generateur cryptographique. De plus, ils sont plus rapides que les Mersenne Twister sur les derniers procs Intel, du meme ordre pour les autres, consomment moins de memoire et en plus ils sont robustes, contrairement au Mersenne Twister. En fait, il n'y a plus aucune raison mathematique de prendre le generateur de la bibliotheque standard...

Pour le cas d'utilisation, il faut juste un générateur aléatoire qui offre une bonne distribution. Inutile d'aller jusqu'à un générateur cryptographique (et s'ils sont rapides, c'est parce qu'ils s'appuient sur le système, par exemple via un device ; hors, les accès à ce device sont rendus séquentiels par le système, de manière à ne pas donner la même donnée à deux lecteurs différents. Sans compter que si on épuise l'entropie, alors le système va bloquer la récupération de données jusqu'à ce que l'entropie soit revenue. On retomberait alors dans un cas similaire, voire pire).

Si rand() fonctionne suffisamment bien pour obtenir une bonne qualité d'image, alors un autre générateur congruentiel linéaire offrant au moins la même qualité fournira le même service. Le tout est qu'il faut que ce générateur stocke son état - par opposition à un état global. Mersenne Twister offre de meilleure garantie sur la période et sur la distribution des valeurs, mais je ne sais pas dans quelle mesure ce gain est appréciable s'il s'accompagne d'une perte de performance (dans ce cas d'utilisation, les performances sont critiques, sinon on ne chercherait pas à disperser le travail sur plusieurs threads).

Le seul problème d'un générateur linéaire dans ce cas précis, c'est la graine. Et pour générer une graine pour chaque threads, on peut utiliser rand() ou un autre générateur random - il faut éviter d'utiliser time(), car on risque d'obtenir la même valeur de graine pour plusieurs threads).

Personnellement, je partirai sur une distribution uniforme, un générateur congruentiel linéaire, et une graine obtenue avec random_engine. Je ne suis pas sûr que ça vaille le coup d'aller beaucoup plus loin.

Par contre, je ferais aussi des tests avec d'autres distributions, histoire de voir si la qualité finale de l'image est dégradée ou améliorée.

[Matthieu Brucher]

Pour le cas d'utilisation, il faut juste un générateur aléatoire qui offre une bonne distribution. Inutile d'aller jusqu'à un générateur cryptographique (et s'ils sont rapides, c'est parce qu'ils s'appuient sur le système, par exemple via un device ; hors, les accès à ce device sont rendus séquentiels par le système, de manière à ne pas donner la même donnée à deux lecteurs différents. Sans compter que si on épuise l'entropie, alors le système va bloquer la récupération de données jusqu'à ce que l'entropie soit revenue. On retomberait alors dans un cas similaire, voire pire).

Il me semble aue non. On calcule juste le hash d'un compteur avec une cle particuliere. Il n'y a pas de device particulier utilise.

Si rand() fonctionne suffisamment bien pour obtenir une bonne qualité d'image, alors un autre générateur congruentiel linéaire offrant au moins la même qualité fournira le même service. Le tout est qu'il faut que ce générateur stocke son état - par opposition à un état global. Mersenne Twister offre de meilleure garantie sur la période et sur la distribution des valeurs, mais je ne sais pas dans quelle mesure ce gain est appréciable s'il s'accompagne d'une perte de performance (dans ce cas d'utilisation, les performances sont critiques, sinon on ne chercherait pas à disperser le travail sur plusieurs threads).

Justement, un MT n'est pas une bonne solution pour un generateur parellele car il est difficile de l'initialiser proprement, justement a cause de sa longue periodicite.

Le seul problème d'un générateur linéaire dans ce cas précis, c'est la graine. Et pour générer une graine pour chaque threads, on peut utiliser rand() ou un autre générateur random - il faut éviter d'utiliser time(), car on risque d'obtenir la même valeur de graine pour plusieurs threads).

Malheureusement non, ca ne suffit pas.

On peut conseiller ici, dans ce cas precis, de faire une solution a l'arrache pas propre, OK. Tu es l'un des seuls a avoir le code et a savoir ce qu'il fait. Mais dans le cas general de la generation de nombre aleatoires en parallele, il faut utiliser un outil qui soit correct, soit donc un generateur tel que ceux proposes par Random123. Dans le doute, il suffit de lire la publication associee a la bibliotheque presente a SC12

[Emmanuel Deloget]

Il me semble aue non. On calcule juste le hash d'un compteur avec une cle particuliere. Il n'y a pas de device particulier utilise.

Je vois.

Justement, un MT n'est pas une bonne solution pour un generateur parellele car il est difficile de l'initialiser proprement, justement a cause de sa longue periodicite.

Je ne comprends pas trop. Chaque thread a son propre générateur, créé avec une graine différente.

Est-ce que tu pourrais m'éclairer sur le sujet ?

Malheureusement non, ca ne suffit pas.

On peut conseiller ici, dans ce cas precis, de faire une solution a l'arrache pas propre, OK. Tu es l'un des seuls a avoir le code et a savoir ce qu'il fait. Mais dans le cas general de la generation de nombre aleatoires en parallele, il faut utiliser un outil qui soit correct, soit donc un generateur tel que ceux proposes par Random123. Dans le doute, il suffit de lire la publication associee a la bibliotheque presente a SC12

C'est vrai que j'ai un peu d'avance sur vous Ceci dit, c'est un champ que tu connais bien, donc je ne vais pas te faire l'insulte de te prendre de haut

Sur le fond, je suis d'accord avec toi - encore qu'aller jusqu'au niveau cryptographique me semble exagéré.

J'espèce ne pas trop en dire : on est dans un cas proche d'une simulation Monte Carlo, donc l'idée est principalement d'avoir une distribution parfaite et un grand nombre de samples. Une générateur linéraire peut, dans ce cas, provoquer des artefacts - dans le sens où le générateur pourrait être biaisé ou avoir une distribution relativement moyenne. Mais s'il est suffisamment bon, alors la diffusion des samples sera elle aussi suffisamment bonne. Le but là n'est pas d'avoir du random pour du random - mais d'être capable de dire "si j'ai 1000 balles a tirer vers 10000 trous, alors chaque trou aura en moyenne 0,1 balles".

Edit : trouvé un papie de NVIDIA qui dit, effectivement, que des générateur MT sur plusieurs threads peuvent être correllés - ce qui n'est peut-être pas génial ici - (encore que, parce que chaque lanceur de balle est affecté à une série de trou, et ne peut pas perturber ses voisins ; du coup, même si tous les lanceurs lancent de la même manière ça ne change pas vraiment grand chose - c'est juste dommage d'un point de vue intellectuel). Le papier de NVIDIA cite un papier de Matsumoto & Nishimura (http://www.math.sci.hiroshima-u.ac.j...T/DC/dgene.pdf) qui, à priori, règle le problème. Leur idée est d'encoder le thread id dans les paramètres qui permettent de créer le générateur MT. A lire...

Ceci dit, ça ne change pas vraiment le fait que MT soit plus lent que d'autres générateurs random

[Matthieu Brucher]

Je ne comprends pas trop. Chaque thread a son propre générateur, créé avec une graine différente.

Est-ce que tu pourrais m'éclairer sur le sujet ?

Le probleme, c'est que tu ne sais pas si tu prends une graine toto et une autre toto +1 quand la premiere suite tombera sur la suivante. Il semblerait qu'avec les generateurs bases sur des compteurs, ce probleme specifique ne se pose pas (autant ?). La publication de Random123 a SC12 en parle, je crois qu'elle est sur leur site Web.

Sur le fond, je suis d'accord avec toi - encore qu'aller jusqu'au niveau cryptographique me semble exagéré.

Completemenent d'accord. D'ailleurs Random 123 propose des genereateurs bases sur une partie de fonction crytpographique si on veut. Avec le jeu d'instructions crypto d'Intel, on fait directement le travail, donc on peut se permettre sans aucun surcout de prendre une vraie fonction cryptographique (qui sera don crush resistant). Tout depend donc de ce qu'on peut se permettre. En tout cas, on peut se permettre d'avoir le choix maintenant, c'est bien