CARNaGE Cellular Automata based Pseudo Random Numbers Generator

Hello,

I’ve written a pseudo-random number generator based on cellular automata… It uses this algorithm : http://home.southernct.edu/~pasqualonia1/ca/report.html
But I’m planning on testing other cellular automata for RNG purpose too.
I’d like to have some feedback on this. It runs quite well on my GTX 260. I get these results :
[b]Nb Samples : 10000000.000000
time : 5.656000 msec
Samples per second = 1.768034E+09 ~ 1768033875.375345

Press ENTER to exit…[/b]

Still behind the Mersenne Twister project… :/

I’m not sure if the timer measurements are correct though, since the screen freezes during execution :/
I tested the output files with ENT (http://www.fourmilab.ch/random/) and another random numbers testing software called “RNGmeter” (http://comscire.com/Downloads/). They both give me good results.
Here is one of the ENT run I did on a 10 million 32bit samples using ENT:
[b]Entropy = 7.999996 bits per byte.

Optimum compression would reduce the size
of this 40000000 byte file by 0 percent.

Chi square distribution for 40000000 samples is 216.10, and randomly
would exceed this value 96.32 percent of the times.

Arithmetic mean value of data bytes is 127.5038 (127.5 = random).
Monte Carlo value for Pi is 3.141688514 (error 0.00 percent).
Serial correlation coefficient is -0.000177 (totally uncorrelated = 0.0).[/b]

RNGmeter gives me a “24.1+” score, while it gives a “24.3+” score to one of the diehard CD random files…

Anyway… Here is the SVN repository for the project : http://code.google.com/p/carnge/
Tell me if it works for you :)

Thanks

~ svn checkout [url="http://carnge.googlecode.com/svn/trunk/"]http://carnge.googlecode.com/svn/trunk/[/url] carnge-read-only ~ cd carnge-read-only/
~/carnge-read-only $ make
Makefile:52: …/…/common/common.mk: No such file or directory
make: *** No rule to make target `…/…/common/common.mk’. Stop

Actually I didn’t work on the Linux build :/

Place the directory in your PATH_TO_CUDA_SDK\C\src directory… This might fix the error. But I doubt the Makefile will work straight away, since I didn’t modify it (it comes from the “template” project)

I made the assumption it was supposed to work since there was a makefile :)
Post back if you correct it and I will try again.

No problem :)

Okay… The Makefile is corrected. It works.

Hmm, the makefile still references …/…/common/common.mk
I have checked out your trunk, and …/…/ won’t look the same for me as for you.

$ make
Makefile:52: …/…/common/common.mk: No such file or directory
make: *** No rule to make target `…/…/common/common.mk’. Stop.

Edit: I’ve got rev 5.

That’s because the folder is meant to be put in the /src folder of the CUDA SDK… That’s because I don’t know any way of making a working Makefile for CUDA, so I just took the one bundled with the “template” project.

This will work:

Change this to point to the location of the SDK

SDK_LOC=$(HOME)/NVIDIA_CUDA_SDK_2.2
all: carnageTest

carnageTest:
nvcc -O3 -o carnageTest carnage.cu carnageTest.cu -I$(SDK_LOC)/common/inc -L$(SDK_LOC)/lib -lcutil

Okay… I modified it (Rev. 6). Thanks :P

Ok, after setting sdk_loc it now builds :)
Can’t start any new kernel at the moment, because I’ve recently upgraded the drivers and need to reboot, which in turn won’t happen until the current kernels finish.

Is it running well ?

Well… It appears that, as I forgot to wait for kernels termination, my timer readings were all wrong.
Performance is crap :/ ( 4MSamples/s )
Needs more work…

Okay… I modified the whole project. It now uses a VERY SIMPLE totalistic cellular automata in shared memory…
I got a throughput of 4.77 GSamples/sec, while the nVidia MT gives me 2.71 GSamples/sec on my GTX260.

Repository for the project is still here:
http://code.google.com/p/carnge/

It “passes” quite well the ENT test:

[b]Entropy = 7.999998 bits per byte.

Optimum compression would reduce the size
of this 96000000 byte file by 0 percent.

Chi square distribution for 96000000 samples is 255.98, and randomly
would exceed this value 47.10 percent of the times.

Arithmetic mean value of data bytes is 127.5157 (127.5 = random).
Monte Carlo value for Pi is 3.141366250 (error 0.01 percent).
Serial correlation coefficient is 0.000060 (totally uncorrelated = 0.0).[/b]

As for the diehard tests, that’s another story…
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: POSSIBLY WEAK at < 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Bit Distribution Test
Assessment: PASSED at > 5% for RGB Generalized Minimum Distance Test
Assessment: PASSED at > 5% for RGB Generalized Minimum Distance Test
Assessment: PASSED at > 5% for RGB Generalized Minimum Distance Test
Assessment: PASSED at > 5% for RGB Generalized Minimum Distance Test
Assessment: PASSED at > 5% for RGB Permutations Test
Assessment: PASSED at > 5% for RGB Permutations Test
Assessment: PASSED at > 5% for RGB Permutations Test
Assessment: POSSIBLY WEAK at < 5% for RGB Permutations Test
Assessment: POOR at < 1% for RGB Permutations Test
Assessment: PASSED at > 5% for RGB Permutations Test
Assessment: PASSED at > 5% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: POOR at < 1% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: POSSIBLY WEAK at < 5% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: POOR at < 1% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: POSSIBLY WEAK at < 5% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: PASSED at > 5% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: POOR at < 1% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: POOR at < 1% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: FAILED at < 0.01% for RGB Lagged Sum Test
Assessment: PASSED at > 5% for Diehard Birthdays Test
Assessment: PASSED at > 5% for Diehard 32x32 Binary Rank Test
Assessment: PASSED at > 5% for Diehard 6x8 Binary Rank Test
Assessment: PASSED at > 5% for Diehard Bitstream Test
Assessment: PASSED at > 5% for Diehard OPSO
Assessment: PASSED at > 5% for Diehard OQSO Test
Assessment: PASSED at > 5% for Diehard DNA Test
Assessment: PASSED at > 5% for Diehard Count the 1s (stream) Test
Assessment: POSSIBLY WEAK at < 5% for Diehard Count the 1s Test (byte)
Assessment: POSSIBLY WEAK at < 5% for Diehard Parking Lot Test
Assessment: PASSED at > 5% for Diehard Minimum Distance (2d Circle) Test
Assessment: PASSED at > 5% for Diehard 3d Sphere (Minimum Distance) Test
Assessment: POSSIBLY WEAK at < 5% for Diehard Squeeze Test
Assessment: PASSED at > 5% for Diehard Runs Test
Assessment: PASSED at > 5% for Diehard Runs Test
Assessment: PASSED at > 5% for Diehard Craps Test
Assessment: POOR at < 1% for Diehard Craps Test
Assessment: FAILED at < 0.01% for Marsaglia and Tsang GCD Test
Assessment: FAILED at < 0.01% for Marsaglia and Tsang GCD Test
Assessment: PASSED at > 5% for STS Monobit Test
Assessment: PASSED at > 5% for STS Runs Test
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for STS Serial Test (Generalized)
Assessment: PASSED at > 5% for Lagged Sum Test

I should test another neihborhood for the totalistic CA, but the dieharder tests take toooo much time to perform, like several hours, so i don’t know…