[Numpy-discussion] Suggestion: Port Theano RNG implementation to NumPy
Hi, In a ticket I did a coment and Charles suggested that I post it here: In Theano we have an C implementation of a faster RNG: MRG31k3p. It is faster on CPU, and we have a GPU implementation. It would be relatively easy to parallize on the CPU with OpenMP. If someone is interested to port this to numpy, their wouldn't be any dependency problem. No license problem as Theano license have the same license as NumPy. The speed difference is significant, but I don't recall numbers. Fred ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] Suggestion: Port Theano RNG implementation to NumPy
AFAIK, CMRG (MRG31k3p) is more equidistributed than Mersenne Twister, but the period is much shorter. However, MT is getting acceptance as the PRNG of choice for numerical work. And when we are doing stochastic simulations in Python, the speed of the PRNG is unlikely to be the bottleneck. Sturla Frédéric Bastien no...@nouiz.org wrote: Hi, In a ticket I did a coment and Charles suggested that I post it here: In Theano we have an C implementation of a faster RNG: MRG31k3p. It is faster on CPU, and we have a GPU implementation. It would be relatively easy to parallize on the CPU with OpenMP. If someone is interested to port this to numpy, their wouldn't be any dependency problem. No license problem as Theano license have the same license as NumPy. The speed difference is significant, but I don't recall numbers. Fred ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] Suggestion: Port Theano RNG implementation to NumPy
I won't go in the discussion of which RNG is better for some problems. I'll just tell why we pick this one. We needed a parallel RNG and we wanted to use the same RNG on CPU and on GPU. We discussed with a professor in our department that is well know in that field(Pierre L'Ecuyer) and he recommanded this one for our problem. For the GPU, we don't want an rng that have too much register too. Robert K. commented that this would need refactoring of numpy.random and then it would be easy to have many rng. Fred On Tue, Feb 18, 2014 at 10:56 AM, Matthieu Brucher matthieu.bruc...@gmail.com wrote: Hi, The main issue with PRNG and MT is that you don't know how to initialize all MT generators properly. A hash-based PRNG is much more efficient in that regard (see Random123 for a more detailed explanation). From what I heard, if MT is indeed chosen for RNG in numerical world, in parallel world, it is not as obvious because of this pitfall. Cheers, Matthieu 2014-02-18 15:50 GMT+00:00 Sturla Molden sturla.mol...@gmail.com: AFAIK, CMRG (MRG31k3p) is more equidistributed than Mersenne Twister, but the period is much shorter. However, MT is getting acceptance as the PRNG of choice for numerical work. And when we are doing stochastic simulations in Python, the speed of the PRNG is unlikely to be the bottleneck. Sturla Frédéric Bastien no...@nouiz.org wrote: Hi, In a ticket I did a coment and Charles suggested that I post it here: In Theano we have an C implementation of a faster RNG: MRG31k3p. It is faster on CPU, and we have a GPU implementation. It would be relatively easy to parallize on the CPU with OpenMP. If someone is interested to port this to numpy, their wouldn't be any dependency problem. No license problem as Theano license have the same license as NumPy. The speed difference is significant, but I don't recall numbers. Fred ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion -- Information System Engineer, Ph.D. Blog: http://matt.eifelle.com LinkedIn: http://www.linkedin.com/in/matthieubrucher Music band: http://liliejay.com/ ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] Suggestion: Port Theano RNG implementation to NumPy
I won't dive into the discussion as well, except to say that parallel RNGs have to have specific characteristics, mainly to initialize many RNGs at the same time. I don't know how MRG31k3p handles this, as the publications was not very clear on this aspect. I guess it falls down as the other from that time (http://dl.acm.org/citation.cfm?id=1276928). BTW, Random123 works also on GPU and can use intrinsics to be also faster than usual congruent RNGs (see http://www.thesalmons.org/john/random123/papers/random123sc11.pdf table 2). Matthieu 2014-02-18 16:00 GMT+00:00 Frédéric Bastien no...@nouiz.org: I won't go in the discussion of which RNG is better for some problems. I'll just tell why we pick this one. We needed a parallel RNG and we wanted to use the same RNG on CPU and on GPU. We discussed with a professor in our department that is well know in that field(Pierre L'Ecuyer) and he recommanded this one for our problem. For the GPU, we don't want an rng that have too much register too. Robert K. commented that this would need refactoring of numpy.random and then it would be easy to have many rng. Fred On Tue, Feb 18, 2014 at 10:56 AM, Matthieu Brucher matthieu.bruc...@gmail.com wrote: Hi, The main issue with PRNG and MT is that you don't know how to initialize all MT generators properly. A hash-based PRNG is much more efficient in that regard (see Random123 for a more detailed explanation). From what I heard, if MT is indeed chosen for RNG in numerical world, in parallel world, it is not as obvious because of this pitfall. Cheers, Matthieu 2014-02-18 15:50 GMT+00:00 Sturla Molden sturla.mol...@gmail.com: AFAIK, CMRG (MRG31k3p) is more equidistributed than Mersenne Twister, but the period is much shorter. However, MT is getting acceptance as the PRNG of choice for numerical work. And when we are doing stochastic simulations in Python, the speed of the PRNG is unlikely to be the bottleneck. Sturla Frédéric Bastien no...@nouiz.org wrote: Hi, In a ticket I did a coment and Charles suggested that I post it here: In Theano we have an C implementation of a faster RNG: MRG31k3p. It is faster on CPU, and we have a GPU implementation. It would be relatively easy to parallize on the CPU with OpenMP. If someone is interested to port this to numpy, their wouldn't be any dependency problem. No license problem as Theano license have the same license as NumPy. The speed difference is significant, but I don't recall numbers. Fred ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion -- Information System Engineer, Ph.D. Blog: http://matt.eifelle.com LinkedIn: http://www.linkedin.com/in/matthieubrucher Music band: http://liliejay.com/ ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion -- Information System Engineer, Ph.D. Blog: http://matt.eifelle.com LinkedIn: http://www.linkedin.com/in/matthieubrucher Music band: http://liliejay.com/ ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] Suggestion: Port Theano RNG implementation to NumPy
Matthieu Brucher matthieu.bruc...@gmail.com wrote: Hi, The main issue with PRNG and MT is that you don't know how to initialize all MT generators properly. A hash-based PRNG is much more efficient in that regard (see Random123 for a more detailed explanation). From what I heard, if MT is indeed chosen for RNG in numerical world, in parallel world, it is not as obvious because of this pitfall. It is possible to solve this by using a set of independent MT generators, one per thread. Independence in this case means that the characteristic polynomials are relatively prime to each other: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dgene.pdf Undortunately the DCMT code was LGPL, not BSD, I don't know if this has changed. Sturla ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] Suggestion: Port Theano RNG implementation to NumPy
On 18.02.2014 17:47, Sturla Molden wrote: Matthieu Brucher matthieu.bruc...@gmail.com wrote: Hi, The main issue with PRNG and MT is that you don't know how to initialize all MT generators properly. A hash-based PRNG is much more efficient in that regard (see Random123 for a more detailed explanation). From what I heard, if MT is indeed chosen for RNG in numerical world, in parallel world, it is not as obvious because of this pitfall. It is possible to solve this by using a set of independent MT generators, one per thread. Independence in this case means that the characteristic polynomials are relatively prime to each other: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dgene.pdf Undortunately the DCMT code was LGPL, not BSD, I don't know if this has changed. I just checked. The file dcmt0.6.1b.tgz, available from http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html, contains this license: ---8--- Copyright (C) 2001-2009 Makoto Matsumoto and Takuji Nishimura. Copyright (C) 2009 Mutsuo Saito All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS AS IS AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Cheers, Andreas. ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Re: [Numpy-discussion] Suggestion: Port Theano RNG implementation to NumPy
Andreas Hilboll li...@hilboll.de wrote: On 18.02.2014 17:47, Sturla Molden wrote: Undortunately the DCMT code was LGPL, not BSD, I don't know if this has changed. I just checked. The file dcmt0.6.1b.tgz, available from http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html, contains this license: Fantastic :-) For speed we could just pre-compute parameters for a set of N generators, up to some reasonable number. (By the way, this generator is also used by NVidia, so it can be used on a GPU.) Sturla ___ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
