L'Ecuyer studied combined multiple recursive generators (CMRG) in order to produce a generator that had good randomness properties with a long period, while at the same time being fairly straightforward to implement. The best known CMRG is MRG32k3a [4] , which is defined by the set of equations for all where The sequence of integers are the output of this generator. When divided by they give pseudorandom outputs with a uniform distribution on the unit interval . These may then be transformed into various other distributions.

At any point in the sequence the state can be represented by the pair of vectors for . It follows that the two recurrences in Eq. 16.1 can be represented as for where each is a matrix, and therefore for any .

The parallel MRG generator has a small state (only six 32-bit integers) and requires few registers. The simple skip-ahead strategy whereby each thread has its own copy of state and produces a contiguous segment of the MRG32k3a sequence (as specified in Eq. 16.4 ) independently of all other threads works well, provided we have a very efficient way to skip ahead to an arbitrary number of points. To efficiently compute for large values of p , one can use the classic “divide-and-conquer” strategy of iteratively squaring the matrix [5] and [8] . It begins by writing where and then computing the sequence by successively squaring the previous term found. It is then a simple matter to compute for and the entire process can be completed in approximately steps.

We can improve the speed of this procedure at the cost of more memory by expanding the exponent p in a base higher than two so that for some and . This improves the “granularity” of the expansion. To illustrate, suppose b = 10 and p = 7. Then computing requires only a single lookup from memory; namely, the precomputed value , and a single matrix-vector product. However, if b = 2, then , requiring three lookups and three matrix-vector products.

We take b = 8 and precompute the set of matrices for and ; namely, for on the host. Because the state is so small, only 10,656 bytes of memory are used, and both sets of matrix powers are copied to constant memory on the GPU. Selecting from this large store of pre-computed matrix powers allows us to compute , roughly three times faster than using b = 2.

To generate a total of N random numbers, a kernel can be launched with any configuration of threads and blocks. Using T threads in total, the i -th thread for will advance its state by and will then generate N / T numbers.

The most efficient way to use the numbers generated in this manner is to consume them as they are produced, without writing them to global memory. Because any configuration of threads and blocks can be used, and because the MRG generator is so light on resources, it can be embedded directly in an application's kernel. If this is not desired, output can be stored in global memory for subsequent use. Note that each thread generates a contiguous segment of random numbers, and therefore, writes to global memory will not be coalesced if they are stored to correspond to the sequence produced by the serial algorithm described in [4] ; in other words, if the j -th value (counting from zero) produced by a given thread is stored at where and blocks and grids are one dimensional. Coalesced access can be regained either by reordering output through shared memory, or by simply writing the j -th number from each thread to

This will result in a sequence in global memory that has a different ordering to the MRG32k3a sequence described in [4] .

We will briefly discuss how to generate Sobol sequences in the unit cube. For more details and further discussion we refer to [2] . A D -dimensional Sobol sequence is composed of D different one-dimensional Sobol sequences. We therefore examine a one-dimensional sequence.

When one is generating at most points, a Sobol sequence is defined by a set of 32-bit integers known as direction numbers . Using these direction numbers, one can compute the sequence from starting from . Here denotes the binary exclusive-or operator, and the 's are the bits in the binary expansion of the Gray code representation of n . The Gray code of n is given by , and so . The function in Eq. 16.3 returns the index of the rightmost zero bit in the binary expansion of n . Finally, to obtain our Sobol sequence we set .

To obtain multidimensional Sobol sequences, different direction numbers are used for each dimension. Care must be taken in choosing these because poor choices can easily destroy the multidimensional uniformity properties of the sequence. For more details we refer to [10] .

The first expression in Eq. 16.3 gives a formula for directly computing , whereas the second expression gives an efficient algorithm for computing from the value of . The first formula therefore allows us to skip ahead to the point . This skip ahead is quite fast as it requires a loop with at most 32 iterations, and each iteration performs a bit shift and (possibly) an xor. We could therefore have parallelized this generator along the same lines as the MRG32k3a generator described earlier in this chapter with threads performing a skip ahead and then generating a block of points. However, there is another option.

Recall the second expression in Eq. 16.3 , fix and consider what happens as n increases to n + 8. If denotes the bit pattern of n , clearly the last three bits remain unchanged when we add 8 to n : adding 1 to n eight times results in flipping eight times, flipping four times and flipping twice. It follows that will enumerate all permutations of 3 bits as n increases to n + 8. Consider now what happens to for : because we are enumerating all permutations of we will have four times, twice, once, and once. Returning to Eq. 16.3 and recalling that two exclusive-ors cancel (i.e., ), we see that for some . This analysis can be repeated for any power of 2: in general, for some given by where | denotes the bitwise or operator. This gives an extremely efficient algorithm for strided (or “leapfrog”) generation, which in turn is good for memory coalescing (see the next section).

Our algorithm works as follows. The values are precomputed on the host and copied to the device. In a 32-bit Sobol sequence, each dimension requires at most 32 of the values. Since individual dimensions of the D dimensional Sobol sequence are independent, it makes sense to use one block to compute the points of each dimension (more than one block can be used, but suppose for now there is only one). For each Sobol dimension then, a block is launched with threads for some and the 32 values for that dimension are copied to shared memory. Within the block, the i -th thread skips ahead to the value using the first expression in Eq. 16.3 . Because p is typically small (around 6 or 7), the skip-ahead loop will have few iterations (around 6 or 7) because the bit pattern of will contain mostly zeros. The thread then iteratively generates points using Eq. 16.4 . Note that is fixed throughout this iteration: all that is needed at each step is the previous y value and the new value of . Writes to global memory are easily coalesced because successive threads in a warp generate successive values in the Sobol sequence. In global memory we store all the numbers for the first Sobol dimension first, then all the numbers for the second Sobol dimension, and so on. Therefore, if N points were generated from a D dimensional Sobol sequence and stored in an array x , the i -th value of the d -th dimension would be located at x[d*N+i] where and .

As a final tuning of the algorithm, additional blocks can be launched for each dimension as long as the number of blocks cooperating on a given dimension is a power of 2. In this case if blocks cooperate, the i -th thread in a block simply generates the points .

TGFSR generator is based on the linear recurrence for all where are given and fixed. Each value has a word length of w that is represented by w 0–1 bits. The value D is a matrix with 0–1 entries, the matrix multiplication in the last term is performed modulo 2, and is again bitwise exclusive-or, which corresponds to bitwise addition modulo 2. These types of generators have several advantages: they are easy to initialize (note that we need N seed values), they have very long periods, and they have good statistical properties.

The Mersenne Twister defines a family of TGFSR generators with a separate output function for converting state elements into random numbers. The output function applies a tempering transform to each generated value before returning it (see [11] for further details) where the transform is chosen to improve the statistical properties of the generator. The family of generators is based on the recurrence for all where are fixed values and each has a word length of w . The expression denotes the concatenation of the most significant bits of and the r least significant bits of for some , and the bit-matrix D is given by where all the entries are either zero or one. The matrix multiplication in Eq. 16.5 is performed bitwise modulo 2.

The popular Mersenne Twister MT19937 [11] is based on this scheme with and has a period equal to the Mersenne prime . The state vector of MT19937 consists of bits — 623 unsigned 32-bit words plus one bit — and is stored as 624 32-bit words. We denote this state vector by for all where denotes the initial seed. When read from top to bottom, the first 19,937 bits are used and the bottom 31 bits (the 31 least significant bits of ) are ignored. If the generator is considered as an operation on individual bits , it can be recast in the form where A is a matrix of dimension 19,937 with elements having value 0 or 1 and the multiplication is performed mod 2. For the explicit form of this matrix, see [11] .

Matsumoto and Nishimura give a simple C implementation of their algorithm that is shown in Listing 16.1 . Their implementation updates all 624 elements of state at once so that the state variable contains for . The subsequent 624 function calls each produce a single random number without updating any state, and the 625-th call will again update the state.

The state size of the Mersenne Twister is too big for each thread to have its own copy. Therefore, the per-thread parallelization strategy used for the MRG32k3a is ruled out, as is the strided generation strategy used for the Sobol generator. Instead, threads within a block have to cooperate to update state and generate numbers, and the level to which this can be achieved determines the performance of the generator. Note from Eq. 16.5 that the process of advancing state is quite cheap, involving three state elements and 7 bit operations.

We follow a hybrid strategy. Each block will skip the state ahead to a given offset, and the threads will then generate a contiguous segment of points from the MT19937 sequence by striding (or leapfrogging). There are three main procedures: skipping ahead to a given point, advancing the state, and generating points from the state. We will examine how to parallelize the latter two procedures first, and then return to the question of skipping ahead.

Generating for any requires the values of where and . In particular, requires . If there are T threads in a block and the i -th thread generates for , then we see that we must have ; otherwise, thread would require , a value that will be generated by thread 0. To avoid dependence between threads, we are limited to fewer than 227 threads per block. We will use 1-D blocks with 224 threads because this is a multiple of 32.

We implement state as a circular buffer in shared memory of length , and we update 224 elements at a time. We begin by generating 224 random numbers from the initial seed and then updating 224 elements of state and storing them at locations state[N…N+223] . This process repeats as often as needed, with the writing indices wrapping around the buffer. All indices except writes to global memory are computed modulo . The code is illustrated in Listing 16.2 . As was the case with the Sobol generator, writes to global memory are easily coalesced because the threads cooperate in a leapfrog manner.

We now consider how blocks can skip ahead to the correct point in the sequence. Given a certain number of Mersenne points to generate, we wish to determine how many points each block should produce and then skip that block ahead by the number of points all the preceding blocks will generate. For this we need a method to skip a single block ahead by a given number of points in the Mersenne sequence.

Such a skip-ahead algorithm was presented by Haramoto et al. [9] . Recall that for where A is a 19,937 × 19,937 matrix. However computing even through a repeated squaring (or “divide-and-conquer”) strategy is prohibitively expensive and would require a lot of memory. Instead, a different approach is followed in [9] based on polynomials in the field (the field with elements and where all operations are performed modulo 2). Briefly, they show that for any we have where and is a polynomial over that depends on v . A formula is given for determining for any given and fixed. Note that each of the coefficients of are either zero or one.

Figure 16.1 shows the time taken for a single block to perform the various tasks in the MT19937 algorithm: calculate on the host, compute , perform v updates of state (not generating points from state), and generating v values with all updates of state. Although evaluating is fairly expensive (equivalent to generating about 2million points and advancing state about 2.3million times), computing the polynomial is is much more so: one could generate almost 13million points in the same time, and advance state almost 20million times. Updating state and generating points scale linearly with v .

Clearly, we would prefer not to calculate on the fly. We would also prefer not to perform the calculation in a separate kernel because the first block never has to skip ahead and this would prevent it from generating points until the calculation was finished. However, there is the question of load balance: the first block can generate around 2million points in the time it takes the second block to skip ahead. Because the total runtime is equal to the runtime of the slowest block, if the number of blocks equals the number of streaming multiprocessors in the GPU, it is clear that blocks should not all generate the same number of points. A mathematical analysis of the runtimes of each block, coupled with experimental measurements, can be done, and this yields formulae for the optimal number of points each block should generate as well as how far the block should skip ahead. This depends on the sample size and so requires us to calculate on the fly.

There are a number of options when choosing a skip-ahead strategy for the Mersenne Twister, and it is not completely clear which approach is best: