Parallel Gibbs sampler using butterfly-patterned partial sums

• US 10,157,346 B2
• Filed: 05/15/2015
• Issued: 12/18/2018
• Est. Priority Date: 06/26/2014
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Steele, Jr., Guy L., Tristan, Jean-Baptiste
• Primary Examiner(s): Smith, Paulinho E
• Application Number:
  US14/713,205
• Publication Number:
  US 20160224902A1
• Time in Patent Office: 1,313 Days
• Field of Search: None
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

An efficient parallel Gibbs sampler using butterfly-patterned partial sums is provided. Instead of building and searching a complete prefix sums table, an alternative “butterfly patterned partial sums table” is described that integrates a lightweight transposition and partial sums operation. Accordingly, the usual full matrix transposition and full prefix sums table building operations can be omitted in favor of building the butterfly-patterned partial sums table, which requires less computational and communication effort. This butterfly-patterned partial sums table is used by a modified binary search phase that calculates the needed prefix-sum table values on-the-fly using the butterfly-patterned partial sums table. Transposed memory access is also provided while avoiding the full matrix transform, providing significant performance benefits for highly parallel architectures, such as graphics processing units (GPUs) where 1-stride or sequential memory accesses are important for optimization.

Claims

1. A method for parallel random sampling from a plurality of discrete probability distributions by one or more multiprocessors, wherein the method comprises:

initializing a partial sums table based on a matrix product of parameters for the plurality of discrete probability distributions, wherein the partial sums table comprises a plurality of blocks, each of which has a maximum size W, which is a value that is based on a number of threads in a warp of at least one of the one or more multiprocessors;

applying one or more iterations of butterfly patterned replacements to each of the plurality of blocks such that a single row of each of the plurality of blocks is un-transposed; and

drawing, in parallel from each of the plurality of discrete probability distributions, at least one respective z value, wherein each parallel drawing performs, respectively;

a first binary search on the single un-transposed row of each of the plurality of blocks to determine a candidate block, and

a second binary search within the candidate block to draw the at least one respective z value;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein the parameters for the plurality of discrete probability distributions are received, in a transposed form, from one or more local memories that are local to one or more respective threads of a plurality of threads executing, concurrently, on the one or more multiprocessors.

3. The method of claim 1, wherein:

a plurality of z values is produced by said drawing, in parallel from each of the plurality of discrete probability distributions, at least one respective z value;

the one or more multiprocessors execute a plurality of threads concurrently; and

the parallel drawing of each of the plurality of z values executes on a respective thread of the plurality of threads.

4. The method of claim 1, wherein a graphics processing unit (GPU) includes at least one multiprocessor of the one or more multiprocessors.

5. The method of claim 1, wherein the parameters are retrieved in parallel, wherein the initializing of the partial sums table is in parallel, and wherein the applying of each of the one or more iterations of butterfly patterned replacements is in parallel.

6. The method of claim 1, wherein the plurality of discrete probability distributions are based on a plurality of documents in a documents corpus, wherein the parameters comprise a matrix “

w”

corresponding to words of the plurality of documents, a theta matrix (θ

) for “

w”

, and a phi matrix (ϕ

) for “

w”

.

7. The method of claim 1, wherein:

the one or more iterations of butterfly patterned replacements comprises X iterations; and

said W is 2 to the power of said X.

8. The method of claim 1, wherein the single row of each of the plurality of blocks is in the last position within each of the plurality of blocks.

9. One or more non-transitory computer-readable media storing one or more sequences of instructions which, when executed by one or more processors, cause parallel random sampling from a plurality of discrete probability distributions by one or more multiprocessors comprising:

initializing a partial sums table based on a matrix product of parameters for the plurality of discrete probability distributions, wherein the partial sums table comprises a plurality of blocks, each of which has a maximum size W, which is a value that is based on a number of threads in a warp of at least one of the one or more multiprocessors;

applying one or more iterations of butterfly patterned replacements to each of the plurality of blocks such that a single row of each of the plurality of blocks is un-transposed; and

drawing, in parallel from each of the plurality of discrete probability distributions, at least one respective z value, wherein each parallel drawing performs, respectively;

a first binary search on the single un-transposed row of each of the plurality of blocks to determine a candidate block, and

a second binary search within the candidate block to draw the at least one respective z value.

10. The one or more non-transitory computer-readable media of claim 9, wherein the parameters for the plurality of discrete probability distributions are received, in a transposed form, from one or more local memories that are local to one or more respective threads of a plurality of threads executing, concurrently, on the one or more multiprocessors.

11. The one or more non-transitory computer-readable media of claim 9, wherein:

a plurality of z values is produced by said drawing, in parallel from each of the plurality of discrete probability distributions, at least one respective z value;

the one or more multiprocessors execute a plurality of threads concurrently; and

the parallel drawing of each of the plurality of z values executes on a respective thread of the plurality of threads.

12. The one or more non-transitory computer-readable media of claim 9, wherein a graphics processing unit (GPU) includes at least one multiprocessor of the one or more multiprocessors.

13. The one or more non-transitory computer-readable media of claim 9, wherein the parameters are retrieved in parallel, wherein the initializing of the partial sums table is in parallel, and wherein the applying of each of the one or more iterations of butterfly patterned replacements is in parallel.

14. The one or more non-transitory computer-readable media of claim 9, wherein the plurality of discrete probability distributions are based on a plurality of documents in a documents corpus, wherein the parameters comprise a matrix “

w”

corresponding to words of the plurality of documents, a theta matrix (θ

) for “

w”

, and a phi matrix (ϕ

) for “

w”

.

15. The one or more non-transitory computer-readable media of claim 9, wherein:

the one or more iterations of butterfly patterned replacements comprises X iterations; and

said W is 2 to the power of said X.

16. The one or more non-transitory computer-readable media of claim 9, wherein the single row of each of the plurality of blocks is in the last position within each of the plurality of blocks.

17. A system comprising one or more multiprocessors configured to perform parallel random sampling from a plurality of discrete probability distributions by the one or more multiprocessors by being configured to:

initialize a partial sums table based on a matrix product of parameters for the plurality of discrete probability distributions, wherein the partial sums table comprises a plurality of blocks, each of which has a maximum size W, which is a value that is based on a number of threads in a warp of at least one of the one or more multiprocessors;

apply one or more iterations of butterfly patterned replacements to each of the plurality of blocks such that a single row of each of the plurality of blocks is un-transposed; and

draw, in parallel from each of the plurality of discrete probability distributions, at least one respective z value, wherein each parallel draw performs, respectively;

a first binary search on the single un-transposed row of each of the plurality of blocks to determine a candidate block, and

a second binary search within the candidate block to draw the at least one respective z value.

18. The system of claim 17, wherein the one or more multiprocessors are further configured to receive the parameters, for the plurality of discrete probability distributions, in a transposed form from one or more local memories that are local to one or more respective threads of a plurality of threads executing, concurrently, on the one or more multiprocessors.

19. The system of claim 17, wherein:

a plurality of z values is produced by drawing, in parallel from each of the plurality of discrete probability distributions, at least one respective z value;

the one or more multiprocessors are configured to execute a plurality of threads concurrently; and

the parallel draw of each of the plurality of z values executes on a respective thread of the plurality of threads.

20. The system of claim 17, wherein the one or more multiprocessors are further configured to retrieve the parameters in parallel, initialize the partial sums table in parallel, and apply each of the one or more iterations of butterfly patterned replacements in parallel.

21. The system of claim 17, wherein the plurality of discrete probability distributions are based on a plurality of documents in a documents corpus, wherein the parameters comprise a matrix “

w”

corresponding to words of the plurality of documents , a theta matrix (θ

) for “

w”

, and a phi matrix (ϕ

) for “

w”

.

22. The system of claim 17, further comprising a graphics processing unit (GPU) that includes at least one multiprocessor of the one or more multiprocessors.

23. The system of claim 17, wherein:

the one or more iterations of butterfly patterned replacements comprises X iterations; and

said W is 2 to the power of said X.

24. The system of claim 17, wherein the single row of each of the plurality of blocks is in the last position within each of the plurality of blocks.