1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
<h3>Generating randomness on a GPU</h3>
<p><i>
It seems the disappearance of Nathan Reed's <a href="http://www.reedbeta.com/blog/quick-and-easy-gpu-random-numbers-in-d3d11/">blog post</a> was temporary, and it's up again.
That means the below is an inferior retelling of his post; please see there.
</i></p>
<p>
When doing simulations on a GPU, e.g. for raytracing, one very quickly needs lots and lots of random numbers.
There is a huge number of fine random number generators, but on a GPU you often have a very particular problem: you need lots of random numbers in a large array, generated in parallel.
This is not something that conventional PRNG's like the <a href="https://en.wikipedia.org/wiki/Xorshift" target="_blank">xorshift family</a> are suitable for, since these are inherently sequential: to generate the next random number, it needs the state produced when generating the previous one.
</p>
<p>
You may try to solve this by initialising the RNG many times, each time with a different seed.
However, RNG's are not built for this: the random sequences generated for all those seeds will be different, probably, but they will still be quite correlated.
This is because the random generators are normally constructed to go <b>deep</b>, not <b>wide</b>.
</p>
<p>
This is an insight I learned from reading a post on Nathan Reed's blog, which has now unfortunately disappeared.
(In fact, its disappearance is the very reason for writing this post.)
However, there is <a href="https://web.archive.org/web/20200611022708/http://www.reedbeta.com/blog/quick-and-easy-gpu-random-numbers-in-d3d11/" target="_blank">a copy on the Internet Archive here</a>!
He astutely realises that RNG's are made to go <i>deep</i>, meaning that the random sequence generated for any particular seed will have good properties when seen on its own, and not to go <i>wide</i>: sequence values at similar depth for different seeds are not very independent.
However, <b>hash functions</b> are made to go <i>wide</i>: the outputs for different "seeds" are meant to be competely different and independent, while less emphasis is sometimes laid on the quality of the behaviour when going deep (i.e. when iterating the hash).
</p>
<p>
This means that when you need many random values in an array, in parallel, what you should do is take a hash function and apply it to the integers 1..n for whatever n you need.
The results will be nice.
Then, since hash functions are generally more expensive to compute than PRNG's, if you want more of those arrays, iterate mapping the PRNG over that array.
</p>
<p>
Nathan further recommends the following hash function, which is not a cryptographic hash function but is nothing short of magical when applied for the right purpose: the Wang hash.
The version on Nathan's blog is somewhat outdated; there is an improved one to be found on the (also defunct) website of Thomas Wang himself (<a href="https://web.archive.org/web/20111127152414/http://www.cris.com/~ttwang/tech/inthash.htm" target="_blank">Internet Archive copy</a>):
</p>
<pre>uint wang_hash(uint key) {
// Taken from Thomas Wang's website
key = ~key + (key << 15); // key = (key << 15) - key - 1;
key = key ^ (key >>> 12);
key = key + (key << 2);
key = key ^ (key >>> 4);
key = key * 2057; // key = key + (key << 3) + (key << 11);
key = key ^ (key >>> 16);
return key;
}</pre>
<p>
This is a small, fast hash function that works well when applied in the above scheme.
As a PRNG, he suggests a LCG or an Xorshift generator; I think it's safest to use Xorshift.
An example implementation is here:
</p>
<pre>uint rand_xorshift() {
// Taken from Nathan Reed's blog post; originally from Marsaglia
rng_state ^= (rng_state << 13);
rng_state ^= (rng_state >> 17);
rng_state ^= (rng_state << 5);
return rng_state;
}</pre>
<p>
For neat images and a visual indication that this setup does generate nice random numbers, see Nathan's post linked above.
</p>
|
