On Wed, Nov 10, 2010 at 11:33 AM, Lauri Alanko wrote:

So a naive implementation of split would be:

split g = (mkGen seed, g') where (seed, g') = random g

Just to be clear, that is the same as Burton Smith's original proposal that Simon mentioned at the outset, right? Specifically, Smith's proposal is yours instantiated with a crypto based PRNG? So, except for the silliness of generating 128 random bits to make an Int, the following would implement the strategy using the "crypto" package on Hackage, correct? -------------------------------------------------- import Codec.Encryption.AES import Data.LargeWord import System.Random data RNG = RNG Word128 Word128 deriving Show next128 (RNG k c) = (encrypt k c, RNG k (c+1)) instance RandomGen RNG where next g = (fromIntegral n, g') where (n,g') = next128 g split g@(RNG k c) = (g', RNG n 0) where (n,g') = next128 g -------------------------------------------------- The reason I brought up AES-NI was that doing AES in hardware would allow about an 8X improvement over the best software implementation (~2 cycles per byte encrypted). Comparison would be warranted, but perhaps it could make the crypto based PRNG efficient enough for day-to-day use. Best, -Ryan

perhaps performance? Is this approach less robust with a faster, non-cryptographic RNG?

Yes, I don't understand that either. Is there a reason that using a weaker PRNG in this case is WORSE than using it in the non-splitting case? Is that why there is more of an impetus to use the cryptographic approach in this case? Anyway, taking for granted that the Burton approach is a useful thing to have implemented, I started developing a package for this stuff -- AES based RNG including both a haskell implementation and wrapping an AESNI-based C one . I haven't posted it to Hackage yet, but you can find the git repository here: https://github.com/rrnewton/intel-aes If you build with cabal and run the benchmark-intel-aes-rng executable, it will give you a breakdown like this: How many random numbers can we generate in a second on one thread? Cost of rdtsc (ffi call): 83 Approx getCPUTime calls per second: 205,640 Approx clock frequency: 3,306,891,339 First, timing with System.Random interface: 193,178,901 random ints generated [constant zero gen] 14,530,358 random ints generated [System.Random stdGen] 16,346 random ints generated [BurtonGenSlow/reference] 32,965 random ints generated [BurtonGenSlow] Comparison to C's rand(): 118,766,285 random ints generated [rand/store in C loop] 114,668,028 random ints generated [rand / Haskell loop] 114,675,116 random ints generated [rand/store Haskell] At the moment this is Haskell-only, I haven't included the wrapped Intel assembly code library yet. As you can see, the pure-Haskell AES based RNG (BurtonGenSlow) is pretty slow. Would anyone else be interested in running those RNG testing tools (diehard, big crush) on this to make sure it is working correctly? Also I'd be happy if anyone with a performance-oriented-eye would like to take a look at what's going on. Both for the sake of the serial performance (above) and because the parallel performance is currently *mysterious* (see below). I figure one of the main reasons for splittable RNG is deterministic parallel computations. Thus it's important that all threads be able to run the RNG efficiently. Right now, if you look at SimpleRNGBench.hs I'm just running the same RNG on numCapabilities threads. Yet with that simple test I'm running into problems, summarized thus: * I get substantial (3X) variance in program performance on consecutive runs. * I see a minor hit in performance adding -threaded, but going from -N1 to -N4 (even with a single-thread of work) yields a big hit in performance and increase in variance. * -N4 with four actual threads of work is actually pretty good for the pure haskell version. All four threads on my nehalem 3.33ghz can maintain 93% of their throughput in the serial case. BUT the variance problem persists. * I run a busy-wait loop that measures cpu frequency... and this seems to get messed up in threaded mode (even with -qm -qa). I don't know why. * I cannot killThread a haskell thread (forkIO or forkOS) that is currently running a divergent FFI call (safe or unsafe). (See "time_c".) You can find the details in the DEVLOG here: https://github.com/rrnewton/intel-aes/blob/master/CHANGELOG Let me know if you have any ideas. I'm going to leave the Haskell version how it is and focus on wrapping the Intel asm (which has a permissive license). Cheers, -Ryan P.S. Regarding this benchmarking -- would it be appropriate to use Criterion for this? Or is it sufficient to measure aggregate throughput as I've been doing?

Small update: I got the first results from the hardware accelerated version on a 3.33 ghz westmere machine. Right now it does twice as well as the Gladman software version, which is also twice as well as the System.Random stdgen, and 1000 times faster than a the Haskell implementation of AES that I got from the Crypto package: How many random numbers can we generate in a second on one thread? Cost of rdtsc (ffi call): 84 Approx getCPUTime calls per second: 209,798 Approx clock frequency: 3,331,093,772 First, timing with System.Random interface: 76,811,104 random ints generated [constant zero gen] 14,482,725 random ints generated [System.Random stdGen] 16,061 random ints generated [PureHaskell/reference] 32,309 random ints generated [PureHaskell] 2,401,893 random ints generated [Gladman inefficient] 15,980,625 random ints generated [Gladman] 2,329,500 random ints generated [IntelAES inefficient] 32,383,799 random ints generated [IntelAES] Comparison to C's rand(): 71,392,408 random ints generated [rand/store in C loop] 71,347,778 random ints generated [rand in Haskell loop] 71,324,158 random ints generated [rand/store in Haskell loop] This is what Burton Smith originally thought, that AES based RNG would be pretty fast and even faster with hardware acceleration. -Ryan On Mon, Jan 31, 2011 at 1:25 AM, Ryan Newton wrote:

Hi Cafe,

I've included Gladman's efficient, portable C implementation of AES generating random numbers now, and the hardware-accelerated version is working too. I'm currently seeing higher throughput for even the software based version than the builtin stdGen:

First, timing with System.Random interface: 13,051,964 random ints generated [System.Random stdGen] ~ 252 cycles/int 15,635 random ints generated [PureHaskell/reference] ~ 210,763 cycles/int 31,159 random ints generated [PureHaskell] ~ 105,757 cycles/int 2,180,488 random ints generated [Gladman inefficient] ~ 1,511 cycles/int 15,015,095 random ints generated [Gladman] ~ 219 cycles/int

That seems like a good argument for cryptographic RNGs to me!

I'm having a lot of trouble getting cabal to build/install it successfully. You can see what I've got there now. I'd be interested to know if anyone else can build it successfully. It should work -- but only by building the assembly code into a .so and assuming the build directory is /opt/intel-aes ;-).

I don't have real numbers for the hardware version yet because the Westmere machine I'm logged into is redhat 5.4 and is giving me "GLIBC_2.7 not found" errors. You can run it for correctness purposes using an emulation tool called sde (software development emulator)http://software.intel.com/en-us/articles/intel-software-development-emulator...that's based on dynamic binary translation.

-Ryan

P.S. Checkout command: git clone git://github.com/rrnewton/intel-aes.git

On Sat, Jan 29, 2011 at 8:52 AM, Ryan Newton wrote:

...

perhaps performance? Is this approach less robust with a faster,

...

non-cryptographic RNG?

Yes, I don't understand that either. Is there a reason that using a weaker PRNG in this case is WORSE than using it in the non-splitting case? Is that why there is more of an impetus to use the cryptographic approach in this case?

Anyway, taking for granted that the Burton approach is a useful thing to have implemented, I started developing a package for this stuff -- AES based RNG including both a haskell implementation and wrapping an AESNI-based C one . I haven't posted it to Hackage yet, but you can find the git repository here:

https://github.com/rrnewton/intel-aes

If you build with cabal and run the benchmark-intel-aes-rng executable, it will give you a breakdown like this:

How many random numbers can we generate in a second on one thread? Cost of rdtsc (ffi call): 83 Approx getCPUTime calls per second: 205,640 Approx clock frequency: 3,306,891,339 First, timing with System.Random interface: 193,178,901 random ints generated [constant zero gen] 14,530,358 random ints generated [System.Random stdGen] 16,346 random ints generated [BurtonGenSlow/reference] 32,965 random ints generated [BurtonGenSlow] Comparison to C's rand(): 118,766,285 random ints generated [rand/store in C loop] 114,668,028 random ints generated [rand / Haskell loop] 114,675,116 random ints generated [rand/store Haskell]

At the moment this is Haskell-only, I haven't included the wrapped Intel assembly code library yet. As you can see, the pure-Haskell AES based RNG (BurtonGenSlow) is pretty slow.

Would anyone else be interested in running those RNG testing tools (diehard, big crush) on this to make sure it is working correctly?

Also I'd be happy if anyone with a performance-oriented-eye would like to take a look at what's going on. Both for the sake of the serial performance (above) and because the parallel performance is currently *mysterious*(see below).

I figure one of the main reasons for splittable RNG is deterministic parallel computations. Thus it's important that all threads be able to run the RNG efficiently. Right now, if you look at SimpleRNGBench.hs I'm just running the same RNG on numCapabilities threads. Yet with that simple test I'm running into problems, summarized thus:

* I get substantial (3X) variance in program performance on consecutive runs. * I see a minor hit in performance adding -threaded, but going from -N1 to -N4 (even with a single-thread of work) yields a big hit in performance and increase in variance. * -N4 with four actual threads of work is actually pretty good for the pure haskell version. All four threads on my nehalem 3.33ghz can maintain 93% of their throughput in the serial case. BUT the variance problem persists. * I run a busy-wait loop that measures cpu frequency... and this seems to get messed up in threaded mode (even with -qm -qa). I don't know why. * I cannot killThread a haskell thread (forkIO or forkOS) that is currently running a divergent FFI call (safe or unsafe). (See "time_c".)

You can find the details in the DEVLOG here:

https://github.com/rrnewton/intel-aes/blob/master/CHANGELOG

Let me know if you have any ideas. I'm going to leave the Haskell version how it is and focus on wrapping the Intel asm (which has a permissive license).

Cheers, -Ryan

P.S. Regarding this benchmarking -- would it be appropriate to use Criterion for this? Or is it sufficient to measure aggregate throughput as I've been doing?

On Thu, Nov 11, 2010 at 3:13 AM, Richard Senington wrote:

I got hold of, and looked through the paper suggested in the root of this thread “Pseudo random trees in Monte-Carlo", and based upon this I have thrown together a version of the binary tree based random number generator suggested.

I would like to point out that I do not know very much about random number generators, the underlying mathematics or any subsequent papers on this subject, this is just a very naive implementation based upon this one paper.

As a question, the following code actually generates a stream of numbers that is more random than I was expecting, if anyone can explain why I would be very interested.

What do you mean more random than you were expecting? Shouldn't they be "maximally random"? BTW, nice module. Do you want to hackage it up? If not, I will.

import System.Random

data LehmerTree = LehmerTree {nextInt :: Int,                               leftBranch :: LehmerTree,                               rightBranch :: LehmerTree}

instance Show LehmerTree where   show g = "LehmerTree, current root = "++(show $ nextInt g)

mkLehmerTree :: Int->Int->Int->Int->Int->Int->LehmerTree mkLehmerTree aL aR cL cR m x0 = innerMkTree x0   where     mkLeft x = (aL * x + cL) `mod` m     mkRight x = (aR * x + cR) `mod` m     innerMkTree x = let l = innerMkTree (mkLeft x)                         r = innerMkTree (mkRight x)                     in LehmerTree x l r

mkLehmerTreeFromRandom :: IO LehmerTree mkLehmerTreeFromRandom = do gen<-getStdGen                             let a:b:c:d:e:f:_ = randoms gen                             return $ mkLehmerTree a b c d e f

This can be pure: mkLehmerTreeFromRandom :: (RandomGen g) => g -> LehmerTree

instance RandomGen LehmerTree where   next g = (fromIntegral.nextInt $ g, leftBranch g)   split g = (leftBranch g, rightBranch g)   genRange _ = (0, 2147483562) -- duplicate of stdRange

test :: IO() test = do gen<-mkLehmerTreeFromRandom           print gen           let (g1,g2) = split gen           let p = take 10 $ randoms gen :: [Int]           let p' = take 10 $ randoms g1 :: [Int]           -- let p'' = take 10 $ randoms g2 :: [Float]           print p           print p'           -- print p''

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Fri, Nov 12, 2010 at 3:33 AM, Richard Senington wrote:

In short, I am worried by the properties of this random number generator. I propose improving the testing system, and then posting both the test suite and this random generator to Hackage, unless you really want it up now in a very very preliminary form.

Yeah I think a package of randomness tests could be really useful. Cool :-)

RS

...

...

import System.Random

data LehmerTree = LehmerTree {nextInt :: Int,                               leftBranch :: LehmerTree,                               rightBranch :: LehmerTree}

instance Show LehmerTree where   show g = "LehmerTree, current root = "++(show $ nextInt g)

mkLehmerTree :: Int->Int->Int->Int->Int->Int->LehmerTree mkLehmerTree aL aR cL cR m x0 = innerMkTree x0   where     mkLeft x = (aL * x + cL) `mod` m     mkRight x = (aR * x + cR) `mod` m     innerMkTree x = let l = innerMkTree (mkLeft x)                         r = innerMkTree (mkRight x)                     in LehmerTree x l r

mkLehmerTreeFromRandom :: IO LehmerTree mkLehmerTreeFromRandom = do gen<-getStdGen                             let a:b:c:d:e:f:_ = randoms gen                             return $ mkLehmerTree a b c d e f

This can be pure:

mkLehmerTreeFromRandom :: (RandomGen g) =>  g ->  LehmerTree

...

instance RandomGen LehmerTree where   next g = (fromIntegral.nextInt $ g, leftBranch g)   split g = (leftBranch g, rightBranch g)   genRange _ = (0, 2147483562) -- duplicate of stdRange

test :: IO() test = do gen<-mkLehmerTreeFromRandom           print gen           let (g1,g2) = split gen           let p = take 10 $ randoms gen :: [Int]           let p' = take 10 $ randoms g1 :: [Int]           -- let p'' = take 10 $ randoms g2 :: [Float]           print p           print p'           -- print p''

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On 12/11/10 20:56, Bryan O'Sullivan wrote:

On Fri, Nov 12, 2010 at 12:34 PM, Luke Palmer mailto:lrpalmer@gmail.com> wrote:

Yeah I think a package of randomness tests could be really useful. Cool :-)

There are already well-established suites of very thorough PRNG tests, such as Diehard and Big Crush. Please don't invent another. Thankyou for the advice, but since I am just learning about some of this stuff, how about I have ago at implementing some of their tests?

On 11/12/10 5:33 AM, Richard Senington wrote:

It does not give the results you would want. This may have something to do with picking "good" parameters for the mkLehmerTree function. For example, using a random setup, I just got these results result expected range 16.814 expected = 16.0 (1,31) 16.191 expected = 16.5 (1,32) 16.576 expected = 17.0 (1,33) 17.081 expected = 17.5 (1,34) 17.543 expected = 18.0 (1,35)

Have you run any significance tests? I wouldn't be surprised to see +/-0.5 as within the bounds of expected randomness. I'm more worried about it seeming to be consistently on the -0.5 end of things, than I am about it not matching expectation (how many samples did you take again?). For small ranges like this, a consistent -0.5 (or +0.5) tends to indicate off-by-one errors in the generator. -- Live well, ~wren