Binomial Random Variate Generator on CUDA

Accelerated Computing CUDA CUDA Programming and Performance
#1

Hello,

I need to generate lots of random numbers in parallel using Binomial Distribution on CUDA. All the Random Number Generators on CUDA are based on the Uniform Distribution (as far I know), what is also useful since all the algorithms for Binomial Distribution needs to use Uniform variates.

Is there any library or implementation for binomial random variate generation on CUDA? I see that there are for JAVA in http://acs.lbl.gov/~hoschek/colt/ , but it uses a very complicated algorithm to be parallelized. However, given a binomial variate following B(N,p), there are simpler algorithms with order of complexity O(N), but it is bad for me because N can be large (around 2^32, maximum for a Integer).

I would appreciate any help.
Thanks a lot.
Miguel

#2

I am still interested in an answer to this question. While it is possible to approximate different parts of the binomial distribution, the nitty gritty of random number generators and optimization is one of those things that is not my specialty.

I am also repeating the question to help establish interest. Hopefully others interested in the expansion of cuRand will also chime in to help establish interest.

Many thanks for any suggestions and/or additional interest-
Brian

#3

You may want to file a feature request against CURAND for this. You can do so via the bug reporting form linked from the registered developer web site. Please prefix the subject line with “RFE” (= request for enhancement) to mark it as a feature request rather than a bug report.

This is outside my area of expertise, but I am wondering whether the following paper might help you implement the desired computation:

Catherine Loader, Fast and accurate computation of binomial probabilities (2000)

#4

Thank you for your response! I will submit a feature request.

Also thank you for the suggestion on the paper. This paper appears to be on computing binomial probabilities as opposed to binomial random numbers. I do think a Box-Mueller transform would generally be computationally efficient. (There are papers on computing pseudo-random binomial variables; and implementations exist in the C libraries for R, C++11 , and the C boost libraries, among others.)

#5

I don’t know about your particular problem, but the OP’s problem (huge N) may well have been solved (indeed approximated to a high degree of accuracy, given N ~=2^32) by a single draw from a normal distribution.

#6

@Brian_T: I am not sure how Box-Muller plays into producing a binomial distribution. I am only aware of Box-Muller for producing a normal distribution, which CURAND already provides.

#7

@njuffa: Sorry, you are correct. I very much misspoke/misthought/mistyped. What I meant to say (instead of referring to the Box-Muller) is that I do not believe an inverse CDF transform is efficient. I was only mentioning it in relation to the paper on binomial probabilities. (It wouldn’t be a particularly direct or efficient one, but that was the only tie I could think of to pseudo-random number generation that I had originally asked about.) Thanks again for your suggestions, I very much appreciate them!

@sBc-Random: Thank you for you input as well. I don’t know enough of the specifics on the OP’s problem either to offer a solution other than seemed to be looking for a general CUDA method for calculating binomial pseudo-random variables. E.g. I think the 2^32 is a reference to a 32-bit (unsigned) int data type.

#8

I am reasonably sure that generating certain random number distributions with the help of the inverse CDF is something that is used in practice for some distributions. Whether the binomial distribution is one of these I cannot say, as this question is outside my area of expertise and I have not performed a literature search. My involvement with CURAND has been limited to performance optimizations so far.

#9

Sorry, I’m 5 years late for this discussion, I haven’t come back again since I wrote my question. If you still feel interested, you can check what I did in my PhD in section 7.5.2 http://fondosdigitales.us.es/media/thesis/2008/C_043-PROV20-INGLES.pdf

Best regards