Random Number Generator

Background

Random Number generators are commonly used in computers for applications such as:

Games- for choosing an opponent's next move or a next card to draw.
Machine Learning - for choosing initial 'guess' values for regression analysis.
Testing - random stimulus can be used for regression testing of IP or software.
- This can be useful for preventing a designer from testing only "safe" sequences, such as only common or expected use cases.
- However, over-reliance on random stimulus can also be a sign of a poor test strategy and is a sign that the tester doesn't understand the design or its weaknesses.

Common Generation Methods

Common methods of generating random numbers are:

Counters, such as taking the lowest bits of a constantly changing signal like a timer. SSH uses this to generate keys by counting time between keypresses.
Generator functions, such as Y = (A*Y' + B) mod C.
- This is good for deterministic but "apparently random" sequences.
- Y' is the previous value of Y.
- This typically works best if A, B and C are large prime numbers.

In this project I use Route Ring Oscillators. A Route ring Oscillator is essentially an odd number of NOT gates chained together. This is a structure commonly used for chip parametrics and scribe structures and allows process engineers to measure how fast transistors are actually transitioning and how voltage, temperature, process variations and assembly factors affect those transitions.

Since there are variations in the toggle times between individual logic cells and the ways they are routed, each route ring oscillator will toggle at a different rate. So a set of 32 route-ring oscillators could be used to generate one 32-bit random value. As long as the chain of logic does not produce a path considerably longer than the clock cycle time, there is no reason we shouldn't have a new random value on every clock cycle.

Source Code

PYNQ Random Number Generator github

Experience

I was able to proof-of-concept this - the barriers I faced were:

Since the design couldn't close timing, I had to apply ALLOW_COMBINATIONAL_PATHS property to my RROs.
Since I was staging NOT gates together, I had to apply DONT_TOUCH to make sure the tool didn't optimize away an even number of NOT gates from each RRO.
Since I was using generate statements, I had to figure out how the actual instances were 'unrolled'.

I was able to get a basic random number generation working:

root@pynq:/home/xilinx# python3 
Python 3.6.5 (default, Apr  1 2018, 05:46:30) 
[GCC 7.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from pynq import Overlay
>>> ol = Overlay("PYNQRandomNumberGenerator.bit")
>>> hex(ol.RNGModuleTop_0.read(4))
'0xffffffff'
# Turn on enable 
>>> ol.RNGModuleTop_0.write(0,1)   
>>> hex(ol.RNGModuleTop_0.read(4))
'0xf8f30c01'
>>> hex(ol.RNGModuleTop_0.read(4))
'0xf0cf3ad'

Further Study

I do notice some 'clumping' - f's and 0's, so my next steps would be to review the schematic and make sure I am properly DONT_TOUCHing the cells so they don't get optimized away and then tweaking the chain length (maybe make it 7 or 9 inverters). Making the individual RRO elements longer would increase stability and bit-to-bit variation but would reduce the transition frequency. Making the chain shorter would increase the risk of the inverters entering a race condition.

As a further analysis step, there are plenty of random number analysis techniques that could be applied given time. Most of them involve:

Determining if the numbers form a uniform distribution? Did I get the same number of 1's, 2's, 259's, 300's?
Determining if there is any pattern to the individual bits? I.E. Do bits in any position often stay 1 or 0 for more than 1 cycle in a row?
- If they do not toggle at all, the route ring oscillator may be too slow or a race condition may be present.
- If they always toggle, your sampling rate may be an even multiple of your toggle rate.