US 9,804,826 B2Granted

Parallelization of random number generators

AssigneeNVIDIA Corporation

InventorsPrzemyslaw Tredak, John Clifton Woolley, Jr.

Life of this patent

Estimating the term…

Loading patent…

Abstract

System and method for pseudo-random number generation based on a recursion with significantly increased multithreaded parallelism. A single pseudo-random generator program is assigned with multiple threads to process in parallel. N state elements indexed incrementally are arranged into a matrix comprising x rows, where a respective adjacent pair of state elements in a same column are related by g=(M+j)mod N, wherein j and g represent indexes of the pair of state elements. x can be determined through an modular manipulative inverse of M and N. The matrix can be divided into sections with each section having a number of columns, and each thread is assigned with a section. In this manner, the majority of the requisite interactions among the state elements occur without expensive inter-thread communications, and further each thread may only need to communicate with a single other thread for a small number of times.

Claims20

Dependent claims

A non-transient computer readable storage medium comprising executable instructions that implement a method of generating a sequence of pseudo-random numbers, said method comprising:

accessing an integer M and an integer N, wherein M is a predetermined number and N represents a number of state elements;
accessing N state elements indexed incrementally, each state element storing a respective first value;
arranging said N state elements into a matrix comprising x rows and a plurality of columns, wherein, a respective pair of adjacent state elements in a same column are related by g=(M+j)mod N, wherein j and g represent indexes of said respective pair of adjacent state elements;
dividing said N state elements into K sections based on indexes of said N state elements;
assigning K execution threads for processing said K sections, wherein each execution thread corresponds to a respective section;
computing respective second values of said N state elements by said K execution threads executed in parallel in accordance with a recursion relationship representable as ai+N=f(ai,ai+c,ai+M), wherein ai+N represents a second value of state element i, wherein ai represents a first value of state element i, wherein ai+c represents a first value of state element i+c, wherein ai+M corresponds to a first value of state element i+M, wherein f represents a function, wherein c is an integer, and wherein further x, K and i are integers;
and
outputting second values of said N state elements as said sequence of pseudo-random numbers.

5 more elements

A computer implemented method of generating random numbers, said method comprising:

accessing a state vector comprising N elements that are indexed incrementally, each element storing a respective first value;
accessing an integer x and an integer M, wherein M is a predetermined number;
arranging said N elements into a matrix based on element indexes of said N elements;
dividing said N elements into K sections;
assigning K execution threads for processing said K sections respectively;
computing respective second values of said N elements by said K execution threads in parallel, wherein a second value of element i is computed in accordance with a recursive function based on respective first values of said element i, element i+c, and element i+M, wherein i represents an element index, i=0, 1, 2, . . . , N−1, and c is an integer,
wherein said computing said second values of said N elements comprises execution thread p only communicating with execution thread q for corresponding first values, wherein p and q represent thread indexes, and wherein p,q=0, 1, 2, . . . , K−1;
and
outputting said respective second values of said N elements, wherein x, K and i are integers.

6 more elements

A computing system comprising:

a bus;
a processor coupled to said bus;
a non-transient computer-readable recording medium storing pseudo-random number generator program, said pseudo-random number generator program, comprising instructions that cause said processor to perform:
accessing a vector comprising N elements indexed incrementally, each element storing a respective first value;
arranging said N elements into a matrix comprising x rows and a plurality of columns, wherein, a respective pair of adjacent elements in a column are related by g=(M+j)mod N, wherein j and g represent indexes of said respective pair, wherein M is a predetermined integer;
dividing said N elements into K sections based on indexes of said N elements;
assigning K execution threads for processing said K sections, wherein each execution thread corresponds to a respective section;
computing respective second values of said N elements by said K execution threads in parallel in accordance with a recursion relationship representable as ai+N=f(ai,ai+c,ai+M), wherein ai+N represents a second value of element i, wherein ai represents a first value of element i, wherein ai+c represents a first value of element i+c, wherein ai+M corresponds to a first value of element i+M, wherein f represents a function, wherein c is a user-defined integer;
and
outputting second values of said N elements as said sequence of pseudo-random numbers, wherein x, K and i are integers.

7 more elements

Dependencies are inferred from the claim text.